znippy_plugin_git/

delta.rs

//! **Computing a git delta**, for the one entry shape this engine cannot copy.
//!
//! # Why an engine whose whole claim is "it copies" computes anything at all
//!
//! [`crate::git_ops::GitStore::emit_set`] copies stored pack entries byte for
//! byte, and that is the product. One shape defeats it: a stored delta whose
//! base falls **outside** the request. The base cannot be added — a base pulled
//! into a narrowed clone drags an object the client never asked for, and if it
//! is a tree it arrives owing children the pack does not carry, which is the
//! `did not receive expected object` defect §2 of the standing report records.
//! Naming the base by oid in a `REF_DELTA` works for a *fetch*, where the
//! receiver already holds it, and cannot work for a *clone*, where the receiver
//! holds nothing.
//!
//! That left exactly one answer for a clone: **send the object whole**. Measured
//! on `h2h-linear-sha1-2048c-1024f-16k`, that is 961 of 31 805 entries — 3.0 % —
//! and it doubled the wire: 11 613 666 bytes where stock git sends 5 820 000 for
//! the identical object set. Three per cent of the entries were essentially all
//! of a 2× gap, because the 961 are 16 KiB blobs whose stored delta is 284 bytes.
//!
//! So this module exists to answer the third option: **re-delta the boundary
//! entry against something the pack DOES carry.** It is the only place in this
//! crate that computes a delta, `crate::git_ops::GitStore::whole_entry` is the
//! only other place that deflates on a serving path, and both run on the same
//! boundary fraction and nowhere else.
//!
//! # The receipt stays a fact
//!
//! An entry this produces is [`crate::pack_walk::EmitEntry::recompressed`], same
//! as the whole rebuild it replaces — its payload really was inflated and
//! re-deflated, and `copied + recompressed == objects` is unchanged. What is new
//! is [`crate::pack_walk::EmitEntry::deltified`], a strict subset of
//! `recompressed`: *of the entries that had to be rebuilt, this many went out as
//! a computed delta rather than whole*. A full clone measures all three as zero,
//! because a whole-repository request contains every base.
//!
//! # The format
//!
//! git's delta stream, which [`crate::resolve`] already applies: the base's size
//! and the target's size as LEB128, then instructions. A byte with the top bit
//! set is a **copy** — the low nibble selects which of four offset bytes follow,
//! bits 4-6 which of three size bytes, all little-endian and all absent when
//! zero. A byte with the top bit clear is an **insert** of that many literal
//! bytes, 1..=127.
//!
//! Two encoding hazards, both avoided by construction rather than by comment:
//!
//! * a copy whose three size bytes are all zero means **65536**, not zero, so a
//!   zero-length copy must never be emitted — [`Delta::copy`] is only ever
//!   called with `len >= MIN_MATCH`;
//! * a copy offset is four bytes, so a base at or past 4 GiB cannot be named.
//!   [`delta`] refuses such a base up front rather than truncating one.
//!
//! # The search, and what it deliberately does not do
//!
//! `git pack-objects` sorts every object by type, path hash and size and then
//! tries a sliding window of 10 candidates per object, at `pack.depth` 50. That
//! is a *global* search and it is the expensive half of packing.
//!
//! This does none of it. The caller arrives with **one** candidate base — the
//! nearest ancestor of the entry's own stored delta chain that is inside the
//! request — and this module only has to encode against it. The candidate is
//! free: it is read out of the archive's own back-references, which are the
//! packer's original similarity judgement, already made and already stored.
//!
//! # What it produced, end to end
//!
//! One server process, one seeded store, oden 2026-08-11, `git fsck --full
//! --strict` exit 0 on every arm. The only difference between the columns is
//! [`enabled`]:
//!
//! ```text
//! arm                      objects   whole (off)   re-delta (on)
//! full clone                36 172     6 200 252     6 200 252    unchanged
//! narrowed clone `base`     31 805    11 613 666     6 424 726    1.81x
//! --filter=blob:none        16 491     1 566 022     1 566 022    unchanged
//! incremental fetch          4 367     1 339 879     1 339 879    unchanged
//! ```
//!
//! The narrowed pack's own entry shapes say where it went: **3 153 whole
//! entries become 2 294**, so exactly **859** of the 961 found an in-request
//! ancestor — the number this module's search predicted before it was written —
//! and 5 188 940 bytes came off, 6 041 per entry. Stock git sends 5 820 000 for
//! the same 31 805 objects, so what was **2.00× git** is now **1.10×**.
//!
//! # Cost
//!
//! One pass over the base to index it and one over the target to encode, both
//! linear, with a 16-byte block hash and a bounded collision chain, plus one
//! inflate of the base — which the single-slot cache spares for a run of
//! entries sharing one ancestor.
//!
//! Against that, the *deflate* it feeds is strictly cheaper than the one it
//! replaces: a ~1 KB delta instead of a 16 KiB object. The two roughly cancel.
//! Measured on the server's own `utime + stime` over 10 narrowed clones, three
//! interleaved rounds, CPU pressure gated below 2.00: **139 ms per clone with
//! it on, 137 ms with it off**, against a within-arm spread of 133-145. So the
//! 1.81× on the wire costs nothing measurable in CPU, which is the trade this
//! engine had to be able to make and could not be assumed.

