Hello everyone,

Here's an early form of some code for delta compression in git archives.  It 
builds on top of my packed item patch from before.  Using this patch will 
create repositories that can't be read by unpatched git, and it is only ready 
for light testing.  The file format might change slightly in later revs.

deltas live as subfiles in packed files, and the packed item header has the 
sha1 of the file the delta is against. deltas are never taken against deltas, 
only whole files (so the chain length is only 1).  

When importing all of Ingo's bk->cvs patches into git (28,000 changesets), 
delta git applies the patches faster (2hrs vs 2.5hrs), consumes less space 
(900MB vs 2.5GB), and checks out the resulting git tree faster in hot and 
cold caches.

Another 200MB or so would be saved by packing trees and commits into the same 
files as the blobs.  This is easy to do, but makes the patch harder to 
maintain because I need to move code around in commit-tree.c and 
write-tree.c.  So I've left those bits out for now.

Because the packed files are created per changeset, if a changeset only 
modifies one file the delta will still end up using a whole block.  So, you 
could get much higher space savings with a tool to walk back over existing 
changesets and pack them together.  This doesn't exist yet, but wouldn't be 
difficult, and I expect it to get close to the mercurial/bk repository sizes.

The patch uses zdelta for delta compression, which you can download here:
http://cis.poly.edu/zdelta/

I'm open to suggestions on better delta libs.  I picked this one because it 
was easy to code.  In order for things to work with git you need to apply the 
attached zdelta.diff to the zdelta-2.1 sources.  It fixes a silly default in 
the Makefile and a symbol collision with zlib.

-chris