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