Mine entrance

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 operands0 0 1 0 0 0 0 1 - long form, small constant and variable operands0 1 0 0 0 0 0 1 - long form, variable and small constant operands0 1 1 0 0 0 0 1 - long form, two variable operands1 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 0let handle_je3 a b c interpreter = if a = b || a = c then 1 else 0let handle_je4 a b c d interpreter = if a = b || a = c || a = d then 1 else 0let handle_jl a b interpreter = let a = signed_word a in let b = signed_word b in if a < b then 1 else 0let handle_jg a b interpreter = let a = signed_word a in let b = signed_word b in if a > b then 1 else 0let handle_jz a interpreter = if a = 0 then 1 else 0let 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 ->sp3b3d: call 3b4a local0 ->local23b55: add g16 b4 ->local23b59: add g16 g35 ->local33b5d: je local3 local2 ?~3b773b61: sub g35 06 ->g353b65: jz local1 ?3b6c3b6c: add g16 g35 ->local43b70: 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 addrlet 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 addrlet 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 ->sp3b3d: call 3b4a local0 ->local23b55: add g16 b4 ->local23b59: add g16 g35 ->local33b5d: je local3 local2 ?~3b773b61: sub g35 06 ->g353b65: jz local1 ?3b6c3b6c: add g16 g35 ->local43b70: storew local4 02 local03b75: ret local43b43: storew local2 01 local13b48: ret local237e2: storew sp 00 0137e7: call 3b36 4e50 28 ->sp3b3d: call 3b4a local0 ->local23b55: add g16 b4 ->local23b59: add g16 g35 ->local33b5d: je local3 local2 ?~3b773b77: loadw local3 02 ->sp3b7b: je sp local0 ?~3b813b81: add local3 06 ->local33b85: jump 3b5d3b5d: je local3 local2 ?~3b773b61: sub g35 06 ->g353b65: jz local1 ?3b6c3b6c: add g16 g35 ->local43b70: storew local4 02 local03b75: ret local43b43: storew local2 01 local13b48: ret local237ef: call 3b36 4792 96 ->sp3b3d: call 3b4a local0 ->local23b55: add g16 b4 ->local23b59: add g16 g35 ->local33b5d: je local3 local2 ?~3b773b77: loadw local3 02 ->sp3b7b: je sp local0 ?~3b813b81: add local3 06 ->local33b85: jump 3b5d3b5d: je local3 local2 ?~3b773b77: loadw local3 02 ->sp3b7b: je sp local0 ?~3b813b81: add local3 06 ->local33b85: jump 3b5d3b5d: je local3 local2 ?~3b773b61: sub g35 06 ->g353b65: jz local1 ?3b6c3b6c: add g16 g35 ->local43b70: storew local4 02 local03b75: ret local43b43: storew local2 01 local13b48: ret local237f7: 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.