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

[GN⁺]

Hacker-News-Kommentare

• Wenn eine solche Implementierung in den 1980ern existiert hätte, gäbe es im C-Standard wohl eine Regel, dass Hash-Kollisionen zwischen unterschiedlichen Tokens mit demselben 16-Bit-Wert undefiniertes Verhalten (UB) auslösen
  Optimierende Compiler der 2000er hätten solche Tokens vielleicht einfach zu No-ops wegoptimiert 😉
  • „Du hast die Option -wTokenHashCollision nicht aktiviert! Das UB ist wegen deiner Unwissenheit entstanden. Die Spezifikation ist vollkommen eindeutig!“ lautete eine scherzhafte Reaktion
  • So realistisch, dass ich laut lachen musste. LMAO
• Sieht ähnlich aus wie mein kürzlich gebauter X86-16-Bootsektor-C-Compiler
  Bootsektor-Spiele zu bauen ist wirklich eine magische, nostalgische Erfahrung. Es erinnert mich an eine Zeit, in der Programmieren noch wirklich Spaß gemacht hat
  Schade, dass solche Projekte im heutigen KI-Zeitalter so unterschätzt werden
  Link zu meinem Projekt
  • Hm, im Artikel geht es nicht um vollständiges C, sondern um einen C-ähnlichen Sprachcompiler, der in 512 Byte passt
    Dein Projekt scheint eine Option zu haben, Code für Bootsektoren zu erzeugen.
    Beide sind interessant, aber die Gemeinsamkeiten beschränken sich auf „Bootsektor“, „C“ und „Compiler“
  • Ich kann der Aussage zustimmen, dass „Programmieren damals wirklich Spaß gemacht hat“, aber heute können viel mehr Menschen dasselbe tun
    Deshalb habe ich das Gefühl, nicht mehr besonders zu sein
• Solche Projekte führen einem vor Augen, wie weit sich moderne Entwicklung von der Hardware entfernt hat
  Wir stapeln immer mehr Abstraktionen aufeinander, sodass man für ein einziges „Hello World“ schon 200 MB node_modules braucht
  Und dann packt jemand einen C-Compiler in 512 Byte
  Niemand sagt, dass alle Bootsektor-Code schreiben sollten, aber solche Projekte zu lesen ist wirklich eine demütigende Erfahrung. Der pädagogische Wert ist ebenfalls groß
• Vielleicht bin ich genau der Autor dieses Projekts. Der Bauprozess hat wirklich Spaß gemacht!
  • Wirklich großartig. Ich baue ebenfalls einen minimalistischen C-Compiler, ziele aber nicht auf den Bootsektor, sondern auf ein 8-Bit-System
    Dieses Projekt zeigt gut, wie einfach die Kernstruktur von C ist.
    Interessant ist, dass sich C aus B entwickelt hat und B wiederum aus einer abgespeckten Form von Fortran
  • Ich frage mich, wie viel kleiner es würde, wenn man if, while und for in einfache goto-Routinen umwandelt
    In Assembler gibt es am Ende ja ohnehin nur jmp.
    Und es sollte nicht „choose your own adventure“, sondern „chose your own adventure“ heißen :)
    Ich liebe Minimalismus
  • Dieser Compiler bzw. das Konzept von „barely-C“ könnte sich auch für eine Bootstrap-Kette eignen
    Man beginnt mit einer sehr kleinen plattformspezifischen Binärdatei und arbeitet sich dann zu immer komplexeren Tools und Compilern vor
    Als Beispiele kann man sich die Projekte mishmashvm und tcc_bootstrap_alt ansehen
• Ein wunderschönes Projekt. Allerdings wäre es gut, 2023 schnell im Titel zu ergänzen
  Die damalige Diskussion fand hier statt
  • Danke! Mit der Version inklusive Makroerweiterung könnte man es etwa so zusammenfassen:
    SectorC: A C Compiler in 512 bytes - Link - Mai 2023 (80 Kommentare)
• Im Vergleich zu dem gestern auf HN geposteten Claude-Projekt, bei dem in zwei Wochen für 20.000 Dollar ein 100.000-Zeilen-C-Compiler gebaut wurde, ist das ein interessanter Kontrast
  • Ein interessanter Vergleich, aber dort kann man den Linux-Kernel kompilieren und Code für mehrere Architekturen erzeugen
    Dieses Projekt hier kann dagegen nur einen Teil von C verarbeiten
    Es ist also eher ein Compiler für eine Teilmenge von C als ein vollständiger C-Compiler.
    Code, den dieser Compiler kompilieren kann, lässt sich auch mit einem echten C-Compiler kompilieren, aber nicht umgekehrt
• Die Verwendung von Token-Hashing zum Aufbau einer Pseudo-Symboltabelle ist wirklich elegant
  • Ich habe früher beim Bauen eines Parsers für ein Testwerkzeug ebenfalls nur Symbol-Hashwerte zur Identifikation von Bezeichnern verwendet
    Hoffentlich habe ich damals nicht genug Symbole benutzt, um 32-Bit-Kollisionen zu erzeugen
  • Sehe ich genauso. Der Trick mit dem Token-Hashing ist wirklich cool
    Übrigens sind im Bereich 0x01e0~0x01fd noch 21 Byte freier Platz übrig. Vielleicht passt da noch etwas hinein ;)
• Der Teil, in dem steht, dass atoi() auf normalem Text wie eine schlechte Hash-Funktion arbeitet, ist interessant
  Aber soweit ich mich erinnere, war atoi() so definiert, dass es bei ungültiger Eingabe 0 zurückgibt
• Das Interesse an Compilern für Bootsektoren scheint ziemlich groß zu sein
  Beim Ausführen unter Linux muss man im qemu-Aufruf statt coreaudio einfach alsa verwenden
  Ich habe dazu einen Pull Request auf GitHub eingereicht. Wenn dem Autor mein ausschweifender Shellskript-Stil gefällt, wird er vielleicht gemergt
• Wirklich ein toller Artikel! Er hat mich an das Bootsektor-OS erinnert, das ich früher gebaut habe
  Jetzt scheint es Zeit zu sein, dort einen C-Compiler hinzuzufügen
  Link zu meinem OS-Projekt