Aug 25

Aug 25 Welcome to the machine: emulating a CPU

Ladies and gentlemen we are floating in space — *Artwork by* *Ashley McNamara*

Inspired by surprisingly real events.

Emergency in space

Welcome to the Situation Room, YOUR NAME. Thank you for coming in at such short notice. Eleven hours and sixteen minutes ago, our scientists lost contact with the Trailblazer 1 probe, en route to Proxima Centauri. Since then we’ve been trying without success to re-establish contact with the spacecraft’s onboard computer. Unless the fault can be rectified, and soon, we are facing a total loss of the vehicle and mission.

The binary data modulated onto the optical carrier signal suddenly changed from valid telemetry to a meaningless string of 1s. Since we’re still receiving the signal, we know the spacecraft is intact, powered, and with its communication laser aimed correctly towards Earth. Doppler radar data indicates that its trajectory is unchanged, making it unlikely that the craft was hit by a meteorite or space debris. It’s just no longer able to talk to us.

The problem appears to be localised to a subsystem known as the RTFM (Remote Telemetry and Flight Management) computer, responsible for the communications link between the spacecraft and Earth. Engineers are speculating that its memory may have been corrupted by a cosmic ray impact, causing the software to malfunction.

Unfortunately, it seems that while the probe’s computers and flight software were thoroughly documented before launch, that documentation is no longer available, due to… well, let’s just say mistakes were made. We also no longer have the source code or any way to reproduce it. It seems that these files were deleted when one of our cloud drives ran low on space, and everybody thought some other department had a copy.

Emulator than you think

That’s where you come in. We urgently need your help to investigate the RTFM software issue. Specifically, the first thing we need is a program that can execute code written for the spacecraft’s onboard computer. A program like this is called an emulator: it acts like a model of the computer’s central processing unit (CPU), and will enable us to write and test code before uploading it to the RTFM for real. Time is running out, and there’s no room for mistakes: a botched software update could put the probe out of action for good.

You might also have heard the term virtual machine, meaning not “nearly a machine”, but something more like “not actually a machine, but behaving like one”. Emulator, virtual machine, same thing.

It may sound complicated, but emulators are actually fairly easy to write, once you understand how the emulated machine (the guest) works. The RTFM computer uses a relatively small and simple CPU, compared to the one in your computer (the host machine).

Booting up

This CPU is called the R8, and to emulate it, you’ll be writing the necessary code to implement the R8’s instruction set: the commands it understands. You can use any programming language you like to do this, but I have starter repos set up for a couple of popular languages:

go-r8 (Go)
rust-r8 (Rust)

These repos will give you the basic structure of the project, plus some tests and stub functions to get you up and running, but after that it’s entirely up to you what to do. So if you want to use a language other than Go or Rust, you could look at one of these repos to see what’s there, and start by reproducing it in your language of choice.

The first thing the emulator needs is a properly-initialised CPU, ready to work. So, in the Go repo, for example, there’s an r8.New() function that returns a CPU in its default initial state, which is specified by a test. In the Rust repo you’ll find an implementation of Default for the CPU that does the same thing.

The test and the constructor function are already provided in the starter repo, so your first challenge is a straightforward one:

GOAL: Run the test and make sure it passes.

In Go, for example, run go test, or in Rust run cargo test.

Talking my language

The CPU is the heart of any computer: it does the data processing, executes the software, and controls every other part of the system. Usually made up of many transistors and other electronic components on a silicon chip, each different model of CPU understands a different machine language. This consists of commands like “add this number to this other number”, “read the value at this memory address”, “jump to the program starting at this other address”, and so on.

Machine language is much lower-level than a programming language such as Go or Rust: it deals directly with the hardware on the chip. All the same, there are many similarities, and programs in Go and other high-level languages are usually compiled—translated—into the equivalent machine code—program in machine language.

Putting two and two together

For example, here’s a short program that a CPU such as the R8 might execute:

ld 2
add 2

Can you guess what it does? That’s right, it adds 2 and 2. The ld (load) instruction puts a number into the CPU’s working area, or scratchpad (known as a register). In this case, it loads the number 2.

Then the add instruction adds another number to what’s already in the register. In this case, it adds the number 2. The result, if everything’s working correctly, is that the register should contain the value 4.

Cracking the code

The R8 doesn’t understand words like ld or add, though: those are mnemonics (from the Greek for “remember”) designed to be easy for humans to read and write. Actual machine language just consists of numbers.

Every R8 instruction has its own unique identifying number: instruction number 1, instruction number 2, and so on. These are called opcodes (for “operation codes”). For example, the opcode for ld is 16, and the opcode for add is 80. (Don’t worry about why these particular numbers; they’re essentially arbitrary, like phone numbers.)

