You are at the entrance of an abandoned coal mine. Strange squeaky sounds come from the passage at the north end. You may also escape to the west.

> go north

Ominous.

Code for this episode can be found in https://github.com/ericlippert/flathead/tree/blog15.

Last time we managed to get as far as the fifth instruction, a je (jump-if-equal) instruction.

Here is a question we did not adequately explore when we were discussing how to decode an opcode: how many ways are there to encode the first byte of any one of the instructions in the “2OP” family of instructions? Let’s look just at je, which is the very first 2OP opcode. The following bit patterns are legal:

0 0 0 0 0 0 0 1 - long form, two small constant operands
0 0 1 0 0 0 0 1 - long form, small constant and variable operands
0 1 0 0 0 0 0 1 - long form, variable and small constant operands
0 1 1 0 0 0 0 1 - long form, two variable operands
1 1 0 0 0 0 0 1 - variable form, 2OP opcode

The first byte of any 2OP instruction has five possible choices for the top three bits; the bottom five bits give the 2OP opcode. This explains why there are 256 possible values for a byte, but only 92 actual non-extended bytecodes. There are only 32 possible 2OP instructions, but they consume five times that many possible first bytes. To justify the expense, a 2OP code had better be commonly used in long form. There are numerous two-operand instructions that were put in the VAR bucket rather than take up five bytecodes.

If you want to give a long constant operand to a 2OP instruction you’ve got to encode it using the variable form, because recall that the types of the operands come in the following byte. But there is room in that type byte for type of four operands, not two. This leads us to the somewhat bizarre conclusion that it is possible to have “binary” opcodes that take some number other than two operands.

For the je instruction, this is legal and happens in practice. je is extremely common in long form, so it would waste memory to put it in the VAR opcode bucket. But it is useful for it to take multiple operands in some cases, so there you go. je may not take one operand. If it takes two, three or four then the branch condition is that the first operand be equal to any of the subsequent operands.

Let’s make implementations for all the simple math conditional branch instructions, and while we’re at it, let’s do unconditional jump as well. All the conditional branch instructions have handlers which simply compute values. Since the jump instruction does not have a conditional branch, I count it as one of the “weird” instructions which makes an unusual change to control flow. So it gets its own special handler:

let handle_je2 a b interpreter =
  if a = b then 1 else 0

let handle_je3 a b c interpreter =
  if a = b || a = c then 1 else 0

let handle_je4 a b c d interpreter =
  if a = b || a = c || a = d then 1 else 0

let handle_jl a b interpreter =
  let a = signed_word a in
  let b = signed_word b in
  if a < b then 1 else 0

let handle_jg a b interpreter =
  let a = signed_word a in
  let b = signed_word b in
  if a > b then 1 else 0

let handle_jz a interpreter =
  if a = 0 then 1 else 0

let handle_jump offset interpreter instruction =
  let offset = signed_word offset in
  let target = Instruction.jump_address instruction offset in
  set_program_counter interpreter target

Easy! And of course I have added calls to these in the big switch.

If we run Mini-Zork now we crash on the ninth instruction:

37d9: call 3b36 3e88 ffff ->sp
3b3d: call 3b4a local0 ->local2
3b55: add g16 b4 ->local2
3b59: add g16 g35 ->local3
3b5d: je local3 local2  ?~3b77
3b61: sub g35 06 ->g35
3b65: jz local1  ?3b6c
3b6c: add g16 g35 ->local4
3b70: storew local4 02 local0

storew and related instruction storeb take an address, an index and a value. Basically this is writing to an array of the appropriate type. We can trivially implement those and their corresponding loadw and loadb instructions:

let handle_loadw arr idx interpreter =
  let arr = Word_address arr in
  let addr = inc_word_addr_by arr idx in
  Story.read_word interpreter.story addr

let handle_loadb arr idx interpreter =
  let arr = Byte_address arr in
  let addr = inc_byte_addr_by arr idx in
  Story.read_byte interpreter.story addr

let handle_storew arr ind value interpreter =
  let arr = Word_address arr in
  let addr = inc_word_addr_by arr ind in
  { interpreter with story = Story.write_word interpreter.story addr value }
  
let handle_storeb arr ind value interpreter =
  let arr = Byte_address arr in
  let addr = inc_byte_addr_by arr ind  in
  { interpreter with story = Story.write_byte interpreter.story addr value }

The spec does not say whether the pointer arithmetic here uses a signed or unsigned index; I’m going to assume unsigned.

And now when we run Mini-Zork:

37d9: call 3b36 3e88 ffff ->sp
3b3d: call 3b4a local0 ->local2
3b55: add g16 b4 ->local2
3b59: add g16 g35 ->local3
3b5d: je local3 local2  ?~3b77
3b61: sub g35 06 ->g35
3b65: jz local1  ?3b6c
3b6c: add g16 g35 ->local4
3b70: storew local4 02 local0
3b75: ret local4
3b43: storew local2 01 local1
3b48: ret local2
37e2: storew sp 00 01
37e7: call 3b36 4e50 28 ->sp
3b3d: call 3b4a local0 ->local2
3b55: add g16 b4 ->local2
3b59: add g16 g35 ->local3
3b5d: je local3 local2  ?~3b77
3b77: loadw local3 02 ->sp
3b7b: je sp local0  ?~3b81
3b81: add local3 06 ->local3
3b85: jump 3b5d
3b5d: je local3 local2  ?~3b77
3b61: sub g35 06 ->g35
3b65: jz local1  ?3b6c
3b6c: add g16 g35 ->local4
3b70: storew local4 02 local0
3b75: ret local4
3b43: storew local2 01 local1
3b48: ret local2
37ef: call 3b36 4792 96 ->sp
3b3d: call 3b4a local0 ->local2
3b55: add g16 b4 ->local2
3b59: add g16 g35 ->local3
3b5d: je local3 local2  ?~3b77
3b77: loadw local3 02 ->sp
3b7b: je sp local0  ?~3b81
3b81: add local3 06 ->local3
3b85: jump 3b5d
3b5d: je local3 local2  ?~3b77
3b77: loadw local3 02 ->sp
3b7b: je sp local0  ?~3b81
3b81: add local3 06 ->local3
3b85: jump 3b5d
3b5d: je local3 local2  ?~3b77
3b61: sub g35 06 ->g35
3b65: jz local1  ?3b6c
3b6c: add g16 g35 ->local4
3b70: storew local4 02 local0
3b75: ret local4
3b43: storew local2 01 local1
3b48: ret local2
37f7: store 10 2e

HOLY GOODNESS we are doing amazingly well here! Calls and returns are working seamlessly, we’re adding and subtracting numbers and writing stuff into arrays and the whole bit.

Next time on FAIC: the store instruction is somewhat unusual.