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