highghlow
This post was written by my friend Ivan, and then translated and edited by me.
This post is the second in a series about DoomBF, a project, the goal of which is to run Doom (1993) in the esoteric programming language Brainfuck.
RISC-V
RISC-V is an open-source instruction set architecture, which is a Reduced Instruction Set Computer (RISC). While the full architecture includes extensions for many things, such as multiplication, floating point and cryptographic operations, the base instruction set — rv32i — is quite small, and it's entire specification fits within 16 pages of not-at-all-dense text.
First, we compile Doom to to rc32i, and then convert it to brainfuck. Each RISC-V instruction has it's own Python class, which is responsible for generating the brainfuck code, which depends of it's register arguments. This is not a RISC-V virtual machine written in brainfuck, it is a compiler. So, instructions add x3, x4, x5 and add x7, x8, x9 would be compiled to different brainfuck snippets. Of course, at the time of compiling the compiler doesn't know what values will be stored there.
Brainfuck Idioms
- [-]! — Reset the current cell to zero
- [>+<-]! — Move the value of the current cell to the right
- [>+<-]! — Copy the value of the current cell to the right
-
[…-]!
— Conditional code execution (
if)
ifnot
Tape:
Code:
This idiom check if the current cell is zero, and executes some code only if it is, which is similar to if (!cur) { … } in C. It requires two zero cells to the right of the current cell, which is the conditional. The conditional doesn't get destroyed (unlike the if above).
>+<sets the value of the second cell to1?0100…[>-]if the conditional is not zero, go to the second cell and set it zero.After this, if the conditional is 0, the tape will look like this:
000100…and if the conditional is 1, like this:
?0000…This is unusual for a brainfuck program, as usually all execution stay on the same cells, and just change the values, but here even the selected cell is different.
>moves one cell to right000100…?0000…[-check if the current cell is 1, and if it is, enters the loop. That means it only get executed if the conditional was 0, which is exactly what we want.…>]is the conditional code. It should end on the 3rd cell, so that both execution paths merge.?0000…<<goes back to the first cell.?0000…
RISC-V instructions
The RISC-V architecture has 32 registers names x0 to x32 (they also have aliases, such as a0, sp and ra, but they aren't important for the implementation).
The x0 register is special, as when reading it always has a value of 0, and writes to it are simply ignored.
Most instructions have 3 arguments: a destination register, and two source registers. For example add x2, x3, x4 adds together the values of x3 and x4 (without changing them), and writes the result to x2.
Comparison instructions (>, >=, ==, !=, etc.) write either 0x00000000 or 0x00000001 as the result.
Most jump instructions take a signed address that is relative to the current instruction, some of them also save the current instruction's address to the stack. Every instruction takes up 4 bytes in rv32i.
Jumps
In my program — "RISC-BF" — I used an addressing system based on ifnot. A special cell contains the address of the next instruction. All normal instructions (arithmetic and memory operations) just save the address of the instruction after themselves, unlike jump instructions, which store an unrelated address, which they may or may not load from a register.
At the end of every instruction the program goes all the way back to the beginning, and starts going through every instruction in the program, checking if it is the right one. At each instruction 1 is subtracted from the cell containing the target instruction's address. If after the subtraction the value becomes zero, the instruction is executed and the whole process starts again. This is needed because brainfuck doesn't have jumps, and so the only way to go backwards in a program is by wrapping it in a big loop.
As the program we want to run has way more that 256 (the maximum value of a cell in brainfuck) instructions, we need to use multiple cells to store this address. You can use multi-byte subtraction to subtract one from these cells and then check if they are all zero, which is implementable in brainfuck, but will cause instruction seeking to be O(n) to it's address. We can do better by using the tree method: handling each of the cells individually. So, first we will use the first byte to determine which of the 256 blocks of instructions we need to run, then do the same with the second, third and forth bytes. With this method instruction seeking becomes O(log n) to the address, and we will have to run only 256*4 = 1024 ifnots in the worst case.
Register operations
RISC-V has a special x0 that ignores all interactions, so ot doesn't get a reserved spot on the tape, instead operations with it are detected at compile time. I also had to add special cases where the destination register is the same as one of the sources, or the two sources refer to the same register, because some opertaions may temporarily modify the source values, and you have to take that into account, or they start reading corrupted values.
The comparison instructions and the conditional jump ended up being especially large, as they have a ton of special cases to worry about.
Arithmetic
How would we, for example, add two 4-byte numbers? If we store each byte in one cell, then we into a problem with overflow. When a lower byte overlows, we have to add one to the byte above it, but detecting an overflow would require us to compare the old value to the new one and check if it became smaller after we added something to it, which would be quite slow.
I decided instead to store all register values in half-bytes, meaning they would take up 8 cells, where each cell contains a number 0 to 15. This makes addition more efficient, as you can account for overflow by just dividing the cell value by 16, and adding that to the next cell, and you can still easily convert it to thecompact format for storing it in memory:
Tape:
Code:
Tape:
Code:
In memory, hovewer, all values are stored in the compact format, as they take up 2 times less space that way, and it doesn't really impact performace, because no arithmetic operations happen directly in memory.
Memory access
Tape:
Code:
You have to store variables somewhere, and 32 registers is way too little space for that, so there is RAM, which can store much more data, but also requires a special algorithm to read and write data by it's address. You can, of course move along the tape in brainfuck, and canonically we even have infinite RAM, but we can only move a constant distance, specified at compile time. To move to an arbitrary position, we have to use a loop, but after we've moved along a tape, we can no longer read the address, so I had to create a special algorithm to take the address with us when moving along the tape.
I reserved 16 cells between the registers and memory (annotated here as x, y and z) for this algorithm. 1 empty, 6 for the target address, 1 for temporary storage and 4 for the value we have read/want to write. Others are used only for Input/Output and are not used in regular memory operations.
To move along the tape for one step, we move x to the first cell, and then move everything one space to the right, starting from the right-most cell.
Now we subtract 1 from addr, and add 1 to addr_scrap; it is used to keep track of where we are on the tape, so that we will be able to return back to the beginning of it by doing everything in reverse.
Here I had the exact same problem as with instruction addressing — the address consists of multiple cells, and I solved it in the same way, using the tree method.
The address cells, like the registers, have values 0-15 instead of 0-255 (except the first one, which has the full range), which gives us 165 * 256 = 256MiB of memory, which is more than enough to run Doom.
So, after processing the last addr cell, I move by 16 for the previous one by just swapping the values in my cells with ones 16 away. This shuffles the data we pass through in memory, but as long as we go back in the same way, it will be unshuffled.
Eventually I have to move by 165 for the first cell, and it is why I chose such a small memory size, as this operation requires writing over 64 million >s for each memory operation, making the full program weigh a whole 3.35TiB! I could've addressed this, of course, by using multi-byte subtraction, instead of handling each cell separately, but that would massively slow down the program by making the interpreter to a bunch of small moves instead of a couple big ones.
Compression
As I mentioned before, the program is absurdly large, but it mostly consists of the same character repeated many times, which makes it a perfect candidate for run-length encoding. This is why I started using the BPK compression format (developed for this project). It just contains characters, potentitally with {} after them with a hexadecimal number specifying the amount of times that character should be repeated. This way the full program is just 335MiB, which can be loaded in a few seconds by our interpreter.