Daisy Z-Machine

This guide describes the Z-machine interpreter supplied with DaisyOS. The interpreter lets Daisy run the interactive fiction Infocom published in the 1980s: ZORK, DEADLINE, THE HITCHHIKER'S GUIDE TO THE GALAXY, and some thirty more. It runs them directly, without emulating any other computer.

To begin, type ZORK. The interpreter takes over the display and keyboard, plays the story, and returns you to the BASIC prompt when the story ends or when you press STOP.

 West of House             S:0   M:4

>open mailbox
Opening the small mailbox reveals a
leaflet.

>take leaflet
Taken.

>north
North of House
You are facing the north side of a
white house. There is no door here,
and all the windows are boarded up. To
the north a narrow path winds through
the trees.

>_

What the Z-Machine Is

Infocom did not write their games for any particular computer. They wrote them for an imaginary one, the Z-machine, and then wrote a small interpreter for each real machine they wanted to sell to. A story file such as ZORK1.DAT holds the compiled program for that imaginary computer.

This is why a ZORK that runs on the Apple II also runs on the Commodore 64, the TRS-80 and the IBM PC. Only the interpreter changes.

Daisy is now one more machine on that list.

Why Not Emulate a Z80

You might ask why Daisy does not just emulate a Z80 and run the CP/M release of ZORK, since that software already exists.

The answer is that ZORK1.COM is itself a Z-machine interpreter, compiled for CP/M-80. To run it, Daisy would emulate a Z80 in order to reach the same virtual machine one layer further down. That costs a 64K address space in RAM and a disk drive to hold the story file.

Running the story directly costs 11,941 bytes of RAM and no storage hardware at all.

Where the Interpreter Came From

The interpreter is not original work. It descends as follows:

• ZIP 2.0Mark Howell
• JZIP 2.1John Holder2000
• A2Z_MachineDan Cogliano, ZContent2018
• Daisy Z-Machinethis port2026

JZIP is a portable C interpreter covering Z-machine versions 1 through 8. It carries a BSD licence, so it may be used here. The files written for this port carry the GNU General Public Licence version 3, like the rest of DaisyOS.

A2Z_Machine is JZIP moved to an Adafruit ItsyBitsy M4, an ARM Cortex-M4 board. It was taken as the starting point because it had already settled the differences between JZIP's assumptions and those of the Arduino framework.

Why A2Z Could Not Be Used As It Stood

A2Z runs on a board with 192K of RAM and 2 megabytes of SPI flash holding a file system. It loads the whole story image into RAM and reads it from files on a mass storage device.

Daisy has 98,304 bytes of RAM, of which DaisyOS itself uses 28,080, and no mass storage of any kind. ZORK1.DAT is 84,992 bytes. The A2Z method therefore needs 113,072 bytes on a machine that has 98,304.

A2Z also uses four libraries Daisy does not carry (SdFat, Adafruit_SPIFlash, TinyUSB and mcurses), and its display code is written against mcurses throughout.

The Other Reference Port

A second port was studied: Zorkduino, by rossum, which runs ZORK on an ATmega328 with 2K of RAM. It manages this by putting every stack and memory access through a 160-byte cache and a 512-byte disk buffer, backed by a one-megabyte page file on an SD card.

Daisy needs neither method. It has forty-eight times the RAM of an ATmega328, and, more important, its processor maps flash into the normal address space.

What Was Kept, Replaced and Thrown Away

A2Z_Machine holds 23 source files. Eleven were kept, four were replaced, one was adapted, and seven were thrown away.

• Keptinterpre, control, math, object, operand, property, text, variable, input, screen, extern
• Adaptedztypes.h

The kept files are the interpreter proper. They are unchanged apart from the corrections listed later in this guide. ztypes.h holds the types and the data access macros; see A Trap in the Header Field Names.

Arduino Code That Had To Go

These were in the A2Z sources and had to be removed or replaced. They are listed because each one fails to compile with a message that does not point at the cause.

How a Story File Is Divided

The next few sections describe the main difference between this port and the ones it came from. Read them before changing anything in the module.

Every Z-machine story splits into three regions. The boundaries are held in the header. The addresses shown are those of ZORK I.

What JZIP Does

JZIP was written for machines that read the story off a disk one page at a time. It keeps a chain of 512-byte pages in a least-recently-used cache.

A dictionary lookup is a binary search across the whole dictionary. If the dictionary were paged, every lookup would throw out the page the interpreter is running from, and the interpreter would spend its life reading the disk. So JZIP makes its resident area reach all the way up to the base of high memory, keeping dynamic and static memory in RAM at once.

For ZORK I that is 20,480 bytes, or forty pages, of which only 11,859 are ever written.

What Daisy Does Instead

The SAM3X maps its flash into the normal address space. A story compiled into the firmware as a const array can therefore be read with a plain subscript, at full speed, with no cache and no copying.

The cache, the page chain and the dictionary padding were all removed. Only the writable region goes in RAM.

