[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:

I dati di input sono 27. Potete scegliere quelli che volete.
Potete scegliere qualsiasi architettura vogliate
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...)
Di conseguenza non dovete presupporre coprocessori o altre periferiche esterne al processore
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)
Il risultato dell'elaborazione lo dovete lasciare in un array in memoria, non bisogna visualizzarlo o inviarlo a qualche periferica.
Il codice dovrebbe far uso il più possibile delle caratteristiche del processore
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 (http://www.hwupgrade.it/forum/showpost.php?p=31394756&postcount=3) #3
Intel x86 (http://www.hwupgrade.it/forum/showpost.php?p=31404469&postcount=5) #5
MIPS (http://www.hwupgrade.it/forum/showpost.php?p=31562954&postcount=11) #11
Zilog Z80 (http://www.hwupgrade.it/forum/showpost.php?p=31610651&postcount=14) #14
MOS 6502 (http://www.hwupgrade.it/forum/showthread.php?p=32373950#post32373950) #25
ARM (http://www.hwupgrade.it/forum/showpost.php?p=37426814&postcount=34) #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 :D

[rеpne scasb]

■

[cdimauro]

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 :D
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 :cool: ), 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]

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 !!! :muro:
Penso di aver interpretato male i salti condizionati, darò un'occhiata...

[Z80Fan]

Funziona!!! :yeah:
E c'ho messo pure i commenti significativi :D

# 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". :D

[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 :D
A proposito, ho trovato un'implementazione del quick sort per lo z80:
http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#Zilog_Z80000_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]

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]

Non sembrano esserci troppi lettori interessati :)Un tempo l'avrei fatto in assembly Z80 :O Ma comunque l'hai fatto tu.
Oggi, forse... per ARM? :wtf:

Solo, dovrei prendermi del tempo...

[Z80Fan]

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

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 :) )

[Z80Fan]

stavo per cimentarmi ma ormai il motorola già c'è .(non avevo dubbi :) )
Grazie cmq della partecipazione :)

[Z80Fan]

Un altro processore importante che ci manca è il 6502 / 6510.
Se trovo un buon emulatore, posso provare a codificarlo (e penso anche di averlo da qualche parte...)

[cdimauro]

http://6502asm.com/

[Z80Fan]

http://6502asm.com/

Che bello, ha anche il display a colori :D
Cmq penso che mi rivolgerò a simulatori più "professionali", ho trovato qualcosa qui:
http://www.6502.org/tools/emu/

[Z80Fan]

Dopo sforzi titanici, ho completato il mergesort 6502! :ave:

; Implementazione dell'algortimo Merge Sort per processore MOS 6502
; Autore: Z80Fan
; Data 21/6/2010

; vista l'esiguità dello spazio nello stack del 6502,
; uso un altro stack, fatto a mano, per memorizzare i parametri
; di mergesort

paramStackPtr = $200 ;Puntatore allo stack; parte subito dopo lo stack 6502
numeroElementi = 27

.START main

; macro push: prende l'indirizzo di un elemento di 1 byte locato in pagina zero
;(quindi 1 byte di indirizzo) e mette quell'elemento nel nostro stack

push .MACRO ptr
LDX paramStackOff ; carico l'offset dello stack
DEX ; faccio spazio per il byte da salvare
LDA ptr ; carico il byte da salvare
STA paramStackPtr, X ; salvo
STX paramStackOff ; salvo le modifiche allo "stack pointer"
.ENDM

; macro pop: come push solo che fa il contrario.
pop .MACRO ptr
LDX paramStackOff ; carico l'offset dello stack
LDA paramStackPtr, X ; carico il byte da ripristinare
STA ptr ; salvo
INX ; rilascio lo spazio occupato dal byte
STX paramStackOff ; salvo le modifiche allo "stack pointer"
.ENDM


; Definizione delle variabili nella pagina zero (gli offset nella pagina zero):
; per merge:
left = 0 ; parametri
center = 1
right = 2
tempCenter = 3 ; locazioni per salvare temporaneamente left e center
salvaLeft = 4

