rust-kernel / src / fs / lzo.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//! LZO1X decompression, hand-written (btrfs's "lzo" compression).
//!
//! LZO (Markus Oberhumer, 1996) is an LZ77-style compressor built for speed.
//! The compressed stream is a sequence of instructions, each either
//! "copy the next N bytes as they are" (a **literal run**) or "copy N bytes
//! from D bytes back in the output" (a **match**, which may overlap itself,
//! so `abcabcabc` is "abc" plus one match of 6 at distance 3).
//!
//! An instruction starts with one byte `t`; its range says what it is:
//!
//! ```text
//! t >= 64      M2 match: length 3-8, distance up to 2 KiB (one more byte)
//! 32 <= t < 64 M3 match: length from t (or a run of zero bytes), distance
//!              up to 16 KiB in the next two bytes
//! 16 <= t < 32 M4 match: distance 16-48 KiB; distance 16 KiB exactly
//!              means "end of stream"
//! t < 16       depends on what came before (the `state`):
//!              after a match with no trailing literals: a literal run;
//!              after 1-3 trailing literals: a 2-byte match, distance <= 1 KiB;
//!              after a long literal run: a 3-byte match, distance 2-3 KiB
//! ```
//!
//! The low 2 bits of most match instructions say how many literals (0-3)
//! follow the match, so short literal runs cost no extra byte. Long lengths
//! are written as a 0 (meaning "more"), then zero bytes worth 255 each,
//! then a final byte that's added.
//!
//! This follows the Linux kernel's `lzo1x_decompress_safe`, with every
//! read and back-reference checked: bad input gives `Err`, never a panic.

use alloc::vec::Vec;

/// Decompress one LZO1X stream, appending to `out`. `limit` is the most
/// bytes this stream may produce (btrfs: one sector).
pub fn decompress(src: &[u8], out: &mut Vec<u8>, limit: usize) -> Result<(), &'static str> {
    let start = out.len();
    let mut ip = 0usize;
    let byte = |ip: &mut usize| -> Result<usize, &'static str> {
        let b = *src.get(*ip).ok_or("truncated")?;
        *ip += 1;
        Ok(b as usize)
    };
    // A length continued in zero bytes: each 0 adds 255, then the final byte.
    let long_len = |ip: &mut usize, base: usize| -> Result<usize, &'static str> {
        let mut n = base;
        loop {
            let b = byte(ip)?;
            if b != 0 {
                return Ok(n + b);
            }
            n += 255;
        }
    };
    let literals = |ip: &mut usize, n: usize, out: &mut Vec<u8>| -> Result<(), &'static str> {
        let bytes = src.get(*ip..*ip + n).ok_or("truncated literal run")?;
        out.extend_from_slice(bytes);
        *ip += n;
        Ok(())
    };

    // `state`: 0 = last instruction was a match without trailing literals,
    // 1-3 = it had that many trailing literals, 4 = a literal run of 4+.
    let mut state;
    // The first byte may be a literal run of 18+ (t - 17) bytes.
    if *src.first().ok_or("empty")? > 17 {
        let n = byte(&mut ip)? - 17;
        literals(&mut ip, n, out)?;
        state = if n < 4 { n } else { 4 };
    } else {
        state = 0;
    }

    loop {
        if out.len() - start > limit {
            return Err("output too long");
        }
        let t = byte(&mut ip)?;
        let (len, dist, next);
        if t < 16 {
            if state == 0 {
                // Literal run of t + 3 bytes (t == 0: a long length).
                let n = if t == 0 { long_len(&mut ip, 15)? } else { t };
                literals(&mut ip, n + 3, out)?;
                state = 4;
                continue;
            }
            let b = byte(&mut ip)?;
            next = t & 3;
            if state < 4 {
                (len, dist) = (2, 1 + (t >> 2) + (b << 2));
            } else {
                (len, dist) = (3, 1 + 0x800 + (t >> 2) + (b << 2));
            }
        } else if t >= 64 {
            let b = byte(&mut ip)?;
            next = t & 3;
            (len, dist) = ((t >> 5) + 1, 1 + ((t >> 2) & 7) + (b << 3));
        } else if t >= 32 {
            len = if t & 31 == 0 { long_len(&mut ip, 31)? } else { t & 31 } + 2;
            let v = byte(&mut ip)? | (byte(&mut ip)? << 8);
            next = v & 3;
            dist = 1 + (v >> 2);
        } else {
            len = if t & 7 == 0 { long_len(&mut ip, 7)? } else { t & 7 } + 2;
            let v = byte(&mut ip)? | (byte(&mut ip)? << 8);
            next = v & 3;
            let d = ((t & 8) << 11) + (v >> 2);
            if d == 0 {
                return Ok(()); // the end marker (0x11 0x00 0x00)
            }
            dist = d + 0x4000;
        }
        // Copy the match byte by byte: it may overlap what it's producing.
        if dist > out.len() - start {
            return Err("match before the start");
        }
        for _ in 0..len {
            out.push(out[out.len() - dist]);
        }
        literals(&mut ip, next, out)?;
        state = next;
    }
}