Skip to main content

unityrs_core/codec/
lzma.rs

1// Ported from UnityPy 1.25.2 (MIT): UnityPy/helpers/CompressionHelper.py. See THIRD_PARTY_LICENSES.
2//! Compression type 1: [`Lzma`], liblzma's raw LZMA1 decoder.
3
4use bytes::Bytes;
5
6use super::{BlockCodec, Codec, Decoded};
7use crate::budget::{DecodeBuf, Reservation};
8use crate::error::{Error, LimitKind};
9use crate::limits::{ChargeError, heap_cost};
10
11/// Compression type 1: liblzma's raw LZMA1 decoder, to the end of the input.
12#[derive(Clone, Copy, Debug, Default)]
13pub struct Lzma;
14
15const _: () = crate::send_sync::<Lzma>();
16
17/// The dictionary the first LZMA attempt allocates at most, when the
18/// declared size is larger (see [`Lzma`]'s `decode`).
19const LZMA_FIRST_DICT_MAX: u64 = 8 << 20;
20
21/// liblzma's smallest dictionary (`LZMA_DICT_SIZE_MIN`): a smaller size is
22/// allocated at this, and the first attempt asks for no less.
23const LZMA_DICT_SIZE_MIN: u32 = 4096;
24
25/// The room liblzma's LZ decoder keeps on each side of its dictionary
26/// (`2 * LZ_DICT_REPEAT_MAX`, `lz/lz_decoder.h:75` of the xz 5.8.4 that
27/// `liblzma-sys` 0.4.9 builds).
28const LZ_DICT_REPEAT_ROOM: u64 = 2 * 288;
29
30impl Lzma {
31    /// What one liblzma raw LZMA1 decoder holds beside its dictionary, in
32    /// glibc chunks ([`heap_cost`]): liblzma's own state, 32,784 bytes (the
33    /// stream's `lzma_internal`, `common/common.c:183`; the LZ decoder's
34    /// coder, `lz/lz_decoder.c:229`; the LZMA1 decoder and its probability
35    /// tables, `lzma/lzma_decoder.c:1122`, of the xz 5.8.4 that
36    /// `liblzma-sys` 0.4.9 builds), and the 256 bytes the `liblzma` crate's
37    /// filter chain takes on the Rust heap while it is built (a one-entry
38    /// array grown to four, 16 bytes then 64, both held while it grows, and
39    /// a 128-byte options node: `src/stream.rs:709-735` and `:1128-1131` of
40    /// `liblzma` 0.4.9). Each attempt charges it beside the dictionary
41    /// ([`Self::decoder_charge`]; review round 12: only the dictionary was
42    /// charged, so about 32 KiB a decode reached no meter).
43    ///
44    /// `tests/lzma_decoder_heap.rs` measures both on glibc, in a child
45    /// process, and fails unless liblzma's allocations and the filter chain
46    /// are exactly [`Self::decoder_charge`], and one decode's charge covers
47    /// the heap it holds with at most 32 bytes to spare (the filter array's
48    /// first chunk, freed once it grows); `cargo test -p unityrs-core --test
49    /// lzma_decoder_heap -- --nocapture` prints what it measured.
50    pub const DECODER_STATE: u64 = 32_784 + 256;
51
52    /// What one decode attempt with a dictionary of `dict` bytes charges
53    /// before liblzma allocates anything: the dictionary buffer liblzma
54    /// allocates (`lz/lz_decoder.c:253-289`: at least 4 KiB, rounded up to
55    /// a multiple of 16, and `2 * LZ_DICT_REPEAT_MAX`, 576 bytes, more; its
56    /// `LZ_DICT_EXTRA` is 0 in `liblzma-sys`'s build, whose `config.h`
57    /// defines no `HAVE_IMMINTRIN_H`, `lz/lz_decoder.h:22-46`), in a glibc
58    /// chunk, and [`Self::DECODER_STATE`].
59    /// A `const fn`, so a bound sized from it is checked when it compiles
60    /// (`unityrs-tpk`'s `TpkProvider::MAX_DECODER_MEMORY`).
61    #[must_use]
62    pub const fn decoder_charge(dict: u32) -> u64 {
63        let dict = if dict < LZMA_DICT_SIZE_MIN {
64            LZMA_DICT_SIZE_MIN
65        } else {
66            dict
67        };
68        let buffer = (dict as u64).next_multiple_of(16) + LZ_DICT_REPEAT_ROOM;
69        heap_cost(buffer) + Self::DECODER_STATE
70    }
71}
72
73impl BlockCodec for Lzma {
74    /// `decompress_lzma` (`CompressionHelper.py:17-44`): the properties byte
75    /// and the little-endian dictionary size, then a raw LZMA1
76    /// `LZMADecompressor`'s `decompress(data[5:])`, whose loop is
77    /// Python's `decompress_buf` (`Modules/_lzmamodule.c`): run until the
78    /// stream ends, the input is used up with room left in the output, or an
79    /// error; the declared size plays no part.
80    ///
81    /// **The dictionary.** liblzma allocates the dictionary the properties
82    /// name (up to 4 GiB) on the C heap. The decoder only uses it to
83    /// refuse a match distance at or beyond `min(output so far, dictionary)`,
84    /// so a dictionary at least as large as the output decodes exactly what
85    /// the named one does. The first attempt uses the declared size, between
86    /// liblzma's 4 KiB minimum and 8 MiB, capped by the named size (a
87    /// well-formed block fills exactly its declared size, so it decodes
88    /// once); an attempt that fails on data
89    /// after it outgrew its dictionary is decoded again with a larger one
90    /// (at least twice the output so far, capped by the named size), so the
91    /// dictionary stays within a constant plus twice the block's charged
92    /// output. The two caps keep a match farther back than the named
93    /// dictionary UnityPy's `LZMAError`, whatever the declared size
94    /// (`tests/codecs.rs`
95    /// `lzma_a_match_past_the_named_dictionary_raises_whatever_the_declared_size`).
96    /// Each attempt's dictionary buffer and the decoder's state
97    /// ([`Lzma::DECODER_STATE`]) are charged to the input's meter
98    /// ([`DecodeBuf::meter`]) before liblzma allocates them, and returned
99    /// when the attempt ends, so the meter sees them beside the output (plan
100    /// section 3.15); a refusal is the meter's, like a refused growth. The
101    /// output's room is `out`'s: it grows geometrically, never past the
102    /// block's cap, nor past its declared size while the block is short of it
103    /// (its windows stop there, [`DecodeBuf::begin_block`]), and a retry
104    /// keeps the room the failed attempt grew, so an attempt holds its room
105    /// (and, while the room grows, the block it replaces) beside its
106    /// dictionary. A caller that must bound that sum by
107    /// the output's cap alone allocates the room whole first, as unityrs-tpk
108    /// does (`TpkProvider::MAX_DECODER_MEMORY`; review round 13).
109    fn decode(
110        &self,
111        input: &Bytes,
112        uncompressed: u32,
113        out: &mut DecodeBuf,
114    ) -> Result<Decoded, Error> {
115        // UnityPy helpers/CompressionHelper.py:26: `struct.unpack("<BI", data[:5])`.
116        let (Some(&props), Some(dict)) = (input.first(), input.get(1..5)) else {
117            return Err(lzma_error(&format!(
118                "struct.error: unpack requires a buffer of 5 bytes (got {})",
119                input.len()
120            )));
121        };
122        let named = u32::from_le_bytes(<[u8; 4]>::try_from(dict).unwrap_or_default());
123        let data = input.get(5..).unwrap_or_default();
124        // UnityPy helpers/CompressionHelper.py:27-30
125        let lc = u32::from(props % 9);
126        let rest = u32::from(props / 9);
127        let (pb, lp) = (rest / 5, rest % 5);
128        let first =
129            u64::from(uncompressed).clamp(u64::from(LZMA_DICT_SIZE_MIN), LZMA_FIRST_DICT_MAX);
130        let mut dict = u32::try_from(first).unwrap_or(u32::MAX).min(named);
131        let start = out.len();
132        loop {
133            match lzma_attempt([lc, lp, pb], dict, data, uncompressed, out) {
134                Err(LzmaFail::Data(produced))
135                    if dict < named
136                        && u64::try_from(produced).unwrap_or(u64::MAX) >= u64::from(dict) =>
137                {
138                    out.truncate(start);
139                    let wider = u64::try_from(produced)
140                        .unwrap_or(u64::MAX)
141                        .saturating_mul(2)
142                        .max(u64::from(dict).saturating_mul(2));
143                    dict = u32::try_from(wider).unwrap_or(u32::MAX).min(named);
144                }
145                Err(LzmaFail::Data(_)) => return Err(lzma_error("LZMAError: Corrupt input data")),
146                Err(LzmaFail::Other(e)) => return Err(e),
147                Ok(()) => return Ok(Decoded::Written),
148            }
149        }
150    }
151}
152
153fn lzma_error(detail: &str) -> Error {
154    Error::Decompress {
155        codec: Codec::Lzma,
156        detail: detail.into(),
157    }
158}
159
160enum LzmaFail {
161    /// `LZMA_DATA_ERROR` after this many bytes of output.
162    Data(usize),
163    /// Anything else.
164    Other(Error),
165}
166
167impl From<ChargeError> for LzmaFail {
168    fn from(e: ChargeError) -> Self {
169        Self::Other(e.into())
170    }
171}
172
173/// A liblzma failure after `produced` bytes of the block's output, in an
174/// attempt that holds `held` bytes of dictionary and decoder state on a
175/// meter booked as `what`. `LZMA_MEM_ERROR` is the allocator refusing what
176/// liblzma allocates itself, the dictionary above all, which the meter had granted:
177/// a refusal of memory, as a growth the Rust allocator refuses is
178/// ([`crate::limits::MeteredVec`]), so it is the meter's reservation's
179/// [`Error::Budget`] (transient: nothing keeps it, and the same block decodes
180/// once the memory is there), never a decode failure (review round 6: it
181/// was `Decompress`, `"MemoryError"`, so a TPK loaded while the process was
182/// short of memory read as a corrupt one). `tests/codecs.rs`
183/// `liblzmas_refused_dictionary_is_the_meters_reservation_refused` makes the
184/// C allocator refuse it, in a child process under an address-space cap
185/// (`unityrs_testkit::address_space`), on a meter of each reservation
186/// (review round 7: only this function's own test covered it).
187fn failure(e: liblzma::stream::Error, produced: usize, held: u64, what: Reservation) -> LzmaFail {
188    let other = |detail: &str| LzmaFail::Other(lzma_error(detail));
189    match e {
190        liblzma::stream::Error::Data => LzmaFail::Data(produced),
191        liblzma::stream::Error::Options => other("LZMAError: Invalid or unsupported options"),
192        liblzma::stream::Error::Mem => {
193            crate::counters::allocator(what);
194            LzmaFail::Other(Error::Budget(crate::limits::refusal(held, what)))
195        }
196        _ => other("LZMAError: Internal error"),
197    }
198}
199
200/// The window an LZMA decode grows its output by at most at once.
201const LZMA_WINDOW_MAX: usize = 1 << 20;
202
203/// One decode of an LZMA1 stream with dictionary `dict`, appended to `out`.
204fn lzma_attempt(
205    [lc, lp, pb]: [u32; 3],
206    dict: u32,
207    data: &[u8],
208    declared: u32,
209    out: &mut DecodeBuf,
210) -> Result<(), LzmaFail> {
211    use liblzma::stream::{Action, Filters, LzmaOptions, Status, Stream};
212
213    let other = |what: &str| LzmaFail::Other(lzma_error(what));
214    // liblzma allocates the whole dictionary (at least its 4 KiB minimum)
215    // and its state when the decoder starts, and the filter chain allocates
216    // on the Rust heap: all charged first, held for the attempt.
217    let held = Lzma::decoder_charge(dict);
218    let _decoder = out.meter().charge(held)?;
219    let what = out.meter().reservation();
220    let map = |e: liblzma::stream::Error, produced: usize| failure(e, produced, held, what);
221    // CPython's `parse_filter_spec_lzma` starts from the default preset and
222    // sets what the filter spec names.
223    let mut opts = LzmaOptions::new_preset(6).map_err(|e| map(e, 0))?;
224    opts.dict_size(dict)
225        .literal_context_bits(lc)
226        .literal_position_bits(lp)
227        .position_bits(pb);
228    let mut filters = Filters::new();
229    filters.lzma1(&opts);
230    let mut stream = Stream::new_raw_decoder(&filters).map_err(|e| map(e, 0))?;
231    let seg_start = out.len();
232    // The first window is the declared size, which a well-formed block
233    // fills exactly; a probe then finds the end without growing again.
234    let declared_len = usize::try_from(declared).unwrap_or(usize::MAX);
235    let mut want = match declared_len {
236        0 => LZMA_WINDOW_MAX,
237        n => n.min(LZMA_WINDOW_MAX),
238    };
239    let input_done =
240        |stream: &Stream| usize::try_from(stream.total_in()).unwrap_or(usize::MAX) >= data.len();
241    let rest = |stream: &Stream| {
242        let consumed = usize::try_from(stream.total_in()).unwrap_or(usize::MAX);
243        data.get(consumed..).unwrap_or_default()
244    };
245    // Whether the last call left the output full (Python then grows its
246    // buffer and calls again; here a one-byte probe asks first, so a
247    // well-formed block is never given room it does not fill).
248    let mut full = false;
249    loop {
250        let produced = out.len() - seg_start;
251        if full {
252            let mut probe = [0u8; 1];
253            let before = stream.total_out();
254            let status = stream
255                .process(rest(&stream), &mut probe, Action::Run)
256                .map_err(|e| map(e, produced))?;
257            if stream.total_out() > before {
258                out.extend_from_slice(&probe)?;
259            }
260            match status {
261                Status::StreamEnd => return Ok(()),
262                Status::MemNeeded if !input_done(&stream) => {
263                    return Err(other("LZMAError: Insufficient buffer space"));
264                }
265                _ => {}
266            }
267            // Nothing more and no input left ends it. No progress with input
268            // left: liblzma answers `LZMA_OK` once before `LZMA_BUF_ERROR`,
269            // so ask again with a window.
270            if stream.total_out() == before && input_done(&stream) {
271                return Ok(());
272            }
273            full = false;
274            continue;
275        }
276        // A window never passes the declared size while the block is short
277        // of it, so the room (which `DecodeBuf` grows to the declared end and
278        // no further) ends where a well-formed block does (perf stage 2: the
279        // last 1 MiB window passed it and doubled the room). Past it, windows
280        // are as before. A window the meter or the block's cap refuses is
281        // retried smaller, down to one byte; a refused byte goes to the
282        // probe, which fails only if the stream has another byte to give.
283        let left = declared_len.saturating_sub(produced);
284        let ask = if left > 0 { want.min(left) } else { want };
285        let base = out.len();
286        let window = match out.grow_zeroed(ask) {
287            Ok(w) => w,
288            Err(e) if ask > 1 => {
289                want = refused_window(&e, ask, produced);
290                continue;
291            }
292            Err(_) => {
293                full = true;
294                continue;
295            }
296        };
297        let room = window.len();
298        let before = stream.total_out();
299        let status = stream.process(rest(&stream), window, Action::Run);
300        let made = usize::try_from(stream.total_out() - before).unwrap_or(room);
301        out.truncate(base + made);
302        let status = status.map_err(|e| map(e, produced + made))?;
303        match status {
304            Status::StreamEnd => return Ok(()),
305            // `LZMA_BUF_ERROR` with no input left and room in the output is
306            // not an error in Python; with input left, it is.
307            Status::MemNeeded if !input_done(&stream) && made < room => {
308                return Err(other("LZMAError: Insufficient buffer space"));
309            }
310            _ => {}
311        }
312        if made == room {
313            // `avail_out == 0`.
314            full = true;
315            want = want.saturating_mul(2).min(LZMA_WINDOW_MAX);
316        } else if input_done(&stream) {
317            // `avail_in == 0`: a truncated stream yields what decoded.
318            return Ok(());
319        }
320    }
321}
322
323/// The next window after `want` bytes were refused with `e`, after
324/// `produced` bytes of this block: the room left under the block's cap when
325/// that is what refused, else half.
326fn refused_window(e: &ChargeError, want: usize, produced: usize) -> usize {
327    let half = (want / 2).max(1);
328    match e {
329        ChargeError::Limit(l) if l.kind() == LimitKind::BlockOutput => {
330            let room = usize::try_from(l.max())
331                .unwrap_or(usize::MAX)
332                .saturating_sub(produced);
333            room.clamp(1, half)
334        }
335        _ => half,
336    }
337}
338
339#[cfg(test)]
340mod tests {
341    use super::{LzmaFail, failure};
342    use crate::budget::{BudgetExceeded, Reservation};
343    use crate::error::Error;
344    use crate::once::CellError;
345
346    /// Round 6: liblzma's `LZMA_MEM_ERROR` (the allocator refusing the
347    /// dictionary liblzma allocates itself) was `Decompress`, `"MemoryError"`,
348    /// a decode failure. It is the meter's reservation refused the memory it
349    /// had granted, as a growth the Rust allocator refuses is: a caller tells
350    /// it from a corrupt block, and nothing keeps it.
351    #[test]
352    fn liblzmas_memory_error_is_a_refusal_of_memory_not_a_decode_failure() {
353        for what in [Reservation::Input, Reservation::Provider] {
354            match failure(liblzma::stream::Error::Mem, 3, 8 << 20, what) {
355                LzmaFail::Other(e @ Error::Budget(_)) => {
356                    assert!(e.is_transient());
357                    let Error::Budget(b) = e else { unreachable!() };
358                    assert_eq!(
359                        b,
360                        BudgetExceeded {
361                            requested: 8 << 20,
362                            what
363                        }
364                    );
365                }
366                LzmaFail::Other(e) => panic!("{what:?}: {e:?}"),
367                LzmaFail::Data(n) => panic!("{what:?}: a data error after {n} bytes"),
368            }
369        }
370        // A data error is still the stream's, after the bytes it made.
371        assert!(matches!(
372            failure(liblzma::stream::Error::Data, 3, 4096, Reservation::Input),
373            LzmaFail::Data(3)
374        ));
375    }
376
377    /// On a dependency's meter, liblzma's memory error is a refusal of the
378    /// dependency pool, counted as every other one is
379    /// (`crate::limits::pool_refusals`), which the Environment's retry tells
380    /// a refusal it already retried from a later one by (review round 8).
381    #[test]
382    fn liblzmas_memory_error_on_a_dependency_counts_as_a_pool_refusal() {
383        let before = crate::limits::pool_refusals();
384        let fail = failure(
385            liblzma::stream::Error::Mem,
386            3,
387            8 << 20,
388            Reservation::Dependency,
389        );
390        assert!(
391            matches!(&fail, LzmaFail::Other(Error::Budget(b)) if b.what == Reservation::Dependency)
392        );
393        assert_eq!(crate::limits::pool_refusals() - before, 1);
394    }
395}