Assembler

[Dimitree]

ciao ragazzi
prima di tutto volevo segnaralvi questo corso sui PIC, di Tanzilli:

http://www.areasx.com/index.php?D=1&pag ... idsezione=

di sicuro molti di voi già lo conoscono, ma magari può sempre servire a qualcuno nuovo..


Sto studiando l'Assembler, ma non quello dei PIC bensì un Assembler di una macchina MIPS simulata sul pc..e mi sono bloccato quando si inizia a lavorare con le chiamate ricorsive e quindi si utilizza lo stack..
qualcuno saprebbe aiutarmi? per esempio ecco un pezzo di codice che non ho capito (semplice funzione che calcola il fattoriale) :

----------------------------------------------------------------------------------------------------

main:
  - si salva la variabile presa da input nel registro preservante $a0
  - si chiama la funzione Fattoriale e contemporaneamente si salva nel registro $ra l'indirizzo di ritorno, dove la funzione dovrà tornare quando avrà finito


Fattoriale:

subu $sp, $sp, 8                                 # alloca lo spazio necessario nello stack (in questo caso sottrae 8 allo stack pointer)
sw $ra, 4($sp)                                 # memorizza il valore di ritorno nello stack

ble $a0, 1, base                                 # se ($a0 <= 1) va all'etichetta "base"

sw $a0, 0($sp)                                 # salva X nello stack (X è il valore che abbiamo in $a0, cioè quello che abbiamo passato alla funz.)

subu $a0, $a0, 1                         # diminuisce X di uno
jal FACT                                         # richiama la funzione (con X diminuito di 1)

lw $t0, 0($sp)                                 # riprende X dallo stack (l'X originale, vero?)

mul $v0, $t0, $v0                         # X * (X-1)

j end                                                 # salta all'etichetta "end"




base:
li $v0, 1                                 # mette in $v0 il risultato 1


end:
lw $ra, 4($sp)                                 # carica l'indirizzo di $ra che avevamo nello stack
addu $sp, $sp, 8                                 # disalloca lo spazio allocato precedentemente nello stack

jr $ra                                 # ritorna al main caricando l'indirizzo salvato in $ra


----------------------------------------------------------------------------------------------------------------------------

scusate per la poca chiarezza..
Quello che non riesco a capire è come funziona la chiamata, se io la simulo "a carta e penna" mi diminuisce sempre X finchè non va nel caso base e torna sempre 1, se invece carico il programma nel simulatore funziona benissimo e calcola il fattoriale.
sapete aiutarmi a capire come funzionano le varie chiamate ricorsive?

grazie mille
Dimitri

[luix]

Sto studiando anche io le macchine mips per un esame, premetto che però l'esame è qualcosa del tipo "fondamenti" quindi non studiamo funzioni ricorsive, l'etichetta FATT dove si trova all'interno del codice?

[hilkin]

Percaso la funzione jal salva anche nel registro $ra? in quel caso la cosa dovrebbe funzionare, almeno cosi mi sembra da una lettura non approfondita, se mi dici come è fatta l'architettura e una piccola leggneda delle funzioni usate ti posso rispondere meglio

[Dimitree]

si certo, scusate se non l'ho fatto subito ma avevo fretta  red_face
infatti come vedete ho anche sbagliato sezione, per favore Luix potresti spostarla in "digitale"? grazie e scusate ancora
tra un pò posto le istruzioni utilizzate nell'esempio

[Hades]

occhio ai registri che usi, alcuni sono di sistema per cui non sono scrivibili dal codice in esecuzione ma servono alla cpu per eseguire le istruzioni che hai inviato... Ora non ricordo esattamente quali, se mi dai un paio di giorni mi rispulcio il manuale che abbiamo usato noi per il progetto di Assembly MIPS e ti aiuto!
Se vuoi ti passo anche il pdf (sempre che lo trovo!!!!)

[Fix_Metal]

Non capisco come tu possa perderti. Ti consiglio di fare uno step-by-step col simulatore, per capire meglio "l'inghippo" che non riesci a trovare.
Approfitto per darvi il link del corso che ho fatto l'anno scorso, trattava il MIPS2000. Ci sono slide che spiegano da 0 l'architettura e il linguaggio.
Le slide sono scritte in inglese un po' maccheronico (si riconosce che è scritto da un italiano per intenderci), ma sono di semplice lettura.
Link

[Dimitree]

il simulatore che sto usando io invece è lo SPIM

le istruzioni che ho usato sono:

jal      =  jump & link, ovvero chiama la funzione e salva l'indirizzo di ritorno nell'apposito registro $ra
lw    =  load word
sw  = store word
subu  = sottrazione unsigned
addu  = addizione unsigned
mul    = moltiplicazione
ble  = se il primo operando è minore o uguale al secondo operando, va all'etichetta



per hilkin:

si, la jal salva anche l'indirizzo successivo alla chiamata nel registro $ra, così si sa dove ritornare a fine chiamata



per Hades:  ho usato questi registri:

$a0 (anche $a1)  = registro preservante, va usato questo per passare gli argomenti alle funzioni
$t0  (da $t0 a $t9)  = semplice registro da usare per le operazioni, non è preservante
$ra  = registro riservato per salvare l' indirizzo di ritorno di una funzione
$v0 = registro preservante utilizzato per salvare il valore di ritorno della funzione
$sp = stack pointer

l'utilizzo dei registri è come da manuale diciamo (non l'ho fatto io questo codice  ) e infatti il codice funziona alla perfezione, solo che non riesco a capire l'andamento delle chiamate varie, e se non lo capisco non riesco a fare nessuna funzione ricorsiva (direi che questa è la più semplice) 

[Fix_Metal]

i registri $aX non sono 4?

[hilkin]

Provo a riscriverti i commenti e vediamo se riesco ad aiutarti


jal       =   jump & link, ovvero chiama la funzione e salva l'indirizzo di ritorno nell'apposito registro $ra
lw    =  load word
sw   = store word
subu   = sottrazione unsigned
addu  = addizione unsigned
mul    = moltiplicazione
ble   = se il primo operando è minore o uguale al secondo operando, va all'etichetta
per Hades:  ho usato questi registri:

$a0 (anche $a1)  = registro preservante, va usato questo per passare gli argomenti alle funzioni
$t0  (da $t0 a $t9)  = semplice registro da usare per le operazioni, non è preservante
$ra  = registro riservato per salvare l' indirizzo di ritorno di una funzione
$v0 = registro preservante utilizzato per salvare il valore di ritorno della funzione
$sp = stack pointer


main:
   - si salva la variabile presa da input nel registro preservante $a0
   - si chiama la funzione Fattoriale e contemporaneamente si salva nel registro $ra l'indirizzo di ritorno, dove la funzione dovrà tornare quando avrà finito


Fattoriale:

subu $sp, $sp, 8                                 # alloca lo spazio necessario nello stack (in questo caso sottrae 8 allo stack pointer)
                                                                # la cosa interessante in questo punto è che crea 2 spazi (probabilmente a 4 byte l'uno)
                                                                # se guardi durante l'intera struttura del programma questi due spazi vengono rispettati sempre
                                                                # ed in particolare 4($sp) serve per avere un punto di ritorno alla funzione chiamata, mentre
                                                                # 0($sp) porta il vero e proprio dato (il valore che poi si moltiplicherà nel passo ricorsivo)
                                                                # è molto importante questa struttura di dato + puntatore perchè è con questa che nell'ultima
                                                                # parte del programma si fanno tutte le moltiplicazioni

sw $ra, 4($sp)                                 # memorizza il valore di ritorno nello stack
                                                                # Il valore che viene memorizzato è semplicemente il punto a cui tornare per il programma principale
                                                                # nella prima chiamata di FACT, mentre per le successive chiamate ricorsive indica il vero e proprio
                                                                # a cui tornare nella funzione stessa (dopo la jal)

