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.set_prev_huffman(
449            dict.huf_table()
450                .and_then(|(dt, tl)| HuffmanEncodeTable::from_decode_table(dt, tl)),
451        );
452        self.output.clear();
453        compress_core(
454            input,
455            params,
456            Some(dict.id()),
457            dict.content(),
458            *dict.rep_offsets(),
459            &mut self.hash_table,
460            &mut self.hash_long,
461            &mut self.dict_hash,
462            &mut self.sequences,
463            &mut self.output,
464            &mut self.workspace,
465            &mut self.combined,
466            self.content_checksum,
467        )?;
468        Ok(self.take_or_borrow_output())
469    }
470
471    fn compress_with_prepared<S: OutputSink>(
472        &mut self,
473        input: &[u8],
474        output: &mut S,
475    ) -> Result<(), CompressError> {
476        let prep = self.prepared.as_ref().unwrap();
477        let params = strategy::level_params_with_prefix(self.level, prep.prefix_len, input.len())
478            .expect("level validated at construction");
479
480        let dict_id = prep.dict_id;
481        let prefix_len = prep.prefix_len;
482        let snapshot_matches = prep.snapshot_matches(&params);
483        // An input the snapshot is not sized for also attaches, which beats
484        // prefilling tables per call: any one-block input for Fast, and for
485        // DFast, which probes two dictionary tables per position, up to
486        // C zstd's cutoff for its dfast strategy.
487        let other_tier = !snapshot_matches
488            && match params.strategy {
489                Strategy::Fast => true,
490                Strategy::DFast => input.len() <= DFAST_ATTACH_LIMIT,
491            };
492        let use_attached = !input.is_empty()
493            && input.len() <= MAX_BLOCK_SIZE
494            && (input.len() <= ATTACH_THRESHOLD || other_tier)
495            && prep.has_attached(params.min_match);
496
497        if !use_attached && !snapshot_matches {
498            return self.compress_with_dict_fallback(input, dict_id, prefix_len, output);
499        }
500
501        {
502            let prep = self.prepared.as_mut().unwrap();
503            if use_attached {
504                prep.build_attached(params.min_match);
505            } else {
506                // The per-call prefix path resizes these tables for its own
507                // parameter tier, so restore length and contents together.
508                let (short, long) = prep.snapshots();
509                self.hash_table.copy_from(short);
510                if !long.is_empty() {
511                    self.hash_long.copy_from(long);
512                }
513            }
514            prep.combined.truncate(prep.prefix_len);
515            prep.combined.extend_from_slice(input);
516        }
517
518        let prep = self.prepared.as_ref().unwrap();
519
520        if use_attached {
521            self.workspace
522                .set_prev_huffman(if params.force_raw_literals {
523                    None
524                } else {
525                    prep.huf_table.clone()
526                });
527        } else if let Some(ref huf) = prep.huf_table {
528            self.workspace.set_prev_huffman(Some(huf.clone()));
529        } else {
530            self.workspace.set_prev_huffman(None);
531        }
532        self.workspace.prev_ll = prep.ll_table.clone();
533        self.workspace.prev_of = prep.of_table.clone();
534        self.workspace.prev_ml = prep.ml_table.clone();
535
536        output.reserve(input.len() + 32);
537        write_frame_header_with_checksum(
538            output,
539            input.len(),
540            Some(dict_id),
541            params.window_log,
542            self.content_checksum,
543        )?;
544
545        if input.is_empty() {
546            block_encoder::encode_raw_block(&[], true, output)?;
547        } else if use_attached {
548            // The input's own tables, sized to it.
549            let input_log = |cap: u32| {
550                if input.len() >= 2 {
551                    cap.min(strategy::src_log(input.len()))
552                        .max(strategy::HASH_LOG_MIN)
553                } else {
554                    strategy::HASH_LOG_MIN
555                }
556            };
557            let input_params = LevelParams {
558                hash_log: input_log(params.hash_log),
559                chain_log: input_log(params.chain_log),
560                ..params
561            };
562            let mut rep_offsets = prep.rep_offsets;
563            let tables = prep.attached(params.min_match).unwrap();
564            let block_end = prefix_len + input.len();
565            match params.strategy {
566                Strategy::Fast => {
567                    self.small_hash.clear(1usize << input_params.hash_log);
568                    let dict = AttachedDict {
569                        table: &tables.table,
570                        hash_log: prep.attached_hash_log,
571                        prefix_len,
572                    };
573                    fast::compress_fast_block_attached(
574                        &prep.combined,
575                        block_end,
576                        &input_params,
577                        &prep.rep_offsets,
578                        dict,
579                        &mut self.small_hash,
580                        &mut self.sequences,
581                    );
582                }
583                Strategy::DFast => {
584                    self.small_hash.clear(1usize << input_params.chain_log);
585                    self.small_long.clear(1usize << input_params.hash_log);
586                    let dict = dfast::AttachedDfastDict {
587                        short: &tables.table,
588                        long: &tables.long,
589                        short_log: prep.attached_hash_log,
590                        long_log: prep.attached_long_log,
591                        prefix_len,
592                    };
593                    dfast::compress_dfast_block_attached(
594                        &prep.combined,
595                        block_end,
596                        &input_params,
597                        &prep.rep_offsets,
598                        dict,
599                        &mut self.small_hash,
600                        &mut self.small_long,
601                        &mut self.sequences,
602                    );
603                }
604            }
605
606            if params.force_raw_literals {
607                block_encoder::encode_compressed_block_raw(
608                    input,
609                    &self.sequences,
610                    &mut rep_offsets,
611                    true,
612                    output,
613                    &mut self.workspace,
614                )?;
615            } else {
616                block_encoder::encode_compressed_block(
617                    input,
618                    &self.sequences,
619                    &mut rep_offsets,
620                    true,
621                    output,
622                    &mut self.workspace,
623                    strategy::block_policy(&params, input.len()),
624                )?;
625            }
626        } else {
627            let combined = &prep.combined;
628            let mut rep_offsets = prep.rep_offsets;
629
630            if input.len() <= MAX_BLOCK_SIZE {
631                match params.strategy {
632                    Strategy::Fast => {
633                        fast::compress_fast_block(
634                            combined,
635                            prefix_len,
636                            prefix_len + input.len(),
637                            &params,
638                            &rep_offsets,
639                            &mut self.hash_table,
640                            &mut self.sequences,
641                        );
642                    }
643                    Strategy::DFast => {
644                        dfast::compress_dfast_block(
645                            combined,
646                            prefix_len,
647                            prefix_len + input.len(),
648                            &params,
649                            &rep_offsets,
650                            &mut self.hash_table,
651                            &mut self.hash_long,
652                            &mut self.sequences,
653                        );
654                    }
655                }
656                if params.force_raw_literals {
657                    block_encoder::encode_compressed_block_raw(
658                        input,
659                        &self.sequences,
660                        &mut rep_offsets,
661                        true,
662                        output,
663                        &mut self.workspace,
664                    )?;
665                } else {
666                    block_encoder::encode_compressed_block(
667                        input,
668                        &self.sequences,
669                        &mut rep_offsets,
670                        true,
671                        output,
672                        &mut self.workspace,
673                        strategy::block_policy(&params, input.len()),
674                    )?;
675                }
676            } else {
677                let mut positions = PositionBase::new(params.window_log);
678                let mut offset = 0;
679                while offset < input.len() {
680                    let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
681                    let is_last = offset + chunk_size >= input.len();
682                    let (start, end) = (prefix_len + offset, prefix_len + offset + chunk_size);
683                    if let Some(shift) = positions.advance(start, end) {
684                        rebase::reduce_hash_table(&mut self.hash_table, shift);
685                        rebase::reduce_hash_table(&mut self.hash_long, shift);
686                    }
687                    let base = positions.base();
688                    let src = &combined[base..];
689                    match params.strategy {
690                        Strategy::Fast => {
691                            fast::compress_fast_block(
692                                src,
693                                start - base,
694                                end - base,
695                                &params,
696                                &rep_offsets,
697                                &mut self.hash_table,
698                                &mut self.sequences,
699                            );
700                        }
701                        Strategy::DFast => {
702                            dfast::compress_dfast_block(
703                                src,
704                                start - base,
705                                end - base,
706                                &params,
707                                &rep_offsets,
708                                &mut self.hash_table,
709                                &mut self.hash_long,
710                                &mut self.sequences,
711                            );
712                        }
713                    }
714                    if params.force_raw_literals {
715                        block_encoder::encode_compressed_block_raw(
716                            &input[offset..offset + chunk_size],
717                            &self.sequences,
718                            &mut rep_offsets,
719                            is_last,
720                            output,
721                            &mut self.workspace,
722                        )?;
723                    } else {
724                        block_encoder::encode_compressed_block(
725                            &input[offset..offset + chunk_size],
726                            &self.sequences,
727                            &mut rep_offsets,
728                            is_last,
729                            output,
730                            &mut self.workspace,
731                            strategy::block_policy(&params, input.len()),
732                        )?;
733                    }
734                    offset += chunk_size;
735                }
736            }
737        }
738
739        if self.content_checksum {
740            let hash = xxh64(input, 0);
741            let checksum = (hash & 0xFFFF_FFFF) as u32;
742            output.extend_from_slice(&checksum.to_le_bytes())?;
743        }
744
745        Ok(())
746    }
747
748    fn compress_with_dict_fallback<S: OutputSink>(
749        &mut self,
750        input: &[u8],
751        dict_id: u32,
752        prefix_len: usize,
753        output: &mut S,
754    ) -> Result<(), CompressError> {
755        let prep = self.prepared.as_ref().unwrap();
756        let rep_offsets = prep.rep_offsets;
757        let prefix = &prep.combined[..prefix_len];
758
759        let params = strategy::level_params_with_prefix(self.level, prefix_len, input.len())
760            .expect("level validated at construction");
761        self.workspace.set_prev_huffman(prep.huf_table.clone());
762        self.workspace.prev_ll = prep.ll_table.clone();
763        self.workspace.prev_of = prep.of_table.clone();
764        self.workspace.prev_ml = prep.ml_table.clone();
765        compress_core(
766            input,
767            params,
768            Some(dict_id),
769            prefix,
770            rep_offsets,
771            &mut self.hash_table,
772            &mut self.hash_long,
773            &mut self.dict_hash,
774            &mut self.sequences,
775            output,
776            &mut self.workspace,
777            &mut self.combined,
778            self.content_checksum,
779        )
780    }
781
782    fn take_or_borrow_output(&mut self) -> Cow<'_, [u8]> {
783        if self.output.len() >= zrip_core::LARGE_OUTPUT_THRESHOLD {
784            Cow::Owned(core::mem::take(&mut self.output))
785        } else {
786            Cow::Borrowed(&self.output)
787        }
788    }
789}
790
791#[allow(clippy::too_many_arguments, clippy::unnecessary_wraps)]
792pub(crate) fn compress_core<S: OutputSink>(
793    input: &[u8],
794    params: LevelParams,
795    dict_id: Option<u32>,
796    prefix: &[u8],
797    init_rep_offsets: [u32; 3],
798    hash_table: &mut MatchTable,
799    hash_long: &mut MatchTable,
800    dict_hash: &mut MatchTable,
801    sequences: &mut Vec<Sequence>,
802    output: &mut S,
803    workspace: &mut BlockEncodeWorkspace,
804    combined: &mut Vec<u8>,
805    content_checksum: bool,
806) -> Result<(), CompressError> {
807    let hash_size = match params.strategy {
808        Strategy::Fast => 1usize << params.hash_log,
809        Strategy::DFast => 1usize << params.chain_log,
810    };
811    let long_size = 1usize << params.hash_log;
812
813    if prefix.is_empty() {
814        workspace.set_prev_huffman(None);
815        workspace.prev_ll = None;
816        workspace.prev_of = None;
817        workspace.prev_ml = None;
818    }
819
820    output.reserve(input.len() + 32);
821    write_frame_header_with_checksum(
822        output,
823        input.len(),
824        dict_id,
825        params.window_log,
826        content_checksum,
827    )?;
828
829    // Paths that walk the input block by block hash each block right after
830    // compressing it, while its bytes are still in cache.
831    let mut checksum = content_checksum.then(|| Xxh64State::new(0));
832    let mut hashed_blocks = false;
833
834    if input.is_empty() {
835        block_encoder::encode_raw_block(&[], true, output)?;
836    } else {
837        let has_prefix = !prefix.is_empty();
838        let mut rep_offsets = init_rep_offsets;
839        let mut offset = 0;
840        let mut positions = PositionBase::new(params.window_log);
841
842        match params.strategy {
843            Strategy::Fast => {
844                if has_prefix && input.len() <= MAX_BLOCK_SIZE {
845                    fast::compress_fast_with_prefix_reuse(
846                        input,
847                        &params,
848                        &rep_offsets,
849                        prefix,
850                        dict_hash,
851                        hash_table,
852                        sequences,
853                        combined,
854                    );
855                    if params.force_raw_literals {
856                        block_encoder::encode_compressed_block_raw(
857                            input,
858                            sequences,
859                            &mut rep_offsets,
860                            true,
861                            output,
862                            workspace,
863                        )?;
864                    } else {
865                        block_encoder::encode_compressed_block(
866                            input,
867                            sequences,
868                            &mut rep_offsets,
869                            true,
870                            output,
871                            workspace,
872                            strategy::block_policy(&params, input.len()),
873                        )?;
874                    }
875                } else if has_prefix {
876                    combined.clear();
877                    combined.reserve(prefix.len() + input.len());
878                    combined.extend_from_slice(prefix);
879                    combined.extend_from_slice(input);
880                    let plen = prefix.len();
881                    fast::prefill_hash_table(
882                        combined,
883                        plen,
884                        params.hash_log,
885                        params.min_match,
886                        hash_table,
887                    );
888
889                    while offset < input.len() {
890                        let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
891                        let is_last = offset + chunk_size >= input.len();
892                        let (start, end) = (plen + offset, plen + offset + chunk_size);
893                        if let Some(shift) = positions.advance(start, end) {
894                            rebase::reduce_hash_table(hash_table, shift);
895                        }
896                        let base = positions.base();
897                        fast::compress_fast_block(
898                            &combined[base..],
899                            start - base,
900                            end - base,
901                            &params,
902                            &rep_offsets,
903                            hash_table,
904                            sequences,
905                        );
906                        if params.force_raw_literals {
907                            block_encoder::encode_compressed_block_raw(
908                                &input[offset..offset + chunk_size],
909                                sequences,
910                                &mut rep_offsets,
911                                is_last,
912                                output,
913                                workspace,
914                            )?;
915                        } else {
916                            block_encoder::encode_compressed_block(
917                                &input[offset..offset + chunk_size],
918                                sequences,
919                                &mut rep_offsets,
920                                is_last,
921                                output,
922                                workspace,
923                                strategy::block_policy(&params, input.len()),
924                            )?;
925                        }
926                        offset += chunk_size;
927                    }
928                } else {
929                    hash_table.clear(hash_size);
930                    while offset < input.len() {
931                        let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
932                        let block_end = offset + chunk_size;
933                        let is_last = block_end >= input.len();
934                        let block = &input[offset..block_end];
935
936                        if let Some(shift) = positions.advance(offset, block_end) {
937                            rebase::reduce_hash_table(hash_table, shift);
938                        }
939                        if skip_match_search(&params, input.len(), block) {
940                            block_encoder::encode_raw_block(block, is_last, output)?;
941                        } else {
942                            let base = positions.base();
943                            fast::compress_fast_block(
944                                &input[base..],
945                                offset - base,
946                                block_end - base,
947                                &params,
948                                &rep_offsets,
949                                hash_table,
950                                sequences,
951                            );
952                            if params.force_raw_literals {
953                                block_encoder::encode_compressed_block_raw(
954                                    block,
955                                    sequences,
956                                    &mut rep_offsets,
957                                    is_last,
958                                    output,
959                                    workspace,
960                                )?;
961                            } else {
962                                block_encoder::encode_compressed_block(
963                                    block,
964                                    sequences,
965                                    &mut rep_offsets,
966                                    is_last,
967                                    output,
968                                    workspace,
969                                    strategy::block_policy(&params, input.len()),
970                                )?;
971                            }
972                        }
973                        if let Some(c) = checksum.as_mut() {
974                            c.update(block);
975                        }
976                        offset = block_end;
977                    }
978                    hashed_blocks = true;
979                }
980            }
981            Strategy::DFast => {
982                if has_prefix && input.len() <= MAX_BLOCK_SIZE {
983                    dfast::compress_dfast_with_prefix_reuse(
984                        input,
985                        &params,
986                        &rep_offsets,
987                        prefix,
988                        hash_table,
989                        hash_long,
990                        sequences,
991                        combined,
992                    );
993                    block_encoder::encode_compressed_block(
994                        input,
995                        sequences,
996                        &mut rep_offsets,
997                        true,
998                        output,
999                        workspace,
1000                        strategy::block_policy(&params, input.len()),
1001                    )?;
1002                } else if has_prefix {
1003                    combined.clear();
1004                    combined.reserve(prefix.len() + input.len());
1005                    combined.extend_from_slice(prefix);
1006                    combined.extend_from_slice(input);
1007                    let plen = prefix.len();
1008                    dfast::prefill_hash_tables(
1009                        combined,
1010                        plen,
1011                        params.hash_log,
1012                        params.chain_log,
1013                        params.min_match,
1014                        hash_table,
1015                        hash_long,
1016                    );
1017
1018                    while offset < input.len() {
1019                        let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
1020                        let is_last = offset + chunk_size >= input.len();
1021                        let (start, end) = (plen + offset, plen + offset + chunk_size);
1022                        if let Some(shift) = positions.advance(start, end) {
1023                            rebase::reduce_hash_table(hash_table, shift);
1024                            rebase::reduce_hash_table(hash_long, shift);
1025                        }
1026                        let base = positions.base();
1027                        dfast::compress_dfast_block(
1028                            &combined[base..],
1029                            start - base,
1030                            end - base,
1031                            &params,
1032                            &rep_offsets,
1033                            hash_table,
1034                            hash_long,
1035                            sequences,
1036                        );
1037                        block_encoder::encode_compressed_block(
1038                            &input[offset..offset + chunk_size],
1039                            sequences,
1040                            &mut rep_offsets,
1041                            is_last,
1042                            output,
1043                            workspace,
1044                            strategy::block_policy(&params, input.len()),
1045                        )?;
1046                        offset += chunk_size;
1047                    }
1048                } else {
1049                    hash_table.clear(hash_size);
1050                    hash_long.clear(long_size);
1051                    while offset < input.len() {
1052                        let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
1053                        let block_end = offset + chunk_size;
1054                        let is_last = block_end >= input.len();
1055                        let block = &input[offset..block_end];
1056
1057                        if let Some(shift) = positions.advance(offset, block_end) {
1058                            rebase::reduce_hash_table(hash_table, shift);
1059                            rebase::reduce_hash_table(hash_long, shift);
1060                        }
1061                        if skip_match_search(&params, input.len(), block) {
1062                            block_encoder::encode_raw_block(block, is_last, output)?;
1063                        } else {
1064                            let base = positions.base();
1065                            dfast::compress_dfast_block(
1066                                &input[base..],
1067                                offset - base,
1068                                block_end - base,
1069                                &params,
1070                                &rep_offsets,
1071                                hash_table,
1072                                hash_long,
1073                                sequences,
1074                            );
1075                            block_encoder::encode_compressed_block(
1076                                block,
1077                                sequences,
1078                                &mut rep_offsets,
1079                                is_last,
1080                                output,
1081                                workspace,
1082                                strategy::block_policy(&params, input.len()),
1083                            )?;
1084                        }
1085                        if let Some(c) = checksum.as_mut() {
1086                            c.update(block);
1087                        }
1088                        offset = block_end;
1089                    }
1090                    hashed_blocks = true;
1091                }
1092            }
1093        }
1094    }
1095
1096    if let Some(c) = checksum {
1097        let hash = if hashed_blocks {
1098            c.finish()
1099        } else {
1100            xxh64(input, 0)
1101        };
1102        output.extend_from_slice(&((hash & 0xFFFF_FFFF) as u32).to_le_bytes())?;
1103    }
1104
1105    Ok(())
1106}
1107
1108#[cfg(test)]
1109mod tests {
1110    use super::*;
1111
1112    fn dict() -> Dictionary {
1113        let fixture = include_bytes!("../../../tests/fixtures/corpus_dict_roundtrip.bin");
1114        let len = u32::from_le_bytes([fixture[0], fixture[1], fixture[2], fixture[3]]) as usize;
1115        Dictionary::from_bytes(&fixture[4..4 + len]).unwrap()
1116    }
1117
1118    /// Blocks reuse a dictionary's sequence tables only when they hold every
1119    /// code the block needs. Encoding a code a table lacks writes garbage.
1120    #[test]
1121    fn dictionary_tables_lacking_a_code_are_not_reused() {
1122        use zrip_core::fse::table_builder::serialize_fse_table_description;
1123        use zrip_core::fse::{LL_DEFAULT_ACCURACY, LL_DEFAULT_DIST};
1124        use zrip_core::fse::{ML_DEFAULT_ACCURACY, ML_DEFAULT_DIST};
1125        // Offset codes 0 to 10 only, as for offsets up to 2 KiB.
1126        const OF_DIST: [i16; 11] = [1, 1, 1, 1, 3, 3, 3, 3, 6, 6, 4];
1127        let mut raw = Vec::new();
1128        raw.extend_from_slice(&zrip_core::dict::DICT_MAGIC.to_le_bytes());
1129        raw.extend_from_slice(&7u32.to_le_bytes());
1130        raw.extend_from_slice(&[128 + 1, 0x11]);
1131        raw.extend(serialize_fse_table_description(&OF_DIST, 5));
1132        raw.extend(serialize_fse_table_description(
1133            &ML_DEFAULT_DIST,
1134            ML_DEFAULT_ACCURACY,
1135        ));
1136        raw.extend(serialize_fse_table_description(
1137            &LL_DEFAULT_DIST,
1138            LL_DEFAULT_ACCURACY,
1139        ));
1140        for rep in [1u32, 4, 8] {
1141            raw.extend_from_slice(&rep.to_le_bytes());
1142        }
1143        raw.extend((0..1024u32).map(|i| (i * 7 % 251) as u8));
1144        let dict = Dictionary::from_bytes(&raw).unwrap();
1145        assert!(dict.of_table().is_some());
1146
1147        // Noise, then a copy from 5000 bytes back: offset code 12.
1148        let mut x = 0x2545_f491u32;
1149        let mut input: Vec<u8> = (0..5000)
1150            .map(|_| {
1151                x ^= x << 13;
1152                x ^= x >> 17;
1153                x ^= x << 5;
1154                x as u8
1155            })
1156            .collect();
1157        input.extend_from_within(..2048);
1158        for level in [1, 3] {
1159            let frames = [
1160                CompressContext::with_dict(level, dict.clone())
1161                    .unwrap()
1162                    .compress(&input)
1163                    .unwrap()
1164                    .into_owned(),
1165                crate::compress_with_dict(&input, level, &dict).unwrap(),
1166            ];
1167            for frame in &frames {
1168                let out = zrip::decompress_with_dict(frame, &dict).unwrap();
1169                assert!(out == input, "L{level}: frame decodes to another input");
1170            }
1171        }
1172    }
1173
1174    /// Tables built while a frame's input follows the dictionary in the
1175    /// buffer match tables built from the dictionary alone.
1176    #[test]
1177    fn dictionary_tables_ignore_buffered_input() {
1178        let dict = dict();
1179        let input: Vec<u8> = (0..4096u32)
1180            .map(|i| (i.wrapping_mul(0x9e37_79b1) >> 24) as u8)
1181            .collect();
1182        for level in -7..=4 {
1183            let params = strategy::level_params(level).unwrap();
1184            let mut clean = PreparedDict::new(&dict, level, &params);
1185            let mut stale = PreparedDict::new(&dict, level, &params);
1186            stale.combined.extend_from_slice(&input);
1187            assert!(clean.snapshots() == stale.snapshots(), "L{level} snapshots");
1188            let mlss: Vec<u32> = clean.attached.iter().map(|a| a.min_match).collect();
1189            for mls in mlss {
1190                clean.build_attached(mls);
1191                stale.build_attached(mls);
1192                let (c, s) = (clean.attached(mls).unwrap(), stale.attached(mls).unwrap());
1193                assert!(
1194                    c.table == s.table && c.long == s.long,
1195                    "L{level} attached tables for min match {mls}"
1196                );
1197            }
1198        }
1199    }
1200}