Indirect Memory, Branching, and If/Else in X-Toy

Code along video

Learning objectives

So far, our X-Toy programs run in a straight line: the program counter starts at address 10 and moves forward one address at a time until it hits a halt. In this code along, we first add two more memory operations, load indirect and store indirect, which read and write RAM at an address held in a register. We then meet the instructions that let a program branch: jump zero, jump, and jump positive. With them, we will translate an if/else statement into X-Toy, and we will see how to test whether one number is greater than another by subtracting.

Code along summary

Setup

We continue in Visual X-TOY from the previous code along; there is nothing new to install.

Load indirect and store indirect

Recall the load instruction, opcode 8. In the word 8488, the 8 means load, the next hex digit 4 is the destination register R[4], and the final two hex digits 88 are the memory address to read. So 8488 copies whatever is stored at address 88 into R[4]. The address is written directly into the instruction.

Sometimes we would rather keep the address in a register. Perhaps R[8] holds the value 006E, and we want to treat that value as a memory address. This is what load indirect does. Its opcode is A (binary 1010, which is 8 + 2 = 10). The second hex digit is the destination register d, the third hex digit is ignored, and the last hex digit names a register t. The instruction looks inside R[t], treats its value as an address, and copies the contents of RAM at that address into R[d]. For example, A208 sets R[2] equal to the value in memory at the address stored in R[8].

Bits 15 to 12	Bits 11 to 8	Bits 7 to 4	Bits 3 to 0
1010 = A (load indirect)	0010 = R[2] (d)	0000 (ignored)	1000 = R[8] (t)
1011 = B (store indirect)	0010 = R[2] (d)	0000 (ignored)	1000 = R[8] (t)

We have seen this idea before in the course. When we passed a list, a dictionary, or an object of a class we defined to a function, the function received a reference to the data, which is why it could change the underlying object. A register holding a memory address is the same idea at the lowest level: the register stores a reference to something in RAM. Some languages call this a pointer. It also hints at how we could walk through an array stored in memory, by keeping the address of the current element in a register.

Just as we can load indirectly, we can also store indirectly. Store, opcode 9, writes a register to an address written in the instruction, so 9488 writes R[4] to address 88. Store indirect, opcode B, instead writes R[d] to the address stored in R[t]. The word B208 looks in R[8] to find where to put the value, and then stores R[2] there.

Opcode	Slide mnemonic	Visual X-TOY pseudocode	Example
8	LOAD Rd, addr	R[d] <- mem[addr]	8488: R[4] <- mem[88]
9	STORE Rd, addr	mem[addr] <- R[d]	9488: mem[88] <- R[4]
A	LOAD.I Rd, Rt	R[d] <- mem[R[t]]	A208: R[2] <- mem[R[8]]
B	STORE.I Rd, Rt	mem[R[t]] <- R[d]	B208: mem[R[8]] <- R[2]

We will not write much code with these two instructions, but they bring us to twelve operations. Every one of them reads from memory, manipulates registers, or writes back to memory.

The missing ingredient: branching

This leaves us with a quandary. We want to write functions, for loops, and if statements, but nothing in our computer lets it make a choice. When we run a program, the program counter starts at 10 and simply moves to 11, 12, 13, and so on. What we need is for the program counter to be able to branch: to test some condition about the state of the machine and then go one way or another.

This idea was revolutionary in the early days of computer science, and it is so inherent to modern programming that we took it for granted when we first learned about if statements. Think of a choose your own adventure book: you start on page 1, and on page 2 you have to decide whether to turn to page 47 or page 91. The decision a program makes is not intelligent, since it is entirely determined by the state of the machine, but it means that different inputs can lead to different outputs.

Jump zero and jump

The first branching operation is jump zero, opcode C (binary 1100, which is 8 + 4 = 12). As usual, the second hex digit names a register d, and the final two hex digits give a memory address. If R[d] is equal to zero, the program counter is set to that address; otherwise, the program counter increases by 1 as normal. For example, say that we are at address 3A and it contains C488. If R[4] is zero, the next instruction executed is the one at address 88; we skip right past 3B. If R[4] is not zero, we carry on to 3B.

The second is plain jump, opcode E (binary 1110, which is 8 + 4 + 2 = 14). It sets the program counter to whatever value register d contains, with no condition attached, and the last two hex digits are ignored. So E4XX sends execution to the address stored in R[4].

Opcode	Slide mnemonic	Visual X-TOY pseudocode	What it does
C	JMP0 Rd, addr	if (R[d] == 0) goto addr	If R[d] is zero, set the PC to addr; else increase the PC by 1.
E	JUMP Rd	goto R[d]	Set the PC to the value stored in R[d].

Implementing if/else in X-Toy

Let’s use these operations to implement the following if statement, in which we think of r3 and r4 as registers. Recall that printing a register means storing it to the special address FF.

if r3 == r4:
    print(r3)
else:
    print(r4)

