[Gnu-arch-users] EDelta

[Jacob Gorm Hansen]

hi,

since the issue of binary diffing seems to come up on this list every
now and then, and because a lot of versioning-interested people hang out
here, I would like to announce that I have put my binary differ which is
 especially geared towards diffing of executables, up for download at

http://www.diku.dk/~jacobg/edelta/

The underlying algorithm is similar to what XDelta does, but in contrast
to generic binary differs it does not choke on the systematic reordering
that happens when code is inserted of deleted from an executable. The
LCS matcher allows matching substrings to have 'holes' (short
non-matching sequences) of up to 32 bits in size. Typically, many such
holes can be patched by adding a constant integer value, corresponding
to how much a block of code has moved due to insertions or deletions.
EDelta tries to be effecient, but running the output through gzip
afterwards, as does XDelta, is often a good idea, though this is not
currently in the code.

Like XDelta, EDelta runs in O(n) time, and by doing so fails to find
some reorderings, but generally does a good job, and is much faster than
other algorithms, such as the one used by BSDiff. I does not require any
knowledge of the particular instruction set, as does EXEDiff.

I imagine EDelta could be useful for distributing binary patches, for a
 build system which records all builds, or perhaps for nothing at all.

Best regards,
Jacob