{"thread":{"id":"659","subject":"[PATCH] Deltification library work by Nicolas Pitre.","startedAt":"2005-05-19T10:28:39Z","lastAt":"2005-05-19T17:39:20Z","messageCount":8,"participants":["Junio C Hamano","Nicolas Pitre","Linus Torvalds","Davide Libenzi"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"3540","messageId":"7vwtpv1pd4.fsf@assigned-by-dhcp.cox.net","threadId":"659","inReplyTo":null,"subject":"[PATCH] Deltification library work by Nicolas Pitre.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T10:28:39Z","receivedAt":"2005-05-19T10:28:39Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is stolen from the deltification patch by Nicolas Pitre.\nAlthough the deltification patch has not been submitted for the\ninclusion, the library part here is useful for the rename\ndetection logic in the diff work I have been doing.  The next\npatch will depend on this, so if Nico is OK with this one,\nplease consider inclusion of this patch.  This does not include\nthe main part of Nico's work, which is to delitify repository\nobjects.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\nMakefile     |    2 \ndelta.h      |    6 +\ndiff-delta.c |  330 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n3 files changed, 337 insertions(+), 1 deletion(-)\ndelta.h (. --> 100644)\ndiff-delta.c (. --> 100644)\n\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -36,7 +36,7 @@\n \t$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(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\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h blob.h tree.h commit.h tag.h\n \ndiff --git a/delta.h b/delta.h\nnew file mode 100644\n--- /dev/null\n+++ b/delta.h\n@@ -0,0 +1,6 @@\n+/*\n+ * Copyright (c) 2005 Nicolas Pitre <nico@cam.org>\n+ */\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);\ndiff --git a/diff-delta.c b/diff-delta.c\nnew file mode 100644\n--- /dev/null\n+++ b/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 <davidel@xmailserver.org>\n+ *  Copyright (C) 2003\tDavide Libenzi\n+ *\n+ *  Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (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 <stdlib.h>\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+}\n------------------------------------------------\n\n"},{"id":"3548","messageId":"Pine.LNX.4.62.0505191019180.20274@localhost.localdomain","threadId":"659","inReplyTo":"7vwtpv1pd4.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Deltification library work by Nicolas Pitre.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-19T14:27:14Z","receivedAt":"2005-05-19T14:27:14Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 19 May 2005, Junio C Hamano wrote:\n\n> This is stolen from the deltification patch by Nicolas Pitre.\n> Although the deltification patch has not been submitted for the\n> inclusion, the library part here is useful for the rename\n> detection logic in the diff work I have been doing.  The next\n> patch will depend on this, so if Nico is OK with this one,\n> please consider inclusion of this patch.\n\nI'd prefer if the following patch was applied instead, following the \npatch separation I've done already.\n\n=====\n\nThis patch adds basic library functions to create and replay delta \ninformation. Also included is a test-delta utility to validate the code.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\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 <davidel@xmailserver.org>\n+ *  Copyright (C) 2003\tDavide Libenzi\n+ *\n+ *  Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (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 <stdlib.h>\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@@ -36,9 +36,9 @@\n \t$(INSTALL) $(PROG) $(SCRIPTS) $(dest)$(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+LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h\n \n LIB_H += strbuf.h\n LIB_OBJS += strbuf.o\n@@ -72,6 +72,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 <nico@cam.org>\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 <stdlib.h>\n+#include <string.h>\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 <nico@cam.org>\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 <stdio.h>\n+#include <unistd.h>\n+#include <string.h>\n+#include <fcntl.h>\n+#include <sys/types.h>\n+#include <sys/stat.h>\n+#include <sys/mman.h>\n+#include \"delta.h\"\n+\n+static const char *usage =\n+\t\"test-delta (-d|-p) <from_file> <data_file> <out_file>\";\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":"3549","messageId":"Pine.LNX.4.58.0505190736020.2322@ppc970.osdl.org","threadId":"659","inReplyTo":"Pine.LNX.4.62.0505191019180.20274@localhost.localdomain","subject":"Re: [PATCH] Deltification library work by Nicolas Pitre.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-19T14:38:23Z","receivedAt":"2005-05-19T14:38:23Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 19 May 2005, Nicolas Pitre wrote:\n> \n> I'd prefer if the following patch was applied instead, following the \n> patch separation I've done already.\n\nSure. I'll apply this one and merge in Junio's rename on top of it, but I \nwanted to verify one thing first:\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\nI don't know the different LGPL versions, so can somebody verify that LGPL\n2.1 is fully compatible with GPLv2...\n\nIn fact I'd prefer to have that notice in the code to make it obvious that \nthe LGPL becomes the GPLv2 when linked into the rest of git.\n\n\t\tLinus\n"},{"id":"3550","messageId":"Pine.LNX.4.62.0505191104410.20274@localhost.localdomain","threadId":"659","inReplyTo":"Pine.LNX.4.58.0505190736020.2322@ppc970.osdl.org","subject":"Re: [PATCH] Deltification library work by Nicolas Pitre.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-19T15:14:04Z","receivedAt":"2005-05-19T15:14:04Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 19 May 2005, Linus Torvalds wrote:\n\n> Sure. I'll apply this one and merge in Junio's rename on top of it, but I \n> wanted to verify one thing first:\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> I don't know the different LGPL versions, so can somebody verify that LGPL\n> 2.1 is fully compatible with GPLv2...\n> \n> In fact I'd prefer to have that notice in the code to make it obvious that \n> the LGPL becomes the GPLv2 when linked into the rest of git.\n\nI don't mind switching it to GPL v2 if I'm allowed to.  I kept LGPL v2.1 \nfor that file since that's the license used for xdiff where significant \nportion of that file has been copied from.\n\nIn fact I think the code in that file might be simplified even further \neventually, at which point there  might not be much of the original code \nleft anymore and the license switched to GPL v2.  But in the mean time \nsomeone else with better knowledge of GPL vs LGPL interaction is needed \nto give advice.\n\n\nNicolas\n"},{"id":"3552","messageId":"Pine.LNX.4.58.0505190833380.2322@ppc970.osdl.org","threadId":"659","inReplyTo":"Pine.LNX.4.58.0505190736020.2322@ppc970.osdl.org","subject":"Re: [PATCH] Deltification library work by Nicolas Pitre.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-05-19T15:36:20Z","receivedAt":"2005-05-19T15:36:20Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n[ This goes to the list because Davide can apparently receive the list \n   emails, but for some reason apparently doesn't like my osdl.org \n   address ]\n\nDavide,\n\nwould you mind signing off on me adding the lines\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+ *  Use of this within git automatically means that the LGPL\n+ *  licensing gets turned into GPLv2 within this project. \n  */\n\n(If you just send me an ack and your \"signed-off-by\" line, I'll edit \nNico's patch appropriately, and check it in with all of our sign-offs).\n\nThat way there's no question about the dual-licensing.\n\n\t\tLinus\n"},{"id":"3553","messageId":"Pine.LNX.4.63.0505190837430.3895@localhost.localdomain","threadId":"659","inReplyTo":"Pine.LNX.4.58.0505190833380.2322@ppc970.osdl.org","subject":"Re: [PATCH] Deltification library work by Nicolas Pitre.","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2005-05-19T15:40:10Z","receivedAt":"2005-05-19T15:40:10Z","isPatch":true,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Thu, 19 May 2005, Linus Torvalds wrote:\n\n>\n> [ This goes to the list because Davide can apparently receive the list\n>   emails, but for some reason apparently doesn't like my osdl.org\n>   address ]\n\n[Just greylist timeout ;)]\n\n\n> Davide,\n>\n> would you mind signing off on me adding the lines\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> + *  Use of this within git automatically means that the LGPL\n> + *  licensing gets turned into GPLv2 within this project.\n>  */\n\nSigned-off-by: Davide Libenzi <davidel@xmailserver.org>\n\n\n- Davide\n\n"},{"id":"3560","messageId":"7vekc3178w.fsf@assigned-by-dhcp.cox.net","threadId":"659","inReplyTo":"Pine.LNX.4.62.0505191104410.20274@localhost.localdomain","subject":"Re: [PATCH] Deltification library work by Nicolas Pitre.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-19T16:59:59Z","receivedAt":"2005-05-19T16:59:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"NP\" == Nicolas Pitre <nico@cam.org> writes:\n\nNP> In fact I think the code in that file might be simplified even further \nNP> eventually, at which point there  might not be much of the original code \nNP> left anymore and the license switched to GPL v2.\n\nI am afraid that kind of code transformation would not change\nthe copyright issues.\n\n"},{"id":"3563","messageId":"Pine.LNX.4.62.0505191338210.20274@localhost.localdomain","threadId":"659","inReplyTo":"7vekc3178w.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Deltification library work by Nicolas Pitre.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-19T17:39:20Z","receivedAt":"2005-05-19T17:39:20Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 19 May 2005, Junio C Hamano wrote:\n\n> >>>>> \"NP\" == Nicolas Pitre <nico@cam.org> writes:\n> \n> NP> In fact I think the code in that file might be simplified even further \n> NP> eventually, at which point there  might not be much of the original code \n> NP> left anymore and the license switched to GPL v2.\n> \n> I am afraid that kind of code transformation would not change\n> the copyright issues.\n\nMaybe you're right.  Anyway it is a non issue now.\n\n\nNicolas\n"}]}