SectorC: A C Compiler in 512 bytes (2023) (opens in new tab)

(xorvoid.com)

381 pointsvalyala1mo ago79 comments

79 comments

If this implementation had existed in the 1980s, the C standard would have a rule that different tokens hashing to the same 16-bit value invoke undefined behavior, and optimizing compilers in the 2000s would simply optimize such tokens away to a no-op. ;)

RodgerTheGreat1mo ago

"you don't have -wTokenHashCollision enabled! it's your own foolish ignorance that triggered UB; the spec is perfectly clear!"

fredrikholm1mo ago

Hey stop it with the ad hominems!

xorvoid1mo ago

Too real! LMAO

mati3651mo ago

Oh, it looks like my X86-16 boot sector C compiler that I made recently [1]. Writing boot sector games has a nostalgic magic to it, when programming was actually fun and showed off your skills. It's a shame that the AI era has terribly devalued these projects.

[1] https://github.com/Mati365/ts-c-compiler

guenthert1mo ago

Er, what? The article describes a compiler for a not-quite-C programming language which fits entirely in 512B. Your project, if I see this correctly, can optionally produce code meant to execute as boot sector.

Both interesting projects, but other than the words 'boot sector', 'C' and 'compiler', I don't see a similarity.

w4yai1mo ago

> when programming was actually fun and showed off your skills

Oh no. Now more people are able to do what I do. I'm not special anymore.

mlsu1mo ago

Seems like this is facetious but to me, “I’m not special” is a pretty valid thing to be sad about.

tgv1mo ago

The two dos in "do what I do" do absolutely not carry the same meaning.

xorvoid1mo ago

I may be the author.. enjoy! It was an absolute blast making this!

einpoklum1mo ago

An interesting use case - for the compiler as-is or for the essentiall idea of barely-C - might be in bootstrapping chains, i.e. starting from tiny platform-specific binaries one could verify the disassembly of, and gradually building more complex tools, interpreters, and compiler, so that eventually you get to something like a version of GCC and can then build an entire OS distribution.

Examples:

https://github.com/cosinusoidally/mishmashvm/

and https://github.com/cosinusoidally/tcc_bootstrap_alt/

ahazred8ta1mo ago

Related: the stage0/stage1 series of hex-to-c compiler bootstrapping tools https://github.com/oriansj/stage0?tab=readme-ov-file and OTCC https://bellard.org/otcc/

tekknolagi1mo ago

You may enjoy https://github.com/ludocode/onramp

teo_zero1mo ago

It would be interesting to understand what non-toy programs can be coded in this subset of C. For example, could tcc be rewritten in this dialect?

direwolf201mo ago

https://bootstrapping.miraheze.org/wiki/Main_Page

(Why does the referenced short story remind me of "There Is No Antimemetics Division"?)

veltas1mo ago

This is very nice. I'm currently writing a minimalist C compiler although my goal isn't fitting in a boot sector, it's more targeted at 8-bit systems with a lot more room than that.

This is a great demonstration of how simple the bare bones of C are, which I think is one reason I and many others find it so appealing despite how Spartan it is. C really evolved from B which was a demake of Fortran, if Ken Thompson is to be trusted.

JamesTRexx1mo ago

Would and how much would it shrink when if, while, and for were replaced by the simple goto routine? (after all, in assembly there is only jmp and no other fancy jump instruction (I assume) ).

And PS, it's "chose your own adventure". :-) I love minimalism.

SAI_Peregrinus1mo ago

What fancy jumps are present in assembly depends on the CPU architecture. But there are always conditional jumps, like JNZ that jumps if the Zero flag isn't set.

MobiusHorizons1mo ago

The “fancy jump” is the branch instruction. As far as I know all ISAs have them. Even rv32i which is famously minimal has several branch instructions in addition to two forms of unconditional jump. Branches are typically used to construct if / for / while as well as && and || (because of short circuiting) and ternary (although some architectures may have special instructions for that that may or may not be faster than branches depending on the exact model). Without it you would have to use computed goto with a destination address computed without conditional execution using constant time techniques.

dzaima1mo ago

