SectorC, kompiler C yang dibuat dalam 512 byte

• SectorC yang ditulis dalam assembly x86-16 adalah kompiler C superkecil yang muat di dalam boot sector (512 byte) pada mesin x86, dan mendukung subset bahasa C yang cukup untuk menulis program yang benar-benar bisa dijalankan
• Mencakup variabel global, fungsi, pernyataan if/while, operator, dereferensi pointer, komentar, assembly inline, sehingga program lengkap tetap bisa dijalankan dengan struktur seminimal mungkin
• Untuk menyederhanakan tokenizer, dirancang bahasa Barely C dengan tokenisasi berbasis spasi dan hash atoi(), sehingga tetap mempertahankan sintaks C yang ada sambil mencapai penghematan ukuran yang ekstrem
• Dalam proses optimasi kode, diterapkan berbagai teknik kompresi level assembly seperti penghapusan jump, penggabungan call, pemanfaatan offset 8-bit, penggunaan stosw/lodsw, sehingga ukuran diperkecil dari 468 byte menjadi 303 byte
• Hasilnya, sebuah kompiler C lengkap yang mencakup tokenizer, parser, code generator, runtime berhasil diimplementasikan seluruhnya dalam 512 byte, memperlihatkan contoh ekstrem minimisasi perangkat lunak

---

Gambaran umum SectorC

• SectorC adalah kompiler C yang ditulis dalam assembly x86-16 dan sepenuhnya muat di dalam boot sector 512 byte
  • Repositori GitHub: xorvoid/sectorc
  • Bahasa yang didukung adalah subset C pada tingkat yang cukup untuk menulis program nyata
• Fitur yang didukung mencakup variabel global, fungsi, kontrol alur (if/while), berbagai operator, dereferensi pointer, assembly inline, komentar
• Sebagai contoh program, ditunjukkan kode yang menggambar animasi gelombang sinus dalam mode VGA

Latar belakang desain dan pendekatan

