====== Assembler-Programmierung mit dem RISC Simulator ======

===== - 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 [[https://www.matheretter.de/rechner/dezimalbinar|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$

<box 100%>
**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
<nodisp 1>
++++Lösung|
   * 0xFF = 1111 1111 = 255
   * 0x100 = 1 0000 0000 = 256
   * 0x3A = 0011 1010 = 58
   * 1010 1010 = 0xAA = 170
   * 0111 1101 = 0x7D = 125
   * 1111 1110 = 0xFE = 254
++++
</nodisp>
</box>

===== - Arbeitsumgebung =====

Den ARM-Risc-Simulator von Peter Higginson findet man hier:
[[https://peterhigginson.co.uk/RISC/|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|https://www.peterhigginson.co.uk/RISC/instruction_set.pdf]]

Der Simulator läuft direkt im Browser und besteht aus drei Teilen:
{{ :ef_informatik:arm-simulator.png?800 |}}
  * Rot: Programmeditor
  * Blau: CPU, Logik, Busse
  * Grün: RAM
  * Dazu kommt noch die Steuerung über die Buttons links unten.




<box 100%>
**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.
</box>

<box 100%>
**Aufgabe 2:**
  * Sieh dir das Beispielprogramm //example// an.
</box>



<box 100%>
**Aufgabe 3:**
  * Schreibe ein Programm, dass die beiden Dezimalzahlen 48801 und 53214 addiert.
  * Lege das Ergebnis an den Speicheradressen 102 und 103 ab.

<nodisp 1>
++++Lösung|
<code>
        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
</code>
++++
</nodisp>
</box>

<box 100%>
**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!

<nodisp 1>
++++Lösung|
<code>
        LDR R0,100
        LDR R1,101
        MLX R1,R0
        STR R1,102
        STR R2,103
        DAT
        ...
        DAT
        DAT 48801
        DAT 53214
</code>
++++
</nodisp>
</box>


===== - 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?

<box 100%>
**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.

<nodisp 1>
++++Lösung|
<code>
        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
</code>
++++
</nodisp>
</box>

<box 100%>
**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.


<nodisp 1>
++++Lösung|
<code>
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
</code>
++++
</nodisp>
</box>

===== - 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.
<box 100%>
**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?
</box>

<box 100%>
**Aufgabe 8:**

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

<nodisp 1>
++++Lösung|
<code>
        MOV R1,#10
        MOV R2,#1
LOOP:   OUT R1,4
        SUB R1,R2
        CMP R1,#0
        BGE LOOP
        HLT
</code>
++++
</nodisp>

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

<nodisp 1>
++++Lösung|
<code>
        MOV R1,#0
        MOV R2,#1
LOOP:   ADD R1,R2
        ADD R2,#1
        CMP R2,#100
        BLE LOOP
        OUT R1,4
        HLT
</code>
++++
</nodisp>
</box>

<box 100%>
**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.

<nodisp 1>
++++Lösung|
<code>
        INP R0,2
        INP R1,2
        CMP R0,R1
        BLE LOWER
        OUT R0
        BRA DONE
LOWER   OUT R1
DONE    HLT
</code>
++++
</nodisp>
</box>



===== - 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 ([[https://de.wikipedia.org/wiki/Dynamischer_Speicher|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...
==== - 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.
==== - 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. 

===== - 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.
<box 100%>
**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.

<nodisp 1>
++++Lösung|
<code>
        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
</code>
++++
</nodisp>
</box>
<box 100%>
**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.

<nodisp 1>
++++Lösung|
<code>
        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
</code>
++++
</nodisp>
</box>
<box 100%>
**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.

<nodisp 1>
++++Lösung|
<code>
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
</code>
++++
</nodisp>
</box>

===== - Rekursion =====
Beachte dazu den Artikel in [[https://de.wikipedia.org/wiki/Rekursion|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 (Mathematik)|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:
<code csharp>
    static long Fakultät(long Zahl)
    {
      long lRet = 1;
      if (Zahl > 1)
      {
        lRet = Zahl * Fakultät(Zahl - 1);
      }
      return lRet;
    }
</code>

<box 100%>
**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!

<nodisp 1>
++++Lösung|
<code>
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
</code>
++++
</nodisp>
</box>