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