ldeflate/src/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");
}
}
}