bsdiff and bspatch are tools for building and applying patches
to binary files. By using suffix sorting (specifically, Larsson
and Sadakane's qsufsort) and taking advantage of how executable
files change, bsdiff routinely produces binary patches 50-80%
smaller than those produced by Xdelta, and 15% smaller than
those produced by .RTPatch (a $2750/seat commercial patch tool).
These programs were originally named bdiff and bpatch, but the
large number of other programs using those names lead to
confusion; I'm not sure if the "bs" in refers to "binary
software" (because bsdiff produces exceptionally small patches
for executable files) or "bytewise subtraction" (which is the
key to how well it performs). Feel free to offer other
suggestions. bsdiff is quite memory-hungry. It requires
max(17*n,9*n+m)+O(1) bytes of memory, where n is the size of the
old file and m is the size of the new file. bspatch requires
n+m+O(1) bytes. bsdiff runs in O((n+m) log n) time; on a 200MHz
Pentium Pro, building a binary patch for a