crates/gunnar-delta/src/index.rs
//! The base index: a bucketed table of 16-byte anchors, built once per base.
//!
//! # Shape
//!
//! git's `create_delta_index` indexes the base at every `RABIN_WINDOW`-byte
//! block boundary and looks the target up with a rolling hash slid one byte at a
//! time. That asymmetry is the trick: sliding the *target* by one while
//! anchoring the *base* every 16 bytes still finds every match of length ≥ 16,
//! at a sixteenth of the index size. This is the same shape, with a Karp–Rabin
//! polynomial in place of git's Rabin tables. The hash is internal and has no
//! effect on the output format, only on match quality, and every hit is
//! confirmed by comparison before it is used.
//!
//! # Layout, and why it is three flat arrays
//!
//! `heads` / `positions` / `hashes` is a counting sort into buckets: no linked
//! lists, no per-bucket `Vec`, one allocation each. A bucket is
//! `positions[heads[b]..heads[b+1]]`, and `hashes[k]` is the folded hash of
//! `positions[k]`'s block so a candidate can be rejected without touching the
//! base at all. That rejection is most of the win, because the base is a large,
//! randomly-accessed array and a cache miss on it costs more than the compare it
//! was avoiding.
//!
//! # Memory
//!
//! `n/16 × 8 + buckets × 4` bytes, which is about `0.75 × n`. That is the number
//! [`crate::Limits::max_base_size`] exists to bound, because the encoder caches
//! `window + 1` of these per thread.
use crate::error::Result;
use crate::limits::Limits;
/// The anchor width. Matches git's `RABIN_WINDOW`, and with it the smallest
/// match this index can find.
pub(crate) const ANCHOR: usize = 16;
/// Karp–Rabin multiplier: the FNV-1a 64-bit prime, odd, with well-distributed
/// low bits and no table.
const M: u64 = 0x0000_0100_0000_01b3;
const fn pow(mut base: u64, mut exp: u32) -> u64 {
let mut acc: u64 = 1;
while exp > 0 {
if exp & 1 == 1 {
acc = acc.wrapping_mul(base);
}
base = base.wrapping_mul(base);
exp >>= 1;
}
acc
}
/// `M^ANCHOR`, the coefficient of the byte leaving the window.
const M_POW_ANCHOR: u64 = pow(M, ANCHOR as u32);
/// Hash of `w`, which must be exactly [`ANCHOR`] bytes.
#[inline]
pub(crate) fn anchor_hash(w: &[u8]) -> u64 {
debug_assert_eq!(w.len(), ANCHOR);
let mut h: u64 = 0;
for &b in w {
h = h.wrapping_mul(M).wrapping_add(u64::from(b));
}
h
}
/// Slide the window one byte: `out` leaves at the front, `inb` joins at the back.
#[inline]
pub(crate) fn roll(h: u64, out: u8, inb: u8) -> u64 {
h.wrapping_mul(M)
.wrapping_sub(u64::from(out).wrapping_mul(M_POW_ANCHOR))
.wrapping_add(u64::from(inb))
}
/// Mix the polynomial down to 32 bits used both as the bucket selector and the
/// stored filter. Multiplying by the golden-ratio constant and taking the high
/// half is what stops a low-entropy polynomial from piling into one bucket.
#[inline]
pub(crate) fn fold(h: u64) -> u32 {
(h.wrapping_mul(0x9E37_79B9_7F4A_7C15) >> 32) as u32
}
/// A built index over one base object's bytes.
pub(crate) struct Index {
/// `buckets + 1` offsets into `positions`/`hashes`.
heads: Vec<u32>,
/// Block start offsets in the base, grouped by bucket.
positions: Vec<u32>,
/// `fold(anchor_hash)` of each entry, for rejection without a base read.
hashes: Vec<u32>,
mask: u32,
/// What [`Index::bytes`] reports, and the cache's budget unit.
bytes: usize,
}
impl Index {
/// Build an index over `base`, or `Ok(None)` if `base` is too short to hold
/// a single anchor.
///
/// Refuses rather than attempts anything above
/// [`Limits::max_index_bytes`].
pub(crate) fn build(base: &[u8], limits: &Limits) -> Result<Option<Index>> {
if base.len() < ANCHOR {
return Ok(None);
}
// A copy instruction's offset field is 32 bits wide. A base at or above
// 4 GiB cannot be addressed by the format at all, so this is a property
// of git's delta encoding, not a policy choice.
Limits::check("base object size", base.len() as u64, u32::MAX as u64)?;
let n_blocks = base.len() / ANCHOR;
let buckets = n_blocks.next_power_of_two().max(16);
let bytes = n_blocks * 8 + (buckets + 1) * 4;
Limits::check(
"base index size",
bytes as u64,
limits.max_index_bytes as u64,
)?;
let mask = (buckets - 1) as u32;
// Pass 1: hash every block and count per bucket.
let mut folded = vec![0u32; n_blocks];
let mut heads = vec![0u32; buckets + 1];
for (blk, slot) in folded.iter_mut().enumerate() {
let at = blk * ANCHOR;
let f = fold(anchor_hash(&base[at..at + ANCHOR]));
*slot = f;
heads[(f & mask) as usize + 1] += 1;
}
// Prefix sum: `heads[b]` becomes the start of bucket `b`.
for b in 0..buckets {
heads[b + 1] += heads[b];
}
// Pass 2, scatter. `cursor` walks each bucket, so within a bucket the
// entries stay in ascending block order and the candidate scan is
// deterministic.
let mut positions = vec![0u32; n_blocks];
let mut hashes = vec![0u32; n_blocks];
let mut cursor: Vec<u32> = heads[..buckets].to_vec();
for (blk, &f) in folded.iter().enumerate() {
let b = (f & mask) as usize;
let k = cursor[b] as usize;
cursor[b] += 1;
positions[k] = (blk * ANCHOR) as u32;
hashes[k] = f;
}
Ok(Some(Index {
heads,
positions,
hashes,
mask,
bytes,
}))
}
/// Approximate resident size, for the cache budget.
pub(crate) fn bytes(&self) -> usize {
self.bytes
}
/// The candidate run for a folded hash: parallel slices of positions and
/// their filters, in a fixed order.
#[inline]
pub(crate) fn bucket(&self, folded: u32) -> (&[u32], &[u32]) {
let b = (folded & self.mask) as usize;
let (s, e) = (self.heads[b] as usize, self.heads[b + 1] as usize);
(&self.positions[s..e], &self.hashes[s..e])
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn rolling_hash_agrees_with_a_fresh_hash_at_every_offset() {
let data: Vec<u8> = (0..4096u32)
.map(|i| (i.wrapping_mul(2654435761) >> 13) as u8)
.collect();
let mut h = anchor_hash(&data[..ANCHOR]);
for p in 1..=(data.len() - ANCHOR) {
h = roll(h, data[p - 1], data[p + ANCHOR - 1]);
assert_eq!(
h,
anchor_hash(&data[p..p + ANCHOR]),
"rolled hash diverged at offset {p}"
);
}
}
#[test]
fn every_indexed_block_is_findable_in_its_own_bucket() {
let data: Vec<u8> = (0..100_000u32).map(|i| (i % 251) as u8).collect();
let idx = Index::build(&data, &Limits::default()).unwrap().unwrap();
for blk in 0..data.len() / ANCHOR {
let at = blk * ANCHOR;
let f = fold(anchor_hash(&data[at..at + ANCHOR]));
let (pos, hs) = idx.bucket(f);
assert!(
pos.iter()
.zip(hs)
.any(|(&p, &h)| p as usize == at && h == f),
"block at {at} missing from its bucket"
);
}
}
#[test]
fn a_base_shorter_than_one_anchor_has_no_index() {
assert!(Index::build(&[1, 2, 3], &Limits::default())
.unwrap()
.is_none());
}
#[test]
fn an_index_above_the_byte_cap_is_refused_not_attempted() {
let limits = Limits {
max_index_bytes: 1024,
..Limits::default()
};
let data = vec![7u8; 1024 * 1024];
match Index::build(&data, &limits) {
Err(crate::Error::Refused { what, limit, .. }) => {
assert_eq!(what, "base index size");
assert_eq!(limit, 1024);
}
other => panic!(
"expected a refusal, got {other:?}",
other = other.map(|o| o.is_some())
),
}
}
}