use anyhow::Result;

/// **Is the boundary re-delta on?** `true` unless `ZNIPPY_GIT_BOUNDARY_DELTA` is
/// set to `0`, `off` or `false`.
///
/// It exists so the trade this module makes — wire bytes against clone CPU — can
/// be measured as an A/B on **one binary against one seeded store**, rather than
/// against two builds whose difference nobody can pin down afterwards. Read once
/// and cached: this is on the path of every request, and a `getenv` per served
/// object is exactly the kind of cost an engine that claims CPU should not add.
///
/// Off, every boundary entry is shipped whole, which is the behaviour before
/// this module existed and is always correct.
pub fn enabled() -> bool {
    static ON: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
    *ON.get_or_init(|| match crate::arms::read_env(crate::arms::ENV_BOUNDARY_DELTA) {
        Some(v) => !matches!(v.to_ascii_lowercase().as_str(), "0" | "off" | "false"),
        None => true,
    })
}

/// The block size the base is indexed at, and the shortest match worth a copy
/// instruction.
///
/// git's `diff-delta.c` uses 16 for the same two purposes. Below it a copy
/// instruction (1-8 bytes) stops being cheaper than the literal it replaces.
const MIN_MATCH: usize = 16;

/// How many index entries sharing one hash bucket are probed before giving up
/// on the position.
///
/// A bound and not a completeness property: a base full of one repeated block
/// would otherwise make the encoder quadratic. git bounds the same walk.
const MAX_PROBE: usize = 4;

/// A copy instruction names its base offset in **four** bytes.
const MAX_BASE: usize = u32::MAX as usize;

/// A copy instruction names its length in **three** bytes. `0` is not zero, it
/// is 65536, so lengths are capped below the point where that could be emitted.
const MAX_COPY: usize = 0xff_ffff;

/// **A git delta that rebuilds `target` out of `base`**, or `None` when there is
/// no point sending one.
///
/// `None` — not an error — for every case where the whole object is the better
/// answer, and the caller's fallback is exactly that. Two conditions produce it,
/// and only two:
///
/// * a base at or past 4 GiB, which a copy offset cannot name. Checked up
///   front, because nothing downstream could notice a truncated offset;
/// * **a delta that came out no smaller than the target itself.** This is the
///   guard that makes a badly chosen candidate merely useless rather than
///   harmful, and it is also what answers every degenerate input — an empty
///   base, an empty target, a base shorter than one block — without a special
///   case for any of them, because all of them produce a literal-only encoding
///   that is longer than what it encodes. An earlier revision checked the
///   empties separately; removing that check changed no outcome on any input,
///   which is the definition of a guard that could never fail.
///
/// The size comparison is against the **raw** target length rather than the
/// deflated one, because the delta is deflated afterwards by the same encoder at
/// the same level: comparing the two before compression compares like with like
/// and costs no extra deflate to decide.
pub fn delta(base: &[u8], target: &[u8]) -> Result<Option<Vec<u8>>> {
    if base.len() > MAX_BASE {
        return Ok(None);
    }

    let index = BlockIndex::build(base);
    let mut d = Delta::new(base.len(), target.len());

    let mut i = 0usize;
    let mut literal_from = 0usize;
    while i < target.len() {
        let m = if i + MIN_MATCH <= target.len() {
            index.longest_match(base, target, i)
        } else {
            None
        };
        match m {
            Some((at, len)) => {
                d.literal(&target[literal_from..i]);
                d.copy(at, len);
                i += len;
                literal_from = i;
            }
            None => i += 1,
        }
        // A delta that has already outgrown its target cannot win, and every
        // further byte of search is spent for nothing.
        if d.out.len() >= target.len() {
            return Ok(None);
        }
    }
    d.literal(&target[literal_from..]);

    if d.out.len() >= target.len() {
        return Ok(None);
    }
    Ok(Some(d.out))
}

