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