The other 73,133 bytes are read from flash where they sit.

A Trap in the Header Field Names

The second one is the size of the writable region, and is the figure this port allocates.

The proof is simple. z_restart reloads h_restart_size bytes, and the save routine writes exactly h_restart_size bytes of datap. A save that left out part of dynamic memory would not restore.

Measured Cost

The figures below are read from the linked ELF file. Note that PlatformIO's reported RAM figure counts only .bss and leaves out .relocate, which on the Due is also in RAM. Both are counted here.

Of the flash added, 84,992 bytes is the story image itself. The interpreter takes about 19,544 bytes.

While a story is running, another 11,941 bytes are allocated. They are given back when it ends.

DaisyBASIC's heap is left alone. The two never run at the same time, and the interpreter gives its memory back before the BASIC prompt returns.

Corrections to the Interpreter

Seven faults had to be fixed. Four follow from the smaller resident area described above and would not show up in a port that kept JZIP's paging. Two are old faults that a 40-column display brings out. The last was introduced by this port and was found by playing the game on the machine.

They are written down in full here, because anyone merging a later JZIP release will have to apply them again.

1 z_restart Runs Past the End of Dynamic Memory

Symptom: memory corruption after the RESTART command.

z_restart reloads dynamic memory in whole pages:

restart_size = ( h_restart_size / PAGE_SIZE ) + 1;
for ( i = 0; i < restart_size; i++ )
    read_page( i, &datap[i * PAGE_SIZE] );

For ZORK I that is 24 pages, or 12,288 bytes, written into a buffer of 11,859. The overrun is 429 bytes. JZIP gets away with it only because its datap is 20,480 bytes long.

Fix: the region is copied from the flash image by ZmReloadDynamic().

2 The Data Accessors Do Not Reach the Dictionary

Symptom: the parser recognises no words at all, and reads past the end of the allocation.

JZIP defines its accessors as plain subscripts:

#define get_byte(offset) ((zbyte_t) datap[offset])

In ZORK I the dictionary sits at $3B21 to $4E37, that is 15,137 to 20,023, which is above the 11,859-byte dynamic region. Every dictionary lookup would read past the end of datap.

Fix: get_byte, get_word, set_byte and set_word are now bounds-aware inline functions. Reads at or above zm_dyn_size are answered from the flash story image.

Writes at or above that line break the Z-machine specification. JZIP soaks them up silently into its resident copy of read-only data. Flash cannot be written at all, so such a store is now dropped and reported through ZmWriteGuard().

3 Unchecked Pointers Into Dynamic Memory

Symptom: none seen in normal play. A bad story file could read outside the allocation.

Three routines take a raw C pointer into datap from an address the story supplies: tokenise_line, z_sread_aread and z_encode.

Fix: each is now guarded by ZmDynamicRange().

4 SAVE Does Not Consume Its Branch Data

Symptom: interpret(): failing opcode: 0 right after typing SAVE.

This one needs explaining. In Z-machine versions 1 to 3, SAVE is a branch instruction. The bytes after the opcode are branch data, and the interpreter has to read them and act on them. From version 4 on, SAVE stores a result instead.

The rewritten z_save returned a status code to its caller but did neither. The branch data was left in the instruction stream and decoded as the next opcode.

Fix: every exit from z_save and z_restore, including the early refusals, now goes through one reporting point:

if ( h_type < V4 )
    conditional_jump( status == 0 );
else
    store_operand( status == 0 ? 1 : 0 );   /* 2 for restore */

This matters even though saving is unavailable, because refusing a save has to leave the interpreter running.

5 The Status Line Assumes Eighty Columns

Symptom: on a 40-column display, ZORK I prints the room name, the score and the move count on top of one another.

North of Score  0        Moves: 2      <- wrong
 West of House             S:0   M:4   <- fixed

z_show_status puts its fields at screen_cols - 31 and screen_cols - 15. On an 80-column screen those are columns 49 and 65. On Daisy's 40-column screen they are columns 9 and 25.

The room name "North of House" is fourteen characters and has already gone past column 9. pad_line sets status_pos = column no matter what, which rewinds the buffer instead of advancing it, and the score field lands on top of the room name.

Fix: displays narrower than 72 columns use short labels and field positions of screen_cols - 14 and screen_cols - 8, which leaves twenty-five columns for the room name.

6 The [MORE] Prompt Is Never Erased

Symptom: a stray [MORE] sits in the middle of the text.

JZIP prints the prompt, waits for a key, then counts on the story's next output to write over it. When that output happens to be a newline, the prompt survives and scrolls up into the story text. ZORK III shows this on its opening screen.

Fix: the cursor goes back to the start of the prompt and the line is erased once the key is pressed.

7 STOP Does Not Stop the Story

Symptom: pressing STOP or CTRL-C puts the game in a loop printing "Beg pardon?".

>
Beg pardon?

>
Beg pardon?

>
Beg pardon?