So the “add 2 and 2” program we just saw actually looks like this in machine language:

16 2
80 2

You can see why mnemonics were invented! It would be awfully difficult to write programs using only numbers, even though that’s the language that the R8 (like all CPUs) actually speaks. Instead, we use the symbolic names like add and ld, giving us what’s called assembly language (I’m not sure why: maybe because writing programs is a bit like putting together IKEA furniture?)

We know that R8 programs are a sequence of numbers, but where do these numbers actually live in the computer, and how does the CPU know where to find them?

Cycling along

Another important component of every computer is memory: also a silicon chip, but a different kind of chip from a CPU. Its job is not to do anything, but just to store numbers: opcodes, operands, science data, images, or anything else we want the computer to handle.

Memory is arranged very simply: it’s just a sequence of locations—places you can store a number—each with its own address, which is also a number. Think of memory addresses as being just like postal addresses. Address 66, for example, is like “Number 66, Memory Street, Computerville”. It contains a number, which may or may not be an opcode for a machine instruction, or an operand, or just zero because it’s currently unoccupied.

Even though a CPU might seem complicated, and in detail it is, it’s very simple in principle. It just does one thing, over and over, forever:

Fetch the next instruction from memory
Execute it.

It’s called the fetch-execute cycle. And that’s all your emulator needs to do: fetch the next instruction, and execute it. Let’s take the first part first.

Count on me

Saying ‘the next instruction’ implies that we have some way of remembering where we currently ‘are’ in memory. That is to say, we need a CPU register that holds the memory address of the next instruction to execute.

This is what the pc register is for (PC stands for ‘Program Counter’, which is the traditional name for this register). It keeps track of where the CPU is in the program.

Suppose pc holds 0, for example. If the CPU were to start running now, the first thing it would do would be to read the contents of memory address 0 (we say that pc points to this address). It will interpret this as an opcode, and do whatever that opcode tells it to do. Afterwards, it will increment pc (add 1 to it), and the cycle begins again: the CPU will read the contents of memory address 1, interpret it as an opcode, and… well, you know the rest.

And that’s what your emulator will do, too: perform this fetch-execute cycle continuously. For testing and debugging purposes, though, we’ll start by just fetching and executing one instruction at a time. And let’s choose a very easy instruction to implement: the nop instruction (short for “no operation”). It does nothing!

(Why have such an instruction in the first place, you might ask? Good question, and not every CPU has nop, but the R8 does. One use for it is just to pass the time, for example if you wanted the machine to wait for a specified delay period without doing anything. Anyway, it’s a good choice for our first emulated instruction.)

Stepping out

We’ll need a way for users to tell the machine to do one iteration of its fetch-execute cycle: fetch the next instruction from memory at the address held by pc, execute it, and return. So there’s a method on the CPU named Step() that will do this.

Let’s see how we might use it to execute the nop instruction. First, we’ll call New to create a freshly-initialised CPU.

Next, we need to load the program into memory. It’s only one instruction long, so we just need to put the opcode for the nop instruction (which is 1) into some memory location. We could use 0, but let’s have the program start at address 256 instead, to make things more interesting. And we’ll set pc to 256 so that it’s pointing at this instruction.

Now we call Step, which will do the following:

Read the contents of memory at the address held by pc (which is currently 256).
Interpret that value as an opcode, and do what it instructs (the value will be 1, which is the opcode for nop, so we do nothing).
Increment pc (so that the CPU will be ready to fetch the next instruction on the next call to Step).

So the upshot of all this is that if you call Step() on a machine with pc pointing to a nop instruction, the state of the machine should be unchanged after it returns except that the pc register should hold a value one higher than before.

Let’s find out!

GOAL: Uncomment and run the TestNopInstructionIncrementsPC test, which does the following:

Creates a new CPU.
Stores the nop instruction at address 256.
Sets the pc register to 256.
Calls Step() on the machine.
Tests that the machine’s pc register contains the value 257. If not, the test fails with a message like "want pc == 257, got ..."

This test will not pass yet, because the Step() method currently does nothing. Over to you to fix that!

GOAL: Write the code in Step needed to make this test pass. You don’t need much!

HINT: You can solve this the “malicious compliance” way, doing literally what the test asks for and no more. Right now the test is only concerned with the value of pc after calling Step. We’ll extend the test later, of course, so if you want to get ahead a little, you could read the contents of memory at the address held by pc and use something like a switch statement (in Go) or a match expression (in Rust) to decide what to do, as well as updating the value of pc.

SOLUTION: If you’re stuck, or if you want to compare your answer with one suggested version, have a look at my Go solution, or the Rust solution.

It doesn’t matter if you’ve implemented Step slightly differently, as long as the test passes. After all, the real CPU on the spacecraft implements it using transistors! It’s the behaviour that matters with an emulator, not the implementation.