It only does if & while, not for. A goto in a single-pass thing would need separate handling for forwards vs backwards jumps, which involves keeping track of data per name (in a form where you can tell when it's not yet set; whereas if/while data is freely held in recursion stack). And you'd still need to handle at least `if ( expr ) goto foo;` to do any conditionals at all.

direwolf201mo ago

It's "choose your own adventure"

1 more reply

riedel1mo ago

Beautiful, but make sure to quickly add 2023 to the title.

Discussed at the time: https://news.ycombinator.com/item?id=36064971

dang1mo ago

Thanks! Macroexpanded:

SectorC: A C Compiler in 512 bytes - https://news.ycombinator.com/item?id=36064971 - May 2023 (80 comments)

gjvc1mo ago

why? and why "quickly?

wzbtoolbox1mo ago

This is the kind of project that reminds you how far removed modern development is from the actual machine. We pile abstractions on abstractions until "Hello World" needs 200MB of node_modules, and then someone fits a C compiler in 512 bytes.

Not saying we should all write boot sector code, but reading through projects like this is genuinely humbling. Great educational resource too.

lock11mo ago

This kind of comment reminds me of how broad "software development" is.

On other HN posts, they're stating something like "software development is dead", "LLM as a compiler", "Do you read compiled assembly?", and so on.

While some other posts like this contain huge mechanical sympathy and literally r/w the assembly directly.

mojuba1mo ago

Compare that to the C compiler in 100,000 lines written by Claude in two weeks for $20,000 (I think was posted on HN just yesterday)

vidarh1mo ago

It's a fun comparison, but with the notable difference that that one can compile the Linux kernel and generate code for multiple different architectures, while this one can only compile a small proportion of valid C. It's a great project, but it's not so much a C compiler, as a compiler for a subset of C that allows all programs this compiler can compile to also be compiled by an actual C compiler, but not vice versa.

d_silin1mo ago

But can it compile "Hello, World" example from its own README.md?

https://github.com/anthropics/claudes-c-compiler/issues/1

2 more replies

mojuba1mo ago

Well I'm pretty sure the author can make a compliant C compiler in a few more sectors.

1 more reply

sanufar1mo ago

The way hashing is used for tokens and for making a pseudo symbol table is such an elegant idea.

fix4fun1mo ago

I think the same. Really nice project and good trick with hashing tokens.

PS. There left 21 bytes (21 * 0x00 - from 0x01e0 to 0x01fd). Maybe something can be packed there ;)

avadodin1mo ago

I actually "shipped" a parser using the symbols' hash(as the only identifier) for a test tool once. Hopefully, the users never used enough symbols to collide 32-bits.

benj1111mo ago

I've had the idea before. Was never quite brave enough to do it. It's elegant until it isn't....

shikaan1mo ago

Such a great read! Reminds me of the bootsector OS I made some time ago[^1]

Maybe it's time to equip it with a C compiler...

[1]: https://github.com/shikaan/osle

fooker1mo ago

This is so cool!

Fun fact, Tiny C Compiler was derived from such a C compiler submitted to the the International Obfuscated C Code Contest.

https://www.ioccc.org/2001/bellard/index.html

xorvoid1mo ago

Further Fun fact, that submission was called OTCC. I reverse engineered it and that provided inspiration for SectorC.

https://xorvoid.com/otcc_deobfuscated.html https://github.com/xorvoid/otcc_deobfuscated

pseudohadamard1mo ago

Meh, I did an entire awk interpreter in two lines:

  #!/bin/sh
  echo "awk: bailing out" >&2

DeathArrow1mo ago

For me is not interesting because it fits in 512 bytes, it's interesting because it's very simple. I think it would be a great introduction to learning about compilers.

EGreg1mo ago

Reminds me of Allegro SizeHack where we made games in 10KB - but we were using C and Allegro library!

https://www.oocities.org/trentgamblin/sizehack/entries.html#...

kreelman1mo ago

There seems to be a good amount of interest for a boot sector compiler!!

If you're running on Linux, adjust the qemu call to use alsa rather than coreaudio.

I generated a pull request for this on Github. If the author is happy enough with my verbose shell scripting style :-) it might get included.

userbinator1mo ago

C-subset, to be precise; but microcomputer C compilers were in the tens of KB range, for one that can actually compile real C.

drob5181mo ago

Brilliant! I love the stealing of Forth ideas to power this. Forth’s minimalism is highly underrated.

zahlman1mo ago

> Big Insight #2 is that atoi() behaves as a (bad) hash function on ordinary text. It consumes characters and updates a 16-bit integer.

I could have sworn I remembered atoi() being defined to return 0 for invalid input (i.e. text not representing an integer in base ten).

MobiusHorizons1mo ago

That would be true of one using a libc, but in a boot sector, you only have the bios, so the atoi being referenced is the one defined in c near the beginning of the article

zahlman1mo ago

Ah, I somehow skipped over that exact code block on first read.

