Re: Delitifier broken (Re: diff-core segfault)

On Mon, 12 Dec 2005, Linus Torvalds wrote:

On Mon, 12 Dec 2005, Linus Torvalds wrote:

quoted

   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