Inhaltsverzeichnis

Assembler-Programmierung mit dem RISC Simulator

Assembler-Programmierung mit dem RISC Simulator

1. Hexadezimalsystem

Assembler ist eine etwas besser leserliche Form der Maschinensprache (Sprache, die die CPU 'versteht'). Mit Assembler hast du bereits im Little Man Computer Bekanntschaft gemacht.

Befehle in Maschinensprache werden im Binärsystem ausgedrückt. Selbst für relativ kleine Zahlen resultiert dies daher in ziemlich langen Ausdrücken. Deshalb schreibt man diese oft ins Hexadezimalsystem um, was folgende Vorteile hat:

viel kompakter
einfache Umrechnung Binärsystem ↔ Hexadezimalsystem (einfacher als z.B. ins Dezimalsystem)
Die Umrechnung Dezimalsystem ↔ Hexadezimalsystem erfolgt wie die Umrechnung Dezimalsystem → Binärsystem mit dem Restwertverfahren
Der Online-Umrechner gibt's wie gewohnt hier: https://zahlensysteme-rechner.de

Das Hexadezimalsystem ist das Zahlensystem mit:

Basis $16$
Nennwerten $0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F$
Typischerweise wird Präfix $0x$ vor Hexadezimalzahl geschrieben

Beispiele:

Umrechnung Hexadeimalsystem → Dezimalsystem $0xB3 = 11 \cdot 16^1 + 3 \cdot 16^0 = 179$
Umrechnung Hexadeimalsystem → Binärsystem $0xB3 = 11 \cdot 16^1 + 3 \cdot 16^0 = 1011 0011$
Umrechnung Binärsystem → Hexadezimalsystem $1100 1011 = 1100 \cdot 16^1 + 1011 \cdot 16^0 = (8+4) \cdot 16^1 + (8+2+1) \cdot 16^0 = C \cdot 16^1 + B \cdot 16^0 = 0xCB$

Aufgaben:

Stelle folgende Zahlen im Binärsystem dar und wandle die ins Dezimalsystem um:

0xFF
0x100
0x3A

Stelle folgende Zahlen im Hexadezimalsystem dar und wandle sie ins Dezimalsystem um:

1010 1010
0111 1101
1111 1110

Lösung

2. Arbeitsumgebung

Den ARM-Risc-Simulator von Peter Higginson findet man hier: https://peterhigginson.co.uk/RISC/ Eine kleine Hilfe und die ganze Versionsgeschichte findet man direkt mit Help

Das ist die Übersicht aller möglichen Befehle: https://www.peterhigginson.co.uk/RISC/instruction_set.pdf

Der Simulator läuft direkt im Browser und besteht aus drei Teilen:

Rot: Programmeditor
Blau: CPU, Logik, Busse
Grün: RAM
Dazu kommt noch die Steuerung über die Buttons links unten.

Aufgabe 1:

Stelle zunächst die RAM-Darstellung von Dezimal (wie unprofessionell!) auf Hexadezimal um. Das machst du in den Options.
In Select findest du mehrere Beispielprogramme. Wähle add aus. Das Programm wird im Editor angezeigt und gleichzeitig ab Adresse 000 in den Speicher geladen.
Lass das Programm mit Step schrittweise ablaufen und beobachte, welche Daten in welcher Reihenfolge fliessen.
Du kannst die Animation mit den beiden Pfeiltaste « und » bremsen oder beschleunigen. Mit def fast in den Options kannst du die Animation auch komplett unterdrücken.
Später kannst du das ganze Programm mit Run auf einmal laufen lassen.
Versuche, die beiden Zahlen nicht zu addieren, sondern zu multiplizieren.

Aufgabe 2:

Sieh dir das Beispielprogramm example an.

Aufgabe 3:

Schreibe ein Programm, dass die beiden Dezimalzahlen 48801 und 53214 addiert.
Lege das Ergebnis an den Speicheradressen 102 und 103 ab.

Lösung

        LDR R0,100
        LDR R1,101
        ADD R2,R1,R0
        ADC R3,R7
        STR R2,102
        STR R3,103
        DAT
        ...
        DAT
        DAT 48801
        DAT 53214

Aufgabe 4:

Schreibe ein Programm, dass die beiden Dezimalzahlen 48801 und 53214 multipliziert.
Lege das Ergebnis an den Speicheradressen 102 und 103 ab.
Verwende den Befehl MLX.
Beachte genau, was in den Registern passiert!

Lösung

        LDR R0,100
        LDR R1,101
        MLX R1,R0
        STR R1,102
        STR R2,103
        DAT
        ...
        DAT
        DAT 48801
        DAT 53214

