[SOLVED] algorithm Java MIPS Musterlo sung

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 Error
# 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
jEnde
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

Die Tuerme von Hanoi
–

.asciiz
Anzahl der Scheiben ( 0<=n<=20;) n = “.asciiz”

“.asciiz”Bewege Scheibe “.asciiz” von Stapel “.asciiz” nach Stapel “.asciiz”
“.asciiz”
Wert zu hoch! (0<=n<20)
“.asciiz”
Wert zu klein! (0<=n<20)
” 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 mainli $v0,4la $a0,str0syscallli $v0,4la $a0,str1syscallli $v0,5syscalla(0, m) = m + 1a(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 nblt$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
jalackermann
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
jreturn
# 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
jalackermann # und rufe die Ackermann-Funktion erneut auf
jreturn
MNichtNull:
addi $a1,$a1,-1# Setze $a1 auf m-1
jalackermann # 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
jalackermann # 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

Ackermann-Funktion
–

.asciiz
Wert fuer n ( 0<=n<10;) n = “.asciiz”
Wert fuer m ( 0<=m<10;) m = “.asciiz”

Ackermann liefert: “.asciiz”
Wert zu hoch! (0<=n, m<10)
“.asciiz”
Wert zu klein! (0<=n, m<10)
“Seite 10 / 10