79 of the 111 files on the disc are packed, and none of them uses a codec
that has a name on its front. A scan for RNC, IMP!, ATN!, PP20,
PP11, XPKF, CrM!, LZX and SQSH over every file returns nothing
(tools/scan.py). What the packed files have instead is a four-byte
big-endian header, an entropy of 6.7 to 7.8, and a decruncher 201 bytes long
sitting at hunk offset 0x703E of /Legends.
ULONG offset to the trailer (always filesize - 4)
BYTE[] packed data
ULONG checksum -- never read
ULONG unpacked size
The first field looks like a length and is not. /Legends uses it as an
offset:
7452 subi.l #4,heap ; back the bump allocator up four bytes
745C movea.l heap,a0
7462 move.l (a0),saved ; keep what is about to be overwritten
7468 bsr.w load_file ; Open / Seek / Seek / Read / Close
746C movea.l heap,a1
7472 move.l (a1),d0 ; d0 = the header
7474 move.l (a1,d0.l),unpacked_size ; <-- a longword AT file + header
747C lea 4(a1),a0 ; a0 = the packed data
7480 bsr.w unpack ; 0x703E
Because the header is always filesize - 4, file + header is the last
longword of the file, and that is the unpacked size. The longword before it
is the cruncher's checksum, and the decruncher steps over it with a bare
subq.w #4,a0 without ever looking at it. Nothing on this disc verifies a
checksum it carries in every packed file.
tools/pak.py is a transcription of the routine, not a reimplementation from
a format description -- registers, backwards buffer and all. The routine is
the specification.
It reads its bitstream backwards, a longword at a time, from twelve bytes before the end of the file, using the classic sentinel-bit register:
7052 MAIN: lsr.l #1,d0 ; C = bit, and d0 shrinks
7054 bne.b .have ; d0 non-zero: bits left
7056 move.l -(a0),d0 ; refill from further back in the file
7058 roxr.l #1,d0 ; the old bit becomes the new sentinel
705A .have: bcs.b MATCH
and it writes its output backwards too, into the same buffer, from
payload + unpacked size down to payload. It stops when the write pointer
reaches the start.
The token set:
| First bit | Then | Meaning |
|---|---|---|
0 |
0, 3-bit n |
literal run of n + 1 bytes (1 to 8) |
0 |
1 |
match, 2 bytes, 8-bit offset |
1 |
2-bit c = 0 |
match, 3 bytes, 9-bit offset |
1 |
2-bit c = 1 |
match, 4 bytes, 10-bit offset |
1 |
2-bit c = 2, 8-bit n, 12-bit offset |
match, n + 1 bytes (1 to 256) |
1 |
2-bit c = 3, 8-bit n |
literal run of n + 9 bytes (9 to 264) |
A match copies from a2 + offset, that is, from data already produced
further along the output -- because the output is being built from its end.
This is Bytekiller. The backwards longword bitstream, the sentinel bit,
the trailer of [first chunk][checksum][unpacked size] read in that order,
and that exact table of four offset widths and two literal-run forms are the
Amiga demo-scene cruncher of the same name -- the one best known outside the
scene as the packer Eric Chahi used for Another World in 1991. Krisalis
shipped it in a 1996 CD32 title with the checksum check taken out.
| Class | Files | On disc | Unpacked | Ratio |
|---|---|---|---|---|
Full-screen art (*.Pak in root) |
21 | 958,988 | 1,805,696 | 53.1 % |
| Fonts | 4 | 14,120 | 61,600 | 22.9 % |
Sprite banks (sprites*.pak) |
34 | 1,022,404 | 3,480,712 | 29.4 % |
Text (English/French/German.Pak) |
15 | 60,448 | 115,440 | 52.4 % |
Level code (LevelN/Legends.Pak) |
5 | 2,109,680 | 6,372,776 | 33.1 % |
| Total | 79 | 4,165,640 | 11,836,224 | 35.2 % |
Best ratio on the disc: fontwhit.pak, 3,476 bytes to 19,712 (17.6 %).
Worst: Warp.Pak, 53,960 to 64,000 (84.3 %) -- a full screen of star field
and noise that barely packs at all.
The five LevelN/Legends.Pak are the interesting case. Each is a hunk file
whose single HUNK_CODE contains a .Pak stream, and whose declared hunk size
is not the packed size but the unpacked one:
| Level | File | Hunk allocation | Unpacked | Slack |
|---|---|---|---|---|
| 1 | 588,964 | 1,531,604 chip | 1,531,604 | 0 |
| 2 | 521,516 | 1,469,276 chip | 1,469,276 | 0 |
| 3 | 339,948 | 1,143,092 chip | 1,143,092 | 0 |
| 4 | 350,464 | 1,142,964 chip | 1,142,964 | 0 |
| 5 | 308,788 | 1,085,840 chip | 1,085,840 | 0 |
Zero slack on all five. LoadSeg is being used as a chip-memory allocator:
AmigaDOS reads the file into a block sized for the unpacked data, and the game
expands it in place. The hunk is flagged chip and there is no relocation
table, because there is nothing in it to relocate until it has been unpacked.
python tools/scan.py _work/ext # no magic anywhere
python tools/unpackall.py # all 79, with ratios and checksums
python tools/pak.py _work/ext/KrisLogo.Pak