SoluzioniProva14Settembre2001 < Architetture2/MZ

---++ Prova pratica di Assembler - 14 Settembre 2001

	* Vedi RisultatiProva14Settembre2001
----
%TOC%
----
---+++ 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.
<blockquote style="background-color:#f5f5f5">
<pre>
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
</pre>
</blockquote>

---++++ 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

<blockquote style="background-color:#f5f5f5">
<pre>
.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
</pre>
</blockquote>

----
---+++ 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.

<blockquote style="background-color:#f5f5f5">
<pre>
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
</pre>
</blockquote>

---++++ 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

<blockquote style="background-color:#f5f5f5">
<pre>
.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
</pre>
</blockquote>

----
---+++ 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.

<blockquote style="background-color:#f5f5f5">
<pre>
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
</pre>
</blockquote>

---++++ 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

<blockquote style="background-color:#f5f5f5">
<pre>
.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
</pre>
</blockquote>
----
---+++ 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.

<blockquote style="background-color:#f5f5f5">
<pre>
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
</pre>
</blockquote>

---++++ 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

<blockquote style="background-color:#f5f5f5">
<pre>
.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
</pre>
</blockquote>

----
-- Users.AndreaSterbini - 13 Sep 2001 <br>

<!--
	* Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
-->
This topic: Architetture2/MZ > SoluzioniProva14Settembre2001
Topic revision: r5 - 2001-09-28 - AndreaSterbini