ldeflate/

precompressed.rs

//! **Never compress what is already compressed** — an exact probe, and the
//! stored-DEFLATE emitter that makes acting on it free.
//!
//! Level-6 DEFLATE over already-compressed content measures a ratio of **1.000
//! while running 42x slower than a hash over the same bytes**
//! (`.nornir/ldeflate-design.md`, the incompressible finding). Every format this
//! crate writes hits that case constantly: a git object store full of packfiles,
//! a JAR full of PNGs, a `.tar.gz` of `.jpg`s. Paying an entropy coder to
//! produce its input back is the single largest avoidable cost on the write
//! side.
//!
//! `zip.rs` already stored an entry when deflate failed to help — but *after*
//! deflating it, so the CPU was already spent and only the bytes were saved.
//! This module moves the decision in front of the encoder, for all three
//! containers at once.
//!
//! # Why there is no entropy estimate
//!
//! Inherited verbatim from the reference implementation, and worth restating
//! because it is the first thing anyone reaches for: an entropy estimate is a
//! heuristic with a tunable threshold, it costs a scan proportional to the data,
//! and it misjudges in both directions. Every probe here is **exact** — a fixed
//! byte pattern at a fixed offset, at most [`SNIFF_PREFIX_LEN`] byte compares,
//! no threshold, no sample size, no allocation.
//!
//! # Provenance, and why this module is the one writer (LAW 5)
//!
//! The probe is the owner's, from `znippy-common/src/precompressed.rs`, and for
//! one commit it existed twice. It lives **here** now, and `znippy-common`'s
//! module is a re-export of this one — `znippy_common::precompressed::{
//! looks_compressed, is_zlib_stream, ContentHint, SNIFF_PREFIX_LEN}` are these
//! items, not copies of them.
//!
//! The direction is forced. `znippy-common` already depends on `znippy-zoomies`
//! (`znippy-common/Cargo.toml:95`, plus `ljar`/`lbzip2`/`lgz`), so an
//! `ldeflate -> znippy-common` edge would close a cycle; and `znippy-common`
//! drags `arrow`, `blake3` and an `openzl-sys` whose `build.rs` fetches a tarball
//! over the network — for 88 lines of `std`-only pattern matching. The
//! dependency arrow already pointed here, and this crate is the *compressor*,
//! the only thing that ever needs to ask the question.
//!
//! The extension half of the reference chain (`skip_by_path`, backed by
//! `znippy_common::index::is_probably_compressed`) is deliberately **not**
//! lifted, and is the one part `znippy-common` still owns: this crate is handed
//! `&[u8]`, never a `Path`. A caller who has a path resolves it to a
//! [`ContentHint`] and passes that. `znippy_common::precompressed::SkipPolicy`
//! is therefore a thin wrapper over [`SkipPolicy`] that adds the path leg and
//! delegates the byte leg to [`SkipPolicy::skip`] — the hint-to-verdict mapping
//! for bytes exists once, here.

/// Bytes of prefix the probe reads. Sized by WebP, whose form type sits at
/// offset 8..12 — the longest anchored pattern here.
pub const SNIFF_PREFIX_LEN: usize = 16;

/// What a caller already knows about its content, if anything.
///
/// The hint is honoured **in both directions**: `Compressible` is never vetoed
/// by a probe, so a caller who knows better than the magic bytes wins.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum ContentHint {
    /// Nothing known — probe the bytes.
    #[default]
    Unknown,
    /// Caller asserts this is already compressed. Store it, do not probe.
    AlreadyCompressed,
    /// Caller asserts this is worth compressing. Compress it, do not probe.
    Compressible,
}

/// Whether, and how, the compressor is allowed to skip the entropy coder.
///
/// [`Default`] is [`resolve`](Self::resolve) — the probe is **on**. An
/// optimisation that a caller must opt into is one that nobody gets; and unlike
/// a cap, being wrong here costs a few percent of ratio on a file that lied
/// about its own magic bytes, not a correctness bug. Every output remains a
/// valid stream of its container either way.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct SkipPolicy {
    hint: ContentHint,
}

