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

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. If we can’t rectify the problem, we may be faced with a total loss of the vehicle and mission.

That’s why we need your help.

Classified briefing

Welcome to the Situation Room. Thank you for coming in at such short notice. Do you have coffee? Okay, then let’s get right to it, because time is a factor.

As you know, the Trailblazer mission is a multi-billion-dollar international scientific collaboration to send a lightsail-powered robotic probe to the Proxima Centauri star system, a journey of about 20 years. The tiny spacecraft, about the size of a smartphone, was launched 15 years ago on a drive beam powered by giant phased laser arrays located in over 40 countries, and reached its coasting velocity of 20% light speed within about 10 minutes, crossing the orbit of Mars half an hour after launch and heading rapidly for the outskirts of the solar system.

For the last 15 years Trailblazer has been sailing serenely through interstellar space, sending back valuable science data and engineering telemetry, as the mission team tested, checked, and rechecked all the onboard instruments in preparation for the probe’s flyby through the Prox Cen system and its many interesting exoplanets.

Then everything went dead.

The machine stops

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.

Racing against time

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 sounds 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 we’ve set up starter repos for you for a couple of popular languages:

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

Sebastián Alvarez has kindly provided a starter repo in TypeScript, too:

ts-r8-challenges

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 those provided, you could look at one of these repos to get the general idea, and start by implementing 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.NewCPU() 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.

The soul of a new machine

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: the programming language that tells it what to do.

Machine language consists of commands that mean things 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.

It’s much lower-level than a programming language like Rust: it deals directly with the hardware on the chip. All the same, there are many similarities, and programs in Rust, Go, and other “high-level” languages are usually compiled—automatically translated—into the equivalent machine code, an executable 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 is that the register will contain the value 4—at least, it will if everything’s working correctly, which it may not be on the Trailblazer spacecraft, but that’s what we’re here to find out.

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 basically 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?)

A trip down memory lane

Notice that in order to work out the final result of this program, you had to hold a couple of intermediate results in your head. The CPU does the same thing, by storing them in its working register, which is like your short-term memory. It’s a physical device that lives on the chip itself, and we’ll see how it works in more detail later on, but for now we’re just concerned with the fact that we can store numbers in it.

To that point, we know that R8 programs are also a sequence of numbers, but unlike the data in the working register, they’re not stored on the chip. So where do these numbers actually live in the computer, and how does the CPU know where to find them?

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 Lane, Computerville”. What lives at that address? A single piece of data—that is, a number.

What that number actually means is irrelevant as far as the memory device is concerned. It might be an opcode that’s part of a machine code program, like 16 for a ld instruction. It might be the operand for such an instruction, like the 10 in ld 10. It could be the brightness value of the top left pixel in a camera image of Jupiter. Or it might just be zero, because no meaningful data has been written to that location yet. Whatever the data is in location number N, the CPU can retrieve it by asking the memory for the contents of address N.

Getting nowhere fast

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.

Saying ‘the next instruction’ implies that the CPU has 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 count 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 create a freshly-initialised CPU. Next, we’ll load the program into its 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. Since pc starts at 0, let’s use memory address 0.

Now we call Step, which will do the following:

Read the contents of memory at the address held by pc (which is currently 0).
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 TestStepIncrementsPC test, which does the following:

Creates a new CPU.
Stores the nop instruction at address 0.
Calls Step() on the machine.
Tests that the machine’s pc register contains the value 1. If not, the test fails with a message like "want pc == 1, 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 if you like, 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.

You’ll find the TypeScript solutions to each challenge in Sebastián’s ts-r8-solutions repo.

It doesn’t matter if you’ve implemented Step in a slightly different way to these example solutions, 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.

The point is that your program accurately models how the real computer works. If it’s executing a program that tells it to do nothing, it obediently does nothing—four million times a second!

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 = 1
}

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 1 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 TestStepIncrementsPC 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 1, as the test already checks. But after the second Step, it should be 2.

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 (test, implementation), or the Rust solution (test, implementation).

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. Here’s a homework problem for you while you’re eagerly awaiting the next instalment.

GOAL: Define named constants for OpHALT (0) and OpNOP (1). Prefixing the names with Op helps remind readers what kind of value they are.

Refactor the tests and code to use these constants (for example, in the Step test, we should set the contents of address 0 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.

If you get stuck, tune in next time to see the suggested solutions.

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.