A 3.5 inch floppy disk lying on a wooden table, lit by a lantern, with a handwritten label: Lore of the Ember, Disk 1

The problem

On the Atari ST, Lore of the Ember will ship on two double density floppies. No custom format, no extra tracks: plain 720 KB disks, the kind we all used back then. Five acts, four levels per act, five bosses, the intro, the title screen and the program itself: all of it has to fit.

But the first disk was already almost full. The program and its menu module, the title screen, the intro, the loading screen and the first level took 642 KB out of the 711 available. That left 69 KB, and level 2, with its tile set and its map, needs 85. It no longer fit.

Most games of the time that fit on two floppies had the same answer: nothing on the disk is stored as is. Every file is packed, and the game unpacks it while loading. That is what I did.

The format: ZX0

I chose ZX0, by Einar Saukas. It is an LZ77 style format designed for small machines: a packed file is just a sequence of three kinds of blocks.

  • Literals: "copy the next N bytes as they are".
  • A copy with the same offset as the last one: "copy N bytes from the same distance back as last time".
  • A copy with a new offset: "copy N bytes from D bytes back".
The sentence "the stone, the ember, the stone" unpacked in five blocks: 11 literals, a copy of 4 bytes from 11 back, 5 literals, a copy of 2 bytes with the same offset, then a copy of 9 bytes from 22 back
A 31 byte sentence, unpacked block by block. The arrows start from what was already written: almost half of the text is never stored, only pointed at.

The numbers (lengths, offsets) are written as interlaced Elias gamma codes: a small number takes few bits, a large one takes more, and the unpacker reads them bit by bit without ever knowing their size in advance. The offset is split in two: its high part as a gamma code, its low part in a full byte.

The whole point is on the unpacking side. It takes a few dozen 68000 instructions and it is fast: the very same unpacker already serves the intro and the loading screen.

The packer: salvador

Finding the best way to cut a file into blocks is the packer's job, and that is the slow part. The original tool searches for the optimal parse; I replaced it with salvador, by Emmanuel Marty. It produces the same format, with almost the same density, in a second or two per file.

One format detail played a trick on me: ZX0 comes in two flavours, and the unpacker I had written for the intro reads the second one. In the standard version, only the high part of the offsets has its bits inverted; in the one the game reads, every gamma code does, lengths included. Rather than touch the unpacker, my packing tool fixes salvador's output: it reads the stream back, finds every length bit and flips it. The bits stay where they are, only their meaning changes, and nothing is lost.

Each packed file is then read back by a reference unpacker, which has to give back the original byte for byte. Otherwise the disk is not built.

Unpacking without extra memory

The game fits in one megabyte, give or take a thousand bytes. Adding a second buffer to read the packed file into before unpacking it is out of the question.

The solution is a classic: in-place unpacking. The packed file is read at the end of the destination buffer, and the unpacker writes from the start. It moves through its input more slowly than it writes, since every bit read produces several bytes, but it starts with a large head start. As long as the writing never catches up with the reading, nothing is overwritten before it has been read.

Three states of the same buffer: the packed stream placed at the end, then the unpacked part growing from the start while the reading keeps its head start, then the whole file unpacked
A single buffer: the packed file arrives at the end, the unpacked file is built from the start.

That "as long as" gets checked: for each file, my tool simulates the unpacking and records how close the writing ever gets to the reading. If the game's buffer does not have that margin, the file stays unpacked and the game reads it as before. It recognises a packed file by its eight byte header: a signature, then the unpacked size.

The odd address trap

The first packed disk crashed on the first load. The unpacker went off copying bytes from a nonsensical address, and the program stopped dead.

The cause was upstream. A packed file can have any length, and I placed it exactly at the end of the buffer: depending on its size, it could start at an odd address. But reading the floppy goes through the DMA, which can only write to even addresses. Every byte landed one step off. The unpacker was reading a stream it no longer recognised, and on its first copy, it fetched its bytes from anywhere.

The fix is one line: the file goes to the even address just below, one byte earlier if needed, and my tool counts that byte in its margin.

Three rows of memory cells from $1000 to $1009. The stream requested from $1003; the DMA writes it from $1002, and the unpacker reads B instead of A; placed at $1002, it reads A
The floppy DMA cannot start on an odd address: it writes from the even address just below, and the whole stream slides by one byte.

The result

Space on the floppy Unpacked Packed
Title screen (logo, title and its animation) 82 KB 9 KB
Level 1 (tiles and map) 66 KB 16 KB
Level 2 (tiles and map) 85 KB 19 KB

The first disk went from 69 KB free without level 2 to 173 KB free with it. The hard disk version stays unpacked: space is not an issue there, and it loads without unpacking anything.

Two 711 KB bars. Before: program 340 KB, menu module 38, intro 107, loading screen 7, title screen 82, level 1 66, and 69 KB free where level 2, 85 KB, does not fit. After: title screen 9 KB, level 1 16, level 2 19, and 173 KB free
The first floppy, counted in 1 KB blocks. The program, its menu module and the intro have not moved yet.

What comes next

The biggest file on the disk is still the program itself: 340 KB, almost half of it. It packs to roughly half its size. But it cannot unpack itself: it will need a small launcher that reads it packed, unpacks it in memory, puts its addresses back in place and hands over control, all without going past the megabyte. That is the next job, and after it, only the tidying up will be left: the start and Act I on the first disk, the four other acts on the second.