Musterlo ̈sung
U ̈bung4 RAWiSe18/19
Aufgabe 1 (Berechnung von n!)
Im folgenden ist der Code fu ̈r die in der Vorlesung besprochene Prozedur zur Berechnung
# schaffe Platz fuer 2 Worte # sichere Ruecksprungadresse # sichere Argument n #n<1?
# if (n >= 1) goto L1
# Resultat ist 1
# entferne 2 Worte vom Stack
# Ruecksprung
#n=n-1
# rekursiver Aufruf
# stelle Argument n wieder her
# stelle Ruecksprungadresse wieder her # gib n*fact(n-1) zurueck
# entferne 2 Worte vom Stack
# Ruecksprung
von n! gegeben: fact: addi
$sp, $sp, -8
sw $ra, 4($sp)
sw $a0, 0($sp)
slti $t0, $a0, 1
beq $t0, $zero, L1
addi $v0, $zero, 1
addi $sp, $sp, 8
jr $ra
L1: addi
jal fact
lw $a0, 0($sp)
lw $ra, 4($sp)
mul $v0, $a0, $v0
addi $sp, $sp, 8
jr $ra
$a0, $a0, -1
(1) Laden Sie den Sourcecode dieser Prozedur, fact.s, von der PANDA-Seite und schreiben Sie ein Programm, das eine Zahl n einliest, n! berechnet und ausgibt. Verwenden Sie dazu die Programmteile (Eingabe, Ausgabe) aus den Programmen der letzten U ̈bung.
(2) Testen Sie das Programm mit MARS im single-step Modus. Beobachten Sie, wie der Stack durch die Funktionsaufrufe aufgebaut wird. Welche Register mu ̈ssen auf den Stack gesichert werden und warum? Unter welchen Bedingungen kann man auf das Sichern der Ru ̈cksprungadresse verzichten?
Musterlo ̈sung
(1) —
(2) Siehe Vorlesungsfolien. Eine Prozedur kann auf das Sichern der Ru ̈cksprungadresse nur verzichten, wenn sie keine weiteren Prozeduren aufruft.
Seite 1 / 10
Musterlo ̈sung
U ̈bung4 RAWiSe18/19
Aufgabe 2 (Sortierprogramm)
Gegeben ist folgender Javacode:
public class sort {
public static void sort (int[] v) {
for (int i = 0; i < v.length; i += 1) {
for (int j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1) {
swap(v, j);
} }
}
protected static void swap(int[] v, int k) {
int temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
} }
(1) Erkla ̈ren Sie die Funktionsweise des Sortierprogramms.
(2) Schreiben Sie ein MIPS Assemblerprogramm, das dieses Sortierverfahren imple- mentiert. Der angegebe Javacode dient lediglich als Spezifikation des Algorithmus. Java-Operationen wie v.length oder Bereichspru ̈fungen bei der Arrayadressierung mu ̈ssen nicht in Assembler nachgebildet werden.
(3) Testen Sie das Assemblerprogramm, indem Sie ein statisches Feld von 8 Worten definieren und sortieren lassen.
Seite 2 / 10
Musterlo ̈sung
U ̈bung4 RAWiSe18/19
Musterlo ̈sung
BubbleSort in MIPS-Assembler:
main:
.text
.globl main
li $v0, 4
la $a0, str0
syscall
li $v0, 4
la $a0, str1
syscall
lw $t7, Size
sll $t7, $t7, 2
Ausgabe1:
OuterLoop:
InnerLoop:
li $v0, 1
lw $a0, NStart($t6)
syscall
li $v0, 4
la $a0, str2
syscall
addi $t6, $t6, 4
blt $t6, $t7, Ausgabe1
li $v0, 4
la $a0, str3
syscall
li $t0, 0
addi $t1, $t0,
addi $t0, $t0, 4
bltz $t1, OuterLoop
add $t2, $t1, 4
lw $t5, NStart($t1)
lw $t6, NStart($t2)
ble $t5, $t6, OuterLoop
sw $t6, NStart($t1)
sw $t5, NStart($t2)
addi $t1, $t1, -4
bgez $t1, InnerLoop
#$t0auf0setzen($t0=i)
#$t0-4nach$t1($t1=j) # i+=4
# j+1 berechnen
# v[j]
# v[j+1]
# v[j] = v[j+1]
# v[j+1] = v[j]
li $t6,
0
# Ausgabe des Titels
# Size nach $t7
# Auf Wortadresse bringen #$t6=0
-4
Seite 3 / 10
Musterlo ̈sung
U ̈bung4 RAWiSe18/19
blt $t0, $t7, OuterLoop # i
# Eingabe kleiner als Minimalwert?
# Wenn ja -> Error
# Sichere n
# Ausgabe Sting 2
# Uebergabeargumente setzten $a0 = n #$a1=start=1
#$a2=finish=2
#$a3=extra=3
# Programm Ende 10: exit
# Fuer 5 Woerter Platz schaffen
# Ruecksprungadresse
# extra
# finish
Ende:
hanoi:
move $a0, $s7
li $a1, 1
li $a2, 2
li $a3, 3
jal hanoi
li $v0, 10
syscall
addi $sp, $sp, -20
sw $ra, 16($sp)
sw $a3, 12($sp)
sw $a2, 8($sp)
li
la
syscall
j Ende
move
li
la
syscall
$s7, $v0
$v0, 4
$a0, str2
$v0, 4
$a0, err2
Seite 6 / 10
Musterlo ̈sung
U ̈bung4 RAWiSe18/19
sw $a1, 4($sp)
sw $a0, 0($sp)
bnez $a0, NNichtNull
j return
NNichtNull:
addi $a0, $a0, -1
lw $a1, 4($sp)
lw $a2, 12($sp)
lw $a3, 8($sp)
jal hanoi
li $v0, 4
la $a0, str3
syscall
li $v0, 1
lw $a0, 0($sp)
syscall
li $v0, 4
la $a0, str4
syscall
li $v0, 1
lw $a0, 4($sp)
syscall
li $v0, 4
la $a0, str5
syscall
li $v0, 1
lw $a0, 8($sp)
syscall
li $v0, 4
la $a0, str6
syscall
lw $a0, 0($sp)
addi $a0, $a0, -1
lw $a1, 12($sp)
lw $a2, 8($sp)
lw $a3, 4($sp)
jal hanoi
return:
lw $a0, 0($sp)
lw $a1, 4($sp)
lw $a2, 8($sp)
lw $a3, 12($sp)
lw $ra, 16($sp)
# start #n
# Wenn n=0, Ruecksprung
# n = n-1
# start
# extra
# finish
# Hanoi aufrufen
# Ausgabe
#nnach$a0
# Ausgabe
# start nach $a0
# Ausgabe
# finish nach $a0
# Ausgabe
#nnach$a0 # n = n-1
# extra
# finish
# start
# Hanoi aufrufen
Seite 7 / 10
str0:
str1:
str2:
str3:
str4:
str5:
str6:
err1:
err2:
Musterlo ̈sung
U ̈bung4 RAWiSe18/19
addi $sp, $sp, 20 # Stack freigeben
jr $ra
.data
.align 2
.asciiz “\n\n\nDie Tuerme von Hanoi\n—————————-\n\n”
.asciiz “\nAnzahl der Scheiben ( 0<=n<=20;) n = "
.asciiz "\n\n"
.asciiz "Bewege Scheibe "
.asciiz " von Stapel "
.asciiz " nach Stapel "
.asciiz "\n"
.asciiz "\nWert zu hoch! (0<=n<20)\n"
.asciiz "\nWert zu klein! (0<=n<20)\n"
Aufgabe 4 (Ackermann-Funktion)
Schreiben Sie ein MIPS-Assemblerprogramm fu ̈r die Ackermannfunktion a(n, m), die fol- gendermassen rekursiv definiert ist:
main:
.text
.align 2
.globl main
li $v0, 4
la $a0, str0
syscall
li $v0, 4
la $a0, str1
syscall
li $v0, 5
syscall
a(0, m) = m + 1
a(n + 1,0) = a(n,1)
a(n + 1, m + 1) = a(n, a(n + 1, m))
Musterlo ̈sung
# Ausgabe des Titels
# Ausgabe Eingabestring 1
# Eingabe fuer n
blt $v0, 10, test2 # Eingabe groesser als Maximalwert?
li $v0, 4 # Wenn ja -> Error
Seite 8 / 10
test2:
EingabeM:
Musterlo ̈sung
U ̈bung4 RAWiSe18/19
la $a0, err1
syscall
j ende
bge $v0, $zero, EingabeM # Eingabe kleiner als Minimalwert?
test3:
testok:
blt $v0, 10, test3 # Eingabe groesser als Maximalwert?
li $v0, 4 # Wenn ja -> Error
la $a0, err1
syscall
j ende
bge $v0, $zero, testok # Eingabe kleiner als Minimalwert?
li $v0, 4
la $a0, err2
syscall
j ende
move $s0, $v0
li $v0, 4
la $a0, str2
syscall
li $v0, 5
syscall
# Wenn ja -> Error
# Wert n in $s0 speichern
# Ausgabe Eingabestring 2
# Eingabe fuer m
li $v0, 4
la $a0, err2
syscall
j ende
move $s1, $v0
move $a0, $s0
move $a1, $s1
jal ackermann
move $s0, $v0
li $v0, 4
la $a0, str3
syscall
li $v0, 1
move $a0, $s0
syscall
# Wenn ja -> Error
# Wert von m in $S1 speichern
# Uebergabeargumente setzten $a0 = n #$a1=m
# Ergebnis sichern nach $s0
# Ausgabe Eingabestring 2
# Ergebnis nach $a0
Seite 9 / 10
ende:
ackermann:
Musterlo ̈sung
U ̈bung4 RAWiSe18/19
li $v0, 10 # Programm Ende 10: exit
syscall
addi $sp, $sp, -12 # Fuer 3 Woerter Platz schaffen
sw $ra, 8($sp)
sw $a1, 4($sp)
sw $a0, 0($sp)
bnez $a0, NNichtNull
addi $v0, $a1, 1
j return
# Wenn n=0 gebe m+1 zurueck (in $v0)
NNichtNull:
bnez $a1, MNichtNull
addi $a0, $a0, -1 # Wenn m=0, setzte $a0 auf n-1
addi $a1, $zero, 1 # und $a1 auf 1
jal ackermann # und rufe die Ackermann-Funktion erneut auf
j return
MNichtNull:
addi $a1, $a1, -1 # Setze $a1 auf m-1
jal ackermann # und rufe die Ackermann-Funktion erneut auf
move $a1, $v0 # Setze m auf den Rueckgabewert der Ackermann-Funktion
addi $a0, $a0, -1 # Setzte $a0 auf n-1
jal ackermann # und rufe die Ackermann-Funktion erneut auf
return:
str0:
str1:
str2:
str3:
err1: err2:
lw $a0, 0($sp)
lw $a1, 4($sp)
lw $ra, 8($sp)
addi $sp, $sp, 12 # Stack freigeben
jr $ra
.data
.align 2
.asciiz “\n\n\nAckermann-Funktion\n—————————-\n\n”
.asciiz “\nWert fuer n ( 0<=n<10;) n = "
.asciiz "\nWert fuer m ( 0<=m<10;) m = "
.asciiz "\n\nAckermann liefert: "
.asciiz "\nWert zu hoch! (0<=n, m<10)\n"
.asciiz "\nWert zu klein! (0<=n, m<10)\n"
Seite 10 / 10