Assembler

... ist Maschinensprache. Der Prozessor liest die Befehle direkt vom Speicher und verarbeitet diese. Von der Hardware werden sie zwar meist in Mikrobefehle zerlegt, jedoch ist Assembler die direkteste Kommunikationsmöglichkeit mit dem Prozessor.
Je nach CPU Typ gibt es verschiedene Assembler Befehlssätze. Ich werde hier auf den MIPS Prozessor eingehen, ein Prozessor mit reduziertem Befehlssatz, der Operationen nur zwischen Registern durchführt; Werte müssen also explizit aus dem Speicher in ein Register geladen werden. Register kann man sich als kleine Speicherplätze vorstellen, auf die sehr schneller Zugriff möglich ist. Unser Prozessor habe 31 Register, von denen einige besondere Funktionen haben. Register 0 ist z.B. konstant Null. Wozu soll dies gut sein? Da der Prozessor einen reduzierten Befehlssatz hat, gibt es keinen Befehl um Inhalte von einem Register ins Andere zu kopieren. In dem Fall addiert man einfach zum Quellregister den Wert von Register 0!
Auf weitere Sonderregister werden wir später stoßen.

Die hier vorgestellten Programm können z.B. auf dem Simulator "Spim" ausgeführt werden.
Ein Assemblerprogramm wird heute als normale Textdatei geschrieben. Die Befehle sind meist ein bis fünf Zeichen lang und werden entweder von Registern, Speicheradressen, oder elementaren Werten (immediate) gefolgt.
Programmlistings beginnen zunächst mit Optionen für den Compiler (gelb), auf die ich hier nicht näher eingehe, gefolgt von einem Datenteil und dem Codeteil (alles nach "#" sind Kommentare):

.option pic2	# Optionen
.set noreorder	# Keine Optimierung
.data	# Datenteil beginnt hier
.align 4	# Ausgerichteter Speicherzugriff
hallow: .asciiz "Hallo Welt!\n"	# Ascii, nullterminierte Zeichenkette
.text	# Codeteil beginnt
.align 4	# Ausgerichteter Speicherzugriff
main: li $2, 4	# Systemaufruf 4 = print_str
la $4, hallow	# Adresse der Zeichenkette im Speicher
syscall	# Systemaufruf
li $2, 10	# Systemaufruf 10 = beenden
syscall	# Systemaufruf

Diese Programm macht nichts weiter als "Hallo Welt!" und einen Zeilenumbruch auszugeben. Im Datenteil sorgen wir dafür, dass unser Speicher beim Programmstart den String enthält. Bei der Ausführung wird dann in das Register 2 der Wert 4 geschrieben (li = load immediate). Dieses Register beinhaltet einen Wert für den Systemaufruf, 4 steht für Zeichenkette ausgeben. Nun muss man natürlich wissen, welche Zeichenkette. Dafür laden wir in das Register 4, welches für diesen Zweck vorgesehen ist, die Adresse unserer Zeichenkette im Speicher. Der Assembler ersetzt später das Label "hallow" durch die tatsächliche Position im Speicher. Syscall führt den Befehl nun aus und gibt so lange die entsprechenden Zeichen aus, bis er auf ein Ascii null stößt. Schließlich wird der Programmlauf beendet, durch den Systemaufruf 10.
Wie sicher schon bemerkt wurde, steht das $-Zeichen für Register. Bei immediate Befehlen steht der wirkliche Wert im Befehl drin, wie z.B. die 4 und die 10 im obigen Beispiel. Nun ein neues Beispiel, die Opionenzeilen lasse ich weg:

.text	# Codeteil
main: addi $4, $0, 123	# Beispielwert in Register 4 (durch Addieren von null)
li $5, 30	# Beispielwert in Register 5 (anders als hier drüber)
sub $6, $4, $5	# Im Register 6 steht Wert von Register 4 - Register 5
addi $6, $6, 7	# Zum Register 6 7 addieren
li $2, 10	# Systemaufruf 10 = beenden
syscall	# Systemaufruf