• Karena tokenizer C konvensional terlalu besar untuk dimuat dalam 512 byte, struktur bahasanya sendiri harus disederhanakan
• Big Insight #1: Seperti bahasa Forth, diperkenalkan struktur token yang dipisahkan dengan spasi untuk merancang varian bahasa bernama “Barely C”
  • Contoh: sintaks seperti int(main)(){while(!done){ diproses sebagai satu “mega token”
  • Tetap dikenali sebagai kode C yang valid oleh kompiler C yang ada
• Big Insight #2: Fungsi atoi() digunakan seperti fungsi hash untuk mengubah token menjadi angka
  • Literal integer, keyword, dan identifier semuanya diproses berdasarkan nilai hasil atoi()
  • Identifier diakses sebagai indeks dalam array 64K

Implementasi Barely C

• Implementasi pertama berukuran 468 byte, menggunakan struktur parser recursive descent berbasis token atoi
  • Tanpa symbol table, segmen 64K diakses langsung menggunakan nilai hash
  • Code generation mengikuti gaya OTCC dengan register ax sebagai tempat penyimpanan hasil
• Setelah itu sempat dicoba pendekatan byte-threaded code untuk meniru struktur ala Forth, tetapi dalam batas 512 byte justru tidak efisien dan akhirnya dibuang

Teknik minimisasi kode

• Kembali ke struktur linear dan ukuran diperkecil dari 468 byte → 303 byte
  • Menggunakan teknik seperti penghapusan jump (fall-through), tail-call, call fusion, pemanfaatan stosw/lodsw, serta mempertahankan jump offset 8-bit
• Ini menghasilkan ruang kosong 207 byte untuk menambahkan fitur lain

Ekspansi ke fitur C yang lengkap

• Dengan tambahan 200 byte, berhasil dicapai dukungan sintaks C yang lengkap
  • Blok if/while bertingkat, berbagai operator biner (+, -, *, &, |, ^, <<, >>, ==, !=, <, >, <=, >=)
  • Dukungan definisi fungsi dan pemanggilan rekursif, assembly inline (asm), komentar satu baris/multibaris
  • Melalui tabel operator (binary_oper_tbl), setiap operator didefinisikan dalam 4 byte, sehingga 14 operator dapat ditangani dalam 56 byte

Struktur tata bahasa

• Seluruh tata bahasa terdiri dari program, var_decl, func_decl, statement, expr, dan lain-lain
• Mendukung komentar // maupun /* */
• Teks definisi grammar itu sendiri berukuran 704 byte, lebih besar daripada implementasi nyatanya

Assembly inline dan runtime

• Melalui pernyataan asm, machine code x86-16 dapat disisipkan langsung
  • Ini merupakan fitur penting untuk menangani I/O
• Runtime (rt/) terdiri dari dua file yang ditulis dalam C
  • rt/lib.c: routine library berbasis assembly inline
  • rt/_start.c: entry point program _start()

Program contoh

• examples/hello.c: menampilkan teks langsung ke memori 0xB8000
• examples/sinwave.c: menampilkan animasi gelombang sinus dalam mode VGA 0x13
• examples/twinkle.c: memainkan “Twinkle Twinkle Little Star” lewat PC speaker (dengan peringatan suara)

Kesimpulan

• SectorC adalah kompiler C ultrakecil yang mewujudkan target yang tampak mustahil, dan memperlihatkan contoh ekstrem minimisasi perangkat lunak serta desain bahasa yang kreatif
• Penutup artikelnya diakhiri dengan pilihan “apa yang dipelajari” yang bernada humor, yang secara satir menekankan sikap menantang hal yang tampak mustahil dan nilai penyederhanaan perangkat lunak

[GN⁺]

Opini Hacker News

• Kalau implementasi seperti ini sudah ada pada tahun 1980-an, mungkin standar C akan punya aturan bahwa jika token yang berbeda menimbulkan hash collision pada nilai 16-bit yang sama, maka itu memicu undefined behavior (UB)
  Compiler pengoptimalan era 2000-an mungkin juga akan langsung mengoptimalkan token-token itu menjadi no-op 😉
  • "Kamu kan tidak mengaktifkan opsi -wTokenHashCollision! UB terjadi karena ketidaktahuanmu. Spesifikasinya sudah sangat jelas!" tulis seseorang dengan nada bercanda
  • Terlalu realistis sampai bikin ngakak. LMAO
• Ini terlihat mirip dengan compiler C boot sector X86-16 yang baru-baru ini saya buat
  Membuat game boot sector benar-benar pengalaman magis yang membangkitkan nostalgia. Jadi teringat masa saat pemrograman benar-benar menyenangkan
  Di era AI sekarang, rasanya proyek seperti ini terlalu diremehkan
  Tautan proyek saya
  • Hmm, yang dibahas di tulisan ini bukan C penuh, melainkan compiler bahasa mirip C yang muat dalam 512 byte
    Proyekmu tampaknya punya opsi untuk menghasilkan kode untuk boot sector.
    Keduanya sama-sama menarik, tetapi kesamaannya paling hanya pada 'boot sector', 'C', dan 'compiler'
  • Saya setuju dengan kalimat "masa saat pemrograman benar-benar menyenangkan", tetapi sekarang lebih banyak orang bisa melakukan hal yang sama
    Jadi rasanya saya tidak istimewa lagi
• Proyek seperti ini mengingatkan betapa jauh pengembangan modern sudah menjauh dari hardware
  Kita terus menumpuk abstraksi sampai untuk menjalankan "Hello World" saja butuh 200MB node_modules
  Sementara itu, ada orang yang memasukkan compiler C ke dalam 512 byte
  Bukan berarti semua orang harus menulis kode boot sector, tetapi membaca proyek seperti ini benar-benar merendahkan ego. Nilai edukasinya juga besar
• Mungkin saya adalah pembuat proyek ini. Proses membuatnya benar-benar menyenangkan!
  • Keren sekali. Saya juga sedang membuat compiler C minimalis, tetapi bukan untuk boot sector melainkan menargetkan sistem 8-bit
    Proyek ini menunjukkan dengan baik betapa sederhananya struktur inti C.
    Menarik bahwa C berkembang dari bahasa B, dan B sendiri berkembang dari versi ringkas Fortran
  • Saya penasaran seberapa jauh ukurannya bisa diperkecil jika if, while, dan for diubah menjadi rutin goto sederhana
    Pada akhirnya assembly memang cuma punya jmp.
    Dan seharusnya "chose your own adventure", bukan "choose your own adventure" :)
    Saya suka minimalisme
  • Compiler ini atau konsep 'barely-C' tampaknya juga bisa dipakai dalam rantai bootstrap
    Dimulai dari biner sangat kecil yang spesifik untuk platform tertentu, lalu secara bertahap membuat alat dan compiler yang semakin kompleks
    Sebagai contoh, lihat proyek mishmashvm dan tcc_bootstrap_alt
• Proyek yang indah. Hanya saja, sebaiknya tambahkan 2023 ke judul secepatnya
  Diskusi waktu itu ada di sini
  • Terima kasih! Untuk versi dengan perluasan makro, ini bisa diringkas menjadi
    SectorC: A C Compiler in 512 bytes - tautan - Mei 2023 (80 komentar)
• Menarik membandingkannya dengan compiler C 100 ribu baris yang dibuat Claude kemarin di HN, dengan biaya 20 ribu dolar dalam 2 minggu
  • Perbandingan yang seru, tetapi yang itu bisa mengompilasi kernel Linux dan menghasilkan kode untuk berbagai arsitektur
    Sementara proyek ini hanya bisa menangani sebagian C
    Jadi ini lebih tepat disebut compiler untuk subset C daripada compiler C penuh.
    Kode yang bisa dikompilasi oleh compiler ini juga bisa dikompilasi oleh compiler C sungguhan, tetapi tidak sebaliknya
• Cara membuat pseudo symbol table memakai token hashing benar-benar elegan
  • Saya juga pernah mengelola identifier hanya dengan nilai hash simbol saat membuat parser untuk alat pengujian
    Untungnya saya tidak memakai cukup banyak simbol sampai tabrakan 32-bit benar-benar terjadi
  • Saya juga berpikir begitu. Trik token hashing ini benar-benar keren
    Sebagai catatan, masih ada ruang kosong 21 byte yang tersisa di antara 0x01e0~0x01fd. Mungkin masih bisa ditambah sesuatu ;)
• Bagian yang mengatakan "atoi() bertindak seperti fungsi hash yang buruk untuk teks biasa" itu menarik
  Tetapi kalau saya ingat dengan benar, atoi() memang didefinisikan untuk mengembalikan 0 pada input yang tidak valid
• Ada cukup banyak minat terhadap compiler untuk boot sector
  Saat dijalankan di Linux, pemanggilan qemu tinggal diubah dari coreaudio menjadi alsa
  Saya sudah mengirim pull request untuk itu ke GitHub. Kalau penulisnya tidak keberatan dengan gaya skrip shell saya yang verbose, mungkin akan di-merge
• Tulisannya benar-benar keren! Jadi teringat OS boot sector yang dulu pernah saya buat
  Sepertinya sekarang saatnya menambahkan compiler C ke sana
  Tautan proyek OS saya