Was ich beim Implementieren von Sokoban fürs Intel 8080 gelernt habe

Lange Zeit habe ich Bock gehabt, eine Aufgabe auszusuchen, die mir die Gelegenheit bieten würde, die Computerarchitektur auf eine hardwarenähere Weise zu erforschen. Seitdem ich einen sehr nachlässig unterrichteten und unbefriedigenden Computerarchitekturkurs auf UNM belegte habe ich dieses Thema wieder zu besuchen gewollt. Ich programmiere gern in Brainfuck aber es ist nicht ohne Grund, daß man es eine esoterische Programmiersprache nennt und es ist wohl ähnlicher zum mathematischen Ideal von einer Turingmaschine als zu einer wirklichen CPU. Das Assemblierspracheprogrammieren bleibt immer eine Option aber nie fällt es mir ein, was ich darin programmieren soll.

Vor einigen Wochen entdeckte ich die Webseite von Emulator 101 und wusste sofort, daß es genau was ich gesucht hatte war. Was wäre eine bessere Übung, um die CPUs zu verstehen, als die Implementierung von jeder ihrer Operationen in C? Die Webseite präsentiert eine sehr hilfreiche und detallierte Anleitung davon und am Ende gibt es eine lockende Belohnung: man kann die originale ausführbare Datei von Space Invaders auf dem eigenen Ordner spielen! Die Intel-8080-Architektur ist anders als die moderne Rechnerarchitekturen aber mindestens ist es eine, damit die Leute "wirkliche" Computerprogramme geschrieben hat.

Nach mehrere Wochen von schmerzhaften Fehlerbehebung schaffte ich endlich, Space Invaders auszuführen:

Meine 8080-Emulator soll eine der schwersten Programmen gewesen sein, die ich je debuggen zu müssen habe und es wäre fast gar nicht möglich, wären diese ausführliche Anmerkungen nicht zuhanden. Das schwerste Teil war mir die korrekte Abwicklung von den CPU-Flags weil sie nicht so spezifisch in den Programmierhandbuch vom Intel-8080 dokumentiert sind. Ich habe auch die Datei von einem anderen alten Taito-Videospiel namens Lunar Rescue gefunden und ich konnte es auch spielen (aber nur nachdem es noch mehr Fehlern meines Emulators enthüllte):

Auch spielte ich einen niedlichen Vorgänger von Space Invaders namens Gunfight:

Ich will noch nichts an der Implimentierung des Emulators außer meine herzliche Empfehlung an der Emulator-101-Anleitung, die mir als ein fantastisches Hilfsmittel gedient hat, sagen. Nachdem ich so viel Zeit in der Datei von Space Invaders vertieft verbrachte und Teilen von Lunar Rescue und Gunfight zu rückentwickeln versuchte (meistens um die Korrespondenz zwischen den Spielekontrollen oder den Geräuscheffekten und den Bits der IN- und OUT-Ports auszurechnen) möchtete ich wohl etwas eigenes zu programmieren zu versuchen. Ich bin ein Megafan von Sokoban-Rätsel, deswegen versuchte ich, sie fürs Intel 8080 zu implementieren.

Du kannst sowohl meinen Versuch eines Intel-8080-Emulator als die Dateien von Space Invaders, Lunar Rescue, Gunfight und meinem Sokoban-Spiel in diesem Github-Repo angucken und mithilfe des Makefile übersetzen und spielen. Hier unten findest du einen Screenshot von einem Lieblingsrätsel von mir:

Sokoban ist ein ziemlich einfaches gitterbasiertes Spiel, deshalb nimm ich die Herausforderung an, das Programm direkt als Binärdatei ohne Assembliersprache zu schreiben, um so viel Intuition an der hardwarenahen Programmierung wie möglich zu entwickeln. (Nee, ich bin kein Masochist.) Ich benutze ein Hexaufbereiter namens Hex Fiend um die Binärdatei zu bearbeiten. Es ist eine sehr interessante Übung gewesen, die mir das Gehirn auf ganz andere Weise als die Programmierung mit Hochsprachen angestrengt hat.

Hier schreibe ich nichts technisches an der Struktur meines Programms. Wenn du die Kleinigkeiten gucken möchtest, dann schau mal meine persönliche Notizen an. Hier unten geschrieben kannst du aber einige allgemeine Lektionen fürs Binärprogrammieren lesen, die ich beim Schreiben mein erstes Intel-8080-Programms gelernt habe.

Die Notizen sind besonders wichtig. Meiner Meinung nach sind die Notizen auch wichtig beim Programmieren im allgemeinen und für die meisten Softwareprojekte mache ich sehr viel, doch in einer Hochsprache kann man oft viel undokumentierten Code ohne große Konsequenzen schreiben. Sowohl könnte man selbstdokumentierenden Code schreiben. Nicht so beim Programmieren von Binärdateien.

