crates/gunnar-delta/src/encode.rs
//! The instruction emitter and the match loop. git's delta format, produced.
//!
//! # The format, read off the decoder
//!
//! The specification for this file is `gix_pack::data::delta::apply` and
//! `decode_header_size` (gix-pack 0.73, `src/data/delta.rs`). Nothing here is
//! taken from a prose description of the format; every field width and every
//! flag bit below is what that decoder reads.
//!
//! ```text
//! delta := size(base) size(result) instruction*
//! size := 7 bits per byte, little-endian groups, high bit continues
//! insert := 0x01..=0x7f followed by that many literal bytes
//! copy := 0x80|flags offset bytes (bits 0..3, low to high)
//! size bytes (bits 4..6, low to high)
//! ```
//!
//! Three details the decoder makes load-bearing and prose usually does not:
//!
//! * **A byte of the offset or size is written only when it is non-zero**, and
//! its flag bit is set only then. The decoder ORs in exactly the bytes whose
//! bits are set, so omitting a zero byte is not an optimisation, it is the
//! encoding.
//! * **`size == 0` means 65536.** This encoder never relies on that: a copy of
//! 65536 bytes naturally encodes as the single high byte `0x01` with bit `0x40`
//! set, which the decoder reads as `1 << 16`. Keeping the special case
//! unreachable removes an ambiguity rather than saving a byte.
//! * **Command byte 0 is reserved and rejected.** An insert of length 0 would
//! emit it, so the emitter must never be asked for an empty insert.
//!
//! # The consistency check that is not optional
//!
//! A wrong delta does not fail here. It fails at some later clone, as a corrupt
//! repository, arbitrarily far from the cause. So the emitter counts the bytes
//! its own instructions will produce and [`delta_into`] compares that total to
//! the target length before returning: an [`Error::Inconsistent`] rather than a
//! plausible-looking `Vec<u8>`. It is cheap (one add per instruction) and it is
//! the difference between a bug that surfaces in a unit test and a bug that
//! surfaces in a customer's repository.
use crate::error::{Error, Result};
use crate::index::{anchor_hash, fold, roll, Index, ANCHOR};
use crate::limits::Limits;
use crate::scan::{common_prefix_len, common_suffix_len};
/// Largest run of literal bytes one insert instruction can carry.
const MAX_INSERT: usize = 0x7f;
/// Largest run one copy instruction can carry, at three size bytes.
const MAX_COPY: usize = 0xff_ffff;
/// How to encode one base→target pair.
#[derive(Debug, Clone)]
pub struct Encode {
/// Give up once the delta reaches this many bytes, returning `Ok(None)`.
///
/// This is the pruning that makes a window search affordable: the driver
/// sets it to the best delta found so far, so every later candidate either
/// beats it or stops early. `None` means encode to completion.
pub max_size: Option<usize>,
/// Most index entries examined per target position.
///
/// Bounds the worst case on degenerate input. A base of one repeated byte
/// puts every anchor in one bucket, and without this the scan is quadratic.
/// Deterministic, because bucket order is fixed at build time.
pub max_chain: usize,
/// Stop looking once a match this long is found.
///
/// git uses 4096 for the same reason: past that the marginal byte saved is
/// not worth the remaining candidates.
pub good_enough: usize,
/// Memory and size caps. See [`Limits`].
pub limits: Limits,
}
impl Default for Encode {
fn default() -> Self {
Encode {
max_size: None,
max_chain: 64,
good_enough: 4096,
limits: Limits::default(),
}
}
}
/// Instruction emitter with a running count of what it will reconstruct.
struct Emit<'a> {
out: &'a mut Vec<u8>,
produced: u64,
}
impl Emit<'_> {
/// `size := 7 bits per byte, little-endian groups, high bit continues`.
fn varint(&mut self, mut n: u64) {
while n >= 0x80 {
self.out.push((n as u8) | 0x80);
n >>= 7;
}
self.out.push(n as u8);
}
/// Literal bytes, split into runs of at most 127.
fn insert(&mut self, mut data: &[u8]) {
while !data.is_empty() {
let n = data.len().min(MAX_INSERT);
self.out.push(n as u8);
self.out.extend_from_slice(&data[..n]);
self.produced += n as u64;
data = &data[n..];
}
}
/// A copy from the base, split into runs of at most `0xffffff`.
fn copy(&mut self, mut offset: u32, mut size: usize) {
debug_assert!(size > 0, "an empty copy would emit a reserved command byte");
while size > 0 {
let n = size.min(MAX_COPY);
self.copy_one(offset, n as u32);
self.produced += n as u64;
offset += n as u32;
size -= n;
}
}
fn copy_one(&mut self, offset: u32, size: u32) {
debug_assert!(size > 0 && size as usize <= MAX_COPY);
let cmd_at = self.out.len();
self.out.push(0x80);
let mut flags = 0u8;
for (bit, shift) in [(0x01u8, 0u32), (0x02, 8), (0x04, 16), (0x08, 24)] {
let b = (offset >> shift) as u8;
if b != 0 {
flags |= bit;
self.out.push(b);
}
}
for (bit, shift) in [(0x10u8, 0u32), (0x20, 8), (0x40, 16)] {
let b = (size >> shift) as u8;
if b != 0 {
flags |= bit;
self.out.push(b);
}
}
debug_assert_ne!(
flags, 0,
"a copy with no bytes at all would decode as 65536 at offset 0"
);
self.out[cmd_at] = 0x80 | flags;
}
}
/// Encode `target` as a delta against `base`, appending into `out`.
///
/// Returns `Ok(false)`, leaving `out` truncated back to its original length,
/// when `opts.max_size` was reached, which is an ordinary outcome and not an
/// error. `index` must have been built over `base`.
pub(crate) fn delta_into_with_index(
base: &[u8],
target: &[u8],
index: Option<&Index>,
out: &mut Vec<u8>,
opts: &Encode,
) -> Result<bool> {
let restore_to = out.len();
let budget = opts.max_size.unwrap_or(usize::MAX);
let mut e = Emit { out, produced: 0 };
e.varint(base.len() as u64);
e.varint(target.len() as u64);
let mut p = 0usize;
let mut pending = 0usize;
let mut hash: u64 = 0;
let mut hash_valid = false;
while p + ANCHOR <= target.len() {
hash = if hash_valid {
roll(hash, target[p - 1], target[p + ANCHOR - 1])
} else {
hash_valid = true;
anchor_hash(&target[p..p + ANCHOR])
};
let (mut best_len, mut best_at) = (0usize, 0usize);
if let Some(index) = index {
let folded = fold(hash);
let (positions, hashes) = index.bucket(folded);
let scan = positions.len().min(opts.max_chain);
for k in 0..scan {
if hashes[k] != folded {
continue;
}
let q = positions[k] as usize;
// Reject without touching the base twice: if the byte one past
// the current best does not match, this candidate cannot beat it.
if best_len > 0 {
let (bq, bp) = (q + best_len, p + best_len);
if bq >= base.len() || bp >= target.len() || base[bq] != target[bp] {
continue;
}
}
let len = common_prefix_len(&base[q..], &target[p..]);
if len > best_len {
best_len = len;
best_at = q;
if len >= opts.good_enough {
break;
}
}
}
}
// A hash hit is confirmed over the whole anchor by `common_prefix_len`,
// so any match reaching here is at least ANCHOR long, which is always
// cheaper than the 16 insert bytes it replaces.
if best_len >= ANCHOR {
// Extend backwards into the bytes still pending as literals. This is
// free compression: those bytes were going to be written out anyway.
let room = best_at.min(p - pending);
let back = common_suffix_len(&base[best_at - room..best_at], &target[p - room..p]);
if p - back > pending {
e.insert(&target[pending..p - back]);
}
e.copy((best_at - back) as u32, best_len + back);
p += best_len;
pending = p;
hash_valid = false;
} else {
p += 1;
}
if e.out.len() - restore_to >= budget {
e.out.truncate(restore_to);
return Ok(false);
}
}
if pending < target.len() {
e.insert(&target[pending..]);
}
let produced = e.produced;
if produced != target.len() as u64 {
out.truncate(restore_to);
return Err(Error::Inconsistent {
produced,
expected: target.len() as u64,
});
}
if out.len() - restore_to >= budget {
out.truncate(restore_to);
return Ok(false);
}
Ok(true)
}
/// Encode `target` as a delta against `base`, appending into `out`.
///
/// `Ok(false)` means `opts.max_size` was reached and `out` is unchanged.
pub fn delta_into(base: &[u8], target: &[u8], out: &mut Vec<u8>, opts: &Encode) -> Result<bool> {
let index = Index::build(base, &opts.limits)?;
delta_into_with_index(base, target, index.as_ref(), out, opts)
}
/// Encode `target` as a delta against `base` with default options.
///
/// The bytes returned are a complete git delta payload: the same thing a
/// packfile carries in an `OFS_DELTA` or `REF_DELTA` entry, after
/// decompression.
pub fn delta(base: &[u8], target: &[u8]) -> Result<Vec<u8>> {
let mut out = Vec::new();
let opts = Encode::default();
// `max_size` is None, so the only `false` this can return is unreachable.
let complete = delta_into(base, target, &mut out, &opts)?;
debug_assert!(complete);
Ok(out)
}
#[cfg(test)]
mod tests {
use super::*;
/// The varint the header uses must be exactly what `decode_header_size`
/// reads back: 7 bits per byte, little-endian, high bit continues.
#[test]
fn header_varint_matches_the_decoders_shape() {
for n in [0u64, 1, 0x7f, 0x80, 300, 65535, 1 << 20, u32::MAX as u64] {
let mut out = Vec::new();
Emit {
out: &mut out,
produced: 0,
}
.varint(n);
// The decoder's loop, transcribed.
let (mut size, mut shift) = (0u64, 0u32);
let mut consumed = 0usize;
for cmd in &out {
consumed += 1;
size |= (u64::from(*cmd) & 0x7f) << shift;
shift += 7;
if cmd & 0x80 == 0 {
break;
}
}
assert_eq!(size, n, "varint {n} round-trip");
assert_eq!(consumed, out.len(), "varint {n} left trailing bytes");
}
}
#[test]
fn a_copy_of_exactly_65536_bytes_does_not_use_the_reserved_zero_size() {
let mut out = Vec::new();
Emit {
out: &mut out,
produced: 0,
}
.copy_one(0, 0x10000);
assert_eq!(out, vec![0x80 | 0x40, 0x01], "expected one high size byte");
}
#[test]
fn an_insert_never_emits_the_reserved_command_byte_zero() {
let mut out = Vec::new();
Emit {
out: &mut out,
produced: 0,
}
.insert(&vec![0u8; 300]);
let mut i = 0;
let mut runs = 0;
while i < out.len() {
assert_ne!(out[i], 0, "reserved command byte 0 at {i}");
assert!(out[i] < 0x80, "expected an insert opcode at {i}");
i += 1 + out[i] as usize;
runs += 1;
}
assert_eq!(runs, 3, "300 bytes should split into 127+127+46");
}
}