EDelta uses a variant of the 'Linear Time, Constant Space Differencing Algorithm', described by Burns and Long, but extended to find systematic changes as they typically occur between different versions of executable binaries.
EDelta is a fast (linear time) XDelta-style binary differ, but optimized for executables that have a very systematic way of changing between versions. It has not been thoroughly evaluated so far, but on one example (two versions of Vim) it produces a 30kB delta where XDelta needs 250kB. My personal use for edelta is to quickly deploy Linux kernels from my development-laptop to my test-machines, especially when working over my slow ADSL line at home. I frequently see factor of 100 speedups compared to shipping the whole file.
New version: Version 0.9 which is much improved is released. Highlights include sha1 integrity checking, zlib compression of patches, support for reading and writing patches for stdin and to stdout, which eases integration with ssh for remote patching.
I know of at least two comparable projects, BSDiff and ExeDiff, though the latter is not platform-neutral. BSDiff may produce slightly better results than EDelta, but is extremely slow and uses much more memory. EDelta is fast enough that you can run it as part of a build script to always keep a remote copy in sync. See the enclosed epatch script for an example.
Though I have never gotten around to writing a proper paper about EDelta, this paper at the 2007 Data Compression Conference, by Giovanni Motta et.al., contains a good roundup of how EDelta 0.10 compares to competing algorithms.
New EDelta 0.10 released. This version adds the -le switch which provides better compression on Intel and other little-endian platforms, and also fixes a few bugs. edelta-0.10b.tar.gz.
Released 0.9d due to a bug in 0.9c that made patching fail. Please upgrade from 0.9c. The source code for edelta is here: edelta-0.9e.tar.gz. It should compile by just running 'make'. Version 0.9a has been made ANSI-C compatible to ease porting. Version 0.9b uses binary mode to open files, this might help with incorrent patching on Windows. Version 0.9c adds a -q switch and better args parsing.
A Windows-version maintained by Sauli Vainio is available from here (link works again).
The code is Copyright 2003-2006 Jacob Gorm Hansen, and licensed under the GNU GPL.