Skip to main content

pltrs_codec/
zlib.rs

1//! The zlib format (RFC 1950): a two-byte header, a DEFLATE stream and an
2//! Adler-32 trailer.
3//!
4//! ```
5//! use pltrs_codec::{zlib, CompressionLevel};
6//!
7//! let packed = zlib::compress(b"hello, hello, hello", CompressionLevel::DEFAULT)?;
8//! assert_eq!(&packed[..2], [0x78, 0x9C]);
9//! assert_eq!(zlib::decompress(&packed)?, b"hello, hello, hello");
10//! # Ok::<(), Box<dyn std::error::Error>>(())
11//! ```
12
13use std::error::Error;
14use std::fmt;
15
16use pltrs_core::alloc::OutOfMemory;
17
18use crate::checksum::adler32;
19use crate::deflate::encode::{self, Deflater, Wrap};
20use crate::deflate::{self, CompressionLevel, InflateError, Options};
21
22/// The `FDICT` flag: a preset dictionary identifier follows the header.
23const FLAG_DICTIONARY: u8 = 0x20;
24
25/// An error found while decoding a zlib stream.
26#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub enum ZlibError {
28    /// The input ended inside the header or the checksum trailer.
29    UnexpectedEof,
30    /// The header names a compression method other than DEFLATE (8).
31    UnsupportedMethod(u8),
32    /// The header declares a window larger than 32 KiB.
33    InvalidWindowSize(u8),
34    /// The header's check bits are wrong (`CMF * 256 + FLG` is not a
35    /// multiple of 31).
36    InvalidHeaderCheck,
37    /// The stream needs a preset dictionary, which is not supported.
38    PresetDictionary,
39    /// The compressed data is malformed.
40    Inflate(InflateError),
41    /// The Adler-32 of the decompressed data does not match the trailer.
42    ChecksumMismatch {
43        /// Checksum stored in the stream.
44        expected: u32,
45        /// Checksum of the decompressed data.
46        actual: u32,
47    },
48    /// Bytes follow the end of the stream.
49    TrailingData {
50        /// Number of bytes after the stream.
51        len: usize,
52    },
53}
54
55impl fmt::Display for ZlibError {
56    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
57        match *self {
58            Self::UnexpectedEof => f.write_str("zlib stream ended unexpectedly"),
59            Self::UnsupportedMethod(method) => {
60                write!(f, "unsupported zlib compression method {method}")
61            }
62            Self::InvalidWindowSize(info) => {
63                write!(f, "invalid zlib window size 2^{}", u32::from(info) + 8)
64            }
65            Self::InvalidHeaderCheck => f.write_str("invalid zlib header check bits"),
66            Self::PresetDictionary => f.write_str("zlib preset dictionaries are not supported"),
67            Self::Inflate(error) => write!(f, "invalid zlib data: {error}"),
68            Self::ChecksumMismatch { expected, actual } => write!(
69                f,
70                "zlib checksum mismatch: stream says {expected:#010x}, data gives {actual:#010x}"
71            ),
72            Self::TrailingData { len } => write!(f, "{len} bytes of data after the zlib stream"),
73        }
74    }
75}
76
77impl Error for ZlibError {
78    fn source(&self) -> Option<&(dyn Error + 'static)> {
79        match self {
80            Self::Inflate(error) => Some(error),
81            _ => None,
82        }
83    }
84}
85
86impl From<InflateError> for ZlibError {
87    fn from(error: InflateError) -> Self {
88        Self::Inflate(error)
89    }
90}
91
92/// Compresses `data` into a new zlib stream at `level`, as zlib-ng's
93/// `compress2` does.
94///
95/// # Errors
96///
97/// When the memory for the compressor or the output cannot be allocated.
98pub fn compress(data: &[u8], level: CompressionLevel) -> Result<Vec<u8>, OutOfMemory> {
99    compress_with(data, Options::new(level))
100}
101
102/// Compresses `data` into a new zlib stream as zlib-ng does with
103/// `options`.
104///
105/// # Errors
106///
107/// When the memory for the compressor or the output cannot be allocated.
108pub fn compress_with(data: &[u8], options: Options) -> Result<Vec<u8>, OutOfMemory> {
109    let mut out = Vec::new();
110    encode::one_shot(data, options, Wrap::Zlib, &mut None, &mut out)?;
111    Ok(out)
112}
113
114/// Appends the zlib compression of `data` at `level` to `out`.
115///
116/// # Errors
117///
118/// When the memory for the compressor or the output cannot be allocated
119/// (what was written of it stays in `out`).
120pub fn compress_into(
121    data: &[u8],
122    level: CompressionLevel,
123    out: &mut Vec<u8>,
124) -> Result<(), OutOfMemory> {
125    encode::one_shot(data, Options::new(level), Wrap::Zlib, &mut None, out)
126}
127
128/// Compresses stream after stream with the same tables, for writers of
129/// many streams (PDF's): each stream is the one [`compress_with`] writes,
130/// without allocating and clearing the compressor's 300 KiB of tables
131/// anew for each.
132///
133/// ```
134/// use pltrs_codec::{zlib, CompressionLevel};
135/// use pltrs_codec::deflate::Options;
136///
137/// let mut compressor = zlib::Compressor::new();
138/// let options = Options::new(CompressionLevel::DEFAULT);
139/// for text in [&b"first stream"[..], b"second, second"] {
140///     let mut packed = Vec::new();
141///     compressor.compress_into(text, options, &mut packed)?;
142///     assert_eq!(packed, zlib::compress_with(text, options)?);
143/// }
144/// # Ok::<(), Box<dyn std::error::Error>>(())
145/// ```
146#[derive(Debug, Default)]
147pub struct Compressor {
148    tables: Option<Deflater>,
149}
150
151impl Compressor {
152    /// A compressor that allocates its tables at its first stream.
153    pub fn new() -> Self {
154        Self::default()
155    }
156
157    /// Appends the zlib stream of `data` with `options` to `out`.
158    ///
159    /// # Errors
160    ///
161    /// When the memory for the compressor or the output cannot be
162    /// allocated (what was written of the stream stays in `out`).
163    pub fn compress_into(
164        &mut self,
165        data: &[u8],
166        options: Options,
167        out: &mut Vec<u8>,
168    ) -> Result<(), OutOfMemory> {
169        encode::one_shot(data, options, Wrap::Zlib, &mut self.tables, out)
170    }
171}
172
173/// Decompresses a complete zlib stream; trailing bytes are an error.
174pub fn decompress(input: &[u8]) -> Result<Vec<u8>, ZlibError> {
175    decompress_with_limit(input, usize::MAX)
176}
177
178/// Like [`decompress`], but fails instead of producing more than `limit`
179/// bytes.
180pub fn decompress_with_limit(input: &[u8], limit: usize) -> Result<Vec<u8>, ZlibError> {
181    let mut out = Vec::with_capacity(limit.min(input.len().saturating_mul(4)));
182    let used = decompress_into(input, &mut out, limit)?;
183    if used < input.len() {
184        return Err(ZlibError::TrailingData {
185            len: input.len() - used,
186        });
187    }
188    Ok(out)
189}
190
191/// Decompresses the zlib stream at the start of `input`, appending at most
192/// `limit` bytes to `out`, and returns the number of input bytes the stream
193/// occupied (bytes after it are left alone).
194///
195/// On error, `out` may hold part of the decompressed data.
196pub fn decompress_into(input: &[u8], out: &mut Vec<u8>, limit: usize) -> Result<usize, ZlibError> {
197    let &[cmf, flags] = input.first_chunk::<2>().ok_or(ZlibError::UnexpectedEof)?;
198    if cmf & 0x0F != 8 {
199        return Err(ZlibError::UnsupportedMethod(cmf & 0x0F));
200    }
201    if cmf >> 4 > 7 {
202        return Err(ZlibError::InvalidWindowSize(cmf >> 4));
203    }
204    if (u16::from(cmf) << 8 | u16::from(flags)) % 31 != 0 {
205        return Err(ZlibError::InvalidHeaderCheck);
206    }
207    if flags & FLAG_DICTIONARY != 0 {
208        return Err(ZlibError::PresetDictionary);
209    }
210    let start = out.len();
211    let stream_end = 2 + deflate::decompress_into(&input[2..], out, limit)?;
212    let trailer = input
213        .get(stream_end..)
214        .and_then(<[u8]>::first_chunk::<4>)
215        .ok_or(ZlibError::UnexpectedEof)?;
216    let expected = u32::from_be_bytes(*trailer);
217    let actual = adler32(&out[start..]);
218    if expected != actual {
219        return Err(ZlibError::ChecksumMismatch { expected, actual });
220    }
221    Ok(stream_end + 4)
222}
223
224#[cfg(test)]
225mod tests {
226    use super::*;
227    use crate::deflate::encode::RowSource;
228    use crate::deflate::{MemoryLevel, Strategy};
229    use crate::test_util::{Rng, varied_inputs};
230
231    #[test]
232    fn headers_match_zlib_for_every_level() {
233        let expected = [
234            [0x78, 0x01],
235            [0x78, 0x01],
236            [0x78, 0x5E],
237            [0x78, 0x5E],
238            [0x78, 0x5E],
239            [0x78, 0x5E],
240            [0x78, 0x9C],
241            [0x78, 0xDA],
242            [0x78, 0xDA],
243            [0x78, 0xDA],
244        ];
245        for (level, bytes) in (0..=9).zip(expected) {
246            let packed = compress(b"", CompressionLevel::new(level).unwrap()).unwrap();
247            assert_eq!(packed[..2], bytes, "level {level}");
248        }
249        for strategy in [Strategy::HuffmanOnly, Strategy::Rle, Strategy::Fixed] {
250            let options = Options::new(CompressionLevel::BEST).strategy(strategy);
251            assert_eq!(compress_with(b"", options).unwrap()[..2], [0x78, 0x01]);
252        }
253        let filtered = Options::new(CompressionLevel::BEST).strategy(Strategy::Filtered);
254        assert_eq!(compress_with(b"", filtered).unwrap()[..2], [0x78, 0xDA]);
255    }
256
257    #[test]
258    fn matches_reference_stream() {
259        let packed = compress(b"hello", CompressionLevel::DEFAULT).unwrap();
260        let reference = [
261            0x78, 0x9C, 0xCB, 0x48, 0xCD, 0xC9, 0xC9, 0x07, 0x00, 0x06, 0x2C, 0x02, 0x15,
262        ];
263        assert_eq!(packed, reference);
264        assert_eq!(decompress(&reference).unwrap(), b"hello");
265    }
266
267    #[test]
268    fn round_trips_at_every_level() {
269        let mut rng = Rng::new(11);
270        for input in varied_inputs(&mut rng).iter().step_by(3) {
271            for level in 0..=9 {
272                let packed = compress(input, CompressionLevel::new(level).unwrap()).unwrap();
273                assert_eq!(decompress(&packed).unwrap(), *input, "level {level}");
274            }
275        }
276    }
277
278    /// Rows of `len` bytes cut from `data`.
279    struct Rows<'a> {
280        data: &'a [u8],
281        len: usize,
282    }
283
284    impl encode::RowSource for Rows<'_> {
285        fn rows(&self) -> usize {
286            self.data.len() / self.len
287        }
288
289        fn row(&mut self, index: usize) -> &[u8] {
290            &self.data[index * self.len..(index + 1) * self.len]
291        }
292    }
293
294    #[test]
295    fn rows_arrive_in_buffers_of_the_given_size() {
296        let mut rng = Rng::new(12);
297        let noise = rng.bytes(300_000);
298        let pattern: Vec<u8> = (0..300_000).map(|i| (i / 7 % 13) as u8).collect();
299        for data in [&noise, &pattern] {
300            for level in [0, 1, 3, 6, 9] {
301                let options = Options::new(CompressionLevel::new(level).unwrap());
302                let mut rows = Rows { data, len: 1201 };
303                let packed = encode::rows(&mut rows, options, 65_536).unwrap();
304                let whole = rows.rows() * rows.len;
305                assert_eq!(decompress(&packed.stream).unwrap(), data[..whole]);
306                assert_eq!(packed.ends.last(), Some(&packed.stream.len()));
307                let full = &packed.ends[..packed.ends.len() - 1];
308                assert!(
309                    full.iter()
310                        .zip(1..)
311                        .all(|(&end, index)| end == index * 65_536),
312                    "every buffer full but the last, level {level}"
313                );
314            }
315        }
316    }
317
318    #[test]
319    fn a_reused_compressor_writes_what_a_new_one_writes() {
320        let mut rng = Rng::new(13);
321        let mut inputs = varied_inputs(&mut rng);
322        // Long inputs first, so that short ones follow tables full of
323        // their hashes and window bytes.
324        inputs.sort_by_key(|input| std::cmp::Reverse(input.len()));
325        let mut compressor = Compressor::new();
326        for (index, input) in inputs.iter().enumerate() {
327            let level = CompressionLevel::new((index % 10) as u8).unwrap();
328            let memory = MemoryLevel::new([8, 9, 1][index % 3]).unwrap();
329            let options = Options::new(level).memory_level(memory);
330            let mut packed = vec![0xAA];
331            compressor
332                .compress_into(input, options, &mut packed)
333                .unwrap();
334            assert_eq!(
335                packed[1..],
336                compress_with(input, options).unwrap(),
337                "input {index}"
338            );
339        }
340    }
341
342    #[test]
343    fn rejects_bad_headers_and_trailers() {
344        let good = compress(b"payload payload", CompressionLevel::DEFAULT).unwrap();
345        assert_eq!(decompress(&[]), Err(ZlibError::UnexpectedEof));
346        assert_eq!(decompress(&[0x78]), Err(ZlibError::UnexpectedEof));
347        assert_eq!(
348            decompress(&[0x79, 0x9C]),
349            Err(ZlibError::UnsupportedMethod(9))
350        );
351        assert_eq!(
352            decompress(&[0x88, 0x98]),
353            Err(ZlibError::InvalidWindowSize(8))
354        );
355        assert_eq!(
356            decompress(&[0x78, 0x9D]),
357            Err(ZlibError::InvalidHeaderCheck)
358        );
359        assert_eq!(decompress(&[0x78, 0xBB]), Err(ZlibError::PresetDictionary));
360
361        let mut corrupted = good.clone();
362        let last = corrupted.len() - 1;
363        corrupted[last] ^= 0x01;
364        assert!(matches!(
365            decompress(&corrupted),
366            Err(ZlibError::ChecksumMismatch { .. })
367        ));
368        assert_eq!(
369            decompress(&good[..good.len() - 2]),
370            Err(ZlibError::UnexpectedEof)
371        );
372
373        let mut trailing = good.clone();
374        trailing.extend_from_slice(&[1, 2, 3]);
375        assert_eq!(
376            decompress(&trailing),
377            Err(ZlibError::TrailingData { len: 3 })
378        );
379        let mut out = Vec::new();
380        assert_eq!(
381            decompress_into(&trailing, &mut out, usize::MAX),
382            Ok(good.len())
383        );
384        assert_eq!(out, b"payload payload");
385
386        let broken_deflate = [0x78, 0x9C, 0x07, 0x00];
387        assert_eq!(
388            decompress(&broken_deflate),
389            Err(ZlibError::Inflate(InflateError::InvalidBlockType))
390        );
391        assert!(
392            ZlibError::Inflate(InflateError::InvalidBlockType)
393                .source()
394                .is_some()
395        );
396    }
397
398    #[test]
399    fn limit_applies_to_decompressed_size() {
400        let packed = compress(&[7; 1000], CompressionLevel::BEST).unwrap();
401        assert_eq!(decompress_with_limit(&packed, 1000).unwrap().len(), 1000);
402        assert_eq!(
403            decompress_with_limit(&packed, 999),
404            Err(ZlibError::Inflate(InflateError::OutputLimitExceeded {
405                limit: 999
406            }))
407        );
408    }
409}