Skip to main content

zrip_encode/
lib.rs

1//! zstd encoder of [zrip](https://crates.io/crates/zrip): levels -7 to 4,
2//! the Fast and DFast match finders, the block encoder, and the one-shot,
3//! context, streaming and push APIs. Use `zrip` unless you need only the
4//! compressor.
5#![cfg_attr(not(feature = "std"), no_std)]
6#![cfg_attr(feature = "nightly", feature(optimize_attribute))]
7#![forbid(unsafe_code)]
8// Tests build tables and buffers freely; the library goes through `MatchTable`.
9#![cfg_attr(test, allow(clippy::disallowed_methods))]
10
11#[cfg(feature = "alloc")]
12extern crate alloc;
13
14/// Evaluates `$body` compiled for x86-64-v3 (AVX2, BMI1/2, LZCNT) when the CPU
15/// supports it, and compiled for the build target otherwise.
16///
17/// Use it as a whole function body around a call to an `#[inline(always)]`
18/// implementation, so the implementation is duplicated into both contexts.
19/// `fearless_simd` selects the level at runtime and provides the safe
20/// target-feature entry point.
21#[cfg(all(feature = "simd", target_arch = "x86_64", not(target_feature = "avx2")))]
22macro_rules! simd_body {
23    ($body:expr) => {
24        match fearless_simd::Level::new().as_avx2() {
25            Some(avx2) => fearless_simd::Simd::vectorize(
26                avx2,
27                #[inline(always)]
28                || $body,
29            ),
30            None => $body,
31        }
32    };
33}
34
35#[cfg(not(all(feature = "simd", target_arch = "x86_64", not(target_feature = "avx2"))))]
36macro_rules! simd_body {
37    ($body:expr) => {
38        $body
39    };
40}
41
42pub mod adaptive;
43pub(crate) mod block_encoder;
44#[cfg(feature = "alloc")]
45pub mod context;
46pub(crate) mod dfast;
47pub(crate) mod fast;
48#[cfg(feature = "alloc")]
49pub(crate) mod frame_state;
50#[cfg(feature = "ldm")]
51pub(crate) mod ldm;
52mod output;
53pub(crate) mod primitives;
54#[cfg(feature = "alloc")]
55pub mod push;
56pub(crate) mod rebase;
57pub mod strategy;
58#[cfg(feature = "std")]
59pub mod streaming;
60#[cfg(feature = "alloc")]
61pub(crate) mod table;
62
63#[cfg(feature = "alloc")]
64use crate::table::MatchTable;
65#[cfg(feature = "alloc")]
66use alloc::vec::Vec;
67
68use crate::output::{OutputSink, SliceSink};
69use crate::rebase::PositionBase;
70use crate::strategy::Strategy;
71use zrip_core::error::CompressError;
72use zrip_core::frame::{MAX_BLOCK_SIZE, MAX_WINDOW_SIZE, ZSTD_MAGIC};
73use zrip_core::xxhash::xxh64;
74
75pub(crate) fn write_frame_header(
76    output: &mut impl OutputSink,
77    content_size: usize,
78    dict_id: Option<u32>,
79    window_log: u32,
80) -> Result<(), CompressError> {
81    write_frame_header_inner(output, Some(content_size), dict_id, window_log, true)
82}
83
84#[cfg_attr(not(feature = "std"), allow(dead_code))]
85pub(crate) fn write_frame_header_with_checksum(
86    output: &mut impl OutputSink,
87    content_size: usize,
88    dict_id: Option<u32>,
89    window_log: u32,
90    content_checksum: bool,
91) -> Result<(), CompressError> {
92    write_frame_header_inner(
93        output,
94        Some(content_size),
95        dict_id,
96        window_log,
97        content_checksum,
98    )
99}
100
101#[cfg_attr(not(feature = "std"), allow(dead_code))]
102pub(crate) fn write_frame_header_without_content_size(
103    output: &mut impl OutputSink,
104    dict_id: Option<u32>,
105    window_log: u32,
106) -> Result<(), CompressError> {
107    write_frame_header_inner(output, None, dict_id, window_log, true)
108}
109
110fn write_frame_header_inner(
111    output: &mut impl OutputSink,
112    content_size: Option<usize>,
113    dict_id: Option<u32>,
114    window_log: u32,
115    content_checksum: bool,
116) -> Result<(), CompressError> {
117    output.extend_from_slice(&ZSTD_MAGIC.to_le_bytes())?;
118
119    // As in C zstd, a dictionary frame is single-segment when its window
120    // covers the content: decoders keep the dictionary beside the window.
121    let single_segment = content_size.is_some_and(|size| {
122        fits_single_segment(size) && (dict_id.is_none() || size <= 1usize << window_log)
123    });
124    let fcs_size = content_size.map_or(0, |size| {
125        frame_content_size_field_size(size, single_segment)
126    });
127    // Flag 0 means a 1-byte field in single-segment frames, else none.
128    let fcs_flag: u8 = match fcs_size {
129        0 => 0,
130        1 => 0,
131        2 => 1,
132        4 => 2,
133        _ => 3,
134    };
135
136    let dict_id_flag: u8 = match dict_id {
137        None => 0,
138        Some(id) if id <= 0xFF => 1,
139        Some(id) if id <= 0xFFFF => 2,
140        Some(_) => 3,
141    };
142
143    // Frame_Header_Descriptor: content size flag in bits 6-7,
144    // Single_Segment in bit 5, Content_Checksum in bit 2, dictionary ID
145    // flag in bits 0-1.
146    let descriptor = if single_segment { 0x20 } else { 0 }
147        | if content_checksum { 0x04 } else { 0 }
148        | (fcs_flag << 6)
149        | dict_id_flag;
150    output.push(descriptor)?;
151
152    if !single_segment {
153        output.push(window_descriptor_for_log(window_log))?;
154    }
155
156    match dict_id {
157        Some(id) if id <= 0xFF => output.push(id as u8)?,
158        Some(id) if id <= 0xFFFF => output.extend_from_slice(&(id as u16).to_le_bytes())?,
159        Some(id) => output.extend_from_slice(&id.to_le_bytes())?,
160        None => {}
161    }
162
163    let Some(content_size) = content_size else {
164        return Ok(());
165    };
166    match fcs_size {
167        0 => {}
168        1 => output.push(content_size as u8)?,
169        2 => {
170            // The 2-byte field stores the size less 256.
171            let v = (content_size - 256) as u16;
172            output.extend_from_slice(&v.to_le_bytes())?;
173        }
174        4 => output.extend_from_slice(&(content_size as u32).to_le_bytes())?,
175        _ => output.extend_from_slice(&(content_size as u64).to_le_bytes())?,
176    }
177    Ok(())
178}
179
180/// Whether a frame without a dictionary declares its content size as its
181/// window instead of writing a window descriptor.
182fn fits_single_segment(content_size: usize) -> bool {
183    content_size as u64 <= MAX_WINDOW_SIZE
184}
185
186/// The window a frame without a dictionary advertises for `content_size` bytes.
187fn frame_window_size(content_size: usize, window_log: u32) -> usize {
188    if fits_single_segment(content_size) {
189        content_size
190    } else {
191        1usize << window_log
192    }
193}
194
195/// Bytes of the Frame_Content_Size field: 1 only in single-segment frames,
196/// 2 for 256 to 65791 bytes, else 4 or 8.
197fn frame_content_size_field_size(content_size: usize, single_segment: bool) -> usize {
198    if single_segment && content_size <= 255 {
199        1
200    } else if (256..=0xFFFF + 256).contains(&content_size) {
201        2
202    } else if content_size <= 0xFFFF_FFFF {
203        4
204    } else {
205        8
206    }
207}
208
209/// Window_Descriptor of a 2^`window_log`-byte window: exponent
210/// `window_log - 10`, mantissa 0.
211fn window_descriptor_for_log(window_log: u32) -> u8 {
212    let window_log = window_log.clamp(strategy::WINDOW_LOG_MIN, strategy::WINDOW_LOG_MAX);
213    ((window_log - 10) as u8) << 3
214}
215
216/// Whether to store `data`, a block of an `input_len`-byte input, raw without
217/// a match search.
218///
219/// Inputs that keep raw literals skip the sampling: it costs about as much as
220/// their match search, and a block without matches is stored raw anyway.
221pub(crate) fn skip_match_search(
222    params: &strategy::LevelParams,
223    input_len: usize,
224    data: &[u8],
225) -> bool {
226    !strategy::keeps_raw_literals(params, input_len) && block_looks_incompressible(data)
227}
228
229/// Whether `data` looks as flat as random bytes.
230///
231/// Samples eight 512-byte windows spread over the block and applies C zstd's
232/// Huffman bound: no byte value may occur much more than 1/128 of the time.
233/// A single window at the start would miss compressible data later in the
234/// block.
235fn block_looks_incompressible(data: &[u8]) -> bool {
236    const WINDOWS: usize = 8;
237    const WINDOW: usize = 512;
238    if data.len() < WINDOWS * WINDOW {
239        return false;
240    }
241    // Four interleaved tables, so runs of one byte value do not serialize on
242    // a single counter.
243    let mut counts = [[0u16; 256]; 4];
244    let bound = ((WINDOWS * WINDOW) >> 7) + 4;
245    let largest = |counts: &[[u16; 256]; 4]| {
246        (0..256)
247            .map(|i| usize::from(counts[0][i] + counts[1][i] + counts[2][i] + counts[3][i]))
248            .max()
249            .unwrap()
250    };
251    for w in 0..WINDOWS {
252        let start = data.len() * w / WINDOWS;
253        let (chunks, _) = data[start..start + WINDOW].as_chunks::<4>();
254        for c in chunks {
255            counts[0][c[0] as usize] += 1;
256            counts[1][c[1] as usize] += 1;
257            counts[2][c[2] as usize] += 1;
258            counts[3][c[3] as usize] += 1;
259        }
260        // Counts only grow: one value past the bound settles it.
261        if largest(&counts) > bound {
262            return false;
263        }
264    }
265    true
266}
267
268/// Clamps the table and window logs to their valid ranges, then shrinks
269/// them to cover no more than `src_len` bytes.
270pub(crate) fn clamp_params_to_src_size(params: &mut strategy::LevelParams, src_len: usize) {
271    params.hash_log = params
272        .hash_log
273        .clamp(strategy::HASH_LOG_MIN, strategy::HASH_LOG_MAX);
274    params.chain_log = params
275        .chain_log
276        .clamp(strategy::HASH_LOG_MIN, strategy::HASH_LOG_MAX);
277    params.window_log = params
278        .window_log
279        .clamp(strategy::WINDOW_LOG_MIN, strategy::WINDOW_LOG_MAX);
280    if src_len >= 2 {
281        let src_log = strategy::src_log(src_len);
282        params.hash_log = params.hash_log.min(src_log).max(strategy::HASH_LOG_MIN);
283        params.chain_log = params.chain_log.min(src_log).max(strategy::HASH_LOG_MIN);
284        params.window_log = params.window_log.min(src_log);
285    }
286}
287
288/// [`compress`] with explicit `params` instead of a level. The table and
289/// window logs are clamped to their valid ranges and to the input size.
290pub fn compress_with_params(
291    input: &[u8],
292    params: &strategy::LevelParams,
293) -> Result<Vec<u8>, CompressError> {
294    let mut params = *params;
295    clamp_params_to_src_size(&mut params, input.len());
296    compress_inner(input, &params)
297}
298
299/// Compresses `input` into one frame at `level` (-7..=4; -8 runs as -7,
300/// 0 as 1). The frame records the content size and a checksum. Other
301/// levels fail with `CompressError::InvalidLevel`.
302pub fn compress(input: &[u8], level: i32) -> Result<Vec<u8>, CompressError> {
303    let params = strategy::level_params_for_size(level, input.len())
304        .ok_or(CompressError::InvalidLevel(level))?;
305    compress_inner(input, &params)
306}
307
308/// [`compress`] with [`strategy::Options`]: a larger window or long
309/// distance matching. The window shrinks to the input.
310pub fn compress_opts(
311    input: &[u8],
312    level: i32,
313    opts: &strategy::Options,
314) -> Result<Vec<u8>, CompressError> {
315    let params = params_with_options(level, input.len(), opts)?;
316    compress_inner(input, &params)
317}
318
319/// Returns the parameters for a one-shot frame of `input_len` bytes.
320pub(crate) fn params_with_options(
321    level: i32,
322    input_len: usize,
323    opts: &strategy::Options,
324) -> Result<strategy::LevelParams, CompressError> {
325    let mut params = strategy::level_params_for_size(level, input_len)
326        .ok_or(CompressError::InvalidLevel(level))?;
327    strategy::apply_options(&mut params, opts);
328    clamp_params_to_src_size(&mut params, input_len);
329    // The window may have shrunk to the input, so size the LDM table for what
330    // is left. Inputs shorter than LDM's minimum match skip it.
331    #[cfg(feature = "ldm")]
332    if opts.ldm {
333        let window_log = params.window_log.max(strategy::WINDOW_LOG_MIN);
334        let ldm = strategy::LdmParams::default_for_window_log(window_log);
335        params.ldm_params = (input_len >= ldm.min_match_length as usize).then_some(ldm);
336    }
337    Ok(params)
338}
339
340#[allow(clippy::unnecessary_wraps)]
341fn compress_inner(input: &[u8], params: &strategy::LevelParams) -> Result<Vec<u8>, CompressError> {
342    let mut output = Vec::with_capacity(input.len() + 32);
343    compress_frame(input, params, &mut output)?;
344    Ok(output)
345}
346
347/// Writes one frame for `input` at `params`, without a dictionary.
348pub(crate) fn compress_frame(
349    input: &[u8],
350    params: &strategy::LevelParams,
351    output: &mut impl OutputSink,
352) -> Result<(), CompressError> {
353    write_frame_header(output, input.len(), None, params.window_log)?;
354
355    if input.is_empty() {
356        block_encoder::encode_raw_block(&[], true, output)?;
357    } else {
358        // The format's initial repeat offsets.
359        let mut rep_offsets = [1u32, 4, 8];
360        let mut offset = 0;
361        let mut sequences = Vec::with_capacity(input.len().min(MAX_BLOCK_SIZE) / 8);
362        let mut workspace = block_encoder::BlockEncodeWorkspace::new();
363
364        #[cfg(feature = "ldm")]
365        let mut ldm_state = params.ldm_params.as_ref().map(ldm::LdmState::new);
366        let window_size = frame_window_size(input.len(), params.window_log);
367        // Blocks may not exceed the window.
368        let block_size = MAX_BLOCK_SIZE.min(window_size);
369        let mut positions = PositionBase::new(params.window_log);
370
371        match params.strategy {
372            Strategy::Fast => {
373                let hash_size = 1usize << params.hash_log;
374                let mut hash_table = MatchTable::zeroed(hash_size);
375                while offset < input.len() {
376                    let chunk_size = (input.len() - offset).min(block_size);
377                    let block_end = offset + chunk_size;
378                    let is_last = block_end >= input.len();
379                    let block = &input[offset..block_end];
380
381                    if let Some(shift) = positions.advance(offset, block_end) {
382                        rebase::reduce_hash_table(&mut hash_table, shift);
383                        #[cfg(feature = "ldm")]
384                        if let Some(ref mut ldm) = ldm_state {
385                            ldm.reduce_positions(shift);
386                        }
387                    }
388                    let base = positions.base();
389                    let src = &input[base..];
390                    let (start, end) = (offset - base, block_end - base);
391
392                    if skip_match_search(params, input.len(), block) {
393                        block_encoder::encode_raw_block(block, is_last, output)?;
394                    } else {
395                        #[cfg(feature = "ldm")]
396                        let used_ldm = if let Some(ref mut ldm) = ldm_state {
397                            // Fast has no long table.
398                            let mut empty = Vec::new();
399                            ldm.compress_block(
400                                src,
401                                start,
402                                end,
403                                window_size,
404                                params,
405                                &rep_offsets,
406                                &mut hash_table,
407                                &mut empty,
408                                &mut sequences,
409                            );
410                            true
411                        } else {
412                            false
413                        };
414                        #[cfg(not(feature = "ldm"))]
415                        let used_ldm = false;
416
417                        if !used_ldm {
418                            fast::compress_fast_block(
419                                src,
420                                start,
421                                end,
422                                params,
423                                &rep_offsets,
424                                &mut hash_table,
425                                &mut sequences,
426                            );
427                        }
428                        if params.force_raw_literals {
429                            block_encoder::encode_compressed_block_raw(
430                                block,
431                                &sequences,
432                                &mut rep_offsets,
433                                is_last,
434                                output,
435                                &mut workspace,
436                            )?;
437                        } else {
438                            block_encoder::encode_compressed_block(
439                                block,
440                                &sequences,
441                                &mut rep_offsets,
442                                is_last,
443                                output,
444                                &mut workspace,
445                                strategy::block_policy(params, input.len()),
446                            )?;
447                        }
448                    }
449                    offset = block_end;
450                }
451            }
452            Strategy::DFast => {
453                let short_size = 1usize << params.chain_log;
454                let long_size = 1usize << params.hash_log;
455                let mut hash_short = MatchTable::zeroed(short_size);
456                let mut hash_long = MatchTable::zeroed(long_size);
457                while offset < input.len() {
458                    let chunk_size = (input.len() - offset).min(block_size);
459                    let block_end = offset + chunk_size;
460                    let is_last = block_end >= input.len();
461                    let block = &input[offset..block_end];
462
463                    if let Some(shift) = positions.advance(offset, block_end) {
464                        rebase::reduce_hash_table(&mut hash_short, shift);
465                        rebase::reduce_hash_table(&mut hash_long, shift);
466                        #[cfg(feature = "ldm")]
467                        if let Some(ref mut ldm) = ldm_state {
468                            ldm.reduce_positions(shift);
469                        }
470                    }
471                    let base = positions.base();
472                    let src = &input[base..];
473                    let (start, end) = (offset - base, block_end - base);
474
475                    if skip_match_search(params, input.len(), block) {
476                        block_encoder::encode_raw_block(block, is_last, output)?;
477                    } else {
478                        #[cfg(feature = "ldm")]
479                        let used_ldm = if let Some(ref mut ldm) = ldm_state {
480                            ldm.compress_block(
481                                src,
482                                start,
483                                end,
484                                window_size,
485                                params,
486                                &rep_offsets,
487                                &mut hash_short,
488                                &mut hash_long,
489                                &mut sequences,
490                            );
491                            true
492                        } else {
493                            false
494                        };
495                        #[cfg(not(feature = "ldm"))]
496                        let used_ldm = false;
497
498                        if !used_ldm {
499                            dfast::compress_dfast_block(
500                                src,
501                                start,
502                                end,
503                                params,
504                                &rep_offsets,
505                                &mut hash_short,
506                                &mut hash_long,
507                                &mut sequences,
508                            );
509                        }
510                        block_encoder::encode_compressed_block(
511                            block,
512                            &sequences,
513                            &mut rep_offsets,
514                            is_last,
515                            output,
516                            &mut workspace,
517                            strategy::block_policy(params, input.len()),
518                        )?;
519                    }
520                    offset = block_end;
521                }
522            }
523        }
524    }
525
526    // Content_Checksum: the low 32 bits of XXH64 with seed 0.
527    let hash = xxh64(input, 0);
528    let checksum = (hash & 0xFFFF_FFFF) as u32;
529    output.extend_from_slice(&checksum.to_le_bytes())?;
530    Ok(())
531}
532
533/// [`compress`] with `dict`. Decoders need the same dictionary.
534pub fn compress_with_dict(
535    input: &[u8],
536    level: i32,
537    dict: &zrip_core::dict::Dictionary,
538) -> Result<Vec<u8>, CompressError> {
539    let mut output = Vec::with_capacity(input.len() + 32);
540    compress_with_dict_to(input, level, dict, &mut output)?;
541    Ok(output)
542}
543
544/// [`compress_with_dict`], appending the frame to `output`.
545pub(crate) fn compress_with_dict_to(
546    input: &[u8],
547    level: i32,
548    dict: &zrip_core::dict::Dictionary,
549    output: &mut Vec<u8>,
550) -> Result<(), CompressError> {
551    let params = strategy::level_params_with_prefix(level, dict.content().len(), input.len())
552        .ok_or(CompressError::InvalidLevel(level))?;
553
554    output.reserve(input.len() + 32);
555    write_frame_header(output, input.len(), Some(dict.id()), params.window_log)?;
556
557    if input.is_empty() {
558        block_encoder::encode_raw_block(&[], true, output)?;
559    } else {
560        let prefix = dict.content();
561        let mut rep_offsets = *dict.rep_offsets();
562        let mut workspace = block_encoder::BlockEncodeWorkspace::new();
563
564        // Largest codes: 35 for literal lengths, 31 for offsets, 52 for
565        // match lengths.
566        workspace.prev_ll = dict
567            .ll_table()
568            .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 35));
569        workspace.prev_of = dict
570            .of_table()
571            .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 31));
572        workspace.prev_ml = dict
573            .ml_table()
574            .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 52));
575        workspace.set_prev_huffman(dict.huf_table().and_then(|(dt, tl)| {
576            zrip_core::huffman::encode::HuffmanEncodeTable::from_decode_table(dt, tl)
577        }));
578
579        if input.len() <= MAX_BLOCK_SIZE {
580            let sequences = match params.strategy {
581                Strategy::Fast => {
582                    fast::compress_fast_with_prefix(input, &params, &rep_offsets, prefix)
583                }
584                Strategy::DFast => {
585                    dfast::compress_dfast_with_prefix(input, &params, &rep_offsets, prefix)
586                }
587            };
588            if params.force_raw_literals {
589                block_encoder::encode_compressed_block_raw(
590                    input,
591                    &sequences,
592                    &mut rep_offsets,
593                    true,
594                    output,
595                    &mut workspace,
596                )?;
597            } else {
598                block_encoder::encode_compressed_block(
599                    input,
600                    &sequences,
601                    &mut rep_offsets,
602                    true,
603                    output,
604                    &mut workspace,
605                    strategy::block_policy(&params, input.len()),
606                )?;
607            }
608        } else {
609            let mut combined = Vec::with_capacity(prefix.len() + input.len());
610            combined.extend_from_slice(prefix);
611            combined.extend_from_slice(input);
612            let plen = prefix.len();
613            let hash_size = 1usize << params.hash_log;
614            let mut sequences = Vec::new();
615
616            match params.strategy {
617                Strategy::Fast => {
618                    let mut hash_table = MatchTable::zeroed(hash_size);
619                    fast::prefill_hash_table(
620                        &combined,
621                        plen,
622                        params.hash_log,
623                        params.min_match,
624                        &mut hash_table,
625                    );
626                    let mut positions = PositionBase::new(params.window_log);
627                    let mut offset = 0;
628                    while offset < input.len() {
629                        let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
630                        let is_last = offset + chunk_size >= input.len();
631                        let (start, end) = (plen + offset, plen + offset + chunk_size);
632                        if let Some(shift) = positions.advance(start, end) {
633                            rebase::reduce_hash_table(&mut hash_table, shift);
634                        }
635                        let base = positions.base();
636                        fast::compress_fast_block(
637                            &combined[base..],
638                            start - base,
639                            end - base,
640                            &params,
641                            &rep_offsets,
642                            &mut hash_table,
643                            &mut sequences,
644                        );
645                        if params.force_raw_literals {
646                            block_encoder::encode_compressed_block_raw(
647                                &input[offset..offset + chunk_size],
648                                &sequences,
649                                &mut rep_offsets,
650                                is_last,
651                                output,
652                                &mut workspace,
653                            )?;
654                        } else {
655                            block_encoder::encode_compressed_block(
656                                &input[offset..offset + chunk_size],
657                                &sequences,
658                                &mut rep_offsets,
659                                is_last,
660                                output,
661                                &mut workspace,
662                                strategy::block_policy(&params, input.len()),
663                            )?;
664                        }
665                        offset += chunk_size;
666                    }
667                }
668                Strategy::DFast => {
669                    let short_size = 1usize << params.chain_log;
670                    let long_size = 1usize << params.hash_log;
671                    let mut hash_short = MatchTable::zeroed(short_size);
672                    let mut hash_long = MatchTable::zeroed(long_size);
673                    dfast::prefill_hash_tables(
674                        &combined,
675                        plen,
676                        params.hash_log,
677                        params.chain_log,
678                        params.min_match,
679                        &mut hash_short,
680                        &mut hash_long,
681                    );
682                    let mut positions = PositionBase::new(params.window_log);
683                    let mut offset = 0;
684                    while offset < input.len() {
685                        let chunk_size = (input.len() - offset).min(MAX_BLOCK_SIZE);
686                        let is_last = offset + chunk_size >= input.len();
687                        let (start, end) = (plen + offset, plen + offset + chunk_size);
688                        if let Some(shift) = positions.advance(start, end) {
689                            rebase::reduce_hash_table(&mut hash_short, shift);
690                            rebase::reduce_hash_table(&mut hash_long, shift);
691                        }
692                        let base = positions.base();
693                        dfast::compress_dfast_block(
694                            &combined[base..],
695                            start - base,
696                            end - base,
697                            &params,
698                            &rep_offsets,
699                            &mut hash_short,
700                            &mut hash_long,
701                            &mut sequences,
702                        );
703                        block_encoder::encode_compressed_block(
704                            &input[offset..offset + chunk_size],
705                            &sequences,
706                            &mut rep_offsets,
707                            is_last,
708                            output,
709                            &mut workspace,
710                            strategy::block_policy(&params, input.len()),
711                        )?;
712                        offset += chunk_size;
713                    }
714                }
715            }
716        }
717    }
718
719    let hash = xxh64(input, 0);
720    let checksum = (hash & 0xFFFF_FFFF) as u32;
721    output.extend_from_slice(&checksum.to_le_bytes());
722
723    Ok(())
724}
725
726/// [`compress`] into `output`. Returns the frame size. Fails with
727/// `CompressError::OutputTooSmall` if the frame does not fit; `output` then
728/// holds a partial frame. `zrip::compress_bound(input.len())` bytes are
729/// always enough.
730pub fn compress_into(input: &[u8], output: &mut [u8], level: i32) -> Result<usize, CompressError> {
731    let params = strategy::level_params_for_size(level, input.len())
732        .ok_or(CompressError::InvalidLevel(level))?;
733    let mut sink = SliceSink::new(output);
734    compress_frame(input, &params, &mut sink)?;
735    Ok(sink.pos())
736}
737
738#[cfg(test)]
739mod tests {
740    use super::*;
741    use zrip_core::frame::header::parse_frame_header;
742
743    #[test]
744    fn clamp_params_normalizes_public_log_values() {
745        let mut params = strategy::level_params(1).unwrap();
746        params.hash_log = 0;
747        params.chain_log = 40;
748        params.window_log = 40;
749
750        clamp_params_to_src_size(&mut params, usize::MAX);
751
752        assert_eq!(params.hash_log, strategy::HASH_LOG_MIN);
753        assert_eq!(params.chain_log, strategy::HASH_LOG_MAX);
754        assert_eq!(params.window_log, strategy::WINDOW_LOG_MAX);
755    }
756
757    #[test]
758    fn src_log_rounds_up() {
759        assert_eq!(strategy::src_log(2), 1);
760        assert_eq!(strategy::src_log(3), 2);
761        assert_eq!(strategy::src_log(1 << 10), 10);
762        assert_eq!(strategy::src_log((1 << 10) + 1), 11);
763    }
764
765    #[cfg(target_pointer_width = "64")]
766    #[test]
767    fn inputs_past_4_gib_keep_the_level_params() {
768        let full = strategy::level_params(1).unwrap();
769        for len in [1usize << 32, (1 << 32) + 5, 5 << 32] {
770            let sized = strategy::level_params_for_size(1, len).unwrap();
771            assert_eq!(sized.window_log, full.window_log, "len {len}");
772            assert_eq!(sized.hash_log, full.hash_log, "len {len}");
773
774            let mut clamped = full;
775            clamp_params_to_src_size(&mut clamped, len);
776            assert_eq!(clamped.window_log, full.window_log, "len {len}");
777            assert_eq!(clamped.hash_log, full.hash_log, "len {len}");
778        }
779    }
780
781    #[test]
782    fn options_clamp_window_log_before_ldm_defaults() {
783        let window_log = |log: u32| {
784            let mut params = strategy::level_params(1).unwrap();
785            strategy::apply_options(&mut params, &strategy::Options::default().window_log(log));
786            params.window_log
787        };
788        assert_eq!(window_log(1), strategy::WINDOW_LOG_MIN);
789        assert_eq!(window_log(40), strategy::WINDOW_LOG_MAX);
790        #[cfg(feature = "ldm")]
791        {
792            let mut params = strategy::level_params(1).unwrap();
793            let opts = strategy::Options::default().window_log(1).ldm(true);
794            strategy::apply_options(&mut params, &opts);
795
796            let ldm = params.ldm_params.unwrap();
797            assert!(ldm.hash_log >= ldm.bucket_size_log);
798        }
799    }
800
801    #[test]
802    fn window_log_zero_selects_the_default() {
803        let default = strategy::level_params(3).unwrap();
804        let mut params = default;
805        let opts = strategy::Options::default().window_log(20).window_log(0);
806        strategy::apply_options(&mut params, &opts);
807        assert_eq!(params.window_log, default.window_log);
808
809        #[cfg(feature = "ldm")]
810        {
811            let mut params = default;
812            let opts = strategy::Options::default().window_log(0).ldm(true);
813            strategy::apply_options(&mut params, &opts);
814            assert_eq!(params.window_log, 27);
815        }
816    }
817
818    #[cfg(feature = "ldm")]
819    #[test]
820    fn ldm_defaults_window_log_to_27() {
821        let mut params = strategy::level_params(3).unwrap();
822        strategy::apply_options(&mut params, &strategy::Options::default().ldm(true));
823        assert_eq!(params.window_log, 27);
824
825        let mut params = strategy::level_params(3).unwrap();
826        let opts = strategy::Options::default().window_log(22).ldm(true);
827        strategy::apply_options(&mut params, &opts);
828        assert_eq!(params.window_log, 22);
829    }
830
831    #[cfg(feature = "ldm")]
832    #[test]
833    fn ldm_table_follows_the_clamped_window() {
834        let table_log = |len: usize, opts: &strategy::Options| {
835            params_with_options(1, len, opts)
836                .unwrap()
837                .ldm_params
838                .map(|ldm| ldm.hash_log)
839        };
840
841        let bare = strategy::Options::default().ldm(true);
842        assert_eq!(table_log(1, &bare), None);
843        assert_eq!(table_log(63, &bare), None);
844        assert_eq!(table_log(64, &bare), Some(9));
845        assert_eq!(table_log(1 << 10, &bare), Some(9));
846        assert_eq!(table_log(1 << 20, &bare), Some(19));
847        assert_eq!(table_log(1 << 27, &bare), Some(20));
848
849        let explicit = strategy::Options::default().window_log(24).ldm(true);
850        assert_eq!(table_log(1 << 10, &explicit), Some(9));
851        assert_eq!(table_log(1 << 27, &explicit), Some(20));
852    }
853
854    /// Bytes from a skewed alphabet: about 3.5 bits of order-0 entropy per
855    /// byte and few repeated 6-byte strings.
856    fn skewed_bytes(len: usize) -> Vec<u8> {
857        let mut x = 0x2545_F491_4F6C_DD1Du64;
858        (0..len)
859            .map(|_| {
860                x ^= x << 13;
861                x ^= x >> 7;
862                x ^= x << 17;
863                let r = (x >> 32) as u32;
864                b"eeeeeeettttaaoonnissshhrdl  "[(r % 28) as usize] + (r >> 30) as u8
865            })
866            .collect()
867    }
868
869    /// Words from a 64-word vocabulary. Repeats are short and sparse, so a
870    /// sparse match search misses most of them.
871    fn wordy_bytes(len: usize) -> Vec<u8> {
872        const WORDS: &str = "the of and to in is was for on that with as by at \
873            from his her they this have had were which their are but not one \
874            all been when there she would what so if will more no out up into \
875            could them than then some other time very about only upon over \
876            such said great before after little";
877        let words: Vec<&str> = WORDS.split_whitespace().collect();
878        let mut x = 0x9E37_79B9_7F4A_7C15u64;
879        let mut out = Vec::with_capacity(len + 16);
880        while out.len() < len {
881            x ^= x << 13;
882            x ^= x >> 7;
883            x ^= x << 17;
884            out.extend_from_slice(words[(x >> 58) as usize % words.len()].as_bytes());
885            out.push(b' ');
886        }
887        out.truncate(len);
888        out
889    }
890
891    #[test]
892    fn negative_levels_skip_huffman_on_tiny_inputs() {
893        // No usable matches: only Huffman could shrink these bytes.
894        let data = skewed_bytes(2048);
895        for level in -7..=-1 {
896            let out = compress(&data, level).unwrap();
897            assert!(out.len() > data.len(), "L{level}: {} compressed", out.len());
898        }
899        for level in 1..=4 {
900            let out = compress(&data, level).unwrap();
901            assert!(out.len() * 5 < data.len() * 4, "L{level}: {}", out.len());
902        }
903    }
904
905    #[test]
906    fn negative_levels_still_match_tiny_inputs() {
907        let data = wordy_bytes(2048);
908        let sizes: Vec<usize> = (-7..=-1)
909            .map(|level| compress(&data, level).unwrap().len())
910            .collect();
911        // L-6 to L-1 at least 10% smaller; L-7 takes only matches of eight
912        // bytes or more, which these short words seldom repeat. No smaller
913        // output at a faster level.
914        assert!(
915            sizes[1..].iter().all(|&n| n * 11 < data.len() * 10),
916            "{sizes:?}"
917        );
918        assert!(sizes.windows(2).all(|w| w[0] >= w[1]), "{sizes:?}");
919    }
920
921    #[test]
922    fn negative_levels_huffman_code_above_their_raw_limit() {
923        let data = skewed_bytes(32 * 1024);
924        for level in -6..=-1 {
925            let out = compress(&data, level).unwrap();
926            assert!(out.len() * 5 < data.len() * 4, "L{level}: {}", out.len());
927        }
928        // L-7 keeps literals raw, except in blocks that are almost all
929        // literals, with over 32 KiB of them.
930        let data = skewed_bytes(64 * 1024);
931        let out = compress(&data, -7).unwrap();
932        assert!(out.len() * 5 < data.len() * 4, "L-7: {}", out.len());
933        let small = skewed_bytes(16 * 1024);
934        let out = compress(&small, -7).unwrap();
935        assert!(out.len() > small.len(), "L-7 small: {}", out.len());
936    }
937
938    #[test]
939    fn level_minus_8_runs_as_level_minus_7() {
940        let data = wordy_bytes(64 * 1024);
941        assert_eq!(compress(&data, -8).unwrap(), compress(&data, -7).unwrap());
942    }
943
944    #[test]
945    fn faster_levels_keep_raw_literals_longer() {
946        let limits: Vec<usize> = (-6..=-1)
947            .map(|level| strategy::raw_literals_limit(level).unwrap())
948            .collect();
949        assert_eq!(limits.last(), Some(&2048));
950        assert!(limits.windows(2).all(|w| w[0] > w[1]), "{limits:?}");
951        assert_eq!(strategy::raw_literals_limit(-7), None);
952        assert_eq!(strategy::raw_literals_limit(1), None);
953    }
954
955    #[test]
956    fn small_plain_frame_uses_single_segment_header() {
957        let mut output = Vec::new();
958
959        write_frame_header(&mut output, 12, None, 19).unwrap();
960        let header = parse_frame_header(&output).unwrap();
961
962        assert!(header.single_segment);
963        assert_eq!(header.frame_content_size, Some(12));
964        assert_eq!(header.window_size, 12);
965        assert_eq!(header.dict_id, None);
966        assert!(header.content_checksum);
967        assert_eq!(header.header_size, 6);
968    }
969
970    #[test]
971    fn large_plain_frame_uses_bounded_window_descriptor() {
972        let mut output = Vec::new();
973        let content_size = MAX_WINDOW_SIZE as usize + 1;
974
975        write_frame_header(&mut output, content_size, None, 19).unwrap();
976        let header = parse_frame_header(&output).unwrap();
977
978        assert!(!header.single_segment);
979        assert_eq!(header.frame_content_size, Some(content_size as u64));
980        assert_eq!(header.window_size, 1 << 19);
981        assert_eq!(header.dict_id, None);
982        assert!(header.content_checksum);
983        assert_eq!(header.header_size, 10);
984    }
985
986    #[test]
987    fn dict_frame_its_window_covers_is_single_segment() {
988        let mut output = Vec::new();
989
990        write_frame_header(&mut output, 12, Some(0x1234), 10).unwrap();
991        let header = parse_frame_header(&output).unwrap();
992
993        assert!(header.single_segment);
994        assert_eq!(header.frame_content_size, Some(12));
995        assert_eq!(header.dict_id, Some(0x1234));
996        assert!(header.content_checksum);
997        assert_eq!(header.header_size, 8);
998    }
999
1000    #[test]
1001    fn dict_frame_past_its_window_uses_window_descriptor() {
1002        let mut output = Vec::new();
1003
1004        write_frame_header(&mut output, 5000, Some(0x1234), 10).unwrap();
1005        let header = parse_frame_header(&output).unwrap();
1006
1007        assert!(!header.single_segment);
1008        assert_eq!(header.frame_content_size, Some(5000));
1009        assert_eq!(header.window_size, 1 << 10);
1010        assert_eq!(header.dict_id, Some(0x1234));
1011        assert_eq!(header.header_size, 10);
1012    }
1013
1014    #[test]
1015    fn no_fcs_frame_uses_window_descriptor() {
1016        let mut output = Vec::new();
1017
1018        write_frame_header_without_content_size(&mut output, None, 19).unwrap();
1019        let header = parse_frame_header(&output).unwrap();
1020
1021        assert!(!header.single_segment);
1022        assert_eq!(header.frame_content_size, None);
1023        assert_eq!(header.window_size, 1 << 19);
1024        assert_eq!(header.dict_id, None);
1025        assert!(header.content_checksum);
1026        assert_eq!(header.header_size, 6);
1027    }
1028}