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