阅读中文版本

Build a Binary Diff Patcher

A binary diff tool that computes a compact patch between two byte sequences using a rolling hash and applies it to reconstruct the target without the source at apply time.

binary-diff-patcher/
├── src/diff.ts
├── src/apply.ts
├── src/rolling-hash.ts
├── tests/diff.test.ts
└── package.json

for (let i=0; i+BLK <= src.length; i+=BLK) index.set(hash(src,i), i);

if (index.has(h)) emitCopy(index.get(h), BLK); else literals.push(target[i]);

for (const op of patch) out.push(op.type==="copy" ? src.slice(op.off, op.off+op.len) : op.bytes);

patch.checksum = sha256(target.length + ":" + ops.length);

Project overview

A binary diff that ships the whole target is just a copy. The point of a diff is to send only what changed, and the point of this build is to find the shared blocks between a source and a target without reading the source at apply time.

The diff splits the source into fixed-size blocks and indexes each by a rolling hash. It then scans the target with the same hash; when the hash hits the index, it verifies the full block and emits a copy opcode referencing the source offset. Bytes that do not match any block accumulate into insert opcodes. The patch is a compact stream of copy and insert ops.

The rolling hash is what makes the scan cheap. A naive hash recomputed at every position costs O(block size) per step; a rolling hash updates in O(1) by adding the new byte and removing the old one, so scanning a megabyte of target with a 64-byte block takes a million hash updates, not sixty-four million.

The apply side replays the opcodes against the source to reconstruct the target. It does not need the diff, only the patch and the source. A footer checksum catches a truncated or tampered patch before it produces wrong output, because a binary patch applied to the wrong source is a silent corruption that is far worse than a loud failure.

The value of this project is the matching, not the format. A copy-and-insert opcode stream is trivial; finding the longest shared blocks with a rolling hash and verifying them before trusting a hash hit is the part worth learning, because a hash collision that emits a wrong copy is the bug that turns a small patch into a wrong file.

What you will build

The project delivers five capabilities, each driven by a test:

• Rolling-hash block matching
• Copy and insert opcodes
• Apply without source at apply time
• Patch integrity checksum
• Stream-friendly patch format

The diff splits the source into fixed-size blocks and indexes each block by a rolling hash. It scans the target with the same rolling hash; on a block match it emits a copy opcode referencing the source offset, and on a miss it accumulates literal bytes into an insert opcode. The patch is a sequence of copy and insert ops plus a target-length checksum.

Architecture and data model

The block index is a hash map from rolling-hash value to source offset. Because collisions are possible, the index stores the offset and the diff verifies the full block before emitting a copy. A collision that passes the hash but fails the block check is treated as a miss, and the scan continues.

The rolling hash is a polynomial hash with a base and a modulus, chosen so the update is a multiply, an add, and a subtract. The block size is a tunable: too large and a small change shifts every block and defeats matching; too small and the index is huge and the copy opcodes are short. Sixty-four bytes is a reasonable default for text-like data.

The opcode stream is a sequence of records. A copy opcode is a type byte, a source offset, and a length. An insert opcode is a type byte, a length, and the literal bytes. The patch footer stores the target length and a checksum over the opcode count, so the applier can detect a truncated patch before replaying it.

The apply side is deliberately simple: it walks the opcodes and pushes bytes into an output buffer. It checks the output length against the footer before returning, so a patch that produces the wrong length fails loudly. The checksum is a final guard, computed over the reconstructed output and compared to the footer.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• Familiarity with TypedArray and byte offsets

The dependencies cover the core needs:

• node:crypto (built-in) — Patch integrity checksum

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

binary-diff-patcher/ is organized so each concern is testable in isolation:

binary-diff-patcher/
├── src/diff.ts
├── src/apply.ts
├── src/rolling-hash.ts
├── tests/diff.test.ts
└── package.json

Phase 1: Block index

Split the source into blocks and index each by rolling hash to a source offset.

for (let i=0; i+BLK <= src.length; i+=BLK) index.set(hash(src,i), i);

Collisions are resolved by verifying the full block before emitting a copy.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Scan and emit

Scan the target with the same rolling hash; on match emit copy, on miss accumulate literal insert.

