1#[cfg(feature = "alloc")]
2use alloc::borrow::Cow;
3#[cfg(feature = "alloc")]
4use alloc::vec::Vec;
5
6use crate::block_encoder::{self, BlockEncodeWorkspace};
7use crate::fast::AttachedDict;
8use crate::output::{OutputSink, SliceSink};
9use crate::rebase::{self, PositionBase};
10use crate::strategy::{self, LevelParams, Strategy};
11use crate::table::MatchTable;
12use crate::{dfast, fast, skip_match_search, write_frame_header_with_checksum};
13use zrip_core::Sequence;
14use zrip_core::dict::Dictionary;
15use zrip_core::error::CompressError;
16use zrip_core::frame::MAX_BLOCK_SIZE;
17use zrip_core::huffman::encode::HuffmanEncodeTable;
18use zrip_core::xxhash::{Xxh64State, xxh64};
19
20const ATTACH_THRESHOLD: usize = 8192;
25
26const DFAST_ATTACH_LIMIT: usize = 16 * 1024;
29
30struct Attached {
34 min_match: u32,
35 table: Vec<u32>,
36 long: Vec<u32>,
37}
38
39fn attached_log(prefix_len: usize, cap: u32) -> u32 {
42 if prefix_len >= 2 {
43 (strategy::src_log(prefix_len) + 1)
44 .clamp(strategy::HASH_LOG_MIN, cap.max(strategy::HASH_LOG_MIN))
45 } else {
46 strategy::HASH_LOG_MIN
47 }
48}
49
50pub(crate) struct PreparedDict {
58 combined: Vec<u8>,
59 params: LevelParams,
61 hash_snapshot: Vec<u32>,
63 hash_long_snapshot: Vec<u32>,
64 attached: Vec<Attached>,
67 attached_hash_log: u32,
70 attached_long_log: u32,
71 prefix_len: usize,
72 rep_offsets: [u32; 3],
73 dict_id: u32,
74 huf_table: Option<HuffmanEncodeTable>,
75 ll_table: Option<block_encoder::FseEncodeTable>,
76 of_table: Option<block_encoder::FseEncodeTable>,
77 ml_table: Option<block_encoder::FseEncodeTable>,
78}
79
80impl PreparedDict {
81 pub fn new(dict: &Dictionary, level: i32, params: &LevelParams) -> Self {
82 let prefix = dict.content();
83 let prefix_len = prefix.len();
84
85 let mut combined = Vec::with_capacity(prefix_len);
88 combined.extend_from_slice(prefix);
89
90 let (attached_hash_log, attached_long_log) = match params.strategy {
91 Strategy::Fast => (attached_log(prefix_len, params.hash_log), 0),
92 Strategy::DFast => (
93 attached_log(prefix_len, params.chain_log),
94 attached_log(prefix_len, params.hash_log),
95 ),
96 };
97 let mut attached: Vec<Attached> = Vec::new();
98 for size in [1, ATTACH_THRESHOLD, MAX_BLOCK_SIZE] {
100 let min_match = strategy::level_params_for_size(level, prefix_len + size)
101 .expect("level validated by the caller")
102 .min_match;
103 if attached.iter().all(|a| a.min_match != min_match) {
104 attached.push(Attached {
105 min_match,
106 table: Vec::new(),
107 long: Vec::new(),
108 });
109 }
110 }
111
112 let huf_table = dict
113 .huf_table()
114 .and_then(|(dt, tl)| HuffmanEncodeTable::from_decode_table(dt, tl));
115
116 let ll_table = dict
117 .ll_table()
118 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 35));
119 let of_table = dict
120 .of_table()
121 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 31));
122 let ml_table = dict
123 .ml_table()
124 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 52));
125
126 Self {
127 combined,
128 params: *params,
129 hash_snapshot: Vec::new(),
130 hash_long_snapshot: Vec::new(),
131 attached,
132 attached_hash_log,
133 attached_long_log,
134 prefix_len,
135 rep_offsets: *dict.rep_offsets(),
136 dict_id: dict.id(),
137 huf_table,
138 ll_table,
139 of_table,
140 ml_table,
141 }
142 }
143
144 fn snapshot_matches(&self, params: &LevelParams) -> bool {
146 let p = &self.params;
147 match params.strategy {
148 Strategy::Fast => params.hash_log == p.hash_log,
149 Strategy::DFast => params.chain_log == p.chain_log && params.hash_log == p.hash_log,
150 }
151 }
152
153 fn snapshots(&mut self) -> (&[u32], &[u32]) {
155 if self.hash_snapshot.is_empty() {
156 let p = &self.params;
157 let prefix = &self.combined[..self.prefix_len];
160 let mut hash_table = MatchTable::new();
161 match p.strategy {
162 Strategy::Fast => {
163 fast::prefill_hash_table(
164 prefix,
165 self.prefix_len,
166 p.hash_log,
167 p.min_match,
168 &mut hash_table,
169 );
170 }
171 Strategy::DFast => {
172 let mut hash_long = MatchTable::new();
173 dfast::prefill_hash_tables(
174 prefix,
175 self.prefix_len,
176 p.hash_log,
177 p.chain_log,
178 p.min_match,
179 &mut hash_table,
180 &mut hash_long,
181 );
182 self.hash_long_snapshot = hash_long.into_vec();
183 }
184 }
185 self.hash_snapshot = hash_table.into_vec();
186 }
187 (&self.hash_snapshot, &self.hash_long_snapshot)
188 }
189
190 fn has_attached(&self, min_match: u32) -> bool {
192 self.attached.iter().any(|a| a.min_match == min_match)
193 }
194
195 fn build_attached(&mut self, min_match: u32) {
197 let prefix = &self.combined[..self.prefix_len];
199 let (hash_log, long_log) = (self.attached_hash_log, self.attached_long_log);
200 let strategy = self.params.strategy;
201 if let Some(a) = self
202 .attached
203 .iter_mut()
204 .find(|a| a.min_match == min_match && a.table.is_empty())
205 {
206 let mut table = MatchTable::new();
207 match strategy {
208 Strategy::Fast => {
209 fast::prefill_hash_table(prefix, prefix.len(), hash_log, min_match, &mut table);
210 }
211 Strategy::DFast => {
212 let mut long = MatchTable::new();
213 dfast::prefill_hash_tables(
214 prefix,
215 prefix.len(),
216 long_log,
217 hash_log,
218 min_match,
219 &mut table,
220 &mut long,
221 );
222 a.long = long.into_vec();
223 }
224 }
225 a.table = table.into_vec();
226 }
227 }
228
229 fn attached(&self, min_match: u32) -> Option<&Attached> {
231 self.attached.iter().find(|a| a.min_match == min_match)
232 }
233}
234
235pub struct CompressContext {
249 level: i32,
250 content_checksum: bool,
251 dict: Option<(Dictionary, usize)>,
254 prepared: Option<PreparedDict>,
255 hash_table: MatchTable,
256 hash_long: MatchTable,
257 dict_hash: MatchTable,
258 small_hash: MatchTable,
261 small_long: MatchTable,
262 sequences: Vec<Sequence>,
263 output: Vec<u8>,
264 workspace: BlockEncodeWorkspace,
265 combined: Vec<u8>,
266}
267
268impl CompressContext {
269 pub fn new(level: i32) -> Result<Self, CompressError> {
274 strategy::level_params(level).ok_or(CompressError::InvalidLevel(level))?;
275 Ok(Self {
276 level,
277 content_checksum: true,
278 dict: None,
279 prepared: None,
280 hash_table: MatchTable::new(),
281 hash_long: MatchTable::new(),
282 dict_hash: MatchTable::new(),
283 small_hash: MatchTable::new(),
284 small_long: MatchTable::new(),
285 sequences: Vec::new(),
286 output: Vec::new(),
287 workspace: BlockEncodeWorkspace::new(),
288 combined: Vec::new(),
289 })
290 }
291
292 pub fn with_dict(level: i32, dict: Dictionary) -> Result<Self, CompressError> {
302 Self::with_dict_for_size(level, dict, usize::MAX)
303 }
304
305 pub fn with_dict_for_size(
312 level: i32,
313 dict: Dictionary,
314 expected_size: usize,
315 ) -> Result<Self, CompressError> {
316 let total_window = dict.content().len().saturating_add(expected_size);
317 let params = strategy::level_params_for_size(level, total_window)
318 .ok_or(CompressError::InvalidLevel(level))?;
319 let prepared = PreparedDict::new(&dict, level, ¶ms);
320 Ok(Self {
321 level,
322 content_checksum: true,
323 dict: Some((dict, expected_size)),
324 prepared: Some(prepared),
325 hash_table: MatchTable::new(),
326 hash_long: MatchTable::new(),
327 dict_hash: MatchTable::new(),
328 small_hash: MatchTable::new(),
329 small_long: MatchTable::new(),
330 sequences: Vec::new(),
331 output: Vec::new(),
332 workspace: BlockEncodeWorkspace::new(),
333 combined: Vec::new(),
334 })
335 }
336
337 pub const fn level(&self) -> i32 {
339 self.level
340 }
341
342 pub fn set_level(&mut self, level: i32) -> Result<(), CompressError> {
347 if level == self.level {
348 return Ok(());
349 }
350 strategy::level_params(level).ok_or(CompressError::InvalidLevel(level))?;
351 if let Some((dict, expected_size)) = &self.dict {
352 let total_window = dict.content().len().saturating_add(*expected_size);
353 let params = strategy::level_params_for_size(level, total_window)
354 .expect("level validated above");
355 self.prepared = Some(PreparedDict::new(dict, level, ¶ms));
356 }
357 self.level = level;
358 Ok(())
359 }
360
361 pub const fn set_content_checksum(&mut self, enabled: bool) {
366 self.content_checksum = enabled;
367 }
368
369 pub const fn content_checksum(&self) -> bool {
371 self.content_checksum
372 }
373
374 pub fn compress(&mut self, input: &[u8]) -> Result<Cow<'_, [u8]>, CompressError> {
376 let mut output = core::mem::take(&mut self.output);
377 output.clear();
378 let result = self.compress_to(input, &mut output);
379 self.output = output;
380 result?;
381 Ok(self.take_or_borrow_output())
382 }
383
384 pub fn compress_into(
393 &mut self,
394 input: &[u8],
395 output: &mut [u8],
396 ) -> Result<usize, CompressError> {
397 let mut sink = SliceSink::new(output);
398 self.compress_to(input, &mut sink)?;
399 Ok(sink.pos())
400 }
401
402 fn compress_to<S: OutputSink>(
404 &mut self,
405 input: &[u8],
406 output: &mut S,
407 ) -> Result<(), CompressError> {
408 if self.prepared.is_some() {
409 return self.compress_with_prepared(input, output);
410 }
411 let params = strategy::level_params_for_size(self.level, input.len())
412 .expect("level validated at construction");
413 compress_core(
414 input,
415 params,
416 None,
417 &[],
418 [1u32, 4, 8],
419 &mut self.hash_table,
420 &mut self.hash_long,
421 &mut self.dict_hash,
422 &mut self.sequences,
423 output,
424 &mut self.workspace,
425 &mut self.combined,
426 self.content_checksum,
427 )
428 }
429
430 pub fn compress_with_dict(
432 &mut self,
433 input: &[u8],
434 dict: &Dictionary,
435 ) -> Result<Cow<'_, [u8]>, CompressError> {
436 let params =
437 strategy::level_params_with_prefix(self.level, dict.content().len(), input.len())
438 .expect("level validated at construction");
439 self.workspace.prev_ll = dict
440 .ll_table()
441 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 35));
442 self.workspace.prev_of = dict
443 .of_table()
444 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 31));
445 self.workspace.prev_ml = dict
446 .ml_table()
447 .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 52));
448 self.workspace.prev_huffman = dict
449 .huf_table()
450 .and_then(|(dt, tl)| HuffmanEncodeTable::from_decode_table(dt, tl));
451 self.output.clear();
452 compress_core(
453 input,
454 params,
455 Some(dict.id()),
456 dict.content(),
457 *dict.rep_offsets(),
458 &mut self.hash_table,
459 &mut self.hash_long,
460 &mut self.dict_hash,
461 &mut self.sequences,
462 &mut self.output,
463 &mut self.workspace,
464 &mut self.combined,
465 self.content_checksum,
466 )?;
467 Ok(self.take_or_borrow_output())
468 }
469
470 fn compress_with_prepared<S: OutputSink>(
471 &mut self,
472 input: &[u8],
473 output: &mut S,
474 ) -> Result<(), CompressError> {
475 let prep = self.prepared.as_ref().unwrap();
476 let params = strategy::level_params_with_prefix(self.level, prep.prefix_len, input.len())
477 .expect("level validated at construction");
478
479 let dict_id = prep.dict_id;
480 let prefix_len = prep.prefix_len;
481 let snapshot_matches = prep.snapshot_matches(¶ms);
482 let other_tier = !snapshot_matches
487 && match params.strategy {
488 Strategy::Fast => true,
489 Strategy::DFast => input.len() <= DFAST_ATTACH_LIMIT,
490 };
491 let use_attached = !input.is_empty()
492 && input.len() <= MAX_BLOCK_SIZE
493 && (input.len() <= ATTACH_THRESHOLD || other_tier)
494 && prep.has_attached(params.min_match);
495
496 if !use_attached && !snapshot_matches {
497 return self.compress_with_dict_fallback(input, dict_id, prefix_len, output);
498 }
499
500 {
501 let prep = self.prepared.as_mut().unwrap();
502 if use_attached {
503 prep.build_attached(params.min_match);
504 } else {
505 let (short, long) = prep.snapshots();
508 self.hash_table.copy_from(short);
509 if !long.is_empty() {
510 self.hash_long.copy_from(long);
511 }
512 }
513 prep.combined.truncate(prep.prefix_len);
514 prep.combined.extend_from_slice(input);
515 }
516
517 let prep = self.prepared.as_ref().unwrap();
518
519 if use_attached {
520 self.workspace.prev_huffman = if params.force_raw_literals {
521 None
522 } else {
523 prep.huf_table.clone()
524 };
525 } else if let Some(ref huf) = prep.huf_table {
526 self.workspace.prev_huffman = Some(huf.clone());
527 } else {
528 self.workspace.prev_huffman = None;
529 }
530 self.workspace.prev_ll = prep.ll_table.clone();
531 self.workspace.prev_of = prep.of_table.clone();
532 self.workspace.prev_ml = prep.ml_table.clone();
533
534 output.reserve(input.len() + 32);
535 write_frame_header_with_checksum(
536 output,
537 input.len(),
538 Some(dict_id),
539 params.window_log,
540 self.content_checksum,
541 )?;
542
543 if input.is_empty() {
544 block_encoder::encode_raw_block(&[], true, output)?;
545 } else if use_attached {
546 let input_log = |cap: u32| {
548 if input.len() >= 2 {
549 cap.min(strategy::src_log(input.len()))
550 .max(strategy::HASH_LOG_MIN)
551 } else {
552 strategy::HASH_LOG_MIN
553 }
554 };
555 let input_params = LevelParams {
556 hash_log: input_log(params.hash_log),
557 chain_log: input_log(params.chain_log),
558 ..params
559 };
560 let mut rep_offsets = prep.rep_offsets;
561 let tables = prep.attached(params.min_match).unwrap();
562 let block_end = prefix_len + input.len();
563 match params.strategy {
564 Strategy::Fast => {
565 self.small_hash.clear(1usize << input_params.hash_log);
566 let dict = AttachedDict {
567 table: &tables.table,
568 hash_log: prep.attached_hash_log,
569 prefix_len,
570 };
571 fast::compress_fast_block_attached(
572 &prep.combined,
573 block_end,
574 &input_params,
575 &prep.rep_offsets,
576 dict,
577 &mut self.small_hash,
578 &mut self.sequences,
579 );
580 }
581 Strategy::DFast => {
582 self.small_hash.clear(1usize << input_params.chain_log);
583 self.small_long.clear(1usize << input_params.hash_log);
584 let dict = dfast::AttachedDfastDict {
585 short: &tables.table,
586 long: &tables.long,
587 short_log: prep.attached_hash_log,
588 long_log: prep.attached_long_log,
589 prefix_len,
590 };
591 dfast::compress_dfast_block_attached(
592 &prep.combined,
593 block_end,
594 &input_params,
595 &prep.rep_offsets,
596 dict,
597 &mut self.small_hash,
598 &mut self.small_long,
599 &mut self.sequences,
600 );
601 }
602 }
603
604 if params.force_raw_literals {
605 block_encoder::encode_compressed_block_raw(
606 input,
607 &self.sequences,
608 &mut rep_offsets,
609 true,
610 output,
611 &mut self.workspace,
612 )?;
613 } else {
614 block_encoder::encode_compressed_block(
615 input,
616 &self.sequences,
617 &mut rep_offsets,
618 true,
619 output,
620 &mut self.workspace,
621 strategy::block_policy(¶ms, input.len()),
622 )?;
623 }
624 } else {
625 let combined = &prep.combined;
626 let mut rep_offsets = prep.rep_offsets;
627
628 if input.len() <= MAX_BLOCK_SIZE {
629 match params.strategy {
630 Strategy::Fast => {
631 fast::compress_fast_block(
632 combined,
633 prefix_len,
634 prefix_len + input.len(),
635 ¶ms,
636 &rep_offsets,
637 &mut self.hash_table,
638 &mut self.sequences,
639 );
640 }
641 Strategy::DFast => {
642 dfast::compress_dfast_block(
643 combined,
644 prefix_len,
645 prefix_len + input.len(),
646 ¶ms,
647 &rep_offsets,
648 &mut self.hash_table,
649 &mut self.hash_long,
650 &mut self.sequences,
651 );
652 }
653 }
654 if params.force_raw_literals {
655 block_encoder::encode_compressed_block_raw(
656 input,
657 &self.sequences,
658 &mut rep_offsets,
659 true,
660 output,
661 &mut self.workspace,
662 )?;
663 } else {
664 block_encoder::encode_compressed_block(
665 input,
666 &self.sequences,
667 &mut rep_offsets,
668 true,
669 output,
670 &mut self.workspace,
671 strategy::block_policy(¶ms, input.len()),
672 )?;
673 }
674 } else {
675 let mut positions = PositionBase::new(params.window_log);
676 let mut offset = 0;
677 while offset < input.len() {
678 let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
679 let is_last = offset + chunk_size >= input.len();
680 let (start, end) = (prefix_len + offset, prefix_len + offset + chunk_size);
681 if let Some(shift) = positions.advance(start, end) {
682 rebase::reduce_hash_table(&mut self.hash_table, shift);
683 rebase::reduce_hash_table(&mut self.hash_long, shift);
684 }
685 let base = positions.base();
686 let src = &combined[base..];
687 match params.strategy {
688 Strategy::Fast => {
689 fast::compress_fast_block(
690 src,
691 start - base,
692 end - base,
693 ¶ms,
694 &rep_offsets,
695 &mut self.hash_table,
696 &mut self.sequences,
697 );
698 }
699 Strategy::DFast => {
700 dfast::compress_dfast_block(
701 src,
702 start - base,
703 end - base,
704 ¶ms,
705 &rep_offsets,
706 &mut self.hash_table,
707 &mut self.hash_long,
708 &mut self.sequences,
709 );
710 }
711 }
712 if params.force_raw_literals {
713 block_encoder::encode_compressed_block_raw(
714 &input[offset..offset + chunk_size],
715 &self.sequences,
716 &mut rep_offsets,
717 is_last,
718 output,
719 &mut self.workspace,
720 )?;
721 } else {
722 block_encoder::encode_compressed_block(
723 &input[offset..offset + chunk_size],
724 &self.sequences,
725 &mut rep_offsets,
726 is_last,
727 output,
728 &mut self.workspace,
729 strategy::block_policy(¶ms, input.len()),
730 )?;
731 }
732 offset += chunk_size;
733 }
734 }
735 }
736
737 if self.content_checksum {
738 let hash = xxh64(input, 0);
739 let checksum = (hash & 0xFFFF_FFFF) as u32;
740 output.extend_from_slice(&checksum.to_le_bytes())?;
741 }
742
743 Ok(())
744 }
745
746 fn compress_with_dict_fallback<S: OutputSink>(
747 &mut self,
748 input: &[u8],
749 dict_id: u32,
750 prefix_len: usize,
751 output: &mut S,
752 ) -> Result<(), CompressError> {
753 let prep = self.prepared.as_ref().unwrap();
754 let rep_offsets = prep.rep_offsets;
755 let prefix = &prep.combined[..prefix_len];
756
757 let params = strategy::level_params_with_prefix(self.level, prefix_len, input.len())
758 .expect("level validated at construction");
759 self.workspace.prev_huffman = prep.huf_table.clone();
760 self.workspace.prev_ll = prep.ll_table.clone();
761 self.workspace.prev_of = prep.of_table.clone();
762 self.workspace.prev_ml = prep.ml_table.clone();
763 compress_core(
764 input,
765 params,
766 Some(dict_id),
767 prefix,
768 rep_offsets,
769 &mut self.hash_table,
770 &mut self.hash_long,
771 &mut self.dict_hash,
772 &mut self.sequences,
773 output,
774 &mut self.workspace,
775 &mut self.combined,
776 self.content_checksum,
777 )
778 }
779
780 fn take_or_borrow_output(&mut self) -> Cow<'_, [u8]> {
781 if self.output.len() >= zrip_core::LARGE_OUTPUT_THRESHOLD {
782 Cow::Owned(core::mem::take(&mut self.output))
783 } else {
784 Cow::Borrowed(&self.output)
785 }
786 }
787}
788
789#[allow(clippy::too_many_arguments, clippy::unnecessary_wraps)]
790pub(crate) fn compress_core<S: OutputSink>(
791 input: &[u8],
792 params: LevelParams,
793 dict_id: Option<u32>,
794 prefix: &[u8],
795 init_rep_offsets: [u32; 3],
796 hash_table: &mut MatchTable,
797 hash_long: &mut MatchTable,
798 dict_hash: &mut MatchTable,
799 sequences: &mut Vec<Sequence>,
800 output: &mut S,
801 workspace: &mut BlockEncodeWorkspace,
802 combined: &mut Vec<u8>,
803 content_checksum: bool,
804) -> Result<(), CompressError> {
805 let hash_size = match params.strategy {
806 Strategy::Fast => 1usize << params.hash_log,
807 Strategy::DFast => 1usize << params.chain_log,
808 };
809 let long_size = 1usize << params.hash_log;
810
811 if prefix.is_empty() {
812 workspace.prev_huffman = None;
813 workspace.prev_ll = None;
814 workspace.prev_of = None;
815 workspace.prev_ml = None;
816 }
817
818 output.reserve(input.len() + 32);
819 write_frame_header_with_checksum(
820 output,
821 input.len(),
822 dict_id,
823 params.window_log,
824 content_checksum,
825 )?;
826
827 let mut checksum = content_checksum.then(|| Xxh64State::new(0));
830 let mut hashed_blocks = false;
831
832 if input.is_empty() {
833 block_encoder::encode_raw_block(&[], true, output)?;
834 } else {
835 let has_prefix = !prefix.is_empty();
836 let mut rep_offsets = init_rep_offsets;
837 let mut offset = 0;
838 let mut positions = PositionBase::new(params.window_log);
839
840 match params.strategy {
841 Strategy::Fast => {
842 if has_prefix && input.len() <= MAX_BLOCK_SIZE {
843 fast::compress_fast_with_prefix_reuse(
844 input,
845 ¶ms,
846 &rep_offsets,
847 prefix,
848 dict_hash,
849 hash_table,
850 sequences,
851 combined,
852 );
853 if params.force_raw_literals {
854 block_encoder::encode_compressed_block_raw(
855 input,
856 sequences,
857 &mut rep_offsets,
858 true,
859 output,
860 workspace,
861 )?;
862 } else {
863 block_encoder::encode_compressed_block(
864 input,
865 sequences,
866 &mut rep_offsets,
867 true,
868 output,
869 workspace,
870 strategy::block_policy(¶ms, input.len()),
871 )?;
872 }
873 } else if has_prefix {
874 combined.clear();
875 combined.reserve(prefix.len() + input.len());
876 combined.extend_from_slice(prefix);
877 combined.extend_from_slice(input);
878 let plen = prefix.len();
879 fast::prefill_hash_table(
880 combined,
881 plen,
882 params.hash_log,
883 params.min_match,
884 hash_table,
885 );
886
887 while offset < input.len() {
888 let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
889 let is_last = offset + chunk_size >= input.len();
890 let (start, end) = (plen + offset, plen + offset + chunk_size);
891 if let Some(shift) = positions.advance(start, end) {
892 rebase::reduce_hash_table(hash_table, shift);
893 }
894 let base = positions.base();
895 fast::compress_fast_block(
896 &combined[base..],
897 start - base,
898 end - base,
899 ¶ms,
900 &rep_offsets,
901 hash_table,
902 sequences,
903 );
904 if params.force_raw_literals {
905 block_encoder::encode_compressed_block_raw(
906 &input[offset..offset + chunk_size],
907 sequences,
908 &mut rep_offsets,
909 is_last,
910 output,
911 workspace,
912 )?;
913 } else {
914 block_encoder::encode_compressed_block(
915 &input[offset..offset + chunk_size],
916 sequences,
917 &mut rep_offsets,
918 is_last,
919 output,
920 workspace,
921 strategy::block_policy(¶ms, input.len()),
922 )?;
923 }
924 offset += chunk_size;
925 }
926 } else {
927 hash_table.clear(hash_size);
928 while offset < input.len() {
929 let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
930 let block_end = offset + chunk_size;
931 let is_last = block_end >= input.len();
932 let block = &input[offset..block_end];
933
934 if let Some(shift) = positions.advance(offset, block_end) {
935 rebase::reduce_hash_table(hash_table, shift);
936 }
937 if skip_match_search(¶ms, input.len(), block) {
938 block_encoder::encode_raw_block(block, is_last, output)?;
939 } else {
940 let base = positions.base();
941 fast::compress_fast_block(
942 &input[base..],
943 offset - base,
944 block_end - base,
945 ¶ms,
946 &rep_offsets,
947 hash_table,
948 sequences,
949 );
950 if params.force_raw_literals {
951 block_encoder::encode_compressed_block_raw(
952 block,
953 sequences,
954 &mut rep_offsets,
955 is_last,
956 output,
957 workspace,
958 )?;
959 } else {
960 block_encoder::encode_compressed_block(
961 block,
962 sequences,
963 &mut rep_offsets,
964 is_last,
965 output,
966 workspace,
967 strategy::block_policy(¶ms, input.len()),
968 )?;
969 }
970 }
971 if let Some(c) = checksum.as_mut() {
972 c.update(block);
973 }
974 offset = block_end;
975 }
976 hashed_blocks = true;
977 }
978 }
979 Strategy::DFast => {
980 if has_prefix && input.len() <= MAX_BLOCK_SIZE {
981 dfast::compress_dfast_with_prefix_reuse(
982 input,
983 ¶ms,
984 &rep_offsets,
985 prefix,
986 hash_table,
987 hash_long,
988 sequences,
989 combined,
990 );
991 block_encoder::encode_compressed_block(
992 input,
993 sequences,
994 &mut rep_offsets,
995 true,
996 output,
997 workspace,
998 strategy::block_policy(¶ms, input.len()),
999 )?;
1000 } else if has_prefix {
1001 combined.clear();
1002 combined.reserve(prefix.len() + input.len());
1003 combined.extend_from_slice(prefix);
1004 combined.extend_from_slice(input);
1005 let plen = prefix.len();
1006 dfast::prefill_hash_tables(
1007 combined,
1008 plen,
1009 params.hash_log,
1010 params.chain_log,
1011 params.min_match,
1012 hash_table,
1013 hash_long,
1014 );
1015
1016 while offset < input.len() {
1017 let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
1018 let is_last = offset + chunk_size >= input.len();
1019 let (start, end) = (plen + offset, plen + offset + chunk_size);
1020 if let Some(shift) = positions.advance(start, end) {
1021 rebase::reduce_hash_table(hash_table, shift);
1022 rebase::reduce_hash_table(hash_long, shift);
1023 }
1024 let base = positions.base();
1025 dfast::compress_dfast_block(
1026 &combined[base..],
1027 start - base,
1028 end - base,
1029 ¶ms,
1030 &rep_offsets,
1031 hash_table,
1032 hash_long,
1033 sequences,
1034 );
1035 block_encoder::encode_compressed_block(
1036 &input[offset..offset + chunk_size],
1037 sequences,
1038 &mut rep_offsets,
1039 is_last,
1040 output,
1041 workspace,
1042 strategy::block_policy(¶ms, input.len()),
1043 )?;
1044 offset += chunk_size;
1045 }
1046 } else {
1047 hash_table.clear(hash_size);
1048 hash_long.clear(long_size);
1049 while offset < input.len() {
1050 let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
1051 let block_end = offset + chunk_size;
1052 let is_last = block_end >= input.len();
1053 let block = &input[offset..block_end];
1054
1055 if let Some(shift) = positions.advance(offset, block_end) {
1056 rebase::reduce_hash_table(hash_table, shift);
1057 rebase::reduce_hash_table(hash_long, shift);
1058 }
1059 if skip_match_search(¶ms, input.len(), block) {
1060 block_encoder::encode_raw_block(block, is_last, output)?;
1061 } else {
1062 let base = positions.base();
1063 dfast::compress_dfast_block(
1064 &input[base..],
1065 offset - base,
1066 block_end - base,
1067 ¶ms,
1068 &rep_offsets,
1069 hash_table,
1070 hash_long,
1071 sequences,
1072 );
1073 block_encoder::encode_compressed_block(
1074 block,
1075 sequences,
1076 &mut rep_offsets,
1077 is_last,
1078 output,
1079 workspace,
1080 strategy::block_policy(¶ms, input.len()),
1081 )?;
1082 }
1083 if let Some(c) = checksum.as_mut() {
1084 c.update(block);
1085 }
1086 offset = block_end;
1087 }
1088 hashed_blocks = true;
1089 }
1090 }
1091 }
1092 }
1093
1094 if let Some(c) = checksum {
1095 let hash = if hashed_blocks {
1096 c.finish()
1097 } else {
1098 xxh64(input, 0)
1099 };
1100 output.extend_from_slice(&((hash & 0xFFFF_FFFF) as u32).to_le_bytes())?;
1101 }
1102
1103 Ok(())
1104}
1105
1106#[cfg(test)]
1107mod tests {
1108 use super::*;
1109
1110 fn dict() -> Dictionary {
1111 let fixture = include_bytes!("../../../tests/fixtures/corpus_dict_roundtrip.bin");
1112 let len = u32::from_le_bytes([fixture[0], fixture[1], fixture[2], fixture[3]]) as usize;
1113 Dictionary::from_bytes(&fixture[4..4 + len]).unwrap()
1114 }
1115
1116 #[test]
1119 fn dictionary_tables_lacking_a_code_are_not_reused() {
1120 use zrip_core::fse::table_builder::serialize_fse_table_description;
1121 use zrip_core::fse::{LL_DEFAULT_ACCURACY, LL_DEFAULT_DIST};
1122 use zrip_core::fse::{ML_DEFAULT_ACCURACY, ML_DEFAULT_DIST};
1123 const OF_DIST: [i16; 11] = [1, 1, 1, 1, 3, 3, 3, 3, 6, 6, 4];
1125 let mut raw = Vec::new();
1126 raw.extend_from_slice(&zrip_core::dict::DICT_MAGIC.to_le_bytes());
1127 raw.extend_from_slice(&7u32.to_le_bytes());
1128 raw.extend_from_slice(&[128 + 1, 0x11]);
1129 raw.extend(serialize_fse_table_description(&OF_DIST, 5));
1130 raw.extend(serialize_fse_table_description(
1131 &ML_DEFAULT_DIST,
1132 ML_DEFAULT_ACCURACY,
1133 ));
1134 raw.extend(serialize_fse_table_description(
1135 &LL_DEFAULT_DIST,
1136 LL_DEFAULT_ACCURACY,
1137 ));
1138 for rep in [1u32, 4, 8] {
1139 raw.extend_from_slice(&rep.to_le_bytes());
1140 }
1141 raw.extend((0..1024u32).map(|i| (i * 7 % 251) as u8));
1142 let dict = Dictionary::from_bytes(&raw).unwrap();
1143 assert!(dict.of_table().is_some());
1144
1145 let mut x = 0x2545_f491u32;
1147 let mut input: Vec<u8> = (0..5000)
1148 .map(|_| {
1149 x ^= x << 13;
1150 x ^= x >> 17;
1151 x ^= x << 5;
1152 x as u8
1153 })
1154 .collect();
1155 input.extend_from_within(..2048);
1156 for level in [1, 3] {
1157 let frames = [
1158 CompressContext::with_dict(level, dict.clone())
1159 .unwrap()
1160 .compress(&input)
1161 .unwrap()
1162 .into_owned(),
1163 crate::compress_with_dict(&input, level, &dict).unwrap(),
1164 ];
1165 for frame in &frames {
1166 let out = zrip::decompress_with_dict(frame, &dict).unwrap();
1167 assert!(out == input, "L{level}: frame decodes to another input");
1168 }
1169 }
1170 }
1171
1172 #[test]
1175 fn dictionary_tables_ignore_buffered_input() {
1176 let dict = dict();
1177 let input: Vec<u8> = (0..4096u32)
1178 .map(|i| (i.wrapping_mul(0x9e37_79b1) >> 24) as u8)
1179 .collect();
1180 for level in -7..=4 {
1181 let params = strategy::level_params(level).unwrap();
1182 let mut clean = PreparedDict::new(&dict, level, ¶ms);
1183 let mut stale = PreparedDict::new(&dict, level, ¶ms);
1184 stale.combined.extend_from_slice(&input);
1185 assert!(clean.snapshots() == stale.snapshots(), "L{level} snapshots");
1186 let mlss: Vec<u32> = clean.attached.iter().map(|a| a.min_match).collect();
1187 for mls in mlss {
1188 clean.build_attached(mls);
1189 stale.build_attached(mls);
1190 let (c, s) = (clean.attached(mls).unwrap(), stale.attached(mls).unwrap());
1191 assert!(
1192 c.table == s.table && c.long == s.long,
1193 "L{level} attached tables for min match {mls}"
1194 );
1195 }
1196 }
1197 }
1198}