delta-kit

A binary-safe delta codec for Rust: compute a compact delta between two byte strings and apply it to reconstruct the target. Byte-compatible wire format with the suture-protocol crate it was extracted from.

Extracted from the Suture codebase, with decoding hardened from silent fallbacks to proper errors.

Strategies

compute_delta(base, target) picks the smallest applicable encoding:

Opcode	Strategy	When
`0x03`	XOR + Zstd	Either input looks binary (zero byte in first 8 KiB) and the XOR stream compresses smaller (`zstd` feature)
`0x02`	Rabin rolling hash	Both inputs ≥ 4 KiB (fixed 4 KiB blocks indexed by Rabin hash, base 257 over Mersenne 2^61−1, verified by a strong 64-bit hash; target scanned with a rolling window emitting Copy/Insert opcodes)
`0x01`	Prefix/suffix trim	Small inputs; common prefix + suffix stored implicitly, changed middle kept
`0x00`	Full content	Fallback

apply_delta(base, delta) reconstructs the target.

For consumers that must preserve the origin suture-protocol contract (infallible apply_delta -> Vec<u8> with silent repair of malformed deltas), apply_delta_lenient provides exactly those legacy semantics. compute_binary_delta(base, target) exposes the 0x03 XOR+Zstd strategy directly (zstd feature).

Usage

let base = b"Hello, World!";
let target = b"Hello, Rust!";

let (_base_copy, delta) = delta_kit::compute_delta(base, target);
assert_eq!(
    delta_kit::apply_delta(base, &delta).expect("compute_delta output always applies"),
    target.to_vec()
);

compute_delta is total (cannot fail) and always produces a delta that apply_delta accepts. The returned first element is a copy of base, kept for drop-in compatibility with suture-protocol::compute_delta.

Wire format

All integers little-endian; first byte selects the encoding:

0x00 full content : [1..] target
0x01 prefix/suffix: [1..9) u64 prefix_len, [9..17) u64 suffix_len,
                    [17..25) u64 target_len, [25..] changed middle bytes
0x02 instructions : [1..9) u64 target_len, [9..13) u32 count,
                    records: 0x01 + u64 base_offset + u32 len  (Copy)
                             0x02 + u32 len + bytes            (Insert)
0x03 binary XOR   : [1..9) u64 target_len, [9..25) blake3(base)[..16],
                    [25..41) blake3(target)[..16], [41..] zstd(xor)

Hardened decoding (vs. origin)

The origin suture-protocol silently repaired malformed deltas: truncated headers decoded as identity, out-of-range copies were skipped, checksum failures returned an empty vector. This crate returns DeltaError for all of those (Truncated, InvalidOpcode, InvalidInstruction, CopyOutOfRange, InsertOutOfRange, TargetLengthMismatch, ChecksumMismatch). Well-formed deltas decode identically, and compatibility is verified byte-for-byte against the origin implementation across all four encodings; the lenient variant apply_delta_lenient is regression-tested against the origin's malformed-input behaviors.

Cargo features

Feature	Default	Effect
`zstd`	yes	Enables the `0x03` binary XOR+Zstd strategy. Without it, `0x03` deltas fail to decode (`ZstdDisabled`) and are never produced.

Benchmarks

benches/delta_bench.rs (criterion) trends the rolling-hash encode path on representative 64 KiB edits; benches/iai_delta.rs (iai-callgrind) is the deterministic instruction-count regression gate for the encode and apply hot loops (CI-only; requires valgrind).

Indicative numbers from a development machine (x86-64, idle):

Bench	Result
`delta_text_edit_64k` (1 KiB changed mid-file)	~390 µs
`delta_binary_edit_64k` (1 KiB changed, binary-ish base)	~114 µs
`delta_append_64k` (2 KiB appended)	~113 µs

The apply path's heap behavior is pinned by tests/alloc_bounds.rs: applying a delta allocates O(1) buffers bounded by the declared target_len, independent of the instruction count.

Every claim in this README is mapped to its proof artifact in CLAIMS.md.

cargo bench --bench delta_bench   # wall-clock trend
cargo bench --bench iai_delta --no-run  # compile the instruction gate anywhere

Testing

32 tests: unit (strategy coverage, hardened-decode errors), golden wire-format bytes, and property-based tests (arbitrary-bytes roundtrip, binary safety with forced zeros, universal size bound, similar-input bound, delta-of-delta composition).
tests/alloc_bounds.rs: counting-allocator proof that the apply path stays within O(1) buffer allocations regardless of instruction count.
benches/iai_delta.rs: iai-callgrind instruction-count gate for the encode/apply hot loops (CI-only; requires valgrind).
cargo check --no-default-features verified.
cargo clippy -D warnings and cargo fmt --check clean.

License

MIT OR Apache-2.0

delta-kit 0.2.1