How to Write Emulator – Fetch Decode Execute Cycle

How a Redcode “CPU” works

The CPU is a machine, it follows a basic mechanism to the beat of an external clock. In the case of a Redcode simulator, every tick of the clock causes the CPU to go through what is called the Fetch-Decode-Execute (FDE) cycle. All three steps happen in one clock tick. In real hardware things get a bit more … abstract … understanding this is left as an exercise for the reader.

The Redcode simulator contains three registers

• Current instruction register
• Source register
• Destination register

Most of the instructions are written to perform some sort of operation on data in the source register, and apply or store it in the destination register.

Every instruction contains two opcodes called “a” and “b”. So the “ADD” instruction’s “a” opcode will contain the location of the first number, and the “b” opcode will contain the location of the second number. “ADD” will then add the “a” and “b” opcodes from the source register to the “a” and “b” opcodes of the destination register, for example.

Fetch

This is where the instruction to be executed is fetched from memory and stored within the CPU’s registers. The instruction is located using the instruction pointer (also known as the program counter).

Want to crash your program? Make the CPU attempt to fetch an instruction from the wrong part of memory.

Decode

This is where the instruction is looked at, in order to work out what to do. The opcodes’ addressing modes are decoded. Is the opcode a pointer, piece of data or something else? Want to crash your program some more? Make the CPU attempt to decode something that isn’t an instruction.

Execute

This is where the instruction is performed. And again, if you want to crash your program, just make the CPU attempt to execute something that’s invalid. Like dividing by zero.

Calculating addresses

Part of the FDE cycle is to calculate the memory addresses for each instruction. Each opcode has an addressing mode, and allows for some interesting self-modifying code if done correctly.

Depending on the operand and its addressing mode, the data being used might be in a nearby memory location, be an immediate piece of data, or be modified after calculating its address. Yes, the act of fetching an instruction can cause that instruction to be modified.

All addresses are relative to the current instruction pointer. A redcode program is, by its own design, relocatable and has no way of knowing what memory location it is in, nor can it directly access a specific location in memory. They’re all offsets from the current instruction.

Redcode contains the following addressing modes for each operand

• Immediate – This operand is the data
• Direct – Treat the operand’s value as a pointer offset from here
• Indirect – This is a pointer-to-a-pointer
• Pre Decrement indirect – Pointer-to-a-pointer, but first decrement the value
• Post Decrement indirect – Pointer-to-a-pointer, but after dereferencing it, decrement its value and update it in the core

It’s a bit crazy really, but means for loops and pointers can be used with a short and compact set of instructions.

Understanding this was one thing, making it work was an entirely different problem! Here’s the first time I got the simulator actually executing code correctly

Redcode FDE Cycle

The FDE cycle in Redcode is quite rigid and defined, it has to be so that programmers can understand how their programs will run. Redcode has a few extra parts to make things a little more exciting too.

• More than one program runs at once
• Each program can have threads

However to prevent the sorts of madness associated with multitasking and multiprogramming, the programs and their threads are run one after the other. One instruction from each is run in turn, every cycle.

The code goes something like this (without threading, I’ve not implemented that yet!):

For each warrior:
	If warrior is alive:
		Fetch next instruction, store in instruction register
		Decode both opcodes, storing them in their registers
		Increment the instruction pointer
		Execute the instruction

And here’s a recording of the simulator correctly running more than one warrior at once