In diesem Tutorial zeige ich Ihnen, wie Sie Ihre eigene virtuelle Maschine (VM) schreiben, auf der Assembler-Programme wie
2048 (mein Freund) oder
Roguelike (meine) ausgeführt werden können. Wenn Sie programmieren können, aber besser verstehen möchten, was im Computer geschieht und wie Programmiersprachen funktionieren, ist dieses Projekt genau das Richtige für Sie. Das Schreiben einer eigenen virtuellen Maschine mag etwas beängstigend erscheinen, aber ich verspreche, dass das Thema überraschend einfach und lehrreich ist.
Der endgültige Code besteht aus ungefähr 250 Zeilen in C. Es reicht aus, nur die Grundlagen von C oder C ++ zu kennen, z. B. die
binäre Arithmetik . Jedes Unix-System (einschließlich macOS) eignet sich zum Erstellen und Ausführen. Zum Konfigurieren der Konsoleneingabe und -anzeige werden mehrere Unix-APIs verwendet, die jedoch für den Hauptcode nicht unbedingt erforderlich sind. (Die Implementierung der Windows-Unterstützung wird geschätzt).
Hinweis: Diese VM ist ein kompetentes Programm . Das heißt, Sie lesen gerade den Quellcode! Jeder Code wird detailliert angezeigt und erklärt, sodass Sie sicher sein können, dass nichts fehlt. Der endgültige Code wird durch einen Plexus von Codeblöcken erstellt. Projekt-Repository hier .
1. Inhalt
- Inhaltsverzeichnis
- Einführung
- Architektur LC-3
- Assembler-Beispiele
- Programmausführung
- Umsetzung von Anweisungen
- Anleitung Spickzettel
- Verarbeitungsverfahren unterbrechen
- Spickzettel für Interrupt-Routinen
- Software herunterladen
- Speicherabgebildete Register
- Plattformfunktionen
- Start der virtuellen Maschine
- Alternative Methode in C ++
2. Einführung
Was ist eine virtuelle Maschine?
Eine virtuelle Maschine ist ein Programm, das sich wie ein Computer verhält. Es simuliert einen Prozessor mit mehreren anderen Hardwarekomponenten, sodass Sie rechnen, aus dem Speicher lesen und in den Speicher schreiben und mit Eingabe- / Ausgabegeräten wie einem echten physischen Computer interagieren können. Am wichtigsten ist, dass VM eine Maschinensprache versteht, die Sie zum Programmieren verwenden können.
Wie viel Hardware eine bestimmte VM simuliert, hängt von ihrem Zweck ab. Einige VMs reproduzieren das Verhalten eines bestimmten Computers. Die Leute haben kein NES mehr, aber wir können trotzdem Spiele für NES spielen, indem wir Hardware auf Software-Ebene simulieren. Diese Emulatoren müssen jedes
Detail und jede wichtige Hardwarekomponente des Originalgeräts
genau nachbilden .
Andere VMs entsprechen keinem bestimmten Computer, sondern teilweise mehreren gleichzeitig! Dies geschieht hauptsächlich, um die Softwareentwicklung zu erleichtern. Stellen Sie sich vor, Sie möchten ein Programm erstellen, das auf mehreren Computerarchitekturen ausgeführt wird. Die virtuelle Maschine bietet eine Standardplattform, die Portabilität bietet. Es ist nicht erforderlich, das Programm für jede Architektur in verschiedenen Assembler-Dialekten neu zu schreiben. Es reicht aus, nur eine kleine VM in jeder Sprache zu erstellen. Danach kann jedes Programm nur noch einmal in der Assemblersprache einer virtuellen Maschine geschrieben werden.
Hinweis: Der Compiler löst solche Probleme, indem er eine Standard -Hochsprache für verschiedene Prozessorarchitekturen kompiliert. VM erstellt eine Standard- CPU-Architektur , die auf verschiedenen Hardwaregeräten simuliert wird. Einer der Vorteile des Compilers besteht darin, dass es keinen Laufzeit-Overhead wie bei VM gibt. Obwohl Compiler gut funktionieren, ist das Schreiben eines neuen Compilers für mehrere Plattformen sehr schwierig, sodass VMs weiterhin nützlich sind. In der Realität werden auf verschiedenen Ebenen sowohl VM als auch Compiler zusammen verwendet.
Die Java Virtual Machine (JVM) ist ein sehr erfolgreiches Beispiel. Die JVM selbst ist relativ mittelgroß und klein genug, damit ein Programmierer sie verstehen kann. Auf diese Weise können Sie Code für Tausende verschiedener Geräte, einschließlich Telefone, schreiben. Nach der Implementierung der JVM auf dem neuen Gerät kann jedes geschriebene Java-, Kotlin- oder Clojure-Programm ohne Änderungen daran arbeiten. Die einzigen Kosten sind nur der Overhead für die VM selbst und die
weitere Abstraktion von der Maschinenebene. Dies ist normalerweise ein ziemlich guter Kompromiss.
Eine VM muss nicht groß oder allgegenwärtig sein, um ähnliche Vorteile zu erzielen. Ältere
Videospiele verwendeten häufig kleine VMs, um einfache Skriptsysteme zu erstellen.
VMs sind auch nützlich, um Programme sicher zu isolieren. Eine Anwendung ist die Speicherbereinigung.
Es gibt keine einfache Möglichkeit, die automatische Speicherbereinigung über C oder C ++
zu implementieren, da das Programm keinen eigenen Stapel oder keine eigenen Variablen sehen kann. Die VM befindet sich jedoch außerhalb des laufenden Programms und kann alle
Verweise auf Speicherzellen auf dem Stapel beobachten.
Ein weiteres Beispiel für dieses Verhalten sind
intelligente Verträge von
Ethereum . Intelligente Verträge sind kleine Programme, die von jedem Validierungsknoten in der Blockchain ausgeführt werden. Das heißt, die Bediener erlauben die Ausführung von Programmen, die von völlig Fremden geschrieben wurden, auf ihren Maschinen, ohne die Möglichkeit zu haben, sie im Voraus zu studieren. Um böswillige Aktionen zu verhindern, werden sie auf einer
VM ausgeführt , die keinen Zugriff auf das Dateisystem, das Netzwerk, die Festplatte usw. hat. Ethereum ist auch ein gutes Beispiel für Portabilität. Dank VM können Sie intelligente Verträge abschließen, ohne die Funktionen vieler Plattformen zu berücksichtigen.
3. Architektur LC-3
Unsere VM simuliert einen fiktiven Computer namens
LC-3 . Es ist beliebt für das Unterrichten von Studenten Assembler. Hier ein im
Vergleich zu x86 vereinfachter
Befehlssatz , der jedoch alle grundlegenden Konzepte beibehält, die in modernen CPUs verwendet werden.
Zunächst müssen Sie die erforderlichen Hardwarekomponenten simulieren. Versuchen Sie zu verstehen, was jede Komponente ist, aber machen Sie sich keine Sorgen, wenn Sie nicht sicher sind, wie sie in das Gesamtbild passt. Beginnen wir mit der Erstellung einer Datei in C. Jeder Code aus diesem Abschnitt sollte in den globalen Bereich dieser Datei eingefügt werden.
Die Erinnerung
Der LC-3 verfügt über 65.536 Speicherzellen (2
16 ), von denen jede einen 16-Bit-Wert enthält. Dies bedeutet, dass nur 128 KB gespeichert werden können - viel weniger als Sie es gewohnt sind! In unserem Programm ist dieser Speicher in einem einfachen Array gespeichert:
uint16_t memory[UINT16_MAX];
Register
Ein Register ist ein Steckplatz zum Speichern eines Wertes in der CPU. Register sind wie eine CPU-Workbench. Damit es mit einigen Daten arbeiten kann, muss es sich in einem der Register befinden. Da es jedoch nur wenige Register gibt, kann zu einem bestimmten Zeitpunkt nur eine minimale Datenmenge heruntergeladen werden. Programme umgehen dieses Problem, indem sie Werte aus dem Speicher in Register laden, Werte in andere Register berechnen und dann die Endergebnisse wieder im Speicher speichern.
Es gibt nur 10 Register im LC-3 mit jeweils 16 Bit. Die meisten von ihnen sind universell einsetzbar, aber einigen sind Rollen zugewiesen.
- 8 Allzweckregister (
R0-R7 ) - 1 Register des Teamzählers (
PC ) - 1 Bedingungsflagregister (
COND )
Allzweckregister können verwendet werden, um beliebige Softwareberechnungen durchzuführen. Der Befehlszähler ist eine vorzeichenlose Ganzzahl, die die Speicheradresse des nächsten auszuführenden Befehls ist. Bedingungsflags geben Auskunft über die vorherige Berechnung.
enum { R_R0 = 0, R_R1, R_R2, R_R3, R_R4, R_R5, R_R6, R_R7, R_PC, R_COND, R_COUNT };
Wie der Speicher werden wir die Register in einem Array speichern:
uint16_t reg[R_COUNT];
Befehlssatz
Eine Anweisung ist ein Befehl, der den Prozessor anweist, eine grundlegende Aufgabe auszuführen, z. B. zwei Zahlen hinzuzufügen. Der Befehl enthält einen
Opcode (Operationscode), der den Typ der auszuführenden Aufgabe angibt, sowie einen Satz von
Parametern , die Eingaben für die auszuführende Aufgabe liefern.
Jeder
Opcode stellt eine Aufgabe dar, die der Prozessor „ausführen“ kann. Es gibt 16 Opcodes in LC-3. Ein Computer kann nur die Reihenfolge dieser einfachen Anweisungen berechnen. Die Länge jedes Befehls beträgt 16 Bit, und die linken 4 Bit speichern den Operationscode. Der Rest wird zum Speichern von Parametern verwendet.
Später werden wir detailliert besprechen, was jede Anweisung tut. Definieren Sie momentan die folgenden Opcodes. Stellen Sie sicher, dass Sie diese Reihenfolge einhalten, um den richtigen Aufzählungswert zu erhalten:
enum { OP_BR = 0, OP_ADD, OP_LD, OP_ST, OP_JSR, OP_AND, OP_LDR, OP_STR, OP_RTI, OP_NOT, OP_LDI, OP_STI, OP_JMP, OP_RES, OP_LEA, OP_TRAP };
Hinweis: In der Intel x86-Architektur gibt es Hunderte von Anweisungen, während es in anderen Architekturen wie ARM und LC-3 nur sehr wenige gibt. Kleine Befehlssätze werden als RISC bezeichnet , während größere als CISC bezeichnet werden . Große Befehlssätze bieten in der Regel keine grundlegend neuen Funktionen, vereinfachen jedoch häufig das Schreiben von Assembler-Code . Ein CISC-Befehl kann mehrere RISC-Befehle ersetzen. CISC-Prozessoren sind jedoch komplexer und teurer in Design und Herstellung. Dieser und andere Kompromisse erlauben es nicht, das „optimale“ Design zu nennen .
Bedingungsflags
Das Register
R_COND speichert Bedingungsflags, die Informationen über die zuletzt durchgeführte Berechnung liefern. Auf diese Weise können Programme logische Bedingungen überprüfen, z. B.
if (x > 0) { ... } .
Jeder Prozessor verfügt über viele Statusflags, um verschiedene Situationen zu signalisieren. Der LC-3 verwendet nur drei Bedingungsflags, die das Vorzeichen der vorherigen Berechnung anzeigen.
enum { FL_POS = 1 << 0, FL_ZRO = 1 << 1, FL_NEG = 1 << 2, };
Hinweis: (Das Zeichen << wird als Linksverschiebungsoperator bezeichnet . (n << k) verschiebt die Bits n um k Stellen n links. Somit ist 1 << 2 gleich 4 Lesen Sie hier, wenn Sie mit dem Konzept nicht vertraut sind. Dies ist sehr wichtig.)
Wir haben die Konfiguration der Hardwarekomponenten unserer virtuellen Maschine abgeschlossen! Nach dem Hinzufügen von Standardeinschlüssen (siehe Link oben) sollte Ihre Datei ungefähr so aussehen:
{Includes, 12} {Registers, 3} {Opcodes, 3} {Condition Flags, 3}
Hier finden Sie Links zu nummerierten Abschnitten des Artikels, aus denen die entsprechenden Codefragmente stammen. Eine vollständige Auflistung finden Sie im Arbeitsprogramm - ca. trans.4. Assembler-Beispiele
Schauen wir uns nun das LC-3-Assembler-Programm an, um eine Vorstellung davon zu bekommen, was die virtuelle Maschine tatsächlich tut. Sie müssen nicht wissen, wie man in Assembler programmiert, oder hier alles verstehen. Versuchen Sie einfach, eine allgemeine Vorstellung davon zu bekommen, was los ist. Hier ist eine einfache "Hallo Welt":
.ORIG x3000 ; this is the address in memory where the program will be loaded LEA R0, HELLO_STR ; load the address of the HELLO_STR string into R0 PUTs ; output the string pointed to by R0 to the console HALT ; halt the program HELLO_STR .STRINGZ "Hello World!" ; store this string here in the program .END ; mark the end of the file
Wie in C führt das Programm eine Anweisung von oben nach unten aus. Im Gegensatz zu C gibt es jedoch keine verschachtelten Bereiche
{} oder Kontrollstrukturen wie
if oder
while . nur eine einfache Liste von Operatoren. Daher ist es viel einfacher durchzuführen.
Bitte beachten Sie, dass die Namen einiger Operatoren den zuvor definierten Opcodes entsprechen. Wir wissen, dass die Anweisungen 16 Bit sind, aber jede Zeile sieht aus, als hätte sie eine andere Anzahl von Zeichen. Wie ist eine solche Nichtübereinstimmung möglich?
Dies liegt daran, dass der Code, den wir lesen, in
Assemblersprache geschrieben ist - in Klartext, lesbar und beschreibbar. Ein Tool,
Assembler genannt , konvertiert jede Textzeile in eine 16-Bit-Binäranweisung, die eine virtuelle Maschine versteht. Diese binäre Form, bei der es sich im Wesentlichen um ein Array von 16-Bit-Anweisungen handelt, wird als
Maschinencode bezeichnet und tatsächlich von einer virtuellen Maschine ausgeführt.
Hinweis: Obwohl Compiler und Assembler bei der Entwicklung eine ähnliche Rolle spielen, sind sie nicht identisch. Der Assembler codiert einfach das, was der Programmierer im Text geschrieben hat, ersetzt die Zeichen durch ihre binäre Darstellung und packt sie in Anweisungen.
Die
.STRINGZ .ORIG und
.STRINGZ sehen aus wie Anweisungen, aber nein. Dies sind Assembler-Anweisungen, die einen Teil des Codes oder der Daten generieren. Beispielsweise fügt
.STRINGZ eine Zeichenfolge an einer bestimmten Stelle in ein Binärprogramm ein.
Schleifen und Bedingungen werden mit einer goto-ähnlichen Anweisung ausgeführt. Hier ist ein weiteres Beispiel, das bis 10 zählt.
AND R0, R0, 0 ; clear R0 LOOP ; label at the top of our loop ADD R0, R0, 1 ; add 1 to R0 and store back in R0 ADD R1, R0, -10 ; subtract 10 from R0 and store back in R1 BRn LOOP ; go back to LOOP if the result was negative ... ; R0 is now 10!
Hinweis: In diesem Lernprogramm muss die Montage nicht gelernt werden. Wenn Sie jedoch interessiert sind, können Sie mit den LC-3-Tools Ihre eigenen LC-3-Programme schreiben und erstellen.
5. Programmausführung
Noch einmal, die vorherigen Beispiele geben nur eine Vorstellung davon, was die VM tut. Um eine VM zu schreiben, benötigen Sie kein vollständiges Verständnis des Assemblers. Solange Sie das entsprechende Verfahren zum Lesen und Ausführen von Anweisungen befolgen, funktioniert
jedes LC-3-Programm unabhängig von seiner Komplexität ordnungsgemäß. Theoretisch kann eine VM sogar einen Browser oder ein Betriebssystem wie Linux ausführen!
Wenn Sie tief nachdenken, dann ist dies eine philosophisch wunderbare Idee. Die Programme selbst können beliebig komplexe Aktionen erzeugen, die wir nie erwartet haben und die wir möglicherweise nicht verstehen können. Gleichzeitig beschränkt sich ihre gesamte Funktionalität auf einfachen Code, den wir schreiben werden! Gleichzeitig wissen wir alles und nichts darüber, wie jedes Programm funktioniert. Turing erwähnte diese wunderbare Idee:
„Die Meinung, dass Maschinen einen Menschen mit nichts überraschen können, basiert meines Erachtens auf einem Fehler, für den Mathematiker und Philosophen besonders anfällig sind. Ich meine die Annahme, dass, da eine Tatsache Eigentum des Geistes geworden ist, sofort alle Konsequenzen dieser Tatsache Eigentum des Geistes werden. “ - Alan M. Turing
Vorgehensweise
Hier ist die genaue Beschreibung der zu schreibenden Prozedur:
- Laden Sie eine Anweisung aus dem Speicher unter der Adresse des
PC Registers herunter. PC Register erhöhen.- Zeigen Sie den Opcode an, um zu bestimmen, welche Art von Anweisung befolgt werden soll.
- Befolgen Sie die Anweisungen anhand der Parameter.
- Kehren Sie zu Schritt 1 zurück.
Sie können die Frage stellen: "Aber wenn die Schleife den Zähler ohne
if oder
while weiter erhöht, werden die Anweisungen dann nicht enden?" Die Antwort ist nein. Wie bereits erwähnt, ändern einige goto-ähnliche Anweisungen den Ausführungsfluss, indem sie über den
PC springen.
Wir beginnen die Untersuchung dieses Prozesses als Beispiel für den Hauptzyklus:
int main(int argc, const char* argv[]) { {Load Arguments, 12} {Setup, 12} enum { PC_START = 0x3000 }; reg[R_PC] = PC_START; int running = 1; while (running) { uint16_t instr = mem_read(reg[R_PC]++); uint16_t op = instr >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; case OP_JMP: {JMP, 7} break; case OP_JSR: {JSR, 7} break; case OP_LD: {LD, 7} break; case OP_LDI: {LDI, 6} break; case OP_LDR: {LDR, 7} break; case OP_LEA: {LEA, 7} break; case OP_ST: {ST, 7} break; case OP_STI: {STI, 7} break; case OP_STR: {STR, 7} break; case OP_TRAP: {TRAP, 8} break; case OP_RES: case OP_RTI: default: {BAD OPCODE, 7} break; } } {Shutdown, 12} }
6. Umsetzung der Anweisungen
Jetzt besteht Ihre Aufgabe darin, für jeden Opcode die richtige Implementierung vorzunehmen. Eine detaillierte Spezifikation jeder Anweisung ist in der
Projektdokumentation enthalten . Aus der Spezifikation müssen Sie herausfinden, wie jede Anweisung funktioniert, und eine Implementierung schreiben. Das ist einfacher als es klingt. Hier werde ich zeigen, wie zwei davon implementiert werden. Code für den Rest finden Sie im nächsten Abschnitt.
HINZUFÜGEN
Der
ADD Befehl nimmt zwei Zahlen, addiert sie und speichert das Ergebnis in einem Register. Die Spezifikation finden Sie in der Dokumentation auf Seite 526. Jede
ADD Anweisung lautet wie folgt:
Das Diagramm enthält zwei Zeilen, da es für diese Anweisung zwei verschiedene „Modi“ gibt. Bevor ich die Modi erkläre, versuchen wir, die Ähnlichkeiten zwischen ihnen zu finden. Beide beginnen mit vier identischen Bits
0001 . Dies ist der Opcode-Wert für
OP_ADD . Die nächsten drei Bits sind für das Ausgangsregister mit
DR gekennzeichnet. Das Ausgaberegister ist der Ort, an dem der Betrag gespeichert wird. Die folgenden drei Bits sind:
SR1 . Dies ist ein Register, das die erste hinzuzufügende Nummer enthält.
Somit wissen wir, wo das Ergebnis gespeichert werden soll, und wir kennen die erste hinzuzufügende Zahl. Es bleibt nur die zweite Nummer für die Hinzufügung herauszufinden. Hier beginnen sich die beiden Linien zu unterscheiden. Beachten Sie, dass das 5. Bit oben 0 und unten 1 ist. Dieses Bit entspricht entweder dem
Direktmodus oder dem
Registermodus . Im Registermodus wird die zweite Nummer wie die erste im Register gespeichert. Es ist als
SR2 markiert und in den Bits zwei bis null enthalten. Die Bits 3 und 4 werden nicht verwendet. In Assembler wird es so geschrieben:
ADD R2 R0 R1 ; add the contents of R0 to R1 and store in R2.
Im Sofortmodus wird der Sofortwert in den Befehl selbst eingebettet, anstatt den Inhalt des Registers hinzuzufügen. Dies ist praktisch, da das Programm keine zusätzlichen Anweisungen benötigt, um diese Nummer aus dem Speicher in das Register zu laden. Stattdessen befindet es sich bereits in der Anweisung, wenn wir es brauchen. Der Nachteil ist, dass dort nur kleine Zahlen gespeichert werden können. Um genau zu sein, maximal 2
5 = 32. Dies ist am nützlichsten, um Zähler oder Werte zu erhöhen. In Assembler können Sie wie folgt schreiben:
ADD R0 R0 1 ; add 1 to R0 and store back in R0
Hier ist ein Auszug aus der Spezifikation:
Wenn Bit [5] 0 ist, wird der zweite Quelloperand von SR2 erhalten. Wenn Bit [5] 1 ist, wird der zweite Quelloperand durch Erweitern von imm5 auf 16 Bit erhalten. In beiden Fällen wird der zweite Quelloperand zum Inhalt von SR1 hinzugefügt und das Ergebnis in DR gespeichert. (S. 526)
Dies ähnelt dem, was wir besprochen haben. Aber was ist eine „Erweiterung der Bedeutung“? Obwohl der Wert im Direktmodus nur 5 Bit hat, muss er mit einer 16-Bit-Nummer hinzugefügt werden. Diese 5 Bits sollten auf 16 erweitert werden, um einer anderen Zahl zu entsprechen. Für positive Zahlen können wir die fehlenden Bits mit Nullen füllen und den gleichen Wert erhalten. Bei negativen Zahlen funktioniert dies jedoch nicht. Zum Beispiel ist -1 in fünf Bits
1 1111 . Wenn Sie es nur mit Nullen füllen, erhalten wir
0000 0000 0001 1111 , was 32 ist! Das Erweitern des Werts verhindert dieses Problem, indem Bits mit Nullen für positive Zahlen und Einsen für negative Zahlen gefüllt werden.
uint16_t sign_extend(uint16_t x, int bit_count) { if ((x >> (bit_count - 1)) & 1) { x |= (0xFFFF << bit_count); } return x; }
Hinweis: Wenn Sie an binären negativen Zahlen interessiert sind, können Sie sich über zusätzlichen Code informieren . Dies ist jedoch nicht wesentlich. Kopieren Sie einfach den obigen Code und verwenden Sie ihn, wenn in der Spezifikation angegeben ist, dass der Wert erweitert werden soll.
Die Spezifikation hat den letzten Satz:
Die Bedingungscodes werden abhängig davon festgelegt, ob das Ergebnis negativ, null oder positiv ist. (S. 526)
Früher haben wir die Aufzählungsbedingung für Flags definiert, und jetzt ist es Zeit, diese Flags zu verwenden. Jedes Mal, wenn ein Wert in das Register geschrieben wird, müssen die Flags aktualisiert werden, um das Vorzeichen anzuzeigen. Wir schreiben eine Funktion zur Wiederverwendung:
void update_flags(uint16_t r) { if (reg[r] == 0) { reg[R_COND] = FL_ZRO; } else if (reg[r] >> 15) { reg[R_COND] = FL_NEG; } else { reg[R_COND] = FL_POS; } }
Jetzt können wir den Code für
ADD schreiben:
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t imm_flag = (instr >> 5) & 0x1; if (imm_flag) { uint16_t imm5 = sign_extend(instr & 0x1F, 5); reg[r0] = reg[r1] + imm5; } else { uint16_t r2 = instr & 0x7; reg[r0] = reg[r1] + reg[r2]; } update_flags(r0); }
Dieser Abschnitt enthält viele Informationen. Fassen wir also zusammen.
ADD nimmt zwei Werte und speichert sie in einem Register.- Im Registermodus befindet sich der zweite hinzuzufügende Wert im Register.
- Im direkten Modus ist der zweite Wert in die rechten 5 Bits des Befehls eingebettet.
- Werte, die kürzer als 16 Bit sind, sollten erweitert werden.
- Jedes Mal, wenn der Befehl den Fall ändert, sollten die Bedingungsflags aktualisiert werden.
Sie können überwältigt sein, wenn Sie 15 weitere Anweisungen schreiben. Die hier erhaltenen Informationen können jedoch wiederverwendet werden. Die meisten Anweisungen verwenden eine Kombination aus Werterweiterung, verschiedenen Modi und Flag-Aktualisierungen.
LDI
LDI bedeutet "indirektes" oder "indirektes" Laden (indirektes Laden). Dieser Befehl wird verwendet, um einen Wert von einem Speicherort in ein Register zu laden. Spezifikation auf Seite 532.
So sieht das binäre Layout aus:
Im Gegensatz zu
ADD gibt es keine Modi und weniger Parameter. Diesmal lautet der Operationscode
1010 , was dem Aufzählungswert
OP_LDI . Wieder sehen wir ein Drei-Bit-
DR (Ausgangsregister) zum Speichern des geladenen Wertes. Die restlichen Bits sind als
PCoffset9 markiert. Dies ist der unmittelbare Wert, der in die Anweisung eingebettet ist (ähnlich wie bei
imm5 ). Da der Befehl aus dem Speicher geladen wird, können wir davon ausgehen, dass diese Nummer eine Art Adresse ist, die angibt, woher der Wert geladen werden soll. In der Spezifikation wird näher erläutert:
Die Adresse wird berechnet, indem die Bits des Werts [8:0] auf 16 Bits erweitert und dieser Wert dem vergrößerten PC hinzugefügt werden. Was unter dieser Adresse im Speicher gespeichert ist, ist die Adresse der Daten, die in den DR geladen werden. (S. 532)
Nach wie vor müssen Sie diesen 9-Bit-Wert erweitern, diesmal jedoch zum aktuellen
PC hinzufügen. (Wenn Sie sich den Ausführungszyklus ansehen, hat sich der
PC unmittelbar nach dem Laden dieser Anweisung erhöht.) Die resultierende Summe ist die Ortsadresse im Speicher, und diese Adresse
enthält einen anderen Wert, nämlich die Adresse des Ladewerts.
Dies mag wie ein Umweg erscheinen, um aus dem Speicher zu lesen, aber es ist notwendig. Der
LD Befehl ist auf einen Adressversatz von 9 Bit begrenzt, während der Speicher eine Adresse von 16 Bit benötigt.
LDI ist nützlich, um Werte zu laden, die irgendwo außerhalb des aktuellen Computers gespeichert sind. Um sie jedoch zu verwenden, sollte die Adresse des endgültigen Speicherorts in der Nähe gespeichert werden. Sie können es sich als lokale Variable in C vorstellen, die auf einige Daten verweist:
Nach dem Schreiben des Werts in
DR sollten die Flags wie zuvor aktualisiert werden:
Die Bedingungscodes werden abhängig davon festgelegt, ob das Ergebnis negativ, null oder positiv ist. (S. 532)
Hier ist der Code für diesen Fall: (
mem_read im nächsten Abschnitt erläutert):
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset)); update_flags(r0); }
Wie gesagt, für diese Anweisung haben wir einen wesentlichen Teil des Codes und der Kenntnisse verwendet, die wir zuvor beim Schreiben von
ADD . Das gleiche gilt für den Rest der Anleitung.
Jetzt müssen Sie den Rest der Anweisungen implementieren. Befolgen Sie die
Spezifikationen und verwenden Sie den bereits geschriebenen Code. Der Code für alle Anweisungen finden Sie am Ende des Artikels. Zwei der zuvor genannten Opcodes werden nicht benötigt:
OP_RTI und
OP_RES . Sie können sie ignorieren oder einen Fehler machen, wenn sie aufgerufen werden. Wenn Sie fertig sind, kann der Großteil Ihrer VM als vollständig betrachtet werden!
7. Kinderbett gemäß Anleitung
Dieser Abschnitt enthält vollständige Implementierungen der verbleibenden Anweisungen, wenn Sie nicht weiterkommen.
RTI & RES
(nicht verwendet)
abort();
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t imm_flag = (instr >> 5) & 0x1; if (imm_flag) { uint16_t imm5 = sign_extend(instr & 0x1F, 5); reg[r0] = reg[r1] & imm5; } else { uint16_t r2 = instr & 0x7; reg[r0] = reg[r1] & reg[r2]; } update_flags(r0); }
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; reg[r0] = ~reg[r1]; update_flags(r0); }
Zweig
{ uint16_t pc_offset = sign_extend((instr) & 0x1ff, 9); uint16_t cond_flag = (instr >> 9) & 0x7; if (cond_flag & reg[R_COND]) { reg[R_PC] += pc_offset; } }
Springe
RET wird in der Spezifikation als separate Anweisung angegeben, da dies ein weiterer Befehl in Assembler ist. Dies ist eigentlich ein Sonderfall von
JMP .
RET tritt immer dann auf, wenn
R1 7 ist.
{ uint16_t r1 = (instr >> 6) & 0x7; reg[R_PC] = reg[r1]; }
Sprungregister
{ uint16_t r1 = (instr >> 6) & 0x7; uint16_t long_pc_offset = sign_extend(instr & 0x7ff, 11); uint16_t long_flag = (instr >> 11) & 1; reg[R_R7] = reg[R_PC]; if (long_flag) { reg[R_PC] += long_pc_offset; } else { reg[R_PC] = reg[r1]; } break; }
Laden
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = mem_read(reg[R_PC] + pc_offset); update_flags(r0); }
Register laden
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t offset = sign_extend(instr & 0x3F, 6); reg[r0] = mem_read(reg[r1] + offset); update_flags(r0); }
Effektive Ladeadresse
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = reg[R_PC] + pc_offset; update_flags(r0); }
Speichern
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); mem_write(reg[R_PC] + pc_offset, reg[r0]); }
Indirekt speichern
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); mem_write(mem_read(reg[R_PC] + pc_offset), reg[r0]); }
Ladenregister
{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t offset = sign_extend(instr & 0x3F, 6); mem_write(reg[r1] + offset, reg[r0]); }
8. Interrupt-Handhabungsverfahren
LC-3 bietet mehrere vordefinierte Routinen für die Ausführung allgemeiner Aufgaben und die Interaktion mit E / A-Geräten. Beispielsweise gibt es Verfahren zum Empfangen von Tastatureingaben und zum Ausgeben von Zeilen an die Konsole. Sie werden Trap-Routinen genannt, die Sie sich als Betriebssystem oder API für LC-3 vorstellen können. Jedem Unterprogramm wird ein Interrupt-Code (Trap-Code) zugewiesen, der es identifiziert (ähnlich einem Opcode).
Zur Ausführung wird eine Anweisung TRAPmit dem Code des gewünschten Unterprogramms aufgerufen .Legen Sie für jeden Interrupt-Code eine Aufzählung fest: enum { TRAP_GETC = 0x20, TRAP_OUT = 0x21, TRAP_PUTS = 0x22, TRAP_IN = 0x23, TRAP_PUTSP = 0x24, TRAP_HALT = 0x25 };
Sie fragen sich möglicherweise, warum Interrupt-Codes nicht in den Anweisungen enthalten sind. Dies liegt daran, dass sie LC-3 tatsächlich keine neuen Funktionen hinzufügen, sondern nur eine bequeme Möglichkeit bieten, die Aufgabe zu erledigen (wie Systemfunktionen in C). Im offiziellen LC-3-Simulator werden Interrupt-Codes in Assembler geschrieben . Wenn ein Interrupt-Code aufgerufen wird, wechselt der Computer zur Adresse dieses Codes. Die CPU führt die Anweisungen der Prozedur aus und wird nach Abschluss PCan den Ort zurückgesetzt, von dem aus der Interrupt aufgerufen wurde.: 0x3000 0x0 . , .
Es gibt keine Spezifikation für die Implementierung von Interrupt-Routinen: genau das, was sie tun sollen. In unserer VM verhalten wir uns etwas anders, indem wir sie in C schreiben. Wenn der Interrupt-Code aufgerufen wird, wird die Funktion C aufgerufen. Nach ihrer Operation wird der Befehl fortgesetzt.Obwohl die Prozeduren in Assembler geschrieben werden können und der physische Computer LC-3 dies sein wird, ist dies nicht die beste Option für die VM. Anstatt Ihre eigenen primitiven Eingabe-Ausgabe-Prozeduren zu schreiben, können Sie diejenigen verwenden, die auf unserem Betriebssystem verfügbar sind. Dies wird die virtuelle Maschine auf unseren Computern verbessern, den Code vereinfachen und eine höhere Abstraktionsebene für die Portabilität bereitstellen.Hinweis: Ein spezielles Beispiel ist die Tastatureingabe. Die Assembler-Version verwendet eine Schleife, um die Tastatureingabe kontinuierlich zu überprüfen. Aber so viel Prozessorzeit wird verschwendet! Mit der entsprechenden OS-Funktion kann das Programm vor dem Eingangssignal ruhig schlafen.
Fügen Sie im Multiple-Choice-Operator für den Opcode TRAPeinen weiteren Schalter hinzu: switch (instr & 0xFF) { case TRAP_GETC: {TRAP GETC, 9} break; case TRAP_OUT: {TRAP OUT, 9} break; case TRAP_PUTS: {TRAP PUTS, 8} break; case TRAP_IN: {TRAP IN, 9} break; case TRAP_PUTSP: {TRAP PUTSP, 9} break; case TRAP_HALT: {TRAP HALT, 9} break; }
Wie bei den Anweisungen werde ich Ihnen zeigen, wie Sie ein Verfahren implementieren und den Rest selbst erledigen.Putts
Der Interrupt-Code wird PUTSverwendet, um eine Zeichenfolge mit einer abschließenden Null zurückzugeben (ähnlich printfin C). Spezifikation auf Seite 543.Um eine Zeichenfolge anzuzeigen, müssen wir der Interrupt-Routine eine Zeichenfolge zur Anzeige geben. Dies erfolgt durch Speichern der Adresse des ersten Zeichens R0vor Beginn der Verarbeitung.Aus der Spezifikation:Zeigen Sie die ASCII-Zeichenfolge in der Konsolenanzeige an. Zeichen sind in aufeinanderfolgenden Speicherzellen enthalten, ein Zeichen pro Zelle, beginnend mit der in angegebenen Adresse R0. Die Ausgabe endet, wenn ein Wert im Speicher gefunden wird x0000. (S. 543)
Beachten Sie, dass im Gegensatz zu C-Zeichenfolgen die Zeichen hier nicht in einem Byte, sondern an einer Stelle im Speicher gespeichert werden . Der Speicherplatz des LC-3 beträgt 16 Bit, sodass jedes Zeichen in der Zeichenfolge 16 Bit beträgt. Um dies in der C-Funktion anzuzeigen, müssen Sie jeden Wert in ein Zeichen konvertieren und separat drucken. { uint16_t* c = memory + reg[R_R0]; while (*c) { putc((char)*c, stdout); ++c; } fflush(stdout); }
Für dieses Verfahren ist nichts mehr erforderlich. Die Interrupt-Routinen sind ziemlich einfach, wenn Sie C kennen. Kehren Sie nun zu den Spezifikationen zurück und implementieren Sie den Rest. Wie bei den Anweisungen finden Sie den vollständigen Code am Ende dieses Handbuchs.9. Spickzettel für Interruptroutinen
Dieser Abschnitt enthält vollständige Implementierungen der verbleibenden Interruptroutinen.Zeicheneingabe
reg[R_R0] = (uint16_t)getchar();
Zeichenausgabe
putc((char)reg[R_R0], stdout); fflush(stdout);
Zeicheneingabeanforderung
printf("Enter a character: "); reg[R_R0] = (uint16_t)getchar();
Leitungsausgang
{ uint16_t* c = memory + reg[R_R0]; while (*c) { char char1 = (*c) & 0xFF; putc(char1, stdout); char char2 = (*c) >> 8; if (char2) putc(char2, stdout); ++c; } fflush(stdout); }
Programmbeendigung
puts("HALT"); fflush(stdout); running = 0;
10. Programme herunterladen
Wir haben viel über das Laden und Ausführen von Anweisungen aus dem Speicher gesprochen, aber wie gelangen Anweisungen im Allgemeinen in den Speicher? Wenn Sie ein Assembler-Programm in Maschinencode konvertieren, ist das Ergebnis eine Datei, die ein Array von Anweisungen und Daten enthält. Sie können es herunterladen, indem Sie den Inhalt einfach direkt an eine Adresse im Speicher kopieren.Die ersten 16 Bits der Programmdatei geben die Adresse im Speicher an, an der das Programm starten soll. Diese Adresse wird als Ursprung bezeichnet . Es muss zuerst gelesen werden, danach werden die restlichen Daten aus der Datei in den Speicher eingelesen.Hier ist der Code zum Laden des Programms in den LC-3-Speicher: void read_image_file(FILE* file) { uint16_t origin; fread(&origin, sizeof(origin), 1, file); origin = swap16(origin); uint16_t max_read = UINT16_MAX - origin; uint16_t* p = memory + origin; size_t read = fread(p, sizeof(uint16_t), max_read, file); while (read-- > 0) { *p = swap16(*p); ++p; } }
Beachten Sie, dass für jeden geladenen Wert aufgerufen wird swap16. LC-3-Programme werden in direkter Bytereihenfolge geschrieben, aber die meisten modernen Computer verwenden die umgekehrte Reihenfolge. Infolgedessen müssen wir jeden geladenen umdrehen uint16. (Wenn Sie versehentlich einen fremden Computer wie PPC verwenden , muss nichts geändert werden.) uint16_t swap16(uint16_t x) { return (x << 8) | (x >> 8); }
Hinweis: Die Bytereihenfolge bezieht sich darauf, wie die Bytes einer Ganzzahl interpretiert werden. In umgekehrter Reihenfolge ist das erste Byte die niedrigstwertige Ziffer und in umgekehrter Reihenfolge umgekehrt. Soweit ich weiß, ist die Entscheidung meist willkürlich. Verschiedene Unternehmen haben unterschiedliche Entscheidungen getroffen, daher haben wir jetzt unterschiedliche Implementierungen. Für dieses Projekt müssen Sie nichts mehr über die Bytereihenfolge wissen.
Fügen Sie auch eine praktische Funktion für hinzu read_image_file, die den Pfad für die Zeichenfolge übernimmt: int read_image(const char* image_path) { FILE* file = fopen(image_path, "rb"); if (!file) { return 0; }; read_image_file(file); fclose(file); return 1; }
11. Zugeordnete Register
Einige Sonderregister sind in der regulären Registertabelle nicht verfügbar. Stattdessen ist ihnen eine spezielle Adresse im Speicher vorbehalten. Um diese Register zu lesen und zu schreiben, lesen und schreiben Sie einfach in ihren Speicher. Sie werden als speicherabgebildete Register bezeichnet . Normalerweise werden sie zur Interaktion mit speziellen Hardwaregeräten verwendet.Für unseren LC-3 müssen wir zwei abbildbare Register implementieren. Dies ist das Tastaturstatusregister ( KBSR) und das Tastaturdatenregister ( KBDR). Die erste zeigt an, ob die Taste gedrückt wurde, und die zweite gibt an, welche Taste gedrückt wurde.Obwohl Tastatureingaben mit angefordert werden können GETC, blockiert sie die Ausführung, bis Eingaben empfangen werden. KBSRund KBDRerlaubenFragen Sie den Status des Geräts ab, während Sie das Programm weiter ausführen, damit es während des Wartens auf Eingaben reagiert. enum { MR_KBSR = 0xFE00, MR_KBDR = 0xFE02 };
Zugeordnete Register erschweren den Speicherzugriff etwas. Wir können nicht direkt in das Speicherarray lesen und schreiben, sondern müssen spezielle Funktionen aufrufen - den Setter und den Getter. Nach dem Lesen des Speichers aus dem KBSR-Register überprüft der Getter die Tastatur und aktualisiert beide Speicherorte. void mem_write(uint16_t address, uint16_t val) { memory[address] = val; } uint16_t mem_read(uint16_t address) { if (address == MR_KBSR) { if (check_key()) { memory[MR_KBSR] = (1 << 15); memory[MR_KBDR] = getchar(); } else { memory[MR_KBSR] = 0; } } return memory[address]; }
Dies ist die letzte Komponente einer virtuellen Maschine! Wenn Sie den Rest der Interrupt-Routinen und -Anweisungen implementiert haben, sind Sie fast bereit, es zu versuchen!Alles, was geschrieben wurde, sollte in der folgenden Reihenfolge zur C-Datei hinzugefügt werden: {Memory Mapped Registers, 11} {TRAP Codes, 8} {Memory Storage, 3} {Register Storage, 3} {Functions, 12} {Main Loop, 5}
12. Plattformfunktionen
Dieser Abschnitt enthält einige langwierige Details, die für den Zugriff auf die Tastatur und die ordnungsgemäße Funktion erforderlich sind. Der Betrieb virtueller Maschinen ist weder interessant noch informativ. Fühlen Sie sich frei zu kopieren und einzufügen!Wenn Sie versuchen, die VM unter einem anderen Betriebssystem als Unix wie Windows zu starten, müssen diese Funktionen durch die entsprechenden Windows-Funktionen ersetzt werden. uint16_t check_key() { fd_set readfds; FD_ZERO(&readfds); FD_SET(STDIN_FILENO, &readfds); struct timeval timeout; timeout.tv_sec = 0; timeout.tv_usec = 0; return select(1, &readfds, NULL, NULL, &timeout) != 0; }
Code zum Extrahieren des Pfads aus den Programmargumenten und zum Ausgeben eines Verwendungsbeispiels, falls diese fehlen. if (argc < 2) { printf("lc3 [image-file1] ...\n"); exit(2); } for (int j = 1; j < argc; ++j) { if (!read_image(argv[j])) { printf("failed to load image: %s\n", argv[j]); exit(1); } }
Unix-spezifischer Konfigurationscode für die Terminaleingabe. struct termios original_tio; void disable_input_buffering() { tcgetattr(STDIN_FILENO, &original_tio); struct termios new_tio = original_tio; new_tio.c_lflag &= ~ICANON & ~ECHO; tcsetattr(STDIN_FILENO, TCSANOW, &new_tio); } void restore_input_buffering() { tcsetattr(STDIN_FILENO, TCSANOW, &original_tio); }
Wenn das Programm unterbrochen wird, möchten wir die Konsole auf ihre normalen Einstellungen zurücksetzen. void handle_interrupt(int signal) { restore_input_buffering(); printf("\n"); exit(-2); }
signal(SIGINT, handle_interrupt); disable_input_buffering();
restore_input_buffering();
{Sign Extend, 6} {Swap, 10} {Update Flags, 6} {Read Image File, 10} {Read Image, 10} {Check Key, 12} {Memory Access, 11} {Input Buffering, 12} {Handle Interrupt, 12}
#include <stdio.h> #include <stdlib.h> #include <stdint.h> #include <string.h> #include <signal.h> #include <unistd.h> #include <fcntl.h> #include <sys/time.h> #include <sys/types.h> #include <sys/termios.h> #include <sys/mman.h>
Start der virtuellen Maschine
Jetzt können Sie die virtuelle LC-3-Maschine erstellen und ausführen!- Kompilieren Sie das Programm mit Ihrem Lieblings-Compiler.
- Laden Sie die kompilierte Version von 2048 oder Rogue herunter .
- Führen Sie das Programm mit der obj-Datei als Argument aus:
lc3-vm path/to/2048.obj - Spielen Sie im Jahr 2048!
Control the game using WASD keys. Are you on an ANSI terminal (y/n)? y +--------------------------+ | | | | | | | 2 | | | | 2 | | | | | | | +--------------------------+
Debuggen
Wenn das Programm nicht richtig funktioniert, haben Sie höchstwahrscheinlich eine Anweisung falsch codiert. Das Debuggen kann schwierig sein. Ich empfehle, dass Sie gleichzeitig den Assembler-Code des Programms lesen - und mit Hilfe des Debuggers Schritt für Schritt den Anweisungen der virtuellen Maschine nacheinander folgen. Stellen Sie beim Lesen des Codes sicher, dass die VM die vorgesehene Anweisung befolgt. Wenn eine Nichtübereinstimmung auftritt, finden Sie heraus, welche Anweisung das Problem verursacht hat. Lesen Sie die Spezifikation erneut und überprüfen Sie den Code erneut.14. Alternative Methode in C ++
Hier ist eine erweiterte Methode zum Ausführen von Anweisungen, die die Codegröße erheblich reduziert. Dies ist ein völlig optionaler Abschnitt.Da C ++ während des Kompilierungsprozesses leistungsstarke Generika unterstützt, können wir mit dem Compiler Teile von Anweisungen erstellen. Diese Methode reduziert die Codeduplizierung und liegt tatsächlich näher an der Hardwareebene des Computers.Die Idee ist, die für jede Anweisung gemeinsamen Schritte wiederzuverwenden. Einige Anweisungen verwenden beispielsweise die indirekte Adressierung oder Erweiterung eines Werts und das Hinzufügen zum aktuellen Wert PC. Stimmen Sie zu, wäre es schön, diesen Code einmal für alle Anweisungen zu schreiben?Wenn wir die Anweisung als eine Folge von Schritten betrachten, sehen wir, dass jede Anweisung nur eine Neuanordnung mehrerer kleinerer Schritte ist. Wir werden Bit-Flags verwenden, um anzugeben, welche Schritte für jede Anweisung zu befolgen sind. Der Wert 1im Befehlsnummernbit gibt an, dass der Compiler für diesen Befehl diesen Codeabschnitt enthalten sollte. template <unsigned op> void ins(uint16_t instr) { uint16_t r0, r1, r2, imm5, imm_flag; uint16_t pc_plus_off, base_plus_off; uint16_t opbit = (1 << op); if (0x4EEE & opbit) { r0 = (instr >> 9) & 0x7; } if (0x12E3 & opbit) { r1 = (instr >> 6) & 0x7; } if (0x0022 & opbit) { r2 = instr & 0x7; imm_flag = (instr >> 5) & 0x1; imm5 = sign_extend((instr) & 0x1F, 5); } if (0x00C0 & opbit) {
static void (*op_table[16])(uint16_t) = { ins<0>, ins<1>, ins<2>, ins<3>, ins<4>, ins<5>, ins<6>, ins<7>, NULL, ins<9>, ins<10>, ins<11>, ins<12>, NULL, ins<14>, ins<15> };
Hinweis: Diese Technik habe ich mit dem von Bisqwit entwickelten NES-Emulator kennengelernt . Wenn Sie an Emulation oder NES interessiert sind, empfehle ich die Videos.Andere Versionen von C ++ verwenden den bereits geschriebenen Code. Vollversion hier . {Includes, 12} {Registers, 3} {Condition Flags, 3} {Opcodes, 3} {Memory Mapped Registers, 11} {TRAP Codes, 8} {Memory Storage, 3} {Register Storage, 3} {Functions, 12} int running = 1; {Instruction C++, 14} {Op Table, 14} int main(int argc, const char* argv[]) { {Load Arguments, 12} {Setup, 12} enum { PC_START = 0x3000 }; reg[R_PC] = PC_START; while (running) { uint16_t instr = mem_read(reg[R_PC]++); uint16_t op = instr >> 12; op_table[op](instr); } {Shutdown, 12} }