TI 2 - Tutorium bei Dimitri Schachmann

• Speicher Hierarchie
• Cache
  • Cache Hit
  • Cache Miss
• Zugriffe
  • Einzelzugriffe
  • Blockzugriffe
  • Seitenzugriffe
• Seite/Page
• litte endian
• big endian

• Jump Prediction
• Predicated Instructions

• sudo apt-get install libgtk2.0-dev
• programm mit Bild als Argument starten
• http://en.wikibooks.org/wiki/X86\_Assembly/SSE

• Shell Kurs
• am Freitag den 22 und 29 Juni, jeweils 13 - 14.30 Uhr.
• Ankündigung im Verteiler

• Fragen zu Brainfuck?
• vor call register sichern

• Pipelining
• Hazards
• Branch/Jump prediction
• sse

• IEEE Gleichkommazahlen

  a	478.3801	0	10000111	1101 1110 0110 0001 0100 111
  b	-0.4250525	1	01111101	1011 0011 0100 0000 1111 011

  Das Ergebnis nach IEEE Addition.

  0

  10000111

  1101 1101 1111 0100 0111 111

  477.95505

• Bei den IEEE Gleitkomma Berechnungen am ende die Dartstellung im Register angeben.

• 32bit register wären geschickt gewesen.

• Brainfuck

• Pipelining
  • Die verschiedenen Arten von hazards

• Viele sollten sich nochmal anschauen wie das Rechnen mit den verschiedenen Zahlendarstellungen funktioniert.

• IEEE 754 Addition
  • Sub
• Fehler in der dritten Aufgabe?
• Bubble Sort
  • was wird der Funktion übergeben?
  • Größe des Arrays?
  • Adressierung bei NASM hier
  • array(7) nach RAX kopieren
    • ecx ist array index
    • mov rax, [rdi-ecx*4]

• Pipelining
  • Die verschiedenen Arten von hazards
• realtive Adressierung

• IEEE Beispiele
  • Von IEEE Gleitkommazahl nach Dezimalzahl
  • Von Dezimalzahl nach IEEE Gleitkommazahl
  • Addition von zwei Gleitkommazahlen

• 4.
• 5.

• Fragen?

• Klausur voraussichtlich am 13.07.2012 16-18 Uhr Hörsaal in der Arnimallee 22
• Abgaberichtlinien:
  • Per Mail den Quellcode als Quellcodedateien!!!! Also .asm für Assembler und .c für C-Code. Wenn Erläuterungen dabei sein sollen, dann entweder als Kommetar in den Quellcode, oder als pdf. Bitte keine .doc oder .odt Dateien!
  • Bitte keine losen Blätter und getackert. Keine Klarsichtfolien bitte.
  • bitte den Code ausdrucken und nicht HANDSCHRIFTLICH ABSCHREIBEN. Srsly! wtf?!?!
  • jeder braucht einen Übungspartner

• Gleitkommazahlen allgemein
  • Zahlenbereich
  • Zahlenverteilung
  • max real
    • ist die größte darstellbare normalisierte positive Zahl
  • min real
    • ist die kleinste darstellbare normalisierte positive Zahl
  • small real
    • ist die kleinste Zahl, die man zu 1 addieren kann, um einen von 1 verschiedenen Wert zu erhalten.
• IEEE-P 754 Gleitkommazahlen
  • Vorzeichen 1 bit
  • Charakteristik 8 bit
  • Mantisse 23 bit
  • Das erste Bit der Mantisse wird implizit zu 1 angenommen, wenn die Charakteristik nicht nur Nullen enthält.
  • Normalisierung: das erste Bit der Mantisse (die implizite 1) steht vor dem Komma.
  • Ist die Charakteristik gleich 0, entspricht dies dem gleichen Exponenten wie die Charakteristik 1.
  • Das erste Bit der Mantisse wird aber dann explizit dargestellt
  • Sind alle Bits der Charakteristik gleich 1, signalisiert dies eine Ausnahmesituation.
• Runden von Gleitkommazahlen
  • round to even ist das übliche.

• Befehlsliste
• div
• x = n*(n+1)/2
• shr, shl
• loop

• ALU (Arithmetisch-logische Einheit)
• Carry-ripple Addierer
• Carry-lookahead Addierer

