Skip to main content

unityrs_core/codec/
lz4.rs

1// Ported from UnityPy 1.25.2 (MIT): UnityPy/helpers/CompressionHelper.py. See THIRD_PARTY_LICENSES.
2// Ported from liblz4 1.9.4 (BSD-2-Clause): lib/lz4.c, LZ4_decompress_generic. See THIRD_PARTY_LICENSES.
3//
4// The decoder below translates liblz4's. liblz4 1.9.4's notice, from lib/lz4.c:
5//
6// LZ4 - Fast LZ compression algorithm
7// Copyright (C) 2011-2020, Yann Collet.
8//
9// BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15//     * Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//     * Redistributions in binary form must reproduce the above
18// copyright notice, this list of conditions and the following disclaimer
19// in the documentation and/or other materials provided with the
20// distribution.
21//
22// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
28// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
29// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
30// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
31// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
32// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33
34//! Compression types 2 and 3: [`Lz4`], with liblz4 1.9.4's acceptance.
35
36use bytes::Bytes;
37
38use super::{BlockCodec, Codec, Decoded};
39use crate::budget::DecodeBuf;
40use crate::error::Error;
41
42/// Compression types 2 and 3: an LZ4 block, `uncompressed` as the maximum.
43#[derive(Clone, Copy, Debug, Default)]
44pub struct Lz4;
45
46const _: () = crate::send_sync::<Lz4>();
47
48impl BlockCodec for Lz4 {
49    /// `lz4.block.decompress(data, uncompressed_size)` (python-lz4 4.4.4
50    /// over liblz4 1.9.4's `LZ4_decompress_safe`): a declared size above
51    /// `i32::MAX` is python-lz4's `OverflowError` (its argument parse, so
52    /// first), and so, next, is an input above `i32::MAX` bytes, before
53    /// anything is reserved or read; otherwise the block is
54    /// scanned with liblz4's exact control flow (`lz4_run`), which gives
55    /// its verdict and the output's length, and only then is the output
56    /// allocated (that length, charged) and decoded. python-lz4 reserves
57    /// the whole declared size before it decodes, so where the machine
58    /// cannot reserve it UnityPy raises `MemoryError` and unityrs reads on
59    /// (`PARITY.md` section 19.3, "a count UnityPy allocates before it
60    /// reads").
61    fn decode(
62        &self,
63        input: &Bytes,
64        uncompressed: u32,
65        out: &mut DecodeBuf,
66    ) -> Result<Decoded, Error> {
67        let fail = |detail: String| Error::Decompress {
68            codec: Codec::Lz4,
69            detail: detail.into(),
70        };
71        let Ok(capacity) = i32::try_from(uncompressed) else {
72            return Err(fail(
73                "OverflowError: signed integer is greater than maximum".to_owned(),
74            ));
75        };
76        if i32::try_from(input.len()).is_err() {
77            return Err(fail(
78                "OverflowError: Input too large for LZ4 API".to_owned(),
79            ));
80        }
81        let capacity = usize::try_from(capacity).unwrap_or(0);
82        let lz4_error = |at: usize| {
83            fail(format!(
84                "LZ4BlockError: Decompression failed: corrupt input or insufficient space in \
85                 destination buffer. Error code: {}",
86                at.saturating_add(1)
87            ))
88        };
89        let n = lz4_run(input, capacity, None).map_err(lz4_error)?;
90        let dst = out.grow_zeroed(n)?;
91        lz4_run(input, capacity, Some(dst)).map_err(lz4_error)?;
92        Ok(Decoded::Written)
93    }
94}
95
96// liblz4 1.9.4 (lz4.c) constants.
97const MINMATCH: usize = 4;
98const LASTLITERALS: usize = 5;
99const MFLIMIT: usize = 12;
100const FASTLOOP_SAFE_DISTANCE: usize = 64;
101const ML_MASK: usize = 15;
102const RUN_MASK: usize = 15;
103
104/// `read_variable_length` (lz4.c 1.9.4): the bytes at `*ip` summed while each
105/// is 255; an error (`rvl_error`) once `*ip` passes `limit`, or, with
106/// `initial_check`, when it starts at or past it. `limit` is signed: a
107/// limit below the input's start fails the first check.
108fn read_variable_length(
109    src: &[u8],
110    ip: &mut usize,
111    limit: isize,
112    initial_check: bool,
113) -> Option<usize> {
114    let past = |ip: usize| isize::try_from(ip).map_or(true, |i| i > limit);
115    if initial_check && isize::try_from(*ip).map_or(true, |i| i >= limit) {
116        return None;
117    }
118    let mut length = 0usize;
119    loop {
120        let s = *src.get(*ip)?;
121        *ip += 1;
122        length = length.saturating_add(usize::from(s));
123        if past(*ip) {
124            return None;
125        }
126        if s != 255 {
127            return Some(length);
128        }
129    }
130}
131
132/// Copies a match of `length` bytes at `offset` behind `op` within `dst`,
133/// byte by byte in LZ77 order; offset 0 writes zeros, as liblz4 does (it
134/// zeroes four bytes, then copies them onto themselves).
135fn copy_match(dst: &mut [u8], op: usize, offset: usize, length: usize) {
136    let end = op.saturating_add(length).min(dst.len());
137    if offset == 0 {
138        if let Some(d) = dst.get_mut(op..end) {
139            d.fill(0);
140        }
141        return;
142    }
143    let Some(src) = op.checked_sub(offset) else {
144        return;
145    };
146    let mut at = op;
147    while at < end {
148        // Each pass copies what is already final: up to `offset` bytes, then
149        // twice that, as the copied run lengthens.
150        let step = (at - src).min(end - at);
151        dst.copy_within(src..src + step, at);
152        at += step;
153    }
154}
155
156/// The LZ4 decoder's state: liblz4's `ip` and `op` as offsets, and the
157/// output when this pass writes one.
158struct Lz4State<'a, 'o> {
159    src: &'a [u8],
160    dst: Option<&'o mut [u8]>,
161    ip: usize,
162    op: usize,
163    /// `iend` and `oend`, signed as liblz4's pointer comparisons are.
164    iend: isize,
165    oend: isize,
166}
167
168/// Where the safe loop is entered.
169enum Lz4Entry {
170    /// The loop's top.
171    Top,
172    /// `safe_literal_copy`, with the token and the literal length.
173    Literals(usize, usize),
174    /// `safe_match_copy`, with the offset and the length (MINMATCH added).
175    Match(usize, usize),
176}
177
178fn signed(n: usize) -> isize {
179    isize::try_from(n).unwrap_or(isize::MAX)
180}
181
182impl Lz4State<'_, '_> {
183    fn token(&mut self) -> Result<usize, usize> {
184        let t = self.src.get(self.ip).copied().ok_or(self.ip)?;
185        self.ip += 1;
186        Ok(usize::from(t))
187    }
188
189    fn le16(&mut self) -> Result<usize, usize> {
190        let b = self
191            .src
192            .get(self.ip..self.ip.saturating_add(2))
193            .and_then(|b| <[u8; 2]>::try_from(b).ok())
194            .ok_or(self.ip)?;
195        self.ip += 2;
196        Ok(usize::from(u16::from_le_bytes(b)))
197    }
198
199    fn varlen(&mut self, limit: isize, initial_check: bool) -> Result<usize, usize> {
200        read_variable_length(self.src, &mut self.ip, limit, initial_check).ok_or(self.ip)
201    }
202
203    /// Copies `n` literals and advances both positions.
204    fn literals(&mut self, n: usize) {
205        if let (Some(d), Some(from)) = (
206            self.dst.as_deref_mut(),
207            self.src.get(self.ip..self.ip.saturating_add(n)),
208        ) && let Some(to) = d.get_mut(self.op..self.op.saturating_add(n))
209        {
210            to.copy_from_slice(from);
211        }
212        self.ip = self.ip.saturating_add(n);
213        self.op = self.op.saturating_add(n);
214    }
215
216    /// Copies a match and advances the output.
217    fn copy(&mut self, offset: usize, n: usize) {
218        if let Some(d) = self.dst.as_deref_mut() {
219            copy_match(d, self.op, offset, n);
220        }
221        self.op = self.op.saturating_add(n);
222    }
223
224    /// The match length at `_copy_match` from the token's `mlen`, MINMATCH
225    /// added.
226    fn match_length(&mut self, mlen: usize) -> Result<usize, usize> {
227        let mut length = mlen;
228        if length == ML_MASK {
229            length += self.varlen(self.iend - signed(LASTLITERALS) + 1, false)?;
230        }
231        Ok(length + MINMATCH)
232    }
233
234    /// From the safe loop's literal copy (`cpy = op + length`, then
235    /// `safe_literal_copy`) through the match's offset and length; `None`
236    /// when this was the last sequence.
237    fn safe_literals(
238        &mut self,
239        token: usize,
240        length: usize,
241    ) -> Result<Option<(usize, usize)>, usize> {
242        let cpy = signed(self.op).saturating_add(signed(length));
243        let lit_end = signed(self.ip).saturating_add(signed(length));
244        if cpy > self.oend - signed(MFLIMIT) || lit_end > self.iend - signed(2 + 1 + LASTLITERALS) {
245            // The last sequence: it must end the input exactly and fit.
246            if lit_end != self.iend || cpy > self.oend {
247                return Err(self.ip);
248            }
249            self.literals(length);
250            return Ok(None);
251        }
252        self.literals(length);
253        let offset = self.le16()?;
254        let length = self.match_length(token & ML_MASK)?;
255        Ok(Some((offset, length)))
256    }
257
258    /// The fast loop, run while 64 bytes of output remain; where the safe
259    /// loop takes over.
260    fn fast_loop(&mut self) -> Result<Lz4Entry, usize> {
261        loop {
262            let token = self.token()?;
263            let mut length = token >> 4;
264            if length == RUN_MASK {
265                length += self.varlen(self.iend - signed(RUN_MASK), true)?;
266                if signed(self.op).saturating_add(signed(length)) > self.oend - 32
267                    || signed(self.ip).saturating_add(signed(length)) > self.iend - 32
268                {
269                    return Ok(Lz4Entry::Literals(token, length));
270                }
271            } else if signed(self.ip) > self.iend - (16 + 1) {
272                return Ok(Lz4Entry::Literals(token, length));
273            }
274            self.literals(length);
275            let offset = self.le16()?;
276            let mut length = token & ML_MASK;
277            if length == ML_MASK {
278                length += self.varlen(self.iend - signed(LASTLITERALS) + 1, false)? + MINMATCH;
279                if offset > self.op {
280                    return Err(self.ip);
281                }
282            } else {
283                length += MINMATCH;
284            }
285            if signed(self.op).saturating_add(signed(length))
286                >= self.oend - signed(FASTLOOP_SAFE_DISTANCE)
287            {
288                return Ok(Lz4Entry::Match(offset, length));
289            }
290            if offset > self.op {
291                return Err(self.ip);
292            }
293            self.copy(offset, length);
294        }
295    }
296
297    /// The safe loop with its two-stage shortcut, from `entry`; the decoded
298    /// length.
299    fn safe_loop(&mut self, mut entry: Lz4Entry) -> Result<usize, usize> {
300        // liblz4's `shortiend` and `shortoend`.
301        let short_in = self.iend - 14 - 2;
302        let short_out = self.oend - 14 - 18;
303        loop {
304            let (offset, length) = match std::mem::replace(&mut entry, Lz4Entry::Top) {
305                Lz4Entry::Match(offset, length) => (offset, length),
306                Lz4Entry::Literals(token, length) => match self.safe_literals(token, length)? {
307                    Some(m) => m,
308                    None => return Ok(self.op),
309                },
310                Lz4Entry::Top => {
311                    let token = self.token()?;
312                    let mut length = token >> 4;
313                    if length != RUN_MASK
314                        && signed(self.ip) < short_in
315                        && signed(self.op) <= short_out
316                    {
317                        self.literals(length);
318                        let mlen = token & ML_MASK;
319                        let offset = self.le16()?;
320                        if mlen != ML_MASK && offset >= 8 && offset <= self.op {
321                            self.copy(offset, mlen + MINMATCH);
322                            continue;
323                        }
324                        (offset, self.match_length(mlen)?)
325                    } else {
326                        if length == RUN_MASK {
327                            length += self.varlen(self.iend - signed(RUN_MASK), true)?;
328                        }
329                        match self.safe_literals(token, length)? {
330                            Some(m) => m,
331                            None => return Ok(self.op),
332                        }
333                    }
334                }
335            };
336            // `safe_match_copy`: the offset within the output, and the last
337            // LASTLITERALS bytes left to literals.
338            if offset > self.op {
339                return Err(self.ip);
340            }
341            if signed(self.op).saturating_add(signed(length)) > self.oend - signed(LASTLITERALS) {
342                return Err(self.ip);
343            }
344            self.copy(offset, length);
345        }
346    }
347}
348
349/// liblz4 1.9.4's `LZ4_decompress_generic` as `LZ4_decompress_safe` calls
350/// it (a full block, no dictionary), on x86-64, where `LZ4_FAST_DEC_LOOP`
351/// is on: the fast loop while 64 bytes of output remain, then the safe loop
352/// with its two-stage shortcut. Every check is liblz4's at liblz4's place, so
353/// the verdict is liblz4's; the copies are exact (liblz4's wild copies write
354/// past a copy's end, but only bytes a later copy overwrites or the result
355/// leaves out).
356///
357/// Returns the decoded length, or the input offset at which liblz4 fails (it
358/// returns `-(offset) - 1`). With `dst` (exactly the decoded length, from an
359/// earlier call without it), the output is written there.
360fn lz4_run(src: &[u8], output_size: usize, dst: Option<&mut [u8]>) -> Result<usize, usize> {
361    if output_size == 0 {
362        return if src == [0] { Ok(0) } else { Err(0) };
363    }
364    if src.is_empty() {
365        return Err(0);
366    }
367    let mut st = Lz4State {
368        src,
369        dst,
370        ip: 0,
371        op: 0,
372        iend: signed(src.len()),
373        oend: signed(output_size),
374    };
375    let entry = if st.oend >= signed(FASTLOOP_SAFE_DISTANCE) {
376        st.fast_loop()?
377    } else {
378        Lz4Entry::Top
379    };
380    st.safe_loop(entry)
381}