3. Zahlen jonglieren

Unsere Simulator-CPU kann nur 16-Bit-Zahlen. Was war nochmals die grösste darstellbare unsigned Zahl? Wir können wir zwei 32-Bit-Zahlen addieren oder sogar multiplizieren?

Aufgabe 5:

Schreibe ein Programm, das die beiden Dezimalzahlen 2'596'896'414 und 3'123'455'219 addiert.
Lege das Ergebnis an den Speicheradressen 104, 105 und 106 ab.

Lösung

        LDR R0,100
        LDR R1,102
        ADD R1,R0
        STR R1,104
        LDR R0,101
        LDR R1,103
        ADC R1,R0
        STR R1,105
        ADC R2,R7
        STR R2,106
        DAT
        ...
        DAT
        DAT 0x7e9e
        DAT 0x9ac9
        DAT 0x24f3
        DAT 0xba2c

Aufgabe 6:

Schreibe ein Programm, dass die beiden Dezimalzahlen 2'596'896'414 und 3'123'455'219 multipliziert.
Lege das Ergebnis an den Speicheradressen 104-107 ab.

Tipps:
Zerlege die beiden Zahlen in je zwei Teile, nämlich ein oberes und ein unteres Word (1 Word = 2 Bytes): $$2'596'896'414 = \text{0x}\,\text{9AC9}\,\text{7E9E} = \text{0x}\,\text{9AC9} \cdot 2^{16} + \text{0x}\,\text{7E9E} \cdot 2^0$$ $$3'123'455'219 = \text{0x}\,\text{BA2C}\,\text{24F3} = \text{0x}\,\text{BA2C} \cdot 2^{16} + \text{0x}\,\text{24F3} \cdot 2^0$$ Nun kommt Binom $$\text{0x}\,\text{9AC9}\,\text{7E9E} \cdot \text{0x}\,\text{BA2C}\,\text{24F3} = \text{0x}\,\text{9AC9} \cdot \text{0x}\,\text{BA2C} \cdot 2^{32} + \text{0x}\,\text{9AC9} \cdot \text{0x}\,\text{24F3} \cdot 2^{16} + \text{0x}\,\text{BA2C} \cdot \text{0x}\,\text{7E9E} \cdot 2^{16} + \text{0x}\,\text{7E9E} \cdot \text{0x}\,\text{24F3} \cdot 2^0$$ Jetzt kann man die einzelnen Summanden einfach richtig im Speicher verteilen:

$$2^0$$	204
$$2^{16}$$	205
$$2^{32}$$	206
$$2^{48}$$	207

Aber Achtung! Es gibt immer wieder Überträge, die in die Additionen für die einzelnen Speicheradressen mit einfliessen müssen.

Lösung

E0:     LDR R0,100
        LDR R1,102
        MLX R1,R0
        STR R1,104
        STR R2,105
        ADC R3,R7
        STR R3,106
E16a:   LDR R1,103
        MLX R1,R0
        ADC R3,R7
        ADD R1,105
        LDR R4, 106
        ADC R2,R4
        ADC R3,R7
        STR R1,105
        STR R2,106
        STR R3,107
E16b:   LDR R0,101
        LDR R1, 102
        MLX R1,R0
        ADC R3,R7
        ADD R1,105
        LDR R4, 106
        ADC R2,R4
        ADC R3,R7
        STR R1,105
        STR R2,106
        STR R3,107
E32:    LDR R0,101
        LDR R1, 103
        MLX R1,R0
        ADC R3,R7
        ADD R1,106
        LDR R4, 107
        ADC R2,R4
        ADC R3,R7
        STR R1,106
        STR R2,107
        STR R3,108
        DAT
        ...
        DAT
        DAT 0x7e9e
        DAT 0x9ac9
        DAT 0x24f3
        DAT 0xba2c

4. Vergleiche, Sprünge, Schleifen

Aus fast allen Programmiersprachen gibt es Bedingungen, die entweder Verzweigungen (if…else…) oder Schleifen (for… oder while…) steuern. Damit ein Compiler oder Interpreter diese Anweisungen in Maschinensprache übersetzen kann, muss es das also auch dort geben.

Aufgabe 7:

Öffne in Select das Beispiel ascii.
Dieses Programm gibt in einer Schleife alle druckbaren Zeichen (32-127) der ASCII-Tabelle aus.
Lass das Programm mit Step schrittweise ablaufen und beobachte, wo genau sich die Schleife befindet.
Welche Zeile ist die Bedingung? Welche der Rücksprung? Wohin geht der Rücksprung?
Was genau macht das Programm, nachdem die Schleife verlassen wird?

