Skip to main content

zrip_encode/
strategy.rs

1#![forbid(unsafe_code)]
2
3/// Match-finding strategy.
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub enum Strategy {
6    /// Single hash table (levels -8 through 2).
7    Fast,
8    /// Short + long hash tables (levels 3-4).
9    DFast,
10}
11
12/// Parameters for Long Distance Matching.
13#[derive(Debug, Clone, Copy)]
14pub struct LdmParams {
15    pub hash_log: u32,
16    pub bucket_size_log: u32,
17    pub min_match_length: u32,
18    pub hash_rate_log: u32,
19}
20
21impl LdmParams {
22    pub fn default_for_window_log(window_log: u32) -> Self {
23        let hash_log = 20u32.min(window_log.saturating_sub(1));
24        let hash_rate_log = window_log.saturating_sub(hash_log).max(7);
25        Self {
26            hash_log,
27            bucket_size_log: 4,
28            min_match_length: 64,
29            hash_rate_log,
30        }
31    }
32}
33
34/// Compression parameters for a specific level.
35///
36/// Obtain via [`level_params`] or construct directly for custom tuning.
37/// Pass to [`compress_with_params`](crate::compress_with_params).
38#[derive(Debug, Clone, Copy)]
39pub struct LevelParams {
40    pub strategy: Strategy,
41    pub window_log: u32,
42    pub hash_log: u32,
43    /// DFast short table log. Same as hashLog for Fast strategy.
44    pub chain_log: u32,
45    pub search_log: u32,
46    pub min_match: u32,
47    pub target_length: u32,
48    pub search_strength: u32,
49    pub force_raw_literals: bool,
50    #[cfg(feature = "ldm")]
51    pub ldm_params: Option<LdmParams>,
52}
53
54impl LevelParams {
55    #[must_use]
56    pub fn with_window_log(mut self, window_log: u32) -> Self {
57        self.window_log = window_log;
58        self
59    }
60
61    #[cfg(feature = "ldm")]
62    #[must_use]
63    pub fn with_ldm(mut self, params: LdmParams) -> Self {
64        self.ldm_params = Some(params);
65        self
66    }
67}
68
69/// Default compression level used when level 0 is requested.
70pub const DEFAULT_LEVEL: i32 = 1;
71
72/// Returns the compression parameters for a given level, or `None` if out of range.
73///
74/// Level 0 is treated as "library default" and maps to level 1.
75/// Uses the large-input (>256 KB) parameter tier.
76pub fn level_params(level: i32) -> Option<LevelParams> {
77    level_params_for_size(level, usize::MAX)
78}
79
80/// Returns the compression parameters for a given level, sized for `src_len`.
81///
82/// Uses fixed parameters per level with log values clamped down for small inputs.
83///
84/// Level 0 is treated as "library default" and maps to level 1.
85pub fn level_params_for_size(level: i32, src_len: usize) -> Option<LevelParams> {
86    let mut params = level_params_inner(level)?;
87    params.hash_log = params.hash_log.clamp(HASH_LOG_MIN, HASH_LOG_MAX);
88    params.chain_log = params.chain_log.clamp(HASH_LOG_MIN, HASH_LOG_MAX);
89    params.window_log = params.window_log.clamp(WINDOW_LOG_MIN, WINDOW_LOG_MAX);
90    if (2..usize::MAX).contains(&src_len) {
91        let src_log = 32 - ((src_len as u32) - 1).leading_zeros();
92        params.hash_log = params.hash_log.min(src_log).max(HASH_LOG_MIN);
93        params.chain_log = params.chain_log.min(src_log).max(HASH_LOG_MIN);
94        params.window_log = params.window_log.min(src_log);
95    }
96    if raw_literals_limit(level).is_some_and(|max| src_len <= max) {
97        params.force_raw_literals = true;
98        if let Some((target_length, min_match, search_strength)) = small_input_search(level) {
99            params.target_length = target_length;
100            params.min_match = min_match;
101            params.search_strength = search_strength;
102        }
103    }
104    if level == 3 && (32 * 1024..=128 * 1024).contains(&src_len) {
105        params.search_strength = 7;
106    }
107    Some(params)
108}
109
110pub const HASH_LOG_MIN: u32 = 6;
111pub const HASH_LOG_MAX: u32 = 30;
112pub const WINDOW_LOG_MIN: u32 = 10;
113pub const WINDOW_LOG_MAX: u32 = 27;
114
115/// Largest input a negative level encodes with raw literals.
116///
117/// Building a Huffman table costs a few microseconds regardless of input
118/// size. For tiny messages that dominates the encode time, so the negative
119/// levels skip it: 2 KiB at L-1, growing 1.5x or 1.33x per level (the size
120/// doubles every two levels) to 24 KiB at L-8. `None` for levels that always
121/// try Huffman literals.
122pub(crate) fn raw_literals_limit(level: i32) -> Option<usize> {
123    if !(-8..=-1).contains(&level) {
124        return None;
125    }
126    let rank = (-level - 1) as usize;
127    let base = 2048usize << (rank / 2);
128    Some(if rank % 2 == 1 { base + base / 2 } else { base })
129}
130
131/// Match search for inputs that keep raw literals, as `(target_length,
132/// min_match, search_strength)`.
133///
134/// Without Huffman literals, matches are the only compression, so the
135/// negative levels search more densely on these inputs than on large ones.
136/// L-8 is a slightly sparser L-7. L-4 shares its step with L-3 and L-2 but
137/// grows it faster through regions without matches.
138fn small_input_search(level: i32) -> Option<(u32, u32, u32)> {
139    Some(match level {
140        -8 => (8, 5, 5),
141        -7 => (5, 5, 6),
142        -6 => (4, 5, 6),
143        -5 => (3, 5, 6),
144        -4 => (2, 5, 6),
145        -3 | -2 => (2, 5, 7),
146        -1 => (1, 5, 7),
147        _ => return None,
148    })
149}
150
151/// Whether an input of `input_len` bytes keeps raw literals at these
152/// parameters.
153pub(crate) fn keeps_raw_literals(params: &LevelParams, _input_len: usize) -> bool {
154    params.force_raw_literals
155}
156
157/// Per-block encoding choices derived from the level parameters.
158#[derive(Clone, Copy, Debug)]
159pub(crate) struct BlockPolicy {
160    /// Try Huffman literals and custom sequence tables.
161    pub custom_tables: bool,
162    /// Literals whose sampled order-0 entropy exceeds this many bits per byte
163    /// (8.8 fixed point) stay raw. `u32::MAX` disables the check.
164    pub max_literal_entropy_fp8: u32,
165}
166
167/// Encoding choices for a block of an input of `input_len` bytes.
168///
169/// The fast negative levels skip Huffman coding for dense literals: on
170/// low-compressibility data it costs more time than it saves space. L-8 to
171/// L-1 keep literals above 6.25 bits per byte raw. Small inputs keep all
172/// literals raw (see `raw_literals_limit`).
173pub(crate) fn block_policy(params: &LevelParams, input_len: usize) -> BlockPolicy {
174    let max_literal_entropy_fp8 = if params.strategy == Strategy::Fast && params.min_match >= 5 {
175        match params.target_length {
176            0 | 1 => u32::MAX,
177            _ => 6 * 256 + 64,
178        }
179    } else {
180        u32::MAX
181    };
182    BlockPolicy {
183        custom_tables: use_custom_sequence_tables(params, input_len),
184        max_literal_entropy_fp8,
185    }
186}
187
188fn use_custom_sequence_tables(params: &LevelParams, input_len: usize) -> bool {
189    // Raw-literal inputs also skip custom sequence tables.
190    if keeps_raw_literals(params, input_len) {
191        return false;
192    }
193
194    if (32768..=zrip_core::frame::MAX_BLOCK_SIZE).contains(&input_len)
195        && params.strategy == Strategy::DFast
196        && params.min_match == 4
197        && params.target_length == 1
198        && params.search_strength < 5
199    {
200        return false;
201    }
202    true
203}
204
205/// Returns the maximum hash_log for a given level.
206/// Used by CompressContext to pre-allocate hash tables.
207pub fn max_hash_log(level: i32) -> Option<u32> {
208    let p = level_params_inner(level)?;
209    Some(p.hash_log.max(p.chain_log))
210}
211
212fn level_params_inner(level: i32) -> Option<LevelParams> {
213    Some(match level {
214        0 => return level_params_inner(DEFAULT_LEVEL),
215        // zrip's own level: L-7 with a larger step and faster acceleration
216        // through regions without matches.
217        -8 => LevelParams {
218            strategy: Strategy::Fast,
219            window_log: 19,
220            hash_log: 13,
221            chain_log: 13,
222            search_log: 0,
223            min_match: 6,
224            target_length: 21,
225            search_strength: 5,
226            force_raw_literals: false,
227            #[cfg(feature = "ldm")]
228            ldm_params: None,
229        },
230        -7 => LevelParams {
231            strategy: Strategy::Fast,
232            window_log: 19,
233            hash_log: 13,
234            chain_log: 13,
235            search_log: 0,
236            min_match: 6,
237            target_length: 17,
238            search_strength: 7,
239            force_raw_literals: false,
240            #[cfg(feature = "ldm")]
241            ldm_params: None,
242        },
243        -6 => LevelParams {
244            strategy: Strategy::Fast,
245            window_log: 19,
246            hash_log: 13,
247            chain_log: 13,
248            search_log: 0,
249            min_match: 6,
250            target_length: 13,
251            search_strength: 7,
252            force_raw_literals: false,
253            #[cfg(feature = "ldm")]
254            ldm_params: None,
255        },
256        -5 => LevelParams {
257            strategy: Strategy::Fast,
258            window_log: 19,
259            hash_log: 13,
260            chain_log: 13,
261            search_log: 0,
262            min_match: 6,
263            target_length: 9,
264            search_strength: 7,
265            force_raw_literals: false,
266            #[cfg(feature = "ldm")]
267            ldm_params: None,
268        },
269        -4 => LevelParams {
270            strategy: Strategy::Fast,
271            window_log: 19,
272            hash_log: 13,
273            chain_log: 13,
274            search_log: 0,
275            min_match: 6,
276            target_length: 5,
277            search_strength: 7,
278            force_raw_literals: false,
279            #[cfg(feature = "ldm")]
280            ldm_params: None,
281        },
282        -3 => LevelParams {
283            strategy: Strategy::Fast,
284            window_log: 19,
285            hash_log: 14,
286            chain_log: 14,
287            search_log: 0,
288            min_match: 6,
289            target_length: 4,
290            search_strength: 7,
291            force_raw_literals: false,
292            #[cfg(feature = "ldm")]
293            ldm_params: None,
294        },
295        -2 => LevelParams {
296            strategy: Strategy::Fast,
297            window_log: 19,
298            hash_log: 14,
299            chain_log: 14,
300            search_log: 0,
301            min_match: 6,
302            target_length: 3,
303            search_strength: 7,
304            force_raw_literals: false,
305            #[cfg(feature = "ldm")]
306            ldm_params: None,
307        },
308        -1 => LevelParams {
309            strategy: Strategy::Fast,
310            window_log: 19,
311            hash_log: 14,
312            chain_log: 14,
313            search_log: 0,
314            min_match: 6,
315            target_length: 2,
316            search_strength: 7,
317            force_raw_literals: false,
318            #[cfg(feature = "ldm")]
319            ldm_params: None,
320        },
321        1 => LevelParams {
322            strategy: Strategy::Fast,
323            window_log: 19,
324            hash_log: 15,
325            chain_log: 15,
326            search_log: 0,
327            min_match: 6,
328            target_length: 1,
329            search_strength: 7,
330            force_raw_literals: false,
331            #[cfg(feature = "ldm")]
332            ldm_params: None,
333        },
334        2 => LevelParams {
335            strategy: Strategy::Fast,
336            window_log: 20,
337            hash_log: 16,
338            chain_log: 16,
339            search_log: 0,
340            min_match: 6,
341            target_length: 1,
342            search_strength: 7,
343            force_raw_literals: false,
344            #[cfg(feature = "ldm")]
345            ldm_params: None,
346        },
347        3 => LevelParams {
348            strategy: Strategy::DFast,
349            window_log: 21,
350            hash_log: 18,
351            chain_log: 18,
352            search_log: 1,
353            min_match: 4,
354            target_length: 1,
355            search_strength: 5,
356            force_raw_literals: false,
357            #[cfg(feature = "ldm")]
358            ldm_params: None,
359        },
360        4 => LevelParams {
361            strategy: Strategy::DFast,
362            window_log: 24,
363            hash_log: 20,
364            chain_log: 20,
365            search_log: 0,
366            min_match: 4,
367            target_length: 1,
368            search_strength: 8,
369            force_raw_literals: false,
370            #[cfg(feature = "ldm")]
371            ldm_params: None,
372        },
373        _ => return None,
374    })
375}
376
377/// Options for large-window and LDM compression, orthogonal to level.
378///
379/// Pass to [`compress_opts`](crate::compress_opts) or
380/// [`FrameEncoder::with_options`](crate::streaming::FrameEncoder::with_options).
381#[derive(Debug, Clone, Default)]
382pub struct Options {
383    pub(crate) window_log: Option<u32>,
384    #[cfg_attr(not(feature = "ldm"), allow(dead_code))]
385    pub(crate) ldm: bool,
386}
387
388impl Options {
389    #[must_use]
390    pub fn window_log(mut self, log: u32) -> Self {
391        self.window_log = Some(log);
392        self
393    }
394
395    #[cfg(feature = "ldm")]
396    #[must_use]
397    pub fn ldm(mut self, enable: bool) -> Self {
398        self.ldm = enable;
399        self
400    }
401}
402
403pub fn apply_options(params: &mut LevelParams, opts: &Options) {
404    if let Some(wl) = opts.window_log {
405        params.window_log = wl.clamp(WINDOW_LOG_MIN, WINDOW_LOG_MAX);
406    }
407    #[cfg(feature = "ldm")]
408    if opts.ldm {
409        params.ldm_params = Some(LdmParams::default_for_window_log(params.window_log));
410    }
411}