• Wir verwenden die Intel Syntax für den Assembly code.
• KEINE LOSEN BLÄTTER ABGEBEN.
• Abgabe des Assembly Code und des C Codes. (keine Binärdateien!!!)
• Das 3. Übungsblatt kommt hoffentlich auch bald raus.
• EMACS

• Wiederholung
  • stack pointer, base pointer
  • paramter übergabe
  • rückgabewert
  • sichern
• .bss
  • ermöglicht es "Variablen" zu definieren. Achtung: erst verwenden, wenn keine Register mehr zu verfügung stehen, da *viel* langsammer als Register.
• Schleifen

• Negative Ganzzahlen
  • Allgemein:
    • führende 1 markiert, dass die Zahl negativ ist.
      • außer bei der Charakteristik Dartstellung
  • Charakteristik
  • Einerkomplement
  • Zweierkomplement
    • Dazu bitte externe Quellen (z.B. Wikipedia nachlesen).
• Gleitkommazahlen
  • generisch
  • IEEE
• Zu Beachten
  • Overflow
  • Underflow

• Hat noch jemand Probleme mit dem Blackboard?
• Wer immernoch nicht ins Blackboard kommt, kann den 2 Übungszettel hier runterladen.
• Ab sofort das Tutorium um 08:30 nach Möglichkeit im Raum 005

• Speicher
• Prozess

• (Call) Stack und Heap
• Funktion
• Funktionsaufruf
• Stackframe
• calling convention
• Übergabe von Argumenten
  • über die Register
  • über den Stack
• Sichern der Register

• nasm fürs Assemblieren.
• gcc fürs kompilieren eines Frameworks und linken mit der assemblierten binary.
• gdb fürs debuggen, also Untersuchung von dem was wirklich Sache ist zu Laufzeit.
• Für Windoof:
  • ollydbg
  • mingw

• Syntax
  • Befehle
  • Operanden
• Ein Beispiel (Siehe ganz weit unten)
• Die Wichtigsten Befehle
  • arithmetik
  • unbedingter Sprung
  • bedingte Sprünge
    • CMP rax, 42
    • JZ label
• Realisierung von Schleifen
• Debugging
• Allgemeine Tips fürs Programmieren:
  • divide and conquer: Aufteilen der Aufgabe in kleine Unterprobleme, schließlich die kleinen Lösungen zu einer großen zusammenfügen.
  • Bei Unwissen nicht raten: Fragen! Nerds die ihr kennt, oder das Forum, oder Google.
  • Kann am Anfang hilfreich sein: Den Algorithmus erst in Pseudocode (Python z.B. ;) aufschreiben und dann nach Assembly übersetzen.

• Zahlensysteme:
  • Was ist der Unterschied zwischen den Zahlensystemen?
  • Wieso verwendet man verschiedene Zahlensysteme?
  • Welches Zahlensystem verwendet ein Computer und welche Folgen hat das?

• Ich
  
  • Dimitri Schachmann
    • Dima
  • d.schachmann XXXNOSPAMXXX @ fu-berlin . de
  • page.mi.fu-berlin.de/schachma/ti2.html

• Anwesenheit
  
  • Anwesenheitspflicht inkl. Anwesenheitsliste
    • Mindestens n-2 mal anwesend sein
  • Das Tutorium um 8 Uhr früh geht von 8:30 bis 10:00

• Übungszettel
  
  • Übungszettel kommen wöchtenlich(!) raus und man hat 14(!) Tage Zeit für die Bearbeitung.
  • Es gibt immer eine bewertete Aufgabe
  • Abgabe in Zweiergruppen
  • Der erste Übungszettel ist am 27.04. abzugeben
  • Vor der Vorlesung abgeben
  • Abgabe auf Papier UND per E-Mail
  • E-Mail Betreff der Form: [TI2] Übung Nr. 7 Max Mustermann, Frieda Fröhlich
  • Abgabe in der Takustr. 9 im ersten Stock in meinem Tutorenfach
  • n-2 Zettel bestehen
  • Die anderen Aufgaben auch machen, denn sie sind wichtig fürs Tutorium!
  • Vorrechnen: Jeder muss mindestens ein mal vorrechnen. Vorrechenvorschläge an mich per E-Mail.

• Note
  
  • 100% Klausur

