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