bidiff

A binary diff and patch library for Rust, distantly derived from the bsdiff algorithm.

Instead of suffix arrays, bidiff uses a hash-table index with:

• File-backed mmap by default -- the kernel can page the hash table to disk under memory pressure, keeping anonymous memory usage low
• Optional --ram mode for faster diffs when memory is plentiful
• Parallel construction via lock-free CAS insertion
• Parallel scanning via rayon with ring-buffer channels for streaming matches
• Chunked patch format with independent zstd-compressed chunks for parallel patch application

Usage

# Create a patch
bidiff diff old_file new_file patch_file

# Apply a patch
bidiff patch old_file patch_file output_file

# Round-trip verification (diff then patch, verifies hash match)
bidiff cycle old_file new_file

Options

--scan-chunk-mb <N>   Scan chunk size in MB (default: 1)
--block-size <N>      Hash index block size, minimum 4 (default: 32)
--threads <N>         Max threads for parallel scanning (default: all cores)
--ram                 Keep hash table in RAM (faster, uses more memory)
--max                 Maximize compression (zstd level 22)

Benchmarks

System: AMD Ryzen Threadripper 2950X (32 cores), 60 GiB RAM, Linux 6.12.

Default settings (1 MiB chunks, file-backed hash table). Memory column shows peak anonymous RSS during diffing.

With --max (zstd level 22)

Smaller patches at the cost of much slower diff times. Patch application speed is similar.

System: Apple M2 Max (12 cores), 32 GiB RAM, macOS 26.1.

Default settings (1 MiB chunks, file-backed hash table). Memory column shows peak anonymous RSS during diffing.

Comparison with bidiff 1.1, bsdiff, and xdelta3

bidiff 1.1 (suffix arrays, single-threaded scan), bsdiff 4.3, xdelta3 3.0.11. Same test system.

Patch size

Diff time

Patch time

bsdiff and bidiff 1.1 produce the smallest patches (suffix array matching) but are orders of magnitude slower to diff — minutes vs bidiff's sub-second times. xdelta3 is faster than bsdiff but still 2–25x slower than bidiff and produces the largest patches. bidiff 2.0 trades slightly larger patches for dramatically faster diffing and patching thanks to parallel hash-table scanning and parallel zstd decompression.

Workspace structure

• bidiff (root) -- Library crate. Feature flags:
  • diff -- diffing engine (rayon, ringbuf, memmap2, tempfile)
  • patch -- patch encoding and application (integer-encoding, zstd)
  • Both enabled by default.
• bidiff-cli (cli/) -- CLI binary with diff, patch, and cycle subcommands.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.