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