• Fragen?
  
  • Jetzt?
  • per e-mail an mich, aber viel besser:
  • foren.spline.de

• Kennenlernen
  

• Wir nutzen den nasm Assembler auf 64 bit.
• Persönlich von mir empfohlen: Linux
• Remote arbeiten auf den Unirechnern über SSH möglich mit Putty:
  • Adresse: andorra.imp.fu-berlin.de
• Zum testen von nasm ladet euch hier einen kleinen Test runter. Das probiert ihr in der Konsole wie folgt aus. Wenn die Ausgabe auch so änhlich ausschaut, dann ist alles in Butter. (Sytem: Linux 64 bit)

dima@dima-think:~/ti/demo/test$ unzip nasm_test.zip
Archive:  nasm_test.zip
  inflating: foo.asm
  inflating: Makefile
  inflating: hello.asm
  inflating: bar.c
dima@dima-think:~/ti/demo/test$ make -Bs all
dima@dima-think:~/ti/demo/test$ ./foo
Hello, world!
dima@dima-think:~/ti/demo/test$ ./hello
Test Here!
Hello from Assembly!

• Wer Windows nutzt: wubi! Installiert Ubuntu als Programm unter Windows
• Besser: Linux richtig installieren
• Im Notfall: bei sich für 32 Bit programmieren, dann vor der Abgabe noch auf den Institutsrechnern für 64 bit anpassen.
• Auch möglich: 64 bit Linux in einer virtuellen Maschine
• Für persönliche Hilfe bei Linuxfragen (Installation z.B.) zu Spline gehen

• Vorwissen aus TI I
  • wenig nötig
• Abweichung vom Vorlesungs- und Tutoriumsstoff
  • Ja, aber auch so gewollt.

• Daten
• Speicher
  • Hauptspeicher == Arbeitsspeicher
  • RAM
• Visuelle Darstellung von Speicher
  • Speicher als Band
  • Speicher als gefaltetes Band
• ALLES IST ZAHL
  • Zahlenwerte
  • Buchstaben
  • Speicheradressen
  • Programmbefehle
• Speicherbereiche:
  • Stack
  • Text
  • Heap
  • mehr dazu
• Speicheradressierung
• Register
• Programm
• Prozess

Für dieses Beispiel benötigen wir 2 Quelldateien. Eine für den Assembler Code und eine für das C Programm. Wir wollen sie hier foo.asm und bar.c nennen.

bar.c füllen wir nun mit dem folgenden Inhalt:

 1:  #include<stdio.h>
 2:  
 3:  int foo(int, int, int);
 4:  
 5:  int main()
 6:  {
 7:    int i = foo(42,1337,2047);
 8:    printf("i hat den Wert:%d",i);
 9:    return 0;
10:  }

Hier passiert folgendes:

• Zeile 3: Hier deklarierern wir eine Funktion namens foo, die drei Integer als Parameter erwartet und ein Integer als Rückgabewert hat. Deklarieren bedeutet, dass wir die Existenz einer solchen Funktion ankündigen, die Implementierung muss noch Folgen und wird in unserem Fall in Assebly geschehen.
• Zeile 5: Die main Funktion, ist bei jedem C-Programm der Einstiegspunkt. Hier beginnt später die Ausführung.
• Zeile 7: In dieser Zeile wird eine Integer Variable i deklariert und dann die Funktion foo mit den Argumenten 42,1337 und 2047 aufgerufen. Das Ergebnis dieses Aufrufs wird mit dem Zuweisungsoperator = in die Variable i geschrieben.
• Zeile 8: Hier wird der Wert von i auf der Konsole ausgegeben.
• Zeile 9: Verlassen der Funktion main und damit des ganzen Programms.

Damit ist das Framework auch schon fertig. Es bleibt "nur" noch die eigentliche foo Funktion zu implementieren.

Als erstes wollen wir eine minimale Assembly Funktion schreiben, die zwar nicht das tut was wir von ihr wollen, aber zumindest Syntaktisch korrekt ist, sodass wir das ganze zumindest ausführen können. Schreiben in foo.asm den folgenden Inhalt:

1:  section .text
2:  global foo
3:  foo:
4:          ret

Kurz gesagt, steht da folgendes:

