Skip to main content

zrip_encode/
context.rs

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
20/// Largest input that keeps the dictionary in its own tables instead of
21/// copying the prefilled ones, as C zstd does for its fast and dfast
22/// strategies. Past it, copying the tables costs less than the dictionary
23/// probes.
24const ATTACH_THRESHOLD: usize = 8192;
25
26/// Largest DFast input that attaches the dictionary when its prefilled
27/// tables are sized for other inputs.
28const DFAST_ATTACH_LIMIT: usize = 16 * 1024;
29
30/// Dictionary tables for attached inputs at one minimum match, sized to the
31/// dictionary content: the Fast table, or the DFast short and long tables.
32/// Empty until built.
33struct Attached {
34    min_match: u32,
35    table: Vec<u32>,
36    long: Vec<u32>,
37}
38
39/// The log of an attached table for a `prefix_len`-byte dictionary, at most
40/// `cap`.
41fn 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
50/// Pre-computed dictionary state for hot-loop compression.
51///
52/// Built once from a [`Dictionary`] + [`LevelParams`]. Holds a combined
53/// buffer with the dict prefix already loaded and encode-side entropy tables
54/// built from the dict's decode tables. The prefilled hash tables are built
55/// by the first input that uses them, so a context that compresses only
56/// inputs of other sizes never builds them.
57pub(crate) struct PreparedDict {
58    combined: Vec<u8>,
59    /// The parameters the snapshots are prefilled for.
60    params: LevelParams,
61    /// Empty until built.
62    hash_snapshot: Vec<u32>,
63    hash_long_snapshot: Vec<u32>,
64    /// Dictionary tables for attached inputs, one set per minimum match the
65    /// level uses.
66    attached: Vec<Attached>,
67    /// Logs of the attached Fast or DFast short tables, and of the DFast
68    /// long tables.
69    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        // Inputs that take the per-call prefix path never use it, so it grows
86        // to the input on first use.
87        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        // Small inputs at negative levels search with a shorter match.
99        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    /// Whether `params` use the table sizes the snapshots are built for.
145    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    /// The tables prefilled with the dictionary, built on first use.
154    fn snapshots(&mut self) -> (&[u32], &[u32]) {
155        if self.hash_snapshot.is_empty() {
156            let p = &self.params;
157            // The buffer may still hold the last input after the prefix, and
158            // the Fast prefill hashes up to the end of what it is given.
159            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    /// Whether the level uses attached tables hashed for `min_match`.
191    fn has_attached(&self, min_match: u32) -> bool {
192        self.attached.iter().any(|a| a.min_match == min_match)
193    }
194
195    /// Builds the attached tables hashed for `min_match` if they are missing.
196    fn build_attached(&mut self, min_match: u32) {
197        // Only the prefix, as in `snapshots`.
198        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    /// The attached dictionary tables hashed for `min_match`, once built.
230    fn attached(&self, min_match: u32) -> Option<&Attached> {
231        self.attached.iter().find(|a| a.min_match == min_match)
232    }
233}
234
235/// Reusable compression context that amortizes hash table and buffer allocations.
236///
237/// Holds internal state (hash tables, output buffer, block encoder workspace)
238/// across calls. Useful when compressing many small inputs in a loop.
239///
240/// ```
241/// let mut ctx = zrip::CompressContext::new(1).unwrap();
242/// for i in 0..10 {
243///     let data = format!("message {i}").repeat(100);
244///     let compressed = ctx.compress(data.as_bytes()).unwrap();
245///     assert!(compressed.len() < data.len());
246/// }
247/// ```
248pub struct CompressContext {
249    level: i32,
250    content_checksum: bool,
251    /// The dictionary and expected input size to prepare it again on a
252    /// level change.
253    dict: Option<(Dictionary, usize)>,
254    prepared: Option<PreparedDict>,
255    hash_table: MatchTable,
256    hash_long: MatchTable,
257    dict_hash: MatchTable,
258    /// The input's own tables beside attached dictionary tables: the Fast
259    /// or DFast short table, and the DFast long table.
260    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    /// Creates a new context for the given compression level (-7..=4; -8 runs as -7).
270    ///
271    /// It allocates nothing up front: the first frame sizes the hash tables
272    /// and buffers for its input.
273    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    /// Creates a new context with a pre-loaded dictionary.
293    ///
294    /// The prepared hash table snapshot is for the T0 (>256 KB) parameter
295    /// tier, built by the first input that uses it. Inputs whose tiered
296    /// params match T0's hash sizes use the fast snapshot-restore path;
297    /// others fall back to per-call prefix hashing.
298    ///
299    /// Use [`with_dict_for_size`] to build the snapshot for a specific
300    /// input size tier.
301    pub fn with_dict(level: i32, dict: Dictionary) -> Result<Self, CompressError> {
302        Self::with_dict_for_size(level, dict, usize::MAX)
303    }
304
305    /// Creates a new context with a pre-loaded dictionary, optimized for
306    /// inputs of approximately `expected_size` bytes.
307    ///
308    /// The prepared hash table snapshot is for the parameter tier matching
309    /// `expected_size`, built by the first input that uses it. Inputs in
310    /// the same tier use the fast snapshot-restore path.
311    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, &params);
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    /// The level of the next frame.
338    pub const fn level(&self) -> i32 {
339        self.level
340    }
341
342    /// Switches later frames to `level` (-7..=4; -8 runs as -7).
343    ///
344    /// Hash tables and buffers stay allocated and resize on use. A context
345    /// with a dictionary prepares the dictionary again for the new level.
346    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, &params));
356        }
357        self.level = level;
358        Ok(())
359    }
360
361    /// Enables or disables the standard Zstandard frame content checksum.
362    ///
363    /// Checksums are enabled by default. Disabling them is useful when an
364    /// enclosing format already authenticates the decoded content.
365    pub const fn set_content_checksum(&mut self, enabled: bool) {
366        self.content_checksum = enabled;
367    }
368
369    /// Whether newly compressed frames include a content checksum.
370    pub const fn content_checksum(&self) -> bool {
371        self.content_checksum
372    }
373
374    /// Compresses `input` using the context's level and optional dictionary.
375    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    /// Compresses `input` into a caller-owned buffer while reusing this
385    /// context's hash tables, workspace, and dictionary.
386    ///
387    /// Writes one frame to the start of `output` and returns its length.
388    /// Unlike [`Self::compress`], the result can outlive the next use of this
389    /// context without copying. `zrip::compress_bound(input.len())` bytes are
390    /// always enough. Returns [`CompressError::OutputTooSmall`] if the frame
391    /// does not fit; `output` then holds a partial frame.
392    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    /// Writes one frame for `input` to `output`.
403    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    /// Compresses `input` using an ad-hoc dictionary (overrides the stored one).
431    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(&params);
482        // An input the snapshot is not sized for also attaches, which beats
483        // prefilling tables per call: any one-block input for Fast, and for
484        // DFast, which probes two dictionary tables per position, up to
485        // C zstd's cutoff for its dfast strategy.
486        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                // The per-call prefix path resizes these tables for its own
506                // parameter tier, so restore length and contents together.
507                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            // The input's own tables, sized to it.
547            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(&params, 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                            &params,
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                            &params,
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(&params, 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                                &params,
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                                &params,
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(&params, 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    // Paths that walk the input block by block hash each block right after
828    // compressing it, while its bytes are still in cache.
829    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                        &params,
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(&params, 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                            &params,
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(&params, 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(&params, 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                                &params,
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(&params, 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                        &params,
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(&params, 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                            &params,
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(&params, 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(&params, 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                                &params,
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(&params, 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    /// Blocks reuse a dictionary's sequence tables only when they hold every
1117    /// code the block needs. Encoding a code a table lacks writes garbage.
1118    #[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        // Offset codes 0 to 10 only, as for offsets up to 2 KiB.
1124        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        // Noise, then a copy from 5000 bytes back: offset code 12.
1146        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    /// Tables built while a frame's input follows the dictionary in the
1173    /// buffer match tables built from the dictionary alone.
1174    #[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, &params);
1183            let mut stale = PreparedDict::new(&dict, level, &params);
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}