mopenzl 0.2.0

OpenZL compression and decompression in safe Rust; encoding is byte-identical to Meta's reference library
Documentation 
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286

//! The generic LZ codec (`DI_lz`), feature `lz`.
//!
//! Ports `codecs/lz/decode_lz_binding.c` (`DI_lz`) and
//! `codecs/lz/decode_lz_kernel.c` (`ZL_Lz_decode`). Four inputs: the
//! literals (serial) and the offsets, literal lengths and match lengths
//! (numeric, each of its own width 1, 2, 4 or 8, one entry per sequence).
//! The header is the decoded size as a varint with nothing after it. The
//! output is the literals and matches in sequence order followed by the
//! literals no sequence used, and must fill the declared size exactly.
//!
//! The reference has loops specialised for 16-bit and 32-bit streams plus a
//! generic one, all with one meaning; this port is the generic loop, with
//! the widths read as little-endian integers.

use super::{Ctx, Desc};
use crate::decompressor::core::data::{Input, Stream, Type, corrupt};
use crate::decompressor::error::DecodeError;
use crate::shared::varint;

/// `ZL_StandardTransformID_lz`.
pub(crate) const LZ: Desc = Desc {
    id: 19,
    min_version: 24,
    regens: &[Type::Serial],
    variable_regens: false,
    inputs: &[Type::Serial, Type::Numeric, Type::Numeric, Type::Numeric],
    variable_inputs: 0,
    decode,
};

fn decode(
    ctx: &mut Ctx<'_>,
    inputs: &[Input<'_>],
    regens: &mut [Stream],
) -> Result<(), DecodeError> {
    let [literals, offsets, literal_lens, match_lens] = inputs else {
        return Err(corrupt());
    };
    let sequences = offsets.len();
    if literal_lens.len() != sequences || match_lens.len() != sequences {
        return Err(corrupt());
    }
    let (size, used) = varint::decode(ctx.header).map_err(|_| corrupt())?;
    if used != ctx.header.len() {
        return Err(corrupt());
    }
    let size = usize::try_from(size).unwrap_or(usize::MAX);
    let out = regens[0].fixed(1, size)?;
    let sequences = Sequences {
        literals: literals.bytes,
        offsets: Numbers::new(offsets),
        literal_lens: Numbers::new(literal_lens),
        match_lens: Numbers::new(match_lens),
        count: sequences,
    };
    sequences.expand(out, size)
}

/// A numeric stream read as unsigned little-endian integers of one width.
#[derive(Copy, Clone)]
struct Numbers<'a> {
    bytes: &'a [u8],
    width: usize,
}

impl<'a> Numbers<'a> {
    fn new(input: &Input<'a>) -> Self {
        Self {
            bytes: input.bytes,
            width: input.width,
        }
    }

    /// Element `index`; the caller keeps it below the stream's length.
    fn get(&self, index: usize) -> u64 {
        let mut value = [0u8; 8];
        let start = index * self.width;
        let width = self.width.min(8);
        value[..width].copy_from_slice(&self.bytes[start..start + width]);
        u64::from_le_bytes(value)
    }
}

/// The inputs of the codec.
struct Sequences<'a> {
    literals: &'a [u8],
    offsets: Numbers<'a>,
    literal_lens: Numbers<'a>,
    match_lens: Numbers<'a>,
    count: usize,
}

impl Sequences<'_> {
    /// `ZL_Lz_decode`: appends the `size` decoded bytes to the empty `out`.
    fn expand(&self, out: &mut alloc::vec::Vec<u8>, size: usize) -> Result<(), DecodeError> {
        let mut literals = self.literals;
        for sequence in 0..self.count {
            let literal_len =
                usize::try_from(self.literal_lens.get(sequence)).unwrap_or(usize::MAX);
            let offset = usize::try_from(self.offsets.get(sequence)).unwrap_or(usize::MAX);
            let match_len = usize::try_from(self.match_lens.get(sequence)).unwrap_or(usize::MAX);
            // Literals: enough of them and room for them.
            if literal_len > literals.len() || literal_len > size - out.len() {
                return Err(corrupt());
            }
            let (now, rest) = literals.split_at(literal_len);
            out.extend_from_slice(now);
            literals = rest;
            // Match: a real offset and room for it.
            if offset == 0 || offset > out.len() || match_len > size - out.len() {
                return Err(corrupt());
            }
            copy_match(out, offset, match_len);
        }
        // The literals no sequence used end the output, which must be full.
        if literals.len() > size - out.len() {
            return Err(corrupt());
        }
        out.extend_from_slice(literals);
        if out.len() == size {
            Ok(())
        } else {
            Err(corrupt())
        }
    }
}

/// Appends `length` bytes starting `offset` bytes back; an offset below
/// `length` repeats the pattern.
fn copy_match(out: &mut alloc::vec::Vec<u8>, offset: usize, length: usize) {
    let from = out.len() - offset;
    let mut done = 0;
    while done < length {
        let chunk = offset.min(length - done);
        out.extend_from_within(from..from + chunk);
        done += chunk;
    }
}

#[cfg(test)]
mod tests {
    use alloc::vec;
    use alloc::vec::Vec;

    use super::super::State;
    use super::*;
    use crate::Backend;

