SectorC: Ein in 512 Byte gebauter C-Compiler

• SectorC, geschrieben in x86-16-Assembly, ist ein extrem kleiner C-Compiler, der in den Bootsektor (512 Byte) einer x86-Maschine passt und eine Teilmenge der C-Sprache unterstützt, die groß genug ist, um tatsächlich lauffähige Programme zu schreiben
• Unterstützt werden unter anderem globale Variablen, Funktionen, if/while-Anweisungen, Operatoren, Pointer-Dereferenzierung, Kommentare und Inline-Assembly, sodass selbst mit minimaler Struktur vollständige Programme ausgeführt werden können
• Um den Tokenizer zu vereinfachen, wurde mit leerzeichenbasierter Tokenisierung und einem atoi()-Hash die Sprache Barely C entworfen, die die bestehende C-Syntax beibehält und zugleich eine extreme Größenreduktion erreicht
• Bei der Code-Optimierung wurden verschiedene Komprimierungstechniken auf Assembly-Ebene eingesetzt, darunter Entfernung von Sprüngen, Zusammenlegung von Aufrufen, Nutzung von 8-Bit-Offsets sowie stosw/lodsw, wodurch der Code von 468 Byte auf 303 Byte schrumpfte
• Im Ergebnis wurde innerhalb von 512 Byte ein vollständiger C-Compiler inklusive Tokenizer, Parser, Codegenerator und Runtime implementiert und damit ein extremes Beispiel für Software-Minimierung gezeigt

---

Überblick über SectorC

• SectorC ist ein in x86-16-Assembly geschriebener C-Compiler, der vollständig in einen 512-Byte-Bootsektor passt
  • Das GitHub-Repository ist xorvoid/sectorc
  • Die unterstützte Sprache ist eine C-Teilmenge, mit der sich reale Programme schreiben lassen
• Zu den unterstützten Funktionen gehören globale Variablen, Funktionen, Kontrollstrukturen (if/while), verschiedene Operatoren, Pointer-Dereferenzierung, Inline-Assembly und Kommentare
• Als Beispielprogramm wird Code zum Zeichnen einer Sinuswellen-Animation im VGA-Modus gezeigt

Designhintergrund und Ansatz

• Da ein herkömmlicher C-Tokenizer so groß ist, dass er in 512 Byte praktisch unmöglich unterzubringen wäre, musste die Sprachstruktur selbst vereinfacht werden
• Big Insight #1: Wie bei der Sprache Forth wurde eine durch Leerzeichen getrennte Token-Struktur eingeführt und eine abgewandelte Sprache namens „Barely C“ entworfen
  • Beispiel: Syntax wie int(main)(){while(!done){ wird als einzelnes „Mega-Token“ behandelt
  • Sie wird auch von bestehenden C-Compilern weiterhin als gültiger C-Code erkannt
• Big Insight #2: Die Funktion atoi() wird wie eine Hash-Funktion verwendet, um Tokens in Zahlen umzuwandeln
  • Integer-Literale, Schlüsselwörter und Bezeichner werden alle über den Rückgabewert von atoi() verarbeitet
  • Auf Bezeichner wird über ihren Index in einem 64K-Array zugegriffen

Umsetzung von Barely C

• Die erste Implementierung war 468 Byte groß und nutzte einen rekursiven Abstiegparser mit atoi-basierten Tokens
  • Ohne Symboltabelle wird direkt über den Hashwert auf ein 64K-Segment zugegriffen
  • Die Codegenerierung folgt dem OTCC-Stil und verwendet das Register ax als Speicherort für Ergebnisse
• Später wurde mit byte-threaded code experimentiert, um eine Forth-artige Struktur zu versuchen, doch innerhalb von 512 Byte erwies sich das als eher ineffizient und wurde verworfen

Techniken zur Code-Minimierung

• Durch die Rückkehr zu einer geradlinigen Struktur schrumpfte der Code von 468 Byte auf 303 Byte
  • Verwendet wurden Techniken wie Fall-through zur Sprungvermeidung, Tail-Call, Call Fusion, Nutzung von stosw/lodsw und das Beibehalten von 8-Bit-Sprung-Offsets
• Dadurch wurden 207 Byte freier Platz für zusätzliche Funktionen gewonnen

Ausbau zu vollständigerer C-Funktionalität

• Mit zusätzlichen 200 Byte wurde Unterstützung für vollständige C-Syntax erreicht
  • Verschachtelte if-/while-Blöcke sowie verschiedene *binäre Operatoren (+, -, , &, |, ^, <<, >>, ==, !=, <, >, <=, >=)
  • Unterstützung für Funktionsdefinitionen und rekursive Aufrufe, Inline-Assembly (asm) sowie einzeilige und mehrzeilige Kommentare
  • Über eine Operatortabelle (binary_oper_tbl) wird jeder Operator mit 4 Byte definiert, sodass 14 Operatoren in 56 Byte verarbeitet werden

Grammatikstruktur

• Die gesamte Grammatik besteht aus program, var_decl, func_decl, statement, expr usw.
• Sowohl //- als auch /* */-Kommentare werden unterstützt
• Der Text der Grammatikdefinition selbst ist mit 704 Byte größer als die eigentliche Implementierung

Inline-Assembly und Runtime

• Über die asm-Syntax kann x86-16-Maschinencode direkt eingefügt werden
  • Eine unverzichtbare Funktion für I/O-Verarbeitung
• Die Runtime (rt/) besteht aus zwei in C geschriebenen Dateien
  • rt/lib.c: Bibliotheksroutinen auf Basis von Inline-Assembly
  • rt/_start.c: Programmeinstiegspunkt _start()

Beispielprogramme

• examples/hello.c: Gibt Text direkt in den Speicher 0xB8000 aus
• examples/sinwave.c: Zeigt eine Sinuswellen-Animation im VGA-Modus 0x13 an
• examples/twinkle.c: Spielt „Twinkle Twinkle Little Star“ über den PC-Lautsprecher ab (mit Lautstärkewarnung)

Fazit

• SectorC ist ein ultrakleiner C-Compiler, der ein scheinbar unmögliches Ziel erreicht, und zeigt ein extremes Beispiel für Software-Minimierung und kreatives Sprachdesign
• Der Artikel endet mit humorvollen Auswahlmöglichkeiten zu „Was haben wir gelernt?“ und betont satirisch die Haltung, das Unmögliche herauszufordern, sowie den Wert der Vereinfachung von Software