Frigid River, in the magic boat

You are on the Frigid River just below the dam. The river flows quietly here. There is a landing on the west shore.

> wait

Time passes…
The current carries you downstream.
The river descends here into a valley. The are no landings on either shore. In the distance a faint rumbling can be heard.

> wait

Time passes…
The current carries you downstream.
The sound of rushing water is nearly unbearable here. On both the east and west shores there are beaches.
There is a red buoy here (probably a warning).

> take the buoy

As you take the buoy, you notice something odd about the feel of it.

> go west

The magic boat comes to rest on the shore.


The bug here – “The are no landings” – appears to be just a typo in the string literal.

Code for this episode is at https://github.com/ericlippert/flathead/tree/blog11

We’re continuing to look at this routine; last time we got the addresses of the routines in the call instructions correct.

37d9: call 3b36 3e88 ffff ->sp
37e2: storew sp 00 01
37e7: call 3b36 4e50 28 ->sp
37ef: call 3b36 4792 96 ->sp
37f7: store 10 2e
37fa: store 8a a7
37fd: store 36 01
3800: store 83 1e
3803: insert_obj g73 g00
3806: call 5862 ->sp
380b: new_line
380c: call 61f4 ->sp
3811: call 381a ->sp
3816: jump ffc2

There are two more problems with how we’re displaying the code here. The first is that “store” is a very unusual instruction in that its first argument evaluates to the number of the variable to which the result will be stored. I’ll talk more about the power of this instruction, and how to best render it, in a later episode.

The much easier problem is that the jump address is displayed as an unsigned relative address rather than an absolute address. It’s hard to look at this code and see what it really does, but it is easily fixed:

  match (instr.opcode, instr.operands) with
  | (OP1_140, [Large offset]) ->
    let offset = signed_word offset in
    let (Instruction addr) = jump_address instr offset in
    Printf.sprintf "%04x " addr
  | _ -> match call_address instr story with
    | Some (Routine addr) ->
      (Printf.sprintf "%04x " addr) ^ display_remainder (List.tl instr.operands)
    | _ -> display_remainder instr.operands

And now when we display the routine the jump comes out to

3816: jump 37d9

The jump unconditionally loops back to the beginning of the routine. There are no returns here; this is an infinite loop.

Since this is the “main” routine of the story – this is where execution begins – it is not really surprising that there’s an infinite loop here. In fact this is a very special routine; the main routine has no local variables and may not return. In the Z-machine, a game ends not when main returns, but rather when the quit instruction is executed.

When I first ran my decompiler on this routine I was pleased that it seemed to come out to something sensible, but I quickly grew concerned. Do you see why? Read the code more carefully and you’ll see it.

We have an infinite loop; every time through the loop we do six pushes but only one pop on the evaluation stack. I thought at first that I must have decoded something wrong, but no, this disassembly is correct. This infinite loop appears to consume an unbounded quantity of stack, which I assure you is very bad. What is up with that?

My first thought was that perhaps the called routines were taking values off the stack, but no, that’s not legal. Each routine has its own evaluation stack; it cannot touch the evaluation stack of an earlier frame.

The conclusion I came to was that the last call must also be an infinite loop, and therefore the final jump is not reachable! And indeed, if we disassemble the routine at 381a we see that it is:

381d: call 3826 ->local0
3822: jump 381d

Aha! So that jump at the end of the main routine is never reached, and the stack is not pushed arbitrarily much.

Why does the main routine push so much on the stack in the first place? Because remember, I said (1) the main routine has no locals, and (2) the sole call instruction in version 3 has a store. That store has to store somewhere. It can’t store to a local, and so that leaves either modifying global state for no reason, or pushing the stack. And why write unnecessary pop instructions if we’re never coming back?

Later versions of the Z-machine had call instructions without stores, so a call which wishes to discard its result can do so without having to store to a local or push the stack.

Next time on FAIC: we’ll start to think about the parts we need for a proper interpreter.

Advertisements

One thought on “Frigid River, in the magic boat

  1. Another place you might see garbage being pushed on the stack and never used is around the instructions that store and branch (get_sibling and get_child).

    Those instructions store an object’s sibling or child, then branch if the stored value was nonzero, i.e. if the object has a sibling or child. This is a nice optimization for looping through the object tree, where you want to advance to the next object and then continue the loop if there is one:

    store x first_object
    Loop:
    // …do something with x…
    get_sibling x -> x ?Loop

    But when you only care about the branch, e.g. you’re testing whether or not a container is empty, you still have to store a result somewhere — and if you put it on the stack, popping it off after the branch can be tricky. Inform uses a global scratch variable for cases like this, but Infocom’s compiler just polluted the stack.

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