Joan: /* Versió Z80 */

2017-07-13T23:28:19Z

Versió Z80

Pàgina nova

=Introducció=
'''NOTA''': segueixo el projecte:

'''Simplest possible homebrew Z80 8-bit computer''':
*https://www.youtube.com/watch?v=CS44XJt_gYc&t=68s (amb botó que dispara els pulsos del rellotge)
*https://www.youtube.com/watch?v=kSRZ2_V9SgM (amb rellotge)
*http://nuclear.mutantstargoat.com/hw/z80micro/

Però es comenten altres projectes
*http://cpuville.com/Z80.htm
*https://www.allthingsmicro.com/index.php/projects/build-a-z80-based-computer
*http://zx80.netai.net/grant/z80/SimpleZ80.html

=Components=
*Z84C0006 -> és el Z80 que pot funcionar a 6MHz (IC 6MHZ Z80 CMOS CPU 40-DIP)
*74HC14 -> Circuito Integrado Hex Schmitt Trigger Inverter DIP14
*74HC574N -> TIPO D FLIP-FLOP, 74HC574, DIP20 TEXAS INSTRUMENTS SN74HC574N
*28C16 -> Memoria Eeprom 16K -> 24LC16 o 24LC64
*NE555

Jo tenia experiència amb la memòria 24LC256 (que té 8 pins). És una memòria de 256Kb = 32KBx8bits, amb 3 pins (A0 A1 A2) per llegir o escriure les dades, però es direcciona amb el protocol I2C ( 2-wire serial interface bus), els pins SCL i SDA. Però això no és el que jo vull. El que jo vull és un xip on pugui direccionar els 10 bits del bus de direccions, i els 8 bits del bus de dades del 80, i aquest és el 28C16, que té 24 pins (DIP24).
===Compres===
*http://www.ebay.es/itm/Z84C0006PEC-Z80-B-CPU-CMOS-6-MHz-DIP40-/361046393388?hash=item54100ac22c:g:4tkAAOSwEK9UD2G1
11,53e (1 unitat)
*http://www.ebay.es/itm/10pcsx-74HC14AP-IC-DIP14-/322202332948?hash=item4b04c16f14:g:CTIAAOSw-YVXk6LA
7e (10 unitats)
*http://www.ebay.es/itm/D-TYPE-FLIP-FLOP-74HC574-DIP20-Part-TEXAS-INSTRUMENTS-SN74HC574N-/351041614108?hash=item51bbb5f11c:g:uy8AAOxyBvZTPxet
7e (2 unitats)
*http://www.ebay.es/itm/AT28C16-25-Integrated-Circuit-CASE-DIP24-/401092271449?hash=item5d62f65d59:g:qIgAAOSwHxVW8AAm
12e (1 unitat)

Necessito sockets per la memòria.1 per al programador, i una altra per la placa. 10 x 24-pin Dip / Dil Pcb Ic Socket: 7e (2 unitats)
*http://www.ebay.es/itm/261998168513

===74HC14: Hex Schmitt Trigger Inverter===
[[Fitxer:870047-DI1.gif | thumbnail]]
Circuito Integrado Hex Schmitt Trigger Inverter DIP14
*https://es.wikipedia.org/wiki/Disparador_Schmitt

El Schmitt Trigger usa la histéresis para prevenir el ruido que podría tapar a la señal original y que causaría falsos cambios de estado si los niveles de referencia y entrada son parecidos.

El schmitt trigger hace uso de la histéresis, que es la tendencia a conservar el nivel lógico hasta que no se produzca un cambio brusco. De esta manera se previene el ruido que podría tapar a la señal original y que causaría falsos cambios de estado si los niveles de referencia y entrada son parecidos.
===74HC574N: Octal D-type flip-flop, positive edge-trigger, 3-state===
[[Fitxer:Flip-flop-tipo-d-74hc574.jpg | thumbnail]]
Són Flip-Flops tipus D. N'hi ha 8. La transició es fa quan el clock passa de low a high. Hi ha un pin per ficar la sortida a alta impedància (Z) i deshabilitar.

The typical use for such a chip is in a microprocessor system to gate the system databus into an I/O device only when the specific I/O address is decoded.

