Skip to main content

zrip_encode/
context.rs

1//! [`CompressContext`], which reuses tables and buffers across frames, and
2//! the dictionary state it prepares once.
3#[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
22/// Largest input that keeps the dictionary in its own tables instead of
23/// copying the prefilled ones, as C zstd does for its fast and dfast
24/// strategies. Past it, copying the tables costs less than the dictionary
25/// probes.
26const ATTACH_THRESHOLD: usize = 8192;
27
28/// Largest DFast input that attaches the dictionary when its prefilled
29/// tables are sized for other inputs.
30const DFAST_ATTACH_LIMIT: usize = 16 * 1024;
31
32/// Dictionary tables for attached inputs at one minimum match, sized to the
33/// dictionary content: the Fast table, or the DFast short and long tables.
34/// Empty until built.
35struct Attached {
36    min_match: u32,
37    table: Vec<u32>,
38    long: Vec<u32>,
39}
40
41/// The log of an attached table for a `prefix_len`-byte dictionary, at most
42/// `cap`.
43fn 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
52/// Pre-computed dictionary state for hot-loop compression.
53///
54/// Built once from a [`Dictionary`] + [`LevelParams`]. Holds a combined
55/// buffer with the dict prefix already loaded and encode-side entropy tables
56/// built from the dict's decode tables. The prefilled hash tables are built
57/// by the first input that uses them, so a context that compresses only
58/// inputs of other sizes never builds them.
59pub(crate) struct PreparedDict {
60    /// The dictionary content, then the current input.
61    combined: Vec<u8>,
62    /// The parameters the snapshots are prefilled for.
63    params: LevelParams,
64    /// Empty until built.
65    hash_snapshot: Vec<u32>,
66    hash_long_snapshot: Vec<u32>,
67    /// Dictionary tables for attached inputs, one set per minimum match the
68    /// level uses.
69    attached: Vec<Attached>,
70    /// Logs of the attached Fast or DFast short tables, and of the DFast
71    /// long tables.
72    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    /// Prepares `dict` for `level`, with snapshots for `params`. Builds the
85    /// entropy tables now and the hash tables on first use.
86    pub fn new(dict: &Dictionary, level: i32, params: &LevelParams) -> Self {
87        let prefix = dict.content();
88        let prefix_len = prefix.len();
89
90        // Inputs that take the per-call prefix path never use it, so it grows
91        // to the input on first use.
92        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        // Small inputs at negative levels search with a shorter match.
104        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        // Largest codes: 35 for literal lengths, 31 for offsets, 52 for
122        // match lengths.
123        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    /// Whether `params` use the table sizes the snapshots are built for.
152    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    /// The tables prefilled with the dictionary, built on first use.
161    fn snapshots(&mut self) -> (&[u32], &[u32]) {
162        if self.hash_snapshot.is_empty() {
163            let p = &self.params;
164            // The buffer may still hold the last input after the prefix, and
165            // the Fast prefill hashes up to the end of what it is given.
166            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    /// Whether the level uses attached tables hashed for `min_match`.
198    fn has_attached(&self, min_match: u32) -> bool {
199        self.attached.iter().any(|a| a.min_match == min_match)
200    }
201
202    /// Builds the attached tables hashed for `min_match` if they are missing.
203    fn build_attached(&mut self, min_match: u32) {
204        // Only the prefix, as in `snapshots`.
205        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    /// The attached dictionary tables hashed for `min_match`, once built.
237    fn attached(&self, min_match: u32) -> Option<&Attached> {
238        self.attached.iter().find(|a| a.min_match == min_match)
239    }
240}
241
242/// Reusable compression context that amortizes hash table and buffer allocations.
243///
244/// Holds internal state (hash tables, output buffer, block encoder workspace)
245/// across calls. Useful when compressing many small inputs in a loop.
246///
247/// ```
248/// let mut ctx = zrip::CompressContext::new(1).unwrap();
249/// for i in 0..10 {
250///     let data = format!("message {i}").repeat(100);
251///     let compressed = ctx.compress(data.as_bytes()).unwrap();
252///     assert!(compressed.len() < data.len());
253/// }
254/// ```
255pub struct CompressContext {
256    level: i32,
257    content_checksum: bool,
258    /// The dictionary and expected input size to prepare it again on a
259    /// level change.
260    dict: Option<(Dictionary, usize)>,
261    prepared: Option<PreparedDict>,
262    hash_table: MatchTable,
263    hash_long: MatchTable,
264    dict_hash: MatchTable,
265    /// The input's own tables beside attached dictionary tables: the Fast
266    /// or DFast short table, and the DFast long table.
267    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    /// Creates a new context for the given compression level (-7..=4; -8 runs as -7).
277    ///
278    /// It allocates nothing up front: the first frame sizes the hash tables
279    /// and buffers for its input.
280    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    /// Creates a new context with a pre-loaded dictionary.
300    ///
301    /// The prepared hash table snapshot is for the large-input parameter
302    /// tier, built by the first input that uses it. Inputs whose tiered
303    /// params match its hash sizes use the fast snapshot-restore path.
304    /// Inputs up to 8 KiB, and some other one-block inputs, search the
305    /// dictionary's own tables instead; the rest fall back to per-call
306    /// prefix hashing.
307    ///
308    /// Use [`with_dict_for_size`](Self::with_dict_for_size) to build the
309    /// snapshot for a specific input size tier.
310    pub fn with_dict(level: i32, dict: Dictionary) -> Result<Self, CompressError> {
311        Self::with_dict_for_size(level, dict, usize::MAX)
312    }
313
314    /// Creates a new context with a pre-loaded dictionary, optimized for
315    /// inputs of approximately `expected_size` bytes.
316    ///
317    /// The prepared hash table snapshot is for the parameter tier matching
318    /// `expected_size`, built by the first input that uses it. Inputs in
319    /// the same tier use the fast snapshot-restore path.
320    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, &params);
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    /// The level of the next frame.
347    pub const fn level(&self) -> i32 {
348        self.level
349    }
350
351    /// Switches later frames to `level` (-7..=4; -8 runs as -7).
352    ///
353    /// Hash tables and buffers stay allocated and resize on use. A context
354    /// with a dictionary prepares the dictionary again for the new level.
355    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, &params));
365        }
366        self.level = level;
367        Ok(())
368    }
369
370    /// Enables or disables the standard Zstandard frame content checksum.
371    ///
372    /// Checksums are enabled by default. Disabling them is useful when an
373    /// enclosing format already authenticates the decoded content.
374    pub const fn set_content_checksum(&mut self, enabled: bool) {
375        self.content_checksum = enabled;
376    }
377
378    /// Whether newly compressed frames include a content checksum.
379    pub const fn content_checksum(&self) -> bool {
380        self.content_checksum
381    }
382
383    /// Compresses `input` using the context's level and optional dictionary.
384    ///
385    /// The frame borrows the context's output buffer. A frame of 512 KiB or
386    /// more takes the buffer instead, and the next call allocates a new one.
387    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    /// Compresses `input` into a caller-owned buffer while reusing this
397    /// context's hash tables, workspace, and dictionary.
398    ///
399    /// Writes one frame to the start of `output` and returns its length.
400    /// Unlike [`Self::compress`], the result can outlive the next use of this
401    /// context without copying. `zrip::compress_bound(input.len())` bytes are
402    /// always enough. Returns [`CompressError::OutputTooSmall`] if the frame
403    /// does not fit; `output` then holds a partial frame.
404    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    /// Writes one frame for `input` to `output`.
415    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    /// Compresses `input` using an ad-hoc dictionary (overrides the stored one).
443    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    /// Writes one frame with the prepared dictionary: attached dictionary
484    /// tables, a restored snapshot, or else per-call prefix hashing.
485    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(&params);
497        // An input the snapshot is not sized for also attaches, which beats
498        // prefilling tables per call: any one-block input for Fast, and for
499        // DFast, which probes two dictionary tables per position, up to
500        // C zstd's cutoff for its dfast strategy.
501        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                // The per-call prefix path resizes these tables for its own
521                // parameter tier, so restore length and contents together.
522                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            // The input's own tables, sized to it.
563            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(&params, 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                            &params,
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                            &params,
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(&params, 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                                &params,
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                                &params,
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(&params, 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/// Writes one frame for `input` after an optional dictionary `prefix`, in
806/// the caller's tables and buffers. The caller sets the workspace's
807/// dictionary entropy tables; without a prefix they are cleared here.
808#[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    // Paths that walk the input block by block hash each block right after
847    // compressing it, while its bytes are still in cache.
848    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                        &params,
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(&params, 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                            &params,
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(&params, 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(&params, 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                                &params,
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(&params, 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                        &params,
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(&params, 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                            &params,
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(&params, 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(&params, 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                                &params,
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(&params, 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    /// Blocks reuse a dictionary's sequence tables only when they hold every
1136    /// code the block needs. Encoding a code a table lacks writes garbage.
1137    #[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        // Offset codes 0 to 10 only, as for offsets up to 2 KiB.
1143        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        // Noise, then a copy from 5000 bytes back: offset code 12.
1165        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    /// Tables built while a frame's input follows the dictionary in the
1192    /// buffer match tables built from the dictionary alone.
1193    #[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, &params);
1202            let mut stale = PreparedDict::new(&dict, level, &params);
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}