{"thread":{"id":"577","subject":"[PATCH] improved delta support for git","startedAt":"2005-05-12T03:51:07Z","lastAt":"2005-05-18T19:32:06Z","messageCount":17,"participants":["Nicolas Pitre","Junio C Hamano","Chris Mason","Jon Seymour","Thomas Glanzmann","Dan Holmsand","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"3109","messageId":"Pine.LNX.4.62.0505112309480.5426@localhost.localdomain","threadId":"577","inReplyTo":null,"subject":"[PATCH] improved delta support for git","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-12T03:51:07Z","receivedAt":"2005-05-12T03:51:07Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nOK, here's some improved support for delta objects in a git repository. \nThis patch adds the ability to create and restore delta objects with the \ngit-mkdelta command. A list of objects is provided and the \ncorresponding delta chain is created. The maximum depth of a delta \nchain can be specified with the -d argument. If a max depth of 0 is \nprovided then all given objects are undeltafied and replaced by their \noriginal version. With the -v argument a lot of lovely details are \nprinted out.\n\nAlso included is a script to deltafy an entire repository. Simply \nexecute git-deltafy-script to create deltas of objects corresponding to \nsuccessive previous versions of every files. Running \n'git-deltafy-script -d 0' will revert everything to non deltafied form.\n\nI've yet to add suport to fsck-cache to understand delta objects. It is \nadvised to undeltafy your repository before running it otherwise you'll \nsee lots of reported errors. Once undeltafied you should have good \noutput from fsck-cache again.\n\nPlease backup your repository before playing with this for now... just \nin case.\n\nIf you happen to have the whole kernel history in your repository I'd be \ninterested to know what the space figure is and how it performs. So far \nI tested a tar of the .git/objects directory from git's git repository. \nThis is to estimate the real data size without the filesystem block \nround up. The undeltafied repository created a 1708kb tar file while the \ndeltafied repository created a 1173kb tar file. The chunking storage \ncode should be considered for real life usage of course.\n\nThere are probably things to experiment in order to save space further, \nsuch as deltafying tree objects, and in the context of Linux, deltafying \nfiles with lots of similitudes between content in diferent include/asm-* \nsubdirectories.\n\nSigned-off-by: Nicolas Pitre \n\nIndex: git/diff-delta.c\n===================================================================\n--- /dev/null\n+++ git/diff-delta.c\n@@ -0,0 +1,330 @@\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 (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))\n+\t\treturn NULL;\n+\t\n+\toutpos = 0;\n+\toutsize = 8192;\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+\t/* store reference buffer size */\n+\torig = out + outpos++;\n+\t*orig = i = 0;\n+\tdo {\n+\t\tif (from_size & 0xff) {\n+\t\t\t*orig |= (1 << i);\n+\t\t\tout[outpos++] = from_size;\n+\t\t}\n+\t\ti++;\n+\t\tfrom_size >>= 8;\n+\t} while (from_size);\n+\n+\t/* store target buffer size */\n+\torig = out + outpos++;\n+\t*orig = i = 0;\n+\tdo {\n+\t\tif (to_size & 0xff) {\n+\t\t\t*orig |= (1 << i);\n+\t\t\tout[outpos++] = to_size;\n+\t\t}\n+\t\ti++;\n+\t\tto_size >>= 8;\n+\t} while (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+}\nIndex: git/delta.h\n===================================================================\n--- /dev/null\n+++ git/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);\nIndex: git/Makefile\n===================================================================\n--- git.orig/Makefile\n+++ git/Makefile\n@@ -29,7 +29,7 @@\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 @@\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 \nIndex: git/patch-delta.c\n===================================================================\n--- /dev/null\n+++ git/patch-delta.c\n@@ -0,0 +1,88 @@\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_buf, *out, cmd;\n+\tunsigned long size;\n+\tint i;\n+\n+\t/* the smallest delta size possible is 6 bytes */\n+\tif (delta_size < 6)\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 = i = 0;\n+\tcmd = *data++;\n+\twhile (cmd) {\n+\t\tif (cmd & 1)\n+\t\t\tsize |= *data++ << i;\n+\t\ti += 8;\n+\t\tcmd >>= 1;\n+\t}\n+\tif (size != src_size)\n+\t\treturn NULL;\n+\n+\t/* now the result size */\n+\tsize = i = 0;\n+\tcmd = *data++;\n+\twhile (cmd) {\n+\t\tif (cmd & 1)\n+\t\t\tsize |= *data++ << i;\n+\t\ti += 8;\n+\t\tcmd >>= 1;\n+\t}\n+\tdst_buf = malloc(size);\n+\tif (!dst_buf)\n+\t\treturn NULL;\n+\n+\tout = dst_buf;\n+\twhile (data < top) {\n+\t\tcmd = *data++;\n+\t\tif (cmd & 0x80) {\n+\t\t\tunsigned long cp_off = 0, cp_size = 0;\n+\t\t\tconst unsigned char *buf;\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\tbuf = (cmd & 0x40) ? dst_buf : src_buf;\n+\t\t\tmemcpy(out, 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_buf != size) {\n+\t\tfree(dst_buf);\n+\t\treturn NULL;\n+\t}\n+\n+\t*dst_size = size;\n+\treturn dst_buf;\n+}\nIndex: git/test-delta.c\n===================================================================\n--- /dev/null\n+++ git/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+}\nIndex: git/sha1_file.c\n===================================================================\n--- git.orig/sha1_file.c\n+++ git/sha1_file.c\n@@ -8,6 +8,7 @@\n */\n #include \n #include \"cache.h\"\n+#include \"delta.h\"\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -224,6 +225,19 @@\n \tif (map) {\n \t\tbuf = unpack_sha1_file(map, mapsize, type, size);\n \t\tmunmap(map, mapsize);\n+\t\tif (buf && !strcmp(type, \"delta\")) {\n+\t\t\tvoid *ref = NULL, *delta = buf;\n+\t\t\tunsigned long ref_size, delta_size = *size;\n+\t\t\tbuf = NULL;\n+\t\t\tif (delta_size > 20)\n+\t\t\t\tref = read_sha1_file(delta, type, &ref_size);\n+\t\t\tif (ref)\n+\t\t\t\tbuf = patch_delta(ref, ref_size,\n+\t\t\t\t\t\t delta+20, delta_size-20, \n+\t\t\t\t\t\t size);\n+\t\t\tfree(delta);\n+\t\t\tfree(ref);\n+\t\t}\n \t\treturn buf;\n \t}\n \treturn NULL;\nIndex: git/Makefile\n===================================================================\n--- git.orig/Makefile\n+++ git/Makefile\n@@ -13,7 +13,7 @@\n AR=ar\n \n SCRIPTS=git-apply-patch-script git-merge-one-file-script git-prune-script \\\n-\tgit-pull-script git-tag-script git-resolve-script\n+\tgit-pull-script git-tag-script git-resolve-script git-deltafy-script\n \n PROG= git-update-cache git-diff-files git-init-db git-write-tree \\\n \tgit-read-tree git-commit-tree git-cat-file git-fsck-cache \\\n@@ -21,7 +21,8 @@\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 git-write-blob\n+\tgit-diff-tree-helper git-tar-tree git-local-pull git-write-blob \\\n+\tgit-mkdelta\n \n all: $(PROG)\n \n@@ -95,6 +96,7 @@\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\nIndex: git/mkdelta.c\n===================================================================\n--- /dev/null\n+++ git/mkdelta.c\n@@ -0,0 +1,283 @@\n+/*\n+ * Deltafication of a GIT database.\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 \"cache.h\"\n+#include \"delta.h\"\n+\n+static int replace_object(char *buf, unsigned long len, unsigned char *sha1,\n+\t\t\t char *hdr, int hdrlen)\n+{\n+\tchar tmpfile[PATH_MAX];\n+\tint size;\n+\tchar *compressed;\n+\tz_stream stream;\n+\tint fd;\n+\n+\tsnprintf(tmpfile, sizeof(tmpfile), \"%s/obj_XXXXXX\", get_object_directory());\n+\tfd = mkstemp(tmpfile);\n+\tif (fd < 0)\n+\t\treturn error(\"%s: %s\\n\", tmpfile, strerror(errno));\n+\t\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\tperror(\"unable to write file\");\n+\t\tclose(fd);\n+\t\tunlink(tmpfile);\n+\t\treturn -1;\n+\t}\n+\tfchmod(fd, 0444);\n+\tclose(fd);\n+\n+\tif (rename(tmpfile, sha1_file_name(sha1))) {\n+\t\tperror(\"unable to replace original object\");\n+\t\tunlink(tmpfile);\n+\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int write_delta_file(char *buf, unsigned long len,\n+\t\t\t unsigned char *sha1_ref, unsigned char *sha1_trg)\n+{\n+\tchar hdr[50];\n+\tint hdrlen;\n+\n+\t/* Generate the header + sha1 of reference for delta */\n+\thdrlen = sprintf(hdr, \"delta %lu\", len+20)+1;\n+\tmemcpy(hdr + hdrlen, sha1_ref, 20);\n+\thdrlen += 20;\n+\n+\treturn replace_object(buf, len, sha1_trg, hdr, hdrlen);\n+}\n+\n+static int replace_sha1_file(char *buf, unsigned long len,\n+\t\t\t char *type, unsigned char *sha1)\n+{\n+\tchar hdr[50];\n+\tint hdrlen;\n+\n+\thdrlen = sprintf(hdr, \"%s %lu\", type, len)+1;\n+\treturn replace_object(buf, len, sha1, hdr, hdrlen);\n+}\n+\n+static void *get_buffer(unsigned char *sha1, char *type, unsigned long *size)\n+{\n+\tunsigned long mapsize;\n+\tvoid *map = map_sha1_file(sha1, &mapsize);\n+\tif (map) {\n+\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, size);\n+\t\tmunmap(map, mapsize);\n+\t\tif (buffer)\n+\t\t\treturn buffer;\n+\t}\n+\terror(\"unable to get object %s\", sha1_to_hex(sha1));\n+\treturn NULL;\n+}\n+\n+static void *expand_delta(void *delta, unsigned long delta_size, char *type,\n+\t\t\t unsigned long *size, unsigned int *depth, char *head)\n+{\n+\tvoid *buf = NULL;\n+\t*depth++;\n+\tif (delta_size < 20) {\n+\t\terror(\"delta object is bad\");\n+\t\tfree(delta);\n+\t} else {\n+\t\tunsigned long ref_size;\n+\t\tvoid *ref = get_buffer(delta, type, &ref_size);\n+\t\tif (ref && !strcmp(type, \"delta\"))\n+\t\t\tref = expand_delta(ref, ref_size, type, &ref_size,\n+\t\t\t\t\t depth, head);\n+\t\telse\n+\t\t\tmemcpy(head, delta, 20);\n+\t\tif (ref)\n+\t\t\tbuf = patch_delta(ref, ref_size, delta+20,\n+\t\t\t\t\t delta_size-20, size);\n+\t\tfree(ref);\n+\t\tfree(delta);\n+\t}\n+\treturn buf;\n+}\n+\n+static char *mkdelta_usage =\n+\"mkdelta [ --max-depth=N ] [ ... ]\";\n+\n+int main(int argc, char **argv)\n+{\n+\tunsigned char sha1_ref[20], sha1_trg[20], head_ref[20], head_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_orig, size_delta;\n+\tunsigned int depth_ref, depth_trg, depth_max = -1;\n+\tint i, verbose = 0;\n+\n+\tfor (i = 1; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"-v\")) {\n+\t\t\tverbose = 1;\n+\t\t} else if (!strcmp(argv[i], \"-d\") && i+1 < argc) {\n+\t\t\tdepth_max = atoi(argv[++i]);\n+\t\t} else if (!strncmp(argv[i], \"--max-depth=\", 12)) {\n+\t\t\tdepth_max = atoi(argv[i]+12);\n+\t\t} else\n+\t\t\tbreak;\n+\t}\n+\n+\tif (i + (depth_max != 0) >= argc)\n+\t\tusage(mkdelta_usage);\n+\n+\tif (get_sha1(argv[i], sha1_ref))\n+\t\tdie(\"bad sha1 %s\", argv[i]);\n+\tdepth_ref = 0;\n+\tbuf_ref = get_buffer(sha1_ref, type_ref, &size_ref);\n+\tif (buf_ref && !strcmp(type_ref, \"delta\"))\n+\t\tbuf_ref = expand_delta(buf_ref, size_ref, type_ref,\n+\t\t\t\t &size_ref, &depth_ref, head_ref);\n+\telse\n+\t\tmemcpy(head_ref, sha1_ref, 20);\n+\tif (!buf_ref)\n+\t\tdie(\"unable to obtain initial object %s\", argv[i]);\n+\n+\tif (depth_ref > depth_max) {\n+\t\tif (replace_sha1_file(buf_ref, size_ref, type_ref, sha1_ref))\n+\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\tif (verbose)\n+\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n+\t\tdepth_ref = 0;\n+\t}\n+\n+\twhile (++i < argc) {\n+\t\tif (get_sha1(argv[i], sha1_trg))\n+\t\t\tdie(\"bad sha1 %s\", argv[i]);\n+\t\tdepth_trg = 0;\n+\t\tbuf_trg = get_buffer(sha1_trg, type_trg, &size_trg);\n+\t\tif (buf_trg && !size_trg) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (object is empty)\\n\", argv[i]);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tsize_orig = size_trg;\n+\t\tif (buf_trg && !strcmp(type_trg, \"delta\")) {\n+\t\t\tif (!memcmp(buf_trg, sha1_ref, 20)) {\n+\t\t\t\t/* delta already in place */\n+\t\t\t\tdepth_ref++;\n+\t\t\t\tmemcpy(sha1_ref, sha1_trg, 20);\n+\t\t\t\tbuf_ref = patch_delta(buf_ref, size_ref,\n+\t\t\t\t\t\t buf_trg+20, size_trg-20,\n+\t\t\t\t\t\t &size_ref);\n+\t\t\t\tif (!buf_ref)\n+\t\t\t\t\tdie(\"unable to apply delta %s\", argv[i]);\n+\t\t\t\tif (depth_ref > depth_max) {\n+\t\t\t\t\tif (replace_sha1_file(buf_ref, size_ref,\n+\t\t\t\t\t\t\t type_ref, sha1_ref))\n+\t\t\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\t\t\t\tif (verbose)\n+\t\t\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n+\t\t\t\t\tdepth_ref = 0;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\tif (verbose)\n+\t\t\t\t\tprintf(\"skip %s (delta already in place)\\n\", argv[i]);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tbuf_trg = expand_delta(buf_trg, size_trg, type_trg,\n+\t\t\t\t\t &size_trg, &depth_trg, head_trg);\n+\t\t} else\n+\t\t\tmemcpy(head_trg, sha1_trg, 20);\n+\t\tif (!buf_trg)\n+\t\t\tdie(\"unable to read target object %s\", argv[i]);\n+\n+\t\tif (depth_trg > depth_max) {\n+\t\t\tif (replace_sha1_file(buf_trg, size_trg, type_trg, sha1_trg))\n+\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_trg);\n+\t\t\tdepth_trg = 0;\n+\t\t\tsize_orig = size_trg;\n+\t\t}\n+\n+\t\tif (depth_max == 0)\n+\t\t\tgoto skip;\n+\n+\t\tif (strcmp(type_ref, type_trg))\n+\t\t\tdie(\"type mismatch for object %s\", argv[i]);\n+\n+\t\tif (!size_ref) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (initial object is empty)\\n\", argv[i]);\n+\t\t\tgoto skip;\n+\t\t}\n+\t\t\n+\t\tdepth_ref++;\n+\t\tif (depth_ref > depth_max) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (exceeding max link depth)\\n\", argv[i]);\n+\t\t\tgoto skip;\n+\t\t}\n+\n+\t\tif (!memcmp(head_ref, sha1_trg, 20)) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (would create a loop)\\n\", argv[i]);\n+\t\t\tgoto skip;\n+\t\t}\n+\n+\t\tbuf_delta = diff_delta(buf_ref, size_ref, buf_trg, size_trg, &size_delta);\n+\t\tif (!buf_delta)\n+\t\t\tdie(\"out of memory\");\n+\n+\t\tif (size_delta+20 < size_orig) {\n+\t\t\tif (write_delta_file(buf_delta, size_delta,\n+\t\t\t\t\t sha1_ref, sha1_trg))\n+\t\t\t\tdie(\"unable to write delta for %s\", argv[i]);\n+\t\t\tfree(buf_delta);\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"delta %s (size=%ld.%02ld%%, depth=%d)\\n\",\n+\t\t\t\t argv[i], (size_delta+20)*100 / size_trg,\n+\t\t\t\t ((size_delta+20)*10000 / size_trg)%100,\n+\t\t\t\t depth_ref);\n+\t\t} else {\n+\t\t\tfree(buf_delta);\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (original is smaller)\\n\", argv[i]);\n+\t\t\tskip:\n+\t\t\tdepth_ref = depth_trg;\n+\t\t\tmemcpy(head_ref, head_trg, 20);\n+\t\t}\n+\n+\t\tfree(buf_ref);\n+\t\tbuf_ref = buf_trg;\n+\t\tsize_ref = size_trg;\n+\t\tmemcpy(sha1_ref, sha1_trg, 20);\n+\t}\n+\n+\treturn 0;\n+}\nIndex: git/mktag.c\n===================================================================\n--- git.orig/mktag.c\n+++ git/mktag.c\n@@ -25,20 +25,14 @@\n static int verify_object(unsigned char *sha1, const char *expected_type)\n {\n \tint ret = -1;\n-\tunsigned long mapsize;\n-\tvoid *map = map_sha1_file(sha1, &mapsize);\n+\tchar type[100];\n+\tunsigned long size;\n+\tvoid *buffer = read_sha1_file(sha1, type, &size);\n \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-\n-\t\tif (buffer) {\n-\t\t\tif (!strcmp(type, expected_type))\n-\t\t\t\tret = check_sha1_signature(sha1, buffer, size, type);\n-\t\t\tfree(buffer);\n-\t\t}\n-\t\tmunmap(map, mapsize);\n+\tif (buffer) {\n+\t\tif (!strcmp(type, expected_type))\n+\t\t\tret = check_sha1_signature(sha1, buffer, size, type);\n+\t\tfree(buffer);\n \t}\n \treturn ret;\n }\nIndex: git/git-deltafy-script\n===================================================================\n--- /dev/null\n+++ git/git-deltafy-script\n@@ -0,0 +1,33 @@\n+#!/bin/bash\n+\n+# Script to deltafy an entire GIT repository based on the commit list.\n+# The most recent version of a file is the reference and the previous version\n+# is changed into a delta from that most recent version. And so on for\n+# successive versions going back in time.\n+#\n+# The -d argument allows to provide a limit on the delta chain depth.\n+# If 0 is passed then everything is undeltafied.\n+\n+set -e\n+\n+depth=\n+[ \"$1\" == \"-d\" ] && depth=\"--max-depth=$2\" && shift 2\n+\n+curr_file=\"\"\n+\n+git-rev-list HEAD |\n+git-diff-tree -r --stdin |\n+sed -n '/^\\*/ s/^.*->\\(.\\{41\\}\\)\\(.*\\)$/\\2 \\1/p' | sort | uniq |\n+while read file sha1; do\n+\tif [ \"$file\" == \"$curr_file\" ]; then\n+\t\tlist=\"$list $sha1\"\n+\telse\n+\t\tif [ \"$list\" ]; then\n+\t\t\techo \"Processing $curr_file\"\n+\t\t\techo \"$head $list\" | xargs git-mkdelta $depth -v\n+\t\tfi\n+\t\tcurr_file=\"$file\"\n+\t\tlist=\"\"\n+\t\thead=\"$sha1\"\n+\tfi\n+done\n"},{"id":"3111","messageId":"7voebhkql5.fsf@assigned-by-dhcp.cox.net","threadId":"577","inReplyTo":"Pine.LNX.4.62.0505112309480.5426@localhost.localdomain","subject":"Re: [PATCH] improved delta support for git","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-12T04:36:54Z","receivedAt":"2005-05-12T04:36:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The changes to sha1_file interface seems to be contained to\nread_sha1_file() only; which is a very good sign. You have\nalready expressed that you are aware that fsck-cache needs to be\ntaught about the delta objects, so I'd trust that would be what\nyou will be tackling next.\n\nI started wondering how the delta chains would affect pull.c,\nthe engine that decides which files under GIT_OBJECT_DIRECTORY\nneed to be pulled from the remote side in order to construct the\nset of objects needed by the given commit ID, under various\ncombinations of cut-off criteria given with -c, -t, and -a\noptions.\n\nIt appears to me that changes to the make_sure_we_have_it()\nroutine along the following lines (completely untested) would\nsuffice. Instead of just returning success, we first fetch the\nnamed object from the remote side, read it to see if it is\nreally the object we have asked, or just a delta, and if it is a\ndelta call itself again on the underlying object that delta\nobject depends upon.\n\nSigned-off-by: Junio C Hamano \n---\n# - git-pb: Fixed a leak in read-tree\n# + (working tree)\n--- a/pull.c\n+++ b/pull.c\n@@ -32,11 +32,23 @@ static void report_missing(const char *w\n static int make_sure_we_have_it(const char *what, unsigned char *sha1)\n {\n \tint status;\n+\tunsigned long mapsize;\n+\tvoid *map, *buf;\n+\n \tif (has_sha1_file(sha1))\n \t\treturn 0;\n \tstatus = fetch(sha1);\n \tif (status && what)\n \t\treport_missing(what, sha1);\n+\n+\tmap = map_sha1_file(sha1, &mapsize);\n+\tif (map) {\n+\t\tbuf = unpack_sha1_file(map, mapsize, type, size);\n+\t\tmunmap(map, mapsize);\n+\t\tif (buf && !strcmp(type, \"delta\"))\n+\t\t\tstatus = make_sure_we_have_it(what, buf);\n+\t\tfree(buf);\n+\t}\n \treturn status;\n }\n \n\n\n"},{"id":"3152","messageId":"200505121027.01964.mason@suse.com","threadId":"577","inReplyTo":"7voebhkql5.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] improved delta support for git","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-12T14:27:00Z","receivedAt":"2005-05-12T14:27:00Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Thursday 12 May 2005 00:36, Junio C Hamano wrote:\n> It appears to me that changes to the make_sure_we_have_it()\n> routine along the following lines (completely untested) would\n> suffice. Instead of just returning success, we first fetch the\n> named object from the remote side, read it to see if it is\n> really the object we have asked, or just a delta, and if it is a\n> delta call itself again on the underlying object that delta\n> object depends upon.\n\nIf we fetch the named object and it is a delta, the delta will either depend \non an object we already have or an object that we don't have. If we don't \nhave it, the pull should find it while pulling other commits we don't have.\n\n-chris\n\n\n"},{"id":"3153","messageId":"2cfc403205051207471f6957e0@mail.gmail.com","threadId":"577","inReplyTo":"2cfc403205051207467755cdf@mail.gmail.com","subject":"Re: [PATCH] improved delta support for git","fromName":"Jon Seymour","fromEmail":"jon.seymour@gmail.com","sentAt":"2005-05-12T14:47:34Z","receivedAt":"2005-05-12T14:47:34Z","isPatch":true,"sender":{"key":"jon.seymour@gmail.com","avatar":"https://avatars.githubusercontent.com/u/207131?v=4"},"body":"On 5/13/05, Chris Mason wrote:\n> On Thursday 12 May 2005 00:36, Junio C Hamano wrote:\n> > It appears to me that changes to the make_sure_we_have_it() ...\n>\n> If we fetch the named object and it is a delta, the delta will either depend\n> on an object we already have or an object that we don't have. If we don't\n> have it, the pull should find it while pulling other commits we don't have.\n>\n\nChris,\n\nDoesn't that assume that the object referenced by the delta is\nreachable from the commit being pulled. While that may be true in\npractice, I don't think it is a logical certainty.\n\njon.\n"},{"id":"3154","messageId":"Pine.LNX.4.62.0505121110490.5426@localhost.localdomain","threadId":"577","inReplyTo":"2cfc403205051207471f6957e0@mail.gmail.com","subject":"Re: [PATCH] improved delta support for git","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-12T15:18:17Z","receivedAt":"2005-05-12T15:18:17Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 13 May 2005, Jon Seymour wrote:\n\n> On 5/13/05, Chris Mason wrote:\n> > On Thursday 12 May 2005 00:36, Junio C Hamano wrote:\n> > > It appears to me that changes to the make_sure_we_have_it() ...\n> >\n> > If we fetch the named object and it is a delta, the delta will either depend\n> > on an object we already have or an object that we don't have. If we don't\n> > have it, the pull should find it while pulling other commits we don't have.\n> >\n> \n> Chris,\n> \n> Doesn't that assume that the object referenced by the delta is\n> reachable from the commit being pulled. While that may be true in\n> practice, I don't think it is a logical certainty.\n\n1) If you happen to already have the referenced object in your local \n repository then you're done.\n\n2) If not you pull the referenced object from the remote repository, \n repeat with #1 if it happens to be another delta object.\n\n3) If the remote repository doesn't contain the object referenced by any \n pulled delta object then that repository is inconsistent just like if \n a blob object referenced by a tree object was missing. This \n therefore should not happen. git-fsck-cache will flag broken delta \n links soon.\n\n\nNicolas\n"},{"id":"3168","messageId":"7vbr7gicv8.fsf@assigned-by-dhcp.cox.net","threadId":"577","inReplyTo":"Pine.LNX.4.62.0505121110490.5426@localhost.localdomain","subject":"Re: [PATCH] improved delta support for git","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-12T17:16:11Z","receivedAt":"2005-05-12T17:16:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"NP\" == Nicolas Pitre writes:\n\n>> On 5/13/05, Chris Mason wrote:\n>> > On Thursday 12 May 2005 00:36, Junio C Hamano wrote:\n>> > > It appears to me that changes to the make_sure_we_have_it() ...\n>> >\n>> > If we fetch the named object and it is a delta, the delta will either depend\n>> > on an object we already have or an object that we don't have. If we don't\n>> > have it, the pull should find it while pulling other commits we don't have.\n\nNP> 1) If you happen to already have the referenced object in your local \nNP> repository then you're done.\n\nYes.\n\nNP> 2) If not you pull the referenced object from the remote repository, \nNP> repeat with #1 if it happens to be another delta object.\n\nYes, that is the outline of what my (untested) patch does.\n\nUnless I am grossly mistaken, what Chris says is true only when\nwe are pulling with -a flag to the git-*-pull family. If we are\npulling \"partially near the tip\", we do not necessarily pull\n\"other commits we don't have\", hence detecting delta's\nrequirement at per-object level and pulling the dependent\nbecomes necessary, which is essentially what you wrote in (2)\nabove.\n\n"},{"id":"3244","messageId":"200505130744.28544.mason@suse.com","threadId":"577","inReplyTo":"7vbr7gicv8.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] improved delta support for git","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-13T11:44:26Z","receivedAt":"2005-05-13T11:44:26Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Thursday 12 May 2005 13:16, Junio C Hamano wrote:\n> >>>>> \"NP\" == Nicolas Pitre writes:\n> >>\n> >> On 5/13/05, Chris Mason wrote:\n> >> > On Thursday 12 May 2005 00:36, Junio C Hamano wrote:\n> >> > > It appears to me that changes to the make_sure_we_have_it() ...\n> >> >\n> >> > If we fetch the named object and it is a delta, the delta will either\n> >> > depend on an object we already have or an object that we don't have. \n> >> > If we don't have it, the pull should find it while pulling other\n> >> > commits we don't have.\n>\n> NP> 1) If you happen to already have the referenced object in your local\n> NP> repository then you're done.\n>\n> Yes.\n>\n> NP> 2) If not you pull the referenced object from the remote repository,\n> NP> repeat with #1 if it happens to be another delta object.\n>\n> Yes, that is the outline of what my (untested) patch does.\n>\n> Unless I am grossly mistaken, what Chris says is true only when\n> we are pulling with -a flag to the git-*-pull family. If we are\n> pulling \"partially near the tip\", we do not necessarily pull\n> \"other commits we don't have\", hence detecting delta's\n> requirement at per-object level and pulling the dependent\n> becomes necessary, which is essentially what you wrote in (2)\n> above.\n>\nYes, my post does assume that you're pulling everything and the repo you're \npulling from has a sane state. This should be the common case though, so I \nwould suggest optimizing things to build a list of the delta objects and \ncheck them at the end to see if we didn't pull any.\n\nWe want the list of delta objects regardless, this way we can warn the user \nthat they have pulled in deltas and give them the chance to convert them into \nfull files.\n\n-chris\n"},{"id":"3455","messageId":"20050517182232.GM13508@cip.informatik.uni-erlangen.de","threadId":"577","inReplyTo":"Pine.LNX.4.62.0505112309480.5426@localhost.localdomain","subject":"Re: [PATCH] improved delta support for git","fromName":"Thomas Glanzmann","fromEmail":"sithglan@stud.uni-erlangen.de","sentAt":"2005-05-17T18:22:32Z","receivedAt":"2005-05-17T18:22:32Z","isPatch":true,"sender":{"key":"sithglan@stud.uni-erlangen.de","avatar":null},"body":"Hello Nicolas,\nI just tried it against Linus git-HEAD. It worked like a charm so far. I\nimported mutt-1.5 CVS branch using cvsps (1103 patches).\n\n(medion) [/scratch/mutt/mutt-cvs] git-rev-tree HEAD | wc -l\n1103\n(medion) [/scratch/mutt/mutt-cvs] du -sh .git/objects/\n63M .git/objects/\n(medion) [/scratch/mutt/mutt-cvs] git-deltafy-script -d 2000\n...\n(medion) [/scratch/mutt/mutt-cvs] du -sh .git/objects/\n35M .git/objects/\n\nMaybe you should add git-deltafy-script and git-mkdelta to the installation\ntargets (patch attached).\n\nAnd I wonder why the mutt CVS Repository is still smaller than the\nzdelta compressed mutt git repository. And with mutt CVS Repository I\nmean every commit since mutt-0.9x not only mutt-1.5 branch?\n\n(faui03) [~] du -sh work/mutt/cvsrepository\n34M work/mutt/cvsrepository\n\nGreetings,\n\tThomas\n\n\n[PATCH] Install git-mkdelta and git-deltafy-script\n\nSigned-off-by: Thomas Glanzmann \n\n--- a/Makefile\n+++ b/Makefile\n@@ -19,7 +19,7 @@\n INSTALL=install\n \n SCRIPTS=git-apply-patch-script git-merge-one-file-script git-prune-script \\\n-\tgit-pull-script git-tag-script git-resolve-script\n+\tgit-pull-script git-tag-script git-resolve-script git-deltafy-script\n \n PROG= git-update-cache git-diff-files git-init-db git-write-tree \\\n \tgit-read-tree git-commit-tree git-cat-file git-fsck-cache \\\n@@ -28,7 +28,7 @@\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-helper git-tar-tree git-local-pull git-write-blob \\\n-\tgit-get-tar-commit-id\n+\tgit-get-tar-commit-id git-mkdelta\n \n all: $(PROG)\n \n"},{"id":"3456","messageId":"20050517190244.GP13508@cip.informatik.uni-erlangen.de","threadId":"577","inReplyTo":"20050517182232.GM13508@cip.informatik.uni-erlangen.de","subject":"Re: [PATCH] improved delta support for git","fromName":"Thomas Glanzmann","fromEmail":"sithglan@stud.uni-erlangen.de","sentAt":"2005-05-17T19:02:44Z","receivedAt":"2005-05-17T19:02:44Z","isPatch":true,"sender":{"key":"sithglan@stud.uni-erlangen.de","avatar":null},"body":"Hello,\nbtw. 6 Megabyte are spend on commit and tree objects:\n\n(medion) [/scratch/mutt/mutt-cvs] find .git/objects/ -type f | sed 's^.*\\(..\\)/^\\1^' | while read FILE; do echo -n \"$FILE \" ;git-cat-file -t $FILE; done | egrep 'tree|commit' | awk '{print $1}' | sed 's,^\\(..\\),.git/objects/\\1/,' | xargs ls -l | awk '{sum += $5} END {print sum}'\n6179105\n\nI know my shell sux.\n\n\tThomas\n"},{"id":"3459","messageId":"20050517191029.GQ13508@cip.informatik.uni-erlangen.de","threadId":"577","inReplyTo":"20050517182232.GM13508@cip.informatik.uni-erlangen.de","subject":"Re: [PATCH] improved delta support for git","fromName":"Thomas Glanzmann","fromEmail":"sithglan@stud.uni-erlangen.de","sentAt":"2005-05-17T19:10:30Z","receivedAt":"2005-05-17T19:10:30Z","isPatch":true,"sender":{"key":"sithglan@stud.uni-erlangen.de","avatar":null},"body":"Hi,\nokay I got it. Fragmentation:\n\nbefore:\n\t(medion) [/scratch/mutt/mutt-cvs] du -sh --apparent-size .git/objects/\n\t49M .git/objects/\n\nafter:\n\t(medion) [/scratch/mutt/mutt-cvs] du -sh --apparent-size .git/objects/\n\t19M .git/objects/\n\ncvs repository:\n\n\t(faui00u) [~/work/git/yagf] du -sh --apparent-size ../../mutt/cvsrepository\n\t33M ../../mutt/cvsrepository\n\nSincerely,\n\tThomas\n"},{"id":"3483","messageId":"d6dohe$dql$1@sea.gmane.org","threadId":"577","inReplyTo":"Pine.LNX.4.62.0505112309480.5426@localhost.localdomain","subject":"Re: [PATCH] improved delta support for git","fromName":"Dan Holmsand","fromEmail":"holmsand@gmail.com","sentAt":"2005-05-17T21:43:47Z","receivedAt":"2005-05-17T21:43:47Z","isPatch":true,"sender":{"key":"holmsand@gmail.com","avatar":"https://gravatar.com/avatar/5c722084bafd85e754a02efad01fe69107eb6f393253c49232c5c9f7faa974df?d=mp&s=160"},"body":"\nNicolas (and others),\n\nI've been trying out your delta stuff as well. It was a bit\ndisappointing at first, but some tweaking payed off in the end...\n\nFirst, I tried the entire bkcvs history for 2.6, but storing only the\n\"fs\" directory tree in git (hoping that would be representative\nenough, since the entire tree gets *big*). I got 4678 commits.\n\nIn its original form, it looks like this (first size is \"network\nsize\", the last one disk size on ext3. Average size per object in\nbytes):\n\ntrees: 16M (15684 files) avg: 1119, disk: 61M\nblobs: 121M (17200 files) avg: 7414, disk: 157M\nTotal: 139M (37562 files) avg: 3883, disk: 237M\n\nUsing your code, with unlimited delta depth:\n\ntrees: 16M (15684 files) avg: 1119, disk: 61M\nblobs: 9M (2333 files) avg: 4491, disk: 15M\ndeltas: 30M (14867 files) avg: 2147, disk: 71M\nTotal: 83M (37562 files) avg: 2334, disk: 188M\n\nSame thing, with a maximum delta depth of 2:\n\ntrees: 16M (15684 files) avg: 1119, disk: 61M\nblobs: 45M (6940 files) avg: 6906, disk: 60M\ndeltas: 20M (10260 files) avg: 2086, disk: 48M\nTotal: 83M (37562 files) avg: 2334, disk: 188M\n\nSo, total size from a network perspective went from 139M to 83M, which\nseemed a little disappointing to me.\n\nI think there are too reasons, as shown by these statistics:\n\n1) Too many deltas get too big and/or compress badly.\n\n2) Trees take up a big chunk of total space.\n\n\nTherefore, I tried some other approaches. This one seemed to work\nbest:\n\n1) I limit the maximum size of any delta to 10% of the size of the new\nversion. That guarantees a big saving, as long as any delta is\nproduced.\n\n2) If the \"previous\" version of a blob is a delta, I produce the new\ndelta form the old deltas base version. This works surprisingly well.\nI'm guessing the reason for this is that most changes are really\nsmall, and they tend to be in the same area as a previous change (as\nin \"Commit new feature. Commit bugfix for new feature. Commit fix for\nbugfix of new feature. Delete new feature as it doesn't work...\").\n\n3) I use the same method for all tree objects.\n\nThis method of \"opportunistic delta compression\" has some other\nadvantages: No risk of long delta chains (as the maximum delta depth\nis one). It should be disk cache friendly, as many deltas are produced\nagainst the same base version. And this method could easily be used\nincrementally, or \"on the fly\", as forward deltas are used.\n\nUsing these tweaks helped a lot, size wise:\n\ntrees: 3M (9746 files) avg: 380, disk: 38M\nblobs: 13M (3301 files) avg: 4208, disk: 20M\ndeltas: 11M (19837 files) avg: 586, disk: 78M\nTotal: 28M (37562 files) avg: 799, disk: 155M\n\nAs this method turned 139M worth of git repository into 28M, I decided\nto try the same method on the entire bkcvs history (28203 commits).\n\nPlain vanilla git looks like this:\n\ntrees: 246M (156812 files) avg: 1647, disk: 699M\nblobs: 1171M (185458 files) avg: 6623, disk: 1573M\nTotal: 1422M (370473 files) avg: 4025, disk: 2382M\n\nThe delta compressed approach outlined above yields:\n\ntrees: 47M (73519 files) avg: 672, disk: 289M\nblobs: 156M (49857 files) avg: 3285, disk: 281M\ndeltas: 107M (218894 files) avg: 515, disk: 863M\nTotal: 315M (370473 files) avg: 892, disk: 1544M\n\nSo, 1.4G became 315M. Not too bad, IMHO. Disk size is still big,\nof course, but disks are apparently cheap these days.\n\nIt could probably be even better, if git didn't produce quite as many\ntree objects. Some sort of chunking together of tree objects would\nhelp delta compression a lot (and improve disk size quite a bit in the\nprocess).\n\nAttached is a patch (against current cogito). It is basically the same\nas yours, Nicolas, except for some hackery to make the above possible.\nI'm sure I've made lots of stupid mistakes in it (and the 10% limit is\nhardcoded right now; I'm lazy).\n\n/dan\n\n\nIndex: Makefile\n===================================================================\n--- 4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2/Makefile (mode:100644)\n+++ uncommitted/Makefile (mode:100644)\n@@ -35,7 +35,7 @@\n INSTALL?=install\n \n SCRIPTS=git-apply-patch-script git-merge-one-file-script git-prune-script \\\n-\tgit-pull-script git-tag-script git-resolve-script\n+\tgit-pull-script git-tag-script git-resolve-script git-deltafy-script\n \n PROG= git-update-cache git-diff-files git-init-db git-write-tree \\\n \tgit-read-tree git-commit-tree git-cat-file git-fsck-cache \\\n@@ -44,7 +44,7 @@\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-helper git-tar-tree git-local-pull git-write-blob \\\n-\tgit-get-tar-commit-id\n+\tgit-get-tar-commit-id git-mkdelta\n \n SCRIPT=\tcommit-id tree-id parent-id cg-add cg-admin-lsobj cg-admin-uncommit \\\n \tcg-branch-add cg-branch-ls cg-cancel cg-clone cg-commit cg-diff \\\n@@ -60,7 +60,7 @@\n COMMON=\tread-cache.o\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@@ -94,6 +94,9 @@\n all: $(PROG) $(GEN_SCRIPT)\n \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 \nIndex: delta.h\n===================================================================\n--- /dev/null (tree:4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2)\n+++ uncommitted/delta.h (mode:100644)\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);\nIndex: diff-delta.c\n===================================================================\n--- /dev/null (tree:4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2)\n+++ uncommitted/diff-delta.c (mode:100644)\n@@ -0,0 +1,330 @@\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 (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))\n+\t\treturn NULL;\n+\t\n+\toutpos = 0;\n+\toutsize = 8192;\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+\t/* store reference buffer size */\n+\torig = out + outpos++;\n+\t*orig = i = 0;\n+\tdo {\n+\t\tif (from_size & 0xff) {\n+\t\t\t*orig |= (1 << i);\n+\t\t\tout[outpos++] = from_size;\n+\t\t}\n+\t\ti++;\n+\t\tfrom_size >>= 8;\n+\t} while (from_size);\n+\n+\t/* store target buffer size */\n+\torig = out + outpos++;\n+\t*orig = i = 0;\n+\tdo {\n+\t\tif (to_size & 0xff) {\n+\t\t\t*orig |= (1 << i);\n+\t\t\tout[outpos++] = to_size;\n+\t\t}\n+\t\ti++;\n+\t\tto_size >>= 8;\n+\t} while (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+}\nIndex: git-deltafy-script\n===================================================================\n--- /dev/null (tree:4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2)\n+++ uncommitted/git-deltafy-script (mode:100755)\n@@ -0,0 +1,64 @@\n+#!/bin/bash\n+\n+# Script to deltafy an entire GIT repository based on the commit list.\n+\n+# git-deltafy-script --pack deltafies a repository, from current HEAD\n+# down.\n+# git-deltafy-script --unpack undeltafies all objects.\n+\n+export LANG=C\n+\n+depth=\n+[ \"$1\" == \"-d\" ] && depth=\"--max-depth=$2\" && shift 2\n+\n+prevcommit=\n+prevtree=\n+\n+treeid() {\n+\tgit-cat-file commit \"$1\" | sed -e 's/tree //;q'\n+}\n+\n+mkdelta() {\n+\tgit-mkdelta --max-depth=1 -o -v \"$@\" || exit 1\n+}\n+\n+if [ \"$1\" = --pack ] ; then\n+git-rev-list HEAD | tac |\n+while read commit; do\n+\tif [ \"$prevcommit\" ]; then\n+\t\tgit-diff-tree -r -z $prevcommit $commit |\n+\t\twhile IFS=$'\\t' read -d $'\\0' a1 a2 sha file; do\n+\t\t\tto=${sha#*->}\n+\t\t\tfrom=${sha%->*}\n+\t\t\t[ \"$from\" != \"$to\" ] && mkdelta $from $to \n+\t\tdone\n+\n+\t\tprevdir=\n+\t\tprevsha=\n+\t\ttree=$(treeid \"$commit\") \n+\t\t[ \"$prevtree\" ] || prevtree=$(treeid $prevcommit)\n+\t\t[ $prevtree != $tree ] && mkdelta $prevtree $tree \n+\n+\t\t( git-ls-tree -r $prevtree; git-ls-tree -r $tree ) |\n+\t\tgrep $'^[0-9]*\\ttree' | sort -k4 -s | uniq -u -s4 |\n+\t\twhile IFS=$'\\t' read a1 a2 sha dir; do\n+\t\t\tif [ \"$prevdir\" = \"$dir\" -a \"$prevsha\" != \"$sha\" ]; then\n+\t\t\t\techo \"deltafying tree $dir\"\n+\t\t\t\tmkdelta $prevsha $sha \n+\t\t\tfi\n+\t\t\tprevdir=$dir\n+\t\t\tprevsha=$sha\n+\t\tdone\n+\n+\tfi\n+\tprevcommit=$commit\n+\tprevtree=$tree\n+done\n+elif [ \"$1\" = --unpack ]; then\n+\t( cd .git/objects && find -type f ) | sed 's,[./],,g' | \n+\txargs git-mkdelta --max-depth=0 -v\n+else\n+\techo \"usage: $(basename \"$0\") [--pack|--unpack]\" >&2\n+\texit 1\n+fi\n+exit 0\nIndex: mkdelta.c\n===================================================================\n--- /dev/null (tree:4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2)\n+++ uncommitted/mkdelta.c (mode:100644)\n@@ -0,0 +1,306 @@\n+/*\n+ * Deltafication of a GIT database.\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 \"cache.h\"\n+#include \"delta.h\"\n+\n+static int replace_object(char *buf, unsigned long len, unsigned char *sha1,\n+\t\t\t char *hdr, int hdrlen)\n+{\n+\tchar tmpfile[PATH_MAX];\n+\tint size;\n+\tchar *compressed;\n+\tz_stream stream;\n+\tint fd;\n+\n+\tsnprintf(tmpfile, sizeof(tmpfile), \"%s/obj_XXXXXX\", get_object_directory());\n+\tfd = mkstemp(tmpfile);\n+\tif (fd < 0)\n+\t\treturn error(\"%s: %s\\n\", tmpfile, strerror(errno));\n+\t\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\tperror(\"unable to write file\");\n+\t\tclose(fd);\n+\t\tunlink(tmpfile);\n+\t\treturn -1;\n+\t}\n+\tfchmod(fd, 0444);\n+\tclose(fd);\n+\n+\tif (rename(tmpfile, sha1_file_name(sha1))) {\n+\t\tperror(\"unable to replace original object\");\n+\t\tunlink(tmpfile);\n+\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+static int write_delta_file(char *buf, unsigned long len,\n+\t\t\t unsigned char *sha1_ref, unsigned char *sha1_trg)\n+{\n+\tchar hdr[50];\n+\tint hdrlen;\n+\n+\t/* Generate the header + sha1 of reference for delta */\n+\thdrlen = sprintf(hdr, \"delta %lu\", len+20)+1;\n+\tmemcpy(hdr + hdrlen, sha1_ref, 20);\n+\thdrlen += 20;\n+\n+\treturn replace_object(buf, len, sha1_trg, hdr, hdrlen);\n+}\n+\n+static int replace_sha1_file(char *buf, unsigned long len,\n+\t\t\t char *type, unsigned char *sha1)\n+{\n+\tchar hdr[50];\n+\tint hdrlen;\n+\n+\thdrlen = sprintf(hdr, \"%s %lu\", type, len)+1;\n+\treturn replace_object(buf, len, sha1, hdr, hdrlen);\n+}\n+\n+static void *get_buffer(unsigned char *sha1, char *type, unsigned long *size)\n+{\n+\tunsigned long mapsize;\n+\tvoid *map = map_sha1_file(sha1, &mapsize);\n+\tif (map) {\n+\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, size);\n+\t\tmunmap(map, mapsize);\n+\t\tif (buffer)\n+\t\t\treturn buffer;\n+\t}\n+\terror(\"unable to get object %s\", sha1_to_hex(sha1));\n+\treturn NULL;\n+}\n+\n+static void *expand_delta(void *delta, unsigned long delta_size, char *type,\n+\t\t\t unsigned long *size, unsigned int *depth, char *head)\n+{\n+\tvoid *buf = NULL;\n+\t*depth++;\n+\tif (delta_size < 20) {\n+\t\terror(\"delta object is bad\");\n+\t\tfree(delta);\n+\t} else {\n+\t\tunsigned long ref_size;\n+\t\tvoid *ref = get_buffer(delta, type, &ref_size);\n+\t\tif (ref && !strcmp(type, \"delta\"))\n+\t\t\tref = expand_delta(ref, ref_size, type, &ref_size,\n+\t\t\t\t\t depth, head);\n+\t\telse\n+\t\t\tmemcpy(head, delta, 20);\n+\t\tif (ref)\n+\t\t\tbuf = patch_delta(ref, ref_size, delta+20,\n+\t\t\t\t\t delta_size-20, size);\n+\t\tfree(ref);\n+\t\tfree(delta);\n+\t}\n+\treturn buf;\n+}\n+\n+static char *mkdelta_usage =\n+\"mkdelta [ --max-depth=N ] [ -o ] [ ... ]\";\n+\n+int main(int argc, char **argv)\n+{\n+\tunsigned char sha1_ref[20], sha1_trg[20], head_ref[20], head_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_orig, size_delta;\n+\tunsigned int depth_ref, depth_trg, depth_max = -1;\n+\tint i, verbose = 0, oneparent = 0;\n+\n+\tfor (i = 1; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"-v\")) {\n+\t\t\tverbose = 1;\n+\t\t} else if (!strcmp(argv[i], \"-o\")) {\n+\t\t\toneparent = 1;\n+\t\t} else if (!strcmp(argv[i], \"-d\") && i+1 < argc) {\n+\t\t\tdepth_max = atoi(argv[++i]);\n+\t\t} else if (!strncmp(argv[i], \"--max-depth=\", 12)) {\n+\t\t\tdepth_max = atoi(argv[i]+12);\n+\t\t} else\n+\t\t\tbreak;\n+\t}\n+\n+\tif (i + (depth_max != 0) >= argc)\n+\t\tusage(mkdelta_usage);\n+\n+\tif (get_sha1(argv[i], sha1_ref))\n+\t\tdie(\"bad sha1 %s\", argv[i]);\n+\tdepth_ref = 0;\n+\tbuf_ref = get_buffer(sha1_ref, type_ref, &size_ref);\n+\tif (oneparent && depth_max > 0) {\n+\t\twhile (buf_ref && !strcmp(type_ref, \"delta\")) {\n+\t\t\tif (size_ref < 20)\n+\t\t\t\tdie(\"bad delta object\");\n+\t\t\t//printf (\"getting parent for %s %i\\n\", \n+\t\t\t\t\t//sha1_to_hex(sha1_ref), depth_max);\n+\t\t\tmemcpy(sha1_ref, buf_ref, 20);\n+\t\t\tfree(buf_ref);\n+\t\t\t//printf(\"loading parent %s\\n\",\n+\t\t\t\t\t//sha1_to_hex(sha1_ref));\n+\t\t\tbuf_ref = get_buffer(sha1_ref, \n+\t\t\t\t\ttype_ref, &size_ref);\n+\t\t\tif (!buf_ref) die(\"broken get_buffer!\");\n+\t\t}\n+\t}\n+\tif (buf_ref && !strcmp(type_ref, \"delta\"))\n+\t\tbuf_ref = expand_delta(buf_ref, size_ref, type_ref,\n+\t\t\t\t &size_ref, &depth_ref, head_ref);\n+\telse\n+\t\tmemcpy(head_ref, sha1_ref, 20);\n+\tif (!buf_ref)\n+\t\tdie(\"unable to obtain initial object %s\", argv[i]);\n+\n+\tif (depth_ref > depth_max) {\n+\t\tif (replace_sha1_file(buf_ref, size_ref, type_ref, sha1_ref))\n+\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\tif (verbose)\n+\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n+\t\tdepth_ref = 0;\n+\t}\n+\n+\twhile (++i < argc) {\n+\t\tif (get_sha1(argv[i], sha1_trg))\n+\t\t\tdie(\"bad sha1 %s\", argv[i]);\n+\t\tdepth_trg = 0;\n+\t\tbuf_trg = get_buffer(sha1_trg, type_trg, &size_trg);\n+\t\tif (buf_trg && !size_trg) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (object is empty)\\n\", argv[i]);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tsize_orig = size_trg;\n+\t\tif (buf_trg && !strcmp(type_trg, \"delta\")) {\n+\t\t\tif (!memcmp(buf_trg, sha1_ref, 20)) {\n+\t\t\t\t/* delta already in place */\n+\t\t\t\tdepth_ref++;\n+\t\t\t\tmemcpy(sha1_ref, sha1_trg, 20);\n+\t\t\t\tbuf_ref = patch_delta(buf_ref, size_ref,\n+\t\t\t\t\t\t buf_trg+20, size_trg-20,\n+\t\t\t\t\t\t &size_ref);\n+\t\t\t\tif (!buf_ref)\n+\t\t\t\t\tdie(\"unable to apply delta %s\", argv[i]);\n+\t\t\t\tif (depth_ref > depth_max) {\n+\t\t\t\t\tif (replace_sha1_file(buf_ref, size_ref,\n+\t\t\t\t\t\t\t type_ref, sha1_ref))\n+\t\t\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\t\t\t\tif (verbose)\n+\t\t\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n+\t\t\t\t\tdepth_ref = 0;\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\tif (verbose)\n+\t\t\t\t\tprintf(\"skip %s (delta already in place)\\n\", argv[i]);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tbuf_trg = expand_delta(buf_trg, size_trg, type_trg,\n+\t\t\t\t\t &size_trg, &depth_trg, head_trg);\n+\t\t} else\n+\t\t\tmemcpy(head_trg, sha1_trg, 20);\n+\t\tif (!buf_trg)\n+\t\t\tdie(\"unable to read target object %s\", argv[i]);\n+\n+\t\tif (depth_trg > depth_max || depth_max == 0) {\n+\t\t\tif (replace_sha1_file(buf_trg, size_trg, type_trg, sha1_trg))\n+\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_trg);\n+\t\t\tdepth_trg = 0;\n+\t\t\tsize_orig = size_trg;\n+\t\t}\n+\n+\t\tif (depth_max == 0)\n+\t\t\tgoto skip;\n+\n+\t\tif (strcmp(type_ref, type_trg))\n+\t\t\tdie(\"type mismatch for object %s\", argv[i]);\n+\n+\t\tif (!size_ref) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (initial object is empty)\\n\", argv[i]);\n+\t\t\tgoto skip;\n+\t\t}\n+\t\t\n+\t\tdepth_ref++;\n+\t\tif (depth_ref > depth_max) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (exceeding max link depth)\\n\", argv[i]);\n+\t\t\tgoto skip;\n+\t\t}\n+\n+\t\tif (!memcmp(head_ref, sha1_trg, 20)) {\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"skip %s (would create a loop)\\n\", argv[i]);\n+\t\t\tgoto skip;\n+\t\t}\n+\n+\t\tbuf_delta = diff_delta(buf_ref, size_ref, buf_trg, size_trg, &size_delta);\n+\t\tif (!buf_delta)\n+\t\t\tdie(\"out of memory\");\n+\n+\t\t//if (size_delta+20 < size_orig) {\n+\t\tif ((size_delta+20)*100/size_trg < 10) {\n+\t\t\tif (write_delta_file(buf_delta, size_delta,\n+\t\t\t\t\t sha1_ref, sha1_trg))\n+\t\t\t\tdie(\"unable to write delta for %s\", argv[i]);\n+\t\t\tfree(buf_delta);\n+\t\t\tif (verbose)\n+\t\t\t\tprintf(\"delta %s (size=%ld.%02ld%%, depth=%d)\\n\",\n+\t\t\t\t argv[i], (size_delta+20)*100 / size_trg,\n+\t\t\t\t ((size_delta+20)*10000 / size_trg)%100,\n+\t\t\t\t depth_ref);\n+\t\t} else {\n+\t\t\tfree(buf_delta);\n+\t\t\tif (verbose) {\n+\t\t\t\tprintf(\"skip %s (original is smaller)\", argv[i]);\n+\t\t\t\tprintf(\" (size=%ld.%02ld%%, depth=%d)\\n\",\n+\t\t\t\t (size_delta+20)*100 / size_trg,\n+\t\t\t\t ((size_delta+20)*10000 / size_trg)%100,\n+\t\t\t\t depth_ref);\n+\t\t\t}\n+\t\t\tskip:\n+\t\t\tdepth_ref = depth_trg;\n+\t\t\tmemcpy(head_ref, head_trg, 20);\n+\t\t}\n+\n+\t\tfree(buf_ref);\n+\t\tbuf_ref = buf_trg;\n+\t\tsize_ref = size_trg;\n+\t\tmemcpy(sha1_ref, sha1_trg, 20);\n+\t}\n+\n+\treturn 0;\n+}\nIndex: mktag.c\n===================================================================\n--- 4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2/mktag.c (mode:100644)\n+++ uncommitted/mktag.c (mode:100644)\n@@ -25,20 +25,14 @@\n static int verify_object(unsigned char *sha1, const char *expected_type)\n {\n \tint ret = -1;\n-\tunsigned long mapsize;\n-\tvoid *map = map_sha1_file(sha1, &mapsize);\n+\tchar type[100];\n+\tunsigned long size;\n+\tvoid *buffer = read_sha1_file(sha1, type, &size);\n \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-\n-\t\tif (buffer) {\n-\t\t\tif (!strcmp(type, expected_type))\n-\t\t\t\tret = check_sha1_signature(sha1, buffer, size, type);\n-\t\t\tfree(buffer);\n-\t\t}\n-\t\tmunmap(map, mapsize);\n+\tif (buffer) {\n+\t\tif (!strcmp(type, expected_type))\n+\t\t\tret = check_sha1_signature(sha1, buffer, size, type);\n+\t\tfree(buffer);\n \t}\n \treturn ret;\n }\nIndex: patch-delta.c\n===================================================================\n--- /dev/null (tree:4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2)\n+++ uncommitted/patch-delta.c (mode:100644)\n@@ -0,0 +1,88 @@\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_buf, *out, cmd;\n+\tunsigned long size;\n+\tint i;\n+\n+\t/* the smallest delta size possible is 6 bytes */\n+\tif (delta_size < 6)\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 = i = 0;\n+\tcmd = *data++;\n+\twhile (cmd) {\n+\t\tif (cmd & 1)\n+\t\t\tsize |= *data++ << i;\n+\t\ti += 8;\n+\t\tcmd >>= 1;\n+\t}\n+\tif (size != src_size)\n+\t\treturn NULL;\n+\n+\t/* now the result size */\n+\tsize = i = 0;\n+\tcmd = *data++;\n+\twhile (cmd) {\n+\t\tif (cmd & 1)\n+\t\t\tsize |= *data++ << i;\n+\t\ti += 8;\n+\t\tcmd >>= 1;\n+\t}\n+\tdst_buf = malloc(size);\n+\tif (!dst_buf)\n+\t\treturn NULL;\n+\n+\tout = dst_buf;\n+\twhile (data < top) {\n+\t\tcmd = *data++;\n+\t\tif (cmd & 0x80) {\n+\t\t\tunsigned long cp_off = 0, cp_size = 0;\n+\t\t\tconst unsigned char *buf;\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\tbuf = (cmd & 0x40) ? dst_buf : src_buf;\n+\t\t\tmemcpy(out, 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_buf != size) {\n+\t\tfree(dst_buf);\n+\t\treturn NULL;\n+\t}\n+\n+\t*dst_size = size;\n+\treturn dst_buf;\n+}\nIndex: sha1_file.c\n===================================================================\n--- 4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2/sha1_file.c (mode:100644)\n+++ uncommitted/sha1_file.c (mode:100644)\n@@ -9,6 +9,7 @@\n #include \n #include \n #include \"cache.h\"\n+#include \"delta.h\"\n \n #ifndef O_NOATIME\n #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))\n@@ -353,6 +354,19 @@\n \tif (map) {\n \t\tbuf = unpack_sha1_file(map, mapsize, type, size);\n \t\tmunmap(map, mapsize);\n+\t\tif (buf && !strcmp(type, \"delta\")) {\n+\t\t\tvoid *ref = NULL, *delta = buf;\n+\t\t\tunsigned long ref_size, delta_size = *size;\n+\t\t\tbuf = NULL;\n+\t\t\tif (delta_size > 20)\n+\t\t\t\tref = read_sha1_file(delta, type, &ref_size);\n+\t\t\tif (ref)\n+\t\t\t\tbuf = patch_delta(ref, ref_size,\n+\t\t\t\t\t\t delta+20, delta_size-20, \n+\t\t\t\t\t\t size);\n+\t\t\tfree(delta);\n+\t\t\tfree(ref);\n+\t\t}\n \t\treturn buf;\n \t}\n \treturn NULL;\nIndex: test-delta.c\n===================================================================\n--- /dev/null (tree:4ef3de6ae44888d83e8c00326ddcc9f40cbd12e2)\n+++ uncommitted/test-delta.c (mode:100644)\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":"3487","messageId":"Pine.LNX.4.62.0505180005230.20274@localhost.localdomain","threadId":"577","inReplyTo":"d6dohe$dql$1@sea.gmane.org","subject":"Re: [PATCH] improved delta support for git","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-18T04:32:51Z","receivedAt":"2005-05-18T04:32:51Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 17 May 2005, Dan Holmsand wrote:\n\n> I've been trying out your delta stuff as well. It was a bit\n> disappointing at first, but some tweaking payed off in the end...\n\nCool!\n\nMy goal is to provide the mechanism that can be used by a higher level \nimplementing the deltafication policy. I only provided one script as an \nexample, but it turns out that you found a way to achieve better space \nsaving. And I bet you that there is probably ways to do even better \nwith more exhaustive delta targets. For example you could try all \npossible combinations on an object list for each file (and let it run \novernight).\n\n> 1) Too many deltas get too big and/or compress badly.\n\nOne thing I've been wondering about is whether gzipping small deltas is \nactually a gain. For very small files it seems that gzip is adding more \noverhead making the compressed file actually larger. Might be worth \nstoring some deltas uncompressed if the compressed version turns out to \nbe larger.\n\n> 2) Trees take up a big chunk of total space.\n\nTree objects can be deltafied as well, but I didn't had time to script \nit. A large space saving can be expected there as well, especially for \nchangesets that modify only a few files deep down the tree hierarchy.\n\n> Therefore, I tried some other approaches. This one seemed to work\n> best:\n> \n> 1) I limit the maximum size of any delta to 10% of the size of the new\n> version. That guarantees a big saving, as long as any delta is\n> produced.\n\nWell, any delta object smaller than its original object saves space, \neven if it's 75% of the original size. But...\n\n> 2) If the \"previous\" version of a blob is a delta, I produce the new\n> delta form the old deltas base version. This works surprisingly well.\n> I'm guessing the reason for this is that most changes are really\n> small, and they tend to be in the same area as a previous change (as\n> in \"Commit new feature. Commit bugfix for new feature. Commit fix for\n> bugfix of new feature. Delete new feature as it doesn't work...\").\n\n... but then the ultimate solution is to try out all possible references \nwithin a given list. My git-deltafy-script already finds out the list \nof objects belonging to the same file. Maybe git-mkdelta should try \nall combinations between them. This way a deeper delta chain could be \nallowed for maximum space saving.\n\n> 3) I use the same method for all tree objects.\n\nYup.\n\n> Attached is a patch (against current cogito). It is basically the same\n> as yours, Nicolas, except for some hackery to make the above possible.\n> I'm sure I've made lots of stupid mistakes in it (and the 10% limit is\n> hardcoded right now; I'm lazy).\n\nI will look at it and merge the good stuff.\n\nThanks for testing!\n\n\nNicolas\n"},{"id":"3491","messageId":"d6evrk$jv2$1@sea.gmane.org","threadId":"577","inReplyTo":"Pine.LNX.4.62.0505180005230.20274@localhost.localdomain","subject":"Re: [PATCH] improved delta support for git","fromName":"Dan Holmsand","fromEmail":"holmsand@gmail.com","sentAt":"2005-05-18T08:54:54Z","receivedAt":"2005-05-18T08:54:54Z","isPatch":true,"sender":{"key":"holmsand@gmail.com","avatar":"https://gravatar.com/avatar/5c722084bafd85e754a02efad01fe69107eb6f393253c49232c5c9f7faa974df?d=mp&s=160"},"body":"Nicolas Pitre wrote:\n> My goal is to provide the mechanism that can be used by a higher level \n> implementing the deltafication policy. I only provided one script as an \n> example, but it turns out that you found a way to achieve better space \n> saving. And I bet you that there is probably ways to do even better \n> with more exhaustive delta targets. For example you could try all \n> possible combinations on an object list for each file (and let it run \n> overnight).\n\nWell, any kind of deltafication of, say, the complete kernel history \npretty much has to run overnight anyway :-)\n\n> One thing I've been wondering about is whether gzipping small deltas is \n> actually a gain. For very small files it seems that gzip is adding more \n> overhead making the compressed file actually larger. Might be worth \n> storing some deltas uncompressed if the compressed version turns out to \n> be larger.\n\nIt's probably better to skip deltafication of very small files \naltogether. Big pain for small gain, and all that.\n\n>>1) I limit the maximum size of any delta to 10% of the size of the new\n>>version. That guarantees a big saving, as long as any delta is\n>>produced.\n> \n> \n> Well, any delta object smaller than its original object saves space, \n> even if it's 75% of the original size. But...\n\nThat's not true if you want to keep the delta chain length down (and \nthus performance up).\n\nThen, the most efficient approach is to generate many deltas against the \nsame base file (otherwise, you only get 50% delta files with a maximum \ndelta depth of 1).\n\nBut in this case, the trick is to know when to stop deltafying against \none base file, and start over with another. If you switch to a new \nkeyframe too often, you obviously lose some potential savings. But if \nyou don't switch often enough, you end up repeating the same data in too \nmany delta files.\n\nA maximum delta size of 10% turned out to be ideal for at least the \"fs\" \n tree. 8% was significantly worse, as was 15%. (The ideal size depends \non how big the average change is: the smaller the average change, the \nsmaller the max delta size should be).\n\n> ... but then the ultimate solution is to try out all possible references \n> within a given list. My git-deltafy-script already finds out the list \n> of objects belonging to the same file. Maybe git-mkdelta should try \n> all combinations between them. This way a deeper delta chain could be \n> allowed for maximum space saving.\n\nYeah. But then you lose the ability to do incremental deltafication, or \ndeltafication on-the-fly. And it would be really, really nice to have \ngit do deltas at commit time - that way you could keep the very cool \n\"immutable objects\" property of git, while still saving a lot of space.\n\n> I will look at it and merge the good stuff.\n\nCool! Thanks!\n\n/dan\n\n"},{"id":"3497","messageId":"Pine.LNX.4.58.0505180754060.18337@ppc970.osdl.org","threadId":"577","inReplyTo":"d6dohe$dql$1@sea.gmane.org","subject":"Re: [PATCH] improved delta support for git","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-18T15:12:26Z","receivedAt":"2005-05-18T15:12:26Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 17 May 2005, Dan Holmsand wrote:\n> \n> Therefore, I tried some other approaches. This one seemed to work\n> best:\n> \n> 1) I limit the maximum size of any delta to 10% of the size of the new\n> version. That guarantees a big saving, as long as any delta is\n> produced.\n> \n> 2) If the \"previous\" version of a blob is a delta, I produce the new\n> delta form the old deltas base version. This works surprisingly well.\n> I'm guessing the reason for this is that most changes are really\n> small, and they tend to be in the same area as a previous change (as\n> in \"Commit new feature. Commit bugfix for new feature. Commit fix for\n> bugfix of new feature. Delete new feature as it doesn't work...\").\n> \n> 3) I use the same method for all tree objects.\n\nHas anybody tried:\n\n 4) don't limit yourself to previous-history-objects\n\nOne of the things I liked best about the delta patches was that it is\nhistory-neutral, and can happily delta an object against any other random\nobject, in the same tree, in a future tree, or in a past tree.\n\nEven without any history at all, there should be a noticeable amount of \ndelta opportunities, as different architectures often end up sharing files \nthat are quite similar, but not exactly the same.\n\nNow, that's a very expensive thing to do, since it changes the question of\n\"which object should I delta against\" from O(1) to O(n) (where \"n\" is tyhe\ntotal number of objects), and thus the whole deltafication from O(n) to\nO(n**2), but especially together with your \"max 10%\" rule, you should be\nable to limit your choices very effectively: if you know that your delta\nshould be within 10% of the total size, you can limit your \"let's try that\nobject\" search to other objects that are also within 10% of your object.\n\nThat doesn't change the basic expense factor much in theory (if sizes were\ntruly evenly distributed in it might change it, but there's probably\nonly a few different \"classes\" of file sizes, much fewer than , so it's\nstill probably O(n**2)), but it should cut down the work by some\nnoticeable constant factor, making it a hopefully realistic experiment.\n\nSo your first rule makes a global deltafication cheaper, and in fact,\ntogether with your second rule, you might even decide to make the size \ndifferential depend on the size of the _compressed_ object, since you \ndon't care about objects that have already been deltafied, and if they are \nwithin 10% of each other, then they should also likely compress similarly, \nand it should thus be pretty equivalent to just compare compressed sizes.\n\nAgain, that second optimization wouldn't change the O(n**2) nature of the\nexpense, but should give another nice factor of speedup, maybe making the\nexercise possible in the first place.\n\nAs to the long-term \"O(n**2) deltafication is not practical for big \nprojects with lots of history\" issue, doing things incrementally should \nhopefully solve that, and turn it into a series of O(n) operations at the \ncost of saying \"we'll never re-delta an object against the future once \nwe've found a delta in the past or used it as a base for a delta\".\n\nThe fsck \"scan all objects\" code could be a good starting point.\n\nDoing this experiment at least once should be interesting. It may turn out\nthat the incremental space savings aren't all that noticeable, and that\nthe pure history-based one already finds 90% of all savings, making the\nexpensive version not worth it. It would be nice to _know_, though.\n\n\t\tLinus\n"},{"id":"3503","messageId":"d6ft6v$8eg$1@sea.gmane.org","threadId":"577","inReplyTo":"Pine.LNX.4.58.0505180754060.18337@ppc970.osdl.org","subject":"Re: [PATCH] improved delta support for git","fromName":"Dan Holmsand","fromEmail":"holmsand@gmail.com","sentAt":"2005-05-18T17:15:56Z","receivedAt":"2005-05-18T17:15:56Z","isPatch":true,"sender":{"key":"holmsand@gmail.com","avatar":"https://gravatar.com/avatar/5c722084bafd85e754a02efad01fe69107eb6f393253c49232c5c9f7faa974df?d=mp&s=160"},"body":"Linus Torvalds wrote:\n> Has anybody tried:\n> \n> 4) don't limit yourself to previous-history-objects\n> \n> One of the things I liked best about the delta patches was that it is\n> history-neutral, and can happily delta an object against any other random\n> object, in the same tree, in a future tree, or in a past tree.\n> \n> Even without any history at all, there should be a noticeable amount of \n> delta opportunities, as different architectures often end up sharing files \n> that are quite similar, but not exactly the same.\n> \n> Now, that's a very expensive thing to do, since it changes the question of\n> \"which object should I delta against\" from O(1) to O(n) (where \"n\" is tyhe\n> total number of objects), and thus the whole deltafication from O(n) to\n> O(n**2), but especially together with your \"max 10%\" rule, you should be\n> able to limit your choices very effectively: if you know that your delta\n> should be within 10% of the total size, you can limit your \"let's try that\n> object\" search to other objects that are also within 10% of your object.\n\nYeah, that sounds very interresting *and* very expensive...\n\nIdeally, I'd like to find the set of objects that should *not* be \ndeltafied (i.e. the ideal \"keyframe\" objects), but that would generate \nthe maximum number of small, depth-one deltas with the least total size. \nBut I can't really see how that could be done in a number of \ndeltafications significantly less than the number of atoms in the \nuniverse. Let me think about that some more, though.\n\nI'd like to try a couple of other approaches anyway:\n\na) Sort all objects by size. Start by biggest (or smallest), and try to \nget as many max-10%-deltas out of that as possible, stopping the search \nwhen objects get too small (big) according to some size difference \nlimit. Cross already deltafied objects off the list, and continue. Might \nwork, and might be fast enough with a sufficiently small size limit.\n\nb) Use the same history-based approach as before, and in addition try to \ndeltafy any \"new\" objects against other new objects and previous ones \n(say one or two commits back) in a given size range. That should catch \nrenames, copys of the same template, etc. That shouldn't really affect \nperformance, as new files are added comparatively seldom.\n\n> Doing this experiment at least once should be interesting. It may turn out\n> that the incremental space savings aren't all that noticeable, and that\n> the pure history-based one already finds 90% of all savings, making the\n> expensive version not worth it. It would be nice to _know_, though.\n\nI definitely agree. And I also agree that the history-based \ndeltafication seems less than pure, from a \"git, the object store that \ndoesn't really care\" point of view.\n\nOn the other hand, the history-based thing has its advantages. It takes \nadvantage of people's hard work to make patches as small as possible. \nIt's fast. And (perhaps more importantly), it's deterministic. The \n\"ideal\" approach could possibly require every single blob to be \nredeltafied when a new object is added, if we want to stay ideal.\n\nAnd it could be done at commit-time, thus keeping git's nice promise of \nimmutable files, while still keeping size requirements down. And as my \ncurrent method gives roughly an 80% size reduction over \"plain git\", \nthat might (by boring, excessively practical people) be considered \nenough :-)\n\n/dan\n\n"},{"id":"3509","messageId":"Pine.LNX.4.62.0505181428170.20274@localhost.localdomain","threadId":"577","inReplyTo":"d6evrk$jv2$1@sea.gmane.org","subject":"Re: [PATCH] improved delta support for git","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-18T18:41:54Z","receivedAt":"2005-05-18T18:41:54Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 18 May 2005, Dan Holmsand wrote:\n\n> Nicolas Pitre wrote:\n> > One thing I've been wondering about is whether gzipping small deltas is\n> > actually a gain. For very small files it seems that gzip is adding more\n> > overhead making the compressed file actually larger. Might be worth storing\n> > some deltas uncompressed if the compressed version turns out to be larger.\n> \n> It's probably better to skip deltafication of very small files altogether. Big\n> pain for small gain, and all that.\n\nNo, that's not what I mean.\n\nSuppose a large source file that may change only one line between two \nversions. The delta may therefore end up being only a few bytes long. \nCompressing a few bytes with zlib creates a _larger_ file than the \noriginal few bytes.\n\n> > Well, any delta object smaller than its original object saves space, even if\n> > it's 75% of the original size. But...\n> \n> That's not true if you want to keep the delta chain length down (and thus\n> performance up).\n\nSure. That's why I added the -d switch to mkdelta. But if you can fit \na delta which is 75% the size of its original object size then you still \nsave 25% of the space, regardless of the delta chain length.\n\n> But in this case, the trick is to know when to stop deltafying against one\n> base file, and start over with another. If you switch to a new keyframe too\n> often, you obviously lose some potential savings. But if you don't switch\n> often enough, you end up repeating the same data in too many delta files.\n\nThat's why multiple combinations should be tried. And to keep things \nunder control then a new argument specifying the delta \"distance\" might \nlimit the number of trials.\n\n> A maximum delta size of 10% turned out to be ideal for at least the \"fs\"\n> tree. 8% was significantly worse, as was 15%. (The ideal size depends on how\n> big the average change is: the smaller the average change, the smaller the max\n> delta size should be).\n\nIn fact it seems that deltas might be significantly harder to compress. \nTherefore a test on the resulting file should probably be done as well \nto make sure we don't end up with a delta larger than the original \nobject.\n\n> > ... but then the ultimate solution is to try out all possible references\n> > within a given list. My git-deltafy-script already finds out the list of\n> > objects belonging to the same file. Maybe git-mkdelta should try all\n> > combinations between them. This way a deeper delta chain could be allowed\n> > for maximum space saving.\n> \n> Yeah. But then you lose the ability to do incremental deltafication, or\n> deltafication on-the-fly.\n\nNot at all. Nothing prevents you from making the latest revision of a \nfile be the reference object and the previous revision turned into a \ndelta against that latest revision, even if it was itself a reference \nobject before. The only thing that must be avoided is a delta loop and \ncurrent mkdelta code takes care of that already.\n\n\nNicolas\n"},{"id":"3512","messageId":"d6g569$hln$1@sea.gmane.org","threadId":"577","inReplyTo":"Pine.LNX.4.62.0505181428170.20274@localhost.localdomain","subject":"Re: [PATCH] improved delta support for git","fromName":"Dan Holmsand","fromEmail":"holmsand@gmail.com","sentAt":"2005-05-18T19:32:06Z","receivedAt":"2005-05-18T19:32:06Z","isPatch":true,"sender":{"key":"holmsand@gmail.com","avatar":"https://gravatar.com/avatar/5c722084bafd85e754a02efad01fe69107eb6f393253c49232c5c9f7faa974df?d=mp&s=160"},"body":"Nicolas Pitre wrote:\n> On Wed, 18 May 2005, Dan Holmsand wrote:\n>>Nicolas Pitre wrote:\n>>It's probably better to skip deltafication of very small files altogether. Big\n>>pain for small gain, and all that.\n> \n> No, that's not what I mean.\n> \n> Suppose a large source file that may change only one line between two \n> versions. The delta may therefore end up being only a few bytes long. \n> Compressing a few bytes with zlib creates a _larger_ file than the \n> original few bytes.\n\nOh, I see. You're right, of course. I doubt, however, that there are \nreally large gains to be made, measured in bytes; since small files tend \nto be small :-) It might nevertheless be worthwhile to skip processing \nof really small files, though, as there's basically no hope of gaining \nanything by deltafication.\n\nAnyway, I've also noticed that deltas compress a lot worse than regular \nblobs. In particular, \"complex deltas\" (i.e. small changes on lines \n1,3,5,9,12, etc.), compress poorly. That might explain why my simplistic \n\"depth-one-deltas-against-a-common-keyframe\" method works comparatively \nwell, as that should tend to cleaner deltas from time to time (i.e. \nchunk on lines 1-12 got replaced by new stuff), that ought to be easier \nto compress.\n\n>>>Well, any delta object smaller than its original object saves space, even if\n>>>it's 75% of the original size. But...\n>>\n>>That's not true if you want to keep the delta chain length down (and thus\n>>performance up).\n> \n> Sure. That's why I added the -d switch to mkdelta. But if you can fit \n> a delta which is 75% the size of its original object size then you still \n> save 25% of the space, regardless of the delta chain length.\n\nOk, I guess we're talking about slightly different things here. I was \ntalking about my simple-and-fast method of processing one new version of \nan object at a time, deltafying each new version against the first \nprevious non-deltafied one. If you, in that scenario, allow use of up to \n75% sized deltas, on average delta size will probably be something like 37%.\n\n> In fact it seems that deltas might be significantly harder to compress. \n> Therefore a test on the resulting file should probably be done as well \n> to make sure we don't end up with a delta larger than the original \n> object.\n\nYeah (see above). That's just one of the things I cheated my way out of, \nby limiting delta size to 10% (I trusting that compression doesn't \nincrease size by 90%).\n\n>>>... but then the ultimate solution is to try out all possible references\n>>>within a given list. My git-deltafy-script already finds out the list of\n>>>objects belonging to the same file. Maybe git-mkdelta should try all\n>>>combinations between them. This way a deeper delta chain could be allowed\n>>>for maximum space saving.\n>>\n>>Yeah. But then you lose the ability to do incremental deltafication, or\n>>deltafication on-the-fly.\n> \n> \n> Not at all. Nothing prevents you from making the latest revision of a \n> file be the reference object and the previous revision turned into a \n> delta against that latest revision, even if it was itself a reference \n> object before. The only thing that must be avoided is a delta loop and \n> current mkdelta code takes care of that already.\n\nSure. But there's some downside to modifying already existing objects. \nIn particular, downloads using the existing methods (both http and \nrsync) won't get your new, smaller objects. If someone is pulling from a \ndeltafied repository often enough, and the objects of the top-most \ncommit are always non-deltafied, they will never see any deltas. Object \nimmutability is a really good thing.\n\nAnd there might be some performance issues involved, if you'd like to do \ndeltafying at commit-time (not that I've actually tried this, or \nanything)...\n\nThanks for your comments!\n\n/dan\n\n"}]}