| 1 |
Binary diff/patch utility |
| 2 |
|
| 3 |
bsdiff and bspatch are tools for building and applying patches to |
| 4 |
binary files. By using suffix sorting (specifically, [1]Larsson and |
| 5 |
Sadakane's qsufsort) and taking advantage of how executable files |
| 6 |
change, bsdiff routinely produces binary patches 50-80% smaller than |
| 7 |
those produced by [2]Xdelta, and 15% smaller than those produced by |
| 8 |
[3].RTPatch (a $2750/seat commercial patch tool). |
| 9 |
|
| 10 |
These programs were originally named bdiff and bpatch, but the large |
| 11 |
number of other programs using those names lead to confusion; I'm not |
| 12 |
sure if the "bs" in refers to "binary software" (because bsdiff |
| 13 |
produces exceptionally small patches for executable files) or "bytewise |
| 14 |
subtraction" (which is the key to how well it performs). Feel free to |
| 15 |
offer other suggestions. |
| 16 |
|
| 17 |
bsdiff and bspatch use bzip2; by default they assume it is in /usr/bin. |
| 18 |
|
| 19 |
bsdiff is quite memory-hungry. It requires max(17*n,9*n+m)+O(1) bytes |
| 20 |
of memory, where n is the size of the old file and m is the size of the |
| 21 |
new file. bspatch requires n+m+O(1) bytes. |
| 22 |
|
| 23 |
bsdiff runs in O((n+m) log n) time; on a 200MHz Pentium Pro, building a |
| 24 |
binary patch for a 4MB file takes about 90 seconds. bspatch runs in |
| 25 |
O(n+m) time; on the same machine, applying that patch takes about two |
| 26 |
seconds. |
| 27 |
|
| 28 |
Providing that off_t is defined properly, bsdiff and bspatch support |
| 29 |
files of up to 2^61-1 = 2Ei-1 bytes. |
| 30 |
|
| 31 |
Version 4.3 is available [4]here with MD5 hash |
| 32 |
e6d812394f0e0ecc8d5df255aa1db22a. Version 4.2 is available in the |
| 33 |
FreeBSD, NetBSD, and OpenBSD ports trees as misc/bsdiff, in Darwinports |
| 34 |
as devel/bsdiff, and in gentoo as dev-util/bsdiff. It has also been |
| 35 |
made into a [5]Python extension module, and there is a [6]Windows port |
| 36 |
available. |
| 37 |
|
| 38 |
The algorithm used by BSDiff 4 is described in my (unpublished) paper |
| 39 |
[7]Naive differences of executable code; please cite this in papers as |
| 40 |
|
| 41 |
Colin Percival, Naive differences of executable code, |
| 42 |
http://www.daemonology.net/bsdiff/, 2003. |
| 43 |
|
| 44 |
A far more sophisticated algorithm, which typically provides roughly |
| 45 |
20% smaller patches, is described in my [8]doctoral thesis. |
| 46 |
|
| 47 |
References |
| 48 |
|
| 49 |
1. http://www.cs.lth.se/Research/Algorithms/Papers/jesper5.ps |
| 50 |
2. http://sourceforge.net/projects/xdelta/ |
| 51 |
3. http://www.pocketsoft.com/products.html |
| 52 |
4. http://www.daemonology.net/bsdiff/bsdiff-4.3.tar.gz |
| 53 |
5. http://starship.python.net/crew/atuining/cx_bsdiff/index.html |
| 54 |
6. http://sites.inka.de/tesla/f_others.html#bsdiff |
| 55 |
7. http://www.daemonology.net/papers/bsdiff.pdf |
| 56 |
8. http://www.daemonology.net/papers/thesis.pdf |