; per mergesort
; questi sono i parametri da inviare a mergesort (caricare prima di fare la chiamata)
Mleft = 5 ; indice sinistro
Mright = 6 ; indice destro

; "globali"
paramStackOff = 7 ; l'offset alla cima dello stack dei parametri
vett = 8 ; puntatore al vettore da ordinare (2 byte)
saveX = 10 ; variabile temporanea dove salvare X
saveY = 11 ; variabile temporanea dove salvare Y
saveA = 12 ; variabile temporanea dove salvare A


.ORG $1000

; Array dati
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
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,0,0

;#################################################
;#################################################
;#################################################
; funzioni
main:
;funzione per inizializzare il sistema
CLI ; disattivo interrupt
CLD ; disattivo modalità decimale
LDX #$FF ; mi assicuro che gli stack pointer siano correttamente inizializzati
STX paramStackOff ; stack pointer del nostro stack
TXS ; stack pointer 6502

LDX #0 ; porto X a zero
STX Mleft ; imposto Mleft per la prima chiamata a mergesort
LDX # numeroElementi-1
STX Mright ; imposto Mright per mergesort

LDX #$00 ; prendo la parte mano significativa dell'indirizzo di vdati
STX vett ; e lo metto in vett
LDX #$10 ; idem per quella più significativa
STX vett + 1

JSR mergesort ; chiamo il mergesort

BRK ; fermo il programma (blocca il simulatore, si può usare anche RTS)


;#################################################
;#################################################
;#################################################
merge:
; funzione merge
INC center
INC right
LDA center
STA tempCenter ; faccio in questo modo così posso testare solo l'uguaglianza/disuguaglianza e risparmiarmi controlli sul '<='
LDA left
STA salvaLeft
LDX #0 ; X contiene l'indice nel vettore temporaneo
;---------------------
while: LDA left ; while( left!=tempCenter && center!=right )
CMP tempCenter
BEQ copiaCenter ; esco dal ciclo se left == tempCenter, e finisco di copiare center
LDA center
CMP right
BEQ copiaLeft ; esco se center == right, e finisco di copiare left

LDY left
LDA (vett), Y ; vett[left]
LDY center
CMP (vett), Y ; vett[center]
BMI scriviLeft ; se ( vett[left] < vett[center] ) allora scrivi in vtemp vett[left]
;--
LDA (vett), Y ; altrimenti scrivi vett[center]
STA vtemp, X
INC center ; incrementa center
INX ; incrementa X (indice in vtemp)
JMP while

scriviLeft:
STA vtemp, X ; salva A in vtemp[k] (A è già caricato con vtemp[left])
INC left
INX
JMP while ; ripeti il ciclo
;---------------------
copiaLeft: ; copia elementi rimasti nel semi-vettore di sinistra
LDY left ; uso Y per contenere left
cicloL: CPY tempCenter ; while( left != tempCenter )
BEQ unisci ; esco dal ciclo se left == tempCenter
LDA (vett), Y ; carico da vett
STA vtemp, X ; salvo in vtemp
INX ; incremento i puntatori
INY
JMP cicloL

copiaCenter: ; copia elementi rimasti nel semi-vettore di destra
LDY center ; carico center in Y
cicloC: CPY right ; while( center != right )
BEQ unisci ; esco se center == right
LDA (vett), Y ; carico da vett
STA vtemp, X ; salvo in vtemp
INX ; incremento i puntatori
INY
JMP cicloC

;---------------------
unisci: ; prende gli elementi nel vettore temporaneo e li ricopia nel vettore normale
LDY salvaLeft ; in Y l'indice per il vettore originale
LDX #0 ; in X l'indice del vettore temporaneo
cicloU: CPY right
BEQ finito
LDA vtemp, X
STA (vett), Y
INX
INY
JMP cicloU

;---------------------

finito: RTS


