Fantasy CPU emulator part 1

2021-10-25

Years ago I was introduced to Richard Buckland's course at UNSW. It featured a little microprocessor called the e-4917. In the video professor Buckland explains how it works, and one thing has never stopped amazing me:

That at the lowest level what is in a memory "cell" can be both an instructions to a program or the data used in a program.

In this post I'll explain the basics workings of my fantasy CPU using the e-4917 microprocessor as a basis. We will go through how it works, and how to write some programs in it. In a future post I'll show you how to implement it using React and Typescript.

Photo by Adi Goldstein

Anatomy of a CPU

To understand what we are going to build, we need to understand the basics of a CPU (Central Processing Unit).

A CPU has registers. A register is a memory location which the CPU can access quickly. Our fantasy CPU will only have four registers: R0 and R1, plus two registers called the Instruction Pointer (IP) and the Instruction Store (IS).

R0 and R1 are the workhorses amongst our registers, they are the cells the instructions / operations are actually executed on.

The IP (Instruction Pointer) registry contains the current position the program is in. This a number mapping to a memory address. The IS (Instruction Store) contains the current operation we are executing.

The "program" comes from the computers computers memory. Memory consists of cells which can each store a single bit: a one or a zero. In our fantasy CPU we will pretend that memory can store decimals, so we do not have to go all binary.

Each cell can contain either an instruction or some data. A cell is named by its address which is a number. The first memory cell's address is 0 and we increment it by one for each subsequent cell.

We will visualize memory as a grid of boxes containing numbers.

The CPU executes instructions. Instructions can either be one byte or two byte instructions. A two byte instruction always does something with two memory cells, whereas a one byte instruction only looks at a single cell.

Therefore a one byte instruction will move the IP to the next cell, and a two byte instruction will move the IP two cells over.

The one byte instructions for our fantasy CPU has are:

• 0 = stop the program.
• 1 = addition (R0 = R0 + R1)
• 2 = subtract (R0 = R0 – R1)
• 3 = increment R0 (R0 = R0 + 1)
• 4 = increment R1 (R1 = R1 + 1)
• 5 = decrement R0 (R0 = R0 – 1)
• 6 = decrement R1 (R1 = R1 – 1)
• 7 = make beeping sound

The two byte instructions our fantasy CPU has are:

• 8 = print the value of the next memory cell
• 9 = load value from address into R0
• 10 = load value from address into R1
• 11 = write value of R0 into address
• 12 = write value of R1 into address
• 13 = jump to address, and continue instructions from there
• 14 = jump to address but only if R0 == 0
• 15 = jump to address but only if R0 != 0

The way the CPU executes the program is as follows:

• Look at the address which is in the IP registry, and put the value at that address inside the IS registry. At the start of the program all registers have a value of 0.
• Execute the instruction now loaded in the IS registry.
• Change the memory location to which the IP registry points at. Either incrementing by one if the instruction was a one byte instruction, or by two if the instruction was a two byte instruction.
• Repeat the process until the program completes. In other words when it hits a 0.

Lets look at some examples to get a feel for how this works.

Beeping three times

From our table of instructions we can see that 7 produces a beeping sound. To perform three beeps we configure the memory so that three 7's are next to each other:

Note: if you scroll down past here a popup will appear with a cheat sheet of the operations. You can open and close it yourself.

Here are some instructions on how the emulator works

• The Play button will run the program. Once pressed it turns into a Pause button. If the program is finished it becomes a Restart button.
• By changing the Speed you can slow or speed up to execution, which allows you to better see what is happening.
• The Step button executes the program one step at a time. When the program has finished or crashed clicking step restarts the program.
• The Save button creates a save point, which the Restore button restores to.
• The Restart button resets everything to the original program, as it was when the page loaded.
• You can manipulate the memory by clicking a cell and entering a number. This will automatically create a save point.

The use of colored borders indicate:

• a blue border indicates that the cell is the current position the program is executing. In other words the value of the IP registry.
• a red border indicates that the cell is the position the program stopped at.
• a green border indicates that the cell is being read as an instruction into to the IS registry.
• a light blue border means that the cell is the second part of a two byte instruction.
• an orange border means the cell is being used as an address in an two byte instruction. For registries it means that is is being used as part of an instruction.
• a gray border means nothing of significance is happening. It is the default border color.

Printing 1 2 3

The 8 instruction is very special: it is the only two byte instruction which directly does something with the adjacent cell. Which is printing the value which is in the adjacent cell.

All other two byte instructions will take the adjacent cell as the address to perform the instruction on.

So printing the numbers 1 to 3 can be done like this:

By simply putting an 8 before each number we print it. Whenever something is printed it shows up below in the PRINTER. You will have to pretend that it actually spits out a piece of paper.

Calculating 5 + 37

Say we want to sum two numbers and print the result:

Here is the rundown:

• We put the numbers we want add some distance away from the actual program. This makes things a little easier to read. So we put them in the last positions of the memory. These are locations 14 and 15.
• Next by using 9 we load the value from address 14 which is the value 5 into R0.
• Then by using 10 we load the value from address 15 which is the value 37 into R0.
• Now we perform the addition via the one byte instruction 1. This will override the value inside R0 to become 42, which is the sum of 5 and 37.
• Now that we have the answer we want to print it. This means that we have to put the value in R0 into a cell next to an 8 instruction. This is what calling 11 with address 8 does. It changes the 0 in location 8 into 42.
• Then the 8 on address 7 is performed printing the 42.
• Then it hits a 0 on location 9 so the program stops.

This program demonstrates that a value inside of a memory cell can either be data or code. The 8 on location6 is the argument of a two part instruction, but the 8 on location 7 is a print instruction. Two 8's but with a very different meaning.

Counting backwards from 10