impl SkipPolicy {
    /// Probe the bytes (the default).
    pub const fn resolve() -> Self {
        Self {
            hint: ContentHint::Unknown,
        }
    }
    /// Store everything: the caller knows the whole batch is compressed.
    pub const fn already_compressed() -> Self {
        Self {
            hint: ContentHint::AlreadyCompressed,
        }
    }
    /// Compress everything, probe nothing — the pre-probe behaviour, by name.
    pub const fn compress_everything() -> Self {
        Self {
            hint: ContentHint::Compressible,
        }
    }
    /// From a caller's hint.
    pub const fn from_hint(hint: ContentHint) -> Self {
        Self { hint }
    }
    /// The hint this policy carries.
    pub const fn hint(&self) -> ContentHint {
        self.hint
    }

    /// Should `src` be stored rather than deflated?
    ///
    /// Reads at most [`SNIFF_PREFIX_LEN`] bytes regardless of how long `src` is,
    /// so this is O(1) in the object size — the property that makes it sound to
    /// call on every object on the hot path.
    #[inline]
    pub fn skip(&self, src: &[u8]) -> bool {
        match self.hint {
            ContentHint::AlreadyCompressed => true,
            ContentHint::Compressible => false,
            ContentHint::Unknown => looks_compressed(src),
        }
    }
}

/// One magic-byte pattern that must match at offset 0.
type Magic = (&'static [u8], &'static str);

/// Exact patterns, all anchored at offset 0. Each is a format whose payload is
/// compressed or otherwise incompressible; none has a threshold.
const MAGICS: &[Magic] = &[
    // ── git ─────────────────────────────────────────────────────────────────
    (b"PACK", "git packfile"),
    (b"\xfftOc", "git pack index v2"),
    (b"MIDX", "git multi-pack-index"),
    (b"BITM", "git pack bitmap (EWAH)"),
    // ── general-purpose compressors ─────────────────────────────────────────
    (b"\x1f\x8b", "gzip"),
    (b"\x28\xb5\x2f\xfd", "zstd frame"),
    (b"\xfd7zXZ\x00", "xz"),
    (b"\x04\x22\x4d\x18", "lz4 frame"),
    (b"7z\xbc\xaf\x27\x1c", "7z"),
    (b"Rar!\x1a\x07", "rar"),
    (b"PK\x03\x04", "zip"),
    (b"PK\x05\x06", "zip (empty archive)"),
    (b"PK\x07\x08", "zip (spanned)"),
    // ── already-compressed media ────────────────────────────────────────────
    (b"\x89PNG\r\n\x1a\n", "png"),
    (b"\xff\xd8\xff", "jpeg"),
    (b"GIF87a", "gif"),
    (b"GIF89a", "gif"),
];

/// Does this buffer begin with data that is already compressed?
///
/// At most [`SNIFF_PREFIX_LEN`] byte compares, no allocation, safe on a short or
/// empty slice.
pub fn looks_compressed(prefix: &[u8]) -> bool {
    let head = &prefix[..prefix.len().min(SNIFF_PREFIX_LEN)];

    if MAGICS.iter().any(|(pat, _)| head.starts_with(pat)) {
        return true;
    }
    // bzip2: "BZh" then the block-size digit '1'..='9'.
    if head.len() >= 4 && head.starts_with(b"BZh") && head[3].is_ascii_digit() && head[3] != b'0' {
        return true;
    }
    // WebP is a RIFF container with a WEBP form type at offset 8; the four
    // length bytes between them are not part of the magic.
    if head.len() >= 12 && head.starts_with(b"RIFF") && &head[8..12] == b"WEBP" {
        return true;
    }
    is_zlib_stream(head)
}

