Debian Codegraph @

debian/upstream.changelog

raw
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