From: Nicolas Pitre <nico@cam.org>
Date: Tue, 13 Dec 2005 02:45:16 GMT
Subject: Re: Delitifier broken (Re: diff-core segfault)
Message-ID: <Pine.LNX.4.64.0512122114090.26663@localhost.localdomain>
In-Reply-To: <Pine.LNX.4.64.0512121758410.15597@g5.osdl.org>

On Mon, 12 Dec 2005, Linus Torvalds wrote:

> 
> 
> On Mon, 12 Dec 2005, Linus Torvalds wrote:
> > 
> >    As mentioned, pack-objects.c needs to check the size heuristics before 
> >    doing diff_delta() _anyway_, for performance reasons as well as simply 
> >    because the secondary use of diff_delta() is to estimate how big the 
> >    delta is, and it's always pointless to generate a delta that is 
> >    guaranteed to be bigger than the file (which is always the case with 
> >    either side being an empty file - the size difference will inevitably 
> >    be bigger than the size of the resulting file).
> 
> Side note: this isn't technically entirely true. A binary diff that has a 
> source file that is empty could in theory be smaller than the destination 
> file simply because it may involve a certain amount of automatic 
> compression in the form of "insert 100 spaces" kind of diff encoding. I'm 
> not sure whether xdelta actually does something like that, but it's 
> certainly possible at least in theory.

xdelta doesn't.  It only has two functions currently:

 1) copy x bytes from offset y in source file to current position in 
    destination file;

 2) paste the x following bytes straight from the delta stream to 
    current position into the destination file.

Of course in the GIT context files are buffers.

However I added the possibility for (1) to use the destination file as 
well as the "source" file for block copy in patch_delta().  However 
diff_delta() currently doesn't use that capability.  But if it did then 
the "insert 100 spaces" would be:

	- paste \x20\x20\x20\x20 to dest
	  (delta = 5 bytes, dest = 4 bytes)

	- copy 4 bytes from offset 0 of dest to dest
	  (delta = 7 bytes, dest = 8 bytes)

	- copy 8 bytes from offset 0 of dest to dest
	  (delta = 9 bytes, dest = 16 bytes)

	- copy 16 bytes from offset 0 of dest to dest
	  (delta = 11 bytes, dest = 32 bytes)

	- copy 32 bytes from offset 0 of dest to dest
	  (delta = 13 bytes, dest = 64 bytes)

	- copy 36 bytes from offset 0 of dest to dest
	  (delta = 15 bytes, dest = 100 bytes)

And yet that could be optimized further with a better size for the 
initial paste.  However adding that capability to diff_delta() might 
make it significantly slower for still unknown gain for real life data.  
But I should write the code some day.


Nicolas