Prova di Assembler SPIM del 19-6-2001 - entrambi i canali
Ecco i testi e le (prime) soluzioni delle prova di recupero del 19 Giugno 2001.
Il resto delle soluzioni seguira' appena possibile.
I risultati sono su
RisultatiProva19Giugno2001.
Compito A
Esercizio A1 (15 punti)
Si scriva una procedura che serve a calcolare la matrice trasposta
Trasp di una data matrice
Matr.
Per far questo:
- si presupponga che il numero di righe e di colonne siano stati gia' chiesti in input tramite syscall e che siano compresi tra 1 e 20 inclusi.
- si allochi lo spazio necessario per le matrici Matr e Trasp
- si scriva una routine che riceve come argomenti:
- $a0 = numero di righe
- $a1 = numero di colonne
- e che calcola Trasp
Si ricorda la relazione tra gli elementi delle due matrici:
Soluzione Esercizio A1
.data
Matr: .word 0:400 # matrice di nrig * ncol elementi
Trasp: .word 0:400 # matrice di ncol * nrig elementi
.text
faiTrasposta: # ho $a0=nrig e $a1=ncol
li $t0, 0 # indice nella matrice Matr
li $t1, 0 # i=0 (e' piu' comodo usare indici da 0 a nrig-1
li $t2, 0 # j=0 per i conti seguenti)
sub $t3, $a0, 1 # in $t3 metto nrig-1
sub $t4, $a1, 1 # in $t4 metto ncol-1
ciclo:
lw $t3, Matr($t0) # carico in $t3 l'elemento corrente Matr(i,j)
mul $t4, $t1, $a0 # calcolo la posizione dell'elemento Trasp(j,i)
# nella trasposta le righe sono lunghe nrig elementi (come una colonna di Matr)
add $t4, $t2, $t4 # pos = 4*(i*nrig---+ j)
sll $t4, $t4, 2 # la moltiplicazione per 4 di cui sopra
sw $t3, Trasp($t4)
addi $t0, 4 # passo all'elemento seguente
addi $t1, 1 # i=i---+1
blt $t1, $t3, ciclo # se non e' ancora finita la riga
li $t1, 0 # i=0
addi $t2, 1 # j=j---+1
blt $t2, $t4, ciclo # se non e' ancora finita la matrice
jr $ra
Esercizio A2 (15 punti)
Si scrivano le due procedure mutuamente ricorsive
F e
G definite come segue:
- F(0) = 0
- F(i) = i - G(i-1) se i>0
- F(i) = 3---+ G(i+i) se i<0
- G(i) = i---+ F(i-1) se i>0
- G(i) = 2 * F(i---+1) se i<0
Soluzione Esercizio A2
.text
F:
beqz $a0, casobaseF # se i=0
bgt $a0, $0, fPositiva # se i>0
blt $a0, $0, fNegativa # se i<0
# F(0) = 0
casobaseF:
li $v0, 0 # F=0
jr $ra
# F(i) = i - G(i-1) se i>0
fPositiva: # devo calcolare F(i) = i - G(i-1)
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
sub $a0, $a0, 1 # i = i-1
jal G # G(i-1)
lw $a0, 4($sp) # ripristino $a0 cioe' i
sub $v0, $a0, $v0 # F=i-G(i-1)
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 8 # libero le 2 words allocate prima
jr $ra # torno dalla subroutine
# F(i) = 3---+ G(i+i) se i<0
fNegativa: # devo calcolare F(i) = 3---+ G(i+i)
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
add $a0, $a0, $a0 # i = i---+i
jal G # G(i---+i)
addi $v0, $v0, 3 # F(i) = 3---+ G(i+i)
lw $a0, 4($sp) # ripristino $a0 cioe' i
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 8 # libero le 2 words allocate prima
jr $ra # torno dalla subroutine
G:
bgt $a0, $0, gPositiva # se i>0
blt $a0, $0, gNegativa # se i<0
# G(i) = i---+ F(i-1) se i>0
gPositiva: # devo calcolare G(i) = i---+ F(i-1)
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
sub $a0, $a0, 1 # i = i-1
jal F # F(i-1)
lw $a0, 4($sp) # ripristino $a0 cioe' i
add $v0, $a0, $v0 # G=i---+F(i-1)
lw $ra, 0($sp) # ripristino $ra
addu $sp, $sp, 8 # libero le 2 words allocate prima
jr $ra # torno dalla subroutine
# G(i) = 2 * F(i---+1) se i<0
gNegativa: # devo calcolare G(i) = 2 * F(i---+1) ... praticamente lo stesso di prima :-)
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
add $a0, $a0, 1 # i = i---+1
jal F # F(i---+1)
li $a0, 2 # mi serve la costante 2, la metto in $a0 che poi ripristinero'
mul $v0, $v0, $a0 # G(i) = 2 * F(i---+i)
lw $a0, 4($sp) # ripristino $a0 cioe' i
lw $ra, 0($sp) # ripristino $ra
addu $sp, $sp, 8 # libero le 2 words allocate prima
jr $ra # torno dalla subroutine
Compito B
Esercizio B1 (15 punti)
Si scriva una procedura che serve a calcolare la somma degli elementi che si trovano sulla diagonale della matrice cubica (a 3 dimensioni) che si chiama
Cubo.
Per far questo:
- si presupponga che il lato del cubo sia stato gia' chiesto in input tramite syscall e che sia compreso tra 1 e 30 inclusi.
- si allochi lo spazio necessario per la matrice Cubo
- si scriva una routine che riceve come argomenti:
- e che calcola la somma degli elementi sulla diagonale
Si ricorda che la diagonale di un cubo e' l'insieme degli elementi con indici uguali
i=j=k
Soluzione Esercizio B1 (lenta)
.data
Cubo: .word 0:27000 # un cubo di lato 30 e' formato da 30*30*30=27000 elementi
.text
# come sommare gli elementi della diagonale senza pensarci troppo su :-)
sommaDiagonaleCuboLenta:
li $t0, 0 # indice in memoria
li $t1, 1 # i=1
li $t2, 1 # j=1
li $t3, 1 # k=1
li $v0, 0 # il risultato all'inizio e' 0
ciclo:
bne $t1, $t2, next # se i!=j vado avanti
bne $t2, $t3, next # i=j ma j!=k, vado avanti
lw $t4, Cubo($t0)
add $v0, $v0, $t4 # i=j=k, sommo l'elemento corrente
next:
addi $t0, $t0, 4 # prossima word in memoria
addi $t1, $t1, 1 # i=i---+1
blt $t1, $a0, ciclo # non e' ancora finita la riga?
li $t1, 1 # i=1 (prima casella della prossima riga)
addi $t2, $t2, 1 # j=j---+1
blt $t2, $a0, ciclo # non e' ancora finita la fetta?
li $t1, 1 # i=1 (prima casella della riga)
li $t2, 1 # j=1 (prima riga del prossimo strato)
addi $t3, $t3, 1 # k=k---+1
blt $t3, $a0, ciclo # non e' ancora finito il cubo?
jr $ra # ritorno al chiamante
Soluzione Esercizio B1 (veloce)
Notate che per passare da un elemento al successivo della diagonale
basta sommare 4*(lato*lato---+ lato + 1) = 4*(lato*(lato+1)+1)
infatti si deve passare al
prossimo strato, prossima riga, prossimo elemento
.data
Cubo: .word 0:27000 # un cubo di lato 30 e' formato da 30*30*30=27000 elementi
.text
sommaDiagonaleCuboVeloce:
li $t0, 0 # indice in memoria
addi $t1, $a0, 1 # calcoliamo (lato---+1)
mul $t1, $t1, $a0 # lato*(lato---+1)
addi $t1, $t1, 1 # lato*(lato---+1)+1
sll $t1, $t1, 2 # moltiplico per 4
li $t2, 1 # i=1 (numero di elementi sommati)
li $v0, 0 # il risultato all'inizio e' 0
ciclo:
lw $t3, Cubo($t0)
add $v0, $v0, $t3 # sommo l'elemento corrente
add $t0, $t0, $t1 # passo al prossimo elemento della diagonale
addi $t2, $t2, 1 # i=i---+1
blt $t2, $a0, ciclo # non e' ancora finita la riga?
jr $ra # ritorno al chiamante
Esercizio B2 (15 punti)
Si scrivano le due procedure mutuamente ricorsive
F e
G definite come segue:
- F(0) = 1
- F(i) = i * G((i-1) mod 9)
- G(i) = F(i-3)---+ 4 se i>0
- G(i) = F(i---+2) * i se i<0
Soluzione Esercizio B2
.text
F:
beqz $a0, casobaseF # se i=0
# F(i) = i * G((i-1) mod 9)
subu $sp, $sp, 12 # alloco tre words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
sw $t0, 8($sp) # salvo su stack $t0 che modifico
sub $a0, $a0, 1 # i = i-1
li $t0, 9 # mi serve la costante 9
rem $a0, $a0, $t0 # i = (i-1 mod 9)
jal G # G((i-1)mod 9)
lw $t0, 8($sp) # ripristino $t0
lw $a0, 4($sp) # ripristino $a0 cioe' i
mul $v0, $a0, $v0 # F=i * G((i-1) mod 9)
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 12 # libero le 3 words allocate prima
jr $ra # torno dalla subroutine
# F(0) = 1
casobaseF:
li $v0, 1 # F=1
jr $ra
G:
bgt $a0, $0, gPositiva # se i>0
blt $a0, $0, gNegativa # se i<0
# G(i) = F(i-3)---+ 4 se i>0
gPositiva: # devo calcolare G(i) = F(i-3)---+ 4
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
sub $a0, $a0, 3 # i = i-3
jal F # F(i-3)
add $v0, $v0, 4 # G(i) = F(i-3)---+ 4
lw $a0, 4($sp) # ripristino $a0 cioe' i
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 8 # libero le 2 words allocate prima
jr $ra # torno dalla subroutine
# G(i) = F(i---+2) * i se i<0
gNegativa: # devo calcolare G(i) = F(i---+2) * i
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
addi $a0, $a0, 2 # i = i---+2
jal F # F(i---+2)
lw $a0, 4($sp) # ripristino $a0 cioe' i
mul $v0, $v0, $a0 # G(i) = F(i---+2) * i
lw $ra, 0($sp) # ripristino $ra
addu $sp, $sp, 8 # libero le 2 words allocate prima
jr $ra # torno dalla subroutine
Compito C
Esercizio C1 (15 punti)
Si scriva una procedura che serve a ruotare gli elementi di una matrice
Matr di una colonna a sinistra (cioe' spostare ciascuna riga di un elemento a sinistra con il primo elemento che va all'ultimo posto).
Per far questo:
- si presupponga che il numero di righe e di colonne siano stati gia' chiesti in input tramite syscall e che siano compresi tra 1 e 20 inclusi.
- si allochi lo spazio necessario per la matrice Matr
- si scriva una routine che riceve come argomenti:
- $a0 = numero di righe
- $a1 = numero di colonne
- e che ruota ogni riga di un elemento a sinistra
Soluzione Esercizio C1
Questo esercizio poteva essere risoloto in vari modi:
- per ogni riga scambiare successivamente due elementi
- 1 con 2, 2 con 3, 3 con 4, ......, n-1 con n
- spostare gli elementi della prima colonna di una riga in giu' e poi spostare tutti gli elementi della matrice di un elemento a sinistra
- per ogni riga:
- mettere da parte il rpimo elemento
- spostare gli altri di un elemento a sinistra
- salvare l'elemento nell'ultima posizione della riga
... devo finire di scrivere la soluzione ...
Esercizio C2 (15 punti)
Si scrivano le due procedure mutuamente ricorsive
F e
G definite come segue:
- F(0,j) = j * 3
- F(i,j) = G(j,i-2)---+ 2
- G(0,j) = j * j
- G(i,j) = F(j---+1,i) * 3
Soluzione Esercizio C2
.text
F:
beqz $a0, casobaseF # se i=0
# F(i,j) = G(j,i-2)---+ 2
subu $sp, $sp, 12 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
sw $a1, 8($sp) # salvo su stack $a0 (cioe' i) che modifico
sub $a1, $a0, 2 # j' = i-2
lw $a0, 8($sp) # i = j
jal G # G(j',i-2)
lw $a1, 4($sp) # ripristino $a1 cioe' j
lw $a0, 4($sp) # ripristino $a0 cioe' i
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 12 # libero le 2 words allocate prima
addi $v0, $v0, 2 # F=G(j,i-2)---+ 2
jr $ra # torno dalla subroutine
# F(0,j) = j * 3
casobaseF:
mul $v0, $a1, 3 # F=j*3
jr $ra
G:
beqz $a0, gBase # se i=0
# G(i,j) = F(j---+1,i) * 3
subu $sp, $sp, 12 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' i) che modifico
sw $a1, 8($sp) # salvo su stack $a0 (cioe' i) che modifico
addi $a0, $a1, 1 # i' = j---+1
lw $a1, 4($sp) # j = i
jal F # F(j---+1,i)
lw $a1, 4($sp) # ripristino $a1 cioe' j
lw $a0, 4($sp) # ripristino $a0 cioe' i
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 12 # libero le 2 words allocate prima
mul $v0, $v0, 3 # F(j---+1,i) * 3
jr $ra # torno dalla subroutine
# G(0,j) = j * j
casobaseF:
mul $v0, $a1, $a1 # G=j*j
jr $ra
Compito D
Esercizio D1 (15 punti)
Si scriva una procedura che serve a calcolare la somma degli elementi che si trovano sulla superficie della matrice cubica (a 3 dimensioni) che si chiama
Cubo.
Per far questo:
- si presupponga che il lato del cubo sia stato chiesto gia' in input tramite syscall e che sia compreso tra 1 e 30 inclusi.
- si allochi lo spazio necessario per la matrice Cubo
- si scriva una routine che riceve come argomenti:
- e che calcola la somma degli elementi presenti sulla superficie
Si ricorda che la superficie di un cubo e' l'insieme degli elementi che hanno almeno un indice
- uguale a 1
- oppure uguale al lato
Soluzione Esercizio D1
.data
Cubo: .word 0:27000 # un cubo di lato 30 e' formato da 30*30*30=27000 elementi
.text
sommaSuperficieCubo:
li $t0, 0 # indice in memoria
li $t1, 1 # i=1
li $t2, 1 # j=1
li $t3, 1 # k=1
li $t4, 1 # costante per i confronti
li $v0, 0 # il risultato all'inizio e' 0
ciclo:
beq $t1, $t4, somma # se i=1 sommo
beq $t1, $a0, somma # se i=lato sommo
beq $t2, $t4, somma # se j=1 sommo
beq $t2, $a0, somma # se j=lato sommo
beq $t3, $t4, somma # se k=1 sommo
beq $t3, $a0, somma # se k=lato sommo
b next
somma:
lw $t4, Cubo($t0)
add $v0, $v0, $t4 # i=j=k, sommo l'elemento corrente
next:
addi $t0, $t0, 4 # prossima word in memoria
addi $t1, $t1, 1 # i=i---+1
blt $t1, $a0, ciclo # non e' ancora finita la riga?
li $t1, 1 # i=1 (prima casella della prossima riga)
addi $t2, $t2, 1 # j=j---+1
blt $t2, $a0, ciclo # non e' ancora finita la fetta?
li $t1, 1 # i=1 (prima casella della riga)
li $t2, 1 # j=1 (prima riga del prossimo strato)
addi $t3, $t3, 1 # k=k---+1
blt $t3, $a0, ciclo # non e' ancora finito il cubo?
jr $ra # ritorno al chiamante
Esercizio D2 (15 punti)
Si scrivano le due procedure mutuamente ricorsive
F e
G definite come segue:
- F(a,b) = a se a=b
- F(a,b) = 2---+ G(a, a-b) se a>b
- F(a,b) = G(a, b-a) se a<b
Soluzione Esercizio D2
.text
F:
beq $a0, $a1, casobaseF # se a=b
blt $a0, $a1, minoreF # se a<b
bgt $a0, $a1, maggioreF # se a>b
# F(a,b) = a se a=b
casobaseF:
move $v0, $a0 # F=a
jr $ra
# F(a,b) = 2---+ G(a, a-b) se a>b
maggioreF:
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a1, 4($sp) # salvo su stack $a1 (cioe' a) che modifico
sub $a1, $a0, $a1 # b=a-b
jal G #
lw $a1, 4($sp) # ripristino $a1 cioe' b
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 8 # libero le 2 words allocate prima
add $v0, $v0, 2 # 2---+ G(a, a-b)
jr $ra # torno dalla subroutine
# F(a,b) = G(a, b-a) se a<b
minoreF:
subu $sp, $sp, 8 # alloco due words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a1, 4($sp) # salvo su stack $a1 (cioe' a) che modifico
sub $a1, $a1, $a0 # b=b-a
jal G #
lw $a1, 4($sp) # ripristino $a1 cioe' b
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 8 # libero le 2 words allocate prima
jr $ra # torno dalla subroutine
# G(a,b) = a * F(b, a)
G:
subu $sp, $sp, 12 # alloco tre words su stack
sw $ra, 0($sp) # salvo su stack il return address perche' F e G sono mutuamente ricorsive
sw $a0, 4($sp) # salvo su stack $a0 (cioe' a) che modifico
sw $a1, 8($sp) # salvo su stack $a1 (cioe' b) che modifico
move $a0, $a1 # scambio gli argomenti
lw $a1, 4($sp)
jal F # F(b,a)
lw $a1, 8($sp) # ripristino $a1 cioe' b
lw $a0, 4($sp) # ripristino $a0 cioe' a
lw $ra, 0($sp) # ripristino $ra
add $sp, $sp, 12 # libero le 3 words allocate prima
add $v0, $v0, $a0 # a * F(b, a)
jr $ra # torno dalla subroutine
--
AndreaSterbini - 19 Jun 2001