The 74HC574; 74HCT574 is an 8-bit positive-edge triggered D-type flip-flop with 3-state outputs. The device features a clock (CP) and output enable (OE) inputs. The flip-flops will store the state of their individual D-inputs that meet the set-up and hold time requirements on the LOW-to-HIGH clock (CP) transition. A HIGH on OE causes the outputs to assume a high-impedance OFF-state. Operation of the OE input does not affect the state of the flip-flops. Inputs include clamp diodes. This enables the use of current limiting resistors to interface inputs to voltages in excess of VCC.
*https://en.wikipedia.org/wiki/Flip-flop_(electronics)
The D flip-flop is widely used. It is also known as a "data" or "delay" flip-flop. The D flip-flop captures the value of the D-input at a definite portion of the clock cycle (such as the rising edge of the clock). That captured value becomes the Q output. At other times, the output Q does not change.[22][23] The D flip-flop can be viewed as a memory cell, a zero-order hold, or a delay line.

Truth table:
<pre>
Clock D Qnext
Rising edge 0 0
Rising edge 1 1
Non-Rising X Q
</pre>
===Memòria 28C16 EEPROM 2KBx8 = 16Kb (CMOS)===
[[Fitxer:28c16.gif | thumbnail]]
*At28c16-15pc -> seria 150ns d'accés
*At28c16-25pc -> seria 250ns d'accés

'''NOTA'''. Les memòries de 64K (28C64) són més fàcils de trobar en el eBay, i més barates. 28C32 no existeix. La compatibilitat de pins entre 28C16 i 28C64 és quasi!

Fer el programador per gravar la informació en aquesta EPROM està discutit aquí: [[Programador_EEPROM_amb_Arduino]]

=Construcció. PCB amb CNC, doble capa=
[[Fitxer:Z80 mini.png | thumbnail | v2, hi ha un error]]
Parteixo del projecte original (carpeta ''z80micro1-rev1/''), i retoco la pcb (''_v2'') per tal de fer més gruixudes les pistes, fins allà on pugui. A més, faré tres ponts, i així elimino pistes que eren molt llargues i primes. És una PCB de doble capa, i els forats coincideixen perfectament, fent 4 forats de referència amb la broca de 1mm (i filferro de 1mm).

En el '''v2''' he fet un error, i és que partint del projecte original em vaig carregar les línies de contorn, i que en realitat és un poligon. Això vol dir que en el resultat final no m'ha sortit el ''auto ratsnest'', és a dir que tots els grounds estan desconnectats entre sí. Malament. Jo he d'obtenir unes plaques amb unes superfícies de ground ben grosses, tant en el top com en el bottom. No cal que tots els ''plates'' del ground estiguin connectats entre si (en el top i en el bottom), sinó que han d'estar connectats entre el top i el bottom. En qualsevol cas, és fàcil veure la continuïtat de tot el GND.

