Re: Linear time/space rename logic for *inexact* case
- From
Linus Torvalds <torvalds@linux-foundation.org>
- Date
- Oct 23, 2007, 00:49 UTC
- Message-ID
- <alpine.LFD.0.999.0710221745160.30120@woody.linux-foundation.org>
- In-Reply-To
- <596909b30710221647y6a7481c5me41c31bbe1015e3a@mail.gmail.com>
On Mon, 22 Oct 2007, Andy C wrote:
Show 15 quoted lines
> > from diffcore-delta.c: > " > * Idea here is very simple. > * > * Almost all data we are interested in are text, but sometimes we have > * to deal with binary data. So we cut them into chunks delimited by > * LF byte, or 64-byte sequence, whichever comes first, and hash them. > " > > What is the similarity metric for binary files? Is it related to the > number of 64 byte chunks they have in common? How do you know that > the 64 byte chunks match up? Suppose I have 10k file, and then I > insert 10 random bytes at positions, 1000, 2000, 3000, etc. How does > that work?
The 'LF' byte will start a new window, so even with binary files (assuming some random-enough distribution that you have *some* 'LF' bytes!), you basically get a synchronization event on each LF.
So the 64-byte hunks "line up" automatically, even for binary files. Maybe not immediately, but soon enough (ie on average, assuming some reasonably compressed - ie virtually random - binary format) you should find a LF roughly every fourth hunk.
There are probably smarter ways to guarantee it even in the absense of certain bit-patterns, but I bet the "break every 64 bytes or when you see a LF" thing works well for any reasonable binary file too.
But text files are obviously the most important case. Diffs on binaries are somewhat hit-and-miss regardless.
Linus