1#![cfg_attr(not(feature = "std"), no_std)]
2#![cfg_attr(feature = "nightly", feature(optimize_attribute))]
3#![forbid(unsafe_code)]
4
5#[cfg(feature = "alloc")]
6extern crate alloc;
7
8#[cfg(all(feature = "simd", target_arch = "x86_64", not(target_feature = "avx2")))]
16macro_rules! simd_body {
17 ($body:expr) => {
18 match fearless_simd::Level::new().as_avx2() {
19 Some(avx2) => fearless_simd::Simd::vectorize(
20 avx2,
21 #[inline(always)]
22 || $body,
23 ),
24 None => $body,
25 }
26 };
27}
28
29#[cfg(not(all(feature = "simd", target_arch = "x86_64", not(target_feature = "avx2"))))]
30macro_rules! simd_body {
31 ($body:expr) => {
32 $body
33 };
34}
35
36pub mod adaptive;
37pub(crate) mod block_encoder;
38#[cfg(feature = "alloc")]
39pub mod context;
40pub(crate) mod dfast;
41pub(crate) mod fast;
42#[cfg(feature = "ldm")]
43pub(crate) mod ldm;
44mod output;
45pub(crate) mod primitives;
46pub(crate) mod rebase;
47pub mod strategy;
48#[cfg(feature = "std")]
49pub mod streaming;
50
51#[cfg(feature = "alloc")]
52use alloc::vec;
53#[cfg(feature = "alloc")]
54use alloc::vec::Vec;
55
56use crate::output::{OutputSink, SliceSink};
57use crate::rebase::PositionBase;
58use crate::strategy::Strategy;
59use zrip_core::error::CompressError;
60use zrip_core::frame::{MAX_BLOCK_SIZE, MAX_WINDOW_SIZE, ZSTD_MAGIC};
61use zrip_core::xxhash::xxh64;
62
63pub(crate) fn write_frame_header(
64 output: &mut impl OutputSink,
65 content_size: usize,
66 dict_id: Option<u32>,
67 window_log: u32,
68) -> Result<(), CompressError> {
69 write_frame_header_inner(output, Some(content_size), dict_id, window_log, true)
70}
71
72#[cfg_attr(not(feature = "std"), allow(dead_code))]
73pub(crate) fn write_frame_header_with_checksum(
74 output: &mut impl OutputSink,
75 content_size: usize,
76 dict_id: Option<u32>,
77 window_log: u32,
78 content_checksum: bool,
79) -> Result<(), CompressError> {
80 write_frame_header_inner(
81 output,
82 Some(content_size),
83 dict_id,
84 window_log,
85 content_checksum,
86 )
87}
88
89#[cfg_attr(not(feature = "std"), allow(dead_code))]
90pub(crate) fn write_frame_header_without_content_size(
91 output: &mut impl OutputSink,
92 dict_id: Option<u32>,
93 window_log: u32,
94) -> Result<(), CompressError> {
95 write_frame_header_inner(output, None, dict_id, window_log, true)
96}
97
98fn write_frame_header_inner(
99 output: &mut impl OutputSink,
100 content_size: Option<usize>,
101 dict_id: Option<u32>,
102 window_log: u32,
103 content_checksum: bool,
104) -> Result<(), CompressError> {
105 output.extend_from_slice(&ZSTD_MAGIC.to_le_bytes())?;
106
107 let single_segment = dict_id.is_none() && content_size.is_some_and(fits_single_segment);
108 let fcs_size = content_size.map_or(0, |size| {
109 frame_content_size_field_size(size, single_segment)
110 });
111 let fcs_flag: u8 = match fcs_size {
112 0 => 0,
113 1 => 0,
114 2 => 1,
115 4 => 2,
116 _ => 3,
117 };
118
119 let dict_id_flag: u8 = match dict_id {
120 None => 0,
121 Some(id) if id <= 0xFF => 1,
122 Some(id) if id <= 0xFFFF => 2,
123 Some(_) => 3,
124 };
125
126 let descriptor = if single_segment { 0x20 } else { 0 }
127 | if content_checksum { 0x04 } else { 0 }
128 | (fcs_flag << 6)
129 | dict_id_flag;
130 output.push(descriptor)?;
131
132 if !single_segment {
133 output.push(window_descriptor_for_log(window_log))?;
134 }
135
136 match dict_id {
137 Some(id) if id <= 0xFF => output.push(id as u8)?,
138 Some(id) if id <= 0xFFFF => output.extend_from_slice(&(id as u16).to_le_bytes())?,
139 Some(id) => output.extend_from_slice(&id.to_le_bytes())?,
140 None => {}
141 }
142
143 let Some(content_size) = content_size else {
144 return Ok(());
145 };
146 match fcs_size {
147 0 => {}
148 1 => output.push(content_size as u8)?,
149 2 => {
150 let v = (content_size - 256) as u16;
151 output.extend_from_slice(&v.to_le_bytes())?;
152 }
153 4 => output.extend_from_slice(&(content_size as u32).to_le_bytes())?,
154 _ => output.extend_from_slice(&(content_size as u64).to_le_bytes())?,
155 }
156 Ok(())
157}
158
159fn fits_single_segment(content_size: usize) -> bool {
162 content_size as u64 <= MAX_WINDOW_SIZE
163}
164
165fn frame_window_size(content_size: usize, window_log: u32) -> usize {
167 if fits_single_segment(content_size) {
168 content_size
169 } else {
170 1usize << window_log
171 }
172}
173
174fn frame_content_size_field_size(content_size: usize, single_segment: bool) -> usize {
175 if single_segment && content_size <= 255 {
176 1
177 } else if (256..=0xFFFF + 256).contains(&content_size) {
178 2
179 } else if content_size <= 0xFFFF_FFFF {
180 4
181 } else {
182 8
183 }
184}
185
186fn window_descriptor_for_log(window_log: u32) -> u8 {
187 let window_log = window_log.clamp(strategy::WINDOW_LOG_MIN, strategy::WINDOW_LOG_MAX);
188 ((window_log - 10) as u8) << 3
189}
190
191pub(crate) fn skip_match_search(
197 params: &strategy::LevelParams,
198 input_len: usize,
199 data: &[u8],
200) -> bool {
201 !strategy::keeps_raw_literals(params, input_len) && block_looks_incompressible(data)
202}
203
204fn block_looks_incompressible(data: &[u8]) -> bool {
211 const WINDOWS: usize = 8;
212 const WINDOW: usize = 512;
213 if data.len() < WINDOWS * WINDOW {
214 return false;
215 }
216 let mut counts = [[0u16; 256]; 4];
219 let bound = ((WINDOWS * WINDOW) >> 7) + 4;
220 let largest = |counts: &[[u16; 256]; 4]| {
221 (0..256)
222 .map(|i| usize::from(counts[0][i] + counts[1][i] + counts[2][i] + counts[3][i]))
223 .max()
224 .unwrap()
225 };
226 for w in 0..WINDOWS {
227 let start = data.len() * w / WINDOWS;
228 let (chunks, _) = data[start..start + WINDOW].as_chunks::<4>();
229 for c in chunks {
230 counts[0][c[0] as usize] += 1;
231 counts[1][c[1] as usize] += 1;
232 counts[2][c[2] as usize] += 1;
233 counts[3][c[3] as usize] += 1;
234 }
235 if largest(&counts) > bound {
237 return false;
238 }
239 }
240 true
241}
242
243pub(crate) fn clamp_params_to_src_size(params: &mut strategy::LevelParams, src_len: usize) {
244 params.hash_log = params
245 .hash_log
246 .clamp(strategy::HASH_LOG_MIN, strategy::HASH_LOG_MAX);
247 params.chain_log = params
248 .chain_log
249 .clamp(strategy::HASH_LOG_MIN, strategy::HASH_LOG_MAX);
250 params.window_log = params
251 .window_log
252 .clamp(strategy::WINDOW_LOG_MIN, strategy::WINDOW_LOG_MAX);
253 if src_len >= 2 {
254 let src_log = strategy::src_log(src_len);
255 params.hash_log = params.hash_log.min(src_log).max(strategy::HASH_LOG_MIN);
256 params.chain_log = params.chain_log.min(src_log).max(strategy::HASH_LOG_MIN);
257 params.window_log = params.window_log.min(src_log);
258 }
259}
260
261pub fn compress_with_params(
262 input: &[u8],
263 params: &strategy::LevelParams,
264) -> Result<Vec<u8>, CompressError> {
265 let mut params = *params;
266 clamp_params_to_src_size(&mut params, input.len());
267 compress_inner(input, ¶ms)
268}
269
270pub fn compress(input: &[u8], level: i32) -> Result<Vec<u8>, CompressError> {
271 let params = strategy::level_params_for_size(level, input.len())
272 .ok_or(CompressError::InvalidLevel(level))?;
273 compress_inner(input, ¶ms)
274}
275
276pub fn compress_opts(
277 input: &[u8],
278 level: i32,
279 opts: &strategy::Options,
280) -> Result<Vec<u8>, CompressError> {
281 let params = params_with_options(level, input.len(), opts)?;
282 compress_inner(input, ¶ms)
283}
284
285fn params_with_options(
287 level: i32,
288 input_len: usize,
289 opts: &strategy::Options,
290) -> Result<strategy::LevelParams, CompressError> {
291 let mut params = strategy::level_params_for_size(level, input_len)
292 .ok_or(CompressError::InvalidLevel(level))?;
293 strategy::apply_options(&mut params, opts);
294 clamp_params_to_src_size(&mut params, input_len);
295 #[cfg(feature = "ldm")]
298 if opts.ldm {
299 let window_log = params.window_log.max(strategy::WINDOW_LOG_MIN);
300 let ldm = strategy::LdmParams::default_for_window_log(window_log);
301 params.ldm_params = (input_len >= ldm.min_match_length as usize).then_some(ldm);
302 }
303 Ok(params)
304}
305
306#[allow(clippy::unnecessary_wraps)]
307fn compress_inner(input: &[u8], params: &strategy::LevelParams) -> Result<Vec<u8>, CompressError> {
308 let mut output = Vec::with_capacity(input.len() + 32);
309 compress_frame(input, params, &mut output)?;
310 Ok(output)
311}
312
313fn compress_frame(
314 input: &[u8],
315 params: &strategy::LevelParams,
316 output: &mut impl OutputSink,
317) -> Result<(), CompressError> {
318 write_frame_header(output, input.len(), None, params.window_log)?;
319
320 if input.is_empty() {
321 block_encoder::encode_raw_block(&[], true, output)?;
322 } else {
323 let mut rep_offsets = [1u32, 4, 8];
324 let mut offset = 0;
325 let mut sequences = Vec::with_capacity(MAX_BLOCK_SIZE / 8);
326 let mut workspace = block_encoder::BlockEncodeWorkspace::new();
327
328 #[cfg(feature = "ldm")]
329 let mut ldm_state = params.ldm_params.as_ref().map(ldm::LdmState::new);
330 let window_size = frame_window_size(input.len(), params.window_log);
331 let block_size = MAX_BLOCK_SIZE.min(window_size);
332 let mut positions = PositionBase::new(params.window_log);
333
334 match params.strategy {
335 Strategy::Fast => {
336 let hash_size = 1usize << params.hash_log;
337 let mut hash_table = vec![0u32; hash_size];
338 while offset < input.len() {
339 let chunk_size = (input.len() - offset).min(block_size);
340 let block_end = offset + chunk_size;
341 let is_last = block_end >= input.len();
342 let block = &input[offset..block_end];
343
344 if let Some(shift) = positions.advance(offset, block_end) {
345 rebase::reduce_hash_table(&mut hash_table, shift);
346 #[cfg(feature = "ldm")]
347 if let Some(ref mut ldm) = ldm_state {
348 ldm.reduce_positions(shift);
349 }
350 }
351 let base = positions.base();
352 let src = &input[base..];
353 let (start, end) = (offset - base, block_end - base);
354
355 if skip_match_search(params, input.len(), block) {
356 block_encoder::encode_raw_block(block, is_last, output)?;
357 } else {
358 #[cfg(feature = "ldm")]
359 let used_ldm = if let Some(ref mut ldm) = ldm_state {
360 let mut empty = Vec::new();
361 ldm.compress_block(
362 src,
363 start,
364 end,
365 window_size,
366 params,
367 &rep_offsets,
368 &mut hash_table,
369 &mut empty,
370 &mut sequences,
371 );
372 true
373 } else {
374 false
375 };
376 #[cfg(not(feature = "ldm"))]
377 let used_ldm = false;
378
379 if !used_ldm {
380 fast::compress_fast_block(
381 src,
382 start,
383 end,
384 params,
385 &rep_offsets,
386 &mut hash_table,
387 &mut sequences,
388 );
389 }
390 if params.force_raw_literals {
391 block_encoder::encode_compressed_block_raw(
392 block,
393 &sequences,
394 &mut rep_offsets,
395 is_last,
396 output,
397 &mut workspace,
398 )?;
399 } else {
400 block_encoder::encode_compressed_block(
401 block,
402 &sequences,
403 &mut rep_offsets,
404 is_last,
405 output,
406 &mut workspace,
407 strategy::block_policy(params, input.len()),
408 )?;
409 }
410 }
411 offset = block_end;
412 }
413 }
414 Strategy::DFast => {
415 let short_size = 1usize << params.chain_log;
416 let long_size = 1usize << params.hash_log;
417 let mut hash_short = vec![0u32; short_size];
418 let mut hash_long = vec![0u32; long_size];
419 while offset < input.len() {
420 let chunk_size = (input.len() - offset).min(block_size);
421 let block_end = offset + chunk_size;
422 let is_last = block_end >= input.len();
423 let block = &input[offset..block_end];
424
425 if let Some(shift) = positions.advance(offset, block_end) {
426 rebase::reduce_hash_table(&mut hash_short, shift);
427 rebase::reduce_hash_table(&mut hash_long, shift);
428 #[cfg(feature = "ldm")]
429 if let Some(ref mut ldm) = ldm_state {
430 ldm.reduce_positions(shift);
431 }
432 }
433 let base = positions.base();
434 let src = &input[base..];
435 let (start, end) = (offset - base, block_end - base);
436
437 if skip_match_search(params, input.len(), block) {
438 block_encoder::encode_raw_block(block, is_last, output)?;
439 } else {
440 #[cfg(feature = "ldm")]
441 let used_ldm = if let Some(ref mut ldm) = ldm_state {
442 ldm.compress_block(
443 src,
444 start,
445 end,
446 window_size,
447 params,
448 &rep_offsets,
449 &mut hash_short,
450 &mut hash_long,
451 &mut sequences,
452 );
453 true
454 } else {
455 false
456 };
457 #[cfg(not(feature = "ldm"))]
458 let used_ldm = false;
459
460 if !used_ldm {
461 dfast::compress_dfast_block(
462 src,
463 start,
464 end,
465 params,
466 &rep_offsets,
467 &mut hash_short,
468 &mut hash_long,
469 &mut sequences,
470 );
471 }
472 block_encoder::encode_compressed_block(
473 block,
474 &sequences,
475 &mut rep_offsets,
476 is_last,
477 output,
478 &mut workspace,
479 strategy::block_policy(params, input.len()),
480 )?;
481 }
482 offset = block_end;
483 }
484 }
485 }
486 }
487
488 let hash = xxh64(input, 0);
489 let checksum = (hash & 0xFFFF_FFFF) as u32;
490 output.extend_from_slice(&checksum.to_le_bytes())?;
491 Ok(())
492}
493
494pub fn compress_with_dict(
495 input: &[u8],
496 level: i32,
497 dict: &zrip_core::dict::Dictionary,
498) -> Result<Vec<u8>, CompressError> {
499 let params = strategy::level_params_with_prefix(level, dict.content().len(), input.len())
500 .ok_or(CompressError::InvalidLevel(level))?;
501
502 let mut output = Vec::with_capacity(input.len() + 32);
503 write_frame_header(&mut output, input.len(), Some(dict.id()), params.window_log)?;
504
505 if input.is_empty() {
506 block_encoder::encode_raw_block(&[], true, &mut output)?;
507 } else {
508 let prefix = dict.content();
509 let mut rep_offsets = *dict.rep_offsets();
510 let mut workspace = block_encoder::BlockEncodeWorkspace::new();
511
512 workspace.prev_ll = dict
513 .ll_table()
514 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 35));
515 workspace.prev_of = dict
516 .of_table()
517 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 31));
518 workspace.prev_ml = dict
519 .ml_table()
520 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 52));
521 workspace.prev_huffman = dict.huf_table().and_then(|(dt, tl)| {
522 zrip_core::huffman::encode::HuffmanEncodeTable::from_decode_table(dt, tl)
523 });
524
525 if input.len() <= MAX_BLOCK_SIZE {
526 let sequences = match params.strategy {
527 Strategy::Fast => {
528 fast::compress_fast_with_prefix(input, ¶ms, &rep_offsets, prefix)
529 }
530 Strategy::DFast => {
531 dfast::compress_dfast_with_prefix(input, ¶ms, &rep_offsets, prefix)
532 }
533 };
534 if params.force_raw_literals {
535 block_encoder::encode_compressed_block_raw(
536 input,
537 &sequences,
538 &mut rep_offsets,
539 true,
540 &mut output,
541 &mut workspace,
542 )?;
543 } else {
544 block_encoder::encode_compressed_block(
545 input,
546 &sequences,
547 &mut rep_offsets,
548 true,
549 &mut output,
550 &mut workspace,
551 strategy::block_policy(¶ms, input.len()),
552 )?;
553 }
554 } else {
555 let mut combined = Vec::with_capacity(prefix.len() + input.len());
556 combined.extend_from_slice(prefix);
557 combined.extend_from_slice(input);
558 let plen = prefix.len();
559 let hash_size = 1usize << params.hash_log;
560 let mut sequences = Vec::new();
561
562 match params.strategy {
563 Strategy::Fast => {
564 let mut hash_table = vec![0u32; hash_size];
565 fast::prefill_hash_table(
566 &combined,
567 plen,
568 params.hash_log,
569 params.min_match,
570 &mut hash_table,
571 );
572 let mut positions = PositionBase::new(params.window_log);
573 let mut offset = 0;
574 while offset < input.len() {
575 let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
576 let is_last = offset + chunk_size >= input.len();
577 let (start, end) = (plen + offset, plen + offset + chunk_size);
578 if let Some(shift) = positions.advance(start, end) {
579 rebase::reduce_hash_table(&mut hash_table, shift);
580 }
581 let base = positions.base();
582 fast::compress_fast_block(
583 &combined[base..],
584 start - base,
585 end - base,
586 ¶ms,
587 &rep_offsets,
588 &mut hash_table,
589 &mut sequences,
590 );
591 if params.force_raw_literals {
592 block_encoder::encode_compressed_block_raw(
593 &input[offset..offset + chunk_size],
594 &sequences,
595 &mut rep_offsets,
596 is_last,
597 &mut output,
598 &mut workspace,
599 )?;
600 } else {
601 block_encoder::encode_compressed_block(
602 &input[offset..offset + chunk_size],
603 &sequences,
604 &mut rep_offsets,
605 is_last,
606 &mut output,
607 &mut workspace,
608 strategy::block_policy(¶ms, input.len()),
609 )?;
610 }
611 offset += chunk_size;
612 }
613 }
614 Strategy::DFast => {
615 let short_size = 1usize << params.chain_log;
616 let long_size = 1usize << params.hash_log;
617 let mut hash_short = vec![0u32; short_size];
618 let mut hash_long = vec![0u32; long_size];
619 dfast::prefill_hash_tables(
620 &combined,
621 plen,
622 params.hash_log,
623 params.chain_log,
624 params.min_match,
625 &mut hash_short,
626 &mut hash_long,
627 );
628 let mut positions = PositionBase::new(params.window_log);
629 let mut offset = 0;
630 while offset < input.len() {
631 let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
632 let is_last = offset + chunk_size >= input.len();
633 let (start, end) = (plen + offset, plen + offset + chunk_size);
634 if let Some(shift) = positions.advance(start, end) {
635 rebase::reduce_hash_table(&mut hash_short, shift);
636 rebase::reduce_hash_table(&mut hash_long, shift);
637 }
638 let base = positions.base();
639 dfast::compress_dfast_block(
640 &combined[base..],
641 start - base,
642 end - base,
643 ¶ms,
644 &rep_offsets,
645 &mut hash_short,
646 &mut hash_long,
647 &mut sequences,
648 );
649 block_encoder::encode_compressed_block(
650 &input[offset..offset + chunk_size],
651 &sequences,
652 &mut rep_offsets,
653 is_last,
654 &mut output,
655 &mut workspace,
656 strategy::block_policy(¶ms, input.len()),
657 )?;
658 offset += chunk_size;
659 }
660 }
661 }
662 }
663 }
664
665 let hash = xxh64(input, 0);
666 let checksum = (hash & 0xFFFF_FFFF) as u32;
667 output.extend_from_slice(&checksum.to_le_bytes());
668
669 Ok(output)
670}
671
672pub fn compress_into(input: &[u8], output: &mut [u8], level: i32) -> Result<usize, CompressError> {
673 let params = strategy::level_params_for_size(level, input.len())
674 .ok_or(CompressError::InvalidLevel(level))?;
675 let mut sink = SliceSink::new(output);
676 compress_frame(input, ¶ms, &mut sink)?;
677 Ok(sink.pos())
678}
679
680#[cfg(test)]
681mod tests {
682 use super::*;
683 use zrip_core::frame::header::parse_frame_header;
684
685 #[test]
686 fn clamp_params_normalizes_public_log_values() {
687 let mut params = strategy::level_params(1).unwrap();
688 params.hash_log = 0;
689 params.chain_log = 40;
690 params.window_log = 40;
691
692 clamp_params_to_src_size(&mut params, usize::MAX);
693
694 assert_eq!(params.hash_log, strategy::HASH_LOG_MIN);
695 assert_eq!(params.chain_log, strategy::HASH_LOG_MAX);
696 assert_eq!(params.window_log, strategy::WINDOW_LOG_MAX);
697 }
698
699 #[test]
700 fn src_log_rounds_up() {
701 assert_eq!(strategy::src_log(2), 1);
702 assert_eq!(strategy::src_log(3), 2);
703 assert_eq!(strategy::src_log(1 << 10), 10);
704 assert_eq!(strategy::src_log((1 << 10) + 1), 11);
705 }
706
707 #[cfg(target_pointer_width = "64")]
708 #[test]
709 fn inputs_past_4_gib_keep_the_level_params() {
710 let full = strategy::level_params(1).unwrap();
711 for len in [1usize << 32, (1 << 32) + 5, 5 << 32] {
712 let sized = strategy::level_params_for_size(1, len).unwrap();
713 assert_eq!(sized.window_log, full.window_log, "len {len}");
714 assert_eq!(sized.hash_log, full.hash_log, "len {len}");
715
716 let mut clamped = full;
717 clamp_params_to_src_size(&mut clamped, len);
718 assert_eq!(clamped.window_log, full.window_log, "len {len}");
719 assert_eq!(clamped.hash_log, full.hash_log, "len {len}");
720 }
721 }
722
723 #[test]
724 fn options_clamp_window_log_before_ldm_defaults() {
725 let mut params = strategy::level_params(1).unwrap();
726 let opts = strategy::Options::default().window_log(0);
727
728 strategy::apply_options(&mut params, &opts);
729
730 assert_eq!(params.window_log, strategy::WINDOW_LOG_MIN);
731 #[cfg(feature = "ldm")]
732 {
733 let mut params = strategy::level_params(1).unwrap();
734 let opts = strategy::Options::default().window_log(0).ldm(true);
735 strategy::apply_options(&mut params, &opts);
736
737 let ldm = params.ldm_params.unwrap();
738 assert!(ldm.hash_log >= ldm.bucket_size_log);
739 }
740 }
741
742 #[cfg(feature = "ldm")]
743 #[test]
744 fn ldm_defaults_window_log_to_27() {
745 let mut params = strategy::level_params(3).unwrap();
746 strategy::apply_options(&mut params, &strategy::Options::default().ldm(true));
747 assert_eq!(params.window_log, 27);
748
749 let mut params = strategy::level_params(3).unwrap();
750 let opts = strategy::Options::default().window_log(22).ldm(true);
751 strategy::apply_options(&mut params, &opts);
752 assert_eq!(params.window_log, 22);
753 }
754
755 #[cfg(feature = "ldm")]
756 #[test]
757 fn ldm_table_follows_the_clamped_window() {
758 let table_log = |len: usize, opts: &strategy::Options| {
759 params_with_options(1, len, opts)
760 .unwrap()
761 .ldm_params
762 .map(|ldm| ldm.hash_log)
763 };
764
765 let bare = strategy::Options::default().ldm(true);
766 assert_eq!(table_log(1, &bare), None);
767 assert_eq!(table_log(63, &bare), None);
768 assert_eq!(table_log(64, &bare), Some(9));
769 assert_eq!(table_log(1 << 10, &bare), Some(9));
770 assert_eq!(table_log(1 << 20, &bare), Some(19));
771 assert_eq!(table_log(1 << 27, &bare), Some(20));
772
773 let explicit = strategy::Options::default().window_log(24).ldm(true);
774 assert_eq!(table_log(1 << 10, &explicit), Some(9));
775 assert_eq!(table_log(1 << 27, &explicit), Some(20));
776 }
777
778 fn skewed_bytes(len: usize) -> Vec<u8> {
781 let mut x = 0x2545_F491_4F6C_DD1Du64;
782 (0..len)
783 .map(|_| {
784 x ^= x << 13;
785 x ^= x >> 7;
786 x ^= x << 17;
787 let r = (x >> 32) as u32;
788 b"eeeeeeettttaaoonnissshhrdl "[(r % 28) as usize] + (r >> 30) as u8
789 })
790 .collect()
791 }
792
793 fn wordy_bytes(len: usize) -> Vec<u8> {
796 const WORDS: &str = "the of and to in is was for on that with as by at \
797 from his her they this have had were which their are but not one \
798 all been when there she would what so if will more no out up into \
799 could them than then some other time very about only upon over \
800 such said great before after little";
801 let words: Vec<&str> = WORDS.split_whitespace().collect();
802 let mut x = 0x9E37_79B9_7F4A_7C15u64;
803 let mut out = Vec::with_capacity(len + 16);
804 while out.len() < len {
805 x ^= x << 13;
806 x ^= x >> 7;
807 x ^= x << 17;
808 out.extend_from_slice(words[(x >> 58) as usize % words.len()].as_bytes());
809 out.push(b' ');
810 }
811 out.truncate(len);
812 out
813 }
814
815 #[test]
816 fn negative_levels_skip_huffman_on_tiny_inputs() {
817 let data = skewed_bytes(2048);
819 for level in -7..=-1 {
820 let out = compress(&data, level).unwrap();
821 assert!(out.len() > data.len(), "L{level}: {} compressed", out.len());
822 }
823 for level in 1..=4 {
824 let out = compress(&data, level).unwrap();
825 assert!(out.len() * 5 < data.len() * 4, "L{level}: {}", out.len());
826 }
827 }
828
829 #[test]
830 fn negative_levels_still_match_tiny_inputs() {
831 let data = wordy_bytes(2048);
832 let sizes: Vec<usize> = (-7..=-1)
833 .map(|level| compress(&data, level).unwrap().len())
834 .collect();
835 assert!(
839 sizes[1..].iter().all(|&n| n * 11 < data.len() * 10),
840 "{sizes:?}"
841 );
842 assert!(sizes.windows(2).all(|w| w[0] >= w[1]), "{sizes:?}");
843 }
844
845 #[test]
846 fn negative_levels_huffman_code_above_their_raw_limit() {
847 let data = skewed_bytes(32 * 1024);
848 for level in -6..=-1 {
849 let out = compress(&data, level).unwrap();
850 assert!(out.len() * 5 < data.len() * 4, "L{level}: {}", out.len());
851 }
852 let out = compress(&data, -7).unwrap();
854 assert!(out.len() > data.len(), "L-7: {}", out.len());
855 }
856
857 #[test]
858 fn level_minus_8_runs_as_level_minus_7() {
859 let data = wordy_bytes(64 * 1024);
860 assert_eq!(compress(&data, -8).unwrap(), compress(&data, -7).unwrap());
861 }
862
863 #[test]
864 fn faster_levels_keep_raw_literals_longer() {
865 let limits: Vec<usize> = (-6..=-1)
866 .map(|level| strategy::raw_literals_limit(level).unwrap())
867 .collect();
868 assert_eq!(limits.last(), Some(&2048));
869 assert!(limits.windows(2).all(|w| w[0] > w[1]), "{limits:?}");
870 assert_eq!(strategy::raw_literals_limit(-7), None);
871 assert_eq!(strategy::raw_literals_limit(1), None);
872 }
873
874 #[test]
875 fn small_plain_frame_uses_single_segment_header() {
876 let mut output = Vec::new();
877
878 write_frame_header(&mut output, 12, None, 19).unwrap();
879 let header = parse_frame_header(&output).unwrap();
880
881 assert!(header.single_segment);
882 assert_eq!(header.frame_content_size, Some(12));
883 assert_eq!(header.window_size, 12);
884 assert_eq!(header.dict_id, None);
885 assert!(header.content_checksum);
886 assert_eq!(header.header_size, 6);
887 }
888
889 #[test]
890 fn large_plain_frame_uses_bounded_window_descriptor() {
891 let mut output = Vec::new();
892 let content_size = MAX_WINDOW_SIZE as usize + 1;
893
894 write_frame_header(&mut output, content_size, None, 19).unwrap();
895 let header = parse_frame_header(&output).unwrap();
896
897 assert!(!header.single_segment);
898 assert_eq!(header.frame_content_size, Some(content_size as u64));
899 assert_eq!(header.window_size, 1 << 19);
900 assert_eq!(header.dict_id, None);
901 assert!(header.content_checksum);
902 assert_eq!(header.header_size, 10);
903 }
904
905 #[test]
906 fn dict_frame_uses_window_descriptor_even_when_small() {
907 let mut output = Vec::new();
908
909 write_frame_header(&mut output, 12, Some(0x1234), 10).unwrap();
910 let header = parse_frame_header(&output).unwrap();
911
912 assert!(!header.single_segment);
913 assert_eq!(header.frame_content_size, Some(12));
914 assert_eq!(header.window_size, 1 << 10);
915 assert_eq!(header.dict_id, Some(0x1234));
916 assert!(header.content_checksum);
917 assert_eq!(header.header_size, 12);
918 }
919
920 #[test]
921 fn no_fcs_frame_uses_window_descriptor() {
922 let mut output = Vec::new();
923
924 write_frame_header_without_content_size(&mut output, None, 19).unwrap();
925 let header = parse_frame_header(&output).unwrap();
926
927 assert!(!header.single_segment);
928 assert_eq!(header.frame_content_size, None);
929 assert_eq!(header.window_size, 1 << 19);
930 assert_eq!(header.dict_id, None);
931 assert!(header.content_checksum);
932 assert_eq!(header.header_size, 6);
933 }
934}