Ending the current read is not enough. input_line returned an empty line, the story's parser printed its complaint and asked again, and the next read returned nothing straight away, so the game sat in that loop.

What actually ends a story is interpreter_state, which interpret() tests at the top of every instruction. Nothing was setting it.

There was a second fault behind the first. ZmHostPollKey() returns 0 both for "no key waiting" and for "STOP pressed", so the timed reads could not see a stop request at all and simply waited out their timeout.

Fix: ZmHostQuitRequested() was added to the host seam, and all six places that wait for a key now set interpreter_state to STOP. The interpreter leaves its loop as soon as the current opcode finishes, before the parser ever sees the empty line.

A Fatal Error Stops the Machine

Not a JZIP fault, but an A2Z one, and worth fixing. Its fatal() prints to the serial port and then loops forever flashing an LED. On Daisy that would mean a fault in a story file makes the computer unusable until you switch it off.

Fix: fatal() now unwinds to ZmRunStory() using setjmp and longjmp. A bad story puts the user back at the BASIC prompt with a message. A test that feeds the interpreter four kilobytes of random data checks this.

The Display

The screen driver, zm_vt52.cpp, implements JZIP's screen interface by sending VT52 escape sequences and nothing else. It mentions DaisyVideo nowhere, nor shadow RAM, nor any other part of DaisyOS.

That has two results. On the machine, the byte stream goes to the VT52 engine described below, which draws it. Under test, the same byte stream goes to a simulated screen that a test program can read back.

The driver sticks to sequences the DaisyOS terminal implements:

The scrolling region is what holds the status line still while the story text scrolls underneath it. It is reset whenever the story changes the window split.

src/daisyos/vt52.cpp draws a VT52 stream into the DaisyVideo shadow RAM. It was taken out of the display half of terminal.cpp so that anything producing terminal output can share it. It does not talk to a host. There is no serial port in it, no status bar and no menu. A caller that needs those keeps them and feeds bytes in through Vt52Write().

Printable characters are collected into a run buffer and written with a single PutStringAt and one attribute message. One video message per character is too slow to keep up with a program printing a full screen of text.

DaisyOS System Calls

The interpreter reaches DaisyOS through eleven functions and no others. They are declared in include/zmachine/zm_internal.h and written in src/zmachine/zm_host_daisy.cpp. The test harness supplies its own versions of the same eleven.

Here is every DaisyOS entry point the module uses. From src/daisyos/vt52.cpp, for the display:

From src/zmachine/zm_host_daisy.cpp, for the keyboard:

Two changes were made outside the module. Both are small, and both follow the pattern already set by INVADERS, CONWAY and TERM. In basic_internal.h, an include. In basic_execute.cpp, one arm of the immediate-command dispatcher:

if ((rest = MatchCommand(line, "zork")) != NULL) {
  RunZMachine();
  Newline();
  if (showReady) {
    PrintReady();
  }
  return true;
}

RunZMachine() takes over the display, offers the built-in stories if there is more than one, plays the one you pick, and puts the display back before it returns.

Saving and Restoring

Saving and restoring are not available. SAVE and RESTORE reply that the file could not be opened, and play carries on.

The reason is that Daisy has no writable storage of its own. The only writable medium is DaisyFile, reached over the WiFi modem.

Writing would work. CommMsgSendFprint carries up to 255 bytes in a frame, and a saved game is 13,907 bytes, or fifty-five frames.

Reading would not. CommMsgSendFget moves one byte per round trip, each one a request and an acknowledgement, at 38,400 baud. Reading 13,907 bytes that way would take several minutes.

To switch the feature on, add a block read to the DaisyFile protocol. Only the four ZmHostSave* functions need to change. The code above them is finished and is tested by the harness, which uses ordinary files.

Adding a Story

Story files are not supplied. To install one:

tools/mkstory.py ZORK1.DAT > src/zmachine/zm_stories.cpp
pio run -t upload

The tool says what it has done:

ZORK1          v3   84992 bytes flash, 11859 bytes RAM when running

You can give it several stories at once. Mind the flash budget. Each one takes 80 to 90 kilobytes of the Due's 512, of which DaisyOS itself uses about 160.

The Test Harness

The interpreter can be run without hardware. tools/zmtest/ compiles the same source files natively and runs them against a simulated 40 by 25 VT52 screen.

tools/zmtest/build.sh
tools/zmtest/run-tests.sh /path/to/stories
tools/zmtest/zmtest ZORK1.DAT

The simulated screen implements exactly the sequences daisyos/vt52.cpp implements and no others. So a sequence it cannot draw is one the real terminal would not have drawn either.

The suite makes thirty-one checks, each on what actually reaches the screen rather than on the interpreter's internal state. Runs are time-limited, because a regression in the abandon path shows up as a hang rather than as wrong output.

Story File Header Fields

Offsets are from the start of the story file. All values are words, high byte first, unless noted.

Memory Map, Zork I

Limitations

The source, all three firmware images and the Python file server, can be found on GitHub.