Constructing a Minecraft CPU

Profanity Notice

Due to the very nature of this webpage there will be some written copies of the "f" word. If you would rather they be randomly censored click here. If you think you can handle the vulgar version, have at it.

Brainfuck Intro

Brainfuck is an esoteric programming language with only eight characters. It is turing complete, and as such can compute the same things as other programming languages can. The language has the ability to input and output ascii characters, to move the data pointer to adjacent memory cells, to increment and decrement the values in those cells, and some basic program flow control. The flow control is done with the [ and ] characters, which loop the code inside while the current memory cell has a non-zero value. A more complete description of the language can be is in the following list, alongside a link to the code for this project.

• https://esolangs.org/wiki/Brainfuck
• https://en.wikipedia.org/wiki/Brainfuck
• https://github.com/yit6/brainfuck-cpu

CPU modes

One of the key requirements that I invented is that there should be no compilation step. The program should run a brainfuck program directly, with only a preprocessing step of mapping the [].,+-<> characters to a binary encoding. It is possible to do an ascii encoding for the instructions, which would be a more elegant telling of this joke should someone want to best me. The lack of preprocessing has little effect for most of the brainfuck instructions, but makes the implementation of [ and ] difficult. When encountering these brackets the instruction pointer sometimes has to jump to the matching brace. If there was any preprocessing the location of the matching bracket would be in the program, instead the cpu will have to spend around half of its time doing nothing but scanning for matching braces.

I implemented this with "modes" in the cpu. There are three modes it can be in. The easiest one to describe is normal mode, where the cpu acts normally. By acts normally I mean it executes the instruction the data pointer points at, and the moves on to the next instruction. The other modes are "scan forwards" and "scan backwards". In these modes the cpu does not execute any instructions, it just scans through the program while doing counting how many opening and closing braces it sees. Once it determines that it has reached the correct brace it resumes "normal" operation.

Incrementor/Decrementor

Given the quantity of operations this cpu will have to execute the ALU can be very simple. Half of all brainfuck instructions boil down to incrementing and decrementing things. This is all the ALU will do. Sometimes it will take a number and add 1 to it, described in the formula below:

$$\text{inc}\left(x\right)=x+1$$

The operation is just about the opposite of that. It will take a number and subtract one from it. Here is the formula for that:

$$\text{dec}\left(x\right)=x-1$$

This could be implemented with an adder/subtracter and a constant input of 1, but that seems very bloated here. Adding 1 to a binary number can be thought of as following the following simple procedure:

1. Start at the least significant bit.
2. If the bit is 1, flip it and repeat this step on the next bit.
3. Once a bit is 0 flip it to a one.

This essentially encodes the carrying process. If that feels odd try adding 1 to a binary number with a pencil and paper. A very similar procedure works for subtracting 1:

1. Start at the least significant bit.
2. If the bit is 0, flip it and repeat this step on the next bit.
3. Once a bit is 1 flip it to a zero.

This time it is essentially just borrowing.

I chose to describe these operations as a procedure, but in hardware it would be better to implement all this in a parallel manner. The part with zeroing all bits the are one from the LSB cleanly maps to flipping all the bits with all the bits less than it set. The next step to implement parallel style is flipping the least significant 0 to a one. In a surprise coincidence (or a hint that there is a deeper structure here?) this can also be done by swapping a bit where all the bits less significant are set.

If you are implementing a simulator for this cpu in VHDL, like I was at some point in my past, you would be able to implement a generic version of this very simply with VHDL 2008's unary AND.

library ieee;

use ieee.std_logic_1164.all;

entity inc is
	generic (N : integer);
	port (
		a :  in std_logic_vector(N-1 downto 0);
		y : out std_logic_vector(N-1 downto 0)
	);
end entity inc;

architecture buh of inc is
begin
	y(0) <= not a(0);

	gen: for i in N-1 downto 1 generate
		y(i) <= a(i) xor (and a(i-1 downto 0));
	end generate;
end architecture buh;

Very similar ideas apply for decrementing, so rather than subject you to almost the same logic I will just put the VHDL for it and leave it as a exercise for the reader to verify that it works.

library ieee;

use ieee.std_logic_1164.all;

entity dec is
	generic (N : integer);
	port (
		a :  in std_logic_vector(N-1 downto 0);
		y : out std_logic_vector(N-1 downto 0)
	);
end entity dec;

architecture buh of dec is
begin
	y(0) <= not a(0);

	gen: for i in N-1 downto 1 generate
		y(i) <= a(i) xnor (or a(i-1 downto 0));
	end generate;
end architecture buh;

All the other theory-ish stuff

The CPU will have ROM to store the program, and RAM to store the values in the "tape". The ROM stores 256 instructions and the RAM stores 32 bytes.

The output is displayed in binary on a 2d grid, where each new value pushes the old ones across. I don't recall if the input functionality was every properly implemented.

Minecraft

Incrementor

First I will show the incrementor is implemented in redstone. The blue lines take the input and pass it into the next stages.

The And gate is implemented in the standard minecraft fashion. All the inputs get inverted with a torch, then they all activate the same redstone line, which finally gets inverted at the end.

The final torch for the inversion at the end is tucked away, but if you look closely this is a picture of it.

Now that we have a signal with the result of an And operation of ever bit less significant, all that needs to be done is an exclusive or to flip it. I used a design for the x-or gate that can be stacked vertically every two blocks.

It is surely possible to make a better design that makes use of some pretty technical minecraft specific logic, like a carry-cancel adder, this squarely beats any ripple adder, with 4 redstone ticks of propagation delay.

Instruction Pointer

Since the CPU scans for its next instruction it never needs to jump. The instruction pointer will only ever move to the next or previous instruction. This allows the instruction pointer to be made from an incrementor, decrementor, multiplexer, and a d-flip-flop.

There is one control line to determine the direction, and a clock line that behaves as might be obvious. The output is simply a pointer in ROM to the next instruction.

Bracket counter

The bracket counter is similar in construction to the instruction pointer, but is actually more complicated. This is because the bracket count can either increase, decrease, or remain the same.

ROM

The rom stores 256 instructions, which the fibonacci test program didn't come close to using up.

Output

The output is a grid of lamps. When new data is ready the display shifts to the left to make room. Here it is displaying the portion of the fibonacci sequence that it has calculated. The two initial ones are not displayed, because they were not calculated in the loop.

The grid is merely a big shift register made with locking repeaters.

Conclusion

brainfuck cpu in minecraft