Sandy cave

This is a sand-filled cave whose exit is to the southwest.

> dig in the sand with the shovel

You seem to be digging a hole here.

> again

The hole is getting deeper, but that’s about it.

> again

You are surrounded by a wall of sand on all sides.

> again

You spot a scarab in the sand.

> take the scarab

Taken.

> drop the shovel

Dropped.

> go southwest
> go south
> go west
> go southwest
> go up
> go west
> go west
> go west
> enter the white house
> go west
> put the scarab and the pot of gold and the sceptre in the trophy case

beautiful jeweled scarab: Done.
pot of gold: Done.
sceptre: Done.

> open the trap door

The door reluctantly opens to reveal a rickety staircase descending into darkness.

> go down
> go east


Wow, three treasures at once. We’re moving right along here. And we’ve only got stores, branches and text left to decode from an instruction. Today: stores.

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

In modern VMs like the CLR or the JVM, typically every instruction is simple, and we make heavy use of the evaluation stack. For example, in C# if we had something like

x = M(y);

then we would have instructions to first, push y onto the evaluation stack, next, to call M – which pops the argument and pushes the result – and next, to store the top of the stack in x. We logically have three operations — fetch a local, call a method, store a local — and so we have three instructions.

That’s conceptually very clean and straightforward, but the code tends to be large. The Z-machine instruction set was designed to be compact. In the Z-machine this is all one call instruction; the local variable number for the operand is encoded in the instruction itself, and the local variable we’re going to store to is as well.

The convention for storing the result of an instruction that produces a value is the exact same byte format for fetching the value of a variable, except that this time zero means “push the stack” and not “pop the stack”. Since I already have a wrapper type for variables, I’m just going to re-use it for stores.

But the first thing I need to know is whether or not there even is a store in this instruction; not all instructions produce a value. Many just produce a side effect, or use their value to branch rather than store the value. The spec lists every opcode that does a store. Unfortunately, the different versions of the Z-machine have assigned different meanings to some opcodes, so we’ll need to do a little fancy conditional logic:

let has_store opcode ver =
  match opcode with
  | OP1_143 -> Story.v4_or_lower ver  (* "call_1n" in v5, "not" in v1-4 *)
  | OP0_181 -> Story.v4_or_higher ver (* "save" branches in v3, stores in v4 *)
  | OP0_182 -> Story.v4_or_higher ver (* "restore" branches in v3, stores in v4 *)
  | OP0_185 -> Story.v4_or_higher ver (* "pop" in v4, "catch" in v5 *)
  | VAR_233 -> ver = V6
  | VAR_228 -> Story.v5_or_higher ver
  | OP2_8   | OP2_9   | OP2_15  | OP2_16  | OP2_17  | OP2_18  | OP2_19
  | OP2_20  | OP2_21  | OP2_22  | OP2_23  | OP2_24  | OP2_25
  | OP1_129 | OP1_130 | OP1_131 | OP1_132 | OP1_136 | OP1_142
  | VAR_224 | VAR_231 | VAR_236 | VAR_246 | VAR_247 | VAR_248
  | EXT_0   | EXT_1   | EXT_2   | EXT_3   | EXT_4   | EXT_9
  | EXT_10  | EXT_19  | EXT_29 -> true
  | _ -> false

Every instruction has an opcode. Not every instruction has operands, but we already represent the notion of “no operands” with an empty list. For the first time thus far in this series we will need to represent a single value – the variable that the instruction will store to – that might or might not be there. In C# for reference types we could use null, and for value types we could use a null value of a nullable value type, but what will we do in OCaml, which apparently does not have this “null” I speak of? Using a one-or-zero element list would work but seems suboptimal.

Fortunately OCaml has the equivalent of nullable value types; it has a generic type called option that has two constructors: None and Some. We can therefore decode our store using parts we’ve already assembled. Before I do that though I want to note a minor wording problem in the specification:

“Store” instructions return a value: e.g., mul multiplies its two operands together. Such instructions must be followed by a single byte giving the variable number of where to put the result.

The wording above implies that the instruction has ended after the operands, and that the store (and hence also branch and text) follow the instruction. I cannot get behind this. The store, branch and text are all part of an instruction in my reading of the specification. (We will see in a later episode that the authors of the save-game format specification might believe that the branch/save are not part of the instruction. That however is far in our future still!)

  let decode_store store_address opcode ver =
    if has_store opcode ver then
      let store_byte = read_byte store_address in
      Some (decode_variable store_byte)
    else
      None

Nice and easy! If we have a store, we read it, and we have “some variable”. If we don’t have a store, we don’t read it, and we have nothing.

We’ll need to know how many bytes we read for the store:

  let get_store_length opcode ver =
    if has_store opcode ver then 1 else 0

Next time on FAIC: the branch is a little bit more complicated than the store.

Advertisements

2 thoughts on “Sandy cave

  1. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #2054

  2. I guess you’re going to need at least three functions like has_store, mapping (opcode, ver) to various facts about the instruction. Seems like that’ll be hard to read and hard to confirm – the reader can’t tell if it makes sense for “OP1_142” to be a store instruction without looking it up in the spec.

    Why not keep all the facts in one place, e.g. a function that maps (opcode, ver) to a record {name: string; has_store: bool; …}?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s