nordisk/znippy-zoomies

linflate/tests/inflate_bits.rs

//! `inflate_bits`: decode raw DEFLATE that starts and stops at BIT offsets.
//!
//! A real block boundary inside ordinary DEFLATE sits at any bit, not at a
//! byte. The parallel gzip decoder splits a stream there, so the decoder must
//! (a) stop at the first block end at or after a given bit and say exactly
//! where that was, and (b) resume from that bit with the previous output as
//! the back-reference window. Split + resume must give back the original.

use linflate::{OVERWRITE_HEADROOM, inflate_bits};

/// Compressible, not trivially repetitive: words from a small vocabulary with
/// a varying separator, so the encoder emits dynamic-Huffman blocks with
/// back-references across block ends.
fn corpus(len: usize) -> Vec<u8> {
    let words: [&[u8]; 12] = [
        b"layer",
        b"overlay",
        b"usr",
        b"lib",
        b"python3",
        b"site-packages",
        b"share",
        b"locale",
        b"etc",
        b"ssl",
        b"certs",
        b"bin",
    ];
    let mut out = Vec::with_capacity(len + 32);
    let mut x: u32 = 0x9e37_79b9;
    while out.len() < len {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        out.extend_from_slice(words[(x % 12) as usize]);
        out.push(if x & 0x100 != 0 { b'/' } else { b'\n' });
        if x & 0xf000 == 0 {
            out.extend_from_slice(&x.to_le_bytes());
        }
    }
    out.truncate(len);
    out
}

#[test]
fn split_at_a_bit_and_resume_gives_back_the_original() {
    let data = corpus(3 << 20);
    let deflate = miniz_oxide::deflate::compress_to_vec(&data, 6);
    let total_bits = deflate.len() * 8;
    let mut unaligned = 0;

    for frac in [1usize, 2, 3, 5, 7] {
        let stop = total_bits * frac / 8;
        let mut first = vec![0u8; data.len() + OVERWRITE_HEADROOM];
        let a = inflate_bits(&deflate, 0, stop, &mut first, 0).expect("first part");
        assert!(a.end_bit >= stop, "stopped before the asked bit");
        assert!(
            !a.final_block,
            "a mid-stream stop must not be the final block"
        );
        assert_eq!(&first[..a.written], &data[..a.written]);
        if !a.end_bit.is_multiple_of(8) {
            unaligned += 1;
        }

        // Resume at the exact bit, with the last 32 KB as the window.
        let win = a.written.min(32 * 1024);
        let mut second = vec![0u8; win + data.len() - a.written + OVERWRITE_HEADROOM];
        second[..win].copy_from_slice(&first[a.written - win..a.written]);
        let b =
            inflate_bits(&deflate, a.end_bit, usize::MAX, &mut second, win).expect("second part");
        assert!(b.final_block, "the rest must end on the final block");
        assert_eq!(b.written, data.len() - a.written);
        assert_eq!(&second[win..win + b.written], &data[a.written..]);
        assert!(b.end_bit <= total_bits);
    }
    assert!(
        unaligned > 0,
        "no split landed off a byte boundary; the test proves nothing"
    );
}

#[test]
fn whole_stream_from_bit_zero() {
    let data = corpus(1 << 20);
    let deflate = miniz_oxide::deflate::compress_to_vec(&data, 9);
    let mut out = vec![0u8; data.len() + OVERWRITE_HEADROOM];
    let r = inflate_bits(&deflate, 0, usize::MAX, &mut out, 0).unwrap();
    assert!(r.final_block);
    assert_eq!(&out[..r.written], &data[..]);
}