Re: RFC: New diff-delta.c implementation

[Nicolas Pitre <nico@cam.org>]

On Fri, 21 Apr 2006, Geert Bosch wrote:

> I wrote a new binary differencing algorithm that is both faster
> and generates smaller deltas than the current implementation.
> The format is compatible with that used by patch-delta, so
> it should be easy to integrate.

It looks really interesting.

It ignores the max_size argument but that is trivially fixed.

Then it triggers some assertions in the code when running the test 
suite.

> Originally, I wrote this for the GDIFF format, see
> http://www.w3.org/TR/NOTE-gdiff-19970901.
> The adaptation for GIT format was relatively simple, but is not thoroughly
> tested.

Some trivial tests look fine but it fail on some others.

> The code is not derived from libxdiff, but uses the rabin_slide function
> written
> by David Mazieres (dm@uun.org). Also the tables are generated using his code.
> Finally, this was developed on Darwin, and not a Linux system, so some changes
> may be needed.

It does compile out of the box on Linux.

> Please feel free to play around with this code, and give feedback.
> Keep in mind this wasn't originally written for GIT, and C is not
> my native language, so don't mind my formatting etc.

I did reformat it a bit to be more inline with the rest of GIT's coding 
style (and to help me read it).  I'll look at fixing the issues I can 
fix and post it back.


Nicolas