{"thread":{"id":"8317","subject":"[PATCH] improve delta long block matching with big files","startedAt":"2007-05-26T01:38:58Z","lastAt":"2007-05-26T01:38:58Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"43317","messageId":"alpine.LFD.0.99.0705252119200.3366@xanadu.home","threadId":"8317","inReplyTo":null,"subject":"[PATCH] improve delta long block matching with big files","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-26T01:38:58Z","receivedAt":"2007-05-26T01:38:58Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"Martin Koegler noted that create_delta() performs a new hash lookup\nafter every block copy encoding which are currently limited to 64KB.\n\nIn case of larger identical blocks, the next hash lookup would normally\npoint to the next 64KB block in the reference buffer and multiple block\ncopy operations will be consecutively encoded.\n\nIt is however possible that the reference buffer be sparsely indexed if\nhash buckets have been trimmed down in create_delta_index() when hashing\nof the reference buffer isn't well balanced.  In that case the hash\nlookup following a block copy might fail to match anything and the fact\nthat the reference buffer still matches beyond the previous 64KB block\nwill be missed.\n\nLet's rework the code so that buffer comparison isn't bounded to 64KB\nanymore.  The match size should be as large as possible up front and\nonly then should multiple block copy be encoded to cover it all.\nAlso, fewer hash lookups will be performed in the end.\n\nAccording to Martin, this patch should reduce his 92MB pack down to 75MB\nwith the dataset he has.\n\nTests performed on the Linux kernel repo show a slightly smaller pack and\na slightly faster repack.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/diff-delta.c b/diff-delta.c\nindex 9f998d0..09e6bcd 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -246,7 +246,7 @@ 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, val;\n+\tunsigned int i, outpos, outsize, moff, msize, val;\n \tint inscnt;\n \tconst unsigned char *ref_data, *ref_top, *data, *top;\n \tunsigned char *out;\n@@ -291,30 +291,33 @@ create_delta(const struct delta_index *index,\n \t}\n \tinscnt = i;\n \n+\tmoff = 0;\n+\tmsize = 0;\n \twhile (data < top) {\n-\t\tunsigned int moff = 0, msize = 0;\n-\t\tstruct index_entry *entry;\n-\t\tval ^= U[data[-RABIN_WINDOW]];\n-\t\tval = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];\n-\t\ti = val & index->hash_mask;\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\tif (msize < 4096) {\n+\t\t\tstruct index_entry *entry;\n+\t\t\tval ^= U[data[-RABIN_WINDOW]];\n+\t\t\tval = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];\n+\t\t\ti = val & index->hash_mask;\n+\t\t\tfor (entry = index->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 <= 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\tif (msize >= 4096) /* good enough */\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \n@@ -327,27 +330,13 @@ create_delta(const struct delta_index *index,\n \t\t\t\tout[outpos - inscnt - 1] = inscnt;\n \t\t\t\tinscnt = 0;\n \t\t\t}\n+\t\t\tmsize = 0;\n \t\t} else {\n+\t\t\tunsigned int left;\n \t\t\tunsigned char *op;\n \n-\t\t\tif (msize >= RABIN_WINDOW) {\n-\t\t\t\tconst unsigned char *sk;\n-\t\t\t\tsk = data + msize - RABIN_WINDOW;\n-\t\t\t\tval = 0;\n-\t\t\t\tfor (i = 0; i < RABIN_WINDOW; i++)\n-\t\t\t\t\tval = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];\n-\t\t\t} else {\n-\t\t\t\tconst unsigned char *sk = data + 1;\n-\t\t\t\tfor (i = 1; i < msize; i++) {\n-\t\t\t\t\tval ^= U[sk[-RABIN_WINDOW]];\n-\t\t\t\t\tval = ((val << 8) | *sk++) ^ T[val >> RABIN_SHIFT];\n-\t\t\t\t}\n-\t\t\t}\n-\n \t\t\tif (inscnt) {\n \t\t\t\twhile (moff && ref_data[moff-1] == data[-1]) {\n-\t\t\t\t\tif (msize == 0x10000)\n-\t\t\t\t\t\tbreak;\n \t\t\t\t\t/* we can match one byte back */\n \t\t\t\t\tmsize++;\n \t\t\t\t\tmoff--;\n@@ -363,23 +352,40 @@ create_delta(const struct delta_index *index,\n \t\t\t\tinscnt = 0;\n \t\t\t}\n \n-\t\t\tdata += msize;\n+\t\t\t/* A copy op is currently limited to 64KB (pack v2) */\n+\t\t\tleft = (msize < 0x10000) ? 0 : (msize - 0x10000);\n+\t\t\tmsize -= left;\n+\n \t\t\top = 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+\t\t\tif (moff & 0x000000ff)\n+\t\t\t\tout[outpos++] = moff >> 0,  i |= 0x01;\n+\t\t\tif (moff & 0x0000ff00)\n+\t\t\t\tout[outpos++] = moff >> 8,  i |= 0x02;\n+\t\t\tif (moff & 0x00ff0000)\n+\t\t\t\tout[outpos++] = moff >> 16, i |= 0x04;\n+\t\t\tif (moff & 0xff000000)\n+\t\t\t\tout[outpos++] = moff >> 24, 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+\t\t\tif (msize & 0x00ff)\n+\t\t\t\tout[outpos++] = msize >> 0, i |= 0x10;\n+\t\t\tif (msize & 0xff00)\n+\t\t\t\tout[outpos++] = msize >> 8, i |= 0x20;\n \n \t\t\t*op = i;\n+\n+\t\t\tdata += msize;\n+\t\t\tmoff += msize;\n+\t\t\tmsize = left;\n+\n+\t\t\tif (msize < 4096) {\n+\t\t\t\tint j;\n+\t\t\t\tval = 0;\n+\t\t\t\tfor (j = -RABIN_WINDOW; j < 0; j++)\n+\t\t\t\t\tval = ((val << 8) | data[j])\n+\t\t\t\t\t      ^ T[val >> RABIN_SHIFT];\n+\t\t\t}\n \t\t}\n \n \t\tif (outpos >= outsize - MAX_OP_SIZE) {\n"}]}