Skip to main content

pltrs_codec/deflate/encode/
options.rs

1//! What a compressor is asked for: the level, the strategy and the memory
2//! level of zlib's `deflateInit2`, and the parameters zlib-ng's
3//! `configuration_table` derives from the level.
4
5use std::error::Error;
6use std::fmt;
7
8use crate::deflate::CompressionLevel;
9
10/// How the compressor looks for matches (zlib's `strategy`).
11///
12/// Every strategy writes a valid DEFLATE stream; they trade the search
13/// for repeated strings against speed or against data whose redundancy
14/// lies elsewhere.
15#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
16pub enum Strategy {
17    /// The level's own parsing (`Z_DEFAULT_STRATEGY`).
18    #[default]
19    Default,
20    /// For filtered image data (`Z_FILTERED`): the lazy levels 7–9 drop
21    /// matches of five bytes or fewer. Pillow writes PNG images with it.
22    Filtered,
23    /// Huffman coding of literals only, no matches (`Z_HUFFMAN_ONLY`).
24    HuffmanOnly,
25    /// Matches of distance one only, runs of a byte (`Z_RLE`).
26    Rle,
27    /// The level's parsing, always written with the fixed Huffman codes
28    /// (`Z_FIXED`).
29    Fixed,
30}
31
32impl Strategy {
33    /// Whether the zlib header records the fastest level for it (zlib-ng
34    /// writes `FLEVEL` 0 for the strategies from `Z_HUFFMAN_ONLY` on).
35    pub(crate) fn is_fastest_kind(self) -> bool {
36        matches!(self, Self::HuffmanOnly | Self::Rle | Self::Fixed)
37    }
38}
39
40/// How much memory the compressor buffers symbols in (zlib's
41/// `memLevel`, 1 to 9): a block holds up to `2^(level + 6) - 1` symbols.
42///
43/// ```
44/// use pltrs_codec::deflate::MemoryLevel;
45///
46/// assert_eq!(MemoryLevel::new(8)?, MemoryLevel::DEFAULT);
47/// assert!(MemoryLevel::new(0).is_err());
48/// # Ok::<(), pltrs_codec::deflate::InvalidMemoryLevel>(())
49/// ```
50#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
51pub struct MemoryLevel(u8);
52
53impl MemoryLevel {
54    /// zlib's default, 8: blocks of up to 16 383 symbols.
55    pub const DEFAULT: Self = Self(8);
56    /// The largest, 9: blocks of up to 32 767 symbols, as Pillow asks.
57    pub const MAX: Self = Self(9);
58
59    /// The memory level `level`, which must be between 1 and 9.
60    pub const fn new(level: u8) -> Result<Self, InvalidMemoryLevel> {
61        if matches!(level, 1..=9) {
62            Ok(Self(level))
63        } else {
64            Err(InvalidMemoryLevel(level))
65        }
66    }
67
68    /// The numeric level, 1–9.
69    pub const fn get(self) -> u8 {
70        self.0
71    }
72
73    /// Room for symbols in a block (zlib's `lit_bufsize`).
74    pub(crate) const fn symbol_buffer(self) -> usize {
75        1 << (self.0 + 6)
76    }
77}
78
79impl Default for MemoryLevel {
80    fn default() -> Self {
81        Self::DEFAULT
82    }
83}
84
85/// Error returned for a memory level outside 1 to 9.
86#[derive(Clone, Copy, Debug, PartialEq, Eq)]
87pub struct InvalidMemoryLevel(pub u8);
88
89impl fmt::Display for InvalidMemoryLevel {
90    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
91        write!(f, "invalid memory level {}; expected 1 to 9", self.0)
92    }
93}
94
95impl Error for InvalidMemoryLevel {}
96
97/// Everything that decides the compressed bytes of an input, as zlib's
98/// `deflateInit2` takes it (with a 32 KiB window).
99///
100/// ```
101/// use pltrs_codec::CompressionLevel;
102/// use pltrs_codec::deflate::{self, MemoryLevel, Options, Strategy};
103///
104/// let options = Options::new(CompressionLevel::BEST)
105///     .strategy(Strategy::Filtered)
106///     .memory_level(MemoryLevel::MAX);
107/// let packed = deflate::compress_with(b"abcabcabcabcabc", options)?;
108/// assert_eq!(deflate::decompress(&packed)?, b"abcabcabcabcabc");
109/// # Ok::<(), Box<dyn std::error::Error>>(())
110/// ```
111#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
112pub struct Options {
113    pub(crate) level: CompressionLevel,
114    pub(crate) strategy: Strategy,
115    pub(crate) memory_level: MemoryLevel,
116}
117
118impl Options {
119    /// The options zlib's `deflateInit` gives `level`: the default
120    /// strategy and memory level.
121    pub const fn new(level: CompressionLevel) -> Self {
122        Self {
123            level,
124            strategy: Strategy::Default,
125            memory_level: MemoryLevel::DEFAULT,
126        }
127    }
128
129    /// Sets the strategy.
130    #[must_use]
131    pub const fn strategy(mut self, strategy: Strategy) -> Self {
132        self.strategy = strategy;
133        self
134    }
135
136    /// Sets the memory level.
137    #[must_use]
138    pub const fn memory_level(mut self, memory_level: MemoryLevel) -> Self {
139        self.memory_level = memory_level;
140        self
141    }
142}
143
144/// The parsing a level compresses with (zlib-ng's `deflate_*` functions).
145#[derive(Clone, Copy, Debug, PartialEq, Eq)]
146pub(super) enum Method {
147    /// Stored blocks only (`deflate_stored`, level 0).
148    Stored,
149    /// One fixed-Huffman block, the first match taken (`deflate_quick`,
150    /// level 1).
151    Quick,
152    /// Greedy parsing (`deflate_fast`, level 2).
153    Fast,
154    /// Greedy parsing that looks one match ahead (`deflate_medium`, levels
155    /// 3–6).
156    Medium,
157    /// Lazy parsing (`deflate_slow`, levels 7–9).
158    Slow,
159}
160
161/// The match finder's tuning at a level (a row of `configuration_table`).
162#[derive(Clone, Copy, Debug, PartialEq, Eq)]
163pub(super) struct Config {
164    /// Once the previous match is this long, chains are searched a quarter
165    /// as far.
166    pub(super) good_length: u32,
167    /// Lazy parsing: no better match is looked for after one this long;
168    /// greedy: matches up to this long have all their strings hashed.
169    pub(super) max_lazy: u32,
170    /// The search stops at a match this long.
171    pub(super) nice_length: u32,
172    /// The most chain links followed per search.
173    pub(super) max_chain: u32,
174    /// The parsing.
175    pub(super) method: Method,
176}
177
178impl Config {
179    /// zlib-ng's `configuration_table` row for `level`.
180    pub(super) const fn of(level: CompressionLevel) -> Self {
181        let (good_length, max_lazy, nice_length, max_chain, method) = match level.get() {
182            0 => (0, 0, 0, 0, Method::Stored),
183            1 => (0, 0, 0, 0, Method::Quick),
184            2 => (4, 4, 8, 4, Method::Fast),
185            3 => (4, 6, 16, 6, Method::Medium),
186            4 => (4, 12, 32, 24, Method::Medium),
187            5 => (8, 16, 32, 32, Method::Medium),
188            6 => (8, 16, 128, 128, Method::Medium),
189            7 => (8, 32, 128, 256, Method::Slow),
190            8 => (32, 128, 258, 1024, Method::Slow),
191            _ => (32, 258, 258, 4096, Method::Slow),
192        };
193        Self {
194            good_length,
195            max_lazy,
196            nice_length,
197            max_chain,
198            method,
199        }
200    }
201
202    /// Whether the level hashes with zlib's rolling three-byte hash
203    /// rather than the multiplicative four-byte one: chains longer than
204    /// 1024 links, where the slow match finder looks other chains up.
205    pub(super) const fn rolls(self) -> bool {
206        self.max_chain > 1024
207    }
208}
209
210#[cfg(test)]
211mod tests {
212    use super::*;
213
214    #[test]
215    fn memory_levels_validate_range() {
216        for level in 1..=9 {
217            assert_eq!(MemoryLevel::new(level).map(MemoryLevel::get), Ok(level));
218        }
219        assert_eq!(MemoryLevel::new(10), Err(InvalidMemoryLevel(10)));
220        assert_eq!(
221            InvalidMemoryLevel(0).to_string(),
222            "invalid memory level 0; expected 1 to 9"
223        );
224        assert_eq!(MemoryLevel::DEFAULT.symbol_buffer(), 16_384);
225        assert_eq!(MemoryLevel::MAX.symbol_buffer(), 32_768);
226        assert_eq!(MemoryLevel::default(), MemoryLevel::DEFAULT);
227    }
228
229    #[test]
230    fn levels_select_zlib_ng_methods() {
231        let method = |level| Config::of(CompressionLevel::new(level).unwrap()).method;
232        assert_eq!(method(0), Method::Stored);
233        assert_eq!(method(1), Method::Quick);
234        assert_eq!(method(2), Method::Fast);
235        assert!((3..=6).all(|level| method(level) == Method::Medium));
236        assert!((7..=9).all(|level| method(level) == Method::Slow));
237        assert!(Config::of(CompressionLevel::BEST).rolls());
238        assert!(!Config::of(CompressionLevel::new(8).unwrap()).rolls());
239    }
240
241    #[test]
242    fn options_keep_what_they_are_given() {
243        let options = Options::new(CompressionLevel::FASTEST)
244            .strategy(Strategy::Rle)
245            .memory_level(MemoryLevel::MAX);
246        assert_eq!(options.level, CompressionLevel::FASTEST);
247        assert_eq!(options.strategy, Strategy::Rle);
248        assert_eq!(options.memory_level, MemoryLevel::MAX);
249        assert_eq!(Options::default(), Options::new(CompressionLevel::DEFAULT));
250        assert!(Strategy::Fixed.is_fastest_kind() && !Strategy::Filtered.is_fastest_kind());
251    }
252}