Lets make it a bit more interesting by counting backwards from 10 using a loop. Loops require more planning to do right.

What happens is this:

• Like before we put the number 10 at the far end of the memory on location 15. This memory cell will contain the current number we are going to print. It should decrement by 1 every loop.
• First we must load up the value at address 15 into R0 using instruction 9. So we can perform the next step:
• Which is decrementing R0 with one using instruction 5
• Using instruction 11 we write the vale of R0 into address 15. This prepares cell 15 for the next iteration of the loop.
• Next we also place the value of R0 using 11 into address 8 so we can print it.
• After the print we use two byte instruction 15, followed by a 0 on location 10, to jump to address 0 if R0 is not 0.
• We are now back at step 1 which is repeated until step 6 produces an R0 which is 0. In that case the 0 in position 11will terminate the program.

Creating a function

A function or a procedure is a bit of code which does a certain useful thing. Since we have no dedicated syntax we will have to do a lot more manual work to create a function, and adhere to strict rules.

The rules for creating a function are:

• Reserve a range of memory for the function. Make sure the other programmers do not muck about in this region of memory.
• Make sure that at the end of the function the values of R0 and R1 are restored the the values they had at the start of the function call.
• Write the result of the function to a specific agreed upon memory cell.
• At the end of the function make sure you jump back to the return cell, this should be provided by the caller, at an agreed upon memory cell.

This means that before calling a function the caller must:

• Write all the arguments for the function into the cells the function expects to be filled. For example if the function multiplies two numbers, two numbers need to be written to two cells in memory.
• You must write the return address into the memory cell which will act as a return value.
• Finally when the function is complete you probably want to do something with the results.

The way the caller and function communicate with each other is by both looking at a region of memory which contains: all arguments, return values, and return points. This area is called a frame.

The frame allows us to separate the caller and the function. This allows us to refactor the function without having to update all callers, as long as the function frame remains the same memory locations.

Lets write a function which multiplies two numbers:

The gist of the function is this: when you do not have multiplication instruction, you must write a loop instead. Remember 5 * 4 is the same as doing 5 + 5 + 5 + 5. So the function just uses addition in a loop to do the multiplication.

Lets start with defining the frame which the caller and function use to communicate with each other: we will use cell 88 to cell 91.

• 91 is the right side argument for the multiplication operation
• 90 is the left side argument for the multiplication operation
• 89 will store the result of the calculation.
• 88 will act as the return point for when the function is done.

Now that we know what the frame of our function is it is time to write the function:

• Our function starts at memory location 28. First we want to store the values of R0 and R1 so we can restore them later. This is done by executing 11, 69, 12, 70. The locations64 and 65 were chosen because they where at the very end of the function.
• Now we read the left and right side of the multiplication operator into R0 and R1 via: 10, 90, 9, 91
• Since we are going to make a loop, we need to stop at some point. This is what address 64 represents, I'll call it the counter, when the counter hits zero we should stop. We write the value of R0 into the counter via: 11, 64.
• Position 38 represents the start of the loop. We will jump back into this position if we are not finished yet. Each time we must load in the counter into R0 from cell 64, this is done by executing: 9, 64
• Now we check if we are done, we are finished when the counter is zero. Using instruction 14 we jump to position 54 when done. Position 54 starts the "return" routine.
• When the loop is not finished we execute: 9, 89 this loads the value of cell 89 into R0. Cell 89 represents the accumulator / return value of our function.
• Once the accumulator is loaded in we can perform instruction 1 to sum op R0 and R1
• Now we must write the value back into the accumulator cell by calling: 11, 89. So the next loop knows where we left off.
• Then the following is executed: 9, 64 this loads the counter back into R0. Next we decrement the counter using 5, and write it back using 11, 64
• Now we jump back to cell 38 for the next iteration of the loop via 13, 38
• When the loop finishes it will jump to cell 54: the return routine.
• For our exit we need to know where to go to next. Which is why we do 9, 88 to load the return point into R0 then we write it into 63 using 11, 63.
• Now it is time to restore the registers to their previous values, as all good functions do. This is done via: 9, 69, 10, 70
• Now finally via 13 we jump back into whatever we wrote to cell 63 in step 12.

Now that we have a function we want to call it, first some definitions:

• Cell 21 is the first parameter for the multiplication function
• Cell 22 is the second parameter for the multiplication function
• Cell 23 will store the jump back point, so the function knows where to jump back to, after it is finished.

The process starts at location 0, and I think by now you can figure it out yourself. The gist is that we put all the values into the correct place in the frame, then jump into the function, then read the result and print it.

If you find a way to write the function using less memory, please let me know. So I can add your solution to the post.

Conclusion

First I'm glad that I don't work on such a low level. Writing the last example took me a good 8 hours. Getting it to work is one thing, but optimizing the program is another.

My process was that I start writing the function first using a lot of extra memory space. It is very difficult to know how much space you are going to need in advance. For example the space between the "return routine" and the "loop" is difficult to guess.

Also pen and paper is your friend, I don't think I've ever done so much up front thinking about writing such a simple function. My pen and paper process looks a lot like assembly, comments followed by instructions.

After the function worked I started trimming the amount of cells, so no space was left between the "return routine" and the "loop".

During the writing of the explanation of the function, I discovered two useless two byte instructions. Then I realized that there is a simple trick to see if instructions are useless: replacing them with 7's for a beep. The program made more beeps but otherwise still printed 20. This meant I could remove them without affecting the result. However this which meant moving around cells in the function, which is a pain.

But the good news was this: due to having a frame, only the function had to be rewritten, not the caller. Which was proof to me that having a frame is a useful abstraction, even if it costs a bit more memory.

I hope you enjoyed this trip down my memory lane.

I'll put the making of the emulator using React and TypeScript up when it is ready.

Share on