/// The delta being built, and the two instruction encoders.
struct Delta {
    out: Vec<u8>,
}

impl Delta {
    fn new(base_len: usize, target_len: usize) -> Self {
        // The delta will be a fraction of the target for the shape this runs on;
        // a quarter is a starting point, not a bound.
        let mut out = Vec::with_capacity(target_len / 4 + 32);
        varint(&mut out, base_len as u64);
        varint(&mut out, target_len as u64);
        Delta { out }
    }

    /// Literal bytes, in runs of at most 127 — the largest an insert opcode can
    /// name, because the opcode *is* the length and its top bit means copy.
    fn literal(&mut self, bytes: &[u8]) {
        for chunk in bytes.chunks(0x7f) {
            self.out.push(chunk.len() as u8);
            self.out.extend_from_slice(chunk);
        }
    }

    /// `base[at..at + len]`, as one or more copy instructions.
    ///
    /// **`len` must be non-zero**: three zero size bytes decode as 65536, so an
    /// empty copy is not encodable and is not a thing this is ever asked for —
    /// the only caller has already matched at least [`MIN_MATCH`] bytes.
    fn copy(&mut self, at: usize, len: usize) {
        debug_assert!(len > 0, "a zero-length copy encodes as 65536");
        let mut at = at;
        let mut left = len;
        while left > 0 {
            let n = left.min(MAX_COPY);
            let opcode_at = self.out.len();
            self.out.push(0x80);
            let mut op = 0x80u8;
            for shift in 0..4 {
                let b = ((at >> (shift * 8)) & 0xff) as u8;
                if b != 0 {
                    op |= 1 << shift;
                    self.out.push(b);
                }
            }
            for shift in 0..3 {
                let b = ((n >> (shift * 8)) & 0xff) as u8;
                if b != 0 {
                    op |= 0x10 << shift;
                    self.out.push(b);
                }
            }
            self.out[opcode_at] = op;
            at += n;
            left -= n;
        }
    }
}

/// git's delta-header size encoding: LEB128, little end first.
fn varint(out: &mut Vec<u8>, mut n: u64) {
    loop {
        let mut b = (n & 0x7f) as u8;
        n >>= 7;
        if n > 0 {
            b |= 0x80;
        }
        out.push(b);
        if n == 0 {
            return;
        }
    }
}

/// Where each 16-byte block of the base starts, keyed by a hash of its content.
///
/// Open buckets in one flat `Vec` with a power-of-two mask, and a per-bucket
/// chain held as a second `Vec` of "next" links — one allocation each rather
/// than a `HashMap<u64, Vec<u32>>`, which is one allocation *per distinct
/// block* on a path that runs per object served.
struct BlockIndex {
    /// `mask + 1` buckets, each the head of a chain or `NONE`.
    head: Vec<u32>,
    /// For block `k`, the next block in its bucket, or `NONE`.
    next: Vec<u32>,
    mask: usize,
}

const NONE: u32 = u32::MAX;

impl BlockIndex {
    fn build(base: &[u8]) -> Self {
        let blocks = base.len() / MIN_MATCH;
        let mut buckets = 1usize;
        while buckets < blocks.max(1) * 2 {
            buckets <<= 1;
        }
        let mut idx = BlockIndex {
            head: vec![NONE; buckets],
            next: vec![NONE; blocks],
            mask: buckets - 1,
        };
        // Inserted **last block first**, so each bucket's chain runs
        // lowest-offset-first afterwards. Two blocks with identical content are
        // then probed in base order, which keeps the encoder's output a function
        // of its inputs and not of the insertion order.
        for k in (0..blocks).rev() {
            let at = k * MIN_MATCH;
            let b = (block_hash(&base[at..at + MIN_MATCH]) as usize) & idx.mask;
            idx.next[k] = idx.head[b];
            idx.head[b] = k as u32;
        }
        idx
    }