/// Does this buffer begin with a raw zlib stream (RFC 1950)?
///
/// This is what a git **loose object** is, and the one case an extension table
/// can never reach — the file's name is an oid with no extension at all. It is
/// also what *this crate writes*, so it is what keeps a re-compress pass over
/// `ldeflate`'s own output from paying twice.
///
/// * `CM`    = `CMF & 0x0f` must be `8` — deflate is the only defined method;
/// * `CINFO` = `CMF >> 4` must be `<= 7` — a window over 32 KiB is not defined;
/// * `FDICT` = `FLG & 0x20` must be clear;
/// * `(CMF << 8 | FLG) % 31 == 0` — the header's own check bits.
///
/// The `FDICT` clause is what keeps ordinary text out. `CMF = 0x78` is ASCII
/// `x`, and of the nine `FLG` values satisfying the mod-31 rule, every printable
/// one — `' '`, `'?'`, `'}'` — sets `FDICT` and is rejected. `x^` is the sole
/// printable two-byte sequence that survives.
pub fn is_zlib_stream(prefix: &[u8]) -> bool {
    let [cmf, flg, ..] = prefix else { return false };
    let (cmf, flg) = (*cmf, *flg);

    cmf & 0x0f == 8
        && cmf >> 4 <= 7
        && flg & 0x20 == 0
        && (u16::from(cmf) << 8 | u16::from(flg)) % 31 == 0
}

// ── Stored DEFLATE ───────────────────────────────────────────────────────────

/// Largest payload one DEFLATE stored block can carry: `LEN` is a `u16`.
const STORED_MAX: usize = u16::MAX as usize;

/// Emit `src` as **stored** DEFLATE blocks (RFC 1951 §3.2.4) — a memcpy plus
/// five bytes of framing per 65 535 bytes.
///
/// This is what makes the probe worth having. Asking `flate2` for level 0 would
/// also produce stored blocks, but it still constructs a `Compress`, still runs
/// the deflate state machine, and still copies through its internal window; this
/// is a length-prefixed `extend_from_slice`. The output is ordinary DEFLATE that
/// every inflater reads — including this workspace's own `linflate`.
///
/// `is_last` controls the final block's `BFINAL` bit:
///
/// * `true` — the stream ends here. An empty input still emits one empty final
///   block, because a DEFLATE stream with no blocks is malformed.
/// * `false` — the caller will append more, and the emitted bytes end at a block
///   boundary. That is the same seam `Z_FULL_FLUSH` leaves and what
///   `linflate::deflate_scan` looks for, so a stored segment concatenates with a
///   deflated one.
pub fn stored_deflate(src: &[u8], is_last: bool) -> Vec<u8> {
    // 5 bytes of framing per block, plus one extra block's worth for the empty
    // terminator an exact multiple needs.
    let blocks = src.len().div_ceil(STORED_MAX).max(1);
    let mut out = Vec::with_capacity(src.len() + 5 * blocks + 5);

    let mut chunks = src.chunks(STORED_MAX).peekable();
    if chunks.peek().is_none() {
        push_stored_block(&mut out, &[], is_last);
        return out;
    }
    while let Some(chunk) = chunks.next() {
        let last_block = is_last && chunks.peek().is_none();
        push_stored_block(&mut out, chunk, last_block);
    }
    out
}