Dies waren nun einige arithmetische Operationen. Wer sich die Kommentare zum Programm anschaut oder im debugger durchgeht wird sehen, dass am Ende in Register 6 der Wert 100 (oder Hexadezimal 64) steht. Bitweise Logische Operationen wie or, and lassen sich analog durchführen. Multiplizieren und dividieren geht mit mult und div. Diese Befehle brauchen zwei Operandenregister, das Ergebnis wird nämlich immer in die Sonderregister $hi und $lo gespeichert. Grund ist, dass beim Multiplizieren zweier 32 Bit Zahlen das Ergebnis über 32 Bit hinaus gehen kann. Die höherwertigen Bits stehen deshalb in $hi, die niederwertigen in $lo. Beim Dividieren steht der Divisionsrest in $lo und das ganzzalige Ergebnis in $hi. Mit mfhi $r bzw. mflo $r kann der Wert dieser Register ausgelesen werden.
Wichtige Kontrollsturkturen sind natürlich Sprunganweisungen. Mit jal label (jump and link) springen wir zum mit label bezeichneten Punkt im Programm (z.b. ein Unterprogramm). Jump and link merkt sich die Adresse von der man weggesprungen ist im Register $31. Wir können mit dem Befehl jr $31 (jump return) an die Stelle im Programm zurück spingen, deren Adresse im Register 31 steht (das Programm liegt ja auch nur im Speicher und jede Zeile hat demnach auch eine Speicheradresse). j adresse ist ein unbedingter Sprung, der einfach zur absoluten Adresse springt. Wichtig sind bedingte Sprünge. beq $1, $0, loop sprint zur Marke loop, falls das Register 1 den gleichen Wert des Registers 0 hat. bne $1, $0, loop springt bei ungleichheit. Ähnlich gibt es z.B. bgtz $r, label welches springt, sofern das Register einen Wert größer 0 hat.
Wichtig beim Springen: Der MIPS Prozeassor hat eine Pipeline, das heißt Befehle werden teilweise parallel ausgeführt. Dazu ist es nötig, bei Sprungbefehlen nach dem Sprungbefehl immer ein nop (no operation) einzufügen, da sonst der dahinterstehende Befehl ausgeführt wird, obwohl man eigentlich wegspringen sollte.

Wie greift man auf den Speicher zu? Dies geht mittels lw (load word) und sw (store word). Das Wort ist dabei die Menge an Daten, die geladen/geschrieben werden soll. Ein Wort sind auf unserem System 4 Byte (32 Bit). Wie geht das konkret? Es gibt verschiedene Adressierungsarten. Am wichtigsten für uns ist im Moment Registerindirekt mit Displacement, das heißt, die Speicheradresse des Inhaltes, den wir laden möchten steht in einem Register (das Register zeigt auf die Speicherstelle) und wir haben die Möglichkeit diesen Zeiger noch etwas zu verschieben.
lw $4, 8($10) lädt in das Register 4 das Wort, welches an der Speicheradresse, die den Wert von Register 10, zuzüglich 8 Byte hat. Hierbei ist es wichtig zu wissen, dass die Speicherzugriffe ausgereichtet sein müssen; man kann also nicht irgendwo mitten im Speicher lesen, sondern muss immer ganze Wörter lesen, die Speicheradresse muss bei einer Wortbreite von 4 Byte also immer durch 4 teilbar sein.

Wenn man nun versucht einen Algorithmus in Assembler zu implementieren stößt man schnell auf Probleme. So zum Beispiel, wie man Rekursion umsetzt. Nun, wir machen das genauso, wie es die höheren Programmiersprachen intern machen. Jeder Rekursionsaufruf muss einen Block mit den zugehörigen lokalen Variablen im Speicher erzeugen. Und zwar organisiert als Stapel (Stack).