    /// The longest run of `target` from `from` that also appears in `base`, and
    /// where in `base` it starts — or `None` if nothing reaches [`MIN_MATCH`].
    fn longest_match(
        &self,
        base: &[u8],
        target: &[u8],
        from: usize,
    ) -> Option<(usize, usize)> {
        let probe = &target[from..from + MIN_MATCH];
        let b = (block_hash(probe) as usize) & self.mask;
        let mut best: Option<(usize, usize)> = None;
        let mut k = self.head[b];
        let mut tried = 0usize;
        while k != NONE && tried < MAX_PROBE {
            let at = k as usize * MIN_MATCH;
            k = self.next[k as usize];
            // The hash is a hint. Two different blocks share a bucket often
            // enough that skipping this comparison would emit a copy of bytes
            // the base does not hold — a pack that `index-pack` accepts and
            // whose objects hash to something else.
            if &base[at..at + MIN_MATCH] != probe {
                tried += 1;
                continue;
            }
            tried += 1;
            let mut len = MIN_MATCH;
            while at + len < base.len()
                && from + len < target.len()
                && base[at + len] == target[from + len]
                && len < MAX_COPY
            {
                len += 1;
            }
            if best.is_none_or(|(_, prev)| len > prev) {
                best = Some((at, len));
            }
        }
        best
    }
}

