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