When the test is passing, you can go on to the next section. Or if you like, pause for tea and biscuits, and some deserved self-congratulation: you’ve written a working CPU emulator! Admittedly, so far it has a rather restricted instruction set, but that can soon be fixed.

Keep on runnin’

Actually, if you were feeling lazy, you could have implemented Step by writing no more than this (in Go, for example):

func (cpu *CPU) Step() {
    cpu.PC = 257
}

You could do more, and if you have, that’s not wrong; but this is all the test actually requires. Since nop does nothing, and we know the instruction will be nop, we needn’t even read it from memory. And since the test only checks that pc is 257 afterwards, we can achieve that by just setting it to that value directly. It might look silly, but it takes the test seriously as the full specification of what it should do.

That’s fine, except we know the real Step method will need to do more than this. Let’s extend the test, then, so that we can no longer pass it the lazy way.

GOAL: Extend TestNopInstructionIncrementsPC to store two nop instructions in the first two memory locations, and call Step twice, checking for the correct value of pc after each call. After the first Step, pc should be 257, as the test already checks. But after the second Step, it should be 258.

Adjust Step to make the test pass.

HINT: Updating the test is easy, but if you took the lazy route to implementing Step, now you’ll have to work a little harder. Even so, you still don’t have to actually read the memory or look at the opcode—though you can if you want. The key thing as far as the test is concerned is that pc should increase by 1 every time Step is called.

SOLUTION: Have a look at my suggested Go solution, or the Rust solution.

Great. So your test is now executing the following (not particularly interesting, but valid) R8 program:

nop
nop

The halting problem

We could make this program longer, by adding more nops, but we’d also need to have the test call Step again for each one. If we want to execute programs of arbitrary length, we don’t really want to do it by repeatedly calling Step in the test.

We’d like a way to tell the CPU to just keep on fetching and executing continuously, as it does in reality. Of course the problem then is, what would make it stop?

In reality, CPUs generally don’t stop; they always have work to do, even if it’s just updating the screen, taking care of background jobs like backups, and waiting for you to press a key or click the mouse. But for test purposes, it’ll be very handy for us to have an instruction that tells the CPU to stop work for now, and return control to the emulator. Let’s call it halt (opcode 0).

Nopping and stopping

Now, what would halt do? Well, if you call Step, nothing special. After all, the machine already effectively halts after each Step call. But we’re saying we want a new method that, unlike Step, keeps fetching and executing continuously until it sees a halt instruction, at which point it returns. Let’s call this method Run (by which we really mean “run until halted”, of course).

What would a test for Run look like? You might like to think about this a bit and see if you can come up with something.

GOAL: Try writing a test for Run; don’t actually implement Run yet, just write an empty method. We want to make sure that the test fails when Run does nothing.

HINT: One way to do it would be to submit a program like this to the CPU:

nop
halt

If we called Run on this program, we should expect pc to increase by 2. If it increases by less, or not at all, then Run isn’t calling Step enough times. If it increases by too much, or never returns, then Step isn’t correctly detecting the halt instruction.

SOLUTION: Here’s my Go solution and Rust solution.

Okay, now let’s try to make the test pass!

GOAL: Implement Run.

HINT: We already have code that performs a single fetch-execute cycle, so we don’t need to duplicate it here. Run can simply call Step to do that work. The part that needs a little extra thought is this: how does Run know when to stop running? Or, equivalently, how can Step report the fact that it executed a halt instruction?

SOLUTION: Here’s my Go solution and Rust solution.

Again, you could solve this problem a completely different way than I have, and that’s fine. If the emulator correctly executes the test program, it’s correct.

The magic number

Now we can both Run and Step the machine, it’s time to do a little refactoring. We’re going to be referring to opcodes a lot in the emulator, so it’ll be helpful to define some constants for them, with informative names.

GOAL: Define a new constant for the halt opcode (you’ll find one is already defined for nop).

Refactor the tests and code to use these constants (for example, in the nop test, we should set the contents of address 256 to the named constant OpNOP, instead of a literal 1.) This makes it easier for readers (including our future selves) to see what the test is doing.

Use the tests to make sure that your refactoring didn’t break anything. Check that you also used the constants in your Step method. If you like, change the values of the two constants to something different (99 and 100, say) and make sure that everything still passes (it should). Don’t forget to change them back afterwards.

Great progress! Your emulator is now looking a lot more realistic: it can be single-stepped, or run until halted. All it needs now to be able to start writing useful programs is a few more opcodes, and we’ll get to those in the next part. If you want to skip ahead and learn a bit about the R8 architecture (and maybe implement more of its instructions), have a look at the RX82 project, which uses it to emulate a fantasy retro 8-bit computer from an alternate 1982.