• Zeile 1: Das drückt aus, dass jetzt Quellcode (text) kommt. (section .data würde z.B. einen Datenbereich ankündigen.)
• Zeilen 2-3: Das kündigt an, dass jetzt der Quellcode der Funktion foo folgt.
• Zeile 3: Das ist der Quellcode unserer Funktion. Noch macht die Funktion nichts anderes, als sofort ret(urn) aufzurufen und sich damit zu beenden.

Um das auszuprobieren, wechseln wir in der Konsole in das Verzeichnis, wo unsere Quelldateien liegen und machen folgendes:

1:  dima@dima-think:~/ti2/demo2$ nasm -f elf64 foo.asm
2:  dima@dima-think:~/ti2/demo2$ gcc -o run foo.o bar.c
3:  dima@dima-think:~/ti2/demo2$ ./run
4:  i hat den Wert: 1684280424
5:  dima@dima-think:~/ti2/demo2$ ./run
6:  i hat den Wert: -10320792
7:  dima@dima-think:~/ti2/demo2$ ./run
8:  i hat den Wert: -1113918360

• Zeile 1: Mit nasm -f elf64 foo.asm assemblieren wir unsere Funktion. Dabei erzeugt nasm den entsprechenden Maschinencode. Wer gerade kein 64-bit System hat, nimm elf statt elf64. Dabei entsteht die Datei foo.o, die den Maschinencode enthält.
• Zeile 2: Mit gcc bar.c foo.o -o run kompilieren wir nun bar.c und linken (engl: to link) das mit mit der foo funktion in foo.o. -o run bewrikt, dass die resultierende ausführbare Datei run heißt. Kurz: es funktioniert so.
• Zeilen 3-8: Hier probieren wir unser Programm mit ./run aus. Wie man sieht kommt nicht das richtige Ergebnis raus. Es kommt sogar jedes mal etwas anderes raus. Das liegt daran, dass die aufrufende Funktion (hier: main) darauf vertraut, dass foo den Rückgabewert an eine bestimmte Stelle schreibt. Da unser foo das noch nicht macht, wird in i eben das reingeschrieben, was sich gerade zufällig an dieser speziellen Stelle befindet.
• Falls ihr ./run nicht ausführen könnt, weil z.B. folgendes seht

1:  dima@dima-think:~/ti2/demo2$ ./run
2:  bash: ./run: Permission denied

dann versucht vorher einmalig folgendes um dir Ausführberechtigung zu setzen.

1:  dima@dima-think:~/ti2/demo2$ chmod +x run

Jetzt wollen versuchen einen bestimmten Wert zurückzugeben, und nicht irgendeinen Müll. Rückgabewert auf Ebene das Maschinencodes, werden über das register rax (bei 32 bit eax) and die aufrufende Funktion übergeben. Wie man in Register schreibt, sieht man am folgenden Beispiel.

1:  section .text
2:  global foopp
3:  foo:
4:          mov rax, 23
5:          ret

Hier wird vor dem Verlassen der Funktion noch die Zahl 23 in das Register rax geschrieben (mov(e)). Hier sieht man auch, dass Operationen die etwas schreiben, in der von uns verwendeten Syntax, wie folgt aufgebaut sind:

• <OPERATION> <ZIEL>, <QUELLE>

Unsere Funktion verhält sich schon ein wenig besser, ist aber noch weit davon entfert das zu tun, was wir von ihr wollen.

Für unsere Berechnung benötigen wir die übergebenen Argumente der Funktion. In einem Handbuch steht folgendes auf Seite 20:

• If the class is INTEGER, the next available register of the sequence %rdi, %rsi, %rdx, %rcx, %r8 and %r9 is used.

