Prova pratica di Assembler - 14 Settembre 2001
Esercizio 1A
Si scriva la routine assembler MIPS che implementa la funzione ricorsiva definita come segue:
- f(x,y,z) = 1 se uno (almeno) tra x,y,z vale 0
- f(x,y,z) = x * f(y,z,x-1) altrimenti
- Si assuma che x, y, z siano sempre maggiori o uguali a 0
Esercizio 2A
Sia data una matrice a 4 dimensioni con indici
i,j,k,l che chiameremo
ipercubo:
- Sia supponga che le 4 dimensioni siano uguali e valgano al piu' nrig=10
- Si scriva il programma assembler che:
- definisce l'area di memoria per nrig
- definisce l'area di memoria ipercubo come matrice di words
- calcola la somma degli elementi della matrice per i quali e' vero che (i=j e k=l)
Soluzione 1A
Vi ricordo che e' convenzione usare i registri
$a0,$a1,$a2,$a3
per passare fino a 4 parametri ed i registri
$v0,$v1
per tornare fino a 2 risultati.
F: # x=$a0 y=$a1 z=$a2
beqz $a0, casobase
beqz $a1, casobase
beqz $a2, casobase
subu $sp, $sp, 16 # alloco 4 words per salvare i 3 argomenti ed il registro $ra
sw $ra, 0($sp)
sw $a0, 4($sp)
sw $a1, 8($sp)
sw $a2, 12($sp)
sub $a2, $a0, 1 # z=x-1
lw $a1, 12($sp) # y=z
lw $a0, 8($sp) # x=y
jal F # chiamata ricorsiva: f(y,z,x-1)
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $a2, 12($sp)
subu $sp, $sp, 16 # libero lo spazio allocato su stack
mul $v0, $v0, $a0 # x * f(y,z,x-1)
jr $ra # torno al chiamante
casobase:
li $v0, 1
jr $ra # torno al chiamante
Soluzione 2A
Vi ricordo che una matrice di dimensioni N (in questo caso N=4) non e' altro che una successione di matrici di dimensioni N-1.
- una matrice ipercubica e' una successione di matrici cubiche
- una matrice cubica e' una successione di matrici quadrate
- una matrice quadrata e' una successione di matrici monodimensionali (righe)
- una riga e' una successione di elementi
.data
nrig: .word 10
ipercubo: .word 0:10000 # 10000=10^4 e' il massimo numero di elementi di una matrice n^4 se n e' minore o uguale a 10
.text
.globl main
main:
li $t0, 0 # indice i
li $t1, 0 # indice j
li $t2, 0 # indice k
li $t3, 0 # indice l
li $t4, 0 # offset in memoria
li $t5, 0 # somma risultante
lw $t6, nrig # nrig
ciclo:
bneq $t0, $t1, next # se i e' diverso da j si salta l'elemento
bneq $t2, $t3, next # se k e' diverso da l si salta l'elemento
# se siamo qui vuol dire che i=j e k=l
lw $t7, ipercubo($t4) # leggo il valore dell'elemento
add $t5, $t5, $t7 # sommo il valore
next:
addi $t0, 1 # incremento i
addi $t4, 4 # passo alla WORD successiva
bne $t0, $t6, ciclo # se non ho ancora finito la riga continuo il ciclo
li $t0, 0 # azzero l'indice i
addi $t1, 1 # incremento j
bne $t1, $t6, ciclo # se non ho ancora finito la matrice continuo il ciclo
li $t1, 0 # azzero l'indice j
addi $t2, 1 # incremento k
bne $t2, $t6, ciclo # se non ho ancora finito il cubo continuo il ciclo
li $t2, 0 # azzero l'indice j
addi $t3, 1 # incremento k
bne $t3, $t6, ciclo # se non ho ancora finito l'ipercubo continuo il ciclo
li $v0, 10
syscall
Esercizio 1B
Si scriva la routine assembler MIPS che implementa la funzione ricorsiva definita come segue:
- f(x,y,z,t) = 0 se x,y,z,t sono tutti 0
- f(x,y,z,t) = x * f(t---+1,x-2,y,z) altrimenti
- Si assuma che x,y,z,t siano sempre maggiori o uguali a 0
Esercizio 2B
Sia data una matrice a 3 dimensioni con indici
x,y,z che chiameremo
cubo:
- sia supponga che le 3 dimensioni siano uguali e valgano al piu' nrig=15
- Si scriva il programma assembler che:
- definisce l'area di memoria per nrig
- definisce l'area di memoria cubo come matrice di half words
- calcola il prodotto degli elementi della matrice per i quali e' vero che x---+y+z=nrig
Soluzione 1B
NOTA: Anche se il risultato della funzione f e' sempre zero
(dato che il caso base vale 0 ed e' moltiplicato per i valori di x)
la soluzione deve essere implementata completamente.
Vi ricordo che e' convenzione usare i registri
$a0,$a1,$a2,$a3
per passare fino a 4 parametri ed i registri
$v0,$v1
per tornare fino a 2 risultati.
F: # x=$a0 y=$a1 z=$a2 t=$a3
bneq $a0, $0, nonzero
bneq $a1, $0, nonzero
bneq $a2, $0, nonzero
bneq $a3, $0, nonzero
li $v0, 0
jr $ra # torno al chiamante
nonzero:
subu $sp, $sp, 20 # alloco 5 words per salvare i 4 argomenti ed il registro $ra
sw $ra, 0($sp)
sw $a0, 4($sp) # x
sw $a1, 8($sp) # y
sw $a2, 12($sp) # z
sw $a3, 16($sp) # t
sub $a1, $a0, 2 # y=x-2
add $a0, $a3, 1 # x=t-1
lw $a2, 8($sp) # z=y
lw $a3, 12($sp) # t=z
jal F # chiamata ricorsiva: f(t---+1,x-2,y,z)
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $a2, 12($sp)
lw $a3, 16($sp)
subu $sp, $sp, 20 # libero lo spazio allocato su stack
mul $v0, $v0, $a0 # x * f(t---+1,x-2,y,z)
jr $ra # torno al chiamante
Soluzione 2B
Vi ricordo che una matrice di dimensioni N (in questo caso N=4) non e' altro che una successione di matrici di dimensioni N-1.
- una matrice cubica e' una successione di matrici quadrate
- una matrice quadrata e' una successione di matrici monodimensionali (righe)
- una riga e' una successione di elementi
.data
nrig: .word 10
cubo: .half 0:3375 # 3375=15^3 e' il massimo numero di elementi di una matrice
.text
.globl main
main:
li $t0, 0 # indice x
li $t1, 0 # indice y
li $t2, 0 # indice z
li $t4, 0 # offset in memoria
li $t5, 1 # prodotto risultante
lw $t6, nrig # nrig
ciclo:
add $t3, $t0, $t1
add $t3, $t3, $t2 # x---+y+z
bneq $t3, $t6, next # se x---+y+x e' diverso da nrig si salta l'elemento
# se siamo qui vuol dire che x---+y+z=nrig
lh $t7, ipercubo($t4) # leggo il valore dell'elemento
mul $t5, $t5, $t7 # moltiplico il valore
next:
addi $t0, 1 # incremento x
addi $t4, 2 # passo alla HALF WORD successiva
bne $t0, $t6, ciclo # se non ho ancora finito la riga continuo il ciclo
li $t0, 0 # azzero l'indice x
addi $t1, 1 # incremento y
bne $t1, $t6, ciclo # se non ho ancora finito la matrice continuo il ciclo
li $t1, 0 # azzero l'indice y
addi $t2, 1 # incremento z
bne $t2, $t6, ciclo # se non ho ancora finito il cubo continuo il ciclo
li $t2, 0 # azzero l'indice z
li $v0, 10
syscall
Esercizio 1C
Si scriva la routine assembler MIPS che implementa la funzione ricorsiva definita come segue:
- f(x,y,z)=8 se x*y*z=0
- f(x,y,z)=x*y*z*f(z,x,y-1) altrimenti
- Si assuma che x, y, z siano sempre maggiori o uguali a 0
Esercizio 2C
Sia data una matrice a 4 dimensioni con indici
a,b,c,d che chiameremo
ipercubo:
- Sia supponga che le 4 dimensioni siano uguali e valgano al piu' nrig = 7
- Si scriva il programma assembler che:
- definisce l'area di memoria per nrig
- definisce l'area di memoria ipercubo come matrice di bytes
- conta il numero elementi della matrice per i quali e' vero che ipercubo[a,b,c,d] = a-b---+c-d
Soluzione 1C
Vi ricordo che e' convenzione usare i registri
$a0,$a1,$a2,$a3
per passare fino a 4 parametri ed i registri
$v0,$v1
per tornare fino a 2 risultati.
F: # x=$a0 y=$a1 z=$a2
mul $t0, $a0, $a1 # x*y
mul $t0, $t0, $a2 # x*y*z
beqz $t0, casobase
subu $sp, $sp, 20 # alloco 5 words per salvare i 3 argomenti, il registro $ra e il prodotto ($t0)
sw $ra, 0($sp)
sw $a0, 4($sp)
sw $a1, 8($sp)
sw $a2, 12($sp)
sw $t0, 16($sp)
sub $a2, $a0, 1 # z=x-1
lw $a1, 12($sp) # y=z
lw $a0, 8($sp) # x=y
jal F # chiamata ricorsiva: f(y,z,x-1)
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $a2, 12($sp)
sw $t0, 16($sp)
subu $sp, $sp, 20 # libero lo spazio allocato su stack
mul $v0, $v0, $t0 # x*y*z * f(y,z,x-1)
jr $ra # torno al chiamante
casobase:
li $v0, 8
jr $ra # torno al chiamante
Soluzione 2B
Vi ricordo che una matrice di dimensioni N (in questo caso N=4) non e' altro che una successione di matrici di dimensioni N-1.
- una matrice ipercubica e' una successione di matrici cubiche
- una matrice cubica e' una successione di matrici quadrate
- una matrice quadrata e' una successione di matrici monodimensionali (righe)
- una riga e' una successione di elementi
.data
nrig: .word 7
ipercubo: .byte 0:2401 # 2401=7^4 e' il massimo numero di elementi di una matrice n^4 se n e' minore o uguale a 7
.text
.globl main
main:
li $t0, 0 # indice a
li $t1, 0 # indice b
li $t2, 0 # indice c
li $t3, 0 # indice d
li $t4, 0 # offset in memoria
li $t5, 0 # conteggio risultante
lw $t6, nrig # nrig
ciclo:
sub $s0, $t0, $t1 # a-b
add $s0, $s0, $t2 # a-b---+c
sub $s0, $s0, $t3 # a-b---+c-d
lb $s1, ipercubo($t4) # elemento corrente (byte)
bneq $s0, $s1, next # se il test fallisce si salta l'elemento
# se siamo qui vuol dire che ipercubo[a,b,c,d] non e' uguale ad a-b---+c-d
addi $t5, 1 # conto l'elemento
next:
addi $t0, 1 # incremento a
addi $t4, 1 # passo al BYTE successivo
bne $t0, $t6, ciclo # se non ho ancora finito la riga continuo il ciclo
li $t0, 0 # azzero l'indice a
addi $t1, 1 # incremento b
bne $t1, $t6, ciclo # se non ho ancora finito la matrice continuo il ciclo
li $t1, 0 # azzero l'indice b
addi $t2, 1 # incremento c
bne $t2, $t6, ciclo # se non ho ancora finito il cubo continuo il ciclo
li $t2, 0 # azzero l'indice c
addi $t3, 1 # incremento d
bne $t3, $t6, ciclo # se non ho ancora finito l'ipercubo continuo il ciclo
li $v0, 10
syscall
Esercizio 1D
Si scriva la routine assembler MIPS che implementa la funzione ricorsiva definita come segue:
- f(a,b,c,d) = 1 se a---+b+c+d=0
- f(a,b,c,d) = f(b-1,c,d,a)---+a altrimenti
- Si assuma che a,b,c,d siano sempre maggiori o uguali a 0
Esercizio 2D
Sia data una matrice a 3 dimensioni con indici
i,j,k che chiameremo
cubo:
- Sia supponga che le 3 dimensioni siano uguali e valgano al piu' nrig=11
- Si scriva il programma assembler che:
- definisce l'area di memoria per nrig
- definisce l'area di memoria cubo come matrice di half words
- calcola la somma degli elementi della matrice che hanno almeno un indice (i o j o k) dispari
Soluzione 1D
Vi ricordo che e' convenzione usare i registri
$a0,$a1,$a2,$a3
per passare fino a 4 parametri ed i registri
$v0,$v1
per tornare fino a 2 risultati.
F: # a=$a0 b=$a1 c=$a2 d=$a3
add $t0, $a0, $a1
add $t0, $t0, $a2
add $t0, $t0, $a3
bneq $t0, $0, nonzero
li $v0, 1
jr $ra # torno al chiamante
nonzero:
subu $sp, $sp, 20 # alloco 5 words per salvare i 4 argomenti ed il registro $ra
sw $ra, 0($sp)
sw $a0, 4($sp) # a
sw $a1, 8($sp) # b
sw $a2, 12($sp) # c
sw $a3, 16($sp) # d
sub $a0, $a1, 1 # a=b-1
lw $a1, 12($sp) # b=c
lw $a2, 16($sp) # c=d
lw $a3, 4($sp) # d=a
jal F # chiamata ricorsiva: f(b-1,c,d,a)
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $a2, 12($sp)
lw $a3, 16($sp)
subu $sp, $sp, 20 # libero lo spazio allocato su stack
add $v0, $v0, $a0 # f(b-1,c,d,a)---+a
jr $ra # torno al chiamante
Soluzione 2D
Vi ricordo che una matrice di dimensioni N (in questo caso N=4) non e' altro che una successione di matrici di dimensioni N-1.
- una matrice cubica e' una successione di matrici quadrate
- una matrice quadrata e' una successione di matrici monodimensionali (righe)
- una riga e' una successione di elementi
.data
nrig: .word 10
cubo: .half 0:1331 # 1331=11^3 e' il massimo numero di elementi di una matrice
.text
.globl main
main:
li $t0, 0 # indice i
li $t1, 0 # indice j
li $t2, 0 # indice k
li $t3, 2 # costante 2
li $t4, 0 # offset in memoria
li $t5, 0 # somma risultante
lw $t6, nrig # nrig
ciclo:
rem $s0, $t0, $t5 # resto di i/2
bneq $s0, $0, somma # somma se e' dispari
rem $s0, $t1, $t5 # resto di j/2
bneq $s0, $0, somma # somma se e' dispari
rem $s0, $t2, $t5 # resto di k/2
bneq $s0, $0, somma # somma se e' dispari
b next # tutti sono pari, si salta l'elemento
somma:
# se siamo qui vuol dire che almeno uno e' dispari
lh $t7, ipercubo($t4) # leggo il valore dell'elemento
add $t5, $t5, $t7 # sommo il valore
next:
addi $t0, 1 # incremento i
addi $t4, 2 # passo alla HALF WORD successiva
bne $t0, $t6, ciclo # se non ho ancora finito la riga continuo il ciclo
li $t0, 0 # azzero l'indice i
addi $t1, 1 # incremento j
bne $t1, $t6, ciclo # se non ho ancora finito la matrice continuo il ciclo
li $t1, 0 # azzero l'indice j
addi $t2, 1 # incremento k
bne $t2, $t6, ciclo # se non ho ancora finito il cubo continuo il ciclo
li $t2, 0 # azzero l'indice k
li $v0, 10
syscall
--
AndreaSterbini - 13 Sep 2001