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 -7 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/// L3 and L4 keep denser searches through 256 KiB to preserve matches on short inputs.
84///
85/// Level 0 is treated as "library default" and maps to level 1.
86pub fn level_params_for_size(level: i32, src_len: usize) -> Option<LevelParams> {
87    let mut params = level_params_inner(level)?;
88    if let Some(search_strength) = short_input_search_strength(level, src_len) {
89        params.search_strength = search_strength;
90    }
91    params.hash_log = params.hash_log.clamp(HASH_LOG_MIN, HASH_LOG_MAX);
92    params.chain_log = params.chain_log.clamp(HASH_LOG_MIN, HASH_LOG_MAX);
93    params.window_log = params.window_log.clamp(WINDOW_LOG_MIN, WINDOW_LOG_MAX);
94    if (2..usize::MAX).contains(&src_len) {
95        let src_log = 32 - ((src_len as u32) - 1).leading_zeros();
96        params.hash_log = params.hash_log.min(src_log).max(HASH_LOG_MIN);
97        params.chain_log = params.chain_log.min(src_log).max(HASH_LOG_MIN);
98        params.window_log = params.window_log.min(src_log);
99    }
100    if raw_literals_limit(level).is_some_and(|max| src_len <= max) {
101        params.force_raw_literals = true;
102        if let Some((target_length, min_match, search_strength)) = small_input_search(level) {
103            params.target_length = target_length;
104            params.min_match = min_match;
105            params.search_strength = search_strength;
106        }
107    }
108    Some(params)
109}
110
111/// Returns the compression parameters for `input_len` bytes after a
112/// `prefix_len`-byte dictionary. The tables and window cover both, while the
113/// search density follows the input alone, as in a frame without a dictionary.
114pub(crate) fn level_params_with_prefix(
115    level: i32,
116    prefix_len: usize,
117    input_len: usize,
118) -> Option<LevelParams> {
119    let mut params = level_params_for_size(level, prefix_len.saturating_add(input_len))?;
120    if let Some(search_strength) = short_input_search_strength(level, input_len) {
121        params.search_strength = search_strength;
122    }
123    Some(params)
124}
125
126/// Search strength for inputs of up to two blocks at the levels that search
127/// sparsely on larger ones. Sparse initial tables cost too much ratio there.
128fn short_input_search_strength(level: i32, input_len: usize) -> Option<u32> {
129    if input_len > 256 * 1024 {
130        return None;
131    }
132    match level {
133        3 => Some(4),
134        4 => Some(6),
135        _ => None,
136    }
137}
138
139pub const HASH_LOG_MIN: u32 = 6;
140pub const HASH_LOG_MAX: u32 = 30;
141pub const WINDOW_LOG_MIN: u32 = 10;
142pub const WINDOW_LOG_MAX: u32 = 27;
143
144/// Largest input a negative level encodes with raw literals.
145///
146/// Building a Huffman table costs a few microseconds regardless of input
147/// size. For tiny messages that dominates the encode time, so the negative
148/// levels skip it: 2 KiB at L-1, growing 1.5x or 1.33x per level (the size
149/// doubles every two levels) to 12 KiB at L-6. `None` for L-7, which keeps
150/// literals raw at every size, and for levels that always try Huffman
151/// literals.
152pub(crate) fn raw_literals_limit(level: i32) -> Option<usize> {
153    if !(-6..=-1).contains(&level) {
154        return None;
155    }
156    let rank = (-level - 1) as usize;
157    let base = 2048usize << (rank / 2);
158    Some(if rank % 2 == 1 { base + base / 2 } else { base })
159}
160
161/// Match search for inputs that keep raw literals, as `(target_length,
162/// min_match, search_strength)`.
163///
164/// Without Huffman literals, matches are the only compression, so the
165/// negative levels search more densely on these inputs than on large ones.
166/// L-7 keeps its own search, which always runs on raw literals. L-4 shares
167/// its step with L-3 and L-2 but grows it faster through regions without
168/// matches.
169fn small_input_search(level: i32) -> Option<(u32, u32, u32)> {
170    Some(match level {
171        -6 => (4, 5, 6),
172        -5 => (3, 5, 6),
173        -4 => (2, 5, 6),
174        -3 | -2 => (2, 5, 7),
175        -1 => (1, 5, 7),
176        _ => return None,
177    })
178}
179
180/// Whether an input of `input_len` bytes keeps raw literals at these
181/// parameters.
182pub(crate) fn keeps_raw_literals(params: &LevelParams, _input_len: usize) -> bool {
183    params.force_raw_literals
184}
185
186/// Per-block encoding choices derived from the level parameters.
187#[derive(Clone, Copy, Debug)]
188pub(crate) struct BlockPolicy {
189    /// Try Huffman literals and custom sequence tables.
190    pub custom_tables: bool,
191    /// Literals whose sampled order-0 entropy exceeds this many bits per byte
192    /// (8.8 fixed point) stay raw. `u32::MAX` disables the check.
193    pub max_literal_entropy_fp8: u32,
194}
195
196/// Encoding choices for a block of an input of `input_len` bytes.
197///
198/// The fast negative levels skip Huffman coding for dense literals: on
199/// low-compressibility data it costs more time than it saves space. L-6 to
200/// L-1 keep literals above 6.25 bits per byte raw. Small inputs keep all
201/// literals raw (see `raw_literals_limit`), and L-7 keeps them raw always.
202pub(crate) fn block_policy(params: &LevelParams, input_len: usize) -> BlockPolicy {
203    let max_literal_entropy_fp8 = if params.strategy == Strategy::Fast && params.min_match >= 5 {
204        match params.target_length {
205            0 | 1 => u32::MAX,
206            _ => 6 * 256 + 64,
207        }
208    } else {
209        u32::MAX
210    };
211    BlockPolicy {
212        custom_tables: use_custom_sequence_tables(params, input_len),
213        max_literal_entropy_fp8,
214    }
215}
216
217fn use_custom_sequence_tables(params: &LevelParams, input_len: usize) -> bool {
218    // Raw-literal inputs also skip custom sequence tables.
219    !keeps_raw_literals(params, input_len)
220}
221
222/// Returns the maximum hash_log for a given level.
223/// Used by CompressContext to pre-allocate hash tables.
224pub fn max_hash_log(level: i32) -> Option<u32> {
225    let p = level_params_inner(level)?;
226    Some(p.hash_log.max(p.chain_log))
227}
228
229fn level_params_inner(level: i32) -> Option<LevelParams> {
230    Some(match level {
231        0 => return level_params_inner(DEFAULT_LEVEL),
232        // The fastest level, for LZ4's niche: raw literals, as in C zstd,
233        // and only matches of eight bytes or more (`min_match` 8 hashes and
234        // confirms eight bytes), so frames decode with few sequences and no
235        // Huffman tables. It steps 3 bytes and grows the step every 16 bytes
236        // without a match. L-8, a separate level before, runs as L-7.
237        -8 | -7 => LevelParams {
238            strategy: Strategy::Fast,
239            window_log: 19,
240            hash_log: 13,
241            chain_log: 13,
242            search_log: 0,
243            min_match: 8,
244            target_length: 2,
245            search_strength: 4,
246            force_raw_literals: true,
247            #[cfg(feature = "ldm")]
248            ldm_params: None,
249        },
250        // L-6 to L-4 hash 8 or 7 bytes. With Huffman literals, longer
251        // matches at shorter steps beat 6-byte matches at long steps on both
252        // ratio and speed, as fewer bytes are left to code as literals.
253        -6 => LevelParams {
254            strategy: Strategy::Fast,
255            window_log: 19,
256            hash_log: 13,
257            chain_log: 13,
258            search_log: 0,
259            min_match: 8,
260            target_length: 9,
261            search_strength: 5,
262            force_raw_literals: false,
263            #[cfg(feature = "ldm")]
264            ldm_params: None,
265        },
266        -5 => LevelParams {
267            strategy: Strategy::Fast,
268            window_log: 19,
269            hash_log: 13,
270            chain_log: 13,
271            search_log: 0,
272            min_match: 8,
273            target_length: 5,
274            search_strength: 6,
275            force_raw_literals: false,
276            #[cfg(feature = "ldm")]
277            ldm_params: None,
278        },
279        -4 => LevelParams {
280            strategy: Strategy::Fast,
281            window_log: 19,
282            hash_log: 13,
283            chain_log: 13,
284            search_log: 0,
285            min_match: 7,
286            target_length: 4,
287            search_strength: 5,
288            force_raw_literals: false,
289            #[cfg(feature = "ldm")]
290            ldm_params: None,
291        },
292        // L-3 through L-1 grow the step every 32 bytes without a match.
293        // Long literal runs need fewer probes, while frequent matches keep
294        // the initial step and most of the compression ratio.
295        -3 => 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: 4,
303            search_strength: 5,
304            force_raw_literals: false,
305            #[cfg(feature = "ldm")]
306            ldm_params: None,
307        },
308        -2 => 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: 3,
316            search_strength: 5,
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: 14,
325            chain_log: 14,
326            search_log: 0,
327            min_match: 6,
328            target_length: 2,
329            search_strength: 5,
330            force_raw_literals: false,
331            #[cfg(feature = "ldm")]
332            ldm_params: None,
333        },
334        // L1 and L2 hash seven bytes to favor longer matches and grow the
335        // step every 16 bytes without a match. Dense matches keep the
336        // initial step, while long literal runs need fewer probes.
337        1 => LevelParams {
338            strategy: Strategy::Fast,
339            window_log: 19,
340            hash_log: 15,
341            chain_log: 15,
342            search_log: 0,
343            min_match: 7,
344            target_length: 1,
345            search_strength: 4,
346            force_raw_literals: false,
347            #[cfg(feature = "ldm")]
348            ldm_params: None,
349        },
350        2 => LevelParams {
351            strategy: Strategy::Fast,
352            window_log: 20,
353            hash_log: 16,
354            chain_log: 16,
355            search_log: 0,
356            min_match: 7,
357            target_length: 1,
358            search_strength: 4,
359            force_raw_literals: false,
360            #[cfg(feature = "ldm")]
361            ldm_params: None,
362        },
363        // C zstd's level 3 tables. On large inputs, grow the step after each
364        // unsuccessful probe so long literal runs do not dominate the search.
365        3 => LevelParams {
366            strategy: Strategy::DFast,
367            window_log: 21,
368            hash_log: 17,
369            chain_log: 16,
370            search_log: 1,
371            min_match: 5,
372            target_length: 1,
373            search_strength: 0,
374            force_raw_literals: false,
375            #[cfg(feature = "ldm")]
376            ldm_params: None,
377        },
378        // C zstd's level 4 tables, with a 16 MiB window and faster skip
379        // growth on large inputs.
380        4 => LevelParams {
381            strategy: Strategy::DFast,
382            window_log: 24,
383            hash_log: 18,
384            chain_log: 18,
385            search_log: 0,
386            min_match: 5,
387            target_length: 1,
388            search_strength: 3,
389            force_raw_literals: false,
390            #[cfg(feature = "ldm")]
391            ldm_params: None,
392        },
393        _ => return None,
394    })
395}
396
397/// Options for large-window and LDM compression, orthogonal to level.
398///
399/// Pass to [`compress_opts`](crate::compress_opts) or
400/// [`FrameEncoder::with_options`](crate::streaming::FrameEncoder::with_options).
401#[derive(Debug, Clone, Default)]
402pub struct Options {
403    pub(crate) window_log: Option<u32>,
404    #[cfg_attr(not(feature = "ldm"), allow(dead_code))]
405    pub(crate) ldm: bool,
406}
407
408impl Options {
409    #[must_use]
410    pub fn window_log(mut self, log: u32) -> Self {
411        self.window_log = Some(log);
412        self
413    }
414
415    #[cfg(feature = "ldm")]
416    #[must_use]
417    pub fn ldm(mut self, enable: bool) -> Self {
418        self.ldm = enable;
419        self
420    }
421}
422
423pub fn apply_options(params: &mut LevelParams, opts: &Options) {
424    if let Some(wl) = opts.window_log {
425        params.window_log = wl.clamp(WINDOW_LOG_MIN, WINDOW_LOG_MAX);
426    }
427    #[cfg(feature = "ldm")]
428    if opts.ldm {
429        params.ldm_params = Some(LdmParams::default_for_window_log(params.window_log));
430    }
431}