Präsenz¨ubung 1 - Universität Paderborn

SoSe 2014
Konzepte und Methoden der Systemsoftware
Universität Paderborn
Fachgebiet Rechnernetze
Präsenzübung 1
2014-04-21 bis 2014-04-27
Aufgabe 1: Assembler Wiederholung
0P
Eine Kurzübersicht zu x86-Assembler befindet sich im Anhang.
(a) (0 Punkte) Geben Sie einen groben Überblick, wie eine CPU aufgebaut ist.
Lösung:
Eine CPU besteht aus Rechenwerk und Steuerwerk. Das Steuerwerk setzt Instruktionen um und
ist für die Ablaufsteuerung zuständig. Das Rechenwerk führt arithmetische Operationen durch.
(Folie 1.15)
(b) (0 Punkte) Nennen Sie die am häufigsten verwendeten Register eines x86-Prozessors. Welche
Größe besitzen sie? Nennen Sie zwei Möglichkeiten, auf das zweite (least-significant) Byte in
Register EAX zuzugreifen.
Hinweis: Diese Informationen finden Sie nicht in den Vorlesungsfolien.
Lösung:
Die am häufigsten verwendeten Register sind die Allzweckregister EAX, EBX, ECX, EDX, ESI,
EDI, das Stackpointer-Register ESP, das Basepointer-Register EBP.
Diese Register sind alle 32 Bit groß. Innerhalb der ersten vier gibt es jeweils noch Unterregister.
Für EAX sind das AX, AH und AL, wobei AX die least significant 16 bit von EAX enthält und
selbst in AH und AL zu je 8 bit aufgeteilt ist.
Damit ergibt sich auch gleiche eine Möglichkeit auf das zweite Byte in Register EAX zuzugreifen: Das Register AH enthält dieses. Eine zweite Möglichkeit ist, den Inhalt in EAX durch
Maskieren (and eax, 0xff00) und Verschieben (shr eax, 8) zu verändern.
Musterlösung KMS SoSe 2014
Präsenzübung 1
1/5
(c) (0 Punkte) Übersetzen Sie den folgenden (defekten) Assemblercode in Pseudocode! Welche Argumente werden ihm in den Registern ECX und EDX übergeben? Welcher bekannte Algorithmus
wurde hier versucht zu implementieren?
; ; ; P a r a m e t e r : ecx , e d x
function :
l1 :
cmp edx , 1
jle el1
mov e s i , 1
l2 :
cmp e s i , edx
jge el2
mov a l , b y t e [ e c x + e s i −1]
mov bl , b y t e [ e c x + e s i ]
cmp a l , b l
j l e ns
mov [ e c x + e s i −1] , b l
mov [ e c x + e s i ] , a l
ns :
inc e s i
jmp l 2
el2 :
jmp l 1
el1 :
ret
Lösung:
Der Algorithmus ist ein Bubblesort, der sein Suchfenster nie verkleinert und somit nicht terminiert. Register ECX enthält einen Zeiger auf das Array mit den zu sortierenden Bytes, Register
EDX enthält die Anzahl der zu sortierenden Bytes.
w h i l e ( l e n >1) {
i = 1;
while ( i < len ) {
i f ( a r r [ i −1] > a r r [ i ] ) {
swap ( a r r [ i −1] , a r r [ i ] ) ;
i += 1 ;
}
/ / l e n −= 1 ; h i e r i s t d e r bug −> A u f g a b e 1 d
}
}
return ;
(d) (0 Punkte) Finden und korrigieren Sie den Fehler in Teilaufgabe (c).
Lösung:
Die äußere Schleife ist eine Endlosschleife, es fehlt ein dec edx vor jmp l1:
ns :
el2 :
el1 :
inc
jmp
dec
jmp
ret
esi
l2
edx
l1
Musterlösung KMS SoSe 2014
Präsenzübung 1
2/5
Aufgabe 2: Unterprogrammaufrufe
0P
Eine Kurzübersicht zu x86-Assembler befindet sich im Anhang.
(a) (0 Punkte) Was ist der (Laufzeit-) Stack? Wozu wird er benötigt und wie wird er verwendet?
Lösung:
Der Stack ist per se ein Speicherbereich. Er dient zur Verwaltung von Unterprogrammen, in
ihm werden Aufrufparameter, lokale Variablen und Rücksprungadressen gespeichert. Er wird
benötigt um rekursive Aufrufe von Unterprogrammen zu ermöglichen.
(b) (0 Punkte) Was versteht man unter einer Aufrufkonvention und wozu dient sie?
Hinweis: Diese Informationen finden Sie nicht in den Vorlesungsfolien.
Lösung:
Eine Aufrufkonvention ist eine Vereinbarung, wie ein Unterprogramm aufgerufen wird. Sie
gibt an, wie Parameter an das Unterprogramm übergeben werden, bspw. in Registern oder auf
dem Stack und in welcher Reihenfolge. Sie gibt weiterhin an, wie das Unterprogramm seine
Rückgabewerte zurück gibt, wie die Rücksprungadresse zu finden ist und Welche Register nach
Rückkehr aus dem Unterprogramm verändert sein dürfen. Sie beschreibt auch, wer die Funktionsparameter wieder vom Stack entfernt.
(c) (0 Punkte) Die Anweisungen push, call und ret vereinfachen das Schreiben von Unterprogrammen, sie sind jedoch nicht notwendig: Ihre Funktion kann auch durch andere Anweisungen
ausgedrückt werden. Schreiben Sie jeweils Assemblercode, der sie ersetzen kann.
Lösung:
1. push arg1
sub esp , 4 ; 4 B y t e P l a t z a u f dem S t a c k s c h a f f e n
mov [ e s p ] , a r g 1
2. call arg1
sub esp , 4
mov [ e s p ] , r e t
jmp a r g 1
ret :
3. ret
pop eax
jmp eax
(d) (0 Punkte) Was berechnet der folgende Assemblercode? Beschreiben Sie die verwendete Aufrufkonvention. Wie ruft man ihn auf? Zeichnen Sie das Stacklayout eines Aufrufes!
func :
rec :
done :
sub esp , 4
cmp [ e s p +0 x8 ] , dword 0 x1
jg rec
mov eax , 1
jmp done
mov eax , [ e s p +0 x8 ]
dec eax
push eax
c a l l func
add esp , 0 x4
mov [ e s p ] , eax
imul eax , dword [ e s p +0 x8 ]
mov [ e s p ] , eax
add esp , 4
ret
Musterlösung KMS SoSe 2014
Präsenzübung 1
3/5
Lösung:
Der Code berechnet rekursiv die Fakultät. Äquivalent:
int fak ( int n ) {
i f ( n <= 1 ) r e t u r n 1 ;
return n∗ f a k ( n −1);
}
Aufrufkonvention: Der Aufrufer legt das Argument auf den Stack, dann die Rücksprungadresse.
Der Aufrufer entfernt nach Rückkehr der Funktion den Parameter wieder vom Stack (add esp,0x4).
Der Rückgabewert steht in Register EAX.
Stacklayout:
...
Argument
Rücksprungadresse
lokale Variable
esp
Aufruf fak(17):
push 17
c a l l func
Hinweis: Die lokale Variable [esp] ist überflüssig (sie wird offensichtlich nicht gelesen und die
Rückgabe steht auch in Register EAX). Sie dient nur zur Vorbereitung auf die nächste Teilaufgabe.
(e) (0 Punkte) Implementieren Sie eine Funktion zur rekursiven Berechnung von Elementen der
Fibonacci-Folge in Assembler.
Überläufe ab dem 47. Element können Sie dabei ignorieren.
(
f (n − 1) + f (n − 2) n > 2
f (n) =
1
sonst
Lösung:
fib :
rec :
done :
sub esp , 0 x4
cmp [ e s p +0 x8 ] , dword 0 x2
jg rec
mov eax , 1
jmp done
mov eax , [ e s p +0 x8 ]
dec eax
push eax
call fib
add esp , 0 x4
mov [ e s p ] , eax
mov eax , [ e s p +0 x8 ]
sub eax , 2
push eax
call fib
add esp , 0 x4
add eax , dword [ e s p ]
add esp , 0 x4
ret
Musterlösung KMS SoSe 2014
Präsenzübung 1
4/5
x86 Kurzübersicht (Intel-Syntax)
Registergrößen
EAX
AX
AL
AH
Speicherzugriff
mov eax,[17]
mov eax,[esp]
mov eax,[ebx]
mov eax,[ebx+3]
mov [ecx],dword 5
mov [ecx],byte 5
Anweisungen
add r1,arg2
sub r1,arg2
xor r1,arg2
imul r1,arg2
shr r1,arg2
mov r1,arg2
inc r1
dec r1
nop
jmp arg1
cmp r1,arg2
jg/jl arg1
je/jne arg1
jge arg1
jle arg1
call arg1
ret
push arg1
pop r1
int arg1
32 bit
16 bit, AX=EAX[1:16]
je 8 bit, AL=AX[1:8], AH=AX[9:16]
Schreibt in eax das dword, das an Adresse 17 im Speicher steht
Schreibt in eax das dword, das oben auf dem Stack liegt
Schreibt in eax das dword, das an der Speicheradresse aus ebx steht
Schreibt in eax das dword, das an der Speicheradresse ebx+3“ steht
”
Schreibt eine 5 (als 4 byte-dword) an die Speicheradresse, die in ecx steht
Schreibt eine 5 (als 1 byte) an die Speicheradresse, die in ecx steht
r1 = r1 + arg2
r1 = r1 - arg2
r1 = r1 ˆ arg2
r1 = r1 · arg2
r1 = r1 arg2
r1 = arg2
r1 = r1+1
r1 = r1-1
no op
springe zu Adresse arg1
r1 mit arg2 vergleichen und das Ergebnis in den Prozessorflags speichern
springe zu Adresse arg1, falls der letzte Vergleich größer“ / kleiner“ ergeben hat
”
”
springe zu Adresse arg1, falls der letzte Vergleich gleich“ / ungleich“ ergeben hat
”
”
springe zu Adresse arg1, falls der letzte Vergleich größer oder gleich“ ergeben hat
”
springe zu Adresse arg1, falls der letzte Vergleich kleiner oder gleich“ ergeben hat
”
pusht die nächste Adresse (als Rücksprungadresse) auf den Stack und springt zu arg1
springt an die Adresse (Rücksprungadresse), die ganz oben auf dem Stack liegt
aktualisiert den Stackpointer und schreibt arg1 auf den Stack
läd das oberste Element vom Stack in r1 und aktualisiert den Stackpointer
löst den Interrupt arg1 aus - üblicherweise benutzt als int 0x80 für syscalls
Die Argumente r1 müssen schreibbar sein, also Register oder Speicherreferenzen.
Arg1/2 können auch immediates sein. Bspw. add eax,7
Beispiel bedingter Sprung
cmp eax , 70
jle label1
Siehe auch: http://www.cs.virginia.edu/ evans/cs216/guides/x86.html
Musterlösung KMS SoSe 2014
Präsenzübung 1
5/5