1 Maschinenprogrammierung auf x86-Linux für Anfänger Robert Clausecker 2 Material Referenzen und Handbücher: http://c9x.me/x86 http://ref.x86asm.net/coder64-abc.html http://software.intel.com/en-us/articles/intel-sdm http://sourceware.org/binutils/docs/as Tutorials und Bücher: Assembly Language Step by Step (Jeff Duntemann) Programming from the Ground Up (Jonathan Bartlett) x86 Assembly (Wikibooks) 3 Arbeitsumgebung Benötigte Werkzeuge: - ein Texteditor (z.B. ed, vi, emacs, nano) - ein Assembler (hier: GNU as) - ein Linker (ld) Assemblerprogramme werden in .s-Dateien gespeichert. Wir benutzen den C-Kompiler, um Assembler und Linker aufzurufen. cc -o programm programm.s Weiter Werkzeuge: - ein Debugger (z.B. gdb) - ein Disassembler (z.B. objdump) 4 Hallo Welt (Aufgabe 1) .section .text .global main main: push %rbp mov %rsp,%rbp mov $hallo,%rdi call printf mov $0,%eax leave ret .section .rodata hallo: .string "Hallo Welt!\n" 5 Hallo Welt (erklärt) .section .text # Wechsel in den Abschnitt .text .global main # main ist globales Symbol main: # Hier ist main push %rbp # alten Rahmen sichern mov %rsp,%rbp # neuen Rahmen etablieren mov $hallo,%rdi # Argument laden call printf # Zeichenkette ausgeben mov $0,%eax # Rückgabewert 0 (Erfolg) leave # Rahmen zurücksetzen ret # Funktion beenden .section .rodata # in den Abschnitt rodata wechseln hallo: # Hier ist hallo .string "Hallo Welt!\n" # terminierte Zeichenkette "Hello, World!" 6 Register Ganzzahlregister (64 Bit): rax, rbx, rcx, rdx, rsi, rdi, rbp, rsp, r8--r15 Register können unterteilt werden: 64 Bit 32 Bit 16 Bit 8 Bit rax eax ax al ah rbx ebx bx bl bh rcx ecx cx cl ch rdx edx dx dl dh rsi esi si sil rdi edi di dil rbp ebp bp bpl r8 r8d r8w r8b ... ... ... ... r15 r15d r15w r15b ah, bh, ch, und dh gibt es nur für rax, rbx, rcx, und rdx! 7 Register Register können unterteilt werden: +-------+-------+-------+-------+-------+-------+-------+-------+ rax | eax | | | | | +-------+-------+-------+-------+-------+-------+-------+-------+ +-------+-------+-------+-------+-------+-------+-------+-------+ rax | ax | | | | | | | +-------+-------+-------+-------+-------+-------+-------+-------+ +-------+-------+-------+-------+-------+-------+-------+-------+ rax | al | ah | | | | | | | +-------+-------+-------+-------+-------+-------+-------+-------+ 8 Grundlegende Befehle mov a,b Kopiert Daten aus a nach b. a kann Register oder Zahl sein. mov $1337,%ax # lädt 1337 nach ax mov $msg,%rax # lädt Wert des Symbols msg in eax mov %rax,%rbx # kopiert rax nach rbx $ bezeichnet einen Immediat-Operanden, % bezeichnet einen Register-Operanden. call func Ruft Funktion func auf. Argumentregister: rdi, rsi, rdx, rcx, r8, r9 erhaltene Register: rsp, rbp, r12, r13, r14, r15 zerstörte Register: alle Argumentregister, rax, r10, r11 9 Textausgabe printf(fmt, ...) Gibt Zeichenkette mit Platzhaltern aus, für jeden Platzhalter wird ein weiteres Argument übergeben. %d Zahl %s Zeichenkette %p Adresse %f Gleitkommazahl \n Zeilenumbruch Beispiel: mov $fmt,%rdi mov $18,%esi call printf fmt: .string "Mit %d Jahren ist man erwachsen.\n" 10 Aufgabe 2 Was steht beim Programmstart in den Argumentregistern rdi, rsi, rdx, rcx, r8, und r9? Wie ändert sich der Inhalt, wenn Kommandozeilenargumente übergeben werden? Schreibe ein Programm, das herauszufinden! 11 Auflösung main(argc, argv, envp) argc (edi): Anzahl der Kommandozeilenargumente argv (rsi): Zeiger auf Array mit Argumenten envp (rdx): Zeiger auf Umgebungsvariablen (nicht weiter wichtig) Wie können wir auf die Kommandozeilenargumente zugreifen? 12 Der Arbeitsspeicher - wenn die Register nicht mehr ausreichen, können wir Daten im Arbeitsspeicher ablegen - der Arbeitsspeicher kennt keine Datentypen - jedes Byte hat eine Adresse - Adressen erlauben es uns auf Daten zu verweisen, die sonst nicht in Register passen (wie Strings) 13 Speicheroperanden (%rax) beschreibt den Speicher an der in rax stehenden Adresse 1234 beschreibt den Speicher an Adresse 1234 (merke: kein $). Statt einer Zahl kann auch ein Label verwendet werden. 1234(%rax) beschreibt Speicher an Adresse 1234 + %rax. disp(%base,%index,scale) beschreibt Speicher an Adresse disp + base + index * scale. disp ist Zahl oder Label, base und index sind Register, scale ist 1, 2, 4, oder 8. Jeder Teil bis auf scale kann weggelassen werden. Beispiel: mov (%rax,%rbx,8),%rcx # lädt Speicher an Adresse rax+rbx*8 nach rcx 14 Auf Kommandozeilenargumente zugreifen Aufrufe: ./programm foo bar baz +------------+ | 0 | (Nullzeiger) +------------+ | Argument 3 | --> "baz" +------------+ | Argument 2 | --> "bar" +------------+ | Argument 1 | --> "foo" +------------+ rsi --> | Argument 0 | --> "./programm" +------------+ Beispiel: mov (%rsi),%rax # lädt Zeiger auf Programmname nach rax mov 8(%rsi),%rbx # lädt Zeiger auf erster Argument nach rbx mov 24(%rsi),%rcx # lädt Zeiger auf drittes Argument nach rcx 15 Aufgabe 3 Erweitere das Hallo-Welt-Programm, sodass es dich nach Namen grüßt. Was passiert, wenn kein Name übergeben wird? Beispiel: $ ./hallo Hans Hallo Hans! 16 Arbeiten mit Variablen und Konstanten I .string "foo" Erzeugt String mit Inhalt "foo" .quad xyz Erzeugt 64-Bit Zahl mit Wert xyz .int xyz Erzeugt 32-Bit Zahl mit Wert xyz .short xyz Erzeugt 16-Bit Zahl mit Wert xyz .byte xyz Erzeugt 8-Bit Zahl mit Wert xyz 17 Arbeiten mit Variablen und Konstanten II Beispiele: primes: .int 2, 3, 5, 7, 11, 13, 17, # Tabelle von Primzahlen .int 19, 23, 29, 31, 37, 41, .int 43, 47, 53, 59, 61, 67 mov primes,%eax # lade erste Primzahl (eax = 2) mov primes+4,%eax # lade zweite Primzahl (eax = 3) mov primes(,%rcx,4),%eax # lade rcx-te Primzahl msg: .string "Chemnitzer Linuxtage" mov $msg,%rsi # lade Adresse von msg nach rsi mov 8(%rsi),%al # lade 8. Buchstaben nach al 18 Aufgabe 4 Schreibe ein Programm, das eine Zahl als Argument entgegen nimmt, und in einen Wochentag umrechnet. Benutze dazu die Funktion atol(str) Konvertiert str (in rdi) in eine Zahl in rax. 19 Rechnen mit dem Computer Der Computer kann natürlich auch rechnen: add a,b b = b + a sub a,b b = b - a neg a a = -a imul a,b b = b * a 20 Aufgabe 5 Schreibe ein Programm, was die zwei Kommandozeilenargumente summiert und das Ergebnis ausgibt. Beispiel: $ ./programm 1 2 1 + 2 = 3 21 Vergleichen und Springen I Zahlen können verglichen werden cmp a,b vergleiche b mit a jmp label Springe zu Label je label ; jne label Springe, wenn b == a bzw. wenn b != a jg label ; jle label Springe, wenn b > a bzw. wenn b <= a jl label ; jge label Springe, wenn b < a bzw. wenn b >= a 22 Vergleichen und Springen II Beispiel: wenn (eax == ebx) cmp %eax,%ebx jne 0f foo(); call foo jmp 1f sonst bar(); 0: call bar 1: ... 23 Vergleichen und Springen III | /-------------\ / cmp %eax,%ebx \ < >-. \ jne 0f / \ \-------------/ | | | | | +---------------+ V | call foo | | | jmp 1f | | +---------------+ | / / ,----<----' ,----<----' / / | +---------------+ V | call bar | | +---------------+ \ | `---->-----+ | 24 Aufgabe 6 Repariere das Programm aus der vorherigen Aufgabe, sodass es überprüft, wie viele Argumente übergeben wurden. Beispiel: $ ./programm 1 2 3 $ ./programm 0 Bitte zwei Argumente angeben! 25 Schleifen mindestens einmal: mach 0: foo(); call foo solange (eax == ebx) cmp %eax,%ebx je 0b Null- oder mehrmals: solange (eax == ebx) jmp 1f foo(); 0: call foo 1: cmp %eax,%ebx je 0b 26 Aufgabe 7 Schreibe ein Programm, was die Fakultät einer Zahl berechnet. Es ist: n! = 1 * 2 * 3 * ... * (n - 1) * n Beispiel: $ ./programm 5 120 $ ./programm 7 5040 Was passiert, wenn 0 übergeben wird? Was passiert, wenn große Zahlen übergeben werden? 27 Aufgabe 8 Implementiere echo, d.h. schreibe ein Programm, das seine Argumente ausgibt. Beispiel: $ ./programm foo bar baz foo bar baz $ ./programm hallo welt und so hallo welt und so 28 Der Stapel - jeder Prozess hat einen Stapel - dieser wird über die Register %rsp und %rbp angesprochen - wir der Stapel wächst nach unten, jedes Element ist 8 Byte groß - wenn uns die Register ausgehen, können wir sie auf den Stapel legen - genauso kann man kleine Puffer auf dem Stapel allozieren push foo wie sub $8,%rsp ; mov foo,(%rsp) pop foo wie mov (%rsp),foo ; add $8,%rsp 29 Der Aufrufrahmen I Was macht dieser Rahmen, den wir die ganze Zeit mitführen? push %rbp mov %rsp,%rbp ... leave ret 30 Der Aufrufrahmen II Was macht dieser Rahmen, den wir die ganze Zeit mitführen? > push %rbp . . . <- rbp mov %rsp,%rbp +-------------------+ | Rücksprungadresse | <- rsp ... +-------------------+ | ? ? ? | leave +-------------------+ ret | ? ? ? | +-------------------+ . . . +-------------------+ | ? ? ? | +-------------------+ 31 Der Aufrufrahmen III Was macht dieser Rahmen, den wir die ganze Zeit mitführen? > push %rbp . . . <- rbp mov %rsp,%rbp +-------------------+ | Rücksprungadresse | ... +-------------------+ | alter rbp | <- rsp leave +-------------------+ ret | ? ? ? | +-------------------+ . . . +-------------------+ | ? ? ? | +-------------------+ 32 Der Aufrufrahmen IV Was macht dieser Rahmen, den wir die ganze Zeit mitführen? push %rbp . . . > mov %rsp,%rbp +-------------------+ | Rücksprungadresse | ... +-------------------+ | alter rbp | <- rsp, rbp leave +-------------------+ ret | ? ? ? | +-------------------+ . . . +-------------------+ | ? ? ? | +-------------------+ 33 Der Aufrufrahmen V Was macht dieser Rahmen, den wir die ganze Zeit mitführen? push %rbp . . . mov %rsp,%rbp +-------------------+ | Rücksprungadresse | > ... +-------------------+ | alter rbp | <- rbp leave +-------------------+ ret | ? ? ? | +-------------------+ . . . +-------------------+ | ? ? ? | <- rsp +-------------------+ 34 Der Aufrufrahmen VI Was macht dieser Rahmen, den wir die ganze Zeit mitführen? push %rbp . . . mov %rsp,%rbp +-------------------+ | Rücksprungadresse | > ... +-------------------+ | alter rbp | <- rbp leave +-------------------+ ret | ? ? ? | +-------------------+ . . . leave +-------------------+ wie mov %rbp,%rsp | ? ? ? | <- rsp pop %rbp +-------------------+ 35 Der Aufrufrahmen VII Was macht dieser Rahmen, den wir die ganze Zeit mitführen? push %rbp . . . mov %rsp,%rbp +-------------------+ | Rücksprungadresse | ... +-------------------+ | alter rbp | <- rbp, rsp leave +-------------------+ ret | ? ? ? | +-------------------+ . . . leave +-------------------+ wie > mov %rbp,%rsp | ? ? ? | pop %rbp +-------------------+ 36 Der Aufrufrahmen VIII Was macht dieser Rahmen, den wir die ganze Zeit mitführen? push %rbp . . . <- rbp mov %rsp,%rbp +-------------------+ | Rücksprungadresse | <- rsp ... +-------------------+ | alter rbp | leave +-------------------+ ret | ? ? ? | +-------------------+ . . . leave +-------------------+ wie mov %rbp,%rsp | ? ? ? | > pop %rbp +-------------------+ 37 Selber Funktionen schreiben - Selbst geschriebene Funktionen sehen genauso aus wie main: my_function: push %rbp mov %rsp,%rbp ... leave ret - vor Verwendung zu sichernde Register: rbx, rbp, r12, r13, r14, r15 - rsp und rbp werden durch leave ; ret wiederhergestellt - der Aufrufrahmen kann weggelassen werden, dann aber Vorsicht! 38 Aufgabe 9 Die Fibonacci-Funktion ist rekursiv wie folgt definiert: fib(0) = 0 fib(1) = 1 fib(n) = fib(n - 1) + fib(n - 2) Schreibe ein Programm, dass die n-te Fibonacci-Zahl per Rekursion berechnet. Was passiert wenn n größer wird? Was passiert, wenn n riesig wird? Beispiel: $ ./program 1 1 $ ./program 10 55 $ ./program 20 6765 39 Aufgabe 10 Schreibe einen Filter, der Großbuchstaben in Kleinbuchstaben verwandelt. Benutze dazu eine selbstgeschrieben Funktion tolower, die einen Buchstaben umwandelt. Ferner benutze folgende Funktionen: getchar() Liefert Zeichen aus der Eingabe in eax. eax == -1 wenn Eingebaende erreicht. putchar(c) Schreibe Zeichen c (in rdi) in die Ausgabe. 40 Der Stapel als Variablenspeicher - Wir können den Stackpointer nach unten verschieben, um Platz auf dem Stapel zu allozieren. - dieser Platz wird durch leave automatisch freigegeben Beispiel: push %rbp # Aufrufrahmen ... mov %rsp,%rbp # ... etablieren sub $16,%rsp # 16 Byte auf dem Stack allozieren mov %rdi,-8(%rbp) # Argumente ... mov %rsi,-16(%rbp) # auf dem Stapel ablegen ... leave # Speicher freigeben ret 41 Aufgabe 11 Schreibe ein Programm, das ein Histogramm über die Häufigkeit der eingegegeben Buchstaben ermittelt. Die Eingabe sollte über die Standardeingabe erfolgen. Alloziere dazu ein Array von 256 * 4 Bytes auf dem Stack, in dem du für jedes Byte zählst, wie oft es vorgekommen ist. Beispiel: $ echo -n mississippi | ./program i: 4 m: 1 p: 2 s: 4 Hilfreiche Funktion: memset(buf, c, len) Setze alle Bytes in buf (in rdi) der Länge len (in rdx) auf c (in sil). 42 Binäre und hexadezimale Zahlen - Der Computer rechnet intern zur Basis 2. - Vier Binärstellen werden zu einer Hexadezimalstelle zusammengefasst - Alternativ drei Binärstellen zu einer Oktalzahl - Computer können sehr leicht mit individuellen Bits rechnen 43 Bitweise Operationen and a,b b = b & a (bitweises und) or a,b b = b | a (bitweises oder) xor a,b b = b ^ a (bitweises xor) not a a = ~a (bitweises nicht) shl a,b b = b << a (schieben nach links, a ist imm. oder cl) shr a,b b = b >> a (schieben nach rechts, a ist imm. oder cl) sar a,b b = b >> a (wie shl, aber Vorzeichen wird beachtet) 44 Das Carry Flag - das Carry-Flag speichert, wenn eine Operation einen Überlauf (z.B. bei Addition) oder einen Unterlauf (bei Subtraktion) erzeugt. - bei Schiebeoperationen wird das zuletzt rausgeschobene Bit in das Carry-Flag geschoben. adc a,b b = b + a + CF (Addition mit Überlauf) sbb a,b b = b - a - CF (Subtraktion mit Überlauf) stc CF = 1 clc CF = 0 cmc CF = 1 - CF 45 Aufgabe 12 Schreibe eine Routine, die eine Zahl in eine Hexadezimalzahl umwandelt. Schreibe dazu ein Programm, was diese Routine benutzt, um eine Zahl als Dezimalzahl auszugeben. Die Routine soll wie folgt aufgerufen werden: numtohex(num, buf) num (in rdi) ist die zu konvertierende Zahl. buf ist die Adresse eines Puffers mit Platz für 17 Zeichen (16 Stellen und 1 Byte Terminator). 46 Aufgabe 13 Schreibe ein Programm, was eine der folgenden Operationen umsetzt. Denke darüber nach, wie das Carry-Flag und Bit-Operationen dabei helfen könnten. - Zähle die Anzahl der 1-Bits einer 64-Bit-Zahl - Finde heraus, wie oft eine 64-Bit-Zahl durch 2 teilbar ist. - Finde heraus, wie viele führende Nullen eine 64-Bit Zahl hat - Invertiere die Reihenfolge der Bits einer 64-Bit-Zahl - Invertiere die Reihenfolge der Bytes einer 16-, 32-, und 64-Bit-Zahl 47 weiter nützliche Instruktionen lea a,b Wie mov a,b, aber statt a wird die Adresse von a nach b geschrieben. a muss Speicheroperand sein. inc a Wie add $1,a, aber das Carry-Flag wird nicht verändert. dec a Wie sub $1,a, aber das Carry-Flag wird nicht verändert. movz a,b Wie mov a,b, aber a hat kleineren Typ als b und wird mit Nullen aufgefüllt. movs Wie movz a,b, aber es wird mit dem Vorzeichen aufgefüllt.