Legaia LZS compression Confirmed

Overview

A standard LZSS variant with three Legaia-specific choices:

• 4096-byte sliding ring buffer (the dictionary of recent output that back-references copy from), initialised to zero.
• Initial write position 0xFEE (3054).
• Control byte: 8 bits, LSB-first (each bit says whether the next item is a literal byte or a back-reference).

Pseudocode

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

while !done {
    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 above is the trick that lets the control register tell the decoder when to refill: every shift right pulls a 1 bit into bit 8, and after 8 shifts bit 8 reaches the test position and triggers a refill from input[src].

Container format

crates/lzs::parse_container handles the multi-section player.lzs-style wrapper used by some PROT entries (entries of PROT.DAT, the disc's main asset archive) - a length-prefixed array of independently-compressed sections concatenated together.

Encoding (re-packing)

The retail game ships only the decoder; there is no Sony encoder to reverse. crates/lzs::compress is an encoder written fresh for re-packing edited assets (the randomizer / disc patcher uses it):

• An LZSS matcher with one-step lazy matching whose output the retail decoder accepts byte-for-byte - not a bit-exact clone of Sony's packer.
• Correctness criterion: decompress(compress(x)) == x, validated by a disc-gated round-trip over the real PROT corpus.
• The lazy step packs tightly enough that a re-packed asset fits its original footprint even where that footprint has no compressed slack (every scene MAN but one fits its exact original span).

A linear-history match at distance d maps onto the ring-buffer back-reference base (0xFEE + i - d) & 0xFFF; capping the emitted distance at 4096 - MAX_MATCH keeps every in-copy read (including the self-overlapping RLE 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.

Where LZS is consumed

The asset-type dispatcher (FUN_8001F05C - 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. Standalone-shaped LZS containers (with the descriptor-pair walker in asset-descriptor.md) are also recognised by crates/lzs.

See also