SectorC: A C Compiler in 512 bytes

I saw the repeating &#x27;A&#x27; at the end of the base64 text and thought &quot;it&#x27;s not even 512 bytes; it&#x27;s smaller!&quot;<p>That said, the title is just a little clickbaity --- it&#x27;s a C-subset compiler, and more accurately a JIT interpreter. There also appears to be no attempt at operator precedence. Nonetheless, it&#x27;s still an impressive technical achievement and shows the value of questioning common assumptions.<p>Finally, I feel tempted to offer a small size optimisation:<p><pre><code> sub ax,2 </code></pre> is 3 bytes whereas<p><pre><code> dec ax dec ax </code></pre> is 2 bytes.<p>You may be able to use single-byte xchg&#x27;s with ax instead of movs, and the other thing which helps code density a lot in 16-bit code is to take advantage of the addressing modes and LEA to do 3-operand add immediates where possible.

This reminded me the idea of compilers bootstrapping (<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=35714194" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=35714194</a>). That is, now you can code in SectorC some slightly more advanced version of C capable of compiling TCC (<a href="https:&#x2F;&#x2F;bellard.org&#x2F;tcc&#x2F;" rel="nofollow">https:&#x2F;&#x2F;bellard.org&#x2F;tcc&#x2F;</a>), and then with TCC you can go forward to GCC and so on.

Now they just need to port something like oneKpaq to 16 bit or maybe something from the <i>extremely tiny decompressor</i> thread [1], just to test compression level to get an idea kpaq on its quickest setting(taking minutes instead of what could be days on its highest) reduced SectorC to 82.81% of its size, of course adding the 128 bit stub knocked it to 677 bytes. It would be interesting to try it on the slowest takes day to bruteforce setting, but I&#x27;m not going to attempt that.<p>Some of the compressors in that forum thread since they are 32 bytes and such, might find it easier to get net gains.<p>[0] <a href="https:&#x2F;&#x2F;github.com&#x2F;temisu&#x2F;oneKpaq">https:&#x2F;&#x2F;github.com&#x2F;temisu&#x2F;oneKpaq</a><p>[1] <a href="https:&#x2F;&#x2F;encode.su&#x2F;threads&#x2F;3387-(Extremely)-tiny-decompressors" rel="nofollow">https:&#x2F;&#x2F;encode.su&#x2F;threads&#x2F;3387-(Extremely)-tiny-decompressor...</a>

This is fascinating, I really did not think it was possible to implement even a tiny subset of C in just 512 bytes of x86 code. Using atoi() as a generic hash function is a brilliantly awful hack!

wow, this is impressive.<p>I wrote a similar x86-16 assembler in &lt; 512 B of x86-16 assembly, and this seems much more difficult &lt;<a href="https:&#x2F;&#x2F;github.com&#x2F;kvakil&#x2F;0asm&#x2F;">https:&#x2F;&#x2F;github.com&#x2F;kvakil&#x2F;0asm&#x2F;</a>&gt;. I did find a lot of similar tricks were helpful: using gadgets and hashes. Once trick I don&#x27;t see in sectorc which shaved quite a bit off of 0asm was self-modifying code, which 0asm uses to &quot;change&quot; to the second-pass of the assembler. (I wrote some other techniques here: &lt;<a href="https:&#x2F;&#x2F;kvakil.me&#x2F;posts&#x2F;asmkoan.html" rel="nofollow">https:&#x2F;&#x2F;kvakil.me&#x2F;posts&#x2F;asmkoan.html</a>&gt;.)<p>bootOS (&lt;<a href="https:&#x2F;&#x2F;github.com&#x2F;nanochess&#x2F;bootOS">https:&#x2F;&#x2F;github.com&#x2F;nanochess&#x2F;bootOS</a>&gt;) and other tools by the author are also amazing works of assembly golf.

Pretty nifty, nice work!<p>I&#x27;ll point out to any passerby that this C doesn&#x27;t support structs, so it&#x27;s unlikely you&#x27;d actually want to build anything in it.

Amazing!<p>I think this, from the conclusion, is the real takeaway:<p>&gt; Things that seem impossible often aren’t and we should Just Do It anyway<p>I certainly would never have tried to get a C compiler (even a subset) so small since it my instinct would have been that it was not possible.

See the bootstrap project: <a href="https:&#x2F;&#x2F;bootstrappable.org&#x2F;projects.html" rel="nofollow">https:&#x2F;&#x2F;bootstrappable.org&#x2F;projects.html</a>

I&#x27;m wondering if you can build an actual &quot;Linux from scratch&quot; with this as the lowest level, without the need to use a host system at all.

I started reading the source... and digging for the part that allocates space for variables.... only to realize variable declarations are ignored and unnecessary... wow... what a <i>breathlessly reckless</i> hack! I love it!<p>It&#x27;s like using an M18A1 Claymore mine and hoping it actually is aimed (and stays aimed) in the right direction.

The conclusion table was resume building skill in and of itself.

&gt; I will call it the Barely C Programming Language<p>Or BCPL, for short.<p>&gt; The C programming language was devised in the early 1970s as a system implementation language for the nascent Unix operating system. Derived from the typeless language BCPL, it evolved a type structure; created on a tiny machine as a tool to improve a meager programming environment, it has become one of the dominant languages of today. This paper studies its evolution. [1]<p>[1] <a href="https:&#x2F;&#x2F;www.bell-labs.com&#x2F;usr&#x2F;dmr&#x2F;www&#x2F;chist.html" rel="nofollow">https:&#x2F;&#x2F;www.bell-labs.com&#x2F;usr&#x2F;dmr&#x2F;www&#x2F;chist.html</a>

Reminds of the META II Metacompiler <a href="http:&#x2F;&#x2F;hcs64.com&#x2F;files&#x2F;pd1-3-schorre.pdf" rel="nofollow">http:&#x2F;&#x2F;hcs64.com&#x2F;files&#x2F;pd1-3-schorre.pdf</a>

Great writeup!<p>Especially liked this nugget:<p>&gt; (NOTE: This grammar is 704 bytes in ascii, 38% larger than it&#x27;s implementation!)

That is insane, congrats.<p>I would have wished some explanation on where the function calls like vga_init and vga_set_pixel come from, I&#x27;m not a graybeard yet.

something like this could be interesting for deep-space applications where you only have a bare metal environment with hardened processor and limited memory &amp; of course ping time of days (to earth).<p>or alternatively for embedding a C compiler inside a LLM to use the LLM as a form of virtual machine.

really interesting write-up. thanks for sharing!<p>do you think there are any lessons that can be applied to a &quot;normal&quot; interpreter&#x2F;compiler written in standard C? i&#x27;m always interested in learning how to reduce the size of my interpreter binaries

Great read and awesome achievement. Could see this being useful for smaller microcontrollers.

It was funny to read. Thx! :))

If you don&#x27;t use this... are you even suckless?

Bravo! This was a wonderful read, xorvoid.

Amazing.