SoluzioniProva6Giugno2002 < Architetture2/MZ

---++ Soluzioni della Prova scritta di Assembler del 6 Giugno 2002
----
%TOC%
----

<font color=red size="---+2">Lavori in corso ... </font>

---+++ Esercizio A1 (6 punti)

Scrivere un programma in assembler MIPS che
   1 definisca un'area di memoria *stringa* che conterrà una stringa generica da voi scelta
   1 definisca le aree di memoria *car1* e *car2* che conterranno due caratteri diversi da voi scelti
   1 sostituisca tutte le occorrenze del carattere indicato in *car1* con occorrenze del carattere *car2*
   1 definisca un'area di memoria *int1* che conterrà un intero positivo _n_ da voi scelto
   1 costruisca una stringa, ruotando la precedente di _n_ caratteri verso destra

---++++ Soluzione A1

<verbatim>
.data
stringa: .asciiz "speriamo che me la cavo"
car1:    .ascii  "c"
car2:    .ascii  "d"
int1:    .word    5
stringa2: .space 100

.text
.globl main
main:
   li $t0, 0       # contatore del carattere corrente
   lb $s0, car1    # carattere car1
   lb $s1, car2    # carattere car2

# sostituzione
ciclo:
   lb $s2, stringa($t0)   # carico il carattere corrente
   beqz $s2, ruota        # è finita la stringa
   bne $s2, $s0, skip     # se il carattere è diverso da car1 si salta
   sb $s1, stringa($t0)   # altrimenti è uguale e lo si sostituisce
skip:
   addi $t0, $t0, 1       # incremento l'offset in memoria
   b ciclo
# alla fine in $t0 c'è la lunghezza della stringa

# shift a destra
ruota:
   lw $t2, int1           # dimensione dello spostamento
   li $t3, 0              # provenienza del primo carattere
   move $t1, $t2          # destinazione del primo carattere
ciclo:
   lb $s2, stringa($t3)   #
   mod $t4, $t1, $t0      # la posizione finale del carattere è (x---+n mod lunghezza)
   sb $s2, stringa2($t4)  #
   addi $t3, 1
   addi $t1, 1
   bne $t3, $t0, ciclo    # se non è finita si ripete
   sb $0, stringa2($t0)   # aggiungiamo lo zero finale
</verbatim>

----

---+++ Esercizio A2 (14 punti)
Si consideri la funzione _f_ definita su interi
   * _f(x) = f(x-1) - x_ se _x_ è pari
   * _f(x) = f(x-1)---+ x_ se _x_ è dispari
   * _f(0) = 0_
Si realizzi un programma in assembler MIPS che
   1 definisca un'area di memoria *int1* che conterrà un intero _x_ da voi scelto
   1 calcoli il corrispondente valore di _f(x)_ in modo *ricorsivo*

---++++ Soluzione A2
<verbatim>
.data
int1: .word 99
.text
.globl main
main:
   lw $a0, int1
   jal F
   move $a0, $v0
   li $v0, 1       # print_int
   syscall
   li $v0, 10
   syscall

F:
   beqz $a0, caso_base
   subu $sp, $sp, 8
   sw $a0, 0($sp)
   sw $ra, 4($sp)
   sub $a0, $a0, 1
   jal F
   lw $a0, 0($sp)
   li $t0, 2
   rem $t1, $a0, $t0
   beqz $t1, pari
dispari:
   add $v0, $v0, $a0
   b avanti
pari:
   sub $v0, $v0, $a0
avanti:
   lw $ra, 4($sp)
   addi $sp, $sp, 8
   jr $ra

caso_base:
   li $v0, 0
   jr $ra
</verbatim>

----

---+++ Esercizio A3 (10 punti)
Scrivere un programma in assembler MIPS che
   1 definisca le aree di memoria *nrig* e *ncol* (che conterranno gli interi 5 e 10 rispettivamente)
   1 definisca un'area di memoria *matrice* che conterrà gli elementi interi da voi scelti di una matrice di interi avente 
     numero di righe e colonne pari ai valori contenuti in *nrig* e *ncol* rispettivamente
   1 definisca le aree di memoria *int_i* e *int_j* contenenti valori legali e diversi degli indici di riga: _i_ e _j_
   1 costruisca la matrice ottenuta da quella iniziale sommando i valori delle righe _i_ e _j_ e ponendo il risultato nella riga _j_

