psx_mc/
compress.rs

1// SPDX-License-Identifier: GPL-2.0-or-later
2//! A small, self-contained LZSS codec for save payloads (feature `compress`).
3//!
4//! Chosen over LZ4/zlib because it is tiny, `no_std`, allocation-free, and
5//! decodes with only the output buffer as its history window -- so a card read
6//! can stream compressed frames straight into the caller's buffer with no
7//! scratch. Typical structured save data (sparse tables, repeated records)
8//! compresses well; already-dense data falls back to being stored verbatim by
9//! [`crate::Card::write_compressed`].
10//!
11//! ## Bitstream
12//!
13//! Groups of up to 8 tokens, each group prefixed by a flag byte (bit `i`,
14//! LSB-first, describes token `i`): `1` = literal (one byte follows), `0` =
15//! match (two bytes follow). A match encodes a 12-bit distance (1..=4096) and a
16//! 4-bit length (3..=18) as `((dist-1) << 4) | (len-3)`, big-endian.
17
18const WINDOW: usize = 4096;
19const MIN_MATCH: usize = 3;
20const MAX_MATCH: usize = MIN_MATCH + 15; // 18
21
22/// Compress `src` into `dst`. Returns the compressed length, or `None` if `dst`
23/// is too small to hold the result.
24///
25/// The match search is a bounded linear scan of the window -- simple and
26/// allocation-free. Save writes are deliberate, infrequent actions, so the
27/// O(n·window) cost is acceptable; swap in a hash-chain finder if a project
28/// compresses large buffers on a hot path.
29pub fn compress(src: &[u8], dst: &mut [u8]) -> Option<usize> {
30    let mut out = Emitter { dst, pos: 0 };
31    let mut i = 0;
32    while i < src.len() {
33        // Open a group: reserve the flag byte, then fill up to 8 tokens.
34        let flag_pos = out.reserve()?;
35        let mut flag = 0u8;
36        let mut bit = 0;
37        while bit < 8 && i < src.len() {
38            let (dist, len) = longest_match(src, i);
39            if len >= MIN_MATCH {
40                let token = (((dist - 1) as u16) << 4) | (len - MIN_MATCH) as u16;
41                out.push((token >> 8) as u8)?;
42                out.push(token as u8)?;
43                i += len;
44            } else {
45                flag |= 1 << bit;
46                out.push(src[i])?;
47                i += 1;
48            }
49            bit += 1;
50        }
51        out.set(flag_pos, flag);
52    }
53    Some(out.pos)
54}
55
56/// Decompress a full compressed slice into `dst`. Returns the number of bytes
57/// produced (should equal the original length). Convenience wrapper over
58/// [`decompress_from`].
59pub fn decompress(src: &[u8], dst: &mut [u8]) -> Option<usize> {
60    let mut i = 0;
61    decompress_from(
62        || {
63            let b = src.get(i).copied();
64            if b.is_some() {
65                i += 1;
66            }
67            b
68        },
69        dst,
70    )
71}
72
73/// Streaming decompression: pull compressed bytes from `next` and write the
74/// decoded output into `dst`, stopping once `dst` is full. Returns the number
75/// of bytes produced, or `None` on a malformed stream (a back-reference before
76/// the start of output, or input exhausted early).
77///
78/// Only `dst` is used as history, so no separate window buffer is needed.
79pub fn decompress_from<F: FnMut() -> Option<u8>>(mut next: F, dst: &mut [u8]) -> Option<usize> {
80    let mut pos = 0;
81    while pos < dst.len() {
82        let flag = next()?;
83        let mut bit = 0;
84        while bit < 8 && pos < dst.len() {
85            if flag & (1 << bit) != 0 {
86                dst[pos] = next()?;
87                pos += 1;
88            } else {
89                let b0 = next()? as u16;
90                let b1 = next()? as u16;
91                let token = (b0 << 8) | b1;
92                let dist = ((token >> 4) + 1) as usize;
93                let len = (token & 0xF) as usize + MIN_MATCH;
94                if dist > pos {
95                    return None; // reference before start of output
96                }
97                for _ in 0..len {
98                    if pos >= dst.len() {
99                        break;
100                    }
101                    dst[pos] = dst[pos - dist];
102                    pos += 1;
103                }
104            }
105            bit += 1;
106        }
107    }
108    Some(pos)
109}
110
111/// Longest window match for the data at `src[at..]`. Returns `(distance, len)`;
112/// `len < MIN_MATCH` means "no useful match".
113fn longest_match(src: &[u8], at: usize) -> (usize, usize) {
114    let start = at.saturating_sub(WINDOW);
115    let max_len = MAX_MATCH.min(src.len() - at);
116    let mut best_len = 0;
117    let mut best_dist = 0;
118    let mut j = start;
119    while j < at {
120        let mut l = 0;
121        while l < max_len && src[j + l] == src[at + l] {
122            l += 1;
123        }
124        if l > best_len {
125            best_len = l;
126            best_dist = at - j;
127            if l == max_len {
128                break;
129            }
130        }
131        j += 1;
132    }
133    (best_dist, best_len)
134}
135
136/// Bounds-checked forward writer into a caller buffer.
137struct Emitter<'a> {
138    dst: &'a mut [u8],
139    pos: usize,
140}
141
142impl Emitter<'_> {
143    fn push(&mut self, b: u8) -> Option<()> {
144        *self.dst.get_mut(self.pos)? = b;
145        self.pos += 1;
146        Some(())
147    }
148    /// Reserve one byte (a flag slot) and return its index.
149    fn reserve(&mut self) -> Option<usize> {
150        let p = self.pos;
151        self.push(0)?;
152        Some(p)
153    }
154    fn set(&mut self, at: usize, b: u8) {
155        self.dst[at] = b;
156    }
157}
158
159#[cfg(test)]
160mod tests {
161    use super::*;
162
163    fn roundtrip(data: &[u8]) {
164        let mut comp = [0u8; 4096];
165        let clen = compress(data, &mut comp).expect("fits");
166        let mut out = [0u8; 2048];
167        let n = decompress(&comp[..clen], &mut out[..data.len()]).expect("decode");
168        assert_eq!(n, data.len());
169        assert_eq!(&out[..data.len()], data);
170    }
171
172    #[test]
173    fn empty() {
174        roundtrip(b"");
175    }
176
177    #[test]
178    fn incompressible_and_runs() {
179        roundtrip(b"A");
180        roundtrip(b"AAAAAAAAAAAAAAAAAAAAAAAA");
181        roundtrip(b"the quick brown fox the quick brown fox the quick brown fox");
182        let mut seq = [0u8; 500];
183        for (i, b) in seq.iter_mut().enumerate() {
184            *b = (i * 7 + (i / 13)) as u8;
185        }
186        roundtrip(&seq);
187    }
188
189    #[test]
190    fn sparse_like_a_save() {
191        // Mostly zeros with a few records -- the memory-card common case.
192        let mut data = [0u8; 1024];
193        data[0] = b'S';
194        data[1] = b'C';
195        for k in 0..8 {
196            data[64 * k + 3] = k as u8;
197            data[64 * k + 4] = 0xFF;
198        }
199        roundtrip(&data);
200        let mut comp = [0u8; 2048];
201        let clen = compress(&data, &mut comp).unwrap();
202        assert!(clen < data.len() / 2, "sparse data should shrink a lot");
203    }
204
205    #[test]
206    fn dst_too_small_is_none() {
207        let mut tiny = [0u8; 2];
208        assert!(compress(b"hello world this will not fit", &mut tiny).is_none());
209    }
210}
psx_mc/compress.rs

psx_mc/
compress.rs
