banished_formats/
lzf.rs

1//! LZF decompression (`System::Compression::Decompress`).
2//!
3//! Original: Runtime `0x1800c6ed0`.
4
5use crate::error::{format_err, Result};
6
7/// Decompress one LZF block, appending to `out`. Back-references may only reach
8/// bytes produced by this call, matching the engine's per-block windows.
9pub fn decompress_into(src: &[u8], out: &mut Vec<u8>, max_len: usize) -> Result<()> {
10    let base = out.len();
11    let mut i = 0;
12    while i < src.len() {
13        let ctrl = src[i] as usize;
14        i += 1;
15        if ctrl < 0x20 {
16            let n = ctrl + 1;
17            let Some(lit) = src.get(i..i + n) else {
18                return format_err("LZF literal run past end of input");
19            };
20            out.extend_from_slice(lit);
21            i += n;
22        } else {
23            let mut n = ctrl >> 5;
24            if n == 7 {
25                let Some(&extra) = src.get(i) else {
26                    return format_err("LZF truncated length");
27                };
28                n += extra as usize;
29                i += 1;
30            }
31            let Some(&lo) = src.get(i) else {
32                return format_err("LZF truncated offset");
33            };
34            i += 1;
35            let back = ((ctrl & 0x1F) << 8) + lo as usize + 1;
36            if back > out.len() - base {
37                return format_err("LZF back-reference before block start");
38            }
39            let from = out.len() - back;
40            for k in 0..n + 2 {
41                let b = out[from + k];
42                out.push(b);
43            }
44        }
45        if out.len() - base > max_len {
46            return format_err("LZF block exceeds its window");
47        }
48    }
49    Ok(())
50}
51
52/// Compress one block in the LZF format [`decompress_into`] reads: literal runs of up to 32
53/// bytes, and back-references of 3 to 264 bytes up to 8 KiB back, found by a 3-byte hash.
54/// Any valid encoding loads; this need not match the engine's choice of matches.
55pub fn compress(src: &[u8]) -> Vec<u8> {
56    const MAX_BACK: usize = 1 << 13;
57    const MAX_LEN: usize = 7 + 255 + 2;
58    let mut out = Vec::with_capacity(src.len() + src.len() / 32 + 1);
59    let mut table = vec![usize::MAX; 1 << 14];
60    let hash = |i: usize| {
61        let v = (src[i] as u32) << 16 | (src[i + 1] as u32) << 8 | src[i + 2] as u32;
62        (v.wrapping_mul(2654435761) >> 18) as usize & ((1 << 14) - 1)
63    };
64    // Where the open literal run's control byte is.
65    let mut run: Option<usize> = None;
66    let mut i = 0;
67    while i < src.len() {
68        let mut matched = 0;
69        let mut back = 0;
70        if i + 2 < src.len() {
71            let h = hash(i);
72            let cand = table[h];
73            table[h] = i;
74            if cand != usize::MAX && i - cand <= MAX_BACK && src[cand..cand + 3] == src[i..i + 3] {
75                let limit = (src.len() - i).min(MAX_LEN);
76                matched = 3;
77                while matched < limit && src[cand + matched] == src[i + matched] {
78                    matched += 1;
79                }
80                back = i - cand - 1;
81            }
82        }
83        if matched >= 3 {
84            run = None;
85            let n = matched - 2;
86            if n < 7 {
87                out.push((n << 5 | back >> 8) as u8);
88            } else {
89                out.push((7 << 5 | back >> 8) as u8);
90                out.push((n - 7) as u8);
91            }
92            out.push(back as u8);
93            // Index the positions the match covers so later matches can find them.
94            for k in i + 1..(i + matched).min(src.len().saturating_sub(2)) {
95                table[hash(k)] = k;
96            }
97            i += matched;
98        } else {
99            match run {
100                Some(at) if out[at] < 0x1f => out[at] += 1,
101                _ => {
102                    run = Some(out.len());
103                    out.push(0);
104                }
105            }
106            out.push(src[i]);
107            i += 1;
108        }
109    }
110    out
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    #[test]
118    fn compress_round_trips() {
119        let mut data = Vec::new();
120        for k in 0..20_000u32 {
121            data.extend_from_slice(&(k % 300).to_le_bytes());
122            data.push((k * 7 % 13) as u8);
123        }
124        data.extend(std::iter::repeat_n(9u8, 1000));
125        for block in data.chunks(0x8000) {
126            let packed = compress(block);
127            assert!(packed.len() < block.len());
128            let mut out = Vec::new();
129            decompress_into(&packed, &mut out, 0x8000).unwrap();
130            assert_eq!(out, block);
131        }
132        let mut out = Vec::new();
133        decompress_into(&compress(b"ab"), &mut out, 64).unwrap();
134        assert_eq!(out, b"ab");
135    }
136
137    #[test]
138    fn literal_and_backref() {
139        // "abc" literal, then copy 4 bytes from 3 back -> "abcabca"
140        let src = [0x02, b'a', b'b', b'c', 0x40, 0x02];
141        let mut out = Vec::new();
142        decompress_into(&src, &mut out, 64).unwrap();
143        assert_eq!(out, b"abcabca");
144    }
145
146    #[test]
147    fn rejects_bad_backref() {
148        let mut out = Vec::new();
149        assert!(decompress_into(&[0x20, 0x05], &mut out, 64).is_err());
150    }
151}
banished_formats/lzf.rs

banished_formats/
lzf.rs
