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

Edit | Attach | Watch | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r5 - 2001-09-28 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback