hashsplit: totally change the way the fanout stuff works.

hashsplit: totally change the way the fanout stuff works.

Useless code churn or genius innovation?  You decide.

The previous system for naming chunks of a split file was kind of lame.  We
tried to name the files something that was "almost" their offset, so that
filenames wouldn't shuffle around too much if a few bytes were added/deleted
here and there.  But that totally failed to work if a *lot* of bytes were
added, and it also lost the useful feature that you could seek to a specific
point in a file (like a VM image) without restoring the whole thing.
"Approximate" offsets aren't much good for seeking to.

The new system is even more crazy than the original hashsplit: we now use
the "extra bits" of the rolling checksum to define progressively larger
chunks.  For example, we might define a normal chunk if the checksum ends in
0xFFF (12 bits).  Now we can group multiple chunks together when the
checksum ends in 0xFFFF (16 bits).  Because of the way the checksum works,
this happens about every 2^4 = 16 chunks.  Similarly, 0xFFFFF (20 bits) will
happen 16 times less often than that, and so on.  We can use this effect to
define a tree.

Then, in each branch of the tree, we name files based on their (exact, not
approximate) offset *from the start of that tree*.

Essentially, inserting/deleting/changing bytes will affect more "levels" of
the rolling checksum, mangling bigger and bigger branches of the overall
tree and causing those branches to change.  However, only the content of
that sub-branch (and the *names*, ie offsets, of the following branches at
that and further-up levels) end up getting changed, so the effect can be
mostly localized.  The subtrees of those renamed trees are *not* affected,
because all their offsets are relative to the start of their own tree.  This
means *most* of the sha1sums in the resulting hierarchy don't need to
change, no matter how much data you add/insert/delete.

Anyway, the net result is that "git diff -M" now actually does something
halfway sensible when comparing the trees corresponding to huge split files.
Only halfway (because the chunk boundaries can move around a bit, and such
large files are usually binary anyway) but it opens the way for much cooler
algorithms in the future.

Also, it'll now be possible to make 'bup fuse' open files without restoring
the entire thing to a temp file first.  That means restoring (or even
*using*) snapshotted VMs ought to become possible.