plugins/native/znippy-plugin-git/src/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());
}
}
}