psx_pack/
lib.rs

1// SPDX-License-Identifier: GPL-2.0-or-later
2//! Guest-side WORLD.PAK parsing and in-place chunk decompression.
3//!
4//! `psx-iso::build_world_pack` (behind the `mkisopsx` CLI and the editor's
5//! embedded Play) writes the pack; this crate is the matching reader logic.
6//! Before it existed, every streaming game re-derived the parser and the
7//! LZ4 decoder from the engine's `editor-playtest` example: oot-psx
8//! `loader.rs`, zelda3-psx `loader.rs` (a copy of oot's), hl-psx
9//! `cdstream.rs`. Reader and writer now live in one repo so the format
10//! cannot drift.
11//!
12//! Scope: this root module is PURE logic (parsing + decompression), building
13//! and testing on the host. The CD-ROM command/DMA state machine that feeds
14//! sectors in lives in [`cd`] ([`cd::SectorReader`] + [`cd::load_chunk`]),
15//! `cfg(target_arch = "mips")`-gated; the reader is `psx_io::cd::reader`, on
16//! the `Cd` token. Note [`cd::SectorReader::prepare`] sets `I_MASK` to
17//! VBlank-only until `stop` puts it back; read its docs before adopting.
18//!
19//! Pack layout (all little-endian, from `psx-iso`):
20//!
21//! ```text
22//! header, 28 bytes:  "PSOXWPAK" | u32 version=1 | u32 chunk_count
23//!                    | u32 total_sectors | u32 header_sectors | u32 table_bytes
24//! table:             chunk_count x 24-byte entries:
25//!                    u32 chunk_id | u32 sector_offset | u32 sector_count
26//!                    | u32 byte_size | u32 checksum (FNV-1a) | u32 reserved
27//! payloads:          each chunk starts on a 2048-byte sector boundary
28//! ```
29//!
30//! Chunks written with `--world-pack-compress-rooms` carry an `HLZC` frame
31//! (`"HLZC" | u32 raw_len | LZ4 block`); [`decompress_hlzc_in_place`] undoes
32//! it inside the destination buffer, no scratch memory needed.
33
34#![no_std]
35#![deny(unsafe_op_in_unsafe_fn)]
36#![warn(missing_docs)]
37
38pub mod cd;
39/// Allocation-free Quake and GoldSrc visibility row codecs.
40pub mod visibility;
41
42/// Pack magic, first 8 header bytes.
43pub const MAGIC: [u8; 8] = *b"PSOXWPAK";
44/// The one pack version this parser understands.
45pub const VERSION: u32 = 1;
46/// Fixed header size in bytes.
47pub const HEADER_BYTES: usize = 28;
48/// Size of one chunk-table entry in bytes.
49pub const ENTRY_BYTES: usize = 24;
50/// User-data bytes per CD sector (MODE2 form 1).
51pub const SECTOR_BYTES: usize = 2048;
52/// Magic framing a compressed chunk payload.
53pub const HLZC_MAGIC: [u8; 4] = *b"HLZC";
54
55/// Parsed fixed header.
56#[derive(Copy, Clone, Debug, PartialEq, Eq)]
57pub struct PackHeader {
58    /// Number of entries in the chunk table.
59    pub chunk_count: u32,
60    /// Whole pack size in sectors.
61    pub total_sectors: u32,
62    /// Sectors covering header + chunk table (payloads start after them).
63    pub header_sectors: u32,
64    /// Chunk-table size in bytes (`chunk_count * ENTRY_BYTES`).
65    pub table_bytes: u32,
66}
67
68/// One chunk-table entry.
69#[derive(Copy, Clone, Debug, PartialEq, Eq)]
70pub struct PackEntry {
71    /// Caller-chosen chunk id (the pack is keyed by these, not by index).
72    pub chunk_id: u32,
73    /// Payload start, in sectors from the beginning of the pack.
74    pub sector_offset: u32,
75    /// Payload length in whole sectors.
76    pub sector_count: u32,
77    /// Exact payload length in bytes.
78    pub byte_size: u32,
79    /// FNV-1a over the payload bytes (see [`fnv1a32`]).
80    pub checksum: u32,
81}
82
83fn le32(bytes: &[u8], offset: usize) -> Option<u32> {
84    let b = bytes.get(offset..offset + 4)?;
85    Some(u32::from_le_bytes([b[0], b[1], b[2], b[3]]))
86}
87
88/// Parse and validate the fixed header from the first pack bytes
89/// (any slice covering at least [`HEADER_BYTES`], e.g. the first sector).
90/// `None` on wrong magic or version.
91pub fn parse_header(bytes: &[u8]) -> Option<PackHeader> {
92    if bytes.get(..MAGIC.len())? != MAGIC {
93        return None;
94    }
95    if le32(bytes, 8)? != VERSION {
96        return None;
97    }
98    Some(PackHeader {
99        chunk_count: le32(bytes, 12)?,
100        total_sectors: le32(bytes, 16)?,
101        header_sectors: le32(bytes, 20)?,
102        table_bytes: le32(bytes, 24)?,
103    })
104}
105
106/// Parse the table entry at `index`. `bytes` must start at the beginning of
107/// the pack (header included) and cover the entry; read
108/// `header.header_sectors * SECTOR_BYTES` up front and every entry is in
109/// range. `None` when the slice is too short.
110pub fn parse_entry(bytes: &[u8], index: usize) -> Option<PackEntry> {
111    parse_entry_at(bytes, HEADER_BYTES + index * ENTRY_BYTES)
112}
113
114/// Parse one [`ENTRY_BYTES`]-sized table entry starting at an arbitrary byte
115/// `offset`. This is the sector-local primitive behind [`parse_entry`]: a
116/// caller holding a single 2048-byte header sector (not the whole pack) can
117/// parse the entries it contains directly, and stitch the one entry that
118/// straddles into the next sector through a small [`ENTRY_BYTES`] buffer
119/// (see [`entry_location`]). `None` when the slice is too short.
120pub fn parse_entry_at(bytes: &[u8], offset: usize) -> Option<PackEntry> {
121    Some(PackEntry {
122        chunk_id: le32(bytes, offset)?,
123        sector_offset: le32(bytes, offset + 4)?,
124        sector_count: le32(bytes, offset + 8)?,
125        byte_size: le32(bytes, offset + 12)?,
126        checksum: le32(bytes, offset + 16)?,
127    })
128}
129
130/// Locate table entry `index` on disc: `(header_sector, byte_offset_within_it)`.
131///
132/// The chunk table is packed right after the 28-byte header with no sector
133/// alignment, so every 85th entry straddles a sector boundary
134/// (`offset + ENTRY_BYTES > SECTOR_BYTES`, first at index 84). Sector-by-sector
135/// readers must detect that case and stitch the entry from the tail of this
136/// sector plus the head of the next one.
137pub const fn entry_location(index: u32) -> (u32, usize) {
138    let byte = HEADER_BYTES + index as usize * ENTRY_BYTES;
139    ((byte / SECTOR_BYTES) as u32, byte % SECTOR_BYTES)
140}
141
142/// Linear-scan the table for `chunk_id`. Same slice contract as
143/// [`parse_entry`]. Packs are written sorted by id unless an explicit order
144/// file reorders them, so callers doing many lookups should build their own
145/// cache (hl-psx keeps a 512-entry table) rather than rescanning.
146pub fn find_chunk(bytes: &[u8], header: &PackHeader, chunk_id: u32) -> Option<PackEntry> {
147    for i in 0..header.chunk_count as usize {
148        let entry = parse_entry(bytes, i)?;
149        if entry.chunk_id == chunk_id {
150            return Some(entry);
151        }
152    }
153    None
154}
155
156/// FNV-1a over `bytes`; the checksum `psx-iso` stores per entry.
157pub fn fnv1a32(bytes: &[u8]) -> u32 {
158    let mut hash = 0x811C_9DC5u32;
159    for &byte in bytes {
160        hash ^= byte as u32;
161        hash = hash.wrapping_mul(0x0100_0193);
162    }
163    hash
164}
165
166/// Undo the `HLZC` compression frame in place.
167///
168/// On entry `buf[..loaded]` holds a chunk payload as read from disc. A chunk
169/// without the frame (mkisopsx keeps raw bytes when compression does not
170/// shrink them) is returned untouched as `Some(loaded)`. A framed chunk is
171/// staged at the buffer tail and LZ4-decoded back to the head; `buf` only
172/// needs to be large enough for the RAW payload plus the standard in-place
173/// margin (the cooked-side buffer sizing already guarantees this; a too-small
174/// buffer fails cleanly rather than corrupting).
175///
176/// `None` means a corrupt stream, a truncated buffer, or a decode that did
177/// not produce exactly `raw_len` bytes. Callers should treat it as a failed
178/// load, not a partial one.
179///
180/// Caveat inherited from the format: a RAW chunk whose first four bytes
181/// happen to be `HLZC` would be misread as compressed. Cooked chunk types
182/// all start with their own magics (`HLMA`, `PSXT`, ...), which is what
183/// makes the sniff safe in practice.
184pub fn decompress_hlzc_in_place(buf: &mut [u8], loaded: usize) -> Option<usize> {
185    if loaded > buf.len() {
186        return None;
187    }
188    if loaded < 8 || buf[..4] != HLZC_MAGIC {
189        return Some(loaded);
190    }
191    let raw_len = le32(buf, 4)? as usize;
192    let comp_len = loaded - 8;
193    let cap = buf.len();
194    if raw_len > cap {
195        return None;
196    }
197    // Stage the compressed stream at the buffer tail, then decode tail ->
198    // head. Writes are checked against the read cursor each step, so even a
199    // buffer without enough in-place margin fails instead of corrupting.
200    let src_start = cap - comp_len;
201    buf.copy_within(8..loaded, src_start);
202    lz4_block_decode_in_place(buf, src_start, raw_len)
203}
204
205/// Decode one raw LZ4 block that has been staged at `buf[src_start..]`,
206/// writing the output from `buf[0]`. Returns the decoded length, which must
207/// equal `raw_len`.
208fn lz4_block_decode_in_place(buf: &mut [u8], src_start: usize, raw_len: usize) -> Option<usize> {
209    let cap = buf.len();
210    let mut si = src_start;
211    let mut di = 0usize;
212    while si < cap {
213        let token = buf[si];
214        si += 1;
215        // Literal run (token high nibble, 15 = extended).
216        let mut lit = (token >> 4) as usize;
217        if lit == 15 {
218            loop {
219                let b = *buf.get(si)?;
220                si += 1;
221                lit += b as usize;
222                if b != 255 {
223                    break;
224                }
225            }
226        }
227        if lit > 0 {
228            // In-place safety: the write may not start past the read cursor.
229            if si.checked_add(lit)? > cap || di + lit > raw_len || di > si {
230                return None;
231            }
232            buf.copy_within(si..si + lit, di);
233            si += lit;
234            di += lit;
235        }
236        if si >= cap {
237            break; // the final sequence is literals-only
238        }
239        // Match: 2-byte little-endian offset into the decoded history,
240        // then a 4-based extendable length (token low nibble).
241        if si + 2 > cap {
242            return None;
243        }
244        let off = buf[si] as usize | ((buf[si + 1] as usize) << 8);
245        si += 2;
246        if off == 0 || off > di {
247            return None;
248        }
249        let mut mlen = (token & 15) as usize;
250        if mlen == 15 {
251            loop {
252                let b = *buf.get(si)?;
253                si += 1;
254                mlen += b as usize;
255                if b != 255 {
256                    break;
257                }
258            }
259        }
260        mlen += 4;
261        // Writes must stay below the unread source.
262        if di + mlen > raw_len || di + mlen > si {
263            return None;
264        }
265        // Byte-at-a-time forward copy: replicates the window when
266        // off < mlen, exactly LZ4's overlap semantics.
267        for k in 0..mlen {
268            buf[di + k] = buf[di + k - off];
269        }
270        di += mlen;
271    }
272    if di == raw_len {
273        Some(di)
274    } else {
275        None
276    }
277}
278
279#[cfg(test)]
280mod tests {
281    use super::*;
282    extern crate std;
283    use std::vec;
284    use std::vec::Vec;
285
286    fn frame_hlzc(raw: &[u8]) -> Vec<u8> {
287        let comp = lz4_flex::block::compress(raw);
288        let mut out = Vec::new();
289        out.extend_from_slice(&HLZC_MAGIC);
290        out.extend_from_slice(&(raw.len() as u32).to_le_bytes());
291        out.extend_from_slice(&comp);
292        out
293    }
294
295    #[test]
296    fn parses_a_pack_the_real_writer_built() {
297        let a = vec![0xAAu8; 100];
298        let b: Vec<u8> = (0..5000u32).map(|i| (i * 7) as u8).collect();
299        let pack = psx_iso::build_world_pack(&[(10, a.as_slice()), (42, b.as_slice())]);
300
301        let header = parse_header(&pack).expect("header");
302        assert_eq!(header.chunk_count, 2);
303        assert_eq!(header.table_bytes, 2 * ENTRY_BYTES as u32);
304
305        let e = find_chunk(&pack, &header, 42).expect("chunk 42");
306        assert_eq!(e.byte_size as usize, b.len());
307        assert_eq!(e.sector_count, 3); // 5000 bytes = 3 sectors
308        let start = e.sector_offset as usize * SECTOR_BYTES;
309        let payload = &pack[start..start + e.byte_size as usize];
310        assert_eq!(payload, b.as_slice());
311        assert_eq!(fnv1a32(payload), e.checksum);
312
313        assert!(find_chunk(&pack, &header, 7).is_none());
314    }
315
316    #[test]
317    fn rejects_bad_magic_and_version() {
318        let pack = psx_iso::build_world_pack(&[(1, &[1, 2, 3])]);
319        let mut bad = pack.clone();
320        bad[0] = b'X';
321        assert!(parse_header(&bad).is_none());
322        let mut v2 = pack;
323        v2[8] = 2;
324        assert!(parse_header(&v2).is_none());
325    }
326
327    #[test]
328    fn decodes_real_lz4_in_place() {
329        // Compressible payload with structure (runs + repeats + a text tail).
330        let mut raw = Vec::new();
331        for i in 0..6000u32 {
332            raw.push((i / 64) as u8);
333        }
334        raw.extend_from_slice(b"the quick brown fox jumps over the lazy dog");
335        let framed = frame_hlzc(&raw);
336        assert!(framed.len() < raw.len(), "test payload must compress");
337
338        // Generous margin, as the cook-side sizing provides.
339        let mut buf = vec![0u8; raw.len() + 1024];
340        buf[..framed.len()].copy_from_slice(&framed);
341        let n = decompress_hlzc_in_place(&mut buf, framed.len()).expect("decode");
342        assert_eq!(n, raw.len());
343        assert_eq!(&buf[..n], raw.as_slice());
344    }
345
346    #[test]
347    fn incompressible_payload_passes_through_raw() {
348        // mkisopsx stores raw bytes when compression does not help; the
349        // decoder must hand them back untouched.
350        let raw: Vec<u8> = (0..999u32)
351            .map(|i| (i.wrapping_mul(2654435761) >> 13) as u8)
352            .collect();
353        let mut buf = raw.clone();
354        assert_eq!(
355            decompress_hlzc_in_place(&mut buf, raw.len()),
356            Some(raw.len())
357        );
358        assert_eq!(buf, raw);
359    }
360
361    #[test]
362    fn overlapping_matches_replicate() {
363        // 1 literal + long overlapping match (off=1): classic RLE-via-LZ4.
364        let raw = vec![7u8; 300];
365        let framed = frame_hlzc(&raw);
366        let mut buf = vec![0u8; 512];
367        buf[..framed.len()].copy_from_slice(&framed);
368        let n = decompress_hlzc_in_place(&mut buf, framed.len()).expect("decode");
369        assert_eq!(&buf[..n], raw.as_slice());
370    }
371
372    #[test]
373    fn corrupt_streams_fail_cleanly() {
374        let raw: Vec<u8> = (0..2000u32).map(|i| (i / 32) as u8).collect();
375        let framed = frame_hlzc(&raw);
376
377        // Truncated compressed stream.
378        let mut buf = vec![0u8; raw.len() + 1024];
379        buf[..framed.len() - 5].copy_from_slice(&framed[..framed.len() - 5]);
380        assert_eq!(decompress_hlzc_in_place(&mut buf, framed.len() - 5), None);
381
382        // raw_len larger than the buffer.
383        let mut huge = framed.clone();
384        huge[4..8].copy_from_slice(&u32::MAX.to_le_bytes());
385        let mut buf2 = vec![0u8; raw.len() + 1024];
386        buf2[..huge.len()].copy_from_slice(&huge);
387        assert_eq!(decompress_hlzc_in_place(&mut buf2, huge.len()), None);
388
389        // Buffer without in-place margin: must fail, not corrupt.
390        let mut tight = vec![0u8; framed.len()];
391        tight.copy_from_slice(&framed);
392        assert_eq!(decompress_hlzc_in_place(&mut tight, framed.len()), None);
393    }
394
395    #[test]
396    fn entry_location_matches_flat_table_offsets() {
397        for index in 0..300u32 {
398            let flat = HEADER_BYTES + index as usize * ENTRY_BYTES;
399            let (sector, within) = entry_location(index);
400            assert_eq!(sector as usize * SECTOR_BYTES + within, flat);
401            assert!(within < SECTOR_BYTES);
402        }
403        // The first straddling entry: 28 + 84*24 = 2044, crossing into sector 1.
404        assert_eq!(entry_location(84), (0, 2044));
405        assert_eq!(entry_location(85), (1, 20));
406    }
407
408    /// Scan a real psx-iso pack the way the CD reader does: one buffered
409    /// sector at a time, stitching entries that straddle sector boundaries
410    /// through a 24-byte staging buffer. Every entry must parse identically
411    /// to the flat whole-pack parse.
412    #[test]
413    fn sector_local_scan_with_straddles_matches_flat_parse() {
414        // 90 chunks make the table span three sectors' worth of entries is
415        // not needed; two sectors with one straddle (index 84) is the case
416        // that matters. Non-contiguous ids prove index != id.
417        let payloads: Vec<(u32, Vec<u8>)> = (0..90u32)
418            .map(|i| (i * 3 + 1, vec![i as u8; 5 + (i as usize % 40)]))
419            .collect();
420        let refs: Vec<(u32, &[u8])> = payloads
421            .iter()
422            .map(|(id, bytes)| (*id, bytes.as_slice()))
423            .collect();
424        let pack = psx_iso::build_world_pack(&refs);
425
426        let header = parse_header(&pack).expect("header");
427        assert_eq!(header.chunk_count, 90);
428        assert!(
429            header.header_sectors >= 2,
430            "fixture must produce a multi-sector table"
431        );
432
433        let sector = |s: u32| -> &[u8] {
434            let at = s as usize * SECTOR_BYTES;
435            &pack[at..at + SECTOR_BYTES]
436        };
437
438        let mut straddles = 0;
439        for index in 0..header.chunk_count {
440            let (sec, within) = entry_location(index);
441            assert!(sec < header.header_sectors);
442            let entry = if within + ENTRY_BYTES <= SECTOR_BYTES {
443                parse_entry_at(sector(sec), within).expect("in-sector entry")
444            } else {
445                straddles += 1;
446                let first = SECTOR_BYTES - within;
447                let mut stitched = [0u8; ENTRY_BYTES];
448                stitched[..first].copy_from_slice(&sector(sec)[within..]);
449                stitched[first..].copy_from_slice(&sector(sec + 1)[..ENTRY_BYTES - first]);
450                parse_entry_at(&stitched, 0).expect("stitched entry")
451            };
452            let flat = parse_entry(&pack, index as usize).expect("flat entry");
453            assert_eq!(entry, flat, "entry {index} diverged");
454        }
455        assert_eq!(straddles, 1, "index 84 must straddle sectors 0 and 1");
456    }
457
458    #[test]
459    fn fnv_matches_the_writer() {
460        // Golden value: the writer's fnv1a32 over "PSOXWPAK".
461        let pack = psx_iso::build_world_pack(&[(1, &MAGIC[..])]);
462        let header = parse_header(&pack).unwrap();
463        let e = find_chunk(&pack, &header, 1).unwrap();
464        assert_eq!(e.checksum, fnv1a32(&MAGIC));
465    }
466}
psx_pack/lib.rs

psx_pack/
lib.rs
