Entries
Winning entries Winning authors Location of authors Bugs and (mis)features Fixing entries Updating author info Thanks for the help
Status
News Contest status IOCCC rules IOCCC guidelines Markdown guidelines Security policy
FAQ
Frequently asked questions Enter the IOCCC Compiling entries Running entries How to help
About
Home page IOCCC social media About the IOCCC The judges Contact us
IOCCC image by Matt Zucker

The International Obfuscated C Code Contest

2024/mills - Prize in ℤ₃

Infocom v3 story interpreter

← 2024/maffiodo ↑ 2024 ↑ 2024/stedolan → C code Makefile Inventory ✓

Author:

To build:

    make all

To use:

    ./prog foo.z3 foo.sav

The foo.z3 is an Infocom version 3 Z-machine file, and foo.sav is file that is written when you enter the command SAVE and read when you enter the command RESTORE.

Try:

    ./try.sh

    For your first try, we suggest selecting games 0 or 1

Alternate code:

Alternate build:

    make alt

Alternate use:

    ./try.alt.sh

    For your first try, we suggest selecting games 0 or 1

Judges’ remarks:

What is the “Prize in ℤ₃”? The “double-struck Z” is NOT a reference to a set of integers, nor is the “double-struck Z subscript 3” a reference to a ring of 3-adic integers. Instead, it is a reference to the 3rd version of a certain virtual machine.

To fully appreciate the brilliance of this implementation, we suggest illuminating the source code. But be careful not to get lost in the labyrinthine twists and turns of this source code and get eaten by a Grue!

Author’s remarks:

West of House

    You are standing in an open field west of a white house, with a boarded
    front door.

    There is a small mailbox here.

These are the opening lines from the legendary Zork, one of the most influential and successful games of the early computer era. You can play a demo version with the submitted program using the following command:

    ./prog minizork.z3 minizork.sav

Minizork is a publicly-available demo version of the original Zork, but the program can play any of the classic Infocom text adventure games that run on the version 3 of the Z-machine, a virtual machine which Infocom used to run its mainframe-developed games on the 8-bit microcomputers of the 1980’s.

Although there were several iterations of the Z-machine, this program implements version 3, which was used for dozens of Infocom’s most famous and influential interactive fiction games of the 1980’s, including:

If you are new to interactive fiction, you might want to try one of the two Infocom “four-in-one” demo samplers. These include a gentle introductory tutorial to interactive fiction and some sample puzzles from Zork I, Planetfall, Infidel, The Witness, Trinity and Leather Godesses of Phobos. You can run them by typing:

    ./prog sampler1_R55.z3 sampler1.sav

or

    ./prog sampler2.z3 sampler2.sav

In addition to the Infocom games, there is an entire community of interactive fiction authors who write modern games which can be downloaded from sites like The Interactive Fiction Database, The Interactive Fiction Wiki, and The Interactive Fiction Archive. I’ve included a few “story files” compiled for the Z3 machine from these sites for your enjoyment, but I’ll point out in particular Curses by Graham Nelson, the author of Inform, a literate programming system for writing interactive fiction. You can of course run it with

    ./prog curses-r10.z3 curses.sav

By now you’ve probably figured out that prog takes two command-line arguments, the first being the “story file” which is the game itself, and the second (optional) parameter being the “save file”, which is the file the game will write if you type SAVE and read if you type RESTORE. The second parameter is optional, but if you don’t use it, you won’t be able to SAVE your game (think of this as an “Ironman” mode). Make sure that if you switch story files, you also switch save files, because a RESTORE from an unrelated story file will invoke what the C Standard Committee refers to as “Undefined Behavior”.

You can use this command-line template to run any other “version 3” games you find, including the original Infocom ones. If you are lucky, you can find the original files in one of the (sadly out-of-print) collections like The Lost Treasures of Infocom, or you could download a copy of the Zork Trilogy (which was given away free as part of an Activision promotion long ago). There are of course other places one might find Infocom story files, but since they are not in the public domain I cannot give pointers to them. Maybe Microsoft will decide to release them from abandonware status now that they have bought Activision…

Finally, I have also included a copy of Colossal Cave Adventure, which may be better known by it’s PDP-10 file name ADVENT. You can run it with

    ./prog advent.z3 advent.sav

ADVENT is the original interactive fiction title by Crowther and Woods that inspired Zork and gave us hacker shibboleths like Xyzzy and “You are in a maze of twisty little passages, all alike.”

It is pitch black. You are likely to be eaten by a grue.

So what makes the Z3 machine an interesting obfuscation target? Good question!

The IOCCC has seen all manner of virtual machines over the years, from Commodore PETs to IBM PC’s that can run Windows™ and even a mainframe or two, so what is so challenging about a VM that ran on the TRS-80 and the Apple II?

Well, a lot really. If you’ve got nothing better to do, take a look at the Z-Machine Standards Document which is a detailed reverse-engineering effort of Infocom’s interpreter. A Z-machine implementation has to handle the byte-code for an exceptionally complicated byte-code interpreter, which in turn has to do a lot of high-level operations such as:

The interpreter is complicated because of the Herculean task the Zork implementors set for themselves. Zork itself was originally written on a PDP-10 mainframe at MIT running a version of Lisp called MDL. It was designed to have a more natural parser than the two-word parser of ADVENT. Zork itself escaped into the wild because of MIT’s connection to ARPANET. Contributions and requests from the player-base caused the program to grow in size until it filled the mainframe’s megabyte of memory. When the newly-founded Infocom decided to port their grad-school project to the world of microcomputers, they needed to somehow move a megabyte of MDL code onto 8-bit microcomputers with 32 kilobytes of memory. They got there by chopping the program into three separate parts, creating a stripped-down subset of MDL called ZIL (for Zork Implementation Language) and targeting the compiled ZIL bytecode to run on the Z-machine interpreter. The Z-machine data types were specifically designed to reduce the memory footprint as much as possible (including packed properties and compressed string encodings) but the ZIL code was still too large (at over 100 kilobytes), so the interpreter was designed to page in parts of the story file from the floppy disk, one of the first uses of virtual memory on personal computers.

All of the above was described in a much clearer fashion by Infocom employees in a paper called How to Fit a Large Program into a Small Machine, which I only discovered after writing the previous paragraph, alas. I include it here for the curious, because you can never have enough links in your IOCCC write-up.

A hollow voice says “Fool.”

It took me many iterations to make the interpreter fit inside the IOCCC size limits.

The original quite compact C program was maybe still 50% too large even after doing as much minification as possible. I won’t go into the details of the next iterations of reduction (that would spoil all the fun), but suffice to say, the steps I took share some similarities to the steps the Zork implementors took to do their heroic reduction. It was only by completely throwing out any attempt to make the source code look “pretty” was I able to cross the iocccsize Rule 2b limitation of 2,053, and this included abusing the whitespace rules.

Of course, by time the contest was announced, the size limit had increased which means I had to go back and undo some of my heroics because now I had enough wiggle room to make the source more picturesque. I have however included a version of the original source (prog.alt.c) for your perusal and amusement.

Inventory for 2024/mills

Primary files

Secondary files

Jump to: top

Coda

Nu HTML check this web page
Jump to top Jump to Content Jump to Inventory