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