Re: diff'ing files ...

From: Jeff King <peff@peff.net>
Date: Jun 7, 2011, 22:19 UTC
Message-ID: <20110607221948.GA10104@sigill.intra.peff.net>
In-Reply-To: <BANLkTinwSembzVk4gSYSvsRdHhDfqizkyg@mail.gmail.com>

On Tue, Jun 07, 2011 at 10:12:35PM +0000, Albretch Mueller wrote:

Show 6 quoted lines

> > ... binary diffs, though I don't know offhand the details of the algorithm.
> ~
>  this is the part that I need ;-)
> ~
>  Reading the source code without knowing the basic underlying
> ideas/algorithm (just an outline if possible) won't help much

You could read the comments in the source:

  $ head -n 7 diff-delta.c
  /*
   * diff-delta.c: generate a delta between two buffers
   *
   * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
   * http://www.xmailserver.org/xdiff-lib.html
   *
   * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007

According to the xdiff page linked:

  For binary files, LibXDiff implements both (with some modification)
  the algorithm described in File System Support for Delta Compression
  by Joshua P.  MacDonald, and the algorithm described in Fingerprinting
  By Random Polynomials by Michael O. Rabin.

Nicolas (cc'd) might be able to say what, if any, substantive changes were made from those works.

-Peff