Skip to main content

zrip_encode/
lib.rs

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