SectorC, un compilador de C hecho en 512 bytes

• SectorC, escrito en ensamblador x86-16, es un compilador de C ultracompacto que cabe dentro del sector de arranque (512 bytes) de una máquina x86, y soporta un subconjunto del lenguaje C suficiente para escribir programas realmente funcionales
• Incluye variables globales, funciones, sentencias if/while, operadores, desreferenciación de punteros, comentarios y ensamblador en línea, lo que permite ejecutar programas completos incluso con una estructura mínima
• Para simplificar el tokenizador, se diseñó el lenguaje Barely C con tokenización basada en espacios y un hash usando atoi(), logrando una reducción extrema de tamaño mientras mantiene la sintaxis existente de C
• En el proceso de optimización del código se aplicaron varias técnicas de compresión a nivel de ensamblador, como eliminación de saltos, fusión de llamadas, uso de offsets de 8 bits y uso de stosw/lodsw, reduciendo el tamaño de 468 bytes a 303 bytes
• Como resultado, se implementó dentro de 512 bytes un compilador de C completo que incluye tokenizador, parser, generador de código y runtime, mostrando un caso extremo de minimización de software

---

Resumen de SectorC

• SectorC es un compilador de C escrito en ensamblador x86-16 que cabe por completo dentro de un sector de arranque de 512 bytes
  • El repositorio en GitHub está en xorvoid/sectorc
  • El lenguaje que soporta es un subconjunto de C con capacidad real para escribir programas
• Entre las funciones soportadas se incluyen variables globales, funciones, estructuras de control (if/while), varios operadores, desreferenciación de punteros, ensamblador en línea y comentarios
• Como programa de ejemplo se muestra código que dibuja una animación de onda sinusoidal en modo VGA

Contexto de diseño y enfoque