ble $a0, 1, base                                 # se ($a0 <= 1) va all'etichetta "base"
                                                                # Questa operazione serve per cominciare a terminare le chiamate ricorsive, infatti nel caso base in cui
                                                                # ci ritroviamo con il valore in $a0 =1 siamo arrivati alla chiusura dell chiamate ricorsive e cominciamo
                                                                # quindi a richiamare i valori dallo stack e a moltiplicarli per produrre il risultato della funzione
                                                                # Nel momento in cui $a0 =1 quindi lo stack comincerà solo a svuotarsi

sw $a0, 0($sp)                                 # salva X nello stack (X è il valore che abbiamo in $a0, cioè quello che abbiamo passato alla funz.)
                                                                # In questo punto viene salvato $a0 nello stack prima di andarlo a diminuire definitivamente, verra
                                                                # poi richiamato con una funzione lw

subu $a0, $a0, 1                         # diminuisce X di uno
                                                                # Questo passaggio è importante, in questo punto si crea il valore che verrà salvato nello stack alla
                                                                # prossima FACT nella catena di ricorsione

jal FACT                                         # richiama la funzione (con X diminuito di 1)
                                                                # in questo punto è importantissimo notare che subito dopo la chiamata verrà salvato in una posizione
                                                                # dello stack l'indizizzo $ra che viene salvato in questo momento, ed infatti poi tramite la funzione jr $ra
                                                                # ritorneremo esattamente in questo punto; nello stack avremo quindi una serie di valori di ritorno con
                                                                # i rispettivi valori da moltiplicare

lw $t0, 0($sp)                                 # riprende X dallo stack (l'X originale, vero?)
                                                                # riprende l'X relativo a questo passaggio di ricorsione, è importante notare che a questa funzione viene
                                                                # eseguita sempre e solo dopo avere finito la END e quindi il valore caricato sarà quello corretto (infatti
                                                                # nella END viene aggiornato lo stack pointer)

mul $v0, $t0, $v0                         # X * (X-1)

j end                                                 # salta all'etichetta "end"




base:
li $v0, 1                                 # mette in $v0 il risultato 1
                                                        # importante: questa istruzione viene eseguita una sola volta
                                                        # in pratica inizializza $v0 al valore 1 in modo che poi vengano moltiplicati sempre i valori nello stack sino
                                                        # ad ottenere il fattoriale


end:
lw $ra, 4($sp)                          # carica l'indirizzo di $ra che avevamo nello stack
                                                        # con questa prepara $ra per il salto indietro all'ultima funzione chiamante nella lista di ricorsione

addu $sp, $sp, 8                          # disalloca lo spazio allocato precedentemente nello stack
                                                        # tramite questa funzione si vanno a distruggere i due dati già utilizzati: il valore moltiplicato per creare il
                                                        # fattoriale e il puntatore salvato per il program counter
                                                        # Al prossimo passaggio della funzione ci si ritroverà con valori diversi ovviamente.

jr $ra                                          # ritorna al main caricando l'indirizzo salvato in $ra
                                                        # attenzione: non ritorna necessariamente al main, anzi nella maggior parte dei casi ritornerà a dopo la
                                                        # funzione jal, solo all'ultimo passaggio ritornerà al main ed in $v0 ci si ritroverà il valore in uscita

[Dimitree]

grazie mille! non avevo capito, stupidamente, che le istruzioni che operano sullo stack pointer non si sovrascrivono, quindi lo stack si riempie mano a mano..
Ora però non capisco una cosa..facciamo finta che mandiamo alla funzione il valore 4, questa funzione lo decrementa di uno ogni volta (e contemporaneamente salva i diversi valori) finchè non è uguale a 1, a questo punto va all'etichetta "base" che assegna 1 al $v0, ma dopo aver fatto questo dove torna? va a end oppure torna all'istruzione dopo il confronto "ble"?

[hilkin]

Prosegue con END, ora io non ho studiato questo particolare processore, ma tutti i processori che conosco hanno un program counter, un registro dove ci sta un puntatore alla prossima locazione di memoria da caricare come istruzione nel processore, dopo ogni istruzione che non sia di salto il program counter viene incrementato di 1 (o 2 o 4 a seconda della struttura, ma in maniera coerente), in questa maniera il processore al prossimo ciclo di clok eseguirà l'istruzione successiva. Questo avviene sempre a parte quando siamo di fronte a delle istruzioni di salto o salto condizionato, infatti in quelle istruzioni si va semplicemente ad aggiornare il program counter e quindi al successivo colpo di clok il processore andrà a leggere l'istruzione con il program counter aggiornato.

