bsdiff #

BSDIFF40 binary diff and patch in pure OCaml.

Shipping new software over a slow or metered link, such as a satellite uplink or a device's cellular modem, costs far less as a patch against the version already installed than as a full binary. Compiled code is hard to diff, though: a small source change shifts addresses, so most bytes of the binary change by a small amount instead of staying identical.

BSDIFF40 is the patch format of Colin Percival's bsdiff and bspatch tools. A 32-byte header (the magic BSDIFF40, the compressed lengths of the first two streams and the target's size) is followed by three bzip2 streams: control triples, byte-wise difference data and extra data. Each control triple (x, y, z) tells bspatch to add the next x bytes of the difference stream, byte by byte, to x bytes of the source at the current source offset, then copy the next y bytes of the extra stream verbatim, then move the source offset by z, which may be negative. The matcher finds the source regions to add to with a suffix array over the source, built by qsufsort (Larsson and Sadakane, "Faster suffix sorting", 1999). For an n-byte source the construction takes O(n log n) time and holds two arrays of n + 1 OCaml integers, 16(n + 1) bytes on a 64-bit machine, so diffing a 10 MB binary needs about 160 MB beside the inputs. Each match lookup is a binary search over the array, O(m log n) for m matched bytes. The matcher aligns regions that differ by small per-byte deltas at stable offsets, the difference data is then mostly zeros and compresses well, and the format therefore suits executables. Patches produced here apply with the reference bspatch, and patches produced by the reference bsdiff apply here; the interop suite replays a committed reference patch, and bench/check_tools.ml checks both directions against the installed tools.

For text-like data where regions are either identical or replaced wholesale, the vcdiff package usually produces smaller patches.

Installation #

$ opam install bsdiff

If opam cannot find the package, it has probably not reached the public opam-repository yet. Add the overlay repository, then install it:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam update
$ opam install bsdiff

Usage #

# let source = "the quick brown fox jumps over the lazy dog" in
  let target = "the quick brown cat jumps over the lazy dog!" in
  let patch = Bsdiff.diff ~source ~target in
  Bsdiff.apply_exn ~source patch = target;;
- : bool = true

bsdiff #

Installation #

Usage #

Licence #