This was once an artist’s studio. The walls are splattered with paints of 69 different colors. To the west is a doorway (also covered with paint). A dark and narrow chimney leads up from a fireplace; although you might be able to get up it, it seems unlikely that you could get back down.
On the far wall is a painting of unparalleled beauty.

> take the painting

Taken.

> go west
> go up
> put the painting in the trophy case
> go down
> go north
> go northeast

Always wait until after you’ve prayed to get the painting; it’s so much easier that way than climbing up the chimney.

Code for this and the next several episodes is at https://github.com/ericlippert/flathead/tree/blog9

We are so close to being done with decoding an instruction. Today: some instructions compute a result and then conditionally branch. Let’s decode them.

Once again I will need to know which instructions contain branches; they are listed in the specification.

let has_branch opcode ver =
  match opcode with
  | OP0_181 -> Story.v3_or_lower ver (* "save" branches in v3, stores in v4 *)
  | OP0_182 -> Story.v3_or_lower ver (* "restore" branches in v3, stores in v4 *)
  | OP2_1   | OP2_2   | OP2_3   | OP2_4   | OP2_5   | OP2_6   | OP2_7   | OP2_10
  | OP1_128 | OP1_129 | OP1_130 | OP0_189 | OP0_191
  | VAR_247 | VAR_255
  | EXT_6   | EXT_14 | EXT_24  | EXT_27 -> true
  | _ -> false

Branch decoding is a little bit complicated because there are both “short branches” and “long branches”. Most branches only move the current instruction forwards a small number of bytes, so those can be encoded in a single byte. Branching a large number of instructions, or branching backwards, requires a longer instruction. Again, this thing is built for compactness, not for ease of use. Let’s go to the spec.

Instructions which test a condition are called “branch” instructions. The branch information is stored in one or two bytes, indicating what to do with the result of the test.

• If bit 7 of the first byte is 0, a branch occurs when the condition was
  false; if 1, then branch is on true.
• If bit 6 is set, then the branch occupies 1 byte only, and the “offset”  is in the range 0 to 63, given in the bottom 6 bits.
• If bit 6 is clear, then the offset is a signed 14-bit number given in bits 0 to 5 of the first byte followed by all 8 of the second.
• An offset of 0 means “return false from the current routine”, and 1 means “return true from the current routine”.
• Otherwise, a branch moves execution to the instruction at address (Address after branch data) + Offset – 2.

All right, that is some bit twiddling going on there but we can handle it. First I am going to need a type to represent the branch. A branch has two parts: the address branched to, which might be a return instead of an address, and whether it is branch-on-true or branch-on-false:

type branch_address =
  | Return_true
  | Return_false
  | Branch_address of instruction_address

All right, that’s that. What about the sense? I have a bunch of possible choices here:

type branch = { address : branch_address; sense : bool }

or

type branch = 
  | On_true of branch_address
  | On_false of branch_address

or

type branch = 
  Branch of bool * branch_address

We haven’t seen that last syntax before; it means “the Branch constructor takes a tuple where the first element is a bool and the second is a branch address”.

Hmm.

You know what, just to mix it up a bit, I’m not going to assign this type a name at all, and we’ll see how that works. I’m just going to say that a branch is a tuple of bool and branch address, and let that type stay anonymous. We’ll see if this works!

Now we can write the code:

  let decode_branch branch_code_address opcode ver  =
    if has_branch opcode ver then
      let high = read_byte branch_code_address in
      let sense = fetch_bit bit7 high in
      let bottom6 = fetch_bits bit5 size6 high in
      let offset =
        if fetch_bit bit6 high then
          bottom6
        else
          let low = read_byte (inc_byte_addr branch_code_address) in
          let unsigned = 256 * bottom6 + low in
          if unsigned < 8192 then unsigned else unsigned - 16384 in
      let branch =
        match offset with
        | 0 -> (sense, Return_false)
        | 1 -> (sense, Return_true)
        | _ ->
          let branch_length = if fetch_bit bit6 high then 1 else 2 in
          let (Byte_address address_after) = inc_byte_addr_by branch_code_address branch_length in
          let branch_target = Instruction (address_after + offset - 2) in
          (sense, Branch_address branch_target) in
      Some branch
    else
      None

Make sure that makes sense to you. This thing takes an address, an opcode, and a version. It gives you back an optional tuple of bool and branch address.

And of course we’ll need to know how long the branch portion of the instruction is.

  let get_branch_length branch_code_address opcode ver =
    if has_branch opcode ver then
      let b = read_byte branch_code_address in
      if fetch_bit bit6 b then 1 else 2
    else 0 in

There’s a couple lines of duplicated code here, but, whatever. I’m not going to stress about it.

Next time on FAIC: we’ll read the trailing strings that follow two of the “print” instructions, and then we’ll put the whole thing together.