zig-shrinkit

ShrinkIt archives, in Zig 0.17, both ways round. This reads and writes NuFX — the format Andy Nicholas's 1989 archiver produces, which is what almost everything on the Apple II archives is stored in — and implements both of the compressors Kent Dickey wrote for it, Dynamic LZW/1 and Dynamic LZW/2.

$ shrinkit list "ProDOS 2.0.3 1993-05.shk"
ProDOS 2.0.3 1993-05.shk: 1 record
  PRODOS.2.0.3                     file             15942 -> 15914     LZW/1

$ shrinkit extract MERLIN1.SDK --to out/
MERLIN.S1 (143360 bytes)

$ shrinkit create rebuilt.sdk --disk MERLIN.S1 out/MERLIN.S1

src/crc.zig	the three CRCs, which are one polynomial and two seeds
src/rle.zig	the run-length step, both ways
src/lzw.zig	the dictionary, the bit packing, and the width rule
src/stream.zig	the chunked streams: LZW/1 and LZW/2, compress and decompress
src/nufx.zig	reading an archive: master header, records, threads, Binary II
src/writer.zig	writing one
src/main.zig	the shrinkit command

Nothing here allocates unless it has to. An archive is one []const u8, names and thread bytes are slices into it, and the compressors work in caller-given buffers; the only entry points that take an allocator are the ones that hand back bytes which are not in the file, because they were compressed.

The API documentation is generated from the doc comments, which are most of the explanation of why NuFX is the shape it is.

Adding it to a project

zig fetch --save git+https://git.jcollie.dev/jeff/zig-shrinkit.git

const shrinkit = b.dependency("shrinkit", .{ .target = target });
exe.root_module.addImport("shrinkit", shrinkit.module("shrinkit"));

What a ShrinkIt archive is

Forty-eight bytes of master header and then a run of records, each of which is a header, a filename and some number of threads. A thread is one stream of bytes with a class saying what it is for — a filename, a comment, a file's data fork, a disk image — and a format saying how it was squeezed. A .SDK is an archive whose one record holds a disk; a .SHK usually holds files and sometimes holds a disk as well. They are the same format, and so is a .BXY, which is a .SHK with 128 bytes of Binary II wrapped round it.

Every thread's bytes follow the whole array of thread headers, one after another in the order the headers are in, so finding a thread's data means adding up the lengths of the ones before it. That is also why a malformed archive is exactly the shape that walks off the end of the file, and why the reader here bounds every step against the bytes it was handed.

The compression

Run-length encoding, then LZW, in four kilobyte chunks. Four kilobytes because a track of a 5.25-inch disk is four kilobytes and this began as a program for compressing disks — which is also why every compressed stream starts with a byte holding a disk's volume number, whether or not there is a disk anywhere near it.

The run-length step

A run becomes three bytes: a delimiter, the value, and the count less one. The delimiter is named in the stream rather than fixed by the format, and is always $db. Because it is a byte like any other, a byte that happens to be the delimiter has to be written as a run of one — three bytes to say one — which is why the step can make a chunk bigger, and why the format has a way of saying it did.

Three things about the encoder are not in any description of it and were counted off the archives to hand:

• A run of four or more is escaped and a run of three is not, even though three breaks exactly even. 88 runs of four escaped against none left alone; 3,462 runs of three left alone against none escaped.
• A run longer than 256 is more than one escape, and the last piece of it is escaped too, however short. So 259 of a byte come out as $db v $ff followed by $db v $02, where a fresh look at those last three would have written them plain.
• One archive of the nine disagrees about the first of those and escapes every one of its 173 runs of three. So the threshold is Options.min_run rather than a constant, and four is the default because that is what eight of the nine did.

The LZW step

Ordinary LZW: codes nine to twelve bits wide, $100 meaning "start the table again", and the first real entry at $101. Two things about it had to be read off a real archive.

Codes are packed low bit first. That one announces itself — read them the other way round and the first nine bits of a stream come to a code nothing has defined.

