Infidel goes wild

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: Desert You are in the desert, a vast wasteland of sand and heat. >DROP AXE, SHOVEL pick axe: Dropped. shovel: Dropped. A brief but strong gust of wind comes up off a dune, whipping sand in your face, blinding you for long enough to lose track of the shovel. >EAST Desert You are in the desert, a vast wasteland of sand and heat. >WEST Desert You are in the desert, a vast wasteland of sand and heat. There is a pick axe here. 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 (If you're looking at the 1983 release, this routine is at address 1051a but is otherwise identical.) 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: Desert