How can we check equality? One way is to subtract the two registers: if the difference is zero, they are equal, and otherwise they are not. Here is the X-Toy program, which starts at address 20.

20: 7526   R[5] <- 0026
21: 2243   R[2] <- R[4] - R[3]
22: C225   if (R[2] == 0) goto 25
23: 94FF   write R[4]
24: E500   goto R[5]
25: 93FF   write R[3]
26: 0000   halt

We will come back to line 20 in a moment. Line 21, 2243, sets R[2] equal to R[4] minus R[3] (subtracting in the other order would work just as well). Line 22, C225, then checks whether R[2] is zero. If it is, the two registers are equal, and we jump to line 25, where 93FF prints R[3] before the program halts on line 26.

If R[3] and R[4] are not equal, then R[2] is not zero, the jump does not happen, and we carry on to line 23, where 94FF prints R[4]. But now we have a problem: we do not also want to print R[3] on line 25. We need to jump over that line to the halt on line 26.

The jump instruction E sends the program counter to the address stored in a register, so before we can use it, some register must already hold 26. That is why line 20 loads 0026 into R[5] before we do anything else, and why line 24, E500, jumps to the address in R[5]. Programming in X-Toy requires us to be very precise and to plan ahead, all the way down to knowing which address we will need to jump to before we get there.

Even though our program is just a string of hex numbers, it still represents our if and our else.

Lines	Role	What happens
20	setup	Store the address 26 in R[5] so that we can jump there later.
21 to 22	condition	Compute R[4] - R[3]; if it is zero, the condition is true, so jump to 25.
23 to 24	else part	Print R[4], then jump to 26 to skip the then part.
25	then part	Print R[3].
26	end	Halt.

To run this program in Visual X-TOY, keep in mind that execution starts at address 10, and that the slide program never gives values to R[3] and R[4]. We can add three lines at the top that read the two registers from standard input and then jump to line 20. Since R[0] is always zero, C020 is a handy way to jump unconditionally to an address written in the instruction.

10: 83FF   read R[3]
11: 84FF   read R[4]
12: C020   goto 20

Entering 0007 and 0005 takes the else branch and prints R[4], while entering 0007 twice takes the then branch and prints R[3].

stdin: 0007 0005    output: 0005
stdin: 0007 0007    output: 0007

If R[3] and R[4] are equal, then printing R[3] is the same as printing R[4], so all our program really does is print R[4]. That’s fine: we are using a make believe if statement to show how branching works, and we will soon do something that is not make believe.

Jump positive and testing greater-than

Our final jump is jump positive, opcode D (binary 1101). It is exactly like jump zero, except that it checks whether R[d] is positive instead of whether it is zero. If it is, the program counter is set to the address in the last two hex digits; otherwise, the program counter increases by 1. For example, D488 jumps to address 88 if R[4] is positive.

Opcode	Slide mnemonic	Visual X-TOY pseudocode	What it does
D	JMPP Rd, addr	if (R[d] > 0) goto addr	If R[d] is positive, set the PC to addr; else increase the PC by 1.

Jump positive gives us a way to compare two numbers. Consider the following if statement.

if r3 >= r4:
    print(r3)
else: # r4 > r3
    print(r4)

The X-Toy program looks very similar to the previous one. We again load 26 into R[5] and set R[2] equal to R[4] - R[3]. If this difference is positive, then R[4] is bigger than R[3], which is the else case, so jump positive on R[2] sends us to line 25, which prints R[4]. If the difference is not positive, then R[4] is not bigger than R[3], so the condition r3 >= r4 holds; we fall through to line 23 and print R[3], and then line 24 jumps over the else part to the halt.

20: 7526   R[5] <- 0026
21: 2243   R[2] <- R[4] - R[3]
22: D225   if (R[2] > 0) goto 25
23: 93FF   write R[3]
24: E500   goto R[5]
25: 94FF   write R[4]
26: 0000   halt

Lines	Role	What happens
20	setup	Store the address 26 in R[5].
21 to 22	condition	Compute R[4] - R[3]; if it is positive (the condition is false), jump to 25.
23 to 24	then part	Print R[3], then jump to 26 to skip the else part.
25	else part	Print R[4].
26	end	Halt.

With the same three-line prelude at address 10, entering 0009 and 0002 takes the then branch and prints R[3], and entering 0002 and 0009 takes the else branch and prints R[4]. When the two values are equal, the difference is zero, which is not positive, so we print R[3], as r3 >= r4 requires. In every case, the program prints the larger of the two numbers.

stdin: 0009 0002    output: 0009
stdin: 0002 0009    output: 0009
stdin: 0007 0007    output: 0007

Looking ahead

We now have fifteen of X-Toy’s sixteen operations, including the ability to make decisions. X-Toy can already multiply by a power of two with a left shift, but what if we want to multiply by three, or by any number? In the next code along, we will use jumps to build multiplication as repeated addition, which will give us our first loop, and then we will introduce jump and link so that we can write functions.