We successfully compiled DOOM (1997) to the brainfuck esoteric programming language, creating the most complex brainfuck program ever.

What is brainfuck?

Brainfuck is an esoteric programming language created in 1993 with the goal of having a really small compiler. As a result, the language is extremely minimal, consisting only of 8 unique instructions.

The brainfuck machine operates on a tape, similar to that of a Turing machine, except the cells here contain bytes instead of bits. The head points to one of the cells, and can be moved left or right. The machine goes through a program, executing each instruction one-by-one; everything that is not a valid instruction is ignored. The instructions are:

+ — Increment the current cell (wrappig to 0 after 255)
- — Decrement the current cell (wrapping to 255 after 0)
< — Move the head one cell to the left
> — Move the head one cell to the right
[ — Start a loop. The instructions within a loop are executed while the current cell is not zero. If it is zero when the loop is entered, the loop is skipped.
] — End a loop
. — Write the value of the current cell to stdout
, — Read a value into the current cell from stdin

We did not modify or add any instructions, and did not offload the 3D rendering to a separate program. That would make it too easy. Even the I/O remains the same; we use UNIX pipes and a special "frontend" program to turn it into a playable game.

How did we do it?

In short, we replaced all DOOM's calls to the operating system with our custom ones: doom.wad was hard-coded into the executable, the allocator was replaced and made to just use a buffer instead of requesting memory from the OS, the graphics were made to write raw image data to stdout, etc. Then we compiled it to a statically linked RISC-V executable, and converted that to brainfuck.

If you want to learn more, you can check out our series of blog posts, which goes into the specifics of how to achieve certain things.

How well does it run?

On my machine, about 40 seconds per frame. This is not terribly fast, but is also much faster than I initially thought it would be. It took 2 full days to beat the first level.

The whole program weighs 335MiB in it's run-length encoded form, which is the one actually used to run it. If you decompress it, it takes up 3.35TiB, which, even for us, is not practical to load.

I specifically avoided adding special handling for the constructs we use into my interpreter, even though it would massively speed up execution, as it could potentially introduce bugs that will make the program work only on our interpreter. Not that any other interpreter I know of can load a 3TiB program, but still.

Why?

To test if we can do it; as it turn out, we can! We alredy knew that this is theoretically possible, as brainfuck is Turing-complete, but it's one thing to hypothesise it, and another to see it running right in front of you with your own two eyes.

Who made this?

This was made by:

Alexey Nikolskiy — Organizer; Creator of the MiniDoom portability layer
Ivan Sakaev — Creator of the RISC-BF compiler
Alex Kravchenko — Creator of the industrial-bf brainfuck interpreter (and this website)