The code width goes up one code early, at 2^width - 1 rather than 2^width. That one does not announce itself at all: the first chunk decodes perfectly either way and everything after it is wrong. It is only early from the decoder's side. A decoder learns its table entry from the code before the one it is reading, so its table is always one behind the encoder's, and growing one code early is what keeps the two counting together — which is presumably why nobody writing the format down thought it worth a sentence.

The table holds 3,839 entries, not the round 4,096 it is usually described as having, because the last code twelve bits can name is $fff and the first one the dictionary hands out is $101. A decoder never notices the difference: entries past that point are ones no code can reach. An encoder very much does — it hands out a code of $1000, the bit writer quietly keeps the low twelve bits, and the stream decodes perfectly up to that point and is rubbish afterwards.

The chunked streams

LZW/1 and LZW/2 are the same walk with different bookkeeping. LZW/1 starts each chunk with an empty table and carries a CRC of the whole stream in front of it. LZW/2 keeps the table, the code width and the last code across chunks, starting again only when a chunk turns out not to be worth compressing or the table fills. Getting that wrong is not obvious: the first chunk decodes perfectly and everything after it is wrong.

The last chunk is a whole chunk. The compressor zeroed its buffer and filled what it could, so the tail of the file is padding, and a reader knows to stop only because the thread header said how long the file is.

Every LZW/1 stream in the archives to hand is one byte longer than its codes need, and that byte is whatever happened to be in ShrinkIt's buffer — a zero in 127 of 173 threads and something arbitrary in the other 46. It is slack rather than content, so no compressor can reproduce it; Options.pad_tail writes a zero there anyway, because a decoder that reads a code before asking whether it still wants one would run off the end of a stream that did not have it. LZW/2 has none of this: every chunk of it carries its own length, and every one of those lengths is exactly the bytes its codes need.

The CRCs

Three of them, one polynomial — $1021, most significant bit first, no reflection, no final xor — and two seeds, which is worth knowing before spending an evening on it.

where	seed	over
thread header	$ffff	the file's own bytes
LZW/1 stream header	0	the file padded out to whole chunks
record header, master header	0	everything after its own two-byte field

A thread can carry one, the other, both or neither, and this checks whichever it is given. That the two in a record header are seeded the other way from the thread CRC a few bytes away is not something anybody would guess; it is what a real archive says.

Reading an archive

const archive = try shrinkit.nufx.open(bytes);
var records = archive.iterate();
while (try records.next()) |record| {
    for (0..record.threads) |t| {
        const thread = try record.thread(bytes, @intCast(t));
        if (thread.class != .data) continue;
        const plain = try shrinkit.nufx.unpackAlloc(gpa, archive, record, thread);
        defer gpa.free(plain);
        // ...
    }
}

For the common case of a .SDK, shrinkit.nufx.diskAlloc(gpa, bytes) finds the first disk image and hands it back.

Record.length is the length to believe, which is not always the thread's own: a disk image says how big it is twice, and ShrinkIt versions disagreed often enough that the file type note warns of it. MERLIN1.SDK calls a 143,360 byte ProDOS volume 131,072 bytes, and the CRC inside its own stream only comes out right at the length the record gives.

Writing an archive

var builder: shrinkit.writer.Builder = .init(gpa, .{});
defer builder.deinit();
try builder.addFile(.{ .name = "HELLO", .data = source, .file_type = 0x04 });
try builder.addDisk(.{ .name = "MY.DISK", .data = image });
const bytes = try builder.toOwnedSlice();

What comes out is a version 2 master header and version 3 records, which is what ShrinkIt 3.4 and GS/ShrinkIt write: the name in a filename thread rather than in the record's own name field, one data thread per record, LZW/2 unless that turns out not to pay, and every CRC filled in. Binary II is deliberately read-only — it is 128 bytes of ProDOS attributes wrapped round an archive, and nothing is improved by producing more of them.

What is implemented

Thread formats 0 (stored), 2 (LZW/1) and 3 (LZW/2), both directions. Binary II unwrapping. Every CRC in the format, checked on the way in and written on the way out.

