04-compression.md

04 - RNC ProPack

Every file on the disc whose name ends in .cru is compressed with RNC ProPack method 1 -- Rob Northen Computing's packer, the one whose header magic is the three bytes RNC. cru is for "crunched".

84 of the 91 files are packed. They occupy 2,639,029 bytes on the disc and expand to 10,284,352 -- an overall ratio of 25.7 %, just under four to one. The seven that are not packed are the two SFX banks, the first-stage loader, and the four boot files.

tools/rnc.py unpacks them, and every one of the 84 has been verified against the CRC-16 stored in its own header. No file on the disc fails.

Header

Eighteen bytes, big endian:

Offset	Size	Field
0	3	RNC
3	1	method -- always 1 here
4	4	unpacked length
8	4	packed length
12	2	CRC-16 of the unpacked data
14	2	CRC-16 of the packed data
16	1	leeway
17	1	chunk count

The CRC is the ordinary reflected CRC-16 with polynomial 0xA001 and zero initial value.

leeway is the number of extra bytes needed to unpack the file in place: you load the packed file at the top of its destination buffer and unpack downward into itself. On this disc leeway is 0 for 79 files and 1 for five of them (L1_Int_G, L1_LLoad, L7_Int_E, Lb_Int_G, Lx_MSprF), which is what in-place unpacking of a well-compressed file looks like -- the output almost never catches up with the input.

The bit stream

This is the part that makes method 1 awkward to reimplement, and the reason tools/rnc.py checks the CRC on every unpack.

Bits are read least-significant-bit first out of little-endian 16-bit units, which is the same thing as an LSB-first reader over the plain byte sequence. The first two bits of the stream are flags (the second one marks an encrypted stream; no file here is encrypted).

But the reader is always two bytes ahead of the bits it is handing out. It refills sixteen bits at a time by consuming two bytes, while keeping a peek at the next two in the top half of a 32-bit buffer. That matters because the stream is interleaved with literal bytes: when the decoder is told to emit N literal bytes it takes them from wherever the byte pointer currently is -- which is past the unit the bit reader is chewing on -- and afterwards refills everything above the residual bit count from the new position, without resetting the bit count. The leftover bits of the unit before the literal run survive the run and are consumed next.

Get that wrong and the file still decodes for a few hundred bytes before falling apart, which is exactly why the CRC check is not optional.

The token loop

skip 2 bits
while output is short of the target:
    read three Huffman tables:  raw, len, pos
    subchunks = 16 bits
    while subchunks--:
        n = value(raw)                  number of literal bytes
        if n: copy n literal bytes, then resynchronise the bit reader
        if subchunks:                   the last subchunk has no match
            offset = value(len) + 1
            count  = value(pos) + 2
            copy count bytes from output[-offset]

The table names are the ones ProPack's own source uses, and they are crossed over: the second table read gives the match offset and the third gives the match length.

A table is 5 bits of leaf count, then 4 bits of code length per leaf, assigned canonically in increasing length order and stored bit-reversed because the stream is LSB-first. Decoding a leaf gives an index i; the value is i for i < 2, and otherwise (1 << (i-1)) | read_bits(i-1) -- a plain number-of-significant-bits encoding.

What compresses and what does not

Type	Files	Packed	Unpacked	Ratio
GSBlk	11	1,154,652	3,514,368	32.9 %
Int_E/F/G	33	767,270	2,703,360	28.4 %
XMemI	11	109,788	1,762,816	6.2 %
LLoad	11	141,032	584,904	24.1 %
SprDR	11	20,536	360,448	5.7 %
CompC	1	77,449	356,672	21.7 %
ReloD	1	65,346	262,144	24.9 %
TPage	1	50,428	216,924	23.2 %
ChipI	1	19,143	202,332	9.5 %
CompE	1	156,373	184,704	84.7 %
MSprF	1	38,036	67,840	56.1 %
MSprM	1	38,976	67,840	57.5 %

Lx_CompE is the outlier at 84.7 %, and that is not because ProPack failed: its payload is already compressed with a second, different scheme -- eight blocks tagged CHFI. Re-compressing every unpacked file with zlib confirms it: everything else lands between 0.09 and 0.64, Lx_CompE at 0.825. See 08-cinematics.md.

SprDR and XMemI pack to 6 % because they are fixed-size tables that are half empty (09-level-data.md).

Fixed unpacked sizes

Every file of a given type unpacks to exactly the same length, whatever the level:

Type	Unpacked size
GSBlk	319,488
Int_?	81,920
XMemI	160,256
SprDR	32,768
LLoad	varies (40,526 - 56,680)

The last non-zero byte, though, moves around: L1_GSBlk uses 95.2 % of its 319,488 bytes, L5_GSBlk 90.8 %, Lc_GSBlk 73.9 %. So the data was padded to a fixed length before packing, and the fixed length is the size of the buffer the loader allocates. The loader never has to ask how big a file is; it knows, from the type, before it reads a byte.

LLoad is the exception because it is executable code rather than a buffer (05-loader.md).