Wir wollen dies demontrieren anhand eines Programmes, welches das x-te Glied der Fibonacci Folge berechnet. Über diese Folge, und dem goldenen Schnitt, dem Grenzwert des Quotienten zweier Folgenglieder, könnte man einen eigenen Text schreiben, nun aber nur soviel, dass die Folge sich ergibt durch die Summe der zwei vorigen Glieder, beginnend mit 1, 1 also: 1, 1, 2, 3, 5, 8, 13, ...
Ein normales rekursives Programm würde ungefähr so aussehen:


Funktion Fibonacci(x) {
  if (x < 2) {
    return 1;
  } else {
    return Fibonacci(x-1) + Fibonacci(x-2);
  }
}

Wir lösen das in Assembler, indem wir mit jedem Rekursionsaufruf uns im Speicher die aktuellen Werte (also unsere Übergabevariable x und die Adresse von der wir in die neue Rekursion gesprungen sind) sichern und den Zeiger auf dem Speicher um die entsprechende Zahl verschieben. Diese Zeiger heißt Stackpointer und man kann direkt mit $sp auf das Register zugreifen. Dies habe ich als "Unterprogramme" pop und push implementiert, zu denen wir mit jal springen. Pop löscht den obersten Wert aus dem Stack und setzt ihn ins Register $4. Push speichert den Wert aus Register $4 oben auf dem Stack. Die $11-te Fibonacci Zahl wird nach Ende schließlich in Register $12 stehen.

.option pic2
.set    noreorder
.text
.align  4
main:
#hier sei das umgebende Programm, welches dann zum Label Fibonacci springt und den Parameter in Register $11 übergibt.
#
fibonacci:
#eigentlicher Beginn unserer Funktion
slti  $6, $11, 2    # wenn Übergabewert x >= 2
beq   $6, $0, rek   #  gehe in neue Rekursionsstufe
nop
add  $12, $12, $11  # Rekursion ist zu Ende, Ergebnisregister um x (=1 oder 0) erhöhen
jr    $31           # Ursprüngliche Rücksprungadresse von jal
nop

rek:                # else: neue Rekursionsstufe
add   $4, $31, $0   # Speichere Rücksprungadresse
jal   push          #  auf Stack
nop
add   $4, $11, $0   # Parameter x auf Stack
jal   push
nop
subu  $11,  $11, 2  # funktion rekursiv mit x-2
jal   fibonacci     #  aufrufen
nop
jal   pop           # Ursprüngl. x wieder holen
nop
add   $11, $4, $0
subu  $11, $11, 1   # funktion rekursiv mit x-1
jal   fibonacci     #  aufrufen
nop
jal pop             # Stack der aktuellen Stufe löschen
nop
jr $4               # und zurück woher man kam
nop

pop:                # Unterprogramm
lw $4, 0($sp)       #  speichert $4 in Stack
addi $sp, $sp, 4    #  Stackpointer um 4 Bytes hochschieben
jr $31              #  zurück woher man kam

push:               # Unterprogramm
addi $sp, $sp, -4   #  4 Bytes werden frei
sw $4, 0($sp)       #  Wert aus Stack in $4
jr $31              #  zurück woher man kam

Das ist nun etwas schwerer zu verstehen gebe ich zu. Vielleicht einfach mit einem Debugger wie Spim Schritt für Schritt durchgehen falls es nicht klar ist.

Ja, so hat jeder Prozessor seinen Befehlssatz und jedes Programm, dass Ihr gerade ausführt beim Lesen dieser Zeilen besteht aus solchen Befehlen, nur dass diese bei Intel kompatiblen Prozessoren etwas anders aussehen z.b. so (hier sind Register z.B. %eax und Immediates mit $):

retn 10
push %ebp
mov $32, %eax
add %ebx, %eax
mov $23, %ebx
sub %ebx, %eax
ret