/// One stored block: a byte-aligned 3-bit header (`BFINAL`, `BTYPE = 00`, then
/// five bits of padding to the byte boundary), `LEN`, `~LEN`, then the bytes
/// verbatim.
#[inline]
fn push_stored_block(out: &mut Vec<u8>, chunk: &[u8], is_last: bool) {
    debug_assert!(chunk.len() <= STORED_MAX);
    out.push(if is_last { 1 } else { 0 });
    let len = chunk.len() as u16;
    out.extend_from_slice(&len.to_le_bytes());
    out.extend_from_slice(&(!len).to_le_bytes());
    out.extend_from_slice(chunk);
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Every magic in the table must fire, and each must fire on the *shortest*
    /// buffer that carries it — a probe that needs 16 bytes to recognise a
    /// 2-byte magic would miss every tiny object.
    #[test]
    fn every_magic_in_the_table_is_recognised_at_its_own_length() {
        for (pat, label) in MAGICS {
            assert!(
                looks_compressed(pat),
                "{label}: not recognised from its own {} magic bytes",
                pat.len()
            );
        }
    }

    /// The three probes that are not a plain prefix compare, each from both
    /// sides — a check that only ever says yes is as useless as one that only
    /// ever says no.
    #[test]
    fn the_special_cased_probes_fire_only_on_their_real_shape() {
        // bzip2 needs the block-size digit, and '0' is not one.
        assert!(looks_compressed(b"BZh9\x31\x41\x59\x26"));
        assert!(looks_compressed(b"BZh1"));
        assert!(
            !looks_compressed(b"BZh0"),
            "'0' is not a valid bzip2 block size"
        );
        assert!(
            !looks_compressed(b"BZhx"),
            "a non-digit is not a block size"
        );
        assert!(
            !looks_compressed(b"BZh"),
            "three bytes cannot carry the digit"
        );

        // WebP needs BOTH the RIFF magic and the WEBP form type at 8..12.
        assert!(looks_compressed(b"RIFF\x00\x00\x00\x00WEBPVP8 "));
        assert!(
            !looks_compressed(b"RIFF\x00\x00\x00\x00WAVEfmt "),
            "a RIFF WAVE is not compressed"
        );
        assert!(
            !looks_compressed(b"RIFF\x00\x00\x00\x00WEB"),
            "truncated form type"
        );
    }

    /// The zlib header check, exactly — this is the one that decides whether a
    /// git loose object gets re-deflated, and the one most at risk of matching
    /// ordinary text.
    #[test]
    fn the_zlib_probe_accepts_real_headers_and_rejects_text() {
        // The three levels zlib actually emits at a 32 KiB window.
        for h in [[0x78u8, 0x01], [0x78, 0x9c], [0x78, 0xda]] {
            assert!(is_zlib_stream(&h), "{h:02x?} is a real zlib header");
            assert!(looks_compressed(&h));
        }
        // Wrong method, oversized window, FDICT set, bad check bits.
        assert!(!is_zlib_stream(&[0x77, 0x9c]), "CM != 8");
        assert!(!is_zlib_stream(&[0x88, 0x9c]), "CINFO > 7");
        assert!(!is_zlib_stream(&[0x78, 0xbb]), "FDICT set");
        assert!(!is_zlib_stream(&[0x78, 0x9d]), "check bits fail");
        assert!(!is_zlib_stream(&[0x78]), "one byte is not a header");
        assert!(!is_zlib_stream(&[]), "empty is not a header");

        // Ordinary content must not be mistaken for a stream.
        for text in [
            &b"fn main() { println!(\"hi\"); }"[..],
            b"the quick brown fox jumps over the lazy dog",
            b"{\"key\": \"value\", \"n\": 1}",
            b"<?xml version=\"1.0\"?><osm/>",
            b"# heading\n\nsome prose\n",
            b"\0\0\0\0\0\0\0\0",
        ] {
            assert!(
                !looks_compressed(text),
                "false positive on {:?}",
                &text[..text.len().min(12)]
            );
        }
    }

    /// The probe must be O(1) in the object size: a huge compressible buffer
    /// whose head is plain must not be read past the prefix. Asserted by
    /// behaviour — a 4 MiB buffer whose only compressed-looking bytes are at the
    /// end must not fire.
    #[test]
    fn the_probe_reads_only_the_head() {
        let mut v = vec![b'a'; 4 << 20];
        v.extend_from_slice(b"\x89PNG\r\n\x1a\n");
        assert!(!looks_compressed(&v), "a magic in the tail is not a magic");
        assert!(
            looks_compressed(b"\x89PNG\r\n\x1a\nrest"),
            "but one at the head is"
        );
    }

    /// The policy honours a hint in both directions, overriding the bytes.
    #[test]
    fn a_hint_beats_the_bytes_in_both_directions() {
        let png = b"\x89PNG\r\n\x1a\n....";
        let text = b"plain text, very compressible indeed";

        assert!(SkipPolicy::resolve().skip(png));
        assert!(!SkipPolicy::resolve().skip(text));

        assert!(
            SkipPolicy::already_compressed().skip(text),
            "hint must override the probe"
        );
        assert!(
            !SkipPolicy::compress_everything().skip(png),
            "a Compressible hint is never vetoed by a probe"
        );

        assert_eq!(
            SkipPolicy::default(),
            SkipPolicy::resolve(),
            "the probe is the default"
        );
    }

    /// The stored emitter's framing, byte for byte. `LEN`/`~LEN` is the field
    /// most likely to be got wrong and the one an inflater checks.
    #[test]
    fn a_stored_block_is_framed_exactly_as_rfc1951_says() {
        let out = stored_deflate(b"abc", true);
        assert_eq!(out, vec![0x01, 0x03, 0x00, 0xfc, 0xff, b'a', b'b', b'c']);

        let non_final = stored_deflate(b"abc", false);
        assert_eq!(
            non_final[0], 0x00,
            "BFINAL must be clear on a non-final block"
        );
        assert_eq!(&non_final[1..5], &[0x03, 0x00, 0xfc, 0xff]);
    }

    /// An empty input is still one (empty) final block — a DEFLATE stream with
    /// no blocks at all is malformed, and an empty git object is real.
    #[test]
    fn an_empty_input_still_emits_one_block() {
        assert_eq!(
            stored_deflate(b"", true),
            vec![0x01, 0x00, 0x00, 0xff, 0xff]
        );
    }

    /// Payloads past 65 535 bytes must split into several blocks, with BFINAL
    /// set on the last one only.
    #[test]
    fn a_payload_past_the_block_limit_splits_and_only_the_last_is_final() {
        let src = vec![0xABu8; STORED_MAX + 1];
        let out = stored_deflate(&src, true);
        assert_eq!(
            out.len(),
            src.len() + 10,
            "two blocks, five framing bytes each"
        );
        assert_eq!(out[0], 0x00, "the first of two blocks is not final");
        assert_eq!(
            &out[1..5],
            &[0xff, 0xff, 0x00, 0x00],
            "LEN = 65535, ~LEN = 0"
        );
        let second = STORED_MAX + 5;
        assert_eq!(out[second], 0x01, "the last block is final");
        assert_eq!(
            &out[second + 1..second + 5],
            &[0x01, 0x00, 0xfe, 0xff],
            "LEN = 1"
        );
    }

    /// The whole point, asserted against the real inflater: stored output must
    /// round-trip through `linflate` to the exact input, at every size class
    /// around the block boundary.
    #[test]
    fn stored_output_inflates_back_to_the_input() {
        for len in [
            0usize,
            1,
            255,
            STORED_MAX - 1,
            STORED_MAX,
            STORED_MAX + 1,
            3 * STORED_MAX + 7,
        ] {
            let src: Vec<u8> = (0..len).map(|i| (i * 31 + 7) as u8).collect();
            let body = stored_deflate(&src, true);
            let mut out = vec![0u8; len + linflate::OVERWRITE_HEADROOM];
            let n = linflate::inflate_segment(&body, &mut out)
                .unwrap_or_else(|e| panic!("len {len}: stored output did not inflate: {e:?}"));
            assert_eq!(n, len, "len {len}: wrong output length");
            assert_eq!(
                &out[..n],
                &src[..],
                "len {len}: stored output did not round-trip"
            );
        }
    }

    // ── the zlib probe against a REAL encoder ────────────────────────────────
    //
    // The cases above hand-type the two header bytes, which proves only that the
    // test and the probe agree with each other. These three come from
    // `compress_objects` — this crate's own encoder — and from the canonical git
    // bytes a real object store holds. They moved here from
    // `znippy-common/src/precompressed.rs` when that module became a re-export of
    // this one; the assertions are the reference implementation's, unchanged.

    /// A real zlib stream out of this crate's own encoder. The module doc claims
    /// the probe keeps a re-compress pass over `ldeflate`'s own output from
    /// paying twice — this is that claim, asserted rather than stated.
    ///
    /// `compress_everything()` produces the fixtures so the probe cannot be used
    /// to manufacture its own evidence, and the `FLG` values must genuinely
    /// differ across the level range, else a single accidental constant would
    /// prove nothing.
    #[test]
    fn this_crates_own_zlib_output_is_recognised() {
        let payload = b"the quick brown fox jumps over the lazy dog. ".repeat(40);
        let refs = [payload.as_slice()];
        let mut seen_flg = std::collections::BTreeSet::new();

        for level in [0u32, 1, 5, 6, 9] {
            let cfg = crate::Config {
                level,
                container: crate::Container::Zlib,
                ..crate::Config::default()
            }
            .compress_everything();
            let out = crate::compress_objects(&refs, &cfg).expect("compress");
            let z = &out[0];
            assert!(
                is_zlib_stream(z),
                "level {level}: own output header {:02x?} not recognised",
                &z[..2]
            );
            assert!(
                looks_compressed(z),
                "level {level}: own output must be stored on re-compress"
            );
            seen_flg.insert(z[1]);
        }
        assert!(
            seen_flg.len() > 1,
            "the levels must actually differ in FLG, else this proves nothing: {seen_flg:02x?}"
        );
    }

    /// The git case, both halves, and they need opposite answers:
    ///
    /// * a **loose object file** is the canonical form zlib-deflated — an oid for
    ///   a name, no extension, and it must be stored raw;
    /// * the **canonical form itself** (`"<type> <size>\0<content>"`) is what a
    ///   `znippy-plugin-git` entry holds. It is inflated bytes, compresses well,
    ///   and must reach the coder.
    ///
    /// A rule of the shape "an oid-keyed entry is already compressed" gets the
    /// second one backwards and silently stores compressible data raw.
    #[test]
    fn a_real_loose_object_is_recognised_and_its_canonical_form_is_not() {
        for kind in ["blob", "tree", "commit", "tag"] {
            let body = b"fn main() { println!(\"hello\"); }\n".repeat(8);
            let mut canonical = format!("{kind} {}\0", body.len()).into_bytes();
            canonical.extend_from_slice(&body);

            assert!(
                !looks_compressed(&canonical),
                "canonical {kind} bytes are inflated and must be compressed"
            );

            let cfg = crate::Config {
                container: crate::Container::Zlib,
                ..crate::Config::default()
            }
            .compress_everything();
            let refs = [canonical.as_slice()];
            let loose = crate::compress_objects(&refs, &cfg).expect("compress");
            assert!(
                is_zlib_stream(&loose[0]),
                "{kind}: the zlib header itself must be recognised"
            );
            assert!(
                looks_compressed(&loose[0]),
                "a git loose object must be stored raw"
            );
        }
    }

    /// A plausible first byte is not a zlib stream. `x` is `0x78`, the CMF of
    /// every stream git emits, so text starting with `x` is the exact trap the
    /// `FDICT` clause exists for.
    #[test]
    fn text_that_starts_like_a_zlib_header_is_still_compressed() {
        for (bytes, why) in [
            (b"x = 1;\n".as_slice(), "FLG 0x20 sets FDICT"),
            (b"x is a variable".as_slice(), "FLG 0x20 sets FDICT"),
            (b"x?y".as_slice(), "FLG 0x3f sets FDICT"),
            (b"x}".as_slice(), "FLG 0x7d sets FDICT"),
            (b"xyzzy".as_slice(), "FLG 0x79 fails the mod-31 check"),
            (b"xx".as_slice(), "FLG 0x78 fails the mod-31 check"),
            (b"\x78".as_slice(), "a lone CMF is not a header"),
            (
                b"\x18\x9c".as_slice(),
                "CM and FDICT are fine, but 0x189c fails the mod-31 check",
            ),
        ] {
            assert!(!is_zlib_stream(bytes), "{bytes:?} is not zlib: {why}");
            assert!(
                !looks_compressed(bytes),
                "{bytes:?} must still be compressed"
            );
        }
    }

    /// The negatives the reference implementation kept, which this file's own
    /// text cases do not cover: a would-be magic truncated below its own length,
    /// and an ELF header (a binary that compresses well and must not be mistaken
    /// for a container).
    #[test]
    fn compressible_content_and_truncated_magics_are_left_alone() {
        for (bytes, what) in [
            (
                b"SELECT * FROM njord WHERE id = 42;\n".as_slice(),
                "plain SQL",
            ),
            (
                b"{\"lake\": \"njord\", \"tables\": [1, 2, 3]}\n".as_slice(),
                "json",
            ),
            (
                b"pub fn main() -> Result<()> { Ok(()) }\n".as_slice(),
                "rust source",
            ),
            (b"<?xml version=\"1.0\"?><project/>\n".as_slice(), "xml"),
            (b"\x7fELF\x02\x01\x01\x00".as_slice(), "an ELF binary"),
            (b"".as_slice(), "nothing at all"),
            (b"P".as_slice(), "one byte of a would-be PACK"),
            (b"PAC".as_slice(), "three bytes of a would-be PACK"),
        ] {
            assert!(!looks_compressed(bytes), "{what} must still be compressed");
        }
    }
}