Legaia LZS compression Confirmed

At a glance

In the game

Invisible to the player - it is the unpack step behind every loading pause. Meshes, textures, scene MANs and the monster archive all pass through it.

Magic / marker

None - a bare LZSS bitstream. The decoded bytes carry the magic (TIM, TMD, MES, ...), which is why you must check them.

Lives in

Wrapped around most PROT.DAT entries; selected by the asset-type dispatcher when its copy_only flag is zero.

Retail reader

FUN_8001A55C (decoder only - Sony's packer never shipped)

Parser

crates/lzs - decompress, decompress_tracked, parse_container / decompress_container_strict, compress / compress_optimal; CLI lzs-decode

Confidence

Confirmed - traced from the decoder's disassembly and round-tripped over the whole PROT corpus.

How it works

LZSS keeps a window of the most recent output. Each item in the stream is either a literal (one byte, copied straight through) or a back-reference ("copy n bytes from position p of the window"). A flag byte ahead of every eight items says which is which. The stream carries no length and no end marker, so the caller always supplies the decompressed size. Legaia's variant makes three specific choices:

• 4096-byte sliding ring buffer (the dictionary of recent output that back-references copy from), initialised to zero.
• Initial write position 0xFEE (4078).
• Control byte: 8 bits, LSB-first - bit set = literal, bit clear = back-reference.

Token layout

A back-reference packs a 12-bit absolute window position and a 4-bit length into two bytes:

Pseudocode

let mut window = [0u8; 4096];
let mut window_pos = 0xFEE;
let mut control = 0u32;

while out.len() < expected_output_size {
    if (control & 0x100) == 0 {
        control = (input[src] as u32) | 0xFF00;
        src += 1;
    }
    if (control & 1) != 0 {
        // LITERAL: copy 1 byte
        let v = input[src]; src += 1;
        out.push(v);
        window[window_pos] = v;
        window_pos = (window_pos + 1) & 0xFFF;
    } else {
        // BACK-REF: 2 bytes encode (12-bit absolute window position, 4-bit length-3)
        let b0 = input[src] as u32;
        let b1 = input[src + 1] as u32;
        src += 2;
        let base = b0 | ((b1 & 0xF0) << 4);
        let len = (b1 & 0x0F) + 3;
        for n in 0..len {
            let v = window[(base + n as u32) as usize & 0xFFF];
            out.push(v);
            window[window_pos] = v;
            window_pos = (window_pos + 1) & 0xFFF;
        }
    }
    control >>= 1;
}

The 0xFF00 mask is how the control register knows when to refill. Each shift right moves one of the eight set high bits down; after eight shifts bit 8 is clear, and the test at the top of the loop reads the next flag byte.

A back-reference copies byte by byte and writes each byte to the ring as it goes, so a reference may overlap its own output (the run-length case). The copy stops early if it reaches the expected output size.

Container format

Some PROT entries hold several independently compressed sections behind a small header. The header is the asset descriptor layout: two u32 header words, then 8-byte (size, byte_offset) pairs, where the size's low 24 bits are the section's decompressed length and its high byte is the asset type.

Encoding (re-packing)

The retail game ships only the decoder; there is no Sony encoder to reverse. legaia_lzs::compress is an encoder written fresh for re-packing edited assets - it is what lets the randomizer / disc patcher put a modified monster, script or texture back into the same slot on the disc:

• An LZSS matcher with one-step lazy matching (defer a match by a byte when the next position yields a strictly longer one) whose output the retail decoder accepts byte-for-byte - not a bit-exact clone of Sony's packer.
• Correctness criterion: decompress(compress(x)) == x, checked by round-tripping every compressed entry on the disc.
• The lazy step matters for in-place editing. A purely greedy parse overshoots a scene MAN's original footprint by a handful of bytes, and those footprints have no compressed slack; with the lazy step every scene MAN but one fits its exact original span.
• compress_optimal is a slower shortest-encoding parse (a dynamic program over the token graph). Its output is never longer than compress's, and it closes the last couple of bytes on the few retail streams whose footprint has zero slack.

A linear-history match at distance d maps onto the ring-buffer back-reference position (0xFEE + i - d) & 0xFFF, where i is the output position; capping the emitted distance at 4096 - 18 keeps every in-copy read (including the self-overlapping run-length case where d < len) unambiguous. It does real compression (not literal-only), so re-packed streams fit the slack in fixed-size slots like the monster archive's 0x14000-byte records - the story told in the disc-patching write-up on LZS slots.

Where LZS is consumed

The asset-type dispatcher - the routine that routes each loaded asset to its format handler - calls the LZS path when its copy_only flag is zero. See asset type dispatcher. The descriptor-pair containers above are walked by FUN_80020224 (asset descriptor).

How we know

The algorithm is read straight off the retail decoder's disassembly, and the from-scratch decoder and encoder round-trip every LZS entry on the disc.

Source of record: docs/formats/lzs.md.

See also