---++++ Soluzione A3
<verbatim>
.data
matrice: .word 0:50
nrig:    .word 5
ncol:    .word 10
int_i:   .word 2
int_j:   .word 3

.text
.globl main
main:
   lw $s0, nrig
   lw $s1, ncol
   lw $t0, int_i       # indice della riga i
   mul $t0, $t0, $s1   # calcolo l'offset del primo elemento della riga i
   mul $t0, $t0, 4     # 
   lw $t1, int_j       # indice della riga j
   mul $t1, $t1, $s1   # calcolo l'offset del primo elemento della riga j
   mul $t1, $t1, 4     # 
   li $t2, 0           # contatore degli elementi della riga
ciclo:
   lw $t4, matrice($t0)    # leggo il valore dell'elemento corrente della riga i
   lw $t5, matrice($t1)    # leggo il valore dell'elemento corrente della riga j
   add $t4, $t4, $t5
   sw $t4, matrice($t1)    # memorizzo il risultato
   addi $t0, $t0, 4        # incremento l'offset della riga i in memoria
   addi $t1, $t1, 4        # incremento l'offset della riga j in memoria
   addi $t2, $t2, 1        # conto un altro elemento
   bne $t2, $s1, ciclo     # se non ho finito passo al prossimo elemento
   li $v0, 10
   syscall
</verbatim>

----

---+++ Esercizio B1 (6 punti)
Scrivere un programma in assembler MIPS che
   1 definisca un'area di memoria *stringa* che conterrà una stringa generica da voi scelta
   1 definisca un'aree di memoria *car1* che conterrà un carattere da voi scelto
   1 calcoli il numero di occorrenze del carattere memorizzato in *car1*
   1 controlli se la stringa è palindroma (ovvero se si ottiene la stessa stringa 
     sia che la si legga da sinistra verso destra che da destra verso sinistra)

---++++ Soluzione B1

<verbatim>
.data
stringa: .asciiz "speriamo che me la cavo"
car1:    .ascii  "c"
si:      .asciiz "la stringa è palindroma"
no:      .asciiz "la stringa NON è palindroma"

.text
.globl main
main:
   li $v0, 0       # numero di caratteri "car1" trovati
   li $t0, 0       # contatore del carattere corrente
   lb $s0, car1    # carattere car1

# conteggio
ciclo:
   lb $s2, stringa($t0)   # carico il carattere corrente
   beqz $s2, palindromo    # è finita la stringa
   bne $s2, $s0, skip     # se il carattere è diverso da car1 si salta
   addi $v0, 1            # altrimenti è uguale e si incrementa $v0
skip:
   addi $t0, $t0, 1       # incremento l'offset in memoria
   b ciclo
# alla fine in $t0 c'è la lunghezza della stringa

# palindromo?
palindromo:
   sub $t0, $t0, 1        # l'ultimo carattere è n-1
   li $t3, 0              # indice del primo carattere
ciclo:
   lb $s2, stringa($t3)   # prendo il primo carattere
   lb $s3, stringa($t0)   # e l'ultimo
   bne $s2, $s3, non_palindromo  # se sono diversi non è palindroma
   blt $t3, $t0, ciclo    # se i due indici non si sono ancora incontrati ciclo
# finito il controllo, tutti i caratteri sono uguali a coppie
si_palindromo:
   la $a0, si             # è palindromo
stampa
   li $v0, 4              # print_string
   syscall
   li $v0, 10
   syscall

non_palindromo:
   la $a0, no             # NON è palindromo
   b stampa
</verbatim>

----

---+++ Esercizio B2 (14 punti)
Si consideri la funzione _f_ definita su interi
   * _f(x) = x---+ f(x-1)_ se _x_ è dispari
   * _f(x) = -f(x-1)_ se _x_ è pari
   * _f(0) = 0_