Aufgabe 8:

a) Schreibe ein Programm, das einen Countdown 10,9,…1,0 ausgibt.

Lösung

        MOV R1,#10
        MOV R2,#1
LOOP:   OUT R1,4
        SUB R1,R2
        CMP R1,#0
        BGE LOOP
        HLT

b) Schreibe ein Programm, das Zahlen 1 bis 100 addiert und am Ende die Summe ausgibt.

Lösung

        MOV R1,#0
        MOV R2,#1
LOOP:   ADD R1,R2
        ADD R2,#1
        CMP R2,#100
        BLE LOOP
        OUT R1,4
        HLT

Aufgabe 9: Schreibe ein Programm, welches das Maximum zweier Zahlen bestimmt: Der Benutzer soll hintereinander aufgefordert werden, zwei Zahlen einzugeben. Von diesen wird die grössere bestimmt und ausgegeben.

Wenn man dieses Programm z.B. in Python schreibt, implementiert man dazu eine Verzweigung (if-el(se)if). In Assembler wird dies wie eine Schleife (z.B. in letzter Aufgabe) mit Sprüngen implementiert.

Lösung

        INP R0,2
        INP R1,2
        CMP R0,R1
        BLE LOWER
        OUT R0
        BRA DONE
LOWER   OUT R1
DONE    HLT

5. Speichertypen

Sobald ein Programm gestartet wird, erhält es vom Betriebssystem RAM zugewiesen. Dieses RAM ist in zwei Blöcke unterteilt, die für unterschiedliche Operationen eingesetzt werden: Die Heap und der Stack (Wikipedia). In unserem Simulator beginnt das Programm bei Adresse 0000 und der Stack bei Adresse 0400 (s. Register SP). Der Stack wird absteigend aufgefüllt und belegt so den unteren Teil im Main Memory. Alles dazwischen kann als Heap verwendet werden…

5.1 Heap

Bisher haben wir Daten jeweils an einer bestimmten Adresse im Speicher abgelegt. Bei dieser Methode muss man immer auch die Speicheradresse kennen, sonst sind die Daten nicht mehr auffindbar. Den Adressbereich im Speicher, der dafür zur Verfügung steht, nennt man die Heap. Auf der Heap werden einerseits Daten gespeichert, die über einen grossen Teil des Programm benötigt werden, und andrerseits alle Objekte, Arrays sowie Elemente, deren Grösse sich ändern kann. Da unterschiedliche Datentypen unterschiedliche Speichergrössen haben, wird die Heap sehr unübersichtlich, und die Verwaltung der Speicheradressen ist extrem wichtig und ziemlich aufwändig. Werden einzelne Speicherbereiche nicht mehr gebraucht, sollten sie freigegeben werden, und später sollten die so entstandenen Lücken durch sog. Defragmentierung wieder geschlossen werden.

5.2 Stack

Der Stack ist ein Speicher, der als Stapel angeordnet ist: Es kann immer nur auf das oberste Element zugegriffen werden, und beim Zugriff wird das oberste Element gewöhnlich auch gerade entfernt, sodass nun das zweioberste Element wieder gelesen werden kann. Somit müssen die Elemente, die auf dem Stack abgelegt sind, in exakt umgekehrter Reihenfolge wieder gelesen werden. Der Prozessor hat für den Stack spezielle Befehle, die schnell arbeiten und wenig Verwaltung erfordern: PSH (Push) und POP. Der Stack wird eingesetzt für

die Speicherung der Parameter bei Funktionsaufrufen
funktionslokale Variablen.

6. Funktionen

Funktionen sind Programmteile, die in genau gleicher Art immer wieder benötigt werden. Anstatt überall die Codezeilen erneut einzufügen, wird sie einmal geschrieben und von überall her aufgerufen.

Aufgabe 10:

Schreibe ein Programm, das
- zwei Zahlen einliest und auf dem Stack ablegt
- die Funktion 'Addition' aufruft
- das Ergebnis vom Stack holt und ausgibt.
Schreibe (weiter unten) eine Funktion 'ADDTN', die
- die beiden Zahlen vom Stack holt
- addiert
- und das Ergebnis wieder auf den Stack legt.

Lösung

        INP R0,2
        INP R1,2
        PSH R0
        PSH R1
        JMS ADDTN
        POP R0
        OUT R0,4
        HLT
ADDTN:  POP R1
        POP R0
        ADD R0,R1
        PSH R0
        RET

Aufgabe 11:

Erweitere das Programm aus Aufgabe 10, dass es
- noch eine dritte Zahl einliest
- mit der Funktion 'ADDTN' zur Summe der ersten beiden Zahlen addiert.
- das Ergebnis vom Stack holt und ausgibt.

Lösung

        INP R0,2
        INP R1,2
        PSH R0
        PSH R1
        JMS ADDTN
        POP R0
        INP R1,2
        PSH R0
        PSH R1
        JMS ADDTN
        POP R0
        OUT R0,4
        HLT
ADDTN:  POP R1
        POP R0
        ADD R0,R1
        PSH R0
        RET

Aufgabe 12:

Schreibe ein Programm, das
- eine (kleine!) Zahl einliest
- die Zahl an die Funktion 'FCLT' übergibt
- den Rückgabewert ausgibt.
Schreibe (weiter unten) eine Funktion 'FCLT', die die Fakultät der übergebenen Zahl berechnet und zurück gibt.

Lösung

Iterativ:
        INP R0,2
        PSH R0
        JMS FCLT
        POP R0
        OUT R0,4
        HLT
FCLT:   POP R0
        MOV R1,#1    //Zähler
        MOV R2,#1    //Produkt
LOOP:   MUL R2,R1
        ADD R1,#1
        CMP R1,R0
        BLE LOOP
        PSH R2
        RET



Rekursiv, aber mit Stack Underrun:
        INP R0,2
        PSH R1
        JMS FCLT
        POP R0
        OUT R0,4
        HLT
FCLT:   SUB R0,#1
        CMP R0,#1
        BLE DONE
        PSH R0
        JMS FCLT
        POP R1
        POP R0
        MUL R1,R0
        BRA END
DONE:   MOV R1,#1
END:    PSH R1
        RET


Rekursiv:
        INP R0,2
        PSH R0
        JMS FCLT
        POP R0
        OUT R0,5
        HLT
FCLT:   POP R0
        MOV R1,#1
LOOP:   CMP R0,#1
        BLE DONE
        MUL R1,R0
        SUB R0,#1
        BRA LOOP
DONE:   PSH R1
        RET

7. Rekursion

Beachte dazu den Artikel in Wikipedia, vor allem die Begriffserklärung und den Abschnitt 3. Die Fakultät kann man nicht nur wie in Aufgabe 12 iterativ, sondern auch rekursiv berechnen: Die Funktion Fakultät einer natürlichen Zahl $n \geq 1$ ist definiert als das Produkt der Zahlen 1 bis $n$: $$n! = 1\cdot 2 \cdot 3 \dotsm n$$ Das lässt sich auch als Zahlenfolge und somit rekursiv darstellen: $$(n+1)! = (n+1)\cdot n!$$ Das lässt sich auch genauso programmieren.

In C# könnte eine solche Methode Fakultät() etwa so aussehen:

    static long Fakultät(long Zahl)
    {
      long lRet = 1;
      if (Zahl > 1)
      {
        lRet = Zahl * Fakultät(Zahl - 1);
      }
      return lRet;
    }

Aufgabe 13:

Schreibe ein Programm, das
- eine (kleine!) Zahl einliest
- die Zahl an die Funktion 'FCLT' übergibt
- den Rückgabewert ausgibt.
Schreibe (weiter unten) eine Funktion 'FCLT', die die Fakultät der übergebenen Zahl berechnet und zurück gibt
- Die Berechnung soll rekursiv erfolgen, dh. FCLT ruft sich selber immer wieder auf.
- Dabei muss zwingend ein Abbruchkriterium programmiert werden!

Lösung

Iterativ:
        INP R0,2
	MOV R1,#1		//Zähler
        MOV R2,#1		//Produkt
LOOP:   MUL R2,R1
        ADD R1,#1
        CMP R1,R0
        BLE LOOP
        OUT R2,4
        HLT



Rekursiv, aber mit Stack Underrun:
        INP R0,2
        PSH R0
        JMS FCLT
        POP R0
        OUT R0,4
        HLT
FCLT:   SUB R0,#1
        CMP R0,#1
        BLE DONE
        PSH R0
        JMS FCLT
        POP R1
        POP R0
        MUL R1,R0
        BRA END
DONE:   MOV R1,#1
END:    PSH R1
        RET



Rekursiv: 
        INP R0,2
        JMS FCLT
        OUT R1,5
        HLT
FCLT:   PSH {R0,LR}
        SUB R0,#1
        CMP R0,#1
        BLT DONE
        JMS FCLT
        BRA BACK
DONE:   MOV R1,#1
BACK:   POP {R7,R0}
        MUL R1,R0
        BRA R7
        RET