Unsere drei Argumente liegen also in den Registern rdi, rsi, rdx. Zumindest hoffen wir das. Letztes Jahr haben wir in dieser Veranstaltung mit 32 bit gearbeitet und da musste man noch eine Anstrengung Unternehmen, damit das auf allen Systemen gleich ist. Bei 64 bit ist das angeblich einheitlich. Wir werden im verlauf des Kurses sehen, ob das wirklich so ist. Bei nur drei Argumenten sollte da aber nichts schief gehen. Die Frage ist nämlich, ab wieviel Argumenten werden die Werte nicht über die Register, sondern über den Calling Stack übergeben. Laut diesem Handbuch ab dem 7. Parameter. Prfobieren wir das aus, in dem wir den ersten Parameter (in rdi wieder ausgeben (also in rax schreiben).

• UPDATE: Laut der deutschen Wikipedia ist das tatsächlich so bei Linux und bei Macs. Bei Windows werden nur die ersten 4 Integer Werte über Register übergeben.

1:  section .text
2:  global foo
3:  foo:
4:          mov rax, rdi
5:          ret

Und tatsächlich:

1:  dima@dima-think:~/ti2/demo2$ nasm -f elf64 foo.asm
2:  dima@dima-think:~/ti2/demo2$ gcc bar.c foo.o -o run
3:  dima@dima-think:~/ti2/demo2$ ./run
4:  i hat den Wert: 42

Jetzt wissen wir, wie wir Werte zurückgeben können. Jetzt bleibt nur noch die Berechnung, die tatsächlich schon das einfachste ist. Wir erinnern uns kurz an die Syntax:

• <OPERATION> <ZIEL>, <QUELLE>

Und führen zwei neue Operationen ein:

• add a, b
  • bewirkt a = a + b
• sub a, b
  • bewirkt a = a - b

Dann ist der folgende Code schon selbsterklälrend:

1:  section .text
2:  global foo
3:  foo:
4:          mov rax, 0
5:          add rax, rdi
6:          add rax, rsi
7:          sub rax, rdx
8:          ret

Und tatsächlich:

1:  dima@dima-think:~/ti2/demo2$ nasm -f elf64 foo.asm
2:  dima@dima-think:~/ti2/demo2$ gcc bar.c foo.o -o run
3:  dima@dima-think:~/ti2/demo2$ ./run
4:  i hat den Wert: -668

Da wir die Funktion mit den Werten 42, 1337 und 2047 aufgerufen haben, und (42+1337)-2047=-668 gilt, funktioniert unsere Funktion wie gewünscht. :)

Das war ein sehr einfaches Beispiel. Bei etwas komplexeren Anwendungen, gibt es noch ein paar mehr Dinge zu beachten.

Um das Beispiel so knapp wie möglich zu halten, habe ich etwas wichtiges verschwiegen. Bei den meisten Funktionen auf Aussembly Ebene müssen noch gewisse Vorkehrungen getroffen werden, um gewisse Aufrufkonventionen einzuhalten. Eine Aufrufkonvention ist die schon besprochene Vereinbarung darüber, wo die Argumente für die Funktion liegen. Diese Konvention muss von der aufrufenden Funktion eingehalten werdefn. Die aufgerufene Funktion muss hingegen dafür sorgen, dass nach ihrem Ende die veränderten Register den selben Zustand haben, wie vor ihrem Aufruf. Insbesondere gilt das für den base pointer (auch frame pointer) (bei 64bit rbp). So sieht man typischerweise bei fast allen Funktionen, dass am Anfang der Wert des base pointers auf den Stack gelegt und mit dem neuen Wert des Stackpointers überschrieben wird. Am Ende wird der alte Wert des base pointers wieder vom Stack in das entsprechende Register geschrieben. Das würde bei unserem Beispiel wie folgt aussehen:

 1:  section .text
 2:  global foo
 3:  foo:
 4:          push rbp
 5:          mov  rbp, rsp
 6:          mov rax, 0
 7:          add rax, rdi
 8:          add rax, rsi
 9:          sub rax, rdx
10:          pop rbp
11:          ret

Wer den Sinn des ganzen noch nicht versteht, der sollte sich am besten das hier durchlesen, wo der base pointer frame pointer genannt wird.

• Befehlsliste
• nasm-Dokumentation
• Ein Tutorial. Achtung: Es ist für 32 bit ausgelegt, aber sooooo groß ist der Unterschied auch nun wieder nicht.

• Mit diesem Programm könnt ihr sehr einfach ein 64 bit Linux emulieren.
• Mit gdb könnt ihr zur Laufzeit eures Programms den Inhalt des Speichers und der Register untersuchen. Standartmäßig verwendet gdb die AT&T Syntax für Assembly, wo die Reihenfolge der Operanden, im Gegensatz zu der von uns verwendeten Intel Syntax, vertauscht ist. Das kann man aber ändern, wenn man in gdb folgendes Kommando ausführt:
  • set disassembly-flavor intel