alittlebee1mo ago

This is really beautiful (I feel like this sort of project is outsider art), thank you for sharing.

hgs31mo ago

Great read. It would be neat to see a mini operating system under 1 kb of code.

SeanSullivan861mo ago

Why is it called a C Compiler if it's a subset of C?

1 more reply

NooneAtAll31mo ago

> I wrote a fairly straight-forward and minimalist lexer and it took >150 lines of C code

was it supposed to be "<150"?

owalt1mo ago

They're saying the naive implementation was more than 150 lines of C code (300-450 bytes), i.e. too big.

wbsun1mo ago

Nice, now you can dd it to your boot sector and ... Wait, it is 2026, there are 1000 ways of booting and memory mapping on so-called unified ARM architecture @,@

gonzus1mo ago

Lacking support for structs, I think this is too minimalistic to be called "a C compiler".

benj1111mo ago

Weren't structs a fairly late addition to C?

And anyway, isn't that kind of missing the point. 512 bytes isn't much. Your comment is nearly a 5th of that budget.

pilord3141mo ago

you bootstrap it into a library you can include optionally, duh

kayo_202110301mo ago

Nice. Very K&R-ish. Not a bad thing.

j / k navigate · click thread line to collapse

79 comments

layer81mo ago

RodgerTheGreat1mo ago

"you don't have -wTokenHashCollision enabled! it's your own foolish ignorance that triggered UB; the spec is perfectly clear!"

fredrikholm1mo ago

Hey stop it with the ad hominems!

xorvoid1mo ago

Too real! LMAO

mati3651mo ago

[1] https://github.com/Mati365/ts-c-compiler

guenthert1mo ago

Both interesting projects, but other than the words 'boot sector', 'C' and 'compiler', I don't see a similarity.

w4yai1mo ago

> when programming was actually fun and showed off your skills

Oh no. Now more people are able to do what I do. I'm not special anymore.

mlsu1mo ago

Seems like this is facetious but to me, “I’m not special” is a pretty valid thing to be sad about.

tgv1mo ago

The two dos in "do what I do" do absolutely not carry the same meaning.

xorvoid1mo ago

I may be the author.. enjoy! It was an absolute blast making this!

einpoklum1mo ago

Examples:

https://github.com/cosinusoidally/mishmashvm/

and https://github.com/cosinusoidally/tcc_bootstrap_alt/

ahazred8ta1mo ago

Related: the stage0/stage1 series of hex-to-c compiler bootstrapping tools https://github.com/oriansj/stage0?tab=readme-ov-file and OTCC https://bellard.org/otcc/

tekknolagi1mo ago

You may enjoy https://github.com/ludocode/onramp

teo_zero1mo ago

It would be interesting to understand what non-toy programs can be coded in this subset of C. For example, could tcc be rewritten in this dialect?

direwolf201mo ago

https://bootstrapping.miraheze.org/wiki/Main_Page

(Why does the referenced short story remind me of "There Is No Antimemetics Division"?)

veltas1mo ago

This is very nice. I'm currently writing a minimalist C compiler although my goal isn't fitting in a boot sector, it's more targeted at 8-bit systems with a lot more room than that.

JamesTRexx1mo ago

Would and how much would it shrink when if, while, and for were replaced by the simple goto routine? (after all, in assembly there is only jmp and no other fancy jump instruction (I assume) ).

And PS, it's "chose your own adventure". :-) I love minimalism.

SAI_Peregrinus1mo ago

What fancy jumps are present in assembly depends on the CPU architecture. But there are always conditional jumps, like JNZ that jumps if the Zero flag isn't set.

MobiusHorizons1mo ago

dzaima1mo ago

direwolf201mo ago

It's "choose your own adventure"

1 more reply

riedel1mo ago

Beautiful, but make sure to quickly add 2023 to the title.

Discussed at the time: https://news.ycombinator.com/item?id=36064971

dang1mo ago

Thanks! Macroexpanded:

SectorC: A C Compiler in 512 bytes - https://news.ycombinator.com/item?id=36064971 - May 2023 (80 comments)

gjvc1mo ago

why? and why "quickly?

wzbtoolbox1mo ago

Not saying we should all write boot sector code, but reading through projects like this is genuinely humbling. Great educational resource too.

lock11mo ago

This kind of comment reminds me of how broad "software development" is.

On other HN posts, they're stating something like "software development is dead", "LLM as a compiler", "Do you read compiled assembly?", and so on.

While some other posts like this contain huge mechanical sympathy and literally r/w the assembly directly.

