blog

Making a little computer on Minecraft

January. The perfect month for making promises about losing the weight I gained during the new year's eve. It is also the month I get some time off from work and school, a month which I get some weeks off to do whatever I want. Like everyone, I love getting days off, but I am also the type of person who quickly gets tired of having nothing to do: after four days of bliss, I am struck by infinite boredom that makes me want to go back to work. By the time you are reading this post, I probably went insane and can now be found in some remote park munching on tree barks. One of my favourite games, Minecraft, is particularly good at distracting me from inevitable boredom: the possibility of endless possibilities is something very attractive, and today, I decided to play around and make a "proto-CPU" with redstones. This little computer (and this is how I am going to call it from now on) is going to be really simple, at least for now: no clock or anything, it will mostly work with "manual instructions". I will be able to input numbers, perform additions, record the results in RAM, and load the results from RAM. #### Adders First, I want to make some contraption capable of adding (binary) numbers. How would this work? Let's take a look at how addition would work, in binary, using numbers with a single unit: ```json A + B = Result 0 0 0 0 1 1 1 0 1 1 1 0 ``` The first three rows should make perfect sense, right? But Why is the last one **0**? Well, if we think back in decimal numbers, consider this: ```json 1 + 7 = 08 1 + 8 = 09 1 + 9 = 10 ``` After **9**, if we need to increment a unit, we flip **9** back to **0** and insert a **1** in the front of the number, it becomes **10**. If we don't have an extra unit on the left, however, then `1 + 9 = 0`. If you are not familiar with this concept, it is called **integer overflow**. So, how do we create this simple adder? Well, if you look closely, the output from those operations are exactly what we get from a XOR gate. So, if I make a XOR gate, I will be able to make a single-unit adder.
This circuit takes input from the left (A and B) and outputs the result on the right.
Instructions on how to build these gates can be found in the Minecraft Wiki. Some circuits in this post I will make myself, so you won't find all of them there.
Ok, now how do we scale this so we can have more units? Looking back to the decimal system: ``` 18 + 16 -- ?? ``` How would we solve this? First, we solve **8** + **6**, which is 14. We then "split" the units: 4 goes down as the result, and **1** is *carried* to the next units on the left, like this: ``` 1 18 + 16 -- ?4 ``` Then we sum the three **1**, and get the result 34. This is the same principle we use for the adder, but it is even simpler: in addition to the XOR gate, we also AND them. These would be the results: ``` A + B = AND XOR 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 ``` And look what we get: 00, 01, 01, and 10.
The two "wires" on the right are the inputs, the straight wire on the left is the result, and the curved wire on the left is the carry bit
Great. I now have what is called a **half adder**. It is capable of adding two bits and give me back 1 bit as result and 1 bit as the carry number. The next task now is to make what is called a **full adder**. A full adder is similar to the adder I just made, but it is capable of adding three bits: A, B, and Carry, and give me back 1 bit as the result and 1 bit as carry. For example: ``` c = carry (input) C = carry (output) R = result A B c = R C 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 ``` Why do I need this? Simple: I can chain full adders (using the carry output from one and using it as the carry input for another) in order to make a unit capable of adding numbers composed of several bits (like a byte, for example). Consider this case: ```json A = 0010 B = 0111 Result: 1001 ``` If I have a half-adder, chained with 3 full adders, I could feed the two numbers above in their input, and get the result as the output: ```json F = full adder H = half adder C = carry R = result An = Bit of A/B at index n (from right to left) Input A0 B0 0 1 / H R/ C A1 B1 |1 |0 1 1 | | / | F | R/ C A2 B2 | | |1 0 1 | | | / | | F | | R/ C A3 B3 | | | |1 0 0 | | | | / | | | F | | | R/ C | | | | 1 0 0 1 Output ```
ta-daaa
And here we have it. Notice how the input and output actually match with what I described before: `0010 + 0111 = 1001`. I now have a circuit capable of adding two 4-bit numbers! #### RAM The next part to build is memory. We will need memory in order to record old results and read back from it. First, how should we connect the adder to the memory? For real CPUs, you would probably store the result from the adder in a register, and then decide what to do with it later. In our case, I will send it directly to RAM! So, how does a very basic memory cell works? The most basic memory cell should have 2 inputs and 1 output: the single output is used to tell us the content of the memory cell: 1 or 0; one input, called **data**, tells us what is the bit we want to store; the other input is the **write** bit: when it is on, we take the bit from the input data and store it in the memory - we only store things when the **write** bit is on, otherwise, all memory cells would change all the time. Here is an example of how a memory cell would behave over time, with a series of different inputs: ```json M = Memory cell d' = data output d = data input w = write bit 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 d /w d /w d /w d /w d /w d /w d /w d /w M => M => M => M => M => M => M => M d'| d'| d'| d'| d'| d'| d'| d'| 0 0 1 1 0 0 1 1 ``` And here is how it looks like on Minecraft (inputs are on the left, output is on the right): I decided that my little computer will have 16 bits of memory - very similar to my brain. This is enough to store 4 numbers of 4 bits. Since the bits will be grouped in 4 (like 8 bits = 1 byte, but I am using a word size of 4 bits), groups of 4 bits will have their "write" input joined: if I want to record a full number of 4 bits, all the memory cells in that word will have to have their memory replaced. So, how would we record stuff from the adder in the RAM? It's pretty simple: we can simply send the input from the adder to ALL the four words. Since we need to activate the "write" bit, it will only be recorded in the word we want. Notice how I joined the "write" input for every 4 bits and isolated them on the right side with 4 buttons. If I want to record the output from the adder on the third word, for example, I can just press the third button and the result will be kept at Ram[2]. Lovely. Habemus RAM input, how about output? Let's assume we will only recover one word at a time from ram - this means we will need to make the ram somehow release only the data from the location we want into this 4-bit bus. The easiest way to do this, **in our case**, is just to use some AND gates: I will make 4 levers (one for every word in the ram), and I will *and* the data from the ram with the input from the lever. This means that only the data with an active lever will be carried forward in the bus. This little piece will receive input from a lever and *and* the data from the ram: it will only be carried forward if the lever is active. Here is what it looks like completed: Notice how I am recovering the data from the first word in ram (the output is on the right). You can probably see some tunnels underneath the blue structure - that is where I am passing the redstones for the levers - when I activate a lever, the corresponding word releases its data. #### Registers The next step now is to make a few more pieces of memory for the CPU: registers. In our case, they will use the same circuit as the RAM, so what is the point of them for our case? The registers will give us a more accessible way to manipulate memory: I will place some levers next to them so I can manipulate their bits manually. It will also give us additional memory for temporary values. If I don't build registers, where would I put the initial values for the calculations? I am only going to build two registers - it should be enough for us. First, I will duplicate the output from RAM into two buses - one for each register: Now I can make the registers. And here they are, please take some time to register their glory in your memory:
Truly a wonder of engineering
Fascinating. The levers behind them provide me a quick way to input some numbers into them, and the buttons on the bottom-right side are the **write** bits, so I can record the data in the registers. Alright, how should we connect the registers to the rest of the CPU? If you are building an actual CPU, you probably want to give the programmer a choice of which registers you want to get the data from and where you want the output to go. I will keep this simple: input A comes from register A, input B comes from register B - that's it, no flexibility. BEHOLD #### Test run Let's test this thing! This is what I am going to do: 1- Save `0011` in Register A* 2- Save `0001` in Register B 3- Record the result in Ram[0] (should be `0100`) 4- Save `0001` in Register A 5- Record the result in Ram[1] (should be `0010`) 6- Save `0010` in Register A 7- Record the result in Ram[2] (should be `0011`) 8- Load Ram[0] in Register A 9- Load Ram[1] in Register B 10- Record the result in Ram[3] (should be `0110`) 11- Load Ram[3] in Register A 12- Load Ram[2] in Register B 13- Record the result in Ram[1] (should be `1001`) * I didn't name the registers before, so I am naming them now. Use your imagination to figure out which one is which (hint: the one closer to the adder is A) BEHOLD AGAIN: ##### Operations 1 and 2
1- Save 0011 in Register A
2- Save 0001 in Register B
Result from the output of the adder, being sent to RAM: ##### Operation 3
3- Record the result in Ram[0] (should be 0100)
##### Operation 4
4- Save 0001 in Register A
##### State of RAM after operations 5, 6, and 7
5- Record the result in Ram[1] (should be 0010)
6- Save 0010 in Register A
7- Record the result in Ram[2] (should be 0011)
##### Operation 8
8- Load Ram[0] in Register A
Data stored in Ram[0] being sent to the registers: Data stored in Ram[0] recorded in Register A (I accidentally wiped Register B, but that is fine - it will be rewritten on the next step): ##### Operation 9
9- Load Ram[1] in Register B
Registers are loaded and output of adder is being sent to RAM: ##### Operation 10
10- Record the result in Ram[3] (should be 0110)
RAM is full ##### Operations 11 and 12
11- Load Ram[3] in Register A
12- Load Ram[2] in Register B
Ram[3] being sent to the registers: All registers loaded: ##### Operation 13
13- Record the result in Ram[1] (should be 1001)
Result being sent to ram: Recorded in Ram[0]: I know what you are thinking: yes - it does run Crysis! Probably the best aspect about this thing: it is not affected by Meltdown or Spectre, since I removed the Branch Prediction because it was unsafe (I didn't take screenshots or anything, but I made it. Totally.). Super secure! What would be the next step now? Maybe in the future I could add another piece of memory that could store program instructions, which could automate the process of pressing buttons and switching levers. But I will leave this to another day.
  • 1