Lasciando stare i ricami che si possono fare a quanto scritto sopra per particolari processori (tipo pipeline) ripeto tutti i processori che conosco lavorano così, se qualcosa non ti è chiaro dimmelo che cerco di metterlo giù meglio.

In pratica il tuo programma crea in via preliminare tutto lo stack con i valori da moltiplicare, quando a forza di decrementare trova la variabile a 1 allora comincia a togliere roba dallo stack e a moltiplicare.

[Dimitree]

si è vero che stupidaggine che ho detto.. scusami..  red_face

grazie mille hilkin!
se non è troppo disturbo, posso chiederti di mostrarmi come implementare una funzione che calcola la serie di fibonacci, dato un "n"?
magari capisco meglio come implementare questo tipo di funzioni..
grazie ancora

[hilkin]

Non scusarti, nella programmazione soprattutto in assembler le sviste sono sempre dietro l'angolo.

Ho scaricato il simulatore che avevi scritto qualche post più sopra, adesso lo provo e cerco di metterti giù qualcosa, la traduzione di questa funzione in c ti andrebbe bene?

int fib(int n){
    if (n==0 || n==1) return n;
    return fib(n-1) + fib(n-2);
}

è una funzione che ho trovato sulla wikipedia

[Dimitree]

si va benissimo, grazie!
quel programma è un po macchinoso da installare (perchè si connette per scaricare il .net 3.5) quindi se non riesci non preoccuparti, 
grazie ancora

[hilkin]

io l'ho fatto cosi, però non ho ancora provato a simularlo, devo un'attimo guardarmi il simulatore per capire come funziona.

L'unica cosa di cui non sono sicuro è la funzione  li $v0, $a0  che nel tuo esempio lavorava con registro e numero mentre io l'ho usata tra registro e registro (in altri assembler funziona cosi); per il resto ho usato tutte funzioni già usate.



fib:
  subu $sp, $sp, 4                # creo uno spazio sullo stack
  sw $ra, 0(sp)                  # salvo sullo stack il link per il ritorno alla funzione chiamante

  ble $a0, 1, base                # caso base, se il parametro della funzione chiamata è 0 oppure 1 allora salta

  subu $sp, $sp, 4                # creo uno spazio sullo stack, potevo crearne due all'inizio ma io mi trovo
                                  # bene cosi (sono cose che mi restano dello Z80)
  sw $a0, 0(sp)                  # salvo il parametro passato alla funzione per un successivo utilizzo

  subu $a0, Sa0, 1                # preparo il parametro diminuito di 1

  jal fib                        # chiamo ricorsivamente con x-1

  lw $a0, 0($sp)                  # richiamo dallo stack il valore originale del parametro della funzione chiamante

  subu $a0, Sa0, 2                # preparo il parametro diminuito di 2

  sw $v0, 0($sp)                  # salvo il valore di ritorno dalla prima chiamata ricorsiva nello stack (utilizzo
                                  # la posizione che era occupata da $a0 perchè quel valore non serve più conservato)

  jal fib                        # chiamo ricorsivamente con x-2

  lw $t0, 0($sp)                  # richiamo dallo stack il valore di fib(x-1)
  addu $sp, $sp, 4                # distruggo una posizione dello stack che non mi serve più

  addu $v0, $t0, $v0              # calcolo fib(x-1)+fib(x-2) e lo metto in $v0
 
  j end                          # salta a end

base:
  li $v0, $a0                    # mette in $v0 il valore x

end: 
  lw $ra, 0($sp)                  # rimette a posto il registro $ra per fare in modo che il program counter torni alla funzione chiamante
  addu $sp, $sp, 4                # distrugge una posizione dello stack
  jr $ra                          # ritorna alla funzione chiamante