[Assembly] Microprocessors contest: Merge Sort

[Z80Fan]

Salve programmatori !

In questo thread potrete divertirvi a programmare il vostro processore preferito (meglio, la vostra architettura di processore preferita) in assembly per implementare il famoso algoritmo del Merge Sort (http://it.wikipedia.org/wiki/Merge_sort)

Le "regole" sono:

1. I dati di input sono 27. Potete scegliere quelli che volete.
2. Potete scegliere qualsiasi architettura vogliate
3. Il codice non deve essere legato a qualche particolare macchina (per esempio, il codice per il 68000 non deve essere pensato per girare apposta su un Amiga) - questa regola non vale se il processore è la macchina (ad esempio sistemi vecchi e vecchissimi tipo edsac, pdp ecc...)
4. Di conseguenza non dovete presupporre coprocessori o altre periferiche esterne al processore
5. Per le regole sopra, il codice deve essere eseguito da solo, quindi niente sistema operativo, niente librerie ecc... (non vi preoccupate di come il programma è stato inserito in memoria, fate finta che sia lì e basta)
6. Il risultato dell'elaborazione lo dovete lasciare in un array in memoria, non bisogna visualizzarlo o inviarlo a qualche periferica.
7. Il codice dovrebbe far uso il più possibile delle caratteristiche del processore
8. Sarebbe carino se il listato fosse commentato

Per farvi capire come dovrebbe apparire il codice, mostro un esempio di un codice per processore MIPS per fare la somma degli elementi corrispondenti e mettere il risultato in un terzo vettore.

; Programma che somma gli elementi corrispondenti di 2 vettori in un terzo

	.data
v1:	.word32	1, 2, 3, 4, 5, 6, 7, 8, 9, 10
v2:	.word32	10, 20, 30, 40, 50, 60, 70, 80, 90, 100
v3:	.word32	0, 0, 0, 0, 0, 0, 0, 0, 0, 0

	.text
main:
	xor r1, r1, r1		; azzero l'indice per i vettori
	ori r2, r0, 10		; carico il numero di elementi dei vettori in R2

ciclo:
	lw r3, v1(r1)		; carico gli operandi
	lw r4, v2(r1)

	add r3, r3, r4		; eseguo l'addizione
	addi r2, r2, -1		; decremento il contatore (lo ho messo qua per sfruttare la pipeline, risparmio quasi 30 cicli di clock per tutta l'esecuzione)

	sw r3, v3(r1)		; scrivo il risultato
	
	addi r1, r1, 4		; incremento il puntatore

	bne r2, r0, ciclo	; ripeto se non-zero

Vedete che il listato dovrebbe essere ben indentato e commentato.
Se nel vostro codice avete inserito un'ottimizzazione di cui siete particolarmente orgogliosi, potete scrivere un commento nel listato o una descrizione nel post.

Come già detto, potete scegliere qualsiasi architettura, non importa quanto vecchia o strana.

Questo è tutto, vi auguro una buona programmazione!

------------- Versioni Disponibili -------------

• Motorola 680x0 #3
• Intel x86 #5
• MIPS #11
• Zilog Z80 #14
• MOS 6502 #25
• ARM #34

[cdimauro]

Per semplicità inizialmente proverò a realizzare una versione che ordini un array di byte. Poi passerò a uno di longword (32 bit).

Cercando di essere fedele all'algoritmo descritto nel link che hai postato.

[cdimauro]

Ecco la versione per Motorola 68000:

*-----------------------------------------------------------
* Program    : Merge sort
* Written by : Cesare Di Mauro
* Date       : 26-03-2010
* Description:
*-----------------------------------------------------------

NumeroElementi EQU 27

	ORG	$1000
Start:
	lea	a(pc),a0	; a0 = puntatore all'inizio dell'array da ordinare (a)
	lea	b(pc),a1	; a1 = puntatore all'inizio dell'array temporaneo da usare (b)
	moveq	#0,d0	; left = 0
	moveq	#NumeroElementi - 1 ,d1	; right = numero di elementi dell'array
	bsr.s	MergeSort	; Richiama la routine
	trap	#15	; Esci dall'applicazione


; mergesort (a[], left, right)
;    if (left < right) then
; 	center := (left + right) / 2
; 	mergesort(a, left, center)
; 	mergesort(a, center+1, right)
; 	merge(a, left, center, right)

; a0 = puntatore all'inizio dell'array da ordinare (a)
; a1 = puntatore all'inizio dell'array temporaneo da usare (b)
; d0 = left
; d1 = right

MergeSort:
	cmp.l	d1,d0	; left >= right?
	bge.s	.Exit	; Sì, esci
	movem.l	d2,a1-6,-(sp)	; Salva i registri che verranno sporcati
	move.l	d0,d2	; center = left
	add.l	d1,d2	; center = left + right
	lsr.l	#1,d2	; center = (left + right) / 2
	exg.l	d1,d2	; Scambia right (d1) e center (d2)
	bsr.s	MergeSort	; mergesort(a = a0, left = d0, center = d1)
	exg.l	d1,d2	; Scambia center (d1) e right (d2)
	exg.l	d0,d2	; Scambia left (d0) e center (d2)
	addq.l	#1,d0	; center = center + 1
	bsr.s	MergeSort	; mergesort(a = a0, center+1 = d0, right = d1)
	subq.l	#1,d0	; center = center - 1	
	exg.l	d0,d2	; Scambia center (d0) e left (d2)
	bsr.s	Merge	; merge(a = a0, left = d0, center = d2, right = d1)
	movem.l	(sp)+,d2,a1-6	; Ripristina i registri salvati
.Exit:
	rts


; merge (a[], left, center, right)  
;     i := left
;     j := center + 1
;     k := 0
;  
;     while ((i <= center) && (j <= right)) do
;        if (a[i] <= a[j])
;         then
;           b[k] := a[i]
;           i ?:= i + 1
;  	else
;  	   b[k] := a[j]
;  	   j := j + 1  
;        k := k + 1
;     end while
;  
;     while (i <= center) do
;  	  b[k] := a[i]
;  	  i := i + 1
;  	  k := k + 1
;     end while
;  
;     while (j <= right) do
;  	  b[k] := a[j] 
;  	  j := j + 1
;          k := k + 1
;     end while
;  
;     for k := left to right do
;  	a[k] := b[k - left]

; a0 = puntatore all'inizio dell'array da ordinare (a)
; a1 = puntatore all'inizio dell'array temporaneo da usare (b)
; d0 = left
; d1 = right
; d2 = center

Merge:  
	lea	(a0,d0.l),a2	; i = a0 + left
	lea	1(a0,d2.l),a3	; j = a0 + center + 1
	lea	(a0,d0.l),a4	; "left" = a0 + left
	lea	(a0,d1.l),a5	; "right" = a0 + right
	lea	(a0,d2.l),a6	; "center" = a0 + center
	cmp.l	a6,a2		; i > "center"?
	bhi.s	.ExitLoop1	; Sì, esci dal ciclo
	cmp.l	a5,a3		; j > "right"?
	bhi.s	.ExitLoop1	; Sì, esci dal ciclo
.Loop1
	cmp.b	(a3)+,(a2)+	; a[i] > a[j]?; i = i + 1; j = j + 1
	bhi.s	.Greather	; Sì, salta
	move.b	-1(a2),(a1)+	; b[k] = a[i]; k = k + 1
	subq.l	#1,a3		; j = j - 1
	cmp.l	a6,a2		; i <= "center"?
	ble.s	.Loop1		; Sì, salta all'inizio del ciclo
	bra.s	.ExitLoop1	; No, esci dal ciclo
.Greather:
	move.b	-1(a3),(a1)+	; b[k] = a[j]; k = k + 1
	subq.l	#1,a1		; i = i - 1
	cmp.l	a5,a3		; j <= "right"?
	ble.s	.Loop1		; Sì, salta all'inizio del ciclo
.ExitLoop1:
	cmp.l	a6,a2		; i > "center"?
	bhi.s	.ExitLoop2	; Sì, esci dal ciclo
.Loop2:
	move.b	(a2)+,(a1)+	; b[k] = a[i]; k = k + 1; i = i + 1
	cmp.l	a6,a2		; i <= "center"?
	ble.s	.Loop2		; Sì, continua a copiare
.ExitLoop2:
	cmp.l	a5,a3		; j > "center"?
	bhi.s	.ExitLoop3	; Sì, esci dal ciclo
.Loop3:
	move.b	(a3)+,(a1)+	; b[k] = a[j]; k = k + 1; j = j + 1
	cmp.l	a5,a3		; j <= "right"?
	ble.s	.Loop3		; Sì, continua a copiare
.ExitLoop3:
	sub.l	d1.l,a1		; b = punta all'inizio dell'array temporaneano
.Loop4
	move.b	(a1)+,(a4)+	; a[k] = b[k - left]; k = k + 1
	cmp.l	a1,a4		; k <= "right"?
	ble.l	.Loop4		; Sì, continua a copiare.
	rts

; Variabili:

a	dc.b 	27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
b	ds.b	NumeroElementi

	END	Start

Non l'ho testato, ma a naso dovrebbe andare. Eventualmente se notate degli errori, fatemi sapere che li correggo.

Come già detto, lavora su un array di byte (di 23 elementi).

[Z80Fan]

Molto bene!
Hai seguito lo pseudocodice su wikipedia, lo copio qui in caso lo cambiassero:

mergesort (a[], left, right)
    if (left < right) then
        center = (left + right) / 2
        mergesort(a, left, center)
        mergesort(a, center+1, right)
        merge(a, left, center, right)



merge (a[], left, center, right)  
    i = left
    j = center + 1
    k = 0

    while ((i <= center) && (j <= right)) do
        if (a[i] <= a[j]) then
            b[k] = a[i]
            i = i + 1
        else
            b[k] = a[j]
            j = j + 1  
        k = k + 1
    end while

    while (i <= center) do
        b[k] = a[i]
        i = i + 1
        k = k + 1
    end while

    while (j <= right) do
        b[k] = a[j] 
        j = j + 1
        k = k + 1
    end while

    for k = left to right do
        a[k] = b[k - left]

Verso stasera verificherò (portandolo in c++) che l'algoritmo funzioni correttamente, poi mi metterò a scriverne la versione Z80, e successivamente una versione MIPS (che comincerò a studiare). Tra l'altro stò completando un computerino tipo Altair dotato di Z80, sarebbe carino vedere il merge sort lavorare direttamente sull'hardware

[rеpne scasb]

■

[cdimauro]

Originariamente inviato da Z80Fan

Molto bene!
Hai seguito lo pseudocodice su wikipedia,

Sì, perché serve un "base comune" per poter confrontare le implementazioni per gli altri microprocessori.

Di Merge sort non esiste soltanto quel codice.

Verso stasera verificherò (portandolo in c++) che l'algoritmo funzioni correttamente, poi mi metterò a scriverne la versione Z80, e successivamente una versione MIPS (che comincerò a studiare). Tra l'altro stò completando un computerino tipo Altair dotato di Z80, sarebbe carino vedere il merge sort lavorare direttamente sull'hardware

Quindi ti farai carico di 2 implementazioni. Bravo.

[Z80Fan]

Hey ragazzi io sono un paio di giorni che lavoro sul merge sort Z80, ma non riesco a farlo funzionare. Cioè, a scriverlo ci riesco, ma quando provo ad eseguirlo (per la precisione su un simulatore di IMSAI 8080 con cpu Z80 ), o mi va in ciclo infinito, o mi salta a locazioni impossibili, o mi si blocca per un opcode invalido (in base alle modifiche che faccio). Penso sia un problema di stack, ma non riesco a trovare l'errore, perchè il codice è perfetto...

[cdimauro]

Postalo lo stesso. Io il mio mica l'ho verificato: a meno di bug, dovrebbe funzionare, e gli eventuali bug semplicemente si sistemano.

[Z80Fan]

Originariamente inviato da cdimauro

Postalo lo stesso. Io il mio mica l'ho verificato: a meno di bug, dovrebbe funzionare, e gli eventuali bug semplicemente si sistemano.

D'accordo, lo posto; il fatto e che non mi piaceva postare un codice che porta il mio nome e che non funziona
Cmq per portarlo sullo z80 ho dovuto fare una piccola modifica all'algoritmo base: poichè lo z80 non è dotato di istruzioni per indicizzare array tramite base+offset, invece di passare l'array e l'indice nell'array gli passo direttamente tutto il puntatore; poi lo ho modificato in modo da dover usare solo confronti di uguaglianza/disuguaglianza tra i puntatori:

void merge( char *left, char *center, char *right)
{
     center++;
     right++;
     char *tempCenter = center;
     char *ptemp = vtemp; // vtemp=vettore temporaneo

     while( (left!=tempCenter) && (center!=right) )
     {
          if( *left < *center )
          {
               *ptemp = *left;
               ptemp++;
               left++;
          }
          else
          {
               *ptemp = *center;
               ptemp++;
               center++;
          }
     }

// idem per gli altri 2 while

Questa è la mia implementazione attuale:

; Implementazione dell'algortimo Merge Sort per processore Zilog Z80
; Autore: Z80Fan
; Data 26/3/2010

NUM_ELEMENTI: equ 27

debug: macro x
	push AF
	ld A, x
	cpl
	out (0FFh), A
	pop AF
	endm

ORG 0
jp main

ORG 4
; --- Vettore Dati e vettore temporaneo ---
vdati:	db	27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1	; vettore dei dati
vtemp:	db	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0						; vettore temporaneo
tempCenterL: db 0		; locazione temporanea per "merge"
tempCenterH: db 0

; --- Programma principale ---
main:
	di		; disable interrupts

	debug 1

	ld SP, 0FFF0h
	ld BC, vdati
	ld DE, (vdati+NUM_ELEMENTI-1)

	call mergesort

	debug 0AAh

	halt		; fermo il processore

; --- Funzione Merge ---
; Ingresso:
;   BC = left
;	DE = center
;	HL = right
; Uscita:
;	niente

; void merge (char *left, char *center, char *right)

merge:
	push AF
	push DE
	push IX
	push HL
	push BC

	inc DE

	ld (tempCenterL), DE
	
	inc HL
	
	ld IX, vtemp

while:
	ld A, (tempCenterL)
	cp C
	jp Z, fuoriWhile
	ld A, (tempCenterH)
	cp B
	jp Z, fuoriWhile

	ld A, E
	cp L
	jp Z, fuoriWhile
	ld A, D
	cp H
	jp Z, fuoriWhile

	; corpo While

	; if( *left < *center )
	ld A, (DE)
	push HL
	push BC
	pop HL
	cp (HL)		; tutto 'sto lavoro per non modificare il prototipo della funzione ;) (non si può fare cp (BC) )
	pop HL
	jp M, faiIf

	;corpo Else
	ld A, (DE)
	ld (IX+0), A
	inc DE
	inc IX
	jp while
	
	;corpo IF
faiIf:
	ld A, (BC)
	ld (IX+0), A
	inc BC
	inc IX
	jp while

fuoriWhile:
	; -- Fine While --

copiaLeft:
	ld A, (tempCenterL)
	cp C
	jp Z, copiaCenter
	ld A, (tempCenterH)
	cp B
	jp Z, copiaCenter

	ld A, (BC)
	ld (IX+0), A
	inc BC
	inc IX
	jp copiaLeft

copiaCenter:
	ld A, E
	cp L
	jp Z, ricopia
	ld A, D
	cp H
	jp Z, ricopia

	ld A, (DE)
	ld (IX+0), A
	inc DE
	inc IX
	jp copiaCenter

ricopia:

	pop BC
	pop HL
	push HL
	push BC

	scf
	ccf		; azzero il carry (per il sbc di dopo) (lo Z80 non ha un sub per i registri a 16 bit)
	sbc HL, BC
	inc HL
	ld C, L
	ld H, B

	pop DE	; BC / left
	push DE
	ld HL, vtemp
	ldir

	pop BC
	pop HL
	pop IX
	pop DE
	pop AF

	ret
; --- Fine Merge ---


; --- Funzione Mergesort ---
; Ingresso:
;   BC = left
;	DE = right
; Uscita:
;	niente
; Sporca il registro A

; void mergesort( char *left, char *right )

mergesort:
	; esci se (left == right)
	ld A, D
	cp B
	jp NZ, continua		; se non sono uguali le parti alte, vai subito a fare l'if
	; altrimenti controlla le parti alte
	ld A, E
	cp C
	ret Z		; ritorno (esco dalla funzione) se le parti basse sono uguali

continua:
	push HL
	push DE
	push BC

	; corpo if
	pop HL
	push HL		; HL = BC = left
	add HL, DE	; HL += DE (right)
	srl H
	rr L		; HL = HL>>2 (HL/2)
	; HL = center
	push HL
	pop DE		; DE = HL = center
	call mergesort	;mergesort(left, center)

	pop BC
	pop DE		;ripristino DE a "right"
	push DE
	push BC

	push HL
	pop BC		; BC = HL
	inc BC		; center + 1
	call mergesort	; mergesort(center+1, right)

	pop BC
	push BC		; ripristino BC a "left"
	
	ex DE, HL	; scambio DE e HL (perchè "merge" vuole "right" in HL e "center" in DE)
	call merge

	pop BC
	pop DE
	pop HL

	ret
; --- Fine Mergesort ---

[Z80Fan]

Ho fatto il codice MIPS, e crea gli stessi errori dello Z80 !!!
Penso di aver interpretato male i salti condizionati, darò un'occhiata...

[Z80Fan]

Funziona!!!
E c'ho messo pure i commenti significativi

# Implementazione dell'algoritmo Mergesort per cpu MIPS
#
# Autore: Z80Fan
# Data (di inizio): 06/04/2010
#
# Testato sotto simulatore MARS

#NUM_ELEMENTI = 27

	.data
vdati:	.word	27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
vtemp:	.space	108   #(NUM_ELEMENTI*4)

	.text

main:
	la $a0, vdati		# inizio vettore dati ( la = "load address" )
	add $a1, $0, $0		# left (si somma con 0 per trasferire da un reg. all'altro)
	addi $a2, $0, 26	# right (NUM_ELEMENTI-1)
	jal mergesort

	break 0		# fermo il simulatore

# Il MIPS ha 32 registri, di cui 30 general purpose e 2 fissi (R0 che ritorna sempre 0 e R31 che
# contiene il precedente valore del program counter dopo un salto a funzione (jal = jump and link)
# I 30 registri vengono "logicamente" suddivisi in diverse aree con diversi nomi per semplificare
# la programmazione: R1 viene riservato all'assemblatore, R2-R3 sono v0 e v1 tipo "accumulatori",
# R4-R7 sono a0-a3 argomenti per le funzioni, e R8-R15 sono t0-t7 variabili temporanee
# per la procedura. Gli altri registri hanno significati simili. Il registro R29 viene usato come
# stack pointer, anche se per via dell'architettura si può usare qualsiasi registro come sp, anzi,
# si possono usare più stack contemporaneamente.

#---------------- Funzione mergesort ----------------------------------------------------
# mergesort (a[], left, right)
# Ingresso:
#	$a0 = indirizzo di a[]
#	$a1 = left
#	$a2 = right
mergesort: 
	bge $a1,$a2, ritorna	# if(left >= right) ritorna (bge = "branch greater equal"; in realtà l'assemblatore la assembla in 2 istruzioni più semplici (slt,beq) usando il reg.1 come supporto)

	add $t0, $a1, $a2	# t0(center) = a1(left) + a2(right)
	srl $t0, $t0, 1		# t0 = t0 / 2

	# salvo i registri usati
	addi $sp, $sp, -20	# spazio per 5 registri da 4 byte ciascuno (a0, a1, a2, t0(center) e ra(link reg.) )
	sw $a0,  0($sp)		# simulo il "push" scrivendo i registri a un offset nello spazio che mi son creato prima
	sw $a1,  4($sp)		# ( sw = "store word", word = 32bit )
	sw $a2,  8($sp)
	sw $t0, 12($sp)
	sw $ra, 16($sp)

	add $a2, $t0, $0	# a2(right) = t0(center) per la prossima chiamata
	jal mergesort		# jal = "jump and link"

	lw $a1, 12($sp)		# a1(left) = center
	lw $a2,  8($sp)		# a2(right) = right
	addi $a1, $a1, 1	# center+1
	jal mergesort

	lw $a1,  4($sp)		# a1 = left
	lw $a2, 12($sp)		# a2 = center
	lw $a3,  8($sp)		# a3 = right
	jal merge

	# ripristino i registri
	lw $a0,   0($sp)
	lw $a1,   4($sp)
	lw $a2,   8($sp)
	lw $t0,  12($sp)
	lw $ra, 16($sp)
	addi $sp, $sp, 20	# rilascio lo spazio sullo stack

ritorna:
	jr $ra



#---------------- Funzione merge --------------------------------------------------------
# merge (a[], left, center, right)
# Ingresso:
#	a0 = indirizzo di a[]
#	a1 = left
#	a2 = center
#	a3 = right
# Modifica a1, a2, a3.

merge:
	sll $a1, $a1, 2
	sll $a2, $a2, 2		# moltiplico per 4 gli indici perchè ho dati a 32 bit (4 byte)
	sll $a3, $a3, 2
	add $a1, $a1, $a0	# left, center e right ora contengono a[left], a[center] e a[right]
	add $a2, $a2, $a0
	add $a3, $a3, $a0

	add $t0, $a1, $0	# t0 = indirizzo di a[i]
	addi $t1, $a2, 4	# t1 = a[center] + 1 elemento (4 byte)
	la $t2, vtemp		# t2 = indirizzo di vtemp (la = "load address")

# t0 = indirizzo di a[i]
# t1 = indirizzo di a[j]
# t2 = indirizzo di vtemp (la = "load address")

while:
	bgt $t0, $a2, copiaJ	# if( i > center ) goto fuoriWhile (bgt = "branch greater than")
	bgt $t1, $a3, copiaI	# if( j > right  ) goto fuoriWhile

	#if( a[i] <= a[j] )
	lw $v0, ($t0)		# v0 = a[i] (lw = "load word")
	lw $v1, ($t1)		# v1 = a[j]
	bgt $v0, $v1, faiElse	# if(R2 > R3) goto faiElse
	# corpo dell' if
	sw $v0, ($t2)		# sw = "store word"
	addi $t0, $t0, 4	# avanzo a[i]	
	addi $t2, $t2, 4	# incremento il puntatore b[k]
	j while			# jump while
	#corpo dell'else
faiElse:	
	sw $v1, ($t2)
	addi $t1, $t1, 4	# avanzo a[j]
	addi $t2, $t2, 4	# incremento il puntatore b[k]
	j while			# jump while

copiaI:
	bgt $t0, $a2, ricopia	#if( i > center ) goto ricopia
	lw $v0, ($t0)		# v0 = a[i]
	addi $t0, $t0, 4	# i++
	sw $v0, ($t2)		# b[k] = v0
	addi $t2, $t2, 4 	# k++
	j copiaI

copiaJ:
	bgt $t1, $a3, ricopia	# if( j > right  ) goto ricopia
	lw $v0, ($t1)		# v0 = a[j]
	addi $t1, $t1, 4	# j++
	sw $v0, ($t2)		# b[k] = v0
	addi $t2, $t2, 4	# k++
	j copiaJ

ricopia:
	la $t2, vtemp		# t2 = indirizzo di b[]
	add $t0, $a1, $0	# t0 = a[left]
for:
	bgt $t0, $a3, finito	# if(left > right) goto finito
	lw $v0, ($t2)
	addi $t2, $t2, 4
	sw $v0, ($t0)
	addi $t0, $t0, 4
	j for

finito:
	jr $ra		# ritorno dalla funzione: salto al contenuto del registro link (R31)

[cdimauro]

Non è nemmeno tanto lungo. Pensavo peggio per un RISC così "R".

[Z80Fan]

Ho avuto scarsi risultati nel cercare un simulatore Z80 degno di questo nome, stavo proprio pensando di scrivermene uno io solo per debuggare il merge sort
A proposito, ho trovato un'implementazione del quick sort per lo z80:
http://en.wikibooks.org/wiki/Algorit...80000_Assembly
(nonostante il nome, è un codice Z80 valido.)

[Z80Fan]

Il codice era perfetto si, era un problema di "linking" !!!!
( semplicemente: assemblo, passo il file binario ad un tool che mi ricava un file .hex da dare all'emulatore. Ebbene, questo tool non eseguiva un org, quindi tutti i byte successivi erano spostati di un byte in meno, ma tutte le costanti come gli indirizzi dei salti erano quelli calcolati dall'assemblatore! )

Cmq ho corretto anche altri bug che non avevo notato prima, questa versione è funzionante.

; Implementazione dell'algortimo Merge Sort per processore Zilog Z80
; Autore: Z80Fan
; Data 13/4/2010

NUMELEMENTI: equ 27

org 0
jp main

; --- Vettore Dati e vettore temporaneo ---
vdati:	db	27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1	; vettore dei dati
vtemp:	db	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0						; vettore temporaneo
tempCenterL: db 0		; locazione temporanea per "merge"
tempCenterH: db 0

; --- Programma principale ---
main:
	di		; disable interrupts

	ld SP, 0FFF0h
	ld BC, vdati
	ld DE, vtemp-1

	call mergesort

	halt		; fermo il processore

; --- Funzione Merge ---
; Ingresso:
;   BC = left
;	DE = center
;	HL = right
; Uscita:
;	niente

; void merge (char *left, char *center, char *right)

merge:
	push AF	; salvo i registri
	push DE
	push IX
	push HL
	push BC

	inc DE

	ld (tempCenterL), DE	; salvo il valore centrale incrementato di uno
	
	inc HL		; right + 1
	
	ld IX, vtemp	; in IX il puntatore al vettore temporaneo

while:

	; esci se (tempCenter == BC)
	; devo comparare 2 valori a 16 bit
	ld A, (tempCenterH)
	cp B
	jp NZ, cont1		; se non sono uguali le parti alte, vai subito avanti
	; altrimenti controlla le parti basse
	ld A, (tempCenterL)
	cp C
	jp Z, fuoriWhile		; esco dal while se le parti basse sono uguali
cont1:

	; esci se (HL == DE)
	ld A, D
	cp H
	jp NZ, cont2		; se non sono uguali le parti alte, vai subito avanti
	; altrimenti controlla le parti basse
	ld A, E
	cp L
	jp Z, fuoriWhile		; esco dal while se le parti basse sono uguali
cont2:
	; corpo While

	; if( *left < *center )
	ld A, (DE)
	push HL
	ld H, B		; HL = BC
	ld L, C
	cp (HL)		; tutto 'sto lavoro per non modificare il prototipo della funzione ;) (non si può fare cp (BC), quindi sposto BC in HL e faccio cp (HL) )
	pop HL		; ripristino HL (pop non modifica i flag quindi è ok per il jp dopo)
	jp M, faiElse

	;corpo IF
	ld A, (BC)
	ld (IX+0), A
	inc BC
	inc IX
	jp while

faiElse:
	;corpo Else
	ld A, (DE)
	ld (IX+0), A
	inc DE
	inc IX
	jp while

fuoriWhile:
	; -- Fine While --

copiaLeft:
	; esci se (tempCenter == BC)
	ld A, (tempCenterH)
	cp B
	jp NZ, cont3
	; altrimenti controlla le parti basse
	ld A, (tempCenterL)
	cp C
	jp Z, copiaCenter
cont3:
	ld A, (BC)
	ld (IX+0), A
	inc BC
	inc IX
	jp copiaLeft


copiaCenter:
	; esci se (HL == DE)
	ld A, D
	cp H
	jp NZ, cont4
	; altrimenti controlla le parti basse
	ld A, E
	cp L
	jp Z, ricopia
cont4:
	ld A, (DE)
	ld (IX+0), A
	inc DE
	inc IX
	jp copiaCenter


ricopia:
	pop BC
	pop HL
	push HL
	push BC

	scf
	ccf		; azzero il carry (per il sbc di dopo) (lo Z80 non ha un sub per i registri a 16 bit)
	sbc HL, BC
	inc HL
	ld B, H
	ld C, L

	pop DE	; BC / left
	push DE
	ld HL, vtemp
	ldir	; ldir fa: (DE)=(HL); DE++; HL++; BC--; ripeti se BC != 0

	pop BC	; ripristino i registri
	pop HL
	pop IX
	pop DE
	pop AF

	ret
; --- Fine Merge ---


; --- Funzione Mergesort ---
; Ingresso:
;   BC = left
;	DE = right
; Uscita:
;	niente
; Sporca il registro A

; void mergesort( char *left, char *right )

mergesort:
	; esci se (left == right)
	ld A, D
	cp B
	jp NZ, continua		; se non sono uguali le parti alte, continua
	; altrimenti controlla le parti basse
	ld A, E
	cp C
	ret Z		; ritorno (esco dalla funzione) se le parti basse sono uguali

continua:
	push HL
	push DE
	push BC

	; corpo if
	ld H, B
	ld L, C		; HL = BC = left
	add HL, DE	; HL += DE (right)
	srl H
	rr L		; HL = HL>>2 (HL/2)
	; HL = center
	ld D, H
	ld E, L		; DE = HL = center
	call mergesort	;mergesort(left, center)

	pop BC
	pop DE		;ripristino DE a "right"
	push DE
	push BC

	ld B, H
	ld C, L		; BC = HL
	inc BC		; center + 1
	call mergesort	; mergesort(center+1, right)

	pop BC
	push BC		; ripristino BC a "left"
	
	ex DE, HL	; scambio DE e HL (perchè "merge" vuole "right" in HL e "center" in DE)
	call merge

	pop BC
	pop DE
	pop HL

	ret
; --- Fine Mergesort ---

[Z80Fan]

up

[Z80Fan]

Non sembrano esserci troppi lettori interessati

[banryu79]

Originariamente inviato da Z80Fan

Non sembrano esserci troppi lettori interessati

[OT]
Lettori a leggere ce n'è (616 accessi in lettura, fin'ora): siete in 4 gatti a postare, semmai.

Visto l'argomento, la cosa non mi stupisce
(Forse solo una piccola percentuale di utenti del forum è in grado di/interessata a partecipare a contest in linguaggio assembly).

[MaxArt]

Originariamente inviato da Z80Fan

Non sembrano esserci troppi lettori interessati

Un tempo l'avrei fatto in assembly Z80 Ma comunque l'hai fatto tu.
Oggi, forse... per ARM?

Solo, dovrei prendermi del tempo...

[Z80Fan]

Originariamente inviato da MaxArt

Un tempo l'avrei fatto in assembly Z80 Ma comunque l'hai fatto tu.
Oggi, forse... per ARM?

Solo, dovrei prendermi del tempo...

Ecco, ci servirebbe una versione ARM Prenditi pure il tempo che ti serve

[limpid-sky]

stavo per cimentarmi ma ormai il motorola già c'è .(non avevo dubbi )