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