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}