Zarf Updates

Planetfall was yesterday's public release, but of course I've spent the past few weeks concentrating on Infidel. A couple of days I came across the most egregious bug I've yet seen in an Infocom game.

This bug is extremely difficult to detect by playing the game. I must the first person to notice it, just because I'm the first person to play the game with (the equivalent of) a memory-level debugger.

So why do I call it an egregious bug? Most people would call it a "trivial" bug, since it almost never impacts gameplay. But look you: it's a wild pointer bug which scribbles over memory in an unintended way. As a C programmer, I am legally required to regard memory corruption as the worst of all possible sins. On top of that, it's a compiler bug!

(Warning: This will get into ZIL code and Z-machine implementation details. Note that I will be analyzing Infidel release 22 serial 840522, the update for Macintosh. The original release, serial 830916, has the same bug with slightly different memory addresses.)

---

Let's set the scene. Infidel takes place in the remote Egyptian desert. You start out in your camp. The Nile is to the west. To the east are nine desert locations, a 3x3 grid. (One of these holds the buried pyramid you're searching for.)

If you venture outside that region, or leave your camp in any other direction, you are officially lost in the desert. You can travel as far as you want; you'll just find more desert. (Until sunstroke finds you.) This is a known trick, first seen in Enchanter; a single room called ENDLESS-DESERT represents every unmapped desert location. When you move, if you haven't blundered back to your camp or the mapped area, you just loop back to ENDLESS-DESERT. The game keeps track of your latitude and longitude.

To make this convincing, the game has to juggle objects. If you drop stuff in ENDLESS-DESERT and then move, those items are shifted offstage. Their lat/long coordinates are recorded in an array called DESERT-TABLE. If you return to those coordinates later, the game can shuffle those objects from DESERT-TABLE back to ENDLESS-DESERT, and you will find them waiting for you.