;#################################################
;#################################################
;#################################################
mergesort:
;funzione mergesort (ricorsiva)
; esci se right <= left
LDA Mright
CMP Mleft
BEQ esci ; esci se uguale
BMI esci ; esci se Mright minore di Mleft (Mright-Mleft = negativo)

push Mleft ; mi salvo Mleft e Mright (non serve vett perchè non è mai modificato)
push Mright

LDA Mleft ; center = (left + right) / 2
CLC ; azzera carry
ADC Mright
LSR ; A = center

STA Mright ; metto "center" nel posto di Mright per fare la chiamata ricorsiva a mergesort, Mleft rimane invariato
JSR mergesort ; mergesort( left, center )

LDA Mright ; carico A con "center" (che era memorizzato in Mright)
STA Mleft ; memorizzo center in Mleft per la chiamata ricorsiva
INC Mleft ; center+1
pop Mright ; ripristino Mright (perchè lo ho modificato con center),
push Mright ; mantenendolo comunque nello stack
JSR mergesort ; mergesort(center+1, right)

DEC Mleft ; da center+1 ottengo center
LDA Mleft ; carico center in A
STA center ; metto center in "center" per chiamare merge
pop right ; inserisco il vecchio valore di Mright in right
pop left ; inserisco il vecchio valore di Mleft in left

LDA right ; ripristino anche Mleft e Mright per la funzione precedente
STA Mright
LDA left
STA Mleft

JMP merge ; salto a merge (trucco: quando merge farà RTS, si troverà l'indirizzo della precedente mergesort, così evitiamo di fare 2 rst di fila (quello di merge, e l'ultimo di mergesort)

esci:

RTS

[cdimauro]

In effetti è lunghetto il codice. :D

[Z80Fan]