if (index.has(h)) emitCopy(index.get(h), BLK); else literals.push(target[i]);

Literals are flushed as an insert opcode when a copy begins or the scan ends.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Apply patch

Replay opcodes against the source to reconstruct the target, verifying the length checksum at the end.

for (const op of patch) out.push(op.type==="copy" ? src.slice(op.off, op.off+op.len) : op.bytes);

A checksum mismatch aborts apply with a clear error, not a silent corruption.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Integrity checksum

Hash the target length and the opcode stream into a patch footer checked at apply.

patch.checksum = sha256(target.length + ":" + ops.length);

A truncated or tampered patch fails the checksum before producing wrong output.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Diff a source and target that share a long common block and assert the patch is far smaller than the target; apply the patch to the source and assert the output equals the target byte for byte; diff two unrelated inputs and assert the patch degrades to a single insert.

The tests build a source and a target in memory, diff them, apply the patch, and assert the output equals the target byte for byte. The shared-block test constructs a target that copies a long run from the source with a small edit in the middle, and asserts the patch is far smaller than the target, proving the matcher found the shared blocks.

The unrelated-input test diffs two random buffers and asserts the patch degrades to a single insert opcode containing the whole target, because no blocks match. The shift test inserts one byte at the start of the target so every block shifts, and asserts the patch is still correct, even if it is not small.

The checksum test truncates the patch by one byte and asserts apply throws rather than returning wrong output. The collision test crafts two different blocks with the same rolling hash and asserts the diff verifies the full block and does not emit a wrong copy.

The round-trip test diffs a source against itself and asserts the patch is a single copy of the whole source, the smallest possible patch for an identical target.

pnpm vitest run

Observability

Track the rolling-hash block matching rate, the diff resource usage, and the error count as the three primary signals for the binary-diff-patcher system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the copy and insert opcodes alongside the rolling-hash block matching so a correlation is visible at a glance, because a rising copy and insert opcodes with a stable rolling-hash block matching means the system is doing more work per unit, not that it is failing.

Log every block index transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the diff identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the rolling-hash block matching error rate crossing a threshold, the diff utilization exceeding a percentage, and the copy and insert opcodes latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The binary-diff-patcher system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Ship the diff and apply as a library with no runtime dependencies. The patch format is self-describing: a header with the target length and block size, the opcode stream, and the footer checksum. An applier that knows the format can apply a patch produced by any diff version that shares the format.

Choose the block size from the change granularity, not a default. A patch for a file that changes in small scattered edits wants a small block; a patch for a file that changes in large contiguous runs wants a large block. The block size is a parameter of the diff call, not a constant.

The patch is stream-friendly: the opcode stream can be written and read sequentially, so a large patch does not need to be held in memory. The checksum is computed on the fly during write and verified during read.

Do not compress the patch inside this tool; let the transport compress it. A patch that is already compressed defeats a transport that would compress it better, and the checksum is over the uncompressed opcode stream.

Security considerations

Treat every input to the binary-diff-patcher system as untrusted, because the rolling-hash block matching path is the one place an external caller controls what the system processes. Validate the input shape before any diff operation, and reject early with a clear error rather than letting a malformed input propagate into the block index phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:crypto credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured binary-diff-patcher fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the rolling-hash block matching endpoint per caller, because an unbounded diff operation is a resource leak as much as a security problem. A caller that can trigger the scan and emit path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the block index logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The binary-diff-patcher system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the diff structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• Block size is fixed; a change that shifts every block by one byte defeats matching.
• No delta-of-delta; patching a patch is out of scope.
• The rolling hash is not cryptographic; patch integrity relies on the footer checksum.

The block size is fixed for one diff call. A change that shifts every block by one byte, such as inserting a byte at the start, defeats matching because no block aligns. A variable-block or content-defined chunking approach would handle this, but it is a different algorithm and out of scope.

There is no delta-of-delta. The patch is always against the original source, not against a previous patch. Chaining patches is possible by applying them in order, but the tool does not compose them.

The rolling hash is not cryptographic. A malicious source could craft blocks that collide under the rolling hash, but the full-block verification before emitting a copy means a collision produces a miss, not a wrong copy. The integrity guarantee against a tampered patch is the footer checksum, not the rolling hash.