{"thread":{"id":"3961","subject":"[PATCH] split the diff-delta interface","startedAt":"2006-04-25T03:07:47Z","lastAt":"2006-04-25T03:07:47Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"19069","messageId":"Pine.LNX.4.64.0604242258160.18520@localhost.localdomain","threadId":"3961","inReplyTo":null,"subject":"[PATCH] split the diff-delta interface","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-25T03:07:47Z","receivedAt":"2006-04-25T03:07:47Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This patch splits the diff-delta interface into index creation and delta\ngeneration.  A wrapper is provided to preserve the diff-delta() call.\n\nThis will allow for an optimization in pack-objects.c where the source \nobject could be fixed and a full window of objects tentatively tried \nagainst \nthat same source object without recomputing the source index each time.\n\nThis patch only restructure things, plus a couple cleanups for good \nmeasure. There is no performance change yet.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n\n\ndiff --git a/delta.h b/delta.h\nindex 9464f3e..9ef44c1 100644\n--- a/delta.h\n+++ b/delta.h\n@@ -1,12 +1,73 @@\n #ifndef DELTA_H\n #define DELTA_H\n \n-/* handling of delta buffers */\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, unsigned long max_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+/* opaque object for delta index */\n+struct delta_index;\n+\n+/*\n+ * create_delta_index: compute index data from given buffer\n+ *\n+ * This returns a pointer to a struct delta_index that should be passed to\n+ * subsequent create_delta() calls, or to free_delta_index().  A NULL pointer\n+ * is returned on failure.  The given buffer must not be freed nor altered\n+ * before free_delta_index() is called.  The returned pointer must be freed\n+ * using free_delta_index().\n+ */\n+extern struct delta_index *\n+create_delta_index(const void *buf, unsigned long bufsize);\n+\n+/*\n+ * free_delta_index: free the index created by create_delta_index()\n+ */\n+extern void free_delta_index(struct delta_index *index);\n+\n+/*\n+ * create_delta: create a delta from given index for the given buffer\n+ *\n+ * This function may be called multiple times with different buffers using\n+ * the same delta_index pointer.  If max_delta_size is non-zero and the\n+ * resulting delta is to be larger than max_delta_size then NULL is returned.\n+ * On success, a non-NULL pointer to the buffer with the delta data is\n+ * returned and *delta_size is updated with its size.  The returned buffer\n+ * must be freed by the caller.\n+ */\n+extern void *\n+create_delta(const struct delta_index *index,\n+\t     const void *buf, unsigned long bufsize,\n+\t     unsigned long *delta_size, unsigned long max_delta_size);\n+\n+/*\n+ * diff_delta: create a delta from source buffer to target buffer\n+ *\n+ * If max_delta_size is non-zero and the resulting delta is to be larger\n+ * than max_delta_size then NULL is returned.  On success, a non-NULL\n+ * pointer to the buffer with the delta data is returned and *delta_size is\n+ * updated with its size.  The returned buffer must be freed by the caller.\n+ */\n+static inline void *\n+diff_delta(const void *src_buf, unsigned long src_bufsize,\n+\t   const void *trg_buf, unsigned long trg_bufsize,\n+\t   unsigned long *delta_size, unsigned long max_delta_size)\n+{\n+\tstruct delta_index *index = create_delta_index(src_buf, src_bufsize);\n+\tif (index) {\n+\t\tvoid *delta = create_delta(index, trg_buf, trg_bufsize, \n+\t\t\t\t\t   delta_size, max_delta_size);\n+\t\tfree_delta_index(index);\n+\t\treturn delta;\n+\t}\n+\treturn NULL;\n+}\n+\n+/*\n+ * patch_delta: recreate target buffer given source buffer and delta data\n+ *\n+ * On success, a non-NULL pointer to the target buffer is returned and\n+ * *trg_bufsize is updated with its size.  On failure a NULL pointer is\n+ * returned.  The returned buffer must be freed by the caller.\n+ */\n+extern void *patch_delta(const void *src_buf, unsigned long src_size,\n+\t\t\t const void *delta_buf, unsigned long delta_size,\n \t\t\t unsigned long *dst_size);\n \n /* the smallest possible delta size is 4 bytes */\n@@ -14,7 +75,7 @@ #define DELTA_SIZE_MIN\t4\n \n /*\n  * This must be called twice on the delta data buffer, first to get the\n- * expected reference buffer size, and again to get the result buffer size.\n+ * expected source buffer size, and again to get the target buffer size.\n  */\n static inline unsigned long get_delta_hdr_size(const unsigned char **datap,\n \t\t\t\t\t       const unsigned char *top)\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 1188b31..fdedf94 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -27,53 +27,70 @@ #include \"delta.h\"\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+/* maximum hash entry list for the same hash bucket */\n+#define HASH_LIMIT 64\n \n #define GR_PRIME 0x9e370001\n #define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift))\n \n-struct index {\n+struct index_entry {\n \tconst unsigned char *ptr;\n \tunsigned int val;\n-\tstruct index *next;\n+\tstruct index_entry *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 long trg_bufsize,\n-\t\t\t\t   unsigned int *hash_shift)\n+struct delta_index {\n+\tconst void *src_buf;\n+\tunsigned long src_size;\n+\tunsigned int hash_shift;\n+\tstruct index_entry *hash[0];\n+};\n+\n+struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)\n {\n-\tunsigned int i, hsize, hshift, hlimit, entries, *hash_count;\n-\tconst unsigned char *data;\n-\tstruct index *entry, **hash;\n+\tunsigned int i, hsize, hshift, entries, *hash_count;\n+\tconst unsigned char *data, *buffer = buf;\n+\tstruct delta_index *index;\n+\tstruct index_entry *entry, **hash;\n \tvoid *mem;\n \n+\tif (!buf || !bufsize)\n+\t\treturn NULL;\n+\n \t/* determine index hash size */\n \tentries = bufsize  / BLK_SIZE;\n \thsize = entries / 4;\n \tfor (i = 4; (1 << i) < hsize && i < 31; 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+\tmem = malloc(sizeof(*index) +\n+\t\t     sizeof(*hash) * hsize +\n+\t\t     sizeof(*entry) * entries);\n \tif (!mem)\n \t\treturn NULL;\n+\tindex = mem;\n+\tmem = index + 1;\n \thash = mem;\n-\tentry = mem + hsize * sizeof(*hash);\n+\tmem = hash + hsize;\n+\tentry = mem;\n+\n+\tindex->src_buf = buf;\n+\tindex->src_size = bufsize;\n+\tindex->hash_shift = hshift;\n \tmemset(hash, 0, hsize * sizeof(*hash));\n \n \t/* allocate an array to count hash entries */\n \thash_count = calloc(hsize, sizeof(*hash_count));\n \tif (!hash_count) {\n-\t\tfree(hash);\n+\t\tfree(index);\n \t\treturn NULL;\n \t}\n \n \t/* then populate the index */\n-\tdata = buf + entries * BLK_SIZE - BLK_SIZE;\n-\twhile (data >= buf) {\n+\tdata = buffer + entries * BLK_SIZE - BLK_SIZE;\n+\twhile (data >= buffer) {\n \t\tunsigned int val = adler32(0, data, BLK_SIZE);\n \t\ti = HASH(val, hshift);\n \t\tentry->ptr = data;\n@@ -91,27 +108,18 @@ static struct index ** delta_index(const\n \t * bucket that would bring us to O(m*n) computing costs (m and n\n \t * corresponding to reference and target buffer sizes).\n \t *\n-\t * The more the target buffer is large, the more it is important to\n-\t * have small entry lists for each hash buckets.  With such a limit\n-\t * the cost is bounded to something more like O(m+n).\n-\t */\n-\thlimit = (1 << 26) / trg_bufsize;\n-\tif (hlimit < 4*BLK_SIZE)\n-\t\thlimit = 4*BLK_SIZE;\n-\n-\t/*\n-\t * Now make sure none of the hash buckets has more entries than\n+\t * Make sure none of the hash buckets has more entries than\n \t * we're willing to test.  Otherwise we cull the entry list\n \t * uniformly to still preserve a good repartition across\n \t * the reference buffer.\n \t */\n \tfor (i = 0; i < hsize; i++) {\n-\t\tif (hash_count[i] < hlimit)\n+\t\tif (hash_count[i] < HASH_LIMIT)\n \t\t\tcontinue;\n \t\tentry = hash[i];\n \t\tdo {\n-\t\t\tstruct index *keep = entry;\n-\t\t\tint skip = hash_count[i] / hlimit / 2;\n+\t\t\tstruct index_entry *keep = entry;\n+\t\t\tint skip = hash_count[i] / HASH_LIMIT / 2;\n \t\t\tdo {\n \t\t\t\tentry = entry->next;\n \t\t\t} while(--skip && entry);\n@@ -120,7 +128,12 @@ static struct index ** delta_index(const\n \t}\n \tfree(hash_count);\n \n-\treturn hash;\n+\treturn index;\n+}\n+\n+void free_delta_index(struct delta_index *index)\n+{\n+\tfree(index);\n }\n \n /* provide the size of the copy opcode given the block offset and size */\n@@ -131,21 +144,17 @@ #define COPYOP_SIZE(o, s) \\\n /* the maximum size for any opcode */\n #define MAX_OP_SIZE COPYOP_SIZE(0xffffffff, 0xffffffff)\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-\t\t unsigned long max_size)\n+void *\n+create_delta(const struct delta_index *index,\n+\t     const void *trg_buf, unsigned long trg_size,\n+\t     unsigned long *delta_size, unsigned long max_size)\n {\n \tunsigned int i, outpos, outsize, hash_shift;\n \tint inscnt;\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)\n-\t\treturn NULL;\n-\thash = delta_index(from_buf, from_size, to_size, &hash_shift);\n-\tif (!hash)\n+\tif (!trg_buf || !trg_size)\n \t\treturn NULL;\n \n \toutpos = 0;\n@@ -153,60 +162,55 @@ void *diff_delta(void *from_buf, unsigne\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\tfree(hash);\n+\tif (!out)\n \t\treturn NULL;\n-\t}\n-\n-\tref_data = from_buf;\n-\tref_top = from_buf + from_size;\n-\tdata = to_buf;\n-\ttop = to_buf + to_size;\n \n \t/* store reference buffer size */\n-\tout[outpos++] = from_size;\n-\tfrom_size >>= 7;\n-\twhile (from_size) {\n-\t\tout[outpos - 1] |= 0x80;\n-\t\tout[outpos++] = from_size;\n-\t\tfrom_size >>= 7;\n+\ti = index->src_size;\n+\twhile (i >= 0x80) {\n+\t\tout[outpos++] = i | 0x80;\n+\t\ti >>= 7;\n \t}\n+\tout[outpos++] = i;\n \n \t/* store target buffer size */\n-\tout[outpos++] = to_size;\n-\tto_size >>= 7;\n-\twhile (to_size) {\n-\t\tout[outpos - 1] |= 0x80;\n-\t\tout[outpos++] = to_size;\n-\t\tto_size >>= 7;\n+\ti = trg_size;\n+\twhile (i >= 0x80) {\n+\t\tout[outpos++] = i | 0x80;\n+\t\ti >>= 7;\n \t}\n+\tout[outpos++] = i;\n \n+\tref_data = index->src_buf;\n+\tref_top = ref_data + index->src_size;\n+\tdata = trg_buf;\n+\ttop = trg_buf + trg_size;\n+\thash_shift = index->hash_shift;\n \tinscnt = 0;\n \n \twhile (data < top) {\n \t\tunsigned int moff = 0, msize = 0;\n-\t\tif (data + BLK_SIZE <= top) {\n-\t\t\tunsigned int val = adler32(0, data, BLK_SIZE);\n-\t\t\ti = HASH(val, hash_shift);\n-\t\t\tfor (entry = hash[i]; entry; entry = entry->next) {\n-\t\t\t\tconst unsigned char *ref = entry->ptr;\n-\t\t\t\tconst unsigned char *src = data;\n-\t\t\t\tunsigned int ref_size = ref_top - ref;\n-\t\t\t\tif (entry->val != val)\n-\t\t\t\t\tcontinue;\n-\t\t\t\tif (ref_size > top - src)\n-\t\t\t\t\tref_size = top - src;\n-\t\t\t\tif (ref_size > 0x10000)\n-\t\t\t\t\tref_size = 0x10000;\n-\t\t\t\tif (ref_size <= msize)\n-\t\t\t\t\tbreak;\n-\t\t\t\twhile (ref_size-- && *src++ == *ref)\n-\t\t\t\t\tref++;\n-\t\t\t\tif (msize < ref - entry->ptr) {\n-\t\t\t\t\t/* this is our best match so far */\n-\t\t\t\t\tmsize = ref - entry->ptr;\n-\t\t\t\t\tmoff = entry->ptr - ref_data;\n-\t\t\t\t}\n+\t\tstruct index_entry *entry;\n+\t\tunsigned int val = adler32(0, data, BLK_SIZE);\n+\t\ti = HASH(val, hash_shift);\n+\t\tfor (entry = index->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\tif (ref_size > 0x10000)\n+\t\t\t\tref_size = 0x10000;\n+\t\t\tif (ref_size <= msize)\n+\t\t\t\tbreak;\n+\t\t\twhile (ref_size-- && *src++ == *ref)\n+\t\t\t\tref++;\n+\t\t\tif (msize < ref - entry->ptr) {\n+\t\t\t\t/* this is our best match so far */\n+\t\t\t\tmsize = ref - entry->ptr;\n+\t\t\t\tmoff = entry->ptr - ref_data;\n \t\t\t}\n \t\t}\n \n@@ -271,7 +275,6 @@ 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\tfree(hash);\n \t\t\t\treturn NULL;\n \t\t\t}\n \t\t}\n@@ -280,7 +283,6 @@ void *diff_delta(void *from_buf, unsigne\n \tif (inscnt)\n \t\tout[outpos - inscnt - 1] = inscnt;\n \n-\tfree(hash);\n \t*delta_size = outpos;\n \treturn out;\n }\ndiff --git a/patch-delta.c b/patch-delta.c\nindex d95f0d9..8f318ed 100644\n--- a/patch-delta.c\n+++ b/patch-delta.c\n@@ -13,8 +13,8 @@ #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+void *patch_delta(const void *src_buf, unsigned long src_size,\n+\t\t  const void *delta_buf, unsigned long delta_size,\n \t\t  unsigned long *dst_size)\n {\n \tconst unsigned char *data, *top;\n"}]}