• Como un tokenizador de C convencional es demasiado grande para caber en 512 bytes, fue necesario simplificar la propia estructura del lenguaje
• Gran idea #1: se adoptó una estructura de tokens separados por espacios al estilo de Forth para diseñar una variante del lenguaje llamada “Barely C”
  • Ejemplo: una sintaxis como int(main)(){while(!done){ se trata como un solo “mega token”
  • Sigue siendo reconocida como código C válido incluso por compiladores de C existentes
• Gran idea #2: la función atoi() se usa como si fuera una función hash para convertir tokens en números
  • Literales enteros, palabras clave e identificadores se procesan todos a partir del valor devuelto por atoi()
  • Se accede a los identificadores como índices dentro de un arreglo de 64K

Implementación de Barely C

• La primera implementación tenía 468 bytes y usaba una estructura de parser recursivo descendente con tokens basados en atoi
  • Sin tabla de símbolos: se accede directamente al segmento de 64K usando el valor hash
  • La generación de código sigue el estilo OTCC, usando el registro ax como almacenamiento del resultado
• Después se probó con byte-threaded code para intentar una estructura tipo Forth, pero dentro del límite de 512 bytes resultó menos eficiente y fue descartada

Técnicas de minimización de código

• Al volver a una estructura lineal, el tamaño se redujo de 468 bytes → 303 bytes
  • Se usaron técnicas como eliminación de saltos (fall-through), tail-call, fusión de llamadas (call fusion), uso de stosw/lodsw y mantenimiento de offsets de salto de 8 bits
• Esto permitió asegurar 207 bytes de espacio libre para implementar más funciones

Expansión a funciones completas de C

• Con 200 bytes adicionales se logró soporte para una sintaxis de C más completa
  • Bloques if/while anidados, varios operadores binarios (+, -, *, &, |, ^, <<, >>, ==, !=, <, >, <=, >=)
  • Soporte para definición de funciones y llamadas recursivas, ensamblador en línea (asm) y comentarios de una línea y multilínea
  • Mediante una tabla de operadores (binary_oper_tbl), cada operador se define en 4 bytes y se manejan 14 operadores en 56 bytes

Estructura de la gramática

• La gramática completa está compuesta por program, var_decl, func_decl, statement, expr y otros elementos
• Soporta tanto comentarios // como /* */
• El propio texto de definición de la gramática ocupa 704 bytes, más que la implementación real

Ensamblador en línea y runtime

• La sintaxis asm permite insertar directamente código máquina x86-16
  • Es una función esencial para el manejo de E/S
• El runtime (rt/) está compuesto por dos archivos escritos en C
  • rt/lib.c: rutinas de biblioteca basadas en ensamblador en línea
  • rt/_start.c: punto de entrada del programa _start()

Programas de ejemplo

• examples/hello.c: imprime texto directamente en la memoria 0xB8000
• examples/sinwave.c: muestra una animación de onda sinusoidal en el modo VGA 0x13
• examples/twinkle.c: reproduce “Twinkle Twinkle Little Star” con el altavoz de la PC (incluye advertencia por sonido)

Conclusión

• SectorC es un compilador de C diminuto que hace realidad una meta que parecía imposible, y muestra un caso extremo de minimización de software y diseño creativo de lenguajes
• El texto termina con opciones humorísticas de “qué aprendimos”, subrayando de forma satírica la actitud de desafiar lo imposible y el valor de simplificar el software

[GN⁺]

Comentarios de Hacker News

• Si una implementación como esta hubiera existido en los años 80, parece que el estándar de C habría terminado con una regla diciendo que, si distintos tokens provocan una colisión de hash con el mismo valor de 16 bits, eso causa comportamiento indefinido (UB).
  Puede que los compiladores optimizadores de los 2000 simplemente hubieran optimizado esos tokens como no-op 😉
  • "¡No activaste la opción -wTokenHashCollision! El UB ocurrió por tu ignorancia. ¡La especificación es perfectamente clara!", dejó alguien en tono de broma.
  • Me dio risa de lo realista que suena. LMAO.
• Se parece a un compilador de C para boot sector X86-16 que hice recientemente.
  Hacer juegos de boot sector es una experiencia mágica que de verdad despierta la nostalgia. Me recuerda cuando programar era realmente divertido.
  Da pena que en esta era de la IA proyectos así estén tan subestimados.
  Link a mi proyecto
  • Mmm, lo que trata el artículo no es C completo, sino un compilador de un lenguaje tipo C que cabe en 512 bytes.
    Tu proyecto parece tener una opción para generar código para boot sector.
    Ambos son interesantes, pero lo único que comparten es algo como "boot sector", "C" y "compiler".
  • Coincido con eso de "cuando programar era realmente divertido", pero ahora más gente puede hacer lo mismo.
    Así que ya no siento que yo sea especial.
• Proyectos así te recuerdan qué tan lejos del hardware se ha ido el desarrollo moderno.
  Seguimos apilando abstracciones hasta el punto de necesitar 200 MB de node_modules solo para correr un "Hello World".
  Mientras tanto, alguien mete un compilador de C en 512 bytes.
  No es que todo el mundo deba escribir código para boot sector, pero leer proyectos así de verdad es una experiencia humillante. También tiene mucho valor educativo.
• Puede que yo sea justamente el autor de este proyecto. ¡Fue muy divertido hacerlo!
  • Está increíble. Yo también estoy haciendo un compilador de C minimalista, aunque no para que quepa en un boot sector sino apuntando a un sistema de 8 bits.
    Este proyecto muestra muy bien lo simple que puede ser la estructura central de C.
    Es interesante que C haya evolucionado a partir de B, y B de una versión reducida de Fortran.
  • Me pregunto cuánto más pequeño quedaría si if, while y for se transformaran en simples rutinas con goto.
    Al final en ensamblador solo existe jmp.
    Y debería decir "chose your own adventure", no "choose your own adventure" :)
    Me encanta el minimalismo.
  • Este compilador, o la idea de "barely-C", también podría usarse en una cadena de bootstrap.
    Algo como empezar desde un binario diminuto específico para una plataforma e ir construyendo herramientas y compiladores cada vez más complejos.
    Como ejemplo, se pueden ver los proyectos mishmashvm y tcc_bootstrap_alt.
• Es un proyecto hermoso. Solo que sería bueno agregar 2023 al título cuanto antes.
  La discusión de ese momento estuvo aquí.
  • ¡Gracias! Con la versión expandida con macros, podría organizarse como
    SectorC: A C Compiler in 512 bytes - link - mayo de 2023 (80 comentarios).
• Es interesante compararlo con el compilador de C de 100 mil líneas que Claude hizo en 2 semanas por 20 mil dólares y que apareció ayer en HN.
  • Es una comparación divertida, pero ese sí puede compilar el kernel de Linux y generar código para varias arquitecturas.
    En cambio, este proyecto solo puede manejar una parte de C.
    O sea, más que un compilador de C completo, esto es un compilador que maneja un subconjunto de C.
    El código que este compilador puede compilar también puede compilarse con un compilador de C real, pero no al revés.
• La forma de crear una pseudo tabla de símbolos usando hash de tokens es realmente elegante.
  • Yo también, hace tiempo, al hacer un parser para una herramienta de testing, llegué a manejar los identificadores solo con el valor hash de los símbolos.
    Espero no haber usado tantos símbolos como para provocar una colisión de 32 bits.
  • Pienso lo mismo. El truco de hacer hash de los tokens está buenísimo.
    Como referencia, todavía quedan 21 bytes de espacio libre entre 0x01e0 y 0x01fd. Puede que todavía se le pueda meter algo más ;)
• Me pareció interesante la parte de que "atoi() funciona como una mala función hash para texto normal".
  Pero según recuerdo, atoi() estaba definido para devolver 0 cuando la entrada no es válida.
• Hay bastante interés en compiladores para boot sector.
  Al ejecutarlo en Linux, basta con cambiar la llamada a qemu de coreaudio a alsa.
  Subí un pull request a GitHub para eso. Si al autor le parece bien mi estilo verboso de scripts de shell, quizá lo mergee.
• ¡Fue un artículo realmente genial! Me recordó al OS de boot sector que hice hace tiempo.
  Parece que ya es hora de intentar agregarle un compilador de C.
  Link a mi proyecto de OS