In effetti è lunghetto il codice. :D
Già. Non sono un esperto di 6502, ma questo è il minimo che sono riuscito ad ottenere. Sicuramente la mancanza più grave è la carenza di registri, e le poche operazioni disponibili su ognuno (pensa che non c'è un'istruzione per incrementare/decrementare l'accumulatore!); i modi di indirizzamento, sono si numerosi, ma cmq molto semplici. In questo particolare programma il 6502 non da sicuramente il meglio di se. Un bubble sort sarebbe stato sicuramente più adatto.

[cdimauro]

Mumble. Strano, perché io ricordo INC e DEC per incrementare e decrementare (di uno) l'accumulatore...

[gnakko_patakko]

Ho provato a modificare la versione in assembly MIPS di Z80Fan facendo in modo che l'utente inserisca i valori interi. Purtroppo non riesco a capire se funziona. Sarebbe interessante se qualcuno di Voi riuscisse a modificare quest'ultima versione e fare in modo che stampi il vettore ordinato.

Inoltre, nella versione di Z80Fan la dimensione del vettore temporaneo era ovviamente fissata. Nel caso di quest'ultima ho lasciato il vettore temporaneo di dimensione fissata: non riesco a fare in modo che anche questo utilizzi lo stack.

#################
# SEGMENTO DATI #
#################

.data

vtemp:
.space 16 #(NUM_ELEMENTI*4)

# Prompt

numIntVettStr:
.asciiz "Numero elementi del vettore: "

intVettStr:
.asciiz "Inserisci un numero intero maggiore o uguale a zero (-1 per terminare): "

endReadStr:
.asciiz "Lettura elementi vettore terminata\n"



##################
# SEGMENTO TESTO #
##################

.text
.globl main

main:

la $a0, numIntVettStr # chiede all'untente di specificare il numero totale di
li $v0, 4 # interi da ordinare
syscall

li $v0, 5 # legge il numero di elementi del vettore e lo pone in $v0
syscall
move $s0, $v0

# Crea l'area nello stack per il vettore dati
sll $t0, $s0, 2 # Dati = malloc(N * 4)
sub $sp, $sp, $t0 # vengono riservati (N * 4) byte all'inizio dello stack
move $s1, $sp # l'inizio del vettore viene conservato in $s1

li $t0, 0 # $t0 viene utilizzato come indice del ciclo for
# e viene inizializzato a zero

# Acquisizione dei valori del vettore
read_loop:

la $a0, intVettStr # Visualizza un messaggio per richiedere un intero
li $v0, 4 # non negativo all'utente
syscall


li $v0, 5 # Acquisisce l'intero inserito dall'utente
syscall

# Se e' stato inserito il valore -1 si esce dal ciclo di lettura
beq $v0, -1, exit_read_loop

sll $t1, $t0, 2
add $t1, $s1, $t1
sw $v0, 0($t1)

addi $t0, $t0, 1 # incrementa il contatore
blt $t0, $s0, read_loop

# L'utente ha terminato l'inserimento degli interi
exit_read_loop:

# Visualizza un messaggio per informare l'utente
# che ha scelto di terminare l'inserimento dei valori
la $a0, endReadStr
li $v0, 4
syscall

add $s2, $0, $0 # left (si somma con 0 per trasferire da un reg. all'altro)
sub $s0, $s0, 1 # (numero elementi - 1)
add $s3, $0, $s0 # right = (numero elementi - 1)

jal mergesort # jump and link: l'istruzione e' usata per chiamare una procedura.
# Trasferisce il controllo, in questo caso a "mergesort", proprio
# come una istruzione di salto. Inoltre, memorizza l'indirizzo di
# ritorno nel registro $ra


li $v0, 10 # termina l'esecuzione
syscall # del programma

#######################
# PROCEDURA MERGESORT #
#######################

#################################
# mergesort (a[], left, right) #
# Ingresso: #
# $s1 = indirizzo del vettore #
# $s2 = left #
# $s3 = right #
#################################

mergesort:

bge $s2, $s3, ritorna # se l'indice di sinistra e' maggiore o uguale a quello di destra
# viene effettuato il salto a "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, $s2, $s3 # $t0(center) = $s2(left) + $s3(right), $t0 e' il centro del vettore
srl $t0, $t0, 1 # $t0 = ($t0 / 2)

# Salvataggio dei registri utilizzati

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

add $s3, $t0, $0 # $s3(right) = $t0(center) per la prossima chiamata

jal mergesort # jal = "jump and link"

lw $s2, 12($sp) # $s2(left) = center
lw $s3, 8($sp) # $s3(right) = right
addi $s2, $s2, 1 # (center + 1)

jal mergesort

lw $s2, 4($sp) # $s2 = left
lw $s3, 12($sp) # $s3 = center
lw $s4, 8($sp) # $s4 = right

jal merge

# Ripristino dei registri salvati in precedenza

lw $s1, 0($sp)
lw $s2, 4($sp)
lw $s3, 8($sp)
lw $t0, 12($sp)
lw $ra, 16($sp)
addi $sp, $sp, 20 # rilascio lo spazio sullo stack

ritorna:

jr $ra


#######################
# PROCEDURA MERGE #
#######################

####################################
# merge ([], left, center, right) #
# Ingresso: #
# $s1 = indirizzo del vettore #
# $s2 = left #
# $s3 = center #
# $s4 = right #
# Modifica $s2, $s3, $s4. #
####################################

merge:

sll $s2, $s2, 2
sll $s3, $s3, 2 # moltiplico per 4 gli indici perchè ho dati a 32 bit (4 byte)
sll $s4, $s4, 2
add $s2, $s2, $s1 # left, center e right ora contengono $s1[left], $s1[center] e $s1[right]
add $s3, $s3, $s1
add $s4, $s4, $s1

add $t0, $s2, $0 # t0 = indirizzo di $s1[i]
addi $t1, $s3, 4 # t1 = a[center] + 1 elemento (4 byte)
la $t2, vtemp # t2 = indirizzo del vettore temporaneo DA MODIFICARE

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

while:

bgt $t0, $s3, copiaJ # if( i > center ) goto fuoriWhile (bgt = "branch greater than")
bgt $t1, $s4, copiaI # if( j > right ) goto fuoriWhile

#if( a[i] <= a[j] )

lw $v0, ($t0) # v0 = $s1[i]
lw $v1, ($t1) # v1 = $s1[j]
bgt $v0, $v1, faiElse # if(R2 > R3) goto faiElse

# corpo dell' if

sw $v0, ($t2) # sw = "store word"
addi $t0, $t0, 4 # avanzo $s1[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 $s1[j]
addi $t2, $t2, 4 # incremento il puntatore b[k]
j while # jump while

copiaI:

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

copiaJ:

bgt $t1, $s4, ricopia # if( j > right ) goto ricopia
lw $v0, ($t1) # $v0 = $s1[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, $s2, $0 # t0 = $s1[left]
for:

bgt $t0, $s4, 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 procedura. Viene effettuata la lettura dell'indirizzo di ritorno dal
# registro $ra e trasferito il controllo a questo indirizzo. Questa istruzione viene
# eseguita prima del trasferimento di controllo.

[Z80Fan]

Ho provato a modificare la versione in assembly MIPS di Z80Fan facendo in modo che l'utente inserisca i valori interi. Purtroppo non riesco a capire se funziona. Sarebbe interessante se qualcuno di Voi riuscisse a modificare quest'ultima versione e fare in modo che stampi il vettore ordinato.
Ciao! Mi piacerebbe darti una mano, ma (ti prego non ti arrabbiare se dico una cavolata) il tuo post mi sa tanto da "compiti per casa (http://marchi.usr.dsi.unimi.it/Teaching/Architetture10/Es14-15/Variabili-globali.asm)"...

Ti dico solo che hai già tutto il codice per fare l'output, devi solo cambiare una piiiccola cosina, e con questo ho già detto troppo ;)

Inoltre, nella versione di Z80Fan la dimensione del vettore temporaneo era ovviamente fissata. Nel caso di quest'ultima ho lasciato il vettore temporaneo di dimensione fissata: non riesco a fare in modo che anche questo utilizzi lo stack.

Anche per questo hai già tutto quello che ti serve, solo qui devi cambiare 2 piccole cosine...
Coraggio, ce la puoi fare da solo :) Ti consiglio anche di attrezzarti con un simulatore, in modo che sia più interattiva la cosa, e puoi anche fare step-by-step nel codice per capire come funziona. Io ti consiglio MARS (http://courses.missouristate.edu/KenVollmar/MARS/download.htm), che, oltre a essere in Java e quindi disponibile su tutte le piattaforme, è un simulatore molto potente.

[gnakko_patakko]

Compiti per casa ? :D A 35 anni, ancora vuoi farmi fare i compiti per casa ? Aiutoooo. Comunque, non e' proprio che non ci sia riuscito a farlo: semplicemente non ho provato. La calura e' fin troppa in questi giorni.

[gnakko_patakko]

Sono riuscito ad utilizzare lo stack anche per il vettore temporaneo. Eseguendo il programma uno step-by-step, utilizzando MARS, ho potuto vedere che, come era ovvio, funziona correttamente. L'unico problema che rimane e' che non riesco a far stampare il vettore degli elementi ordinati.

Qualcuno sa come fare ?

[Z80Fan]

Sono riuscito ad utilizzare lo stack anche per il vettore temporaneo. Eseguendo il programma uno step-by-step, utilizzando MARS, ho potuto vedere che, come era ovvio, funziona correttamente. L'unico problema che rimane e' che non riesco a far stampare il vettore degli elementi ordinati.

Qualcuno sa come fare ?
Hai già provato a scrivere un codice, che però non funziona, o non riesci a pensare all'algoritmo?

[Z80Fan]

Salve gente! È da un po' che non ci si sente eh? :D

Ecco per voi il nostro caro mergesort in codice ARM:
@@@@@@@@@@@@@@@@@@ Dati @@@@@@@@@@@@@@@@@@@@@
.data
vettDati: .long 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
.bss
.align 4
vettTemp:
.lcomm b, 4*27

@@@@@@@@@@@@@@@@@ Codice @@@@@@@@@@@@@@@@@@@@
.text
.global _start
_start: @ main
ldr R8, = vettDati @ R8 = a
mov R9, #0 @ R9 = left = 0
mov R10, #26 @ R10 = right = 26
bl mergesort

endloop: b endloop

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ - mergesort (a[], left, right)
@ - Parametri
@ R8 = indirizzo a
@ R9 = left
@ R10 = right
@ - Usa
@ R11 = center
@ R0 = left salvato
@ R1 = right salvato

mergesort:
cmp R9, R10 @ if (left<right)
movhs PC, LR @ esci subito se right >= left

stmdb SP!, {R0-R1, R8-R11, LR} @ salva registri
mov R0, R9
mov R1, R10 @ salvo left e right in due registri

add R11, R9, R10 @ center = left+right ...
mov R11, R11, ASR #1 @ ... /2

mov R10, R11 @ metto center in right per la prima chiamata ricorsiva
bl mergesort @ chiamata ricorsiva

add R9, R11, #1 @ calcolo center+1 e lo metto in left R9
mov R10, R1 @ prendo il vecchio valore di right e lo metto nel nuovo right R10
bl mergesort @ chiamata ricorsiva

mov R9, R0 @ prendo il vecchio valore di left e lo metto nel left di merge R9
bl merge @ chiama merge

@ ripristina registri e ritorna (il valore di LR viene caricato in PC)
ldmia SP!, {R0-R1, R8-R11, PC}


@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ - merge (a[], left, right, center)
@ - Parametri
@ R8 = indirizzo a
@ R9 = left
@ R10 = right
@ R11 = center
@ - Usa:
@ R0 = temp / a[i]
@ R1 = temp / a[j]
@ R3 = i
@ R4 = j
@ R5 = indirizzo vettore temporaneo b

merge:
@ salva registri
stmdb SP!, {R0-R5, R9, LR}

ldr R5, = vettTemp @ carico l'indirizzo del vettore temporaneo
mov R3, R9 @ i = left
add R4, R11, #1 @ j = center + 1

mergewhile:
@ while (i<=center && j<=right)
cmp R3, R11 @ i <= center
bhi copia_j @ esci se i > center e vai a completare j
cmp R4, R10 @ j <= right
bhi copia_i @ esci se j > right e vai a completare i

ldr R0, [R8, R3, LSL #2] @ R0 = a[i]
ldr R1, [R8, R4, LSL #2] @ R1 = a[j]

cmp R0, R1 @ if (a[i] <= a[j]) then
strls R0, [R5], #4 @ b[k] = a[i]
addls R3, R3, #1 @ i++

strhi R1, [R5], #4 @ else b[k] = a[j]
addhi R4, R4, #1 @ j++

b mergewhile

copia_i:
cmp R3, R11 @ i <= center
ldrls R0, [R8, R3, LSL #2] @ R0 = a[i]
strls R0, [R5], #4 @ b[k] = a[i]
addls R3, R3, #1 @ i++
bls copia_i

copia_j:
cmp R4, R10 @ j <= right
ldrls R1, [R8, R4, LSL #2] @ R1 = a[j]
strls R1, [R5], #4 @ b[k] = a[j]
addls R4, R4, #1 @ j++
bls copia_j

ldr R5, = vettTemp @ ripristino R5 a puntare all'inizio di b
copia_b:
cmp R9, R10 @ k < right
ldrls R0, [R5], #4 @ R0 = *b++
strls R0, [R8, R9, LSL #2] @ a[k] = R0
addls R9, R9, #1
bls copia_b

@ ripristina registri e ritorna
ldmia SP!, {R0-R5, R9, PC}
.end

[cdimauro]

Alla fine anche per l'ARM il codice non è molto lungo...

[Z80Fan]

Alla fine anche per l'ARM il codice non è molto lungo...
Già...
Mi son piaciute molto le istruzioni condizionali, mi hanno fatto risparmiare una decina di salti vari (però anche mettendoli il codice non diventa enorme, semplicemente si va a scrivere come sulle architetture che non hanno questa funzionalità).