(Probably. When you drop an item in ENDLESS-DESERT, there's a one-in-three chance that it is immediately covered up by sand and lost forever. That's not relevant here, except that it makes the bug harder to uncover, as we'll see.)

Okay, so far the plan looks solid. Let's see it in action:

Both locations are the same ENDLESS-DESERT, but the pickaxe maintains the illusion of distinct rooms.

(Wouldn't it be more realistic if the shovel disappeared silently, buried in sand, while your back was turned? Maybe that playtested badly.)

Anyhow, that seems to work fine. Where's the bug?

---

Let's take a look at the DESERT-TO-TABLE routine that makes this work:

<ROUTINE DESERT-TO-TABLE (
                         SLOC 
                   "AUX" (TBL ,DESERT-TABLE) 
                         (CNT 0)
                         (F <FIRST? ,ENDLESS-DESERT>)
                         N)
  <REPEAT ()
      <COND (.F <SET N <NEXT? .F>>)
            (ELSE <RETURN>)>
      <COND (<EQUAL? .F ,WINNER>)
            (<FSET? .F ,TAKEBIT>
             <REPEAT ()
                 <COND (<==? <GET .TBL .CNT> 0>
                        <PUT .TBL .CNT .SLOC>
                        <PUT .TBL <+ .CNT 1> .F>
                        <SET CNT <+ .CNT 2>>
                        <REMOVE .F>
                        <RETURN>)
                       (ELSE
                        <SET CNT <+ .CNT 2>>)>>)>
      <SET F .N>>>

There's a similar TABLE-TO-DESERT routine to bring stuff back. We'll focus on this one.

The routine has one required argument: SLOC, the lat/long coordinate. (This is encoded as a single number, but never mind that.) Then "AUX" marks the four optional arguments, which also serve as local variables; the Z-machine doesn't distinguish. TBL is the array address we'll be writing to. It defaults to DESERT-TABLE. F is initialized to the first object in the ENDLESS-DESERT contents list. CNT and N are initialized to zero.

As it happens, when this is called, the game only passes one argument, SLOC. It relies on the default value of TBL=DESERT-TABLE. (If there were two endless deserts in the game, it would want to call this routine with two separate tables. But there ain't.) DESERT-TABLE is an array of 100 values (200 bytes) starting at address 11129.

The function body loops through all the objects in ENDLESS-DESERT (starting with F). Every portable object (ignoring scenery and the player) is removed, and we add two values to the TBL array: the coordinate SLOC and the object ID. The table might already have entries (you can drop stuff in multiple places), so we're careful to find empty slots to fill in. When we reach the end of the list we're done. If the logic looks a bit convoluted, remember that we're dealing with a linked list.

All sound good so far? It sounded good to me. "Hey," I said to myself, "I should display the DESERT-TABLE contents in the State tab! That way people can watch the objects being shuffled in and out."

So I set that up... and it didn't work. The DESERT-TABLE array remained resolutely empty. I could see the objects disappearing and appearing -- just look at that pickaxe above! -- but where were they going?

Any C nerd looking at a fixed-size array will ask "What about array overflow?" But DESERT-TABLE has a comment:

;"length should be 2*number of takeable objects"

Indeed, 100 values at two values per entry is enough space for 50 objects. Piling up every portable object in the game would get you (I think) 45. Anyhow, nothing is being stored anywhere in the array.

---

Time to disassemble the DESERT-TO-TABLE function from the game file and take a look. (I warned you we'd go deep...)

Routine 109bc, 5 locals (0000, 001e, 0000, 0000, 0000)

109c7:  GET_CHILD     ENDLESS-DESERT -> .F [TRUE] 109cb
109cb:  JZ            .F [TRUE] RTRUE
109ce:  GET_SIBLING   .F -> .N [TRUE] 109d2
109d2:  JE            .F, G70 [FALSE] 109d9
109d6:  JUMP          10a02
109d9:  TEST_ATTR     .F, #0f [FALSE] 10a02
109dd:  LOADW         .TBL, .CNT -> -(SP)
109e1:  JZ            (SP)+ [FALSE] 109fb
109e4:  STOREW        .TBL, .CNT, .SLOC
109e9:  ADD           .CNT, #01 -> -(SP)
109ed:  STOREW        .TBL, (SP)+, .F
109f2:  ADD           .CNT, #02 -> .CNT
109f6:  REMOVE_OBJ    .F
109f8:  JUMP          10a02
109fb:  ADD           .CNT, #02 -> .CNT
109ff:  JUMP          109dd
10a02:  STORE         .F, .N
10a05:  JUMP          109cb

I'm using the txd disassembly tool from ztools, but I've edited the output to show variable names. Note that the opcode names do not match ZIL terminology. txd dates from the early 1990s. We had no ZIL manuals so we had to make up our own opcode names.

The first line sets the initial value of F to the first object in the room (<FIRST? ,ENDLESS-DESERT>). The second line tests whether F is zero, which is the condition of the function's REPEAT loop. The loop continues from there.

Notice anything missing? Where do we initialize TBL to its default value of DESERT-TABLE (11129)? That seems like an obvious hole.

Aha, says ZIL, we've got you covered. A Z-machine function has slots to initialize its local variables (or optional arguments) to constants. That's shown in the header lines:

Routine 109bc, 5 locals (0000, 001e, 0000, 0000, 0000)

CNT is initialized to zero, as is N, implicitly. F is not initialized from a slot because it's calculated, not a constant. ZIL generates that FIRST? (GET_CHILD) line at the top of the function. DESERT-TABLE is a constant, so...

...Whoops. No it isn't. DESERT-TABLE is a global variable. Its value will never vary -- it will be 11129 through the whole game -- but ZIL doesn't know that! TBL is initialized to the constant value 30 (hex 1e), which is the index number of DESERT-TABLE.

(Global variables are numbered from 16 to 255 for boring reasons. DESERT-TABLE is the 15th global, so it's number 30.)

It seems clear that nobody thought about this case (an argument defaulting to a global variable value). If they had, ZIL would either display a compiler error ("Default value is not a constant!") or generate a STORE instruction at the top of the function (same as how F is initialized). 30 is simply wrong.

The upshot is that when DESERT-TO-TABLE start writing object numbers to memory, it doesn't write to address 11129. It overwrites memory addresses 30 and up. Oh dear.

The TABLE-TO-DESERT routine uses a default global argument in exactly the same way. So it pulls the object list back from address 30, producing apparently correct results. But memory has been stomped.

---

So what's at that address?

The first 64 bytes of memory are header data, but not all of the header is used. By sheer luck, only addresses 0-29 are meaningful in Z-machine version 3. If DESERT-TABLE had been the third global, index 18, this bug would have corrupted the game's serial number! Which would be a lot more obvious.

So addresses 30-63 are unused, but address 64 is the beginning of the abbreviations data. This is part of the Z-machine text compression scheme: a list of 96 words which occur frequently and can therefore be pulled out and replaced by a few bits.

Prediction: if we drop nine objects in the desert (and then walk away), the last one will overwrite the start of the abbreviations table.

This is a bit of a nuisance to arrange. Remember that dropped objects have a one-in-three chance of simply disappearing. I had to drag a lot of stuff out there and try it a few times. But I succeeded, and the next text the game printed looked like this:

This is of course a heat-driven hallucination, but notice that the word "the" (the first abbreviation) has been replaced by "You" (the second). This indicates that the early string data has been overwritten by junk which happens to have no terminator, so the print routine continues to the next valid string.

In another test I managed to crash the interpreter. I suspect that it overwrote the first abbreviation with the bits representing the first abbreviation, so the print routine went into an infinite loop. You know. As one does.

---

Okay! Bug demonstrated! What have we learned?

This bug shipped and absolutely nobody noticed. When I played Infidel as a kid and explored the desert, my game was corrupting memory. Same with every other player, including Infocom's playtesters.

It's very likely that nobody tried dropping more than eight objects out in the Endless Desert. Why would you? There's nothing out there! It's not on the way to anywhere. The entire mechanism exists only to occupy players who have not yet discovered the pyramid. The attention to detail is typical of Infocom, but that area can't have been playtested very hard.

(I would love to peruse an Infocom testing log to see if any trace of the bug appeared. The Infocom Cabinet doesn't seem to have anything relevant. Let know if you come across such a thing.)

The 1984 revision of the game did nothing to address the bug. Infocom did not have anything like the Visible Zorker. They might have had debugging tools to inspect memory, but nobody thought to apply them to these routines and their storage.

I have not surveyed later games to see if a similar bug exists -- or is correctly handled by the compiler. I'll keep an eye out.

How would one fix the bug? Simple: remove the argument default for TBL, and instead start the routine with <SET TBL ,DESERT-TABLE>. Or else pass in DESERT-TABLE as a second argument to the routine. Either would work.

There's another pair of routines PROP-TO-TBL, TBL-TO-PROP which have a similar bug with the PROP-TBL table (global number 22). I am honestly a bit baffled by these routines. They look like they're doing a similar shuffle-job with the holes you can dig in the sand. (These are stored in desert rooms as the CAPACITY property.) But the game doesn't let you dig in ENDLESS-DESERT; it says "The ground is too hard here." So the routines appear to be useless. They may be a remnant of an earlier feature which was removed during development. Perhaps because it corrupted the serial number!

If I were updating Infidel (as opposed to riffing it), I would definitely restore the ability to dig useless holes out in the desert. That kind of pointless detail is one of the great joys of IF.