/// A cheap, well-mixed hash of exactly [`MIN_MATCH`] bytes.
///
/// Two `u64` reads and a multiply rather than a byte loop: this runs once per
/// **byte** of every target that does not match, so a 16-iteration loop here is
/// a 16× cost on the encoder's hot path.
#[inline]
fn block_hash(b: &[u8]) -> u64 {
    debug_assert_eq!(b.len(), MIN_MATCH);
    let lo = u64::from_le_bytes(b[0..8].try_into().expect("16 bytes"));
    let hi = u64::from_le_bytes(b[8..16].try_into().expect("16 bytes"));
    (lo ^ hi.rotate_left(29)).wrapping_mul(0x9E37_79B9_7F4A_7C15)
}

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

    /// A minimal, independent applier — **not** this module's, and not
    /// `crate::resolve`'s either.
    ///
    /// The oracle that actually matters is stock git, and
    /// `crate::serve::tests::a_narrowed_clone_reuses_an_in_request_base_instead_of_shipping_whole`
    /// runs `index-pack --strict` over a pack built out of these deltas. This
    /// one exists for the cases that are awkward to reach through a whole pack —
    /// the 65536 copy, the 4 GiB refusal — and it is written from the format
    /// description rather than from the encoder, which is the only way a decoder
    /// can catch an encoder rather than agree with it.
    fn apply(base: &[u8], d: &[u8]) -> Vec<u8> {
        let mut i = 0usize;
        let n = |i: &mut usize| {
            let mut v = 0u64;
            let mut s = 0;
            loop {
                let b = d[*i];
                *i += 1;
                v |= u64::from(b & 0x7f) << s;
                s += 7;
                if b & 0x80 == 0 {
                    return v;
                }
            }
        };
        let base_size = n(&mut i);
        assert_eq!(base_size as usize, base.len(), "declared base size");
        let target_size = n(&mut i);
        let mut out = Vec::new();
        while i < d.len() {
            let op = d[i];
            i += 1;
            if op & 0x80 != 0 {
                let mut off = 0usize;
                for bit in 0..4 {
                    if op & (1 << bit) != 0 {
                        off |= (d[i] as usize) << (bit * 8);
                        i += 1;
                    }
                }
                let mut size = 0usize;
                for bit in 0..3 {
                    if op & (0x10 << bit) != 0 {
                        size |= (d[i] as usize) << (bit * 8);
                        i += 1;
                    }
                }
                if size == 0 {
                    size = 0x1_0000;
                }
                out.extend_from_slice(&base[off..off + size]);
            } else {
                let k = op as usize;
                assert_ne!(k, 0, "a zero-length insert is not a valid instruction");
                out.extend_from_slice(&d[i..i + k]);
                i += k;
            }
        }
        assert_eq!(out.len() as u64, target_size, "declared target size");
        out
    }

    /// Pseudo-random bytes, so a "delta" that quietly shipped literals would
    /// show up as a size rather than passing on compressible filler.
    fn noise(n: usize, seed: u64) -> Vec<u8> {
        let mut s = seed | 1;
        (0..n)
            .map(|_| {
                s ^= s << 13;
                s ^= s >> 7;
                s ^= s << 17;
                (s >> 33) as u8
            })
            .collect()
    }

    /// 🔴 **The delta rebuilds the target exactly, and is much smaller than it.**
    ///
    /// Both halves are load-bearing and neither alone is worth anything: an
    /// encoder that emits one giant insert round-trips perfectly and saves
    /// nothing, and one that emits a wrong copy offset is small and produces an
    /// object with a different hash. The corpus is incompressible noise with one
    /// 64-byte splice, which is the boundary blob's real shape — 16 KiB that
    /// differs from its neighbour in a few hundred bytes.
    #[test]
    fn a_computed_delta_round_trips_and_is_a_fraction_of_the_target() {
        let base = noise(16 * 1024, 0x1234);
        let mut target = base.clone();
        target[4096..4160].copy_from_slice(&noise(64, 0x99));
        target.extend_from_slice(&noise(128, 0x77));

        let d = delta(&base, &target).unwrap().expect("a near-copy deltas");
        assert_eq!(apply(&base, &d), target, "the delta must rebuild the target");
        assert!(
            d.len() * 20 < target.len(),
            "a 16 KiB target differing in ~200 bytes must delta to well under 5 % of it, got {} \
             of {}",
            d.len(),
            target.len()
        );
    }

    /// A copy longer than 65536 is split rather than encoded as a zero size,
    /// which decodes as 65536 and would silently truncate.
    #[test]
    fn a_copy_of_exactly_65536_bytes_is_not_encoded_as_a_zero_size() {
        let base = noise(200_000, 0xBEEF);
        // Target = base[0..0x10000] and nothing else, so the encoder is forced
        // to emit a copy of exactly the length that is unencodable as three
        // zero bytes.
        let target = base[..0x1_0000].to_vec();
        let d = delta(&base, &target).unwrap().expect("a pure prefix deltas");
        assert_eq!(apply(&base, &d), target, "the 65536 boundary must round trip");
    }

    /// Nothing in common: the encoder must **decline**, not ship a delta that is
    /// longer than the object it replaces.
    ///
    /// This is what makes a badly chosen candidate base merely useless. Without
    /// it a wrong base costs bytes *and* the re-deflate.
    #[test]
    fn an_unrelated_base_declines_rather_than_growing_the_entry() {
        let base = noise(8192, 1);
        let target = noise(8192, 2);
        assert!(
            delta(&base, &target).unwrap().is_none(),
            "two unrelated buffers have no delta worth sending"
        );
    }

    /// Degenerate inputs answer `None`, and the **grow guard** is what makes
    /// them — there is no special case for an empty side and there must not be
    /// one.
    ///
    /// 🔴 This is a rewrite. It used to assert the same two `is_none()`s against
    /// an implementation that checked `is_empty()` up front, and deleting that
    /// check left the test **green** — the grow guard was already producing the
    /// answer. A guard that cannot fail is not a guard, so the check went and
    /// the test now names the mechanism it is really pinning. Seen red by
    /// removing the grow guard: `delta(b"", b"anything")` then returns an
    /// 11-byte "delta" for 8 bytes of target.
    ///
    /// A base below one block is in here for the same reason: it exercises a
    /// `BlockIndex` with zero blocks, which is the shape an index built by
    /// division would panic or mis-size on.
    #[test]
    fn degenerate_inputs_decline_through_the_grow_guard_and_not_a_special_case() {
        for (base, target) in [
            (&b""[..], &b"anything"[..]),
            (&b"anything"[..], &b""[..]),
            (&b""[..], &b""[..]),
            (&b"short"[..], &b"also short"[..]),
        ] {
            assert!(
                delta(base, target).unwrap().is_none(),
                "base {} bytes, target {} bytes: a delta no smaller than its target must decline",
                base.len(),
                target.len()
            );
        }
    }

    /// A target that is a **prefix** of its base, and one that is an extension:
    /// the two shapes where an off-by-one in the match extension shows up as a
    /// truncated or over-long copy rather than as a crash.
    #[test]
    fn prefixes_and_extensions_round_trip() {
        let base = noise(4096, 7);
        for target in [
            base[..1000].to_vec(),
            base[..4095].to_vec(),
            {
                let mut t = base.clone();
                t.extend_from_slice(&noise(3, 9));
                t
            },
            {
                let mut t = noise(3, 11);
                t.extend_from_slice(&base);
                t
            },
        ] {
            let d = delta(&base, &target)
                .unwrap()
                .unwrap_or_else(|| panic!("a {}-byte near-copy must delta", target.len()));
            assert_eq!(apply(&base, &d), target, "{} bytes", target.len());
        }
    }
}