Skip to main content

zrip_encode/
strategy.rs

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