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