{"thread":{"id":"453","subject":"RFC: adding xdelta compression to git","startedAt":"2005-05-03T03:57:38Z","lastAt":"2005-05-05T03:25:05Z","messageCount":32,"participants":["Alon Ziv","Nicolas Pitre","Linus Torvalds","Davide Libenzi","Chris Mason","Dan Holmsand","C. Scott Ananian","Geert Bosch"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"2440","messageId":"200505030657.38309.alonz@nolaviz.org","threadId":"453","inReplyTo":null,"subject":"RFC: adding xdelta compression to git","fromName":"Alon Ziv","fromEmail":"alonz@nolaviz.org","sentAt":"2005-05-03T03:57:38Z","receivedAt":"2005-05-03T03:57:38Z","isPatch":false,"sender":{"key":"alonz@nolaviz.org","avatar":null},"body":"Looking for novel methods of wasting my time :), I am considering adding \nxdelta to git.\n\nI have two concrete proposals, both of which (IMO) are consistent with the git \nphilosophy:\n\n1. Add a git-deltify command, which will take two trees and replace the second \ntree's blobs with delta-blobs referring to the first tree. Each delta-blob is \nself-contained; from the outside it looks like any other blob, but internally \nit contains another blob reference + an xdelta. The only function which would \nneed to understand the new format would be unpack_sha1_file.\nThe scripting level will be in charge of deciding which trees to deltify (or \nundeltify--we could also have a \"git-undeltify\" command). A sane \ndeltification schedule, for example, could be to always keep tagged versions \nas stand-alone objects, and deltify intermediate versions against the latest \ntag. It would also do its best to avoid delta chains (i.e. a delta referring \nto another delta).\nPros:\n* Interoperates with the existing structure (including pull/push) with almost \nno changes to existing infrastructure.\nCons:\n* Changes the repository format.\n* Some performance impact (probably quite small).\n* Same blob may have different representation in two repositories (one \ncompressed, on deltified). [I am not sure this is really a bad thing...]\n\n2. Add a completely external framework which manages a \"deltas repository\" of \ndeltas. The shadow repository will contain delta objects between selected \ntrees; again the scripts will need to populate it.\nPros:\n* No changes at all to existing code.\nCons:\n* Push/pull tools will need to be taught to talk with the new \"deltas \nrepository\".\n* Synchronization between the deltas repository and the real one may be lost, \nleading to odd failures.\n\nPersonally I'm rooting for #1 above... I would like to begin implementation in \na few days, so any discussion will be useful.\n\n\t-az\n"},{"id":"2442","messageId":"Pine.LNX.4.62.0505030008070.14033@localhost.localdomain","threadId":"453","inReplyTo":"200505030657.38309.alonz@nolaviz.org","subject":"Re: RFC: adding xdelta compression to git","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-03T04:12:23Z","receivedAt":"2005-05-03T04:12:23Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 May 2005, Alon Ziv wrote:\n\n> Looking for novel methods of wasting my time :), I am considering adding \n> xdelta to git.\n> \n> I have two concrete proposals, both of which (IMO) are consistent with the git \n> philosophy:\n> \n> 1. Add a git-deltify command, which will take two trees and replace the second \n> tree's blobs with delta-blobs referring to the first tree. Each delta-blob is \n> self-contained; from the outside it looks like any other blob, but internally \n> it contains another blob reference + an xdelta. The only function which would \n> need to understand the new format would be unpack_sha1_file.\n[....]\n\nGuess what?\n\nThat's exactly what I did, except that I used libxdiff, stripped it to \nthe bare minimum and even optimized it to be as efficient (i.e. fast) as \npossible given the git environment.\n\nI'm finalizing the code right now.\n\n\nNicolas\n"},{"id":"2451","messageId":"Pine.LNX.4.58.0505022131380.3594@ppc970.osdl.org","threadId":"453","inReplyTo":"200505030657.38309.alonz@nolaviz.org","subject":"Re: RFC: adding xdelta compression to git","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-03T04:52:42Z","receivedAt":"2005-05-03T04:52:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 May 2005, Alon Ziv wrote:\n> \n> 1. Add a git-deltify command, which will take two trees and replace the second \n> tree's blobs with delta-blobs referring to the first tree.\n\nIf you do something like this, you want such a delta-blob to be named by \nthe sha1 of the result, so that things that refer to it can transparently \nsee either the original blob _or_ the \"deltified\" one, and will never \ncare.\n\nIt seems that is your plan:\n\n> from the outside it looks like any other blob, but internally it\n> contains another blob reference + an xdelta.\n\nYes. git doesn't much care, as long as the objects unpack to the right \nformat. That's all hidden away.\n\n> The only function which would need to understand the new format would be\n> unpack_sha1_file.\n\nYes. EXCEPT for one thing. fsck. I'd _really_ like fsck to be able to know\nsomething about any xdelta objects, if only because if/when things go\nwrong, it's really nasty to suddenly see a million \"blob\" objects not work\nany more, with no indication of _why_ they don't work. The core reason may\nbe that one original object (that just got used as a base for tons of\nother objects through deltas) is corrupt or missing. And then you want to\nshow that _one_ object.\n\n> Cons:\n> * Changes the repository format.\n\nIt wouldn't necessarily. You should be able to do this with _zero_ changes \nto existing objects what-so-ever.\n\nWhat you do is introduce an \"xdelta\" object, which has a reference to a \nblob object and the delta. The git object model already names all objects \nby a simple ascii name, so adding a new object type in _no_ way changes \nany existing objects.\n\nSo you can just make \"unpack_sha1_file()\" notice that it unpacked a xdelta \nobject, and then do the proper delta application, and nobody will ever be \nthe wiser.\n\n> * Some performance impact (probably quite small).\n\nIf you limit the depth of deltas, probably not too bad.\n\n> * Same blob may have different representation in two repositories (one \n> compressed, on deltified). [I am not sure this is really a bad thing...]\n\nTHIS, I think, is the real issue. fsck-cache and pull etc, that needs to\nknow about references to other objects, would have to be able to see the\nxdelta object, so that they can build up the reference graph. So you'd\nneed to basically make a \"raw_unpack_sha1_file()\" interface (the current\nregular unpack_sha1_file()) for that.\n\nAlso, the fact is, since git saves things as separate files, you'd not win\nas much as you would with some other backing store. So the second step is\nto start packing the objects etc. I think there is actually a very steep\ncomplexity edge here - not because any of the individual steps necessarily\nadd a whole lot, but because they all lead to the \"next step\".\n\nI personally clearly feel that simplicity (and the resulting robustness)\nis worth a _lot_ of disk-space.\n\nSo I think that what you suggest is likely to actually be pretty easy, but \nI'm not entirely convinced it's worth the slide into complexity.\n\n\t\tLinus\n"},{"id":"2452","messageId":"Pine.LNX.4.58.0505022215110.21733@bigblue.dev.mdolabs.com","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505022131380.3594@ppc970.osdl.org","subject":"Re: RFC: adding xdelta compression to git","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2005-05-03T05:30:17Z","receivedAt":"2005-05-03T05:30:17Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Mon, 2 May 2005, Linus Torvalds wrote:\n\n> Yes. EXCEPT for one thing. fsck. I'd _really_ like fsck to be able to know\n> something about any xdelta objects, if only because if/when things go\n> wrong, it's really nasty to suddenly see a million \"blob\" objects not work\n> any more, with no indication of _why_ they don't work. The core reason may\n> be that one original object (that just got used as a base for tons of\n> other objects through deltas) is corrupt or missing. And then you want to\n> show that _one_ object.\n\nLinus, xdelta-based algorithms already stores informations regarding the \nobject that originated the diff. Since they have no context (like \ntext-based diffs) and are simply based on offset-driven copy/insert \noperations, this is a requirement. Libxdiff uses an adler32+size of the \noriginal object, but you can get as fancy as you like in your own \nimplementation. Before a delta patching, the stored information are cross \nchecked with the input base object, and the delta patch will fail in the \neventuality of mismatch. So an fsck is simply a walk backward (or forward, \ndepending on your metadata model) of the whole delta chain.\n\n\n\n- Davide\n\n"},{"id":"2456","messageId":"Pine.LNX.4.62.0505030344170.14033@localhost.localdomain","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505022131380.3594@ppc970.osdl.org","subject":"[PATCH] add the ability to create and retrieve delta objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-03T08:06:41Z","receivedAt":"2005-05-03T08:06:41Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 2 May 2005, Linus Torvalds wrote:\n\n> If you do something like this, you want such a delta-blob to be named by \n> the sha1 of the result, so that things that refer to it can transparently \n> see either the original blob _or_ the \"deltified\" one, and will never \n> care.\n\nYep, that's what I've done last weekend (and just made it actually \nwork since people are getting interested).\n\n==========\n\nThis patch adds the necessary functionalities to perform delta \ncompression on objects. It adds a git-mkdelta command which can replace \nany object with its deltafied version given a reference object.\n\nAccess to a delta object will transparently fetch the reference object \nand apply the transformation. Scripts can be used to perform any sort \nof compression policy on top of it.\n\nThe delta generator has been extracted from libxdiff and optimized for \ngit usage in order to avoid as much data copy as possible, and the delta \nstorage format modified to be even more compact. Therefore no need to \nrely on any external library. The test-delta program can be used to \ntest it.\n\nThe fsck tool doesn't know about delta object and its relation with \nother objects yet. But if one doesn't use git-mkdelta it should not be \na problem. Many refinements are possible but better merge them \nseparately. Loop detection and recursion limit are a few examples.\n\nSigned-off-by: Nicolas Pitre \n\n--- k/delta.h\n+++ l/delta.h\n@@ -0,0 +1,6 @@\n+extern void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t\tvoid *to_buf, unsigned long to_size,\n+\t\t unsigned long *delta_size);\n+extern void *patch_delta(void *src_buf, unsigned long src_size,\n+\t\t\t void *delta_buf, unsigned long delta_size,\n+\t\t\t unsigned long *dst_size);\n--- k/diff-delta.c\n+++ l/diff-delta.c\n@@ -0,0 +1,315 @@\n+/*\n+ * diff-delta.c: generate a delta between two buffers\n+ *\n+ * Many parts of this file have been lifted from LibXDiff version 0.10.\n+ * http://www.xmailserver.org/xdiff-lib.html\n+ *\n+ * LibXDiff was written by Davide Libenzi \n+ * Copyright (C) 2003\tDavide Libenzi\n+ *\n+ * Many mods for GIT usage by Nicolas Pitre , (C) 2005.\n+ *\n+ * This file is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ */\n+\n+#include \n+#include \"delta.h\"\n+\n+\n+/* block size: min = 16, max = 64k, power of 2 */\n+#define BLK_SIZE 16\n+\n+#define MIN(a, b) ((a) < (b) ? (a) : (b))\n+\n+#define GR_PRIME 0x9e370001\n+#define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))\n+\t\n+/* largest prime smaller than 65536 */\n+#define BASE 65521\n+\n+/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */\n+#define NMAX 5552\n+\n+#define DO1(buf, i) { s1 += buf[i]; s2 += s1; }\n+#define DO2(buf, i) DO1(buf, i); DO1(buf, i + 1);\n+#define DO4(buf, i) DO2(buf, i); DO2(buf, i + 2);\n+#define DO8(buf, i) DO4(buf, i); DO4(buf, i + 4);\n+#define DO16(buf) DO8(buf, 0); DO8(buf, 8);\n+\n+static unsigned int adler32(unsigned int adler, const unsigned char *buf, int len)\n+{\n+\tint k;\n+\tunsigned int s1 = adler & 0xffff;\n+\tunsigned int s2 = adler >> 16;\n+\n+\twhile (len > 0) {\n+\t\tk = MIN(len, NMAX);\n+\t\tlen -= k;\n+\t\twhile (k >= 16) {\n+\t\t\tDO16(buf);\n+\t\t\tbuf += 16;\n+\t\t\tk -= 16;\n+\t\t}\n+\t\tif (k != 0)\n+\t\t\tdo {\n+\t\t\t\ts1 += *buf++;\n+\t\t\t\ts2 += s1;\n+\t\t\t} while (--k);\n+\t\ts1 %= BASE;\n+\t\ts2 %= BASE;\n+\t}\n+\n+\treturn (s2 << 16) | s1;\n+}\n+\n+static unsigned int hashbits(unsigned int size)\n+{\n+\tunsigned int val = 1, bits = 0;\n+\twhile (val < size && bits < 32) {\n+\t\tval <<= 1;\n+\t \tbits++;\n+\t}\n+\treturn bits ? bits: 1;\n+}\n+\n+typedef struct s_chanode {\n+\tstruct s_chanode *next;\n+\tint icurr;\n+} chanode_t;\n+\n+typedef struct s_chastore {\n+\tchanode_t *head, *tail;\n+\tint isize, nsize;\n+\tchanode_t *ancur;\n+\tchanode_t *sncur;\n+\tint scurr;\n+} chastore_t;\n+\n+static void cha_init(chastore_t *cha, int isize, int icount)\n+{\n+\tcha->head = cha->tail = NULL;\n+\tcha->isize = isize;\n+\tcha->nsize = icount * isize;\n+\tcha->ancur = cha->sncur = NULL;\n+\tcha->scurr = 0;\n+}\n+\n+static void *cha_alloc(chastore_t *cha)\n+{\n+\tchanode_t *ancur;\n+\tvoid *data;\n+\n+\tancur = cha->ancur;\n+\tif (!ancur || ancur->icurr == cha->nsize) {\n+\t\tancur = malloc(sizeof(chanode_t) + cha->nsize);\n+\t\tif (!ancur)\n+\t\t\treturn NULL;\n+\t\tancur->icurr = 0;\n+\t\tancur->next = NULL;\n+\t\tif (cha->tail)\n+\t\t\tcha->tail->next = ancur;\n+\t\tif (!cha->head)\n+\t\t\tcha->head = ancur;\n+\t\tcha->tail = ancur;\n+\t\tcha->ancur = ancur;\n+\t}\n+\n+\tdata = (void *)ancur + sizeof(chanode_t) + ancur->icurr;\n+\tancur->icurr += cha->isize;\n+\treturn data;\n+}\n+\n+static void cha_free(chastore_t *cha)\n+{\n+\tchanode_t *cur = cha->head;\n+\twhile (cur) {\n+\t\tchanode_t *tmp = cur;\n+\t\tcur = cur->next;\n+\t\tfree(tmp);\n+\t}\n+}\n+\n+typedef struct s_bdrecord {\n+\tstruct s_bdrecord *next;\n+\tunsigned int fp;\n+\tconst unsigned char *ptr;\n+} bdrecord_t;\n+\n+typedef struct s_bdfile {\n+\tconst unsigned char *data, *top;\n+\tchastore_t cha;\n+\tunsigned int fphbits;\n+\tbdrecord_t **fphash;\n+} bdfile_t;\n+\n+static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)\n+{\n+\tunsigned int fphbits;\n+\tint i, hsize;\n+\tconst unsigned char *base, *data, *top;\n+\tbdrecord_t *brec;\n+\tbdrecord_t **fphash;\n+\n+\tfphbits = hashbits(bufsize / BLK_SIZE + 1);\n+\thsize = 1 << fphbits;\n+\tfphash = malloc(hsize * sizeof(bdrecord_t *));\n+\tif (!fphash)\n+\t\treturn -1;\n+\tfor (i = 0; i < hsize; i++)\n+\t\tfphash[i] = NULL;\n+\tcha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);\n+\n+\tbdf->data = data = base = buf;\n+\tbdf->top = top = buf + bufsize;\n+\tdata += (bufsize / BLK_SIZE) * BLK_SIZE;\n+\tif (data == top)\n+\t\tdata -= BLK_SIZE;\n+\n+\tfor ( ; data >= base; data -= BLK_SIZE) {\n+\t\tbrec = cha_alloc(&bdf->cha);\n+\t\tif (!brec) {\n+\t\t\tcha_free(&bdf->cha);\n+\t\t\tfree(fphash);\n+\t\t\treturn -1;\n+\t\t}\n+\t\tbrec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));\n+\t\tbrec->ptr = data;\n+\t\ti = HASH(brec->fp, fphbits);\n+\t\tbrec->next = fphash[i];\n+\t\tfphash[i] = brec;\n+\t}\n+\n+\tbdf->fphbits = fphbits;\n+\tbdf->fphash = fphash;\n+\n+\treturn 0;\n+}\n+\n+static void delta_cleanup(bdfile_t *bdf)\n+{\n+\tfree(bdf->fphash);\n+\tcha_free(&bdf->cha);\n+}\n+\n+#define COPYOP_SIZE(o, s) \\\n+ (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \\\n+ !!(s & 0xff) + !!(s & 0xff00) + 1)\n+\n+void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t void *to_buf, unsigned long to_size,\n+\t\t unsigned long *delta_size)\n+{\n+\tint i, outpos, outsize, inscnt, csize, msize, moff;\n+\tunsigned int fp;\n+\tconst unsigned char *data, *top, *ptr1, *ptr2;\n+\tunsigned char *out, *orig;\n+\tbdrecord_t *brec;\n+\tbdfile_t bdf;\n+\n+\tif (delta_prepare(from_buf, from_size, &bdf))\n+\t\treturn NULL;\n+\t\n+\toutpos = 0;\n+\toutsize = 4096;\n+\tout = malloc(outsize);\n+\tif (!out) {\n+\t\tdelta_cleanup(&bdf);\n+\t\treturn NULL;\n+\t}\n+\n+\tdata = to_buf;\n+\ttop = to_buf + to_size;\n+\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size;\n+\n+\tinscnt = 0;\n+\tmoff = 0;\n+\twhile (data < top) {\n+\t\tmsize = 0;\n+\t\tfp = adler32(0, data, MIN(top - data, BLK_SIZE));\n+\t\ti = HASH(fp, bdf.fphbits);\n+\t\tfor (brec = bdf.fphash[i]; brec; brec = brec->next) {\n+\t\t\tif (brec->fp == fp) {\n+\t\t\t\tcsize = bdf.top - brec->ptr;\n+\t\t\t\tif (csize > top - data)\n+\t\t\t\t\tcsize = top - data;\n+\t\t\t\tfor (ptr1 = brec->ptr, ptr2 = data; \n+\t\t\t\t csize && *ptr1 == *ptr2;\n+\t\t\t\t csize--, ptr1++, ptr2++);\n+\n+\t\t\t\tcsize = ptr1 - brec->ptr;\n+\t\t\t\tif (csize > msize) {\n+\t\t\t\t\tmoff = brec->ptr - bdf.data;\n+\t\t\t\t\tmsize = csize;\n+\t\t\t\t\tif (msize >= 0x10000) {\n+\t\t\t\t\t\tmsize = 0x10000;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!msize || msize < COPYOP_SIZE(moff, msize)) {\n+\t\t\tif (!inscnt)\n+\t\t\t\toutpos++;\n+\t\t\tout[outpos++] = *data++;\n+\t\t\tinscnt++;\n+\t\t\tif (inscnt == 0x7f) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tif (inscnt) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\n+\t\t\tdata += msize;\n+\t\t\torig = out + outpos++;\n+\t\t\ti = 0x80;\n+\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }\n+\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }\n+\t\t\tmsize >>= 8;\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }\n+\n+\t\t\t*orig = i;\n+\t\t}\n+\n+\t\t/* next time around the largest possible output is 1 + 4 + 3 */\n+\t\tif (outpos > outsize - 8) {\n+\t\t\tvoid *tmp = out;\n+\t\t\toutsize = outsize * 3 / 2;\n+\t\t\tout = realloc(out, outsize);\n+\t\t\tif (!out) {\n+\t\t\t\tfree(tmp);\n+\t\t\t\tdelta_cleanup(&bdf);\n+\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tif (inscnt)\n+\t\tout[-inscnt - 1] = inscnt;\n+\n+\tdelta_cleanup(&bdf);\n+\t*delta_size = outpos;\n+\treturn out;\n+}\n--- k/mkdelta.c\n+++ l/mkdelta.c\n@@ -0,0 +1,95 @@\n+#include \"cache.h\"\n+#include \"delta.h\"\n+\n+static int write_delta_file(char *buf, unsigned long len, unsigned char *sha1_ref, unsigned char *path)\n+{\n+\tint size;\n+\tchar *compressed;\n+\tz_stream stream;\n+\tchar hdr[50];\n+\tint fd, hdrlen;\n+\n+\t/* Generate the header */\n+\thdrlen = sprintf(hdr, \"delta %lu\", len+20)+1;\n+\tmemcpy(hdr + hdrlen, sha1_ref, 20);\n+\thdrlen += 20;\n+\n+\tfd = open(path, O_WRONLY | O_CREAT | O_EXCL, 0666);\n+\tif (fd < 0)\n+\t\treturn -1;\n+\n+\t/* Set it up */\n+\tmemset(&stream, 0, sizeof(stream));\n+\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n+\tsize = deflateBound(&stream, len+hdrlen);\n+\tcompressed = xmalloc(size);\n+\n+\t/* Compress it */\n+\tstream.next_out = compressed;\n+\tstream.avail_out = size;\n+\n+\t/* First header.. */\n+\tstream.next_in = hdr;\n+\tstream.avail_in = hdrlen;\n+\twhile (deflate(&stream, 0) == Z_OK)\n+\t\t/* nothing */\n+\n+\t/* Then the data itself.. */\n+\tstream.next_in = buf;\n+\tstream.avail_in = len;\n+\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t/* nothing */;\n+\tdeflateEnd(&stream);\n+\tsize = stream.total_out;\n+\n+\tif (write(fd, compressed, size) != size)\n+\t\tdie(\"unable to write file\");\n+\tclose(fd);\n+\t\t\n+\treturn 0;\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tunsigned char sha1_ref[20], sha1_trg[20];\n+\tchar type_ref[20], type_trg[20];\n+\tvoid *buf_ref, *buf_trg, *buf_delta;\n+\tunsigned long size_ref, size_trg, size_delta;\n+\tchar *filename, tmpname[100];\n+\n+\tif (argc != 3 || get_sha1(argv[1], sha1_ref) || get_sha1(argv[2], sha1_trg))\n+\t\tusage(\"git-mkdelta \");\n+\n+\tbuf_ref = read_sha1_file(sha1_ref, type_ref, &size_ref);\n+\tif (!buf_ref) {\n+\t\tfprintf(stderr, \"%s: unable to read reference object\\n\", argv[0]);\n+\t\texit(1);\n+\t}\n+\tbuf_trg = read_sha1_file(sha1_trg, type_trg, &size_trg);\n+\tif (!buf_trg) {\n+\t\tfprintf(stderr, \"%s: unable to read target object\\n\", argv[0]);\n+\t\texit(1);\n+\t}\n+\tif (strcmp(type_ref, type_trg)) {\n+\t\tfprintf(stderr, \"%s: reference and target are of different type\\n\", argv[0]);\n+\t\texit(2);\n+\t}\n+\tbuf_delta = diff_delta(buf_ref, size_ref, buf_trg, size_trg, &size_delta);\n+\tif (!buf_delta) {\n+\t\tfprintf(stderr, \"%s: unable to create delta\\n\", argv[0]);\n+\t\texit(3);\n+\t}\n+\n+\tfilename = sha1_file_name(sha1_trg);\n+\tsprintf(tmpname, \"%s.delta.tmp\", filename);\n+\tif (write_delta_file(buf_delta, size_delta, sha1_ref, tmpname)) {\n+\t\tperror(tmpname);\n+\t\texit(1);\n+\t}\n+\tif (rename(tmpname, filename)) {\n+\t\tperror(\"rename\");\n+\t\texit(1);\n+\t}\n+\n+\treturn 0;\n+}\n--- k/patch-delta.c\n+++ l/patch-delta.c\n@@ -0,0 +1,73 @@\n+/*\n+ * patch-delta.c:\n+ * recreate a buffer from a source and the delta produced by diff-delta.c\n+ *\n+ * (C) 2005 Nicolas Pitre \n+ *\n+ * This code is free software; you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License version 2 as\n+ * published by the Free Software Foundation.\n+ */\n+\n+#include \n+#include \n+#include \"delta.h\"\n+\n+void *patch_delta(void *src_buf, unsigned long src_size,\n+\t\t void *delta_buf, unsigned long delta_size,\n+\t\t unsigned long *dst_size)\n+{\n+\tconst unsigned char *data, *top;\n+\tunsigned char *dst, *out;\n+\tint size;\n+\n+\t/* the smallest delta size possible is 10 bytes */\n+\tif (delta_size < 10)\n+\t\treturn NULL;\n+\n+\tdata = delta_buf;\n+\ttop = delta_buf + delta_size;\n+\n+\t/* make sure the orig file size matches what we expect */\n+\tsize = data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);\n+\tdata += 4;\n+\tif (size != src_size)\n+\t\treturn NULL;\n+\n+\t/* now the result size */\n+\tsize = data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);\n+\tdata += 4;\n+\tdst = malloc(size);\n+\tif (!dst)\n+\t\treturn NULL;\n+\n+\tout = dst;\n+\twhile (data < top) {\n+\t\tunsigned char cmd = *data++;\n+\t\tif (cmd & 0x80) {\n+\t\t\tunsigned int cp_off = 0, cp_size = 0;\n+\t\t\tif (cmd & 0x01) cp_off = *data++;\n+\t\t\tif (cmd & 0x02) cp_off |= (*data++ << 8);\n+\t\t\tif (cmd & 0x04) cp_off |= (*data++ << 16);\n+\t\t\tif (cmd & 0x08) cp_off |= (*data++ << 24);\n+\t\t\tif (cmd & 0x10) cp_size = *data++;\n+\t\t\tif (cmd & 0x20) cp_size |= (*data++ << 8);\n+\t\t\tif (cp_size == 0) cp_size = 0x10000;\n+\t\t\tmemcpy(out, src_buf + cp_off, cp_size);\n+\t\t\tout += cp_size;\n+\t\t} else {\n+\t\t\tmemcpy(out, data, cmd);\n+\t\t\tout += cmd;\n+\t\t\tdata += cmd;\n+\t\t}\n+\t}\n+\n+\t/* sanity check */\n+\tif (data != top || out - dst != size) {\n+\t\tfree(dst);\n+\t\treturn NULL;\n+\t}\n+\n+\t*dst_size = size;\n+\treturn dst;\n+}\nBinary files k/test-delta and l/test-delta differ\n--- k/test-delta.c\n+++ l/test-delta.c\n@@ -0,0 +1,79 @@\n+/*\n+ * test-delta.c: test code to exercise diff-delta.c and patch-delta.c\n+ *\n+ * (C) 2005 Nicolas Pitre \n+ *\n+ * This code is free software; you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License version 2 as\n+ * published by the Free Software Foundation.\n+ */\n+\n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \"delta.h\"\n+\n+static const char *usage =\n+\t\"test-delta (-d|-p) \";\n+\n+int main(int argc, char *argv[])\n+{\n+\tint fd;\n+\tstruct stat st;\n+\tvoid *from_buf, *data_buf, *out_buf;\n+\tunsigned long from_size, data_size, out_size;\n+\n+\tif (argc != 5 || (strcmp(argv[1], \"-d\") && strcmp(argv[1], \"-p\"))) {\n+\t\tfprintf(stderr, \"Usage: %s\\n\", usage);\n+\t\treturn 1;\n+\t}\n+\n+\tfd = open(argv[2], O_RDONLY);\n+\tif (fd < 0 || fstat(fd, &st)) {\n+\t\tperror(argv[2]);\n+\t\treturn 1;\n+\t}\n+\tfrom_size = st.st_size;\n+\tfrom_buf = mmap(NULL, from_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (from_buf == MAP_FAILED) {\n+\t\tperror(argv[2]);\n+\t\treturn 1;\n+\t}\n+\tclose(fd);\n+\n+\tfd = open(argv[3], O_RDONLY);\n+\tif (fd < 0 || fstat(fd, &st)) {\n+\t\tperror(argv[3]);\n+\t\treturn 1;\n+\t}\n+\tdata_size = st.st_size;\n+\tdata_buf = mmap(NULL, data_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (data_buf == MAP_FAILED) {\n+\t\tperror(argv[3]);\n+\t\treturn 1;\n+\t}\n+\tclose(fd);\n+\n+\tif (argv[1][1] == 'd')\n+\t\tout_buf = diff_delta(from_buf, from_size,\n+\t\t\t\t data_buf, data_size, &out_size);\n+\telse\n+\t\tout_buf = patch_delta(from_buf, from_size,\n+\t\t\t\t data_buf, data_size, &out_size);\n+\tif (!out_buf) {\n+\t\tfprintf(stderr, \"delta operation failed (returned NULL)\\n\");\n+\t\treturn 1;\n+\t}\n+\n+\tfd = open (argv[4], O_WRONLY|O_CREAT|O_TRUNC, 0666);\n+\tif (fd < 0 || write(fd, out_buf, out_size) != out_size) {\n+\t\tperror(argv[4]);\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n--- k/Makefile\n+++ l/Makefile\n@@ -21,7 +21,7 @@ PROG= git-update-cache git-diff-files \n \tgit-check-files git-ls-tree git-merge-base git-merge-cache \\\n \tgit-unpack-file git-export git-diff-cache git-convert-cache \\\n \tgit-http-pull git-rpush git-rpull git-rev-list git-mktag \\\n-\tgit-diff-tree-helper git-tar-tree git-local-pull\n+\tgit-diff-tree-helper git-tar-tree git-local-pull git-mkdelta\n \n all: $(PROG)\n \n@@ -29,7 +29,7 @@ install: $(PROG) $(SCRIPTS)\n \tinstall $(PROG) $(SCRIPTS) $(HOME)/bin/\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \\\n-\t tag.o date.o\n+\t tag.o date.o diff-delta.o patch-delta.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h blob.h tree.h commit.h tag.h\n \n@@ -63,6 +63,9 @@ $(LIB_FILE): $(LIB_OBJS)\n test-date: test-date.c date.o\n \t$(CC) $(CFLAGS) -o $@ test-date.c date.o\n \n+test-delta: test-delta.c diff-delta.o patch-delta.o\n+\t$(CC) $(CFLAGS) -o $@ $^\n+\n git-%: %.c $(LIB_FILE)\n \t$(CC) $(CFLAGS) -o $@ $(filter %.c,$^) $(LIBS)\n \n@@ -92,6 +95,7 @@ git-rpush: rsh.c\n git-rpull: rsh.c pull.c\n git-rev-list: rev-list.c\n git-mktag: mktag.c\n+git-mkdelta: mkdelta.c\n git-diff-tree-helper: diff-tree-helper.c\n git-tar-tree: tar-tree.c\n \n--- k/sha1_file.c\n+++ l/sha1_file.c\n@@ -8,6 +8,7 @@\n */\n #include \n #include \"cache.h\"\n+#include \"delta.h\"\n \n const char *sha1_file_directory = NULL;\n \n@@ -186,7 +187,8 @@ void * unpack_sha1_file(void *map, unsig\n \tint ret, bytes;\n \tz_stream stream;\n \tchar buffer[8192];\n-\tchar *buf;\n+\tchar *buf, *delta_ref;\n+\tunsigned long delta_ref_sz;\n \n \t/* Get the data stream */\n \tmemset(&stream, 0, sizeof(stream));\n@@ -201,8 +203,15 @@ void * unpack_sha1_file(void *map, unsig\n \t\treturn NULL;\n \tif (sscanf(buffer, \"%10s %lu\", type, size) != 2)\n \t\treturn NULL;\n-\n \tbytes = strlen(buffer) + 1;\n+\n+\tif (!strcmp(type, \"delta\")) {\n+\t\tdelta_ref = read_sha1_file(buffer + bytes, type, &delta_ref_sz);\n+\t\tif (!delta_ref)\n+\t\t\treturn NULL;\n+\t} else\n+\t\tdelta_ref = NULL;\n+\n \tbuf = xmalloc(*size);\n \n \tmemcpy(buf, buffer + bytes, stream.total_out - bytes);\n@@ -214,6 +223,17 @@ void * unpack_sha1_file(void *map, unsig\n \t\t\t/* nothing */;\n \t}\n \tinflateEnd(&stream);\n+\n+\tif (delta_ref) {\n+\t\tchar *newbuf;\n+\t\tunsigned long newsize;\n+\t\tnewbuf = patch_delta(delta_ref, delta_ref_sz, buf+20, *size-20, &newsize);\n+\t\tfree(delta_ref);\n+\t\tfree(buf);\n+\t\tbuf = newbuf;\n+\t\t*size = newsize;\n+\t}\n+\n \treturn buf;\n }\n \n"},{"id":"2463","messageId":"200505030724.57827.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.62.0505030344170.14033@localhost.localdomain","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-03T11:24:56Z","receivedAt":"2005-05-03T11:24:56Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 03 May 2005 04:06, Nicolas Pitre wrote:\n> On Mon, 2 May 2005, Linus Torvalds wrote:\n> > If you do something like this, you want such a delta-blob to be named by\n> > the sha1 of the result, so that things that refer to it can transparently\n> > see either the original blob _or_ the \"deltified\" one, and will never\n> > care.\n>\n> Yep, that's what I've done last weekend (and just made it actually\n> work since people are getting interested).\n>\nThis looks much nicer than using zdelta, I'll try switching my packed item to \nyour delta generator later this week. Some quick and dirty space numbers to \nshow why we need to pack the files together:\n\nOn the full import of all the bk->cvs changesets, the average file size \nin .git is 4074 bytes. 73% of the files are 4096 bytes or smaller.\n\nThis means that of the 2.5GB the .git directory consumes, about 1GB is taken \nup by files under 4k where deltas won't save space. If the remaining files \ncould be delta compressed down to less than 4k, they would still take up \naround 400MB on disk.\n\n-chris\n\n"},{"id":"2466","messageId":"d57rip$ojm$1@sea.gmane.org","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505022131380.3594@ppc970.osdl.org","subject":"Re: RFC: adding xdelta compression to git","fromName":"Dan Holmsand","fromEmail":"holmsand@gmail.com","sentAt":"2005-05-03T12:48:14Z","receivedAt":"2005-05-03T12:48:14Z","isPatch":false,"sender":{"key":"holmsand@gmail.com","avatar":"https://gravatar.com/avatar/5c722084bafd85e754a02efad01fe69107eb6f393253c49232c5c9f7faa974df?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> Also, the fact is, since git saves things as separate files, you'd not win\n> as much as you would with some other backing store. So the second step is\n> to start packing the objects etc. I think there is actually a very steep\n> complexity edge here - not because any of the individual steps necessarily\n> add a whole lot, but because they all lead to the \"next step\".\n\nActually, you can win quite a lot.\n\nI've just been playing with storing the entire \nlinux-2.4.0-to-2.6.12-rc2-patchset as xdelta patches in git. The entire \nthing ended up being 577M (instead of some 3.5G), according to du -sh \n--apparent-size. Considering that that's some 800M of patches, that's \nnot too bad.\n\nI used a very simple scheme: I stored a delta to the previous version of \nevery file if that delta was less than 20% in size of the new file \n(otherwise, the whole file was stored as usual). If the previous version \nwas already in delta form, the delta was computed from that versions \n\"parent\". I didn't even care to look at files less than 4k in size.\n\nIn other words, I didn't have to use any delta \"chains\", and still got \nquite massive storage size gains. And this scheme could easily be used \non the fly; I'm guessing that it would be performance neutral (or even a \nslight gain, since less has to be compressed and written to disk on \ncommits, and there might be less to read when diffing, since two \n\"delta-blobs\" might share the same parent).\n\nOr, with careful tuning, a repo might be \"deltaified\" later on (assuming \nthat delta blobs are addressed using the expanded files' hash).\n\n/dan\n\n"},{"id":"2467","messageId":"Pine.LNX.4.62.0505030847140.14033@localhost.localdomain","threadId":"453","inReplyTo":"200505030724.57827.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-03T12:51:03Z","receivedAt":"2005-05-03T12:51:03Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 May 2005, Chris Mason wrote:\n\n> This looks much nicer than using zdelta, I'll try switching my packed item to \n> your delta generator later this week. Some quick and dirty space numbers to \n> show why we need to pack the files together:\n> \n> On the full import of all the bk->cvs changesets, the average file size \n> in .git is 4074 bytes. 73% of the files are 4096 bytes or smaller.\n> \n> This means that of the 2.5GB the .git directory consumes, about 1GB is taken \n> up by files under 4k where deltas won't save space. If the remaining files \n> could be delta compressed down to less than 4k, they would still take up \n> around 400MB on disk.\n\nSure. However it helps for history backups and network transfer.\n\nHowever if the delta compression and packed storage can remain as \ndecoupled as possible from each other this is good for flexibility.\n\n\nNicolas\n"},{"id":"2468","messageId":"200505031013.57476.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.62.0505030344170.14033@localhost.localdomain","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-03T14:13:56Z","receivedAt":"2005-05-03T14:13:56Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 03 May 2005 04:06, Nicolas Pitre wrote:\n> On Mon, 2 May 2005, Linus Torvalds wrote:\n> > If you do something like this, you want such a delta-blob to be named by\n> > the sha1 of the result, so that things that refer to it can transparently\n> > see either the original blob _or_ the \"deltified\" one, and will never\n> > care.\n>\n> Yep, that's what I've done last weekend (and just made it actually\n> work since people are getting interested).\n\nHmmm, something is strange here, am I using this wrong?\n\ncoffee:~/git/linus.orig # ./test-delta -d foo foo2 delta1\ncoffee:~/git/linus.orig # ./test-delta -p foo delta1 out\n*** glibc detected *** free(): invalid next size (fast): 0x0804b008 ***\nAborted\n\nValgrind output:\n\n==9634== Invalid read of size 1\n==9634== at 0x1B9036F0: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1B90906F is not stack'd, malloc'd or (recently) free'd\n==9634==\n==9634== Invalid write of size 1\n==9634== at 0x1B9036F3: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1BA3A08D is not stack'd, malloc'd or (recently) free'd\n==9634==\n==9634== Invalid read of size 1\n==9634== at 0x1B9036F6: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1B90906E is not stack'd, malloc'd or (recently) free'd\n==9634==\n==9634== Invalid write of size 1\n==9634== at 0x1B9036F9: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1BA3A08C is not stack'd, malloc'd or (recently) free'd\n==9634==\n==9634== Invalid read of size 1\n==9634== at 0x1B9036FC: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1B90906D is not stack'd, malloc'd or (recently) free'd\n==9634==\n==9634== Invalid write of size 1\n==9634== at 0x1B9036FF: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1BA3A08B is not stack'd, malloc'd or (recently) free'd\n==9634==\n==9634== Invalid read of size 1\n==9634== at 0x1B903702: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1B90906C is not stack'd, malloc'd or (recently) free'd\n==9634==\n==9634== Invalid write of size 1\n==9634== at 0x1B903708: memcpy (in /usr/lib/valgrind/vgpreload_memcheck.so)\n==9634== by 0x8049142: patch_delta (patch-delta.c:59)\n==9634== by 0x80487CB: main (test-delta.c:65)\n==9634== Address 0x1BA3A08A is not stack'd, malloc'd or (recently) free'd\ndelta operation failed (returned NULL)\n==9634==\n==9634== ERROR SUMMARY: 206 errors from 13 contexts (suppressed: 0 from 0)\n==9634== malloc/free: in use at exit: 0 bytes in 0 blocks.\n==9634== malloc/free: 1 allocs, 1 frees, 5 bytes allocated.\n==9634== For a detailed leak analysis, rerun with: --leak-check=yes\n==9634== For counts of detected errors, rerun with: -v\n\n-chris\n"},{"id":"2469","messageId":"Pine.LNX.4.62.0505031022340.14033@localhost.localdomain","threadId":"453","inReplyTo":"200505031013.57476.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-03T14:24:26Z","receivedAt":"2005-05-03T14:24:26Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 May 2005, Chris Mason wrote:\n\n> On Tuesday 03 May 2005 04:06, Nicolas Pitre wrote:\n> > On Mon, 2 May 2005, Linus Torvalds wrote:\n> > > If you do something like this, you want such a delta-blob to be named by\n> > > the sha1 of the result, so that things that refer to it can transparently\n> > > see either the original blob _or_ the \"deltified\" one, and will never\n> > > care.\n> >\n> > Yep, that's what I've done last weekend (and just made it actually\n> > work since people are getting interested).\n> \n> Hmmm, something is strange here, am I using this wrong?\n> \n> coffee:~/git/linus.orig # ./test-delta -d foo foo2 delta1\n> coffee:~/git/linus.orig # ./test-delta -p foo delta1 out\n> *** glibc detected *** free(): invalid next size (fast): 0x0804b008 ***\n> Aborted\n\nCan you send me your foo and delta2 files?\n\n\nNicolas\n"},{"id":"2470","messageId":"200505031037.38005.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.62.0505031022340.14033@localhost.localdomain","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-03T14:37:37Z","receivedAt":"2005-05-03T14:37:37Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 03 May 2005 10:24, Nicolas Pitre wrote:\n> On Tue, 3 May 2005, Chris Mason wrote:\n> > Hmmm, something is strange here, am I using this wrong?\n> >\n> > coffee:~/git/linus.orig # ./test-delta -d foo foo2 delta1\n> > coffee:~/git/linus.orig # ./test-delta -p foo delta1 out\n> > *** glibc detected *** free(): invalid next size (fast): 0x0804b008 ***\n> > Aborted\n>\n> Can you send me your foo and delta2 files?\n>\nSorry, thought I had the whole command history in there. I went for something \nsmall to start ;)\n\ncoffee:~/git/linus.orig # echo foo > foo\ncoffee:~/git/linus.orig # echo foo2 > foo2\ncoffee:~/git/linus.orig # ./test-delta -d foo foo2 delta1\ncoffee:~/git/linus.orig # ls -la delta1\n-rw-r--r-- 1 root root 14 2005-05-03 10:36 delta1\ncoffee:~/git/linus.orig # ./test-delta -p foo delta1 out\n*** glibc detected *** free(): invalid next size (fast): 0x0804b008 ***\n\n-chris\n"},{"id":"2471","messageId":"Pine.LNX.4.58.0505030742330.3594@ppc970.osdl.org","threadId":"453","inReplyTo":"Pine.LNX.4.62.0505030344170.14033@localhost.localdomain","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-03T14:48:28Z","receivedAt":"2005-05-03T14:48:28Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 May 2005, Nicolas Pitre wrote:\n> \n> Yep, that's what I've done last weekend (and just made it actually \n> work since people are getting interested).\n\nI have to say that it looks uncommonly simple. Also, afaik, this should\nstill work with the current fsck, it's just that because fsck doesn't\nunderstand the linkages, the error reporting won't be as good as it could\nbe (I'd _much_ rather see \"delta failed in object xxxxx\" than \"unable to\nread xxxxxx\").\n\nNow, one thing I like about this approach is that the actual delta \n_generation_ can be done off-line, and independently of anything else. \nWhich means that the performance paths I care about (commit etc) are \nlargely unaffected, and you can \"deltify\" a git archive overnight or \nsomething. \n\nIn fact, it means that you might even be able to use some fairly expensive \n\"search for the best blob object to delta against\", including very much a \nintelligent rename search (ie \"oh, this is a new object, let's see if any \nof the old deleted objects generate a good delta\"), but you might even go \nback more than one generation.\n\nHmm. How nasty are those scripts?\n\n\t\tLinus\n"},{"id":"2473","messageId":"Pine.LNX.4.62.0505031104080.14033@localhost.localdomain","threadId":"453","inReplyTo":"200505031037.38005.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-03T15:04:51Z","receivedAt":"2005-05-03T15:04:51Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 May 2005, Chris Mason wrote:\n\n> On Tuesday 03 May 2005 10:24, Nicolas Pitre wrote:\n> > On Tue, 3 May 2005, Chris Mason wrote:\n> > > Hmmm, something is strange here, am I using this wrong?\n> > >\n> > > coffee:~/git/linus.orig # ./test-delta -d foo foo2 delta1\n> > > coffee:~/git/linus.orig # ./test-delta -p foo delta1 out\n> > > *** glibc detected *** free(): invalid next size (fast): 0x0804b008 ***\n> > > Aborted\n> >\n> > Can you send me your foo and delta2 files?\n> >\n> Sorry, thought I had the whole command history in there. I went for something \n> small to start ;)\n> \n> coffee:~/git/linus.orig # echo foo > foo\n> coffee:~/git/linus.orig # echo foo2 > foo2\n> coffee:~/git/linus.orig # ./test-delta -d foo foo2 delta1\n> coffee:~/git/linus.orig # ls -la delta1\n> -rw-r--r-- 1 root root 14 2005-05-03 10:36 delta1\n> coffee:~/git/linus.orig # ./test-delta -p foo delta1 out\n> *** glibc detected *** free(): invalid next size (fast): 0x0804b008 ***\n\nOK, doh!\n\n--- diff-delta.c.orig\t2005-05-03 11:00:39.900529634 -0400\n+++ diff-delta.c\t2005-05-03 11:01:03.210031176 -0400\n@@ -307,7 +307,7 @@\n \t}\n \n \tif (inscnt)\n-\t\tout[-inscnt - 1] = inscnt;\n+\t\tout[outpos - inscnt - 1] = inscnt;\n \n \tdelta_cleanup(&bdf);\n \t*delta_size = outpos;\n"},{"id":"2474","messageId":"Pine.LNX.4.58.0505030804170.3594@ppc970.osdl.org","threadId":"453","inReplyTo":"200505030724.57827.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-03T15:07:44Z","receivedAt":"2005-05-03T15:07:44Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 May 2005, Chris Mason wrote:\n> \n> On the full import of all the bk->cvs changesets, the average file size \n> in .git is 4074 bytes. 73% of the files are 4096 bytes or smaller.\n\nHave you checked how many of those are blobs?\n\nFor many commits, we generate as many (or more) _tree_ objects as we \ngenerate blobs. \n\nAnd tree obejcts from the same \"supertree\" really is something that I\nwouldn't mind packing some way, because they really tend to be very much\nrelated (since they refer to each other). Eg the commit and the top-level\ntree are almost always a pair, since you'd get a shared top-level tree\nonly with two commits that have the exact same content (which definitely\nhappens, don't get me wrong, but it we get some duplication for that case,\nwe'd still be winning).\n\n\t\tLinus\n"},{"id":"2476","messageId":"Pine.LNX.4.61.0505031146130.32767@cag.csail.mit.edu","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505022131380.3594@ppc970.osdl.org","subject":"Re: RFC: adding xdelta compression to git","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-05-03T15:50:59Z","receivedAt":"2005-05-03T15:50:59Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Mon, 2 May 2005, Linus Torvalds wrote:\n\n>> * Changes the repository format.\n>\n> It wouldn't necessarily. You should be able to do this with _zero_ changes\n> to existing objects what-so-ever.\n\nYes. The 'chunking' code I posted earlier does this, etc. It's kinda odd \ncomputing a SHA-1 including the 'blob \\0' header, even when your \nrepresentation doesn't use this type exactly, but it's no big deal. I'm \nstill tinkering with this, btw; I can get modest improvements in 'real' disk \nspace used, but nothing earth-shattering (yet). I'll post the list of \nthings I tried and how well they worked at some point, just to save people \nthe effort of retrying things.\n\nI've been working from the 'no knowledge of commit structure needed' \nperspective; I think Chris Mason has been using the structure of the \ncommit object to guide delta-fication and showing more impressive \nspace savings.\n --scott\n\nHTAUTOMAT Legion of Doom payment PBPRIME insurgent shortwave AVBUSY \nNader PBCABOOSE overthrow explosion Ortega STANDEL ECJOB Sigint FBI\n ( http://cscott.net/ )\n"},{"id":"2478","messageId":"Pine.LNX.4.61.0505031151380.32767@cag.csail.mit.edu","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505022215110.21733@bigblue.dev.mdolabs.com","subject":"Re: RFC: adding xdelta compression to git","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-05-03T15:52:21Z","receivedAt":"2005-05-03T15:52:21Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Mon, 2 May 2005, Davide Libenzi wrote:\n\n> On Mon, 2 May 2005, Linus Torvalds wrote:\n>\n>> Yes. EXCEPT for one thing. fsck. I'd _really_ like fsck to be able to know\n>> something about any xdelta objects, if only because if/when things go\n\n> Linus, xdelta-based algorithms already stores informations regarding the\n> object that originated the diff. Since they have no context (like\n> text-based diffs) and are simply based on offset-driven copy/insert\n> operations, this is a requirement. Libxdiff uses an adler32+size of the\n> original object, but you can get as fancy as you like in your own\n> implementation. Before a delta patching, the stored information are cross\n> checked with the input base object, and the delta patch will fail in the\n> eventuality of mismatch. So an fsck is simply a walk backward (or forward,\n> depending on your metadata model) of the whole delta chain.\n\nLinus knows this. His point is just to be sure you actually *code* that \nwalk in fsck, and (hopefully) do so w/o complicating the fsck too much.\n --scott\n\nsupercomputer BOND quiche SYNCARP Honduras North Korea Qaddafi PANCHO \nSKILLET KUDESK non-violent protest ESQUIRE struggle Saddam Hussein\n ( http://cscott.net/ )\n"},{"id":"2477","messageId":"Pine.LNX.4.62.0505031127050.14033@localhost.localdomain","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505030742330.3594@ppc970.osdl.org","subject":"[PATCH] add the ability to create and retrieve delta objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-03T15:52:46Z","receivedAt":"2005-05-03T15:52:46Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 3 May 2005, Linus Torvalds wrote:\n\n> On Tue, 3 May 2005, Nicolas Pitre wrote:\n> > \n> > Yep, that's what I've done last weekend (and just made it actually \n> > work since people are getting interested).\n> \n> I have to say that it looks uncommonly simple. Also, afaik, this should\n> still work with the current fsck, it's just that because fsck doesn't\n> understand the linkages, the error reporting won't be as good as it could\n> be (I'd _much_ rather see \"delta failed in object xxxxx\" than \"unable to\n> read xxxxxx\").\n\nYep. Let's do it in a separate patch if you please.\n\n> Now, one thing I like about this approach is that the actual delta \n> _generation_ can be done off-line, and independently of anything else. \n> Which means that the performance paths I care about (commit etc) are \n> largely unaffected, and you can \"deltify\" a git archive overnight or \n> something. \n\nYes. And actually you can use any kind of delta reference topology as \nyou wish. It may start from the first object revision and the next \nrevision is a delta against the first, the third a delta against the \nsecond, etc. But it is much more interesting to do it the other way \naround, such that the second revision is stored as is and the first \nrevision is made a delta against the second revision. Then on the next \ncommit the third revision is stored as is and the second rev made a \ndelta against the third, and so on. You therefore get delta compression \nat commit time with little overhead if you wish to do that. And this \napproach has the advantage of keeping the latest object revisions fast \naccessible and the delta overhead is relegated to the old historic \nobjects.\n\nAnd suppose the delta chain is too deep for some objects and accessing \nthem gets too much overhead. No problem: just pick a random object in \nthe middle of the delta chain and swap it with its original undeltafied \nversion and the delta chain is now cut in two.\n\nEtc. It's flexible and open to any arrangement.\n\nOK, here's a revised patch correcting the little bug found by\nChris Mason.\n\n==========\n\nThis patch adds the necessary functionalities to perform delta\ncompression on objects. It adds a git-mkdelta command which can replace\nany object with its deltafied version given a reference object.\n\nAccess to a delta object will transparently fetch the reference object\nand apply the transformation. Scripts can be used to perform any sort\nof compression policy on top of it.\n\nThe delta generator has been extracted from libxdiff and optimized for\ngit usage in order to avoid as much data copy as possible, and the delta\nstorage format modified to be even more compact. Therefore no need to\nrely on any external library. The test-delta program can be used to\ntest it.\n\nMany refinements are needed but better merge them separately. Loop \ndetection and recursion treshold are a few examples.\n\nSigned-off-by: Nicolas Pitre \n\n--- a/Makefile\n+++ b/Makefile\n@@ -29,7 +29,7 @@ install: $(PROG) $(SCRIPTS)\n \tinstall $(PROG) $(SCRIPTS) $(HOME)/bin/\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \\\n-\t tag.o date.o\n+\t tag.o date.o diff-delta.o patch-delta.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h blob.h tree.h commit.h tag.h\n \n@@ -63,6 +63,9 @@ $(LIB_FILE): $(LIB_OBJS)\n test-date: test-date.c date.o\n \t$(CC) $(CFLAGS) -o $@ test-date.c date.o\n \n+test-delta: test-delta.c diff-delta.o patch-delta.o\n+\t$(CC) $(CFLAGS) -o $@ $^\n+\n git-%: %.c $(LIB_FILE)\n \t$(CC) $(CFLAGS) -o $@ $(filter %.c,$^) $(LIBS)\n \n@@ -92,6 +95,7 @@ git-rpush: rsh.c\n git-rpull: rsh.c pull.c\n git-rev-list: rev-list.c\n git-mktag: mktag.c\n+git-mkdelta: mkdelta.c\n git-diff-tree-helper: diff-tree-helper.c\n git-tar-tree: tar-tree.c\n git-write-blob: write-blob.c\nCreated: delta.h (mode:100644)\n--- /dev/null\n+++ b/delta.h\n@@ -0,0 +1,6 @@\n+extern void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t\tvoid *to_buf, unsigned long to_size,\n+\t\t unsigned long *delta_size);\n+extern void *patch_delta(void *src_buf, unsigned long src_size,\n+\t\t\t void *delta_buf, unsigned long delta_size,\n+\t\t\t unsigned long *dst_size);\nCreated: diff-delta.c (mode:100644)\n--- /dev/null\n+++ b/diff-delta.c\n@@ -0,0 +1,315 @@\n+/*\n+ * diff-delta.c: generate a delta between two buffers\n+ *\n+ * Many parts of this file have been lifted from LibXDiff version 0.10.\n+ * http://www.xmailserver.org/xdiff-lib.html\n+ *\n+ * LibXDiff was written by Davide Libenzi \n+ * Copyright (C) 2003\tDavide Libenzi\n+ *\n+ * Many mods for GIT usage by Nicolas Pitre , (C) 2005.\n+ *\n+ * This file is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ */\n+\n+#include \n+#include \"delta.h\"\n+\n+\n+/* block size: min = 16, max = 64k, power of 2 */\n+#define BLK_SIZE 16\n+\n+#define MIN(a, b) ((a) < (b) ? (a) : (b))\n+\n+#define GR_PRIME 0x9e370001\n+#define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))\n+\t\n+/* largest prime smaller than 65536 */\n+#define BASE 65521\n+\n+/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */\n+#define NMAX 5552\n+\n+#define DO1(buf, i) { s1 += buf[i]; s2 += s1; }\n+#define DO2(buf, i) DO1(buf, i); DO1(buf, i + 1);\n+#define DO4(buf, i) DO2(buf, i); DO2(buf, i + 2);\n+#define DO8(buf, i) DO4(buf, i); DO4(buf, i + 4);\n+#define DO16(buf) DO8(buf, 0); DO8(buf, 8);\n+\n+static unsigned int adler32(unsigned int adler, const unsigned char *buf, int len)\n+{\n+\tint k;\n+\tunsigned int s1 = adler & 0xffff;\n+\tunsigned int s2 = adler >> 16;\n+\n+\twhile (len > 0) {\n+\t\tk = MIN(len, NMAX);\n+\t\tlen -= k;\n+\t\twhile (k >= 16) {\n+\t\t\tDO16(buf);\n+\t\t\tbuf += 16;\n+\t\t\tk -= 16;\n+\t\t}\n+\t\tif (k != 0)\n+\t\t\tdo {\n+\t\t\t\ts1 += *buf++;\n+\t\t\t\ts2 += s1;\n+\t\t\t} while (--k);\n+\t\ts1 %= BASE;\n+\t\ts2 %= BASE;\n+\t}\n+\n+\treturn (s2 << 16) | s1;\n+}\n+\n+static unsigned int hashbits(unsigned int size)\n+{\n+\tunsigned int val = 1, bits = 0;\n+\twhile (val < size && bits < 32) {\n+\t\tval <<= 1;\n+\t \tbits++;\n+\t}\n+\treturn bits ? bits: 1;\n+}\n+\n+typedef struct s_chanode {\n+\tstruct s_chanode *next;\n+\tint icurr;\n+} chanode_t;\n+\n+typedef struct s_chastore {\n+\tchanode_t *head, *tail;\n+\tint isize, nsize;\n+\tchanode_t *ancur;\n+\tchanode_t *sncur;\n+\tint scurr;\n+} chastore_t;\n+\n+static void cha_init(chastore_t *cha, int isize, int icount)\n+{\n+\tcha->head = cha->tail = NULL;\n+\tcha->isize = isize;\n+\tcha->nsize = icount * isize;\n+\tcha->ancur = cha->sncur = NULL;\n+\tcha->scurr = 0;\n+}\n+\n+static void *cha_alloc(chastore_t *cha)\n+{\n+\tchanode_t *ancur;\n+\tvoid *data;\n+\n+\tancur = cha->ancur;\n+\tif (!ancur || ancur->icurr == cha->nsize) {\n+\t\tancur = malloc(sizeof(chanode_t) + cha->nsize);\n+\t\tif (!ancur)\n+\t\t\treturn NULL;\n+\t\tancur->icurr = 0;\n+\t\tancur->next = NULL;\n+\t\tif (cha->tail)\n+\t\t\tcha->tail->next = ancur;\n+\t\tif (!cha->head)\n+\t\t\tcha->head = ancur;\n+\t\tcha->tail = ancur;\n+\t\tcha->ancur = ancur;\n+\t}\n+\n+\tdata = (void *)ancur + sizeof(chanode_t) + ancur->icurr;\n+\tancur->icurr += cha->isize;\n+\treturn data;\n+}\n+\n+static void cha_free(chastore_t *cha)\n+{\n+\tchanode_t *cur = cha->head;\n+\twhile (cur) {\n+\t\tchanode_t *tmp = cur;\n+\t\tcur = cur->next;\n+\t\tfree(tmp);\n+\t}\n+}\n+\n+typedef struct s_bdrecord {\n+\tstruct s_bdrecord *next;\n+\tunsigned int fp;\n+\tconst unsigned char *ptr;\n+} bdrecord_t;\n+\n+typedef struct s_bdfile {\n+\tconst unsigned char *data, *top;\n+\tchastore_t cha;\n+\tunsigned int fphbits;\n+\tbdrecord_t **fphash;\n+} bdfile_t;\n+\n+static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)\n+{\n+\tunsigned int fphbits;\n+\tint i, hsize;\n+\tconst unsigned char *base, *data, *top;\n+\tbdrecord_t *brec;\n+\tbdrecord_t **fphash;\n+\n+\tfphbits = hashbits(bufsize / BLK_SIZE + 1);\n+\thsize = 1 << fphbits;\n+\tfphash = malloc(hsize * sizeof(bdrecord_t *));\n+\tif (!fphash)\n+\t\treturn -1;\n+\tfor (i = 0; i < hsize; i++)\n+\t\tfphash[i] = NULL;\n+\tcha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);\n+\n+\tbdf->data = data = base = buf;\n+\tbdf->top = top = buf + bufsize;\n+\tdata += (bufsize / BLK_SIZE) * BLK_SIZE;\n+\tif (data == top)\n+\t\tdata -= BLK_SIZE;\n+\n+\tfor ( ; data >= base; data -= BLK_SIZE) {\n+\t\tbrec = cha_alloc(&bdf->cha);\n+\t\tif (!brec) {\n+\t\t\tcha_free(&bdf->cha);\n+\t\t\tfree(fphash);\n+\t\t\treturn -1;\n+\t\t}\n+\t\tbrec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));\n+\t\tbrec->ptr = data;\n+\t\ti = HASH(brec->fp, fphbits);\n+\t\tbrec->next = fphash[i];\n+\t\tfphash[i] = brec;\n+\t}\n+\n+\tbdf->fphbits = fphbits;\n+\tbdf->fphash = fphash;\n+\n+\treturn 0;\n+}\n+\n+static void delta_cleanup(bdfile_t *bdf)\n+{\n+\tfree(bdf->fphash);\n+\tcha_free(&bdf->cha);\n+}\n+\n+#define COPYOP_SIZE(o, s) \\\n+ (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \\\n+ !!(s & 0xff) + !!(s & 0xff00) + 1)\n+\n+void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t void *to_buf, unsigned long to_size,\n+\t\t unsigned long *delta_size)\n+{\n+\tint i, outpos, outsize, inscnt, csize, msize, moff;\n+\tunsigned int fp;\n+\tconst unsigned char *data, *top, *ptr1, *ptr2;\n+\tunsigned char *out, *orig;\n+\tbdrecord_t *brec;\n+\tbdfile_t bdf;\n+\n+\tif (delta_prepare(from_buf, from_size, &bdf))\n+\t\treturn NULL;\n+\t\n+\toutpos = 0;\n+\toutsize = 4096;\n+\tout = malloc(outsize);\n+\tif (!out) {\n+\t\tdelta_cleanup(&bdf);\n+\t\treturn NULL;\n+\t}\n+\n+\tdata = to_buf;\n+\ttop = to_buf + to_size;\n+\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size;\n+\n+\tinscnt = 0;\n+\tmoff = 0;\n+\twhile (data < top) {\n+\t\tmsize = 0;\n+\t\tfp = adler32(0, data, MIN(top - data, BLK_SIZE));\n+\t\ti = HASH(fp, bdf.fphbits);\n+\t\tfor (brec = bdf.fphash[i]; brec; brec = brec->next) {\n+\t\t\tif (brec->fp == fp) {\n+\t\t\t\tcsize = bdf.top - brec->ptr;\n+\t\t\t\tif (csize > top - data)\n+\t\t\t\t\tcsize = top - data;\n+\t\t\t\tfor (ptr1 = brec->ptr, ptr2 = data; \n+\t\t\t\t csize && *ptr1 == *ptr2;\n+\t\t\t\t csize--, ptr1++, ptr2++);\n+\n+\t\t\t\tcsize = ptr1 - brec->ptr;\n+\t\t\t\tif (csize > msize) {\n+\t\t\t\t\tmoff = brec->ptr - bdf.data;\n+\t\t\t\t\tmsize = csize;\n+\t\t\t\t\tif (msize >= 0x10000) {\n+\t\t\t\t\t\tmsize = 0x10000;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!msize || msize < COPYOP_SIZE(moff, msize)) {\n+\t\t\tif (!inscnt)\n+\t\t\t\toutpos++;\n+\t\t\tout[outpos++] = *data++;\n+\t\t\tinscnt++;\n+\t\t\tif (inscnt == 0x7f) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tif (inscnt) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\n+\t\t\tdata += msize;\n+\t\t\torig = out + outpos++;\n+\t\t\ti = 0x80;\n+\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }\n+\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }\n+\t\t\tmsize >>= 8;\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }\n+\n+\t\t\t*orig = i;\n+\t\t}\n+\n+\t\t/* next time around the largest possible output is 1 + 4 + 3 */\n+\t\tif (outpos > outsize - 8) {\n+\t\t\tvoid *tmp = out;\n+\t\t\toutsize = outsize * 3 / 2;\n+\t\t\tout = realloc(out, outsize);\n+\t\t\tif (!out) {\n+\t\t\t\tfree(tmp);\n+\t\t\t\tdelta_cleanup(&bdf);\n+\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tif (inscnt)\n+\t\tout[outpos - inscnt - 1] = inscnt;\n+\n+\tdelta_cleanup(&bdf);\n+\t*delta_size = outpos;\n+\treturn out;\n+}\nCreated: patch-delta.c (mode:100644)\n--- /dev/null\n+++ b/patch-delta.c\n@@ -0,0 +1,73 @@\n+/*\n+ * patch-delta.c:\n+ * recreate a buffer from a source and the delta produced by diff-delta.c\n+ *\n+ * (C) 2005 Nicolas Pitre \n+ *\n+ * This code is free software; you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License version 2 as\n+ * published by the Free Software Foundation.\n+ */\n+\n+#include \n+#include \n+#include \"delta.h\"\n+\n+void *patch_delta(void *src_buf, unsigned long src_size,\n+\t\t void *delta_buf, unsigned long delta_size,\n+\t\t unsigned long *dst_size)\n+{\n+\tconst unsigned char *data, *top;\n+\tunsigned char *dst, *out;\n+\tint size;\n+\n+\t/* the smallest delta size possible is 10 bytes */\n+\tif (delta_size < 10)\n+\t\treturn NULL;\n+\n+\tdata = delta_buf;\n+\ttop = delta_buf + delta_size;\n+\n+\t/* make sure the orig file size matches what we expect */\n+\tsize = data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);\n+\tdata += 4;\n+\tif (size != src_size)\n+\t\treturn NULL;\n+\n+\t/* now the result size */\n+\tsize = data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);\n+\tdata += 4;\n+\tdst = malloc(size);\n+\tif (!dst)\n+\t\treturn NULL;\n+\n+\tout = dst;\n+\twhile (data < top) {\n+\t\tunsigned char cmd = *data++;\n+\t\tif (cmd & 0x80) {\n+\t\t\tunsigned int cp_off = 0, cp_size = 0;\n+\t\t\tif (cmd & 0x01) cp_off = *data++;\n+\t\t\tif (cmd & 0x02) cp_off |= (*data++ << 8);\n+\t\t\tif (cmd & 0x04) cp_off |= (*data++ << 16);\n+\t\t\tif (cmd & 0x08) cp_off |= (*data++ << 24);\n+\t\t\tif (cmd & 0x10) cp_size = *data++;\n+\t\t\tif (cmd & 0x20) cp_size |= (*data++ << 8);\n+\t\t\tif (cp_size == 0) cp_size = 0x10000;\n+\t\t\tmemcpy(out, src_buf + cp_off, cp_size);\n+\t\t\tout += cp_size;\n+\t\t} else {\n+\t\t\tmemcpy(out, data, cmd);\n+\t\t\tout += cmd;\n+\t\t\tdata += cmd;\n+\t\t}\n+\t}\n+\n+\t/* sanity check */\n+\tif (data != top || out - dst != size) {\n+\t\tfree(dst);\n+\t\treturn NULL;\n+\t}\n+\n+\t*dst_size = size;\n+\treturn dst;\n+}\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -8,6 +8,7 @@\n */\n #include \n #include \"cache.h\"\n+#include \"delta.h\"\n \n const char *sha1_file_directory = NULL;\n \n@@ -186,7 +187,8 @@ void * unpack_sha1_file(void *map, unsig\n \tint ret, bytes;\n \tz_stream stream;\n \tchar buffer[8192];\n-\tchar *buf;\n+\tchar *buf, *delta_ref;\n+\tunsigned long delta_ref_sz;\n \n \t/* Get the data stream */\n \tmemset(&stream, 0, sizeof(stream));\n@@ -201,8 +203,15 @@ void * unpack_sha1_file(void *map, unsig\n \t\treturn NULL;\n \tif (sscanf(buffer, \"%10s %lu\", type, size) != 2)\n \t\treturn NULL;\n-\n \tbytes = strlen(buffer) + 1;\n+\n+\tif (!strcmp(type, \"delta\")) {\n+\t\tdelta_ref = read_sha1_file(buffer + bytes, type, &delta_ref_sz);\n+\t\tif (!delta_ref)\n+\t\t\treturn NULL;\n+\t} else\n+\t\tdelta_ref = NULL;\n+\n \tbuf = xmalloc(*size);\n \n \tmemcpy(buf, buffer + bytes, stream.total_out - bytes);\n@@ -214,6 +223,17 @@ void * unpack_sha1_file(void *map, unsig\n \t\t\t/* nothing */;\n \t}\n \tinflateEnd(&stream);\n+\n+\tif (delta_ref) {\n+\t\tchar *newbuf;\n+\t\tunsigned long newsize;\n+\t\tnewbuf = patch_delta(delta_ref, delta_ref_sz, buf+20, *size-20, &newsize);\n+\t\tfree(delta_ref);\n+\t\tfree(buf);\n+\t\tbuf = newbuf;\n+\t\t*size = newsize;\n+\t}\n+\n \treturn buf;\n }\n \nCreated: test-delta.c (mode:100644)\n--- /dev/null\n+++ b/test-delta.c\n@@ -0,0 +1,79 @@\n+/*\n+ * test-delta.c: test code to exercise diff-delta.c and patch-delta.c\n+ *\n+ * (C) 2005 Nicolas Pitre \n+ *\n+ * This code is free software; you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License version 2 as\n+ * published by the Free Software Foundation.\n+ */\n+\n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \n+#include \"delta.h\"\n+\n+static const char *usage =\n+\t\"test-delta (-d|-p) \";\n+\n+int main(int argc, char *argv[])\n+{\n+\tint fd;\n+\tstruct stat st;\n+\tvoid *from_buf, *data_buf, *out_buf;\n+\tunsigned long from_size, data_size, out_size;\n+\n+\tif (argc != 5 || (strcmp(argv[1], \"-d\") && strcmp(argv[1], \"-p\"))) {\n+\t\tfprintf(stderr, \"Usage: %s\\n\", usage);\n+\t\treturn 1;\n+\t}\n+\n+\tfd = open(argv[2], O_RDONLY);\n+\tif (fd < 0 || fstat(fd, &st)) {\n+\t\tperror(argv[2]);\n+\t\treturn 1;\n+\t}\n+\tfrom_size = st.st_size;\n+\tfrom_buf = mmap(NULL, from_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (from_buf == MAP_FAILED) {\n+\t\tperror(argv[2]);\n+\t\treturn 1;\n+\t}\n+\tclose(fd);\n+\n+\tfd = open(argv[3], O_RDONLY);\n+\tif (fd < 0 || fstat(fd, &st)) {\n+\t\tperror(argv[3]);\n+\t\treturn 1;\n+\t}\n+\tdata_size = st.st_size;\n+\tdata_buf = mmap(NULL, data_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (data_buf == MAP_FAILED) {\n+\t\tperror(argv[3]);\n+\t\treturn 1;\n+\t}\n+\tclose(fd);\n+\n+\tif (argv[1][1] == 'd')\n+\t\tout_buf = diff_delta(from_buf, from_size,\n+\t\t\t\t data_buf, data_size, &out_size);\n+\telse\n+\t\tout_buf = patch_delta(from_buf, from_size,\n+\t\t\t\t data_buf, data_size, &out_size);\n+\tif (!out_buf) {\n+\t\tfprintf(stderr, \"delta operation failed (returned NULL)\\n\");\n+\t\treturn 1;\n+\t}\n+\n+\tfd = open (argv[4], O_WRONLY|O_CREAT|O_TRUNC, 0666);\n+\tif (fd < 0 || write(fd, out_buf, out_size) != out_size) {\n+\t\tperror(argv[4]);\n+\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n"},{"id":"2479","messageId":"Pine.LNX.4.61.0505031153550.32767@cag.csail.mit.edu","threadId":"453","inReplyTo":"200505030724.57827.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-05-03T15:57:12Z","receivedAt":"2005-05-03T15:57:12Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Tue, 3 May 2005, Chris Mason wrote:\n\n> your delta generator later this week. Some quick and dirty space numbers to\n> show why we need to pack the files together:\n\nAre you accurately accounting for the cost of the extra hard/soft links \nyour scheme requires? Ie the directories get larger, lookups take \nslightly longer, etc. Also access to a given file takes longer, and the \ndeltas are referring to *other* packed files which *also* take longer to \ndecompress and access...\n\nHow much better does delta-fication do, compared to just packing?\n --scott\n\nNSA FJDEFLECT radar WASHTUB justice LCFLUTTER KUCLUB PBHISTORY Ft. Bragg \nammunition immediate ESMERALDITE DC terrorist C4 SLBM affinity group\n ( http://cscott.net/ )\n"},{"id":"2481","messageId":"200505031209.52460.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505030804170.3594@ppc970.osdl.org","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-03T16:09:51Z","receivedAt":"2005-05-03T16:09:51Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 03 May 2005 11:07, Linus Torvalds wrote:\n> On Tue, 3 May 2005, Chris Mason wrote:\n> > On the full import of all the bk->cvs changesets, the average file size\n> > in .git is 4074 bytes. 73% of the files are 4096 bytes or smaller.\n>\n> Have you checked how many of those are blobs?\n>\nI've got cg-admin-lsobj running (effectively find .git -type f | xargs \ncat-file), it is taking a looong time but the ratios seem to stay pretty \nconstant as it makes progress:\n\ntotal: 186863\nblob: 93688 (6.6 per commit)\ncommit: 14172\ntree: 79003 (5.5 per commit)\n\n> For many commits, we generate as many (or more) _tree_ objects as we\n> generate blobs.\n>\n> And tree obejcts from the same \"supertree\" really is something that I\n> wouldn't mind packing some way, because they really tend to be very much\n> related (since they refer to each other). Eg the commit and the top-level\n> tree are almost always a pair, since you'd get a shared top-level tree\n> only with two commits that have the exact same content (which definitely\n> happens, don't get me wrong, but it we get some duplication for that case,\n> we'd still be winning).\n>\n\nThe packed item patch wouldn't duplicate info in this case. When it initially \ncreates the packed buffer (before compression), it checks for an existing \nfile with the same sha1 and returns if one is found. This is to preserve the \noptimizations for write_tree case where it frequently tries to create files \nthat already exist.\n\n-chris\n"},{"id":"2484","messageId":"200505031235.31984.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.61.0505031153550.32767@cag.csail.mit.edu","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-03T16:35:31Z","receivedAt":"2005-05-03T16:35:31Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 03 May 2005 11:57, C. Scott Ananian wrote:\n> On Tue, 3 May 2005, Chris Mason wrote:\n> > your delta generator later this week. Some quick and dirty space numbers\n> > to show why we need to pack the files together:\n>\n> Are you accurately accounting for the cost of the extra hard/soft links\n> your scheme requires? Ie the directories get larger, lookups take\n> slightly longer, etc. Also access to a given file takes longer, and the\n> deltas are referring to *other* packed files which *also* take longer to\n> decompress and access...\n\nMy patch doesn't create any extra directory entries because the file for the \npacked file is unlinked after all the hard links are made. Even if I kept \nthe packed file directory entry, I'd adding one directory entry and saving an \naverage 6-7 inodes per commit.\n\n>\n> How much better does delta-fication do, compared to just packing?\n\nThe best case for just packing is to pack the blobs, trees and commits all \ninto one object. Doing all three brought the tree down from 2.5GB to 1.57GB. \n\nThe delta patch does pack trees together, but not into the same file as the \nblobs, and commits are not packed at all. This is just because it is a pain \nto carry those changes around; it'll be easy to do later.\n\nWith the delta patch, the tree is around 900MB, I estimate packing the commits \nand trees into the blob files would save another 200MB.\n\nBecause space savings is so tightly coupled with packing ratios, a script to \nrepack blobs, trees and commits from multiple commits will give much better \ncompression. Right now the patch does not delta trees or commits, but it \nmight make sense to delta the trees via the repacking script.\n\n-chris\n"},{"id":"2485","messageId":"200505031254.43952.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.62.0505031104080.14033@localhost.localdomain","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-03T16:54:43Z","receivedAt":"2005-05-03T16:54:43Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 03 May 2005 11:04, Nicolas Pitre wrote:\n> On Tue, 3 May 2005, Chris Mason wrote:\n\n> > coffee:~/git/linus.orig # echo foo > foo\n> > coffee:~/git/linus.orig # echo foo2 > foo2\n> > coffee:~/git/linus.orig # ./test-delta -d foo foo2 delta1\n> > coffee:~/git/linus.orig # ls -la delta1\n> > -rw-r--r-- 1 root root 14 2005-05-03 10:36 delta1\n> > coffee:~/git/linus.orig # ./test-delta -p foo delta1 out\n> > *** glibc detected *** free(): invalid next size (fast): 0x0804b008 ***\n>\n> OK, doh!\n\nThanks, this one works ;) I'll kick off a run with this replacing zdelta, \nshould be around 3 hours. For my small tree run with 300 patches, its faster \nthan zdelta with about the same space savings.\n\n-chris\n"},{"id":"2489","messageId":"Pine.LNX.4.58.0505031031240.3594@ppc970.osdl.org","threadId":"453","inReplyTo":"Pine.LNX.4.61.0505031151380.32767@cag.csail.mit.edu","subject":"Re: RFC: adding xdelta compression to git","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-03T17:35:13Z","receivedAt":"2005-05-03T17:35:13Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 3 May 2005, C. Scott Ananian wrote:\n> \n> Linus knows this. His point is just to be sure you actually *code* that \n> walk in fsck, and (hopefully) do so w/o complicating the fsck too much.\n\nIndeed. It's also a performance issue.\n\nIf you do xdelta objects, and don't tell fsck about it, then fsck will \njust check every object as a blob. Why is that bad?\n\nThink about it: let's say that you have a series of xdelta objects, and a \nfsck that is xdelta-unaware. It will unpack each object independently, \nwhich means that it will keep on doing the same early xdelta work over and \nover and over again. Instead of just applying them in order, and checking \nthe sha1 of the result at each point.\n\nNow, You probably want to limit the length of the chains to some firly \nsmall number anyway, so maybe that's not a big deal. Who knows. And I'm \nactually still so anal that I don't think I'd use this for _my_ tree, just \nbecause I'm a worry-wart (and I still think disk is incredibly cheap ;)\n\n\t\tLinus\n"},{"id":"2491","messageId":"Pine.LNX.4.58.0505031048440.13099@bigblue.dev.mdolabs.com","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505031031240.3594@ppc970.osdl.org","subject":"Re: RFC: adding xdelta compression to git","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2005-05-03T18:10:32Z","receivedAt":"2005-05-03T18:10:32Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Tue, 3 May 2005, Linus Torvalds wrote:\n\n> On Tue, 3 May 2005, C. Scott Ananian wrote:\n> > \n> > Linus knows this. His point is just to be sure you actually *code* that \n> > walk in fsck, and (hopefully) do so w/o complicating the fsck too much.\n> \n> Indeed. It's also a performance issue.\n> \n> If you do xdelta objects, and don't tell fsck about it, then fsck will \n> just check every object as a blob. Why is that bad?\n> \n> Think about it: let's say that you have a series of xdelta objects, and a \n> fsck that is xdelta-unaware. It will unpack each object independently, \n> which means that it will keep on doing the same early xdelta work over and \n> over and over again. Instead of just applying them in order, and checking \n> the sha1 of the result at each point.\n> \n> Now, You probably want to limit the length of the chains to some firly \n> small number anyway, so maybe that's not a big deal. Who knows. And I'm \n> actually still so anal that I don't think I'd use this for _my_ tree, just \n> because I'm a worry-wart (and I still think disk is incredibly cheap ;)\n\nIf you use a \"full tip\" metadata format with reverse deltas, you drop a \n\"full\" version \"time to time\" along the chain, and you keep a small index \nfile, you have:\n\n1) No matter how big it becomes the xdelta collection object, you are only \n touching very limited regions of it (due the small index file, that can \n be less than 20+8 bytes per entry in the xdelta blob)\n\n2) Checkout happens w/out even doing xpatching (since the tip is full)\n\n3) Checkins requires only one xdelta operation (since the tip is full), \n and zero if it is the time to store a full version along the chain (I \n use to drop one every 10-16 xdeltas, depending on the progressive size \n of the delta operations)\n\n4) Worst case performance in reconstructing histories are bound by the \n longest xdelta chain (10-16)\n\nIn some way I tend to agree (strangely ;) with you about the disk-cheap \nmantra, but network bandwidth matter IMO. So, if you do not want (being a \nreal worry-wart) to use xdelta leverage on the FS trees, you can have way \nsmarter network protocols using xdelta plus the knowledge of the git \nhistory structure. The rsync algo uses xdelta, but the poor guy is not \nable to leverage from the knowledge of the history that only git knows. \nSo, if Larry and Greg shares a common object A, Larry changes A and makes \na new git object B, rsync will transfer the whole object B, because it \ndoes not have any idea of the git structure. Git though, has this \nknowledge, and it can say to the remote fetcher: Look, I have this new \nthing called B, that is basically your thing A plus this very small xdelta \n(B-A). And typical xdelta diffs are really small (1/7 to 1/10 of classical \n'diff -u' ones).\n\n\n\n\n- Davide\n\n"},{"id":"2578","messageId":"200505041156.19499.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.62.0505030344170.14033@localhost.localdomain","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-04T15:56:18Z","receivedAt":"2005-05-04T15:56:18Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Tuesday 03 May 2005 04:06, Nicolas Pitre wrote:\n> On Mon, 2 May 2005, Linus Torvalds wrote:\n> > If you do something like this, you want such a delta-blob to be named by\n> > the sha1 of the result, so that things that refer to it can transparently\n> > see either the original blob _or_ the \"deltified\" one, and will never\n> > care.\n>\n> Yep, that's what I've done last weekend (and just made it actually\n> work since people are getting interested).\n>\n\nMy first run didn't go well, diff_delta generates an invalid delta when passed \na buffer of length 0. I really should not have been calling it this way, but \nit should do a quick check and return an error instead of something \ninvalid ;)\n\nI did two additional runs, first where I fixed the delta chain length at 1 as \nin the zdelta patch. In this mode, if it tried to diff against a delta it \nwould find the delta's parent and diff against that instead. Even though \nzdelta had the same speeds for applying patches as xdiff(1), zdelta used \nsignificantly more cpu (53m vs 40m).\n\nThe next run was with the patch I've attached below, it allows chains up to 16 \ndeltas in length. \n git zdelta xdiff (1) xdiff(16)\napply 150m 117m 117m 104m\ncheckout 4m30s 3m41 4m43s 7m11s\ncheckout (hot) 56s 12s 14s 16s\nspace usage 2.5G 1G 1.2G 800m\n\nThe longer delta chains trigger more random io on checkout, negating the speed \nimprovements from the packed item patch. The hot cache times show that xdiff \nisn't using a huge amount of cpu to patch things in, and so there's room for \nsmarter packing and regenerating deltas in order to keep checkout times low. \nThis patch still doesn't pack commits and trees in with the blob files, and \nit doesn't delta trees, and so I expect better space/speed numbers in later \nrevs.\n\nI won't be able to work on this until next week, but here's my plan:\n\n1) update to current git. My patch is from before the safe file generation \nchanges.\n\n2) change update-cache and write-tree so that packing/deltas are off by \ndefault. Add --packed and --delta options to both.\n\n3) create a git-pack tool that can pack/unpack existing changesets,trees and \nfiles, optionally adding/removing deltas.\n\nMy current code should preserve the delta object header used by Nicolas, and \nremoves all knowledge of deltas from the packed item headers. This is not \nquite as efficient, but the resulting code is much cleaner. I haven't tried, \nbut it should be able to read a file created by his mkdelta.c.\n\n-chris\n\n\ndiff -urN --exclude .git linus.diff/cache.h linus.mine/cache.h\n--- linus.diff/cache.h\t2005-05-04 09:54:49.154735216 -0400\n+++ linus.mine/cache.h\t2005-05-04 08:47:28.618990016 -0400\n@@ -64,6 +64,16 @@\n \tchar name[0];\n };\n \n+struct packed_item {\n+\t/* length of compressed data */\n+\tunsigned long len;\n+\tstruct packed_item *next;\n+\t/* sha1 of uncompressed data */\n+\tchar sha1[20];\n+\t/* compressed data */\n+\tchar *data;\n+};\n+\n #define CE_NAMEMASK (0x0fff)\n #define CE_STAGEMASK (0x3000)\n #define CE_STAGESHIFT 12\n@@ -119,8 +129,9 @@\n \n /* Read and unpack a sha1 file into memory, write memory to a sha1 file */\n extern void * map_sha1_file(const unsigned char *sha1, unsigned long *size);\n-extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);\n+extern void * unpack_sha1_file(const unsigned char *sha1, void *map, unsigned long mapsize, char *type, unsigned long *size, int *chain);\n extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);\n+extern void * read_sha1_delta_ref(const unsigned char *sha1, char *type, unsigned long *size, int *chain);\n extern int write_sha1_file(char *buf, unsigned long len, const char *type, unsigned char *return_sha1);\n \n extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);\n@@ -135,6 +146,10 @@\n /* Convert to/from hex/sha1 representation */\n extern int get_sha1_hex(const char *hex, unsigned char *sha1);\n extern char *sha1_to_hex(const unsigned char *sha1);\t/* static buffer result! */\n+extern int pack_sha1_buffer(void *buf, unsigned long buf_len, char *type,\n+ unsigned char *returnsha1, unsigned char *refsha1, \n+\t\t\t struct packed_item **);\n+int write_packed_buffer(struct packed_item *head);\n \n /* General helper functions */\n extern void usage(const char *err);\ndiff -urN --exclude .git linus.diff/delta.h linus.mine/delta.h\n--- linus.diff/delta.h\t1969-12-31 19:00:00.000000000 -0500\n+++ linus.mine/delta.h\t2005-05-03 08:22:32.000000000 -0400\n@@ -0,0 +1,6 @@\n+extern void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t\tvoid *to_buf, unsigned long to_size,\n+\t\t unsigned long *delta_size);\n+extern void *patch_delta(void *src_buf, unsigned long src_size,\n+\t\t\t void *delta_buf, unsigned long delta_size,\n+\t\t\t unsigned long *dst_size);\ndiff -urN --exclude .git linus.diff/diff-delta.c linus.mine/diff-delta.c\n--- linus.diff/diff-delta.c\t1969-12-31 19:00:00.000000000 -0500\n+++ linus.mine/diff-delta.c\t2005-05-03 12:40:58.000000000 -0400\n@@ -0,0 +1,315 @@\n+/*\n+ * diff-delta.c: generate a delta between two buffers\n+ *\n+ * Many parts of this file have been lifted from LibXDiff version 0.10.\n+ * http://www.xmailserver.org/xdiff-lib.html\n+ *\n+ * LibXDiff was written by Davide Libenzi \n+ * Copyright (C) 2003\tDavide Libenzi\n+ *\n+ * Many mods for GIT usage by Nicolas Pitre , (C) 2005.\n+ *\n+ * This file is free software; you can redistribute it and/or\n+ * modify it under the terms of the GNU Lesser General Public\n+ * License as published by the Free Software Foundation; either\n+ * version 2.1 of the License, or (at your option) any later version.\n+ */\n+\n+#include \n+#include \"delta.h\"\n+\n+\n+/* block size: min = 16, max = 64k, power of 2 */\n+#define BLK_SIZE 16\n+\n+#define MIN(a, b) ((a) < (b) ? (a) : (b))\n+\n+#define GR_PRIME 0x9e370001\n+#define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))\n+\t\n+/* largest prime smaller than 65536 */\n+#define BASE 65521\n+\n+/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */\n+#define NMAX 5552\n+\n+#define DO1(buf, i) { s1 += buf[i]; s2 += s1; }\n+#define DO2(buf, i) DO1(buf, i); DO1(buf, i + 1);\n+#define DO4(buf, i) DO2(buf, i); DO2(buf, i + 2);\n+#define DO8(buf, i) DO4(buf, i); DO4(buf, i + 4);\n+#define DO16(buf) DO8(buf, 0); DO8(buf, 8);\n+\n+static unsigned int adler32(unsigned int adler, const unsigned char *buf, int len)\n+{\n+\tint k;\n+\tunsigned int s1 = adler & 0xffff;\n+\tunsigned int s2 = adler >> 16;\n+\n+\twhile (len > 0) {\n+\t\tk = MIN(len, NMAX);\n+\t\tlen -= k;\n+\t\twhile (k >= 16) {\n+\t\t\tDO16(buf);\n+\t\t\tbuf += 16;\n+\t\t\tk -= 16;\n+\t\t}\n+\t\tif (k != 0)\n+\t\t\tdo {\n+\t\t\t\ts1 += *buf++;\n+\t\t\t\ts2 += s1;\n+\t\t\t} while (--k);\n+\t\ts1 %= BASE;\n+\t\ts2 %= BASE;\n+\t}\n+\n+\treturn (s2 << 16) | s1;\n+}\n+\n+static unsigned int hashbits(unsigned int size)\n+{\n+\tunsigned int val = 1, bits = 0;\n+\twhile (val < size && bits < 32) {\n+\t\tval <<= 1;\n+\t \tbits++;\n+\t}\n+\treturn bits ? bits: 1;\n+}\n+\n+typedef struct s_chanode {\n+\tstruct s_chanode *next;\n+\tint icurr;\n+} chanode_t;\n+\n+typedef struct s_chastore {\n+\tchanode_t *head, *tail;\n+\tint isize, nsize;\n+\tchanode_t *ancur;\n+\tchanode_t *sncur;\n+\tint scurr;\n+} chastore_t;\n+\n+static void cha_init(chastore_t *cha, int isize, int icount)\n+{\n+\tcha->head = cha->tail = NULL;\n+\tcha->isize = isize;\n+\tcha->nsize = icount * isize;\n+\tcha->ancur = cha->sncur = NULL;\n+\tcha->scurr = 0;\n+}\n+\n+static void *cha_alloc(chastore_t *cha)\n+{\n+\tchanode_t *ancur;\n+\tvoid *data;\n+\n+\tancur = cha->ancur;\n+\tif (!ancur || ancur->icurr == cha->nsize) {\n+\t\tancur = malloc(sizeof(chanode_t) + cha->nsize);\n+\t\tif (!ancur)\n+\t\t\treturn NULL;\n+\t\tancur->icurr = 0;\n+\t\tancur->next = NULL;\n+\t\tif (cha->tail)\n+\t\t\tcha->tail->next = ancur;\n+\t\tif (!cha->head)\n+\t\t\tcha->head = ancur;\n+\t\tcha->tail = ancur;\n+\t\tcha->ancur = ancur;\n+\t}\n+\n+\tdata = (void *)ancur + sizeof(chanode_t) + ancur->icurr;\n+\tancur->icurr += cha->isize;\n+\treturn data;\n+}\n+\n+static void cha_free(chastore_t *cha)\n+{\n+\tchanode_t *cur = cha->head;\n+\twhile (cur) {\n+\t\tchanode_t *tmp = cur;\n+\t\tcur = cur->next;\n+\t\tfree(tmp);\n+\t}\n+}\n+\n+typedef struct s_bdrecord {\n+\tstruct s_bdrecord *next;\n+\tunsigned int fp;\n+\tconst unsigned char *ptr;\n+} bdrecord_t;\n+\n+typedef struct s_bdfile {\n+\tconst unsigned char *data, *top;\n+\tchastore_t cha;\n+\tunsigned int fphbits;\n+\tbdrecord_t **fphash;\n+} bdfile_t;\n+\n+static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)\n+{\n+\tunsigned int fphbits;\n+\tint i, hsize;\n+\tconst unsigned char *base, *data, *top;\n+\tbdrecord_t *brec;\n+\tbdrecord_t **fphash;\n+\n+\tfphbits = hashbits(bufsize / BLK_SIZE + 1);\n+\thsize = 1 << fphbits;\n+\tfphash = malloc(hsize * sizeof(bdrecord_t *));\n+\tif (!fphash)\n+\t\treturn -1;\n+\tfor (i = 0; i < hsize; i++)\n+\t\tfphash[i] = NULL;\n+\tcha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);\n+\n+\tbdf->data = data = base = buf;\n+\tbdf->top = top = buf + bufsize;\n+\tdata += (bufsize / BLK_SIZE) * BLK_SIZE;\n+\tif (data == top)\n+\t\tdata -= BLK_SIZE;\n+\n+\tfor ( ; data >= base; data -= BLK_SIZE) {\n+\t\tbrec = cha_alloc(&bdf->cha);\n+\t\tif (!brec) {\n+\t\t\tcha_free(&bdf->cha);\n+\t\t\tfree(fphash);\n+\t\t\treturn -1;\n+\t\t}\n+\t\tbrec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));\n+\t\tbrec->ptr = data;\n+\t\ti = HASH(brec->fp, fphbits);\n+\t\tbrec->next = fphash[i];\n+\t\tfphash[i] = brec;\n+\t}\n+\n+\tbdf->fphbits = fphbits;\n+\tbdf->fphash = fphash;\n+\n+\treturn 0;\n+}\n+\n+static void delta_cleanup(bdfile_t *bdf)\n+{\n+\tfree(bdf->fphash);\n+\tcha_free(&bdf->cha);\n+}\n+\n+#define COPYOP_SIZE(o, s) \\\n+ (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \\\n+ !!(s & 0xff) + !!(s & 0xff00) + 1)\n+\n+void *diff_delta(void *from_buf, unsigned long from_size,\n+\t\t void *to_buf, unsigned long to_size,\n+\t\t unsigned long *delta_size)\n+{\n+\tint i, outpos, outsize, inscnt, csize, msize, moff;\n+\tunsigned int fp;\n+\tconst unsigned char *data, *top, *ptr1, *ptr2;\n+\tunsigned char *out, *orig;\n+\tbdrecord_t *brec;\n+\tbdfile_t bdf;\n+\n+\tif (delta_prepare(from_buf, from_size, &bdf))\n+\t\treturn NULL;\n+\t\n+\toutpos = 0;\n+\toutsize = 4096;\n+\tout = malloc(outsize);\n+\tif (!out) {\n+\t\tdelta_cleanup(&bdf);\n+\t\treturn NULL;\n+\t}\n+\n+\tdata = to_buf;\n+\ttop = to_buf + to_size;\n+\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size; from_size >>= 8;\n+\tout[outpos++] = from_size;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size; to_size >>= 8;\n+\tout[outpos++] = to_size;\n+\n+\tinscnt = 0;\n+\tmoff = 0;\n+\twhile (data < top) {\n+\t\tmsize = 0;\n+\t\tfp = adler32(0, data, MIN(top - data, BLK_SIZE));\n+\t\ti = HASH(fp, bdf.fphbits);\n+\t\tfor (brec = bdf.fphash[i]; brec; brec = brec->next) {\n+\t\t\tif (brec->fp == fp) {\n+\t\t\t\tcsize = bdf.top - brec->ptr;\n+\t\t\t\tif (csize > top - data)\n+\t\t\t\t\tcsize = top - data;\n+\t\t\t\tfor (ptr1 = brec->ptr, ptr2 = data; \n+\t\t\t\t csize && *ptr1 == *ptr2;\n+\t\t\t\t csize--, ptr1++, ptr2++);\n+\n+\t\t\t\tcsize = ptr1 - brec->ptr;\n+\t\t\t\tif (csize > msize) {\n+\t\t\t\t\tmoff = brec->ptr - bdf.data;\n+\t\t\t\t\tmsize = csize;\n+\t\t\t\t\tif (msize >= 0x10000) {\n+\t\t\t\t\t\tmsize = 0x10000;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!msize || msize < COPYOP_SIZE(moff, msize)) {\n+\t\t\tif (!inscnt)\n+\t\t\t\toutpos++;\n+\t\t\tout[outpos++] = *data++;\n+\t\t\tinscnt++;\n+\t\t\tif (inscnt == 0x7f) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tif (inscnt) {\n+\t\t\t\tout[outpos - inscnt - 1] = inscnt;\n+\t\t\t\tinscnt = 0;\n+\t\t\t}\n+\n+\t\t\tdata += msize;\n+\t\t\torig = out + outpos++;\n+\t\t\ti = 0x80;\n+\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }\n+\t\t\tmoff >>= 8;\n+\t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }\n+\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }\n+\t\t\tmsize >>= 8;\n+\t\t\tif (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }\n+\n+\t\t\t*orig = i;\n+\t\t}\n+\n+\t\t/* next time around the largest possible output is 1 + 4 + 3 */\n+\t\tif (outpos > outsize - 8) {\n+\t\t\tvoid *tmp = out;\n+\t\t\toutsize = outsize * 3 / 2;\n+\t\t\tout = realloc(out, outsize);\n+\t\t\tif (!out) {\n+\t\t\t\tfree(tmp);\n+\t\t\t\tdelta_cleanup(&bdf);\n+\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tif (inscnt)\n+\t\tout[outpos - inscnt - 1] = inscnt;\n+\n+\tdelta_cleanup(&bdf);\n+\t*delta_size = outpos;\n+\treturn out;\n+}\ndiff -urN --exclude .git linus.diff/fsck-cache.c linus.mine/fsck-cache.c\n--- linus.diff/fsck-cache.c\t2005-05-04 09:54:49.158734608 -0400\n+++ linus.mine/fsck-cache.c\t2005-05-04 08:44:49.778137496 -0400\n@@ -142,7 +142,7 @@\n \t\tif (map) {\n \t\t\tchar type[100];\n \t\t\tunsigned long size;\n-\t\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, &size);\n+\t\t\tvoid *buffer = unpack_sha1_file(sha1, map, mapsize, type, &size, NULL);\n \t\t\tif (!buffer)\n \t\t\t\treturn -1;\n \t\t\tif (check_sha1_signature(sha1, buffer, size, type) < 0)\ndiff -urN --exclude .git linus.diff/git-mktag.c linus.mine/git-mktag.c\n--- linus.diff/git-mktag.c\t2005-05-04 09:54:49.158734608 -0400\n+++ linus.mine/git-mktag.c\t2005-05-04 08:45:04.763859320 -0400\n@@ -31,7 +31,7 @@\n \tif (map) {\n \t\tchar type[100];\n \t\tunsigned long size;\n-\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, &size);\n+\t\tvoid *buffer = unpack_sha1_file(sha1, map, mapsize, type, &size, NULL);\n \n \t\tif (buffer) {\n \t\t\tif (!strcmp(type, expected_type))\ndiff -urN --exclude .git linus.diff/Makefile linus.mine/Makefile\n--- linus.diff/Makefile\t2005-05-04 09:54:49.153735368 -0400\n+++ linus.mine/Makefile\t2005-05-03 16:28:15.000000000 -0400\n@@ -25,7 +25,8 @@\n install: $(PROG) $(SCRIPTS)\n \tinstall $(PROG) $(SCRIPTS) $(HOME)/bin/\n \n-LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o\n+LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o diff-delta.o \\\n+\t patch-delta.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h\n \ndiff -urN --exclude .git linus.diff/patch-delta.c linus.mine/patch-delta.c\n--- linus.diff/patch-delta.c\t1969-12-31 19:00:00.000000000 -0500\n+++ linus.mine/patch-delta.c\t2005-05-04 09:57:53.520707328 -0400\n@@ -0,0 +1,80 @@\n+/*\n+ * patch-delta.c:\n+ * recreate a buffer from a source and the delta produced by diff-delta.c\n+ *\n+ * (C) 2005 Nicolas Pitre \n+ *\n+ * This code is free software; you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License version 2 as\n+ * published by the Free Software Foundation.\n+ */\n+\n+#include \n+#include \n+#include \n+#include \"delta.h\"\n+\n+void *patch_delta(void *src_buf, unsigned long src_size,\n+\t\t void *delta_buf, unsigned long delta_size,\n+\t\t unsigned long *dst_size)\n+{\n+\tconst unsigned char *data, *top;\n+\tunsigned char *dst, *out;\n+\tint size;\n+\n+\t/* the smallest delta size possible is 10 bytes */\n+\tif (delta_size < 10) {\n+\t\treturn NULL;\n+\t}\n+\tdata = delta_buf;\n+\ttop = delta_buf + delta_size;\n+\n+\t/* make sure the orig file size matches what we expect */\n+\tsize = data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);\n+\tdata += 4;\n+\tif (size != src_size) {\n+\t\treturn NULL;\n+\t}\n+\t/* now the result size */\n+\tsize = data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);\n+\tdata += 4;\n+\tdst = malloc(size);\n+\tif (!dst) {\n+\t\treturn NULL;\n+\t}\n+\tout = dst;\n+\twhile (data < top) {\n+\t\tunsigned char cmd = *data++;\n+\t\tif (cmd & 0x80) {\n+\t\t\tunsigned int cp_off = 0, cp_size = 0;\n+\t\t\tif (cmd & 0x01) cp_off = *data++;\n+\t\t\tif (cmd & 0x02) cp_off |= (*data++ << 8);\n+\t\t\tif (cmd & 0x04) cp_off |= (*data++ << 16);\n+\t\t\tif (cmd & 0x08) cp_off |= (*data++ << 24);\n+\t\t\tif (cmd & 0x10) cp_size = *data++;\n+\t\t\tif (cmd & 0x20) cp_size |= (*data++ << 8);\n+\t\t\tif (cp_size == 0) cp_size = 0x10000;\n+\t\t\tmemcpy(out, src_buf + cp_off, cp_size);\n+\t\t\tout += cp_size;\n+\t\t\tif (out > dst + size) {\n+\t\t\t\t*(char *)0 = 0;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tmemcpy(out, data, cmd);\n+\t\t\tout += cmd;\n+\t\t\tdata += cmd;\n+\t\t\tif (out > dst + size) {\n+\t\t\t\t*(char *)0 = 0;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t/* sanity check */\n+\tif (data != top || out - dst != size) {\n+\t\tfree(dst);\n+\t\treturn NULL;\n+\t}\n+\n+\t*dst_size = size;\n+\treturn dst;\n+}\ndiff -urN --exclude .git linus.diff/sha1_file.c linus.mine/sha1_file.c\n--- linus.diff/sha1_file.c\t2005-05-04 09:54:49.165733544 -0400\n+++ linus.mine/sha1_file.c\t2005-05-04 10:42:07.002316808 -0400\n@@ -8,6 +8,7 @@\n */\n #include \n #include \"cache.h\"\n+#include \"delta.h\"\n \n const char *sha1_file_directory = NULL;\n \n@@ -139,39 +140,117 @@\n \treturn map;\n }\n \n-void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size)\n+/*\n+ * looks through buf for the header entry corresponding to sha1. returns\n+ * 0 an entry is found and sets offset to the offset of the packed item\n+ * in the file. The offset is relative to the start of the packed items\n+ * so you have to add in the length of the header before using it\n+ * -1 is returned if the sha1 could not be found\n+ */\n+static int find_packed_header(const unsigned char *sha1, char *buf, unsigned long buf_len, unsigned long *offset)\n+{\n+\tchar *p;\n+\tp = buf;\n+\n+\t*offset = 0;\n+\twhile(p < buf + buf_len) {\n+\t\tunsigned long item_len;\n+\t\tunsigned char item_sha[20];\n+\t\tmemcpy(item_sha, p, 20);\n+\t\tsscanf(p + 20, \"%lu\", &item_len);\n+\t\tp += 20 + strlen(p + 20) + 1;\n+\t\tif (memcmp(item_sha, sha1, 20) == 0)\n+\t\t\treturn 0;\n+\t\t*offset += item_len;\n+\t}\n+\treturn -1;\n+}\n+\n+\n+/*\n+ * uncompresses a data segment without any extra delta/packed processing\n+ */\n+static void * _unpack_sha1_file(z_stream *stream, void *map, \n+ unsigned long mapsize, char *type, \n+\t\t\t\tunsigned long *size)\n {\n \tint ret, bytes;\n-\tz_stream stream;\n \tchar buffer[8192];\n \tchar *buf;\n \n \t/* Get the data stream */\n-\tmemset(&stream, 0, sizeof(stream));\n-\tstream.next_in = map;\n-\tstream.avail_in = mapsize;\n-\tstream.next_out = buffer;\n-\tstream.avail_out = sizeof(buffer);\n-\n-\tinflateInit(&stream);\n-\tret = inflate(&stream, 0);\n-\tif (ret < Z_OK)\n+\tmemset(stream, 0, sizeof(*stream));\n+\tstream->next_in = map;\n+\tstream->avail_in = mapsize;\n+\tstream->next_out = buffer;\n+\tstream->avail_out = sizeof(buffer);\n+\n+\tinflateInit(stream);\n+\tret = inflate(stream, 0);\n+\tif (ret < Z_OK) {\n \t\treturn NULL;\n-\tif (sscanf(buffer, \"%10s %lu\", type, size) != 2)\n+\t}\n+\tif (sscanf(buffer, \"%10s %lu\", type, size) != 2) {\n \t\treturn NULL;\n-\n+\t}\n \tbytes = strlen(buffer) + 1;\n \tbuf = xmalloc(*size);\n \n-\tmemcpy(buf, buffer + bytes, stream.total_out - bytes);\n-\tbytes = stream.total_out - bytes;\n+\tmemcpy(buf, buffer + bytes, stream->total_out - bytes);\n+\tbytes = stream->total_out - bytes;\n \tif (bytes < *size && ret == Z_OK) {\n-\t\tstream.next_out = buf + bytes;\n-\t\tstream.avail_out = *size - bytes;\n-\t\twhile (inflate(&stream, Z_FINISH) == Z_OK)\n+\t\tstream->next_out = buf + bytes;\n+\t\tstream->avail_out = *size - bytes;\n+\t\twhile (inflate(stream, Z_FINISH) == Z_OK)\n \t\t\t/* nothing */;\n \t}\n-\tinflateEnd(&stream);\n+\tinflateEnd(stream);\n+\treturn buf;\n+}\n+\n+void * unpack_sha1_file(const unsigned char *sha1, void *map, \n+\t\t\tunsigned long mapsize, char *type, unsigned long *size, \n+\t\t\tint *chain)\n+{\n+\tz_stream stream;\n+\tchar *buf;\n+\tunsigned long offset;\n+\tunsigned long header_len;\n+\tbuf = _unpack_sha1_file(&stream, map, mapsize, type, size);\n+\tif (!buf)\n+\t\treturn buf;\n+\tif (!strcmp(type, \"delta\")) {\n+\t\tchar *delta_ref;\n+\t\tunsigned long delta_size;\n+\t\tchar *newbuf;\n+\t\tunsigned long newsize;\n+\t\tif (chain)\n+\t\t\t*chain += 1;\n+\t\tdelta_ref = read_sha1_delta_ref(buf, type, &delta_size, chain);\n+\t\tif (!delta_ref) {\n+\t\t\tfree(buf);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tnewbuf = patch_delta(delta_ref, delta_size, buf+20, *size-20, &newsize);\n+\t\tfree(buf);\n+\t\tfree(delta_ref);\n+\t\t*size = newsize;\n+\t\treturn newbuf;\n+\n+\t} else if (!strcmp(type, \"packed\")) {\n+\t\tif (!sha1) {\n+\t\t\tfree(buf);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\theader_len = *size;\n+\t\tif (find_packed_header(sha1, buf, header_len, &offset)) {\n+\t\t\tfree(buf);\n+\t\t\treturn NULL;\n+\t\t}\n+\t\toffset += stream.total_in;\n+\t\tfree(buf);\n+\t\tbuf = unpack_sha1_file(sha1, map+offset, mapsize-offset, type, size, chain);\n+\t}\n \treturn buf;\n }\n \n@@ -182,7 +261,25 @@\n \n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n-\t\tbuf = unpack_sha1_file(map, mapsize, type, size);\n+\t\tbuf = unpack_sha1_file(sha1, map, mapsize, type, size, NULL);\n+\t\tmunmap(map, mapsize);\n+\t\treturn buf;\n+\t}\n+\treturn NULL;\n+}\n+\n+/*\n+ * the same as read_sha1_file except chain is used to count the length\n+ * of any delta chains hit while unpacking\n+ */\n+void * read_sha1_delta_ref(const unsigned char *sha1, char *type, unsigned long *size, int *chain)\n+{\n+\tunsigned long mapsize;\n+\tvoid *map, *buf;\n+\n+\tmap = map_sha1_file(sha1, &mapsize);\n+\tif (map) {\n+\t\tbuf = unpack_sha1_file(sha1, map, mapsize, type, size, chain);\n \t\tmunmap(map, mapsize);\n \t\treturn buf;\n \t}\n@@ -413,3 +510,306 @@\n \t\treturn 1;\n \treturn 0;\n }\n+\n+static void *pack_buffer(void *buf, unsigned long buf_len, char *metadata, int metadata_size, unsigned long *compsize)\n+{\n+\tchar *compressed;\n+\tz_stream stream;\n+\tunsigned long size;\n+\n+\t/* Set it up */\n+\tmemset(&stream, 0, sizeof(stream));\n+\tsize = deflateBound(&stream, buf_len + metadata_size);\n+\tcompressed = xmalloc(size);\n+\n+\t/*\n+\t * ASCII size + nul byte\n+\t */\t\n+\tstream.next_in = metadata;\n+\tstream.avail_in = metadata_size;\n+\tstream.next_out = compressed;\n+\tstream.avail_out = size;\n+\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n+\twhile (deflate(&stream, 0) == Z_OK)\n+\t\t/* nothing */;\n+\n+\tstream.next_in = buf;\n+\tstream.avail_in = buf_len;\n+\t/* Compress it */\n+\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t/* nothing */;\n+\tdeflateEnd(&stream);\n+\tsize = stream.total_out;\n+\t*compsize = size;\n+\treturn compressed;\n+}\n+\n+/*\n+ * generates a delta for buf against refsha1 and returns a compressed buffer\n+ * with the results. NULL is returned on error, or when the delta could\n+ * not be done. This might happen if the delta is larger then either the\n+ * refsha1 or the buffer, or the delta chain is too long.\n+ */\n+static void *pack_delta_buffer(void *buf, unsigned long buf_len, char *metadata, int metadata_size, unsigned long *compsize, unsigned char *sha1, unsigned char *refsha1)\n+{\n+\tchar *compressed;\n+\tchar *refbuffer = NULL;\n+\tchar reftype[20];\n+\tunsigned long refsize = 0;\n+\tchar *delta;\n+\tunsigned long delta_size;\n+\tchar *lmetadata = xmalloc(220);\n+\tunsigned long lmetadata_size;\n+\tint chain_length = 0;\n+\n+\tif (buf_len == 0)\n+\t\treturn NULL;\n+\trefbuffer = read_sha1_delta_ref(refsha1, reftype, &refsize, &chain_length);\n+\n+\tif (chain_length > 16) {\n+\t\tfree(refbuffer);\n+\t\treturn NULL;\n+\t}\n+\t/* note, we could just continue without the delta here */\n+\tif (!refbuffer) {\n+\t\tfree(refbuffer);\n+\t\treturn NULL;\n+\t}\n+\tdelta = diff_delta(refbuffer, refsize, buf, buf_len, &delta_size);\n+\tfree(refbuffer);\n+\tif (!delta)\n+\t\treturn NULL;\n+\tif (delta_size > refsize || delta_size > buf_len) {\n+\t\tfree(delta);\n+\t\treturn NULL;\n+\t}\n+\tif (delta_size < 10) {\n+\t\tfree(delta);\n+\t\treturn NULL;\n+\t}\n+\tlmetadata_size = 1 + sprintf(lmetadata, \"%s %lu\",\"delta\",delta_size+20);\n+\tmemcpy(lmetadata + lmetadata_size, refsha1, 20);\n+\tlmetadata_size += 20;\n+\tcompressed = pack_buffer(delta, delta_size, lmetadata, lmetadata_size, compsize);\n+\tfree(lmetadata);\n+\tfree(delta);\n+\treturn compressed;\n+}\n+\n+/*\n+ * returns a newly malloc'd packed item with a compressed buffer for buf. \n+ * If refsha1 is non-null, attempts a delta against it. The sha1 of buf \n+ * is returned via returnsha1.\n+ */\n+int pack_sha1_buffer(void *buf, unsigned long buf_len, char *type,\n+\t\t unsigned char *returnsha1,\n+\t\t unsigned char *refsha1,\n+\t\t struct packed_item **packed_item)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tstruct stat st;\n+\tchar *compressed = NULL;\n+\tunsigned long size;\n+\tstruct packed_item *item;\n+\tchar *metadata = xmalloc(200);\n+\tint metadata_size;\n+\n+\t*packed_item = NULL;\n+\n+\tmetadata_size = 1 + sprintf(metadata, \"%s %lu\", type, buf_len);\n+\n+\t/* Sha1.. */\n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, metadata, metadata_size);\n+\tSHA1_Update(&c, buf, buf_len);\n+\tSHA1_Final(sha1, &c);\n+\n+\tif (returnsha1)\n+\t\tmemcpy(returnsha1, sha1, 20);\n+\n+\tfilename = sha1_file_name(sha1);\n+\tif (stat(filename, &st) == 0)\n+\t\tgoto out;\n+\n+\t\n+\tif (refsha1) {\n+\t\tcompressed = pack_delta_buffer(buf, buf_len, metadata, \n+\t\t metadata_size, &size, sha1, \n+\t\t\t\t\t refsha1);\n+\t}\n+\tif (!compressed) {\n+\t\tcompressed = pack_buffer(buf, buf_len, metadata, \n+\t\t metadata_size, &size);\n+\t}\n+\tfree(metadata);\n+\tif (!compressed) {\n+\t\treturn -1;\n+\t}\n+\titem = xmalloc(sizeof(struct packed_item));\n+\tmemcpy(item->sha1, sha1, 20);\n+\titem->len = size;\n+\titem->next = NULL;\n+\titem->data = compressed;\n+\t*packed_item = item;\n+out:\n+\treturn 0;\n+}\n+\n+static char *create_packed_header(struct packed_item *head, unsigned long *size)\n+{\n+\tchar *metadata = NULL;\n+\tint metadata_size = 0;\n+\t*size = 0;\n+\tint entry_size = 0;\n+\n+\twhile(head) {\n+\t\tchar *p;\n+\t\tmetadata = realloc(metadata, metadata_size + 220);\n+\t\tif (!metadata)\n+\t\t\treturn NULL;\n+\t\tp = metadata+metadata_size;\n+\t\tmemcpy(p, head->sha1, 20);\n+\t\tp += 20;\n+\t\tentry_size = 1 + sprintf(p, \"%lu\", head->len);\n+\t\tmetadata_size += entry_size + 20;\n+\t\thead = head->next;\n+\t}\n+\t*size = metadata_size;\n+\treturn metadata;\n+}\n+\n+#define WRITE_BUFFER_SIZE 8192\n+static char write_buffer[WRITE_BUFFER_SIZE];\n+static unsigned long write_buffer_len;\n+\n+static int c_write(int fd, void *data, unsigned int len)\n+{\n+\twhile (len) {\n+\t\tunsigned int buffered = write_buffer_len;\n+\t\tunsigned int partial = WRITE_BUFFER_SIZE - buffered;\n+\t\tif (partial > len)\n+\t\t\tpartial = len;\n+\t\tmemcpy(write_buffer + buffered, data, partial);\n+\t\tbuffered += partial;\n+\t\tif (buffered == WRITE_BUFFER_SIZE) {\n+\t\t\tif (write(fd, write_buffer, WRITE_BUFFER_SIZE) != WRITE_BUFFER_SIZE)\n+\t\t\t\treturn -1;\n+\t\t\tbuffered = 0;\n+\t\t}\n+\t\twrite_buffer_len = buffered;\n+\t\tlen -= partial;\n+\t\tdata += partial;\n+ \t}\n+ \treturn 0;\n+}\n+\n+static int c_flush(int fd)\n+{\n+\tif (write_buffer_len) {\n+\t\tint left = write_buffer_len;\n+\t\tif (write(fd, write_buffer, left) != left)\n+\t\t\treturn -1;\n+\t\twrite_buffer_len = 0;\n+\t}\n+\treturn 0;\n+}\n+\n+/*\n+ * creates a new packed file for all the items in head. hard links are\n+ * made from the sha1 of all the items back to the packd file, and then\n+ * the packed file is unlinked.\n+ */\n+int write_packed_buffer(struct packed_item *head)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tchar *metadata = xmalloc(200);\n+\tchar *header;\n+\tint metadata_size;\n+\tint fd;\n+\tint ret = 0;\n+\tunsigned long header_len;\n+\tstruct packed_item *item;\n+\tchar *compressed;\n+\tz_stream stream;\n+\tunsigned long size;\n+\n+\theader = create_packed_header(head, &header_len);\n+\tmetadata_size = 1+sprintf(metadata, \"packed %lu\", header_len);\n+\t/* \n+\t * the header contains the sha1 of each item, so we only sha1 the\n+\t * header\n+\t */ \n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, metadata, metadata_size);\n+\tSHA1_Update(&c, header, header_len);\n+\tSHA1_Final(sha1, &c);\n+\n+\tfilename = strdup(sha1_file_name(sha1));\n+\tfd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);\n+\tif (fd < 0) {\n+\t\t/* add collision check! */\n+\t\tif (errno != EEXIST) {\n+\t\t\tret = -errno;\n+\t\t}\n+\t\tgoto out_nofile;\n+\t}\n+ /* compress just the header info */\n+ memset(&stream, 0, sizeof(stream));\n+ deflateInit(&stream, Z_BEST_COMPRESSION);\n+\tsize = deflateBound(&stream, header_len + metadata_size);\n+ compressed = xmalloc(size);\n+\n+ stream.next_in = metadata;\n+ stream.avail_in = metadata_size;\n+ stream.next_out = compressed;\n+ stream.avail_out = size;\n+ while (deflate(&stream, 0) == Z_OK)\n+ /* nothing */;\n+ stream.next_in = header;\n+ stream.avail_in = header_len;\n+ while (deflate(&stream, Z_FINISH) == Z_OK)\n+ /* nothing */;\n+ deflateEnd(&stream);\n+ size = stream.total_out;\n+\n+\tc_write(fd, compressed, size);\n+\tfree(compressed);\n+\n+\titem = head;\n+\twhile(item) {\n+\t\tif (c_write(fd, item->data, item->len)) {\n+\t\t\tret = -EIO;\n+\t\t\tgoto out;\n+\t\t}\n+\t\titem = item->next;\n+\t}\n+\tif (c_flush(fd)) {\n+\t\tret = -EIO;\n+\t\tgoto out;\n+\t}\n+\titem = head;\n+\twhile(item) {\n+\t\tchar *item_file;\n+\t\tstruct packed_item *next = item->next;\n+\t\titem_file = sha1_file_name(item->sha1);\n+\t\tif (link(filename, item_file) && errno != EEXIST) {\n+\t\t\tret = -errno;\n+\t\t\tbreak;\n+\t\t}\n+\t\tfree(item->data);\n+\t\tfree(item);\n+\t\titem = next;\n+\t}\n+\tunlink(filename);\n+out:\n+\tclose(fd);\n+out_nofile:\n+\tfree(header);\n+\tfree(metadata);\n+\tfree(filename);\n+\treturn ret;\n+}\ndiff -urN --exclude .git linus.diff/update-cache.c linus.mine/update-cache.c\n--- linus.diff/update-cache.c\t2005-05-04 09:54:49.167733240 -0400\n+++ linus.mine/update-cache.c\t2005-05-02 20:51:32.000000000 -0400\n@@ -31,55 +31,39 @@\n \treturn (unsigned long)ptr > (unsigned long)-1000L;\n }\n \n-static int index_fd(unsigned char *sha1, int fd, struct stat *st)\n+static int index_fd(unsigned char *sha1, unsigned char *refsha1, int fd, struct stat *st, struct packed_item **head, struct packed_item **tail, unsigned long *packed_size, int *packed_nr)\n {\n-\tz_stream stream;\n \tunsigned long size = st->st_size;\n-\tint max_out_bytes = size + 200;\n-\tvoid *out = xmalloc(max_out_bytes);\n-\tvoid *metadata = xmalloc(200);\n-\tint metadata_size;\n \tvoid *in;\n-\tSHA_CTX c;\n+\tint ret;\n+\tstruct packed_item *new_item;\n \n \tin = \"\";\n \tif (size)\n \t\tin = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n \tclose(fd);\n-\tif (!out || (int)(long)in == -1)\n+\tif ((int)(long)in == -1) {\n \t\treturn -1;\n-\n-\tmetadata_size = 1+sprintf(metadata, \"blob %lu\", size);\n-\n-\tSHA1_Init(&c);\n-\tSHA1_Update(&c, metadata, metadata_size);\n-\tSHA1_Update(&c, in, size);\n-\tSHA1_Final(sha1, &c);\n-\n-\tmemset(&stream, 0, sizeof(stream));\n-\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n-\n-\t/*\n-\t * ASCII size + nul byte\n-\t */\t\n-\tstream.next_in = metadata;\n-\tstream.avail_in = metadata_size;\n-\tstream.next_out = out;\n-\tstream.avail_out = max_out_bytes;\n-\twhile (deflate(&stream, 0) == Z_OK)\n-\t\t/* nothing */;\n-\n-\t/*\n-\t * File content\n-\t */\n-\tstream.next_in = in;\n-\tstream.avail_in = size;\n-\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n-\t\t/*nothing */;\n-\n-\tdeflateEnd(&stream);\n-\t\n-\treturn write_sha1_buffer(sha1, out, stream.total_out);\n+\t}\n+\tret = pack_sha1_buffer(in, size, \"blob\", sha1, refsha1, &new_item);\n+\tif (new_item) {\n+\t\tif (*tail)\n+\t\t\t(*tail)->next = new_item;\n+\t\t*tail = new_item;\n+\t\tif (!*head)\n+\t\t\t*head = new_item;\n+\t\t*packed_size += new_item->len;\n+\t\t*packed_nr++;\n+\t\tif (*packed_size > (512 * 1024) || *packed_nr > 1024) {\n+\t\t\twrite_packed_buffer(*head);\n+\t\t\t*head = NULL;\n+\t\t\t*tail = NULL;\n+\t\t\t*packed_size = 0;\n+\t\t\t*packed_nr = 0;\n+\t\t}\n+\t}\n+\tmunmap(in, size);\n+\treturn ret;\n }\n \n /*\n@@ -102,12 +86,14 @@\n \tce->ce_size = htonl(st->st_size);\n }\n \n-static int add_file_to_cache(char *path)\n+static int add_file_to_cache(char *path, struct packed_item **packed_head, struct packed_item **packed_tail, unsigned long *packed_size, int *packed_nr)\n {\n \tint size, namelen;\n \tstruct cache_entry *ce;\n \tstruct stat st;\n \tint fd;\n+\tint pos;\n+\tunsigned char *refsha1 = NULL;\n \n \tfd = open(path, O_RDONLY);\n \tif (fd < 0) {\n@@ -129,8 +115,12 @@\n \tfill_stat_cache_info(ce, &st);\n \tce->ce_mode = create_ce_mode(st.st_mode);\n \tce->ce_flags = htons(namelen);\n+\tpos = cache_name_pos(ce->name, namelen);\n+\tif (pos >= 0)\n+\t\trefsha1 = active_cache[pos]->sha1;\n \n-\tif (index_fd(ce->sha1, fd, &st) < 0)\n+\tif (index_fd(ce->sha1, refsha1, fd, &st, packed_head, \n+\t\t packed_tail, packed_size, packed_nr) < 0)\n \t\treturn -1;\n \n \treturn add_cache_entry(ce, allow_add);\n@@ -311,6 +301,10 @@\n \tint allow_options = 1;\n \tstatic char lockfile[MAXPATHLEN+1];\n \tconst char *indexfile = get_index_file();\n+\tstruct packed_item *packed_head = NULL;\n+\tstruct packed_item *packed_tail = NULL;\n+\tunsigned long packed_size = 0;\n+\tint packed_nr = 0;\n \n \tsnprintf(lockfile, sizeof(lockfile), \"%s.lock\", indexfile);\n \n@@ -362,8 +356,13 @@\n \t\t\tfprintf(stderr, \"Ignoring path %s\\n\", argv[i]);\n \t\t\tcontinue;\n \t\t}\n-\t\tif (add_file_to_cache(path))\n+\t\tif (add_file_to_cache(path, &packed_head, &packed_tail, &packed_size, &packed_nr))\n \t\t\tdie(\"Unable to add %s to database\", path);\n+\n+\t}\n+\tif (packed_head) {\n+\t\tif (write_packed_buffer(packed_head))\n+\t\t\tdie(\"write packed buffer failed\");\n \t}\n \tif (write_cache(newfd, active_cache, active_nr) || rename(lockfile, indexfile))\n \t\tdie(\"Unable to write new cachefile\");\ndiff -urN --exclude .git linus.diff/write-tree.c linus.mine/write-tree.c\n--- linus.diff/write-tree.c\t2005-05-04 09:54:49.167733240 -0400\n+++ linus.mine/write-tree.c\t2005-05-02 20:51:32.000000000 -0400\n@@ -5,24 +5,13 @@\n */\n #include \"cache.h\"\n \n-static int check_valid_sha1(unsigned char *sha1)\n-{\n-\tchar *filename = sha1_file_name(sha1);\n-\tint ret;\n-\n-\t/* If we were anal, we'd check that the sha1 of the contents actually matches */\n-\tret = access(filename, R_OK);\n-\tif (ret)\n-\t\tperror(filename);\n-\treturn ret;\n-}\n-\n-static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n+static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1, struct packed_item **head)\n {\n \tunsigned char subdir_sha1[20];\n \tunsigned long size, offset;\n \tchar *buffer;\n \tint nr;\n+\tstruct packed_item *item;\n \n \t/* Guess at some random initial size */\n \tsize = 8192;\n@@ -50,7 +39,7 @@\n \t\tif (dirname) {\n \t\t\tint subdir_written;\n \n-\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);\n+\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1, head);\n \t\t\tnr += subdir_written;\n \n \t\t\t/* Now we need to write out the directory entry into this tree.. */\n@@ -62,9 +51,6 @@\n \t\t\tsha1 = subdir_sha1;\n \t\t}\n \n-\t\tif (check_valid_sha1(sha1) < 0)\n-\t\t\texit(1);\n-\n \t\tentrylen = pathlen - baselen;\n \t\tif (offset + entrylen + 100 > size) {\n \t\t\tsize = alloc_nr(offset + entrylen + 100);\n@@ -77,7 +63,11 @@\n \t\tnr++;\n \t} while (nr < maxentries);\n \n-\twrite_sha1_file(buffer, offset, \"tree\", returnsha1);\n+\tpack_sha1_buffer(buffer, offset, \"tree\", returnsha1, NULL, &item);\n+\tif (item) {\n+\t\titem->next = *head;\n+\t\t*head = item;\n+\t}\n \tfree(buffer);\n \treturn nr;\n }\n@@ -87,6 +77,7 @@\n \tint i, unmerged;\n \tint entries = read_cache();\n \tunsigned char sha1[20];\n+\tstruct packed_item *head = NULL;\n \n \tif (entries <= 0)\n \t\tdie(\"write-tree: no cache contents to write\");\n@@ -107,8 +98,12 @@\n \t\tdie(\"write-tree: not able to write tree\");\n \n \t/* Ok, write it out */\n-\tif (write_tree(active_cache, entries, \"\", 0, sha1) != entries)\n+\tif (write_tree(active_cache, entries, \"\", 0, sha1, &head) != entries)\n \t\tdie(\"write-tree: internal error\");\n+\tif (head) {\n+\t\tif (write_packed_buffer(head))\n+\t\t\tdie(\"write_packed_buffer error\");\n+\t}\n \tprintf(\"%s\\n\", sha1_to_hex(sha1));\n \treturn 0;\n }\n"},{"id":"2579","messageId":"Pine.LNX.4.61.0505041202270.22203@cag.csail.mit.edu","threadId":"453","inReplyTo":"200505041156.19499.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-05-04T16:12:38Z","receivedAt":"2005-05-04T16:12:38Z","isPatch":true,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Wed, 4 May 2005, Chris Mason wrote:\n\n> 3) create a git-pack tool that can pack/unpack existing changesets,trees and\n> files, optionally adding/removing deltas.\n\nA 'git-pull' tool might be more use. I can imagine Linus maintaining his \nlocal tree uncompressed, but the 'kernel.org' tree set up to \ngit-pull-delta from him every hour or whatever, so that the \nnetwork-accessible version is always network-efficient. 'git-pack'\nwould then simplify to a git-pull-delta from an existing local repository.\n\nIdeally, you'd also be able to git-pull from a network packed repository \nand (transparently) unpack and undelta-fy the pulled files as they're \nadded to your local repo. This would keep Linus from accidentally getting \npacked files in his tree when he pulled from a maintainer's \npacked/delta-ed network-accessible tree.\n\nI'd also be interested in seeing the speed/space numbers for some other \ndelta chain lengths between 1 and 16. Maybe some intermediate point is \noptimal. [Also, limiting delta chains to a certain number of other \n*packed* objects -- instead of just 'objects' -- might be an improvement. \nRight now you're packing entire commits together, right? Maybe defining a \ndelta chain as 'N other commits max' might improve i/o performance, as \nyou'd just have to keep N other unpacked files around, instead of an \narbitrary number.]\n --scott\n\nSSBN 743 BOND ESGAIN SUMAC ZPSECANT MHCHAOS Castro Flintlock payment \nanthrax SCRANTON PLO MKNAOMI DNC AVBLIMP RUFUS Secretary AK-47 Noriega\n ( http://cscott.net/ )\n"},{"id":"2584","messageId":"200505041344.51637.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.61.0505041202270.22203@cag.csail.mit.edu","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-04T17:44:50Z","receivedAt":"2005-05-04T17:44:50Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Wednesday 04 May 2005 12:12, C. Scott Ananian wrote:\n> On Wed, 4 May 2005, Chris Mason wrote:\n> > 3) create a git-pack tool that can pack/unpack existing changesets,trees\n> > and files, optionally adding/removing deltas.\n>\n> A 'git-pull' tool might be more use. I can imagine Linus maintaining his\n> local tree uncompressed, but the 'kernel.org' tree set up to\n> git-pull-delta from him every hour or whatever, so that the\n> network-accessible version is always network-efficient. 'git-pack'\n> would then simplify to a git-pull-delta from an existing local repository.\n\nI had pictured the opposite, after the regular pull you would run git-pack to \nredelta/pack things to your local settings. There's a ton of things to try \nin git pull for delta transmission, and I'd rather keep it separate from the \nlocal repository packing for now.\n\nLater on if both tools are working properly we could look at combining them.\n\n>\n> Ideally, you'd also be able to git-pull from a network packed repository\n> and (transparently) unpack and undelta-fy the pulled files as they're\n> added to your local repo. This would keep Linus from accidentally getting\n> packed files in his tree when he pulled from a maintainer's\n> packed/delta-ed network-accessible tree.\n>\nYes, if Linus does take the patches, it's really important for people to be \nable to easily continue without deltas/packing if they want.\n\n> I'd also be interested in seeing the speed/space numbers for some other\n> delta chain lengths between 1 and 16. Maybe some intermediate point is\n> optimal. [Also, limiting delta chains to a certain number of other\n> *packed* objects -- instead of just 'objects' -- might be an improvement.\n> Right now you're packing entire commits together, right? Maybe defining a\n> delta chain as 'N other commits max' might improve i/o performance, as\n> you'd just have to keep N other unpacked files around, instead of an\n> arbitrary number.]\n\nIt's easy to do additional runs, but I would rather do this kind of fine \ntuning with the git-pack tool. That way we could experiment with packing \nmultiple commits into a single file, deltas on tree objects, or even \ncombining commits based on which files tye modify.\n\n-chris\n"},{"id":"2589","messageId":"DE5D04E8-B182-45B1-AB9A-6AA178005FFD@adacore.com","threadId":"453","inReplyTo":"200505041156.19499.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2005-05-04T21:47:27Z","receivedAt":"2005-05-04T21:47:27Z","isPatch":true,"sender":{"key":"bosch@adacore.com","avatar":null},"body":" From your tests it would seem that the zdelta version is the only one\nto provide a uniform improvement over plain git. As it also seems the\nsimplest approach, I wonder why the consensus is that using xdiff\nwould be better?\n\n -Geert\n\nOn May 4, 2005, at 11:56, Chris Mason wrote:\n> I did two additional runs, first where I fixed the delta chain \n> length at 1 as\n> in the zdelta patch. In this mode, if it tried to diff against a \n> delta it\n> would find the delta's parent and diff against that instead. Even \n> though\n> zdelta had the same speeds for applying patches as xdiff(1), zdelta \n> used\n> significantly more cpu (53m vs 40m).\n>\n> The next run was with the patch I've attached below, it allows \n> chains up to 16\n> deltas in length.\n> git zdelta xdiff \n> (1) xdiff(16)\n> apply 150m 117m 117m 104m\n> checkout 4m30s 3m41 4m43s 7m11s\n> checkout (hot) 56s 12s 14s 16s\n> space usage 2.5G 1G 1.2G 800m\n>\n\n"},{"id":"2590","messageId":"Pine.LNX.4.58.0505041501220.2328@ppc970.osdl.org","threadId":"453","inReplyTo":"200505041344.51637.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-04T22:03:39Z","receivedAt":"2005-05-04T22:03:39Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 4 May 2005, Chris Mason wrote:\n>\n> Yes, if Linus does take the patches, it's really important for people to be \n> able to easily continue without deltas/packing if they want.\n\nI'll happily take the patch and just not use the delta packing myself (at \nleast until I trust it). But before I take the patch I want to make sure \nthat people agree on it, and that it's been tested well enough that it \nwon't cause people to corrupt their repositories.\n\nFor example, I do _not_ want to be in the situation SVN is in, where if\nyou corrupt your SVN database, you're totally screwed. There's a real\nadvantage to not having fancy data structures or complicated consistency\nrules.\n\n\t\t\tLinus\n"},{"id":"2592","messageId":"200505041834.19053.mason@suse.com","threadId":"453","inReplyTo":"DE5D04E8-B182-45B1-AB9A-6AA178005FFD@adacore.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-04T22:34:18Z","receivedAt":"2005-05-04T22:34:18Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Wednesday 04 May 2005 17:47, Geert Bosch wrote:\n> From your tests it would seem that the zdelta version is the only one\n> to provide a uniform improvement over plain git. As it also seems the\n> simplest approach, I wonder why the consensus is that using xdiff\n> would be better?\n\nzdelta seems to be a research project. It does compress better than the xdiff \nlib, but the speed improvements against xdiff(1) are probably because the \nresulting tree is smaller. I favor the xdiff code because it's so much \nsmaller, and seems easier for us to maintain.\n\nFor performance, there's still quite a bit of tuning that can be done in terms \nof when and how we delta.\n\n-chris\n"},{"id":"2594","messageId":"200505041843.53469.mason@suse.com","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505041501220.2328@ppc970.osdl.org","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-04T22:43:52Z","receivedAt":"2005-05-04T22:43:52Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Wednesday 04 May 2005 18:03, Linus Torvalds wrote:\n> On Wed, 4 May 2005, Chris Mason wrote:\n> > Yes, if Linus does take the patches, it's really important for people to\n> > be able to easily continue without deltas/packing if they want.\n>\n> I'll happily take the patch and just not use the delta packing myself (at\n> least until I trust it). But before I take the patch I want to make sure\n> that people agree on it, and that it's been tested well enough that it\n> won't cause people to corrupt their repositories.\n>\n> For example, I do _not_ want to be in the situation SVN is in, where if\n> you corrupt your SVN database, you're totally screwed. There's a real\n> advantage to not having fancy data structures or complicated consistency\n> rules.\n\nFair enough ;) I'm pretty flexible about most of the details, so I'm hoping \nit won't be hard to get a consensus. The current code might be a little too \nsimple in format (in the packed and delta headers), but so far it seems \nsufficient for git's needs.\n\nThe git-pack utility would probably be the best way to get other people to \nexperiment and make suggestions, so I'll start there.\n\n-chris\n"},{"id":"2608","messageId":"Pine.LNX.4.62.0505042259150.14033@localhost.localdomain","threadId":"453","inReplyTo":"200505041834.19053.mason@suse.com","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-05T03:10:47Z","receivedAt":"2005-05-05T03:10:47Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 4 May 2005, Chris Mason wrote:\n\n> On Wednesday 04 May 2005 17:47, Geert Bosch wrote:\n> > From your tests it would seem that the zdelta version is the only one\n> > to provide a uniform improvement over plain git. As it also seems the\n> > simplest approach, I wonder why the consensus is that using xdiff\n> > would be better?\n> \n> zdelta seems to be a research project. It does compress better than the xdiff \n> lib, but the speed improvements against xdiff(1) are probably because the \n> resulting tree is smaller. I favor the xdiff code because it's so much \n> smaller, and seems easier for us to maintain.\n\nYep. And compression can be improved without changing de decompressor \nsince the decompressor is only a replay of what the compressor found to \nbe redundent. That redundency searching can probably be improved wrt to \nthe current code. And FRankly considering about 300 lines of code to \ncreate a delta and 60 lines to expand it is hard to beat maintenance \nwise.\n\n> For performance, there's still quite a bit of tuning that can be done in terms \n> of when and how we delta.\n\nIndeed.\n\n\nNicolas\n"},{"id":"2609","messageId":"Pine.LNX.4.62.0505042311550.14033@localhost.localdomain","threadId":"453","inReplyTo":"Pine.LNX.4.58.0505041501220.2328@ppc970.osdl.org","subject":"Re: [PATCH] add the ability to create and retrieve delta objects","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-05T03:25:05Z","receivedAt":"2005-05-05T03:25:05Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 4 May 2005, Linus Torvalds wrote:\n\n> I'll happily take the patch and just not use the delta packing myself (at \n> least until I trust it). But before I take the patch I want to make sure \n> that people agree on it, and that it's been tested well enough that it \n> won't cause people to corrupt their repositories.\n\nTo that effect I'm adding knowledge of delta objects to fsck-cache, to \nverify lists of deltas are all reachable and that they all expand to the \nexpected data. This way it would be a good test to completely deltafy a \nwhole repository, run fsck-cache to ensure everything is fine, and \nundeltafy it all to see if things are still sane.\n\n> For example, I do _not_ want to be in the situation SVN is in, where if\n> you corrupt your SVN database, you're totally screwed. There's a real\n> advantage to not having fancy data structures or complicated consistency\n> rules.\n\nWith deltas it is still a bit more risky by design since many objects \nend up depending on a single one. You loose that top object and it's \nall the delta chain that's gone. But having the choice to use them or \nnot is what makes the whole system flexible and suited to anyone's \nbalance between robustness vs disk space. Converting back and forth is \ncertainly not a problem with the git model.\n\nAnd if you deltafy things such that the objects in your head tree are \nalways top of delta chain then you're not badly affected if some \nintermediate delta objects are corrupted since they are part of old \ntrees only.\n\n\nNicolas\n"}]}