mojuba1mo ago

Compare that to the C compiler in 100,000 lines written by Claude in two weeks for $20,000 (I think was posted on HN just yesterday)

vidarh1mo ago

d_silin1mo ago

But can it compile "Hello, World" example from its own README.md?

https://github.com/anthropics/claudes-c-compiler/issues/1

2 more replies

mojuba1mo ago

Well I'm pretty sure the author can make a compliant C compiler in a few more sectors.

1 more reply

sanufar1mo ago

The way hashing is used for tokens and for making a pseudo symbol table is such an elegant idea.

fix4fun1mo ago

I think the same. Really nice project and good trick with hashing tokens.

PS. There left 21 bytes (21 * 0x00 - from 0x01e0 to 0x01fd). Maybe something can be packed there ;)

avadodin1mo ago

I actually "shipped" a parser using the symbols' hash(as the only identifier) for a test tool once. Hopefully, the users never used enough symbols to collide 32-bits.

benj1111mo ago

I've had the idea before. Was never quite brave enough to do it. It's elegant until it isn't....

shikaan1mo ago

Such a great read! Reminds me of the bootsector OS I made some time ago[^1]

Maybe it's time to equip it with a C compiler...

[1]: https://github.com/shikaan/osle

fooker1mo ago

This is so cool!

Fun fact, Tiny C Compiler was derived from such a C compiler submitted to the the International Obfuscated C Code Contest.

https://www.ioccc.org/2001/bellard/index.html

xorvoid1mo ago

Further Fun fact, that submission was called OTCC. I reverse engineered it and that provided inspiration for SectorC.

https://xorvoid.com/otcc_deobfuscated.html https://github.com/xorvoid/otcc_deobfuscated

pseudohadamard1mo ago

Meh, I did an entire awk interpreter in two lines:

  #!/bin/sh
  echo "awk: bailing out" >&2

DeathArrow1mo ago

For me is not interesting because it fits in 512 bytes, it's interesting because it's very simple. I think it would be a great introduction to learning about compilers.

EGreg1mo ago

Reminds me of Allegro SizeHack where we made games in 10KB - but we were using C and Allegro library!

https://www.oocities.org/trentgamblin/sizehack/entries.html#...

kreelman1mo ago

There seems to be a good amount of interest for a boot sector compiler!!

If you're running on Linux, adjust the qemu call to use alsa rather than coreaudio.

I generated a pull request for this on Github. If the author is happy enough with my verbose shell scripting style :-) it might get included.

userbinator1mo ago

C-subset, to be precise; but microcomputer C compilers were in the tens of KB range, for one that can actually compile real C.

drob5181mo ago

Brilliant! I love the stealing of Forth ideas to power this. Forth’s minimalism is highly underrated.

zahlman1mo ago

> Big Insight #2 is that atoi() behaves as a (bad) hash function on ordinary text. It consumes characters and updates a 16-bit integer.

I could have sworn I remembered atoi() being defined to return 0 for invalid input (i.e. text not representing an integer in base ten).

MobiusHorizons1mo ago

That would be true of one using a libc, but in a boot sector, you only have the bios, so the atoi being referenced is the one defined in c near the beginning of the article

zahlman1mo ago

Ah, I somehow skipped over that exact code block on first read.

alittlebee1mo ago

This is really beautiful (I feel like this sort of project is outsider art), thank you for sharing.

hgs31mo ago

Great read. It would be neat to see a mini operating system under 1 kb of code.

SeanSullivan861mo ago

Why is it called a C Compiler if it's a subset of C?

1 more reply

NooneAtAll31mo ago

> I wrote a fairly straight-forward and minimalist lexer and it took >150 lines of C code

was it supposed to be "<150"?

owalt1mo ago

They're saying the naive implementation was more than 150 lines of C code (300-450 bytes), i.e. too big.

wbsun1mo ago

Nice, now you can dd it to your boot sector and ... Wait, it is 2026, there are 1000 ways of booting and memory mapping on so-called unified ARM architecture @,@

gonzus1mo ago

Lacking support for structs, I think this is too minimalistic to be called "a C compiler".

benj1111mo ago

Weren't structs a fairly late addition to C?

And anyway, isn't that kind of missing the point. 512 bytes isn't much. Your comment is nearly a 5th of that budget.

pilord3141mo ago

you bootstrap it into a library you can include optionally, duh

kayo_202110301mo ago

Nice. Very K&R-ish. Not a bad thing.

j / k navigate · click thread line to collapse