From: Linus Torvalds Date: Tue, 23 Oct 2007 00:49:39 GMT Subject: Re: Linear time/space rename logic for *inexact* case Message-ID: In-Reply-To: <596909b30710221647y6a7481c5me41c31bbe1015e3a@mail.gmail.com> On Mon, 22 Oct 2007, Andy C wrote: > > 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