    /// Literals, three numeric streams and a header.
    type Case<'a> = (&'a [u8], Streams<'a>, &'a [u8]);
    /// Width and values of the offsets, literal lengths and match lengths.
    type Streams<'a> = [(usize, &'a [u64]); 3];

    fn numeric(width: usize, values: &[u64]) -> (usize, Vec<u8>) {
        let bytes = values
            .iter()
            .flat_map(|value| value.to_le_bytes()[..width].to_vec())
            .collect();
        (width, bytes)
    }

    /// Runs the codec on `literals` and `[(width, values)]` streams.
    fn run(
        header: &[u8],
        literals: &[u8],
        streams: Streams<'_>,
        budget: usize,
    ) -> Result<Vec<u8>, DecodeError> {
        let encoded: Vec<_> = streams
            .iter()
            .map(|&(width, values)| numeric(width, values))
            .collect();
        let mut inputs = vec![Input::serial(literals)];
        inputs.extend(encoded.iter().map(|(width, bytes)| Input {
            ty: Type::Numeric,
            width: *width,
            bytes,
            lens: &[],
        }));
        let mut state = State::new(Backend::default());
        let mut ctx = Ctx::new(&mut state, header);
        let mut regens = [Stream::default()];
        regens[0].prepare(Type::Serial, budget);
        decode(&mut ctx, &inputs, &mut regens)?;
        regens[0].validate()?;
        Ok(regens[0].bytes().to_vec())
    }

    #[test]
    fn sequences_expand_with_literals_matches_and_a_tail() {
        // "ab", 5 bytes at distance 2 ("ababa"), "cd", 3 at distance 7 ("aba"), tail.
        let out = run(
            &[16],
            b"abcdTAIL",
            [(2, &[2, 7]), (1, &[2, 2]), (8, &[5, 3])],
            64,
        )
        .unwrap();
        assert_eq!(out, b"abababacdabaTAIL");
        // The narrowest and widest integers hold the same values.
        let wide = run(
            &[16],
            b"abcdTAIL",
            [(8, &[2, 7]), (4, &[2, 2]), (2, &[5, 3])],
            64,
        )
        .unwrap();
        assert_eq!(wide, out);
        // No sequences: the literals are the output.
        assert_eq!(
            run(&[4], b"abcd", [(1, &[]), (1, &[]), (1, &[])], 64).unwrap(),
            b"abcd"
        );
        assert_eq!(
            run(&[0], b"", [(1, &[]), (1, &[]), (1, &[])], 64).unwrap(),
            b""
        );
    }

    #[test]
    fn long_matches_repeat_short_offsets() {
        let out = run(&[103], b"xy", [(1, &[2]), (1, &[2]), (2, &[101])], 128).unwrap();
        let mut expected = b"xy".to_vec();
        expected.extend(b"xy".iter().cycle().take(101));
        assert_eq!(out, expected);
    }

    #[test]
    fn mismatched_counts_and_headers_are_rejected() {
        let ok = [(1usize, &[1u64][..]), (1, &[1]), (1, &[1])];
        assert!(run(&[3], b"ab", ok, 64).is_ok());
        assert_eq!(
            run(&[3], b"ab", [(1, &[1]), (1, &[1, 1]), (1, &[1])], 64),
            Err(corrupt())
        );
        assert_eq!(
            run(&[3], b"ab", [(1, &[1]), (1, &[1]), (1, &[])], 64),
            Err(corrupt())
        );
        // Leftover, missing and overlong headers.
        assert_eq!(run(&[3, 0], b"ab", ok, 64), Err(corrupt()));
        assert_eq!(run(&[], b"ab", ok, 64), Err(corrupt()));
        assert_eq!(run(&[0x80], b"ab", ok, 64), Err(corrupt()));
        // A size beyond the budget, and one that does not match the content.
        assert_eq!(run(&[100], b"ab", ok, 64), Err(corrupt()));
        assert_eq!(run(&[4], b"ab", ok, 64), Err(corrupt()));
        assert_eq!(run(&[2], b"ab", ok, 64), Err(corrupt()));
        // Missing inputs.
        let mut state = State::new(Backend::default());
        let mut ctx = Ctx::new(&mut state, &[0]);
        let mut regens = [Stream::default()];
        regens[0].prepare(Type::Serial, 8);
        assert_eq!(decode(&mut ctx, &[], &mut regens), Err(corrupt()));
    }

    #[test]
    fn corrupt_sequences_are_rejected() {
        // literal length 3 with 2 literals; 4 of 2 total; offset 0; offset
        // beyond the output; match past the end; tail past the end.
        let cases: [Case<'_>; 7] = [
            (b"ab", [(1, &[1]), (1, &[3]), (1, &[1])], &[7]),
            (b"abcd", [(1, &[1]), (1, &[3]), (1, &[1])], &[2]),
            (b"ab", [(1, &[0]), (1, &[2]), (1, &[2])], &[6]),
            (b"ab", [(1, &[3]), (1, &[2]), (1, &[2])], &[6]),
            (b"ab", [(1, &[1]), (1, &[2]), (1, &[9])], &[6]),
            (b"abcdef", [(1, &[1]), (1, &[2]), (1, &[1])], &[5]),
            (b"ab", [(1, &[1]), (1, &[2]), (1, &[1])], &[9]),
        ];
        for (literals, streams, header) in cases {
            assert_eq!(
                run(header, literals, streams, 64),
                Err(corrupt()),
                "{literals:?}"
            );
        }
        // Values above `isize::MAX` are negative in the reference.
        for streams in [
            [(8, &[1][..]), (8, &[u64::MAX]), (8, &[1])],
            [(8, &[u64::MAX]), (8, &[2]), (8, &[1])],
            [(8, &[1]), (8, &[2]), (8, &[u64::MAX])],
            [(8, &[1]), (8, &[1 << 63]), (8, &[1])],
        ] {
            assert_eq!(run(&[8], b"ab", streams, 64), Err(corrupt()));
        }
    }
}