{"thread":{"id":"3431","subject":"[PATCH] diff-delta: big code simplification","startedAt":"2006-02-22T01:43:17Z","lastAt":"2006-02-22T01:43:17Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"16553","messageId":"Pine.LNX.4.64.0602212041480.5606@localhost.localdomain","threadId":"3431","inReplyTo":null,"subject":"[PATCH] diff-delta: big code simplification","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-02-22T01:43:17Z","receivedAt":"2006-02-22T01:43:17Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nThis is much smaller and hopefully clearer code now.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\n diff-delta.c |  235 +++++++++++++++++++++-------------------------------------\n 1 files changed, 87 insertions(+), 148 deletions(-)\n\n167f85034d634944e90f6bff683d74ec680bb331\ndiff --git a/diff-delta.c b/diff-delta.c\nindex ac992e2..2ed5984 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -19,8 +19,9 @@\n  */\n \n #include <stdlib.h>\n+#include <string.h>\n+#include <zlib.h>\n #include \"delta.h\"\n-#include \"zlib.h\"\n \n \n /* block size: min = 16, max = 64k, power of 2 */\n@@ -29,123 +30,54 @@\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-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-\tint isize, nsize;\n-\tchanode_t *ancur;\n-} chastore_t;\n-\n-static void cha_init(chastore_t *cha, int isize, int icount)\n-{\n-\tcha->isize = isize;\n-\tcha->nsize = icount * isize;\n-\tcha->ancur = NULL;\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 = cha->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->ancur;\n-\twhile (cur) {\n-\t\tchanode_t *tmp = cur;\n-\t\tcur = cur->next;\n-\t\tfree(tmp);\n-\t}\n-}\n+#define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift))\n \n-typedef struct s_bdrecord {\n-\tstruct s_bdrecord *next;\n-\tunsigned int fp;\n+struct index {\n \tconst unsigned char *ptr;\n-} bdrecord_t;\n-\n-typedef struct s_bdfile {\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 *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-\ttop = buf + bufsize;\n-\tdata = buf + (bufsize / BLK_SIZE) * BLK_SIZE;\n-\tif (data == top)\n+\tunsigned int val;\n+\tstruct index *next;\n+};\n+\n+static struct index ** delta_index(const unsigned char *buf,\n+\t\t\t\t   unsigned long bufsize,\n+\t\t\t\t   unsigned int *hash_shift)\n+{\n+\tunsigned int hsize, hshift, entries, blksize, i;\n+\tconst unsigned char *data;\n+\tstruct index *entry, **hash;\n+\tvoid *mem;\n+\n+\t/* determine index hash size */\n+\tentries = (bufsize + BLK_SIZE - 1) / BLK_SIZE;\n+\thsize = entries / 4;\n+\tfor (i = 4; (1 << i) < hsize && i < 16; i++);\n+\thsize = 1 << i;\n+\thshift = 32 - i;\n+\t*hash_shift = hshift;\n+\n+\t/* allocate lookup index */\n+\tmem = malloc(hsize * sizeof(*hash) + entries * sizeof(*entry));\n+\tif (!mem)\n+\t\treturn NULL;\n+\thash = mem;\n+\tentry = mem + hsize * sizeof(*hash);\n+\tmemset(hash, 0, hsize * sizeof(*hash));\n+\n+\t/* then populate it */\n+\tdata = buf + entries * BLK_SIZE - BLK_SIZE;\n+\tblksize = bufsize - (data - buf);\n+\twhile (data >= buf) {\n+\t\tunsigned int val = adler32(0, data, blksize);\n+\t\ti = HASH(val, hshift);\n+\t\tentry->ptr = data;\n+\t\tentry->val = val;\n+\t\tentry->next = hash[i];\n+\t\thash[i] = entry++;\n+\t\tblksize = BLK_SIZE;\n \t\tdata -= BLK_SIZE;\n+ \t}\n \n-\tfor ( ; data >= buf; 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+\treturn hash;\n }\n \n /* provide the size of the copy opcode given the block offset and size */\n@@ -161,23 +93,24 @@ void *diff_delta(void *from_buf, unsigne\n \t\t unsigned long *delta_size,\n \t\t unsigned long max_size)\n {\n-\tunsigned int i, outpos, outsize, inscnt, csize, msize, moff;\n-\tunsigned int fp;\n-\tconst unsigned char *ref_data, *ref_top, *data, *top, *ptr1, *ptr2;\n-\tunsigned char *out, *orig;\n-\tbdrecord_t *brec;\n-\tbdfile_t bdf;\n+\tunsigned int i, outpos, outsize, inscnt, hash_shift;\n+\tconst unsigned char *ref_data, *ref_top, *data, *top;\n+\tunsigned char *out;\n+\tstruct index *entry, **hash;\n \n-\tif (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))\n+\tif (!from_size || !to_size)\n+\t\treturn NULL;\n+\thash = delta_index(from_buf, from_size, &hash_shift);\n+\tif (!hash)\n \t\treturn NULL;\n-\t\n+\n \toutpos = 0;\n \toutsize = 8192;\n \tif (max_size && outsize >= max_size)\n \t\toutsize = max_size + MAX_OP_SIZE + 1;\n \tout = malloc(outsize);\n \tif (!out) {\n-\t\tdelta_cleanup(&bdf);\n+\t\tfree(hash);\n \t\treturn NULL;\n \t}\n \n@@ -205,28 +138,32 @@ void *diff_delta(void *from_buf, unsigne\n \t}\n \n \tinscnt = 0;\n-\tmoff = 0;\n+\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 = ref_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 - ref_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\tunsigned int moff = 0, msize = 0;\n+\t\tunsigned int blksize = MIN(top - data, BLK_SIZE);\n+\t\tunsigned int val = adler32(0, data, blksize);\n+\t\ti = HASH(val, hash_shift);\n+\t\tfor (entry = hash[i]; entry; entry = entry->next) {\n+\t\t\tconst unsigned char *ref = entry->ptr;\n+\t\t\tconst unsigned char *src = data;\n+\t\t\tunsigned int ref_size = ref_top - ref;\n+\t\t\tif (entry->val != val)\n+\t\t\t\tcontinue;\n+\t\t\tif (ref_size > top - src)\n+\t\t\t\tref_size = top - src;\n+\t\t\twhile (ref_size && *src++ == *ref) {\n+\t\t\t\tref++;\n+\t\t\t\tref_size--;\n+\t\t\t}\n+\t\t\tref_size = ref - entry->ptr;\n+\t\t\tif (ref_size > msize) {\n+\t\t\t\t/* this is our best match so far */\n+\t\t\t\tmoff = entry->ptr - ref_data;\n+\t\t\t\tmsize = ref_size;\n+\t\t\t\tif (msize >= 0x10000) {\n+\t\t\t\t\tmsize = 0x10000;\n+\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t}\n \t\t}\n@@ -241,13 +178,15 @@ void *diff_delta(void *from_buf, unsigne\n \t\t\t\tinscnt = 0;\n \t\t\t}\n \t\t} else {\n+\t\t\tunsigned char *op;\n+\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\top = out + outpos++;\n \t\t\ti = 0x80;\n \n \t\t\tif (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }\n@@ -262,7 +201,7 @@ void *diff_delta(void *from_buf, unsigne\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\t*op = i;\n \t\t}\n \n \t\tif (outpos >= outsize - MAX_OP_SIZE) {\n@@ -276,7 +215,7 @@ void *diff_delta(void *from_buf, unsigne\n \t\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\tfree(hash);\n \t\t\t\treturn NULL;\n \t\t\t}\n \t\t}\n@@ -285,7 +224,7 @@ void *diff_delta(void *from_buf, unsigne\n \tif (inscnt)\n \t\tout[outpos - inscnt - 1] = inscnt;\n \n-\tdelta_cleanup(&bdf);\n+\tfree(hash);\n \t*delta_size = outpos;\n \treturn out;\n }\n-- \n1.2.2.g6643-dirty\n"}]}