33 ms·
A minimal C compiler in x86 assembly
- chomp 5y ago"Minimal" being almost 5KLOC, sheesh. Actually, I'm surprised that a C compiler fits in that space. Also: --- Goal This is a set of manually created hex programs in a Cthulhu Path to madness fashion. Which only have the goal of creating a bootstrapping path to a C compiler capable of compiling GCC, with only the explicit requirement of a single 1 KByte binary or less.
- adastra22 5y agoI would think that making a minimal forth or lisp would be the better path towards that goal, then use that to bootstrap a c compiler.
- pabs3 5y agoA recent comment from LWN on that note: https://lwn.net/Articles/893608/ https://lwn.net/Articles/893608/ I asked about this on their IRC channel and got this response from oriansj: Well we did bootstrap a FORTH from hex: https://github.com/oriansj/stage0/blob/master/stage2/forth.s https://github.com/oriansj/stage0/blob/master/stage2/forth.s and we did bootstrap a garbage collecting Lisp from hex: https://github.com/oriansj/stage0/blob/master/stage2/lisp.s https://github.com/oriansj/stage0/blob/master/stage2/lisp.s but if you notice: https://github.com/oriansj/stage0/blob/master/stage2/cc_x86.s https://github.com/oriansj/stage0/blob/master/stage2/cc_x86.... writing a C compiler in assembly that supports structs, unions, arrays, inline assembly and a bunch more was done in less than 24 hours by an inexperienced C programmer. Who then after started doing bootstrapping speed runs to demonstrate how trivial of a problem it is to implement that level of functionality in a C compiler. In the decades for which Lisp and FORTH existed, why didn't they solve such a trivial problem? Or better yet, now that you can see how it is done. Could anyone actually produce a C compiler with the same level of functionality in Lisp or FORTH in the same amount of time (or less?). It is easy to talk a big game and words are cheap, we have the entire cc_* family of C compilers written in assembly for multiple architectures and in even cross-platform arrangements. If your language was any good at bootstrapping you'd be able to beat that. Then show your language written in less lines of assembly than cc_x86 to prove the point. Please prove me wrong with working code. Assembly and C have working code good enough to bootstrap GCC+Guile+Linux for more than a year now. https://github.com/fosslinux/live-bootstrap https://github.com/fosslinux/live-bootstrap https://github.com/oriansj/stage0-posix https://github.com/oriansj/stage0-posix It is time for Lisp and FORTH to either deliver or learn to stop talking about something they never were good at in the first place and learn to admit Assembly and C won not because "worse is better" but because objectively they are better languages for bootstrapping new and better tools.
- ducktective 5y agoI miss these technical provocative challenges. Nowadays, everyone tries to "not offend" people.
- samhw 5y ago'Nowadays' as opposed to ... 7 hours ago?
- adastra22 5y agoI mean there are Forths that fit inside a boot sector (<512 bytes). My reading of the goal was a minimal kernel of code from which the larger system can be bootstrapped. Here’s a C minimal compiler in forth for the next stage: https://groups.google.com/g/comp.lang.forth/c/lBYFfVJ1qhc/m/BxvaTHCX_JgJ?pli=1 https://groups.google.com/g/comp.lang.forth/c/lBYFfVJ1qhc/m/...
- mypalmike 5y agoThat an inexperienced C programmer wrote what appears to be 5000 lines of assembly in 24 hours implementing a fully working C compiler seems... a rather extraordinary claim. The file size of around 130K would indicate typing non-stop for 24 hours at something like 100 characters per minute.
- a9h74j 5y agoMaybe GitHub Copilot is that good already.
- Taniwha 5y agoI think they are talking about the later stages of boot strapping 'stage2' where they are writing a more functional, but still small, C compiler in a C subset that can be compiled by this one
- tralarpa 5y ago> typing non-stop for 24 hours at something like 100 characters per minute Not only that. It would be typing at that speed without testing anything. In assembly. Haha. In reality what would happen is that you would type 24 hours (not in one day, I assume) and then spend the next days finding the places where you wrote R5 instead of R4. And, of course, without losing any time on refactoring already written code (changing order of parameters, finding a better name for a function, etc.)
- arinlen 5y ago> "Minimal" being almost 5KLOC, sheesh. 5kloc of assembly code, which roughly correspond to opcodes. That's quite small. It's actually 4399 loc, including blank lines and a significant number of comment lines. Quite impressive. There are JSON parsers that require way more code just to handle the basics of parsing.
- flohofwoe 5y ago5kloc isn't really all that much code, especially in assembly.
- jbverschoor 5y agoIt's a compiler wth. 5k is nothing. If you strip out the comments, the constants, the labels and some other cruft, you're left with 2450 instructions. That should be well under 1000 lines in other languages.
- tomcam 5y agoGotta love this. I hope to see documented what subset of C it will support
- LeFantome 5y agoI believe it was said elsewhere that it was expected to compile GCC 4.7 so that gives you a solid idea of the C features it supports.
- tomcam 5y agoAnd so it does, thank you for catching that. I fear that goal is unreachable with such a small team. GCC is hella complicated.
- MaxBarraclough 5y agoI'd be more optimistic. The cproc C compiler has only a very small team but it supports enough of the C language to compile GCC 4.7. https://github.com/michaelforney/cproc https://github.com/michaelforney/cproc
- tomcam 5y agoThat's news to me! Not sure cproc existed last time I looked at GCC but that was a long time ago. Thank you.
- pabs3 5y agoThis was created as part of the Bootstrappable Builds project to go from an MBR of machine code plus a ton of source all the way up to a full distro. https://bootstrappable.org/ https://bootstrappable.org/
- harha 5y agoThis is pretty cool, there's so much value in knowing how to create things, same as in manufacturing, producing drugs etc. I would love to get guided through how they wrote this.
- deleted 5y ago[deleted]
- loudmax 5y agoThe Goals section from the projects main page are pretty interesting: https://github.com/oriansj/stage0 https://github.com/oriansj/stage0 This is a set of manually created hex programs in a Cthulhu Path to madness fashion. Which only have the goal of creating a bootstrapping path to a C compiler capable of compiling GCC, with only the explicit requirement of a single 1 KByte binary or less. Additionally, all code must be able to be understood by 70% of the population of programmers. If the code can not be understood by that volume, it needs to be altered until it satisfies the above requirement. Very cool project, but I guess I won't hold out for compiling a working web browser from this project.
- adrian_b 5y agoWith a working gcc, you should be able to compile all that is needed to build Chromium and Firefox. There are a few programming languages that cannot be bootstrapped from a C or C++ compiler, so you need a binary executable of a previous compiler version for that language, but I do not think that Chromium uses any of those. The bootstrapping of Rust is complex, but AFAIK it is possible using mrustc. Then you should be able to also compile Firefox.
- stevefan1999 5y agoI'm surprised they wrote a minimal C compiler in assembly rather than any LISP dialects, then make a C compiler in LISP
- arinlen 5y ago> I'm surprised they wrote a minimal C compiler in assembly rather than any LISP dialects, then make a C compiler in LISP I recommend you check out the author's GitHub page. It includes Forth and Lisp projects, explains why C was a success while those projects failed, and challenges any Forth and Lisp fan to actually substantiate their baseless claims with actual work instead of pushing beliefs that don't have any bearing on reality.
- rscho 5y agoAre claims of easy bootstrapping in Forth really baseless, though? ASM makes sense for C subset, but if one wanted to bootstrap a more complete language directly from scratch, things would probably be different.
- t-3 5y agoForth is simple to bootstrap, but maybe not so easy to learn or reason about, because it isn't really taught in any schools or popular online materials. There are tons of resources for thinking about and writing compilers for C-like languages, and there's a decent chance that someone with a CS degree has done so doing their coursework.
- renox 5y agoThe link https://github.com/oriansj/talk-notes/blob/master/DECISIONS.org https://github.com/oriansj/talk-notes/blob/master/DECISIONS.... I think that the takeaway is familiarity trumps technical 'superiority'. That said I don't know why having a working GC for Lisp is that important because typically you'd use Lisp to compile your C-compiler so memory efficiency doesn't really matter..
- 5y ago
- choeger 5y agoWhile everyone asks about lisp or forth for this task, I have to wonder what one has to leave out of C to make it "minimal" enough for this task. The subset of features left out might teach us something about the language.
- martincmartin 5y agoTheir goal is to compile GCC, so whatever subset of C GCC uses.
- matthews2 5y agoGCC 11 and newer requires a C++11 compiler, 4.8 was the first to require C++ at all, and I think that there are some very old versions of GCC that can be built with a pre-standard C compiler.
- userbinator 5y agoYou would need to compile the newer versions with the older versions. The first C++ compiler was probably written in C.
- User23 5y agoInterestingly enough, Cfront[1] was written in C++. [1] https://en.wikipedia.org/wiki/Cfront https://en.wikipedia.org/wiki/Cfront
- cardiffspaceman 5y agoA trope of old-school compiler development is, "We made our language self-hosting, and then we compiled it by hand."
- arinlen 5y agoOne of the projects adopted by the bootstrappable community is maintaining GCC 4.7. https://bootstrappable.org/projects.html https://bootstrappable.org/projects.html From the Projects section: > "We propose to collectively maintain a subset of GCC 4.7 to ensure that we can build the foundation of free software distributions starting with a simple C compiler (such as tinyCC, pcc, etc)."
- glandium 5y agoTrusting trust all the way down: How do you trust your assembler to output the exact machine code corresponding to the source? How do you trust whatever program you might use to do the validation? Ok, let's skip the assembler and write machine code directly. How do you trust the program you use to write that machine code? How do you even trust the firmware will execute your machine code in the way you intend?
- Yajirobe 5y agoYou write tests.
- kragen 5y agoHow do you detect a backdoor inserted in the login program with a test? You'd have to know the backdoor password to write the test. Perhaps you haven't read Thompson's Turing Award lecture and so you have no idea what we're talking about.
- d33 5y agoNot sure if it would work, but wouldn't it greatly complicate creating a backdoor when the host's memory is very heavily constrainted? e.g. an AVR-based "computer" that would hardly do much more than actually translate assembly to machine code?
- kragen 5y agoIt would probably be easier to detect, but when Thompson deployed the attack in practice, nobody noticed, even though the PDP-11 address space was the same size as an AVR's, and the CPU was a lot slower. (AVRs invariably have much less physical RAM installed than a PDP-11, but you'd need some external memory to get a C compiler to build.)
- colejohnson66 5y agoAnother Ken Thompson style hack, but on an AT&T 3B2: https://www.quora.com/What-is-a-coders-worst-nightmare/answer/Mick-Stute https://www.quora.com/What-is-a-coders-worst-nightmare/answe...
- pflanze 5y agoIt appears that this project is in competition with Mes[1], which is also running under the http://bootstrappable.org/ http://bootstrappable.org/ 'umbrella', and which implements both a Scheme interpreter (in C) and a C compiler (in Scheme) it is designed to run. The C compiler that Mes was written for, MesCC, appears to be using some 600 lines of code excluding libraries, which I haven't checked how large they are. It might be smaller than cc_x86.s[2] posted here (or it might not when including the libs), but if concerned about bootstrapping size, the size of the Scheme interpreter would have to be included as well and then the size is surely larger than cc_x86.s; also, I'm unclear about how Mes solves the mutual dependency issue of Scheme <-> C. Mes is authored primarily by Jan (janneke) Nieuwenhuizen. Judging from a comment by Janneke on IRC[3] collaboration seems amicable, if I'm not mis-attributing this quote: <janneke> some routes we try just are a dead end... Not having any ties to either project I welcome corrections of any mistakes I may have made here. [1] https://www.gnu.org/software/mes/ https://www.gnu.org/software/mes/ [2] https://github.com/oriansj/stage0/blob/master/stage2/cc_x86.s https://github.com/oriansj/stage0/blob/master/stage2/cc_x86.... [3] http://logs.guix.gnu.org/bootstrappable/2022-05-01.log http://logs.guix.gnu.org/bootstrappable/2022-05-01.log
- janneke 5y agoAh no, there is no competition, at least not yet ;) Stage0---of with cc_x86.c is a part---as a project started off from the bottom (hex0) and is working up. When stage0 just started, I created GNU Mes soon to be folowed by MesCC, which aimed to build a version of TinyCC and the remaining bootstrap for GNU Guix. The first versions of mescc had its own linker, which was later in a joint effortt replaced by M1 and hex2 from MesCC-Tools (also part of Stage0. My initial idea for Mes was to translate it by hand to assembly, so the M1 assembler would come in handy. As it turned out, cc_x86.c and its next step M2-Planet were developed as part of Stage0. Starting from an 357-byte hex0 provided by the bootstrap-seeds, Stage0-posix builds hex0, kaem, hex1, catm, hex2, M0, cc_x86, M1, M2, get_machine, (mescc-tools), and M2-Planet. M2-Planet in turn builds Mes, which builds a bootstrappable TinyCC, etc.
- pflanze 5y agoThanks for your answer! I'll try out some bootstrapping paths and will make an effort of getting a full understanding of the whole picture, and am hoping to write something up about what I find out. (BTW I did ask on IRC, some further details might be found from the answers I got here: http://logs.guix.gnu.org/bootstrappable/2022-05-03.log#144953 http://logs.guix.gnu.org/bootstrappable/2022-05-03.log#14495...)
- userbinator 5y agox86 Asm of a very different syntax (neither Intel nor AT&T), to be fair. For a second, I thought it was ARM. Then I started to parse some of the syntax and realised it could be made even more minimal, e.g. this function ;; in_set function ;; Receives a Char in R0, char* in R1 ;; Return result in R0 based on what it seems to do, can almost certainly be replaced with a simple repnz scasb.