SoluzioniProva6Giugno2002 < Architetture2/MZ

Soluzioni della Prova scritta di Assembler del 6 Giugno 2002

Lavori in corso ...

Esercizio A1 (6 punti)

Scrivere un programma in assembler MIPS che

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

Soluzione A1

.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

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

definisca un'area di memoria int1 che conterrà un intero x da voi scelto
calcoli il corrispondente valore di f(x) in modo ricorsivo

Soluzione A2

.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

Esercizio A3 (10 punti)

Scrivere un programma in assembler MIPS che

definisca le aree di memoria nrig e ncol (che conterranno gli interi 5 e 10 rispettivamente)
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
definisca le aree di memoria int_i e int_j contenenti valori legali e diversi degli indici di riga: i e j
costruisca la matrice ottenuta da quella iniziale sommando i valori delle righe i e j e ponendo il risultato nella riga j

Soluzione A3

.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

Esercizio B1 (6 punti)

Scrivere un programma in assembler MIPS che

definisca un'area di memoria stringa che conterrà una stringa generica da voi scelta
definisca un'aree di memoria car1 che conterrà un carattere da voi scelto
calcoli il numero di occorrenze del carattere memorizzato in car1
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

.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

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

definisca un'area di memoria int1 che conterrà un intero x da voi scelto
calcoli il corrispondente valore di f(x) in modo ricorsivo

Soluzione B2

.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

Esercizio B3 (10 punti)

Scrivere un programma in assembler MIPS che

definisca le aree di memoria nrig e ncol (che conterranno gli interi 6 e 8 rispettivamente)
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
definisca le aree di memoria int_i e int_j contenenti valori legali e diversi degli indici di riga: i e j
costruisca la matrice ottenuta dalla permutazione delle righe i e j

Soluzione B3

.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

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

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

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

.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

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

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

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

.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

-- AndreaSterbini - 10 Jun 2002