Si realizzi un programma in assembler MIPS che
   1 definisca un'area di memoria *int1* che conterrà un intero _x_ da voi scelto
   1 calcoli il corrispondente valore di _f(x)_ in modo *ricorsivo*

---++++ Soluzione B2
<verbatim>
.data
int1: .word 56
.text
.globl main
main:
   lw $a0, int1
   jal F
   move $a0, $v0
   li $v0, 1       # print_int
   syscall
   li $v0, 10
   syscall

F:
   beqz $a0, caso_base
   subu $sp, $sp, 8
   sw $a0, 0($sp)
   sw $ra, 4($sp)
   sub $a0, $a0, 1
   jal F
   lw $a0, 0($sp)
   li $t0, 2
   rem $t1, $a0, $t0
   beqz $t1, pari
dispari:
   add $v0, $v0, $a0
   b avanti
pari:
   sub $v0, $0, $v0     # NON usate neg (complemento bit-a-bit)
avanti:
   lw $ra, 4($sp)
   addi $sp, $sp, 8
   jr $ra

caso_base:
   li $v0, 0
   jr $ra
</verbatim>

----

---+++ Esercizio B3 (10 punti)
Scrivere un programma in assembler MIPS che
   1 definisca le aree di memoria *nrig* e *ncol* (che conterranno gli interi 6 e 8 rispettivamente)
   1 definisca un'area di memoria *matrice* che conterrà gli elementi interi da voi scelti di una matrice di interi avente 
     numero di righe e colonne pari ai valori contenuti in *nrig* e *ncol* rispettivamente
   1 definisca le aree di memoria *int_i* e *int_j* contenenti valori legali e diversi degli indici di riga: _i_ e _j_
   1 costruisca la matrice ottenuta dalla permutazione delle righe _i_ e _j_

---++++ Soluzione B3
<verbatim>
.data
matrice: .word 0:48
nrig:    .word 6
ncol:    .word 8
int_i:   .word 3
int_j:   .word 4

.text
.globl main
main:
   lw $s0, nrig
   lw $s1, ncol
   lw $t0, int_i   # indice della riga i
   mul $t0, $t0, $s1   # calcolo l'offset del primo elemento della riga i
   mul $t0, $t0, 4     # 
   lw $t1, int_j   # indice della riga j
   mul $t1, $t1, $s1   # calcolo l'offset del primo elemento della riga j
   mul $t1, $t1, 4     # 
   li $t2, 0           # contatore degli elementi della riga
ciclo:
   lw $t4, matrice($t0)    # leggo il valore dell'elemento corrente della riga i
   lw $t5, matrice($t1)    # leggo il valore dell'elemento corrente della riga j
   sw $t4, matrice($t1)    # scambio i valori
   sw $t5, matrice($t0)    # scambio i valori
   addi $t0, $t0, 4        # incremento l'offset della riga i in memoria
   addi $t1, $t1, 4        # incremento l'offset della riga j in memoria
   addi $t2, $t2, 1        # conto un altro elemento
   bne $t2, $s1, ciclo     # se non ho finito passo al prossimo elemento
   li $v0, 10
   syscall
</verbatim>
----

---+++ Esercizio C1 (15 punti)
Si implementi la funzione *ricorsiva* _f(a,b,c)_ definita come segue:
   * _f(a,b,c) = 42_ se _a---+b<0_
   * _f(a,b,c) = c * f(a-b,b-c,a)_  altrimenti

---++++ Soluzione C1
<verbatim>
F:
   add $t0, $a0, $a1      # a---+b
   blt $t0, casobase
   subu $sp, $sp, 16
   sw $ra, 0($sp)
   sw $a0, 4($sp)
   sw $a1, 8($sp)
   sw $a2, 12($sp)
   sub $a0, $a0, $a1
   sub $a1, $a1, $a2
   lw $a2, 4($sp)
   jal F
   lw $ra, 0($sp)
   lw $a0, 4($sp)
   lw $a1, 8($sp)
   lw $a2, 12($sp)
   mul $v0, $v0, $a2
   addu $sp, $sp, 16
   jr $ra

caso_base:
   li $v0, 42
   jr $ra

</verbatim>

----