What is not here

• Format 1, squeeze — Huffman, out of the CP/M world, and rare.
• Formats 4 and 5, twelve and sixteen bit Unix compress. GS/ShrinkIt could write these and hardly ever did; none of the archives to hand has one.
• Writing Binary II wrappers.
• Options in a record's option list, which are read past rather than parsed.

Tests

In the tree

zig build test runs the unit tests, the round trips and the fuzz properties, and needs nothing that is not in the repository.

The round trips are the ones that matter. A decoder tested against its own encoder proves only that the two agree — which is exactly the failure mode LZW/2 invites, since its table, code width and last code all cross chunk boundaries.

Against real archives

The claims above about what ShrinkIt actually does were counted, not guessed, and the counting is a test:

zig build test -Dcorpus="$HOME/dev/Apple Disks" --summary all

It walks a directory of real .shk, .sdk and .bxy files, decodes every thread, checks whichever CRCs each one carries, and then recompresses what came out and compares it with the bytes ShrinkIt wrote. Those archives are somebody else's software and are not in this repository, so the test is opt in and is counted as skipped without it — which is also why the Forgejo workflow does not run it.

Against the 29 archives to hand, at the time of writing:

corpus: 29 archives, 288 records, 576 threads
  stored 365, LZW/1 192, LZW/2 19, unsupported 0
  CRCs checked: 29 master, 288 record header, 19 thread
  recompressed: 127 exact, 46 bar ShrinkIt's slack byte,
                8 with the three-run variant, 30 round tripped only

Everything decodes and every CRC checks. Of the 211 compressed threads, 181 come back as the bytes ShrinkIt wrote — 127 exactly, 46 identical but for the unreproducible slack byte, and 8 with the three-run variant of the run-length step described above. The remaining 30 round trip correctly but are not the same bytes: 19 LZW/2 threads and 11 LZW/1 ones, where some further difference in ShrinkIt's compressor has not been worked out. That distinction is the honest form of the claim, so it is written down rather than rounded off.

Against another implementation

zig65 has a ShrinkIt reader of its own, written before this one and sharing no code with it. An archive written here by each of the three methods is read back by it byte for byte, which is the cross-check that matters: an encoder and a decoder from the same hand can agree with each other and with nobody else.

Fuzzing

tests/fuzz.zig holds the properties. Two things drive them:

zig build fuzz --fuzz                 # Zig's fuzzer, with a web interface
zig build fuzz --fuzz=1M              # a bounded run, then a report
zig build fuzz --fuzz -Dfuzz-filter=lzw2
zig build fuzz-run                    # a loop of our own, a minute of each

Of the nine targets, five feed the library input nobody wrote, two feed it input that is nearly right — which is the harder thing to make — and two take a single piece of code apart. Arbitrary bytes are turned away at the door — nufx.open wants six bytes of magic before it will look at a record, and a compressed stream wants a plausible header and then a chunk header before it reads a single code — so the paths worth worrying about are never reached that way. mutated and mutated-archive compress or archive something real and then change a few bytes of the result, which lands the damage inside a code stream or a thread header. Xored rather than replaced, so that "changed nothing" is a case the generator reaches for free and the round trip falls out of the same target.

What a damaged stream must do is not decode correctly — it may decode to anything, or fail — but do the same thing both times it is asked, into a buffer pre-filled with a different byte each time. That is the property that would catch a decoder reading the dictionary's undefined entries, which is the one place where a bounds check going wrong reads uninitialised stack rather than crashing.

The last two targets exist because the bit packing and the CRC were rewritten for speed, and both are the sort of code that is right for every case anybody thinks of. bits packs a run of nine- to twelve-bit codes and reads them back, then re-reads from every truncation over the last six bytes — the place where BitReader.take's four-at-a-time fast path stops being safe — and insists that running out yields nothing and leaves the reader where it was rather than half way into a code. crc checks the table against a bitwise CRC written out separately, and checks that a seed carried across a split gives what one call over the whole thing gives. That second property is not decoration: the decoder works the LZW/1 stream CRC out a chunk at a time and compares the total with a number written before any of those chunks existed, so a CRC that did not compose would check out on a one-chunk file and fail on every larger one.