Per fer el ratsnest i els GND està explicat a [[Eagle_CadSoft#Ratsnest.2C_fer_el_GND_ben_gros]]

'''v3'''. He fet el ratsnest. He fresat 3 plaques. En la primera em vaig equivocar al fer la volta, els drills no coincidien. Això ja ho tinc solucionat. Però aquesta és la que he aconseguit una més bona definició de les pistes primes (pistes de 16, tot i que en la v4 les he fet de 24). He tingut problemes amb les broques V-shape de 10º, que tenen tendència a trencar-se. Aquestes proves les he fet amb la pcb2gcode amb una profunditat de 0,3mm (el valor per defecte és de 0,2mm), i això fa que es mengi una mica més de coure. La última prova és la vàlida, tot i que m'ha quedat unes pistes massa primes (les de 16), i puc tenir problemes al soldar.

'''v4''' (TBD). He implementat vàries millores. He eliminat les pistes de 16mils i les he ficat a 24mils (les pistes que passen entre els pins del xip, 24mils és suficient). He comprat unes broques de 20º, que espero que no es trenqui com les de 10º, i tindran més precisió que les de 30º. En el pcb2gcode he ficat depth=0,2mm (valor per defecte) en comptes de 0,3mm. Es menjarà menys coure i les pistes hauran de quedar més bé, tot i que hauré de repassar detingudament el resultat.

'''v5a'''. He fet servir mètode de la planxa i àcid. Ha anat força, el mètoe de la planxa eś eficient, tot i que he malmès la placa. He fet servir una combinació de CNC i planxa que s'ha demostrat bastant efectiva. Primer faig els drills de la placa (amb els 4 forats de referència, també a 0,65-0,7mm). Aleshores amb el mètode de la planxa faig les dues cares. Trec el paper (difícil saber quan has de parar), i ataco amb àcid i aigua oxigenada (correcta, però difícil saber quan has de parar. Si et passes, poden quedar les pistes massa primes). De totes maneres, encara que he malmès la placa, és una bona opció.

'''v5b'''. És la primera versió que he construït i ha funcionat (fent servir CNC). He tingut problemes amb les soldadures fredes. D'una banda, tinc un soldador de punta fina de 11 W que va bé, però les soldadures són massa fredes. D'altra banda, tinc soldadors de 26W i 60W però les puntes són massa gruixudes (tot i que en algunes pistes ja és suficient). He corregit un parell d'errors. Hi havia una soldadura freda en la senyal D3, en una soldadura que quedava molt amagada.

He demanat un soldador de punta fina de 26W.

No oblidar-se de soldar les pistes del top que estan unides als xips. He tingut problemes per soldar les pistes del TOP amb els sòcals dels xips (si no faig servir sòcal sinó el xip directament, aleshores no ha de representar cap problemsa). Hi ha dues solucions.
*1. La que he implementat és fer ponts de manera que uneixo les pistes de dalt i de baix, amb soldadures fàcils. El sòcal el soldo només per baix, i ja està. El milllor és que els ponts tinguin pads el més ample possibles i separats dels pins, per facilitar la soldadura.
2. L'altra solució és fer servir sòcals tornejats, un soldador de punta ben fina i fil prim. Ens hem d'assegurar que la connexió sigui bona i segura. Amb sòcals tornejats podem accedir al sòcal per fer la soldadura. Si no tenim sòcals tornejats també es pot fer, s'ha d'entrar només la meitat del sòcal per tal de fer una mica d'espai per fer la soldadura, però és més difícil.

En la v5 (he fet vàries proves) finalment he aconseguit una bona placa amb broca V-shape de 20 graus, i el gruix de les pistes òptim està explicat a:
[[Fer_plaques_PCB_amb_màquina_CNC#Gruixos_de_les_pistes_per_a_CNC]]

'''v6''' (TODO). Treure els ponts i les vies. Això vol dir soldar amb més precisió amb un bon soldador de punta fina. sòcals tornejats.

==RESET==
RESET must be active for a minimum of three full clock cycles before a reset operation is complete. Al principi semblava que no funcionava el RESET amb el manual clock, però llegint la documentació està clar. Amb el RESET apretat, clicar tres vegades el botó de clock.

=Ensamblador Z80. Z80 Assembler=
(carpeta ''projectes/Z80'')
*http://www.nongnu.org/z80asm/
*http://savannah.nongnu.org/projects/z80asm
<pre>
z80asm-1.8.tar.gz

$ ./z80asm --help
Usage: ./z80asm [options] [input files]

Possible options are:
-h --help Display this help text and exit.
-V --version Display version information and exit.
-v --verbose Be verbose. Specify again to be more verbose.
-l --list Write a list file.
-L --label Write a label file.
-p --label-prefix prefix all labels with this prefix.
-i --input Specify an input file (-i may be omitted).
-o --output Specify the output file.
-I --includepath Add a directory to the include path.
Please send bug reports and feature requests to <shevek@fmf.nl>
</pre>

Els primers codis que vull compilar i gravar en la EEPROM són els que es mostren en el projecte del mini-ordinador Z80:
*http://nuclear.mutantstargoat.com/hw/z80micro/

'''exemple1.asm''':
<pre>
org $0
ld a, 1
loop: out (255), a
rlca
jr loop
</pre>

Per obtenir el binari:
<pre>
$ ./z80asm -I /headers/ -o examples/exemple1.bin -i examples/exemple1.asm
$ od -Ax -t x1 exemple1.bin
000000 3e 01 d3 ff 07 18 fb
000007
</pre>
Aquests valors també els puc veure amb la utilitat gràfica '''ghex'''
==Z80Pack: ensamblador i simulador==
És un altre ensamblador, que a més té simulador:
*http://www.autometer.de/unix4fun/z80pack/ftp/
Descarrego la versió 1.34. Les carpetes ''z80asm/'' i ''z80sim/'' es compilen amb ''make'' sense problemes.

Per otenir el binari dels meus dos exemples he de tabular el ORG (o senzillament no posar-lo), i sense el símbol del dòllar:
<pre>
ORG 0
ld a, 1
loop: out (255), a
rlca
jr loop
</pre>
i obtinc el mateix binari
<pre>
./z80asm -fb exemple1.asm
$ od -Ax -t x1 exemple1.bin
000000 3e 01 d3 ff 07 18 fb
000007
</pre>
Si compilo sense l'opció ''-fb'' obtenim:
<pre>
$ ./z80asm exemple1b.asm
Z80 - Assembler Release 1.7, Copyright (C) 1987-2016 by Udo Munk
Pass 1
Read exemple1b.asm
Pass 2
Read exemple1b.asm
0 error(s)
$ od -Ax -t x1 exemple1b.bin
000000 ff 00 00 3e 01 d3 ff 07 18 fb
00000a
</pre>
I això té la seva importància perquè és aquest fitxer el que va bé per al simulador.

===Simulador Z80===
*http://www.autometer.de/unix4fun/z80pack/doc_sim_install.html
<pre>
$ cd ~/z80pack-1.34/z80sim/srcsim
$ make
$ ./z80sim -z
>>>
</pre>
Aleshores ja podem carregar el programa amb l'opció '''r''', i és important veure com '''START:0000''' (això ho hem aconseguit compilant sense l'opció -fb):

Un cop estem en el prompt del simulador ('''>>>'''), l'opció ''g'' és per arrencar el programa, i amb el ''ENTER'' (single step program) vaig avançant pel programa. Amb l'opció ''t, trace'' puc veure vàries instruccions a l'hora.
<pre>
$ ./z80sim -z

####### ##### ### ##### ### # #
# # # # # # # # ## ##
# # # # # # # # # # #
# ##### # # ##### ##### # # # #
# # # # # # # # #
# # # # # # # # # #
####### ##### ### ##### ### # #

Release 1.34, Copyright (C) 1987-2017 by Udo Munk

CPU speed is unlimited
>>> r exemple1b.bin
Loader statistics for file exemple1b.bin:
START : 0000
END : 0006
LOADED: 0007

>>>

PC A SZHPNC I IFF BC DE HL A'F' B'C' D'E' H'L' IX IY SP
0002 01 000000 00 00 0000 0000 0000 0000 0000 0000 0000 0000 0000 ffff
OUT (FF),A
>>>

PC A SZHPNC I IFF BC DE HL A'F' B'C' D'E' H'L' IX IY SP
0004 01 000000 00 00 0000 0000 0000 0000 0000 0000 0000 0000 0000 ffff
RLCA
>>>

PC A SZHPNC I IFF BC DE HL A'F' B'C' D'E' H'L' IX IY SP
0005 02 000000 00 00 0000 0000 0000 0000 0000 0000 0000 0000 0000 ffff
JR 0002
>>>

PC A SZHPNC I IFF BC DE HL A'F' B'C' D'E' H'L' IX IY SP
0002 02 000000 00 00 0000 0000 0000 0000 0000 0000 0000 0000 0000 ffff
OUT (FF),A
>>>
</pre>
Fixem-nos que encara que hem afegit tres bytes al principi del fitxer (''ff 00 00''), quan fem dump de la memòria (opció -d) aquests tres bytes no apareixen, per tant ho fem bé:
<pre>
>>> ? -> per veure les opcions

>>> d
Adr 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f ASCII
0000 - 3e 01 d3 ff 07 18 fb ec 29 cd ba ab f2 fb e3 46 >.......)......F
</pre>
Per visualitzar o canviar un registre, ho fem amb '''x''':
<pre>
>>> x a
A = 04 : 01
</pre>
'''compte''': el nom del registre en minúscules. Hem de posar el nou valor, si és el mateix, repetim el valor.

Amb tot això, aquest simulador m'haurà d'anar bé per programar l'algorisme de les Torres de Hanoi.

=Programes de prova. Ensamblador Z80=
En aquest projecte es proposen dos exercicis simples, on la sortida són 8 LEDs. En el primer exemple els LEDs es van desplaçant, quan arriba al final torna al principi. En el segon exemple, quan el led encès arriba al final, canvia de direcció-

'''exemple 1''':
<pre>
org $0
ld a, 1
loop: out (255), a
rlca
jr loop
</pre>
*'''org $0'''
'''ORG''' is an abbreviation for "origin". ORG is merely an indication on where to put the next piece of code/data, related to the current segment. '''ORG''' it's the location in memory where you want the binary program to be loaded to, if any. '''ORG''' is used to set the assembler location counter.

*'''ld a, 1'''
The LD instruction is used to put the value from one place into another place.
Per tant, fiquem un 1 en el registre A (registre general)

*'''loop:'''
És un label, al qual podem cridar dins del mateix loop. Per tant, ens servirà per fer bucles. El programa s'executarà sense fi.

*'''out (255), a'''
OUT: Writes the value of the second operand into the port given by the first operand.

En el registre A hi havíem ficat un 1. En aquest cas, què significa el port (255)? La idea que es persegueix és que el contingut de A es correspon amb l'encesa dels LEDs.

Llegint en el '''Z80 CPU User Manual''', pàgina 306. '''OUT (n), A'''. The operand n is placed on the bottom half (A0 through A7) of the address bus to select
the I/O device at one of 256 possible ports. The contents of the Accumulator (Register A) also appear on the top half (A8 through A15) of the address bus at this time. Then the byte
contained in the Accumulator is placed on the data bus and written to the selected peripheral device.

Per tant, en el bus de direccions (A0...A7) hem de veure FF (que és el port, però que per nosaltres no té cap sentit), i el contingut de l'acumuladror l'hem de veure en el bus de dades (que és el que interessa), i també a A8...A15 (tot i que nosaltres només tenim A8, A9 i A10. Com que fiquem el contingut de l'acumulador en el bus de dades, això és una operació d'escriptura (WR). Si ens fixem en l'esquema, el clock del LATCH està unit al WR del Z80. Per tant, cada vegada que fem una operació d'escriptura en el bus de dades es fa un latch del bus de dades.

*'''rlca'''
Performs RLC A much quicker, and modifies the flags differently. S,Z, and P/V are preserved, H and N flags are reset.

'''RLC''': 8-bit rotation to the left. The bit leaving on the left is copied into the carry, and to bit 0.
Per tant, amb RLCA el que fem és una rotació cap a l'esquerra de 8 bits. Originalment teníem un 1. El 1 passa cap a l'esquerra:
<pre>
00000001
00000010
00000100
...
</pre>
*'''jr loop'''
'''JR''': Relative jumps to the address. This means that it can only jump between 128 bytes ahead or behind. Can be conditional or unconditional. JR takes up one less byte than JP, but is also slower. Weigh the needs of the code at the time before choosing one over the other (speed vs. size).
Per tant, tornem al loop (quan té un sol argument és un jump sense condició)

La idea doncs del codi és que anem fent una rotació cap a l'esquerra d'un bit en el registre A, i el contingut de A el bolquem al port (255), que està associat al display dels LEDs. En conclusió, hem de veure com roten els LEDs.

'''exemple 2''': Un exercici una mica més interessant
<pre>
org $0
ld a, 1
left: out (255), a
rlca
cp 128
jr z, right
jr left
right: out (255), a
rrca
cp 1
jr z, left
jr right
</pre>
'''CP''' is a subtraction from A that doesn't update A, only the flags it would have set/reset if it really was subtracted. Per tant, en fer la substracció és possible que el flag Z (el bit de Zero en el registre F) estigui a 0 o a 1.
jr z, right: jr és el jump, i quan té dos arguments, el primer argument és la condició. Mirem el flag Z, si és 1, anem a right.

La idea del codi doncs és que el led que s'encén es desplaça cap a l'esquerra o cap a la dreta. Per decidir el canvi de direcció hem de fer una resta, i mirar el flag Z.

Pas a pas el funcionament és el següent.
<pre>
ld a, 1 -> A: 00000001
left: out (255), a -> mostrem el LED: 0000000X
rlca -> A: 00000010
cp 128:
10000000 - 00000010 = (128-2) = 126 = 0x7E = 01111110 (però és una resta sense portar-ne, no afecta al flag Z)
jr z, right -> com que Z=0, no es fa el jump de right, sinó fem el jump de left, per tant, continuem en el mateix bucle.

...
rlca -> A: 01000000
cp 128:
10000000 - 01000000 = (128-64) = 64 = 01000000 (però és una resta sense portar-ne, no afecta al flag Z)
jr z, right -> com que Z=0, no es fa el jump de right, sinó fem el jump de left, per tant, continuem en el mateix bucle.

rlca -> A: 10000000 = (128-128) = 0 = 00000000 (però ara sí que tenim el flag Z=1)
jr z, right -> com que Z=1, ara sí que es fa el jump de right, i per tant saltem a l'altre bucle.

right: out (255), a -> mostrem el LED: X0000000
rrca -> A: 01000000
cp 1:
01000000 - 00000001 = (64-1) = 63 = 0x3F = 00111111 (però és una resta sense portar-ne, no afecta al flag Z)
jr z, left -> com que Z=0, no es fa el jump de left, sinó fem el jump de right, per tant, continuem en el mateix bucle (estem en el bucle de right).
...
rrca -> A: 00000010
cp 1:
00000010 - 00000001 = (2-1) = 1 = 0x01 (però és una resta sense portar-ne, no afecta al flag Z)
jr z, left -> com que Z=0, no es fa el jump de left, sinó fem el jump de right, per tant, continuem en el mateix bucle (estem en el bucle de right).

rrca -> A: 00000001
cp 1:
00000001 - 00000001 = (1-1) = 0 = 0x01 (però ara sí que tenim el flag Z=1)
jr z, left -> com que Z=1, ara sí que fa el jump de left i saltem a l'altre bucle, i tornem a començar.
</pre>
==Codi màquina. Opcodes del Z80==
Tenim els dos programes en ensamblador. S'ha d'obtenir el codi màquina (els bytes que ficarem dins de la EEPROM), i veure com els bytes generats es corresponen amb els opcodes del Z80. És a dir, les instruccions estan associades a unes direccions de memòria que el Z80 entén.

Compilem els dos programes d'exemple que tenim:
<pre>
$ ./z80asm -I ~/Z80/z80asm-1.8/headers/ -o exemple1.bin -i examples/exemple1.asm
$ ./z80asm -I ~/Z80/z80asm-1.8/headers/ -o exemple2.bin -i examples/exemple2.asm
</pre>
I els bytes que obtenim són:
<pre>
$ od -Ax -t x1 exemple1.bin
000000 3e 01 d3 ff 07 18 fb

$ od -Ax -t x1 exemple2.bin
000000 3e 01 d3 ff 07 fe 80 28 02 18 f7 d3 ff 0f fe 01
000010 28 f0 18 f7

</pre>
Repassem els dos exemples:

''exemple1.asm'':
<pre>
org $0
ld a, 1
loop: out (255), a
rlca
jr loop
</pre>

''exemple2.asm'':
<pre>
org $0
ld a, 1
left: out (255), a
rlca
cp 128
jr z, right
jr left
right: out (255), a
rrca
cp 1
jr z, left
jr right
</pre>
I aquí tenim el resum dels opcodes que es fan servir:
*http://z80-heaven.wikidot.com/opcode-reference-chart (en aquesta taula queda més clar)
*http://www.z80.info/z80oplist.txt
<pre>
3E LD A,&00 - SRL (HL) SRL (IY+0)
D3 OUT (&00),A - SET 2,E set 2,(iy+0)->e -
07 RLCA - RLC A rlc (iy+0)->a MOS_ARGS
18 JR &4546 - RR B rr (iy+0)->b -
FE CP &00 - SET 7,(HL) SET 7,(IY+0) [z80]
28 JR Z,&4546 - SRA B sra (iy+0)->b -
0F RRCA - RRC A rrc (iy+0)->a MOS_FF0F
</pre>
*podem veure com en l'exemple1 la direcció de ''loop'' és ''FB''
*podem veure com les direccions de ''left'' i ''right'' són ''F7'' i ''02''

És a dir, cada instrucció té un codi (per ex, ''LD'' és ''3E''), i d'aquesta manera el Z80 sap quina instrucció ha d'executar. A més, donada una instrucció sap si li segueix cap argument, 1 ó 2 arguments.
=Torres de Hanoi en Z80 assembler=
[[Fitxer:Hanoi.jpg | thumbnail]]
==Algorisme==
L'algorisme de les Torres de Hanoi és un exemple típic de recursivitat:
*https://www.tutorialspoint.com/data_structures_algorithms/tower_of_hanoi.htm
I en aquest enllaç tenim l'algorisme recursiu en molts llenguatges (sortida orientada a text), entre ells ''360 Assembly'', però no Z80 assembly:
*https://rosettacode.org/wiki/Towers_of_Hanoi#360_Assembly

'''Algorisme''':
<pre>
Els passos a seguir són:
Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest

A recursive algorithm for Tower of Hanoi can be driven as follows −

START
Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF

END Procedure
STOP
</pre>
I aquí tenim la versió ''X86 assembly'' en dues versions, amb push/pop a una pila i, millor', sense push/pop:
*http://www.mastropaolo.com/2005/06/01/hanoi-towers-as-a-pure-recursion-benchmark-part-2-algorithm-optimizations/
Es compara la velocitat amb C++, i resulta ser el doble de ràpid.
==Versió x86 Assembly==
<pre>
mov ebx, from
mov ecx, to
mov edx, use
mov eax, howmany
xor esi, esi

call HanoiAsm
mov retcode, esi
jmp EndHanoiAsm
HanoiAsm:
dec eax
jz NextLoop
push eax
xchg ecx, edx
call HanoiAsm
xchg ecx, edx
xchg edx, ebx
pop eax
call HanoiAsm
xchg edx, ebx
NextLoop:
inc esi
ret
EndHanoiAsm:
</pre>

'''Assembly, no push/pop''':
<pre>
push ebp
mov ebx, from
mov ecx, to
mov edx, use
xor esi, esi

mov eax, howmany
mov ebp, esp
shl eax, 2
sub ebp, eax
sar eax, 2

call HanoiAsm
pop ebp
mov retcode, esi
jmp EndHanoiAsm
HanoiAsm:
dec eax
jz NextLoop
xchg ecx, edx
call HanoiAsm
mov eax, esp
xchg ecx, edx
sub eax, ebp
xchg edx, ebx
sar eax, 2
call HanoiAsm
xchg edx, ebx
NextLoop:
inc esi
ret
EndHanoiAsm:
</pre>
Explicació:
<pre>
mov ebx, from
mov ecx, to
mov edx, use
mov eax, howmany -> eax serà la variable temporal per guardar els discos que falten
xor esi, esi

call HanoiAsm -> fem la primera crida
mov retcode, esi -> movem el contingut de esi a retcode. Què és retcode?
jmp EndHanoiAsm -> sortim del programa

HanoiAsm:
dec eax -> decrementa el contingut de eax en 1 unitat. eax és el howmany
jz NextLoop -> j<condition>. jz <label> (jump when last result was zero). Aquesta és la condició de què quan disk=1 sortim
push eax -> guarda a la pila el valor de eax, que és el valor actual de num de discs per col.locar
xchg ecx, edx -> Exchanges the contents of the destination (first) and source (second) operands
call HanoiAsm -> tornem a cridar: recursivitat
xchg ecx, edx -> tornem a intercanviar
xchg edx, ebx
pop eax -> recuperem de la pila el valor de eax
call HanoiAsm -> tornem a cridar: recursivitat
xchg edx, ebx -> tornem a intercanviar

NextLoop:
inc esi -> incrementem esi en una unitat i tornem. esi és un registre de propòsit general
ret -> retorna de la crida de HanoiAsm

EndHanoiAsm: -> sortim del programa

http://www.cs.virginia.edu/~evans/cs216/guides/x86.html

mov ebx, from -> fica el contingut de from a ebx
xor esi, esi -> fica esi=0 quan esi sigui igual a ell mateix
</pre>
==Versió Z80==
Per compilar i simular:
<pre>
joan@joan-portatil:~/projectes/Z80/z80pack-1.34/z80asm$ ./z80asm hanoi_v1.asm
$ cp hanoi_v1.bin ../z80sim/srcsim/

joan@joan-portatil:~/projectes/Z80/z80pack-1.34/z80sim/srcsim$ ./z80sim -z
</pre>
I la versió amb Z80, finalment! ja he trobat la solució. '''hanoi_v1.asm''':
<pre>
ORG 0
numdisks EQU 3
source EQU 4
aux EQU 2
dest EQU 1

ld a, numdisks
ld b, source
ld c, aux
ld d, dest
call HanoiAsm
ld e,(255) ;mostrem
jp Fi

HanoiAsm:
dec a ;decrementem, si a=0 (vol dir que a valia 1), anem a la rutina NextLoop, tornem a deixar a=1, i sortim
jr z, NextLoop
push af

ld h,c
ld l,d
ld d,h
ld c,l

call HanoiAsm

pop af
inc a
ld e,a ;mostrem
ld e,b ;mostrem
ld e,c ;mostrem
ld e,(0) ;mostrem
dec a

ld h,b
ld l,d
ld d,h
ld b,l

ld h,d
ld l,c
ld c,h
ld d,l

call HanoiAsm

ld h,b
ld l,c
ld c,h
ld b,l

ret

NextLoop:
inc a
ld e,a ;mostrem
ld e,b ;mostrem
ld e,d ;mostrem
ld e,(0);mostrem
ret

Fi:
</pre>
La solució està fixant-se en el registre E. Surten valors que s'han d'interpretar. Per exemple, per a N=2
<pre>
E=1 -> moure el primer disc des de la posició 4 (el primer peg, source) fins la posició 2 (2n peg, aux)
E=4
E=2

E=2 -> moure el segon disc des de la posició 4 (el primer peg, source) fins la posició 1 (3r peg, destí)
E=4
E=1

E=1 -> moure el primer disc des de la posició 2 (el segon peg, aux) fins la posició 1 (3r peg, destí)
E=2
E=1
</pre>
I per què he escollit els valors de 4,2,1 en els registres b,c i d? Doncs perquè visualment podré veure la solució amb els meus 8 leds. El que he de veure en la sortida a mida que vagi fent cicles de rellotge és la solució:
<pre>
xxxxxxxx -> significa que ve un moviment
.......x
.....x..
......x.

xxxxxxxx -> significa que ve un moviment
......x.
.....x..
.......x

xxxxxxxx -> significa que ve un moviment
......x.
......x.
.......x
</pre>
'''hanoi_v2.asm''':
<pre>
ORG 0
numdisks EQU 3
source EQU 4
aux EQU 2
dest EQU 1

ld a, numdisks
ld b, source
ld c, aux
ld d, dest
call HanoiAsm
ld e,(255) ;mostrem
out (255), e
jp Fi

HanoiAsm:
dec a ;decrementem, si a=0 (vol dir que a valia 1), anem a la rutina NextLoop, tornem a deixar a=1, i sortim
jr z, NextLoop
push af

ld h,c
ld l,d
ld d,h
ld c,l

call HanoiAsm

pop af
inc a
ld e,a ;mostrem
out (255), e
ld e,b ;mostrem
out (255), e
ld e,c ;mostrem
out (255), e
ld e,(0) ;mostrem
out (255), e
dec a

ld h,b
ld l,d
ld d,h
ld b,l

ld h,d
ld l,c
ld c,h
ld d,l

call HanoiAsm

ld h,b
ld l,c
ld c,h
ld b,l

ret

NextLoop:
inc a
ld e,a ;mostrem
out (255), e
ld e,b ;mostrem
out (255), e
ld e,d ;mostrem
out (255), e
ld e,(0) ;mostrem
out (255), e
ret

Fi:
</pre>
<pre>
$ od -Ax -t x1 hanoi_v2.bin
000000 ff 00 00 3e 03 06 04 0e 02 16 01 cd 12 00 1e ff
000010 d3 ff c3 4c 00 3d 28 28 f5 61 6a 54 4d cd 12 00
000020 f1 3c 5f d3 ff 58 d3 ff 59 d3 ff 1e 00 d3 ff 3d
000030 60 6a 54 45 62 69 4c 55 cd 12 00 60 69 4c 45 c9
000040 3c 5f d3 ff 58 d3 ff 5a d3 ff 1e 00 d3 ff c9
00004f
</pre>
{{Autor}}, juny 2017

Home-Built Z-80 Computer - Historial de revisió

Joan: /* Versió Z80 */