---+++ Esercizio C2 (15 punti)
Sia data una matrice di nome *matrice* di dimensioni *nrig=10* ed *ncol=15*
   * Si definiscano le aree di memoria *Matrice, nrig, ncol*.
   * Si calcoli il numero di elementi della matrice che hanno valore uguale al prodotto
     delle proprie coordinate.

---++++ Soluzione C2
<verbatim>
.data
matrice: .word 0:150
nrig:    .word 10
ncol:    .word 15
.text
.globl main
main:
   lw $s0, nrig
   lw $s1, ncol
   li $t0, 0       # indice di riga (i)
   li $t1, 0       # indice di colonna (j)
   li $t2, 0       # conterrà il numero di elementi trovati
   li $t3, 0       # offset in memoria
ciclo:
   lw $t4, matrice($t3)    # leggo il valore dell'elemento corrente
   mul $t5, $t0, $t1       # i*j
   bne $t5, $t4, skip      # se diversi salto
   addi $t2, $t2, 1        # se uguali ne conto uno in più
skip:
   addi $t3, $t3, 4        # incremento l'offset in memoria
   addi $t1, $t1, 1        # i---++
   bne $t1, $s1, ciclo
   li $t1, 0
   addi $t0, $t0, 1        # j---++
   bne $t0, $s0, ciclo
# a questo punto il risultato è in $t2
   li $v0, 10
   syscall
</verbatim>


----

---+++ Esercizio D1 (15 punti)
Si implementi la funzione *ricorsiva* _f(a,b,c)_ definita come segue:
   * _f(a,b,c) = 42_ se _a---+b+c<0_
   * _f(a,b,c) = c*a---+ f(b,c,a-b)_  altrimenti

---++++ Soluzione D1
<verbatim>
F:
   add $t0, $a0, $a1      # a---+b
   add $t0, $t0, $a2      # a---+b+c
   blt $t0, casobase
   subu $sp, $sp, 16
   sw $ra, 0($sp)
   sw $a0, 4($sp)
   sw $a1, 8($sp)
   sw $a2, 12($sp)
   sub $a2, $a0, $a1
   lw $a0, 8($sp)
   lw $a1, 12($sp)
   jal F
   lw $ra, 0($sp)
   lw $a0, 4($sp)
   lw $a1, 8($sp)
   lw $a2, 12($sp)
   mul $v1, $a0, $a2
   add $v0, $v0, $v1
   addu $sp, $sp, 16
   jr $ra

caso_base:
   li $v0, 42
   jr $ra

</verbatim>

----

---+++ Esercizio D2 (15 punti)
Sia data una matrice di nome *matrice* di dimensioni *nrig=13* ed *ncol=12*
   * Si definiscano le aree di memoria *Matrice, nrig, ncol*.
   * Si calcoli la somma degli elementi della matrice che hanno valore uguale alla differenza
     (in valore assoluto) delle proprie coordinate.

---++++ Soluzione D2
<verbatim>
.data
matrice: .word 0:156
nrig:    .word 13
ncol:    .word 12
.text
.globl main
main:
   lw $s0, nrig
   lw $s1, ncol
   li $t0, 0       # indice di riga (i)
   li $t1, 0       # indice di colonna (j)
   li $t2, 0       # conterrà la somma
   li $t3, 0       # offset in memoria
ciclo:
   lw $t4, matrice($t3)    # leggo il valore dell'elemento corrente
   sub $t5, $t0, $t1       # i-j
   abs $t5, $t5            # |i-j|
   bne $t5, $t4, skip      # se diversi salto
   add $t2, $t2, $t4       # se uguali sommo
skip:
   addi $t3, $t3, 4        # incremento l'offset in memoria
   addi $t1, $t1, 1        # i---++
   bne $t1, $s1, ciclo
   li $t1, 0
   addi $t0, $t0, 1        # j---++
   bne $t0, $s0, ciclo
# a questo punto il risultato è in $t2
   li $v0, 10
   syscall
</verbatim>

----


-- Users.AndreaSterbini - 10 Jun 2002

   * Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
This topic: Architetture2/MZ > SoluzioniProva6Giugno2002
Topic revision: r5 - 2002-06-24 - AndreaSterbini