At the time of writing that is 240 million inputs without a finding, a hang or a leak.

Zig's own fuzzer is the one with coverage feedback, and it needs the test binary compiled by LLVM: the self-hosted backend that Debug uses otherwise emits no coverage instrumentation, and the run ends with pcs_len was zero. build.zig sets use_llvm on every test binary for that reason, and for kcov, which cannot read that backend's debug info either. A finding prints input saved to '.zig-cache/f/crash' above the report. The bounded report has one entry per test binary, labelled with its first fuzz test, though every fuzz test in it ran.

tools/fuzz.zig predates a working fuzzer and stays, because it is reproducible from a seed and cheap to run in CI: it mutates the seeds beside each target, hands the result over, and says when something comes back with an error. It is blind, though — the record header thread count that overflowed while being multiplied went unnoticed through those 240 million inputs, and Zig's fuzzer found it within its first two hundred thousand.

Speed

zig build bench                       # three workloads it makes up
zig build bench -- ~/dev/Apple\ Disks/Merlin/MERLIN1.SDK

Megabytes a second on this machine, best of nine rounds, with the same input and the same output before and after — the compressed sizes are identical, so none of this changed what gets written:

workload	compress LZW/1	compress LZW/2	decompress LZW/1	decompress LZW/2
disk	137 → 321	1272 → 1739	152 → 406	161 → 3355
source	65 → 114	117 → 159	75 → 166	86 → 306
noise	33 → 91	42 → 118	170 → 470	170 → 37036

Four changes, in the order they were worth making:

• The CRC nobody asked for. The decoder worked out the LZW/1 stream CRC over every chunk of every stream — including LZW/2 streams, which do not carry one, so it was eight shifts a byte to produce a number that was then thrown away. That one line is most of the LZW/2 column.
• A table for the CRC. Half a kilobyte of it. A LZW/1 stream really does CRC every chunk it decodes, padding included, so this runs over rather more than the file.
• Bits a byte at a time. A code is nine to twelve bits and lies inside three bytes; reading it a bit at a time cost twelve branches to do what two shifts do. Worth about 40% of the LZW-bound work in both directions.
• Padding only the chunk that needs it. The compressor zeroed a four kilobyte buffer before filling it, when only a short last chunk has anything left to pad.

Two more that looked obvious and were not, both rejected on the measurement: making the encoder's hash table cheap to clear, and putting the key in the hash slot so a probe need not touch the dictionary. Each made the workload it was aimed at faster and everything else slower — the tables are 16 KB, and anything that doubles them costs more in cache misses than it saves in work.

The API documentation

https://jeff.jcollie.page/zig-shrinkit/, rebuilt from main on every push.

zig build docs          # into zig-out/docs
zig build docs-serve    # and read it at http://localhost:8000

It has to be served rather than opened: the viewer Zig emits fetches sources.tar and main.wasm at runtime, and a browser refuses both from a file:// page. That is the same reason zig std runs a server.

Building

Getting the code

The repository lives in two places that carry the same history. The Forgejo instance at https://git.jcollie.dev/jeff/zig-shrinkit is the web-visible one:

git clone https://git.jcollie.dev/jeff/zig-shrinkit.git

and it is also on the Radicle network, where the repository's identifier is

rad:z2WJe1cfqeP93RFAG6vZWoJ2wBhvD

and

rad clone rad:z2WJe1cfqeP93RFAG6vZWoJ2wBhvD

fetches it from any node that seeds it. A Radicle repository is findable by that identifier and by nothing else, which is why it is written out here.

The devshell

nix develop
zig build test

The devshell carries Zig 0.17.0 from nixpkgs, kcov and perf.

Licence

MIT. See LICENSES/MIT.txt.