The Memotech MTX Series
Memotech Related Tools
Z-Machine and Virtual Memory
Porting Z-Machine and Virtual Memory
By Bill Brendling
The Z-Machine is a virtual computer
for running text adventure games stored in "story files". Originally developed by
Infocom in 1969 for their games, the Z-Machine is considered to be one of the first
uses of virtual memory. Both the Z-Machine specification and tools for developing
story files are now publicly available. As a result there are now many
of the Z-Machine and a large number of
available for free download.
Story files are essentially programs written in z-code, which is the machine language
of the virtual Z-Machine. They can be up to 512KB long, the first 64KB of which can
be regarded as RAM, which can be modified as the program executes. The remaining
space is ROM and does not change during program execution. Fitting both a Z-Machine
emulator and a full sized story file within the 64KB of memory that a Z80 can address
is clearly a challenge.
Before I started on a Memotech implementation, I identified two existing Z80
- ZXZVM for Spectrum +3 and Amstrad PCW.
These use banked memory to store the story files. ZXZVM is composed of two modules: a
machine-independent interpreter core and a machine-dependent front end.
- CPCZVM is a derivative of
ZXZVM ported to Amstrad CPC machines. It uses virtual memory techniques to implement
the Z-Machine with just 64KB of RAM.
For a first draft of a port, I started with the CP/M code from CPCZVM (That download
also includes a version for AMSDOS that I ignored). There were two initial issues
to deal with:
- The CPC runs CP/M 3.0, whereas the MTX only runs CP/M 2.2. It was necessary to remove
all the 3.0 specific calls. Mostly it was not necessary to put anything in their place
as the default behaviour of 2.2 was appropriate.
- It was necessary to replace the code for writing to the display with MTX appropriate
The resulting program worked as a proof of concept, but was hideously slow. It was
however sufficient to make an initial anouncement of the project on
Unfortunately, I did not keep a copy of this version so it no longer exists. I must
get into the habit of using source control on all my projects.
However the feedback was sufficiently encouraging to attempt to produce a better
port for the MTX. The initial target was an MTX with 64KB RAM, a disc drive and CP/M.
The Virtual Memory Implementation in CPCZVM
From the "Technical Information" section of the
web page for CPCZVM:
- The program reads the first 64KB of the game file, padding with 0's if less than 64KB,
and writes out a SWAP.DAT file. A Z-Machine has a maximum of 64KB of RAM. Therefore the
disc which CPCZVM is run from must have at least 64KB free and be writeable. When the RAM
is written to this swap file is updated. This swap file is also re-generated from the game
file when the game is restarted.
- Part of the CPC's memory is used for the virtual memory cache. A page table describes
which virtual memory blocks are loaded and their physical location within RAM. This is
initially populated from the start from the game file. When a read is done, the virtual
memory address is looked up in the page table, and if it is mapped to physical memory then
the physical memory is read. A write is similar to a read with an additional flag being set
if a write has been made to a mapped page. If a virtual memory page is not currently loaded,
then depending on the metric used, a page is chosen to be evicted. If the page has been
modified it is committed to the swap file. Then the new page is loaded into the same physical
location. During game play, any access to virtual memory in the first 64KB comes from the
swap file, and any accesses above 64KB come from the game file. In this way the virtual
memory supports both Z-Machine RAM and Z-Machine ROM.
Looking at the data structures in Z80 RAM used to implement the above, firstly there
is the virtual memory page table, which contains the following data for each mapped virtual
|Z-Machine (virtual) address
|Location in Z80 memory
|Page dirty flag (must be saved before replacing)
|Page age (time since page was last accessed)
Secondly there is the virtual memory buffers, where the data for each loaded virtual page
is stored. A virtual page size of 128 bytes (one CP/M sector) is used.
The process of reading a byte of Z-Machine memory consists of:
- Search the page table to find a page containing the required virtual memory address.
- If no matching page is found:
- Search the page table again, to find the page with the greatest age.
- If this page has dirty flag set, write the corresponding data from Z80 RAM to
appropriate location in SWAP.DAT.
- Update the slot in the page table for the oldest page with the virtual address of
the required new page.
- Load the data for the required new page from either SWAP.DAT or the story file into the
Z80 RAM buffer previously occupied by the oldest page.
- Calculate the offset of the required virtual address from the start of the virtual page.
- Add the location in Z80 RAM of this virtual page to the calculated offset. This gives
the location of the required data byte.
- Reset the age of the current page to minimum value.
- Loop through the page table, incrementing the ages of all the pages which are less than
- Return the required data byte.
The process of writing a byte of Z-Machine memory is similar, except that:
- Having found or allocated the slot in the page table, the dirty flag is set to indicate
that this virtual page will need saving to SWAP.DAT.
- The new value is written to the selected location in Z80 RAM (rather than returning the
value currently there).
It struck me that this repeated reading through the page table was very expensive in CPU
time and could be improved upon.
New CPMZVM Virtual Memory Implementation
CPMZVM uses a virtual memory page size of 256 bytes rather than 128 bytes. This has a number of
- It is easy to split a virtual address into the page number (top two bytes) and offset
within the page (bottom byte).
- It means that the page size is the same as the physical sectors used by type 07 discs.
- It halves the number of pages.
The maximum Z-Machine story file size is 512KB. Thus a maximum of 2048 pages (11 bits).
Rather than the page table used by the CPC implementation, this version has a page index.
The index contains entries for every page in the story file (not just those in memory).
However, each entry is smaller, just 2 bytes, containing either the location of the
corresponding data buffer in memory, or zero if not currently loaded. This table therefore
occupies a maximum of 4KB.
Conversely, the data buffers are more complex. Instead of just containing the page data
each buffer consists of:
|Pointer to previous buffer in age list
|Pointer to next buffer in age list
|Bit 15: Dirty flag. Bits 10-0: Virtual page
|Data for virtual page
|Size of buffer
The first buffer always contains virtual page 0x0000. This page always remains in RAM.
The first 64 bytes of Z-Machine memory contains the
which is frequently referenced by the interpreter, so having these fixed in memory
speeds access to this data. Secondly, the previous and next pointers in this buffer
form the head and tail pointers for a doubly linked list of the virtual data buffers.
Doubly linked lists provide a method of maintaining a dynamicaly sorted list without
having to copy large amounts of data. An item may be removed from its current position
in the list simply by updating the pointers to it in the buffers logically either side
of it. Similarly, it may be inserted in a new position, just by updating the pointers
on the buffers logically either side of the new position, and setting its pointers
to the locations of its new neighbours.
The process of reading a byte of Z-Machine memory with the new virtual memory
- Look up the buffer location for the required virtual page in the index. This is
at a known offset in the index, not a linear search.
- If the result is zero (so the page is not in memory):
- The oldest buffer is at the tail of the buffer pointer. This is found immediately
from the tail pointer.
- If this buffer has its dirty flag set, save the virtual page data to SWAP.DAT.
The page number for this page is given in the buffer.
- Set the new page number for this buffer, and load the required page data from
SWAP.DAT (for R/W memory) or the story file (for R/O memory).
- Unlink the selected buffer from its present location, and re-link it to the head
of the list. This maintains the buffer list in order of last access, so that the
least recently accessed buffer is at the tail of the list.
- Use the last byte of the virtual address as an offset into the data part of the
page buffer, and return the corresponding byte.
As for the original implementation, the write process is very similar to the read
process, except that the buffer dirty flag is set, and data is added to the in-memory
buffer rather than removed from it.
As well as the complete re-writing of the virtual memory system as described in the
previous section, a number of other changes were made, including:
- As noted in the beginning, the original ZXZVM was written as two modules, linked
by a jump table, to separate the Z-Machine emulator and the machine-specific code.
This seperation was removed, and the machine specific routines called directly.
This allowed the code to be packed down into low memory, leaving the maximum space
free for the virtual memory buffers.
- The Z-Machine is more usually loading or storing 16-bit words rather than bytes.
The CPC implementation did this by calling the byte load or save routines twice,
repeating all the resulting memory lookups. This was revised to look up the address
once and then transfer two bytes (unless they crossed a page boundry).
- As mentioned earlier, the Z-Machine frequently references the game header. Since
with this implementation, this is always present at a fixed location, many of these
references were changed to be direct RAM references.
Tests with MEMU suggest that the combination of all these changes speeded up the program
by a factor of around three, making it almost playable.
Large Memory Version
Some MTX/SDX machines have the luxury of additional banked RAM in excess of the 64KB
needed to run CP/M. This additional RAM is typically used for a RAM disc. However the
Z-Machine emulator can make much more efficient use of the memory accessing it directly.
Therefore a second program was produced that, on startup, simply copies the entire
story file into this additional banked RAM. When access to Z-Machine memory is required,
routines in high memory (above 0xC000) swaps in the required RAM bank and copy the
This version is not using virtual memory, the entire game is in RAM. As a result it
is significantly faster.
- This program must be run from physical media, not from the RAM disc.
- The program will, without any warning, overwrite any data in a RAM disc
by data from the story file.
- There must be more additional RAM (above 64KB) than the size of the story file.
For machines with a correctly mapped 512KB of additional RAM this should always
be the case, but if there is less RAM, or if the RAM is not correctly mapped
then the available memory should be checked.
The source code and compiled executables are in a zip file which can be downloaded from
the Memotech forum
here. In this zip:
- cpmzvm.com - The version for 64KB machines, using virtual memory as described.
- m576zvm.com - The version for machines with 64+512KB of RAM, loading the entire
story file into RAM.
|The file is also
hosted on this website and can be downloaded below