Wohl gibt es Gelegenheiten in den Hochsprachen, bedeutungsvolle Namen den Variablen zuzuweisen, die es in der Assemblierprogrammierung nicht gibt, aber das ist nicht der einzige Grund. In der Assemblierprogrammierung verabschiedet sich die referenzielle Transparenz der Funktionsaufrufe einer Hochsprache. Wohl kann man die referenzielle Transparenz der Funktionen meistens mittels der PUSH- und POP-Anleitungen versichern aber natürlich will man nicht so viel zusätzliche Anleitungen ergänzen, wenn es nicht nötig sei (besonders wenn man mit einem Hexaufbereiter langsam einen Nibble nach dem Anderen hineintippt).

Verschiedene Computerarchitekturen haben einzelne Aufrufkonventionen, die bestimmen (neben anderen Dingen) die Register, die die Funktionsaufrufe erhalten sollen und die Register, die "volatil" behandelt werden können. Solche Konventionen sind der Interoperabilität unentbehrlich. Wenn man selbst ein eigenständiges Spiel entwickelt spielt die Interoperabilität mit den Dateien anderer Programmierer keine Rolle aber trotzdem muss man erinnern welche Register diese oder die andere Funktion als Parameter oder als Rückgabewert benutzt und welche Register es gar nicht verändert (oder den originalen Wert durch ein POP annehmen lässt). Dafür sind die Notizen nötig.

Hier findest du ein Beispiel von einer "Aufrufekonvention" die ich für eine Hilfsfunktion schrieb:

ROUTINE DRAWTILERUN 0x0080
Calling convention for drawTileRun:
- HL must contain the address of the sprite ID sequence
    - Format: 1b length of sequence, followed by L bytes
- (B,C) must be the coordinates on the 32x32 screen to start drawing
- After calling, HL points to the last element of the sequence
- After calling, (B,C) are the coords of the cell AFTER the last cell
- E is not affected

Lass viel Platz zwischen den Funktionen hinter. Wenn man in Assembliersprache programmiert und die Fähigkeit besitzt, eine bestimmte Codezeile mit eine Bezeichnung zu markieren und dazu mit Sprunganweisungen zu springen, dann kümmert sich der Assembler um diese Komplikation und muss man es nicht selbst besorgen. Aber wie ich schon erzählt habe, wurstelte ich mich diese Übung mit einem Hexaufbereiter durch. Wenn man den schon geschriebene Code mit Ergänzungen oder Löschungen bearbeitet dann ändert sich die Speicherstelle jeder nachfolgenden Anweisung. Deshalb wird die Anweisung, auf die jede JMP- oder CALL-Anweisung, die eine Adresse von dieser Speicherregion bestimmt, weist hin, wahrscheinlich kaputtgehen, weil es einen Sprung zu einer ganz anderen Anweisung loslassen wird.

Natürlich ist es nicht erträglich, jede JMP- oder CALL-Anweisung nach jede Bearbeitung manuell zu aktualisieren. Es wäre auch Unsinn, wenn man gläubt, der kann jede Anweisung erstmals korrekt wählen und keine Bearbeitungen machen müssen.

Stattdessen könnte man viel "Schlupfspeicher" nach jede Funktion verteilen, der aus eine lange Folge von NOPs besteht. So kann man ein paar Bytes von irgendeiner Funktion ergänzen oder löschen, ohne die folgende Funktionen zu rühren, weil die endliche Folge von NOPs als ein Puffer dient. Man könnte diese Technik nicht nur am Anfang der Funktionen sondern auch für wichtige Zeilen mitten in der Funktion, die der Zielpunkt einer JMP-Anweisung woanders in der Funktion ist, benutzen, um sich gegen Speicherverschiebungen innerhalb der Funktion abzusichern (besonders wenn die Funktion sehr lang ist).

Um diese Technik zu benutzen ist es doch leider nötig, daß man eine Vermutung über die nach allem unvermeidlichen Überarbeiten maximale Länge von jeder Funktion. Viel Glück! Notfalls kann man einfach zu einem anderswo gespeicherten Code-Ausschnitt springen und danach zurückspringen.

Manchmals muss sich die Effizienz der Annehmlichkeit unterwerfen. Mit "Effizienz" meine ich eher Speichereffizienz als Geschwindigkeit. Die Emulation in C ist ziemlich schnell und wenn es um ein einfaches Spiel wie Space Invaders oder Sokoban geht sind die Rechnungen nicht sehr intensiv. Mein Sokoban-Spiel ist nicht sehr groß aber es ist zwar ein bisschen aufgeschwemmter als die Space-Invaders-Datei großenteils weil man mit der Redundanz sehr viel Zeit sparen kann, wenn man es erdulden kann.

Ein Beispiel von diesem Kompromiss, dem ich beim Implementieren von Sokoban begegnete: In meiner Implementierung werden die Positionen der Spieler und der Kisten als Koordinaten gespeichert und im Gegenteil werden die "Kacheln" (Mauern, Zielscheiben und leere Plätze) in einer Matrix gespeichert. Weil es nur 3 Arten von Kacheln gibt braucht man theoretisch nur 2 Bits, um den Wert eines bestimmten Kachels zu bestimmen. Deshalb kann man die ganze Kachelmatrix eines Sokoban-Rätsels sehr intuitiv mit nur $N/4$ Bytes räpresentieren, wenn es aus $N$ Kacheln besteht.

Doch so machte ich es gar nicht. Stattdessen teilte ich ein Byte pro Kachel zu. All 8x8 Spielsprites sind in einer Speicherregion ab 0x2000 konsekutiv gespeichert und jedes Byte der Kachelmatrix weist den Index des angemessenen Sprites in dieser Reihenfolge hin. Das ist megaineffizient weil es nur drei verschiedene Werte in dieser Matrix gibt, nämlich 0x24 (Mauer), 0x2c (leerer Platz) und 0x27 (Zielscheibe). Diese Wahl ist mir noch ein bisschen peinlich aber wahrscheinlich würde ich noch ein paar Stunden von frustrierenden Fehlerhebung erledigen mussen, wenn ich vier 2-Bit-Kachelcodes in jedem Byte der Kachelmatrix kombiniert hätte, weil in diesem Fall wäre es nötig, das $n/4$-te Byte in der Kachelmatrix zu finden und es $2\cdot (n\bmod 4)$ Bits zu verschieben, um das korrekte Paar von Bits, das einem Kachel mit dem Index $n$ entspricht, zu extrahieren. Danach würde ich den 2-Bit-Kachelcode in den korrekten Spriteindex übersetzen und den entsprechenden Sprite an der angemessenen Stelle zeichnen müssen.

Nein danke. In meiner Implementierung muss ich nur den Anfang der Spritefolge suchen, das Registerpaar HL dem Kachelindex hinzufügen und den Sprite, der da gefunden ist, zeichnen. Im Austausch für diese Annehmlichkeit sind die Rätseldateien aufgeschwemmter, als sie gewesen sein könnten.

Wenn du noch nicht überzeugt bist und noch lieber die 2-Bits-Pro-Kachel-Idee hättest, dann erwidere ich: theoretisch ist es auch möglich, ein Code zu entwickeln, der ungefähr $\approx \log_2(3)\cdot N/8$ oder weniger als $N/8$ Bytes pro $N$ Kacheln verbraucht, wenn es nur $3$ verschiedene Werte für jedes Kachel gibt. Mir ist es noch klarer das ein Kompressionsalgorithmus dieser Art für ein kleines Sokobanspielchen übertrieben wäre - doch es kommt darauf an, was du für einen Ausgleich findest.

Wenn es um die Modularität geht, muss man sich auf das Wesentliche beschränken. Wenn du diese Übung auch mit so wenigen Hilfskrücken von Hochsprachen wie ich übernimmst muss der Softwareentwickler in dich in den Hintergrund treten. Zwar kann es sein, daß du den inneren Softwareentwickler fesseln, knebeln, verblenden und in den Hintergrund werfen musst! Wenn du auf einem sehr modularen Programm beharrst dann wird diese Übung sehr lange dauern.

Ich setzte mich gar nicht daran, etwas Megamodulares zu schreiben. Ohne Zweifel gibt es noch verpasste Gelegenheiten in meiner Implementierung, noch ein Umweg zu integrieren, damit es einfacher wäre, diesen oder jenen Spielmechanismus zu ändern. (Die habe ich meistens verpasst, weil ich den ganzen Scheißprojekt schon fertigstellen wollte.)

Wohl ist die Erweiterbarkeit einigen Aspekten des Spiels nützlichen als anderen Ich habe nicht vor, wesentliche Veränderungen der Spielregeln im Zukunft zu implementieren. Natürlich könnte ich doch ein paar neue Sokobanrätsel ergänzen wollen und deshalb habe ich es so weit wie möglich erleichtert, neue Rätsel ins Datensegment ohne große Änderungen im Codesegment einzuführen.

Codes sind Daten. Einige Hochsprachen betonen die Tatsache, daß "Code" und "Datum" eher zwei Perspektiven auf dem gleichen ding als verschiedene Dinge sind. (Ich habe Scheme im Sinn.) Nie ist diese Einsicht so klar als wenn man die ausführbare Anweisungen manuell im gleichen Binärdatei als die Zeichenfolgen, die Sprites und den Bildspeicherplatz schreibt. Wenn man die RET-Anweisung am Ende einer Funktion vergisst kann der Programmzähler bis zum Bildspeicherplatz oder noch weiter abhauen und auszuführen versuchen, was immer es da findet.

Einige der lächerlichsten Fehlern waren dank des Weglaufens des Programmzählers zu eine unangemessene Speicheradresse. Manchmal stürzt der Programm ab, weil es versucht, eine nicht existierende CPU-Anweisung auszuführen. Sonst stiftet es doch Chaos und Verwüstung auf dem Speil. Dieser Pixelsalat habe ich mehrmals gesehen, meistens als der Programmzähler aus das Codesegment geflüchtet war:

Dieser sieht sehr rätselhaft aus:

Und diese allmähliche Datenverfälschung sah ziemlich skurril aus: