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}