{"thread":{"id":"3993","subject":"[PATCH] replace adler32 with Rabin's polynomial in diff-delta","startedAt":"2006-04-29T04:58:05Z","lastAt":"2006-04-29T04:58:05Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"19241","messageId":"Pine.LNX.4.64.0604290042180.18816@localhost.localdomain","threadId":"3993","inReplyTo":null,"subject":"[PATCH] replace adler32 with Rabin's polynomial in diff-delta","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-29T04:58:05Z","receivedAt":"2006-04-29T04:58:05Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This brings another small repacking speedup for sensibly the same pack \nsize.  On the Linux kernel repo, git-repack -a -f is 3.7% faster for a \n0.4% larger pack.\n\nCredits to Geert Bosch who brought the Rabin's polynomial idea to my \nattention.\n\nThis also eliminate the issue of adler32() reading past the data buffer, \nas noticed by Johannes Schindelin.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\n---\n\ndiff --git a/Makefile b/Makefile\nindex 8ce27a6..c13208f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -609,7 +609,7 @@ test-date$X: test-date.c date.o ctype.o\n \t$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) test-date.c date.o ctype.o\n \n test-delta$X: test-delta.c diff-delta.o patch-delta.o\n-\t$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^ -lz\n+\t$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $^\n \n check:\n \tfor i in *.c; do sparse $(ALL_CFLAGS) $(SPARSE_FLAGS) $$i || exit; done\ndiff --git a/diff-delta.c b/diff-delta.c\nindex fdedf94..a40a89c 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -20,18 +20,106 @@\n \n #include <stdlib.h>\n #include <string.h>\n-#include <zlib.h>\n #include \"delta.h\"\n \n \n-/* block size: min = 16, max = 64k, power of 2 */\n-#define BLK_SIZE 16\n-\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+#define RABIN_SHIFT 23\n+#define RABIN_WINDOW 16\n+\n+static const unsigned int T[256] = {\n+\t0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344,\n+\t0x508c0e37, 0xfbd5bae6, 0x0c7ecf2a, 0xa7277bfb, 0x5acda688, 0xf1941259,\n+\t0x0a41a8bf, 0xa1181c6e, 0x5cf2c11d, 0xf7ab75cc, 0x18fd9e54, 0xb3a42a85,\n+\t0x4e4ef7f6, 0xe5174327, 0x1ec2f9c1, 0xb59b4d10, 0x48719063, 0xe32824b2,\n+\t0x1483517e, 0xbfdae5af, 0x423038dc, 0xe9698c0d, 0x12bc36eb, 0xb9e5823a,\n+\t0x440f5f49, 0xef56eb98, 0x31fb3ca8, 0x9aa28879, 0x6748550a, 0xcc11e1db,\n+\t0x37c45b3d, 0x9c9defec, 0x6177329f, 0xca2e864e, 0x3d85f382, 0x96dc4753,\n+\t0x6b369a20, 0xc06f2ef1, 0x3bba9417, 0x90e320c6, 0x6d09fdb5, 0xc6504964,\n+\t0x2906a2fc, 0x825f162d, 0x7fb5cb5e, 0xd4ec7f8f, 0x2f39c569, 0x846071b8,\n+\t0x798aaccb, 0xd2d3181a, 0x25786dd6, 0x8e21d907, 0x73cb0474, 0xd892b0a5,\n+\t0x23470a43, 0x881ebe92, 0x75f463e1, 0xdeadd730, 0x63f67950, 0xc8afcd81,\n+\t0x354510f2, 0x9e1ca423, 0x65c91ec5, 0xce90aa14, 0x337a7767, 0x9823c3b6,\n+\t0x6f88b67a, 0xc4d102ab, 0x393bdfd8, 0x92626b09, 0x69b7d1ef, 0xc2ee653e,\n+\t0x3f04b84d, 0x945d0c9c, 0x7b0be704, 0xd05253d5, 0x2db88ea6, 0x86e13a77,\n+\t0x7d348091, 0xd66d3440, 0x2b87e933, 0x80de5de2, 0x7775282e, 0xdc2c9cff,\n+\t0x21c6418c, 0x8a9ff55d, 0x714a4fbb, 0xda13fb6a, 0x27f92619, 0x8ca092c8,\n+\t0x520d45f8, 0xf954f129, 0x04be2c5a, 0xafe7988b, 0x5432226d, 0xff6b96bc,\n+\t0x02814bcf, 0xa9d8ff1e, 0x5e738ad2, 0xf52a3e03, 0x08c0e370, 0xa39957a1,\n+\t0x584ced47, 0xf3155996, 0x0eff84e5, 0xa5a63034, 0x4af0dbac, 0xe1a96f7d,\n+\t0x1c43b20e, 0xb71a06df, 0x4ccfbc39, 0xe79608e8, 0x1a7cd59b, 0xb125614a,\n+\t0x468e1486, 0xedd7a057, 0x103d7d24, 0xbb64c9f5, 0x40b17313, 0xebe8c7c2,\n+\t0x16021ab1, 0xbd5bae60, 0x6cb54671, 0xc7ecf2a0, 0x3a062fd3, 0x915f9b02,\n+\t0x6a8a21e4, 0xc1d39535, 0x3c394846, 0x9760fc97, 0x60cb895b, 0xcb923d8a,\n+\t0x3678e0f9, 0x9d215428, 0x66f4eece, 0xcdad5a1f, 0x3047876c, 0x9b1e33bd,\n+\t0x7448d825, 0xdf116cf4, 0x22fbb187, 0x89a20556, 0x7277bfb0, 0xd92e0b61,\n+\t0x24c4d612, 0x8f9d62c3, 0x7836170f, 0xd36fa3de, 0x2e857ead, 0x85dcca7c,\n+\t0x7e09709a, 0xd550c44b, 0x28ba1938, 0x83e3ade9, 0x5d4e7ad9, 0xf617ce08,\n+\t0x0bfd137b, 0xa0a4a7aa, 0x5b711d4c, 0xf028a99d, 0x0dc274ee, 0xa69bc03f,\n+\t0x5130b5f3, 0xfa690122, 0x0783dc51, 0xacda6880, 0x570fd266, 0xfc5666b7,\n+\t0x01bcbbc4, 0xaae50f15, 0x45b3e48d, 0xeeea505c, 0x13008d2f, 0xb85939fe,\n+\t0x438c8318, 0xe8d537c9, 0x153feaba, 0xbe665e6b, 0x49cd2ba7, 0xe2949f76,\n+\t0x1f7e4205, 0xb427f6d4, 0x4ff24c32, 0xe4abf8e3, 0x19412590, 0xb2189141,\n+\t0x0f433f21, 0xa41a8bf0, 0x59f05683, 0xf2a9e252, 0x097c58b4, 0xa225ec65,\n+\t0x5fcf3116, 0xf49685c7, 0x033df00b, 0xa86444da, 0x558e99a9, 0xfed72d78,\n+\t0x0502979e, 0xae5b234f, 0x53b1fe3c, 0xf8e84aed, 0x17bea175, 0xbce715a4,\n+\t0x410dc8d7, 0xea547c06, 0x1181c6e0, 0xbad87231, 0x4732af42, 0xec6b1b93,\n+\t0x1bc06e5f, 0xb099da8e, 0x4d7307fd, 0xe62ab32c, 0x1dff09ca, 0xb6a6bd1b,\n+\t0x4b4c6068, 0xe015d4b9, 0x3eb80389, 0x95e1b758, 0x680b6a2b, 0xc352defa,\n+\t0x3887641c, 0x93ded0cd, 0x6e340dbe, 0xc56db96f, 0x32c6cca3, 0x999f7872,\n+\t0x6475a501, 0xcf2c11d0, 0x34f9ab36, 0x9fa01fe7, 0x624ac294, 0xc9137645,\n+\t0x26459ddd, 0x8d1c290c, 0x70f6f47f, 0xdbaf40ae, 0x207afa48, 0x8b234e99,\n+\t0x76c993ea, 0xdd90273b, 0x2a3b52f7, 0x8162e626, 0x7c883b55, 0xd7d18f84,\n+\t0x2c043562, 0x875d81b3, 0x7ab75cc0, 0xd1eee811\n+};\n+\n+static const unsigned int U[256] = {\n+\t0x00000000, 0x7eb5200d, 0x5633f4cb, 0x2886d4c6, 0x073e5d47, 0x798b7d4a,\n+\t0x510da98c, 0x2fb88981, 0x0e7cba8e, 0x70c99a83, 0x584f4e45, 0x26fa6e48,\n+\t0x0942e7c9, 0x77f7c7c4, 0x5f711302, 0x21c4330f, 0x1cf9751c, 0x624c5511,\n+\t0x4aca81d7, 0x347fa1da, 0x1bc7285b, 0x65720856, 0x4df4dc90, 0x3341fc9d,\n+\t0x1285cf92, 0x6c30ef9f, 0x44b63b59, 0x3a031b54, 0x15bb92d5, 0x6b0eb2d8,\n+\t0x4388661e, 0x3d3d4613, 0x39f2ea38, 0x4747ca35, 0x6fc11ef3, 0x11743efe,\n+\t0x3eccb77f, 0x40799772, 0x68ff43b4, 0x164a63b9, 0x378e50b6, 0x493b70bb,\n+\t0x61bda47d, 0x1f088470, 0x30b00df1, 0x4e052dfc, 0x6683f93a, 0x1836d937,\n+\t0x250b9f24, 0x5bbebf29, 0x73386bef, 0x0d8d4be2, 0x2235c263, 0x5c80e26e,\n+\t0x740636a8, 0x0ab316a5, 0x2b7725aa, 0x55c205a7, 0x7d44d161, 0x03f1f16c,\n+\t0x2c4978ed, 0x52fc58e0, 0x7a7a8c26, 0x04cfac2b, 0x73e5d470, 0x0d50f47d,\n+\t0x25d620bb, 0x5b6300b6, 0x74db8937, 0x0a6ea93a, 0x22e87dfc, 0x5c5d5df1,\n+\t0x7d996efe, 0x032c4ef3, 0x2baa9a35, 0x551fba38, 0x7aa733b9, 0x041213b4,\n+\t0x2c94c772, 0x5221e77f, 0x6f1ca16c, 0x11a98161, 0x392f55a7, 0x479a75aa,\n+\t0x6822fc2b, 0x1697dc26, 0x3e1108e0, 0x40a428ed, 0x61601be2, 0x1fd53bef,\n+\t0x3753ef29, 0x49e6cf24, 0x665e46a5, 0x18eb66a8, 0x306db26e, 0x4ed89263,\n+\t0x4a173e48, 0x34a21e45, 0x1c24ca83, 0x6291ea8e, 0x4d29630f, 0x339c4302,\n+\t0x1b1a97c4, 0x65afb7c9, 0x446b84c6, 0x3adea4cb, 0x1258700d, 0x6ced5000,\n+\t0x4355d981, 0x3de0f98c, 0x15662d4a, 0x6bd30d47, 0x56ee4b54, 0x285b6b59,\n+\t0x00ddbf9f, 0x7e689f92, 0x51d01613, 0x2f65361e, 0x07e3e2d8, 0x7956c2d5,\n+\t0x5892f1da, 0x2627d1d7, 0x0ea10511, 0x7014251c, 0x5facac9d, 0x21198c90,\n+\t0x099f5856, 0x772a785b, 0x4c921c31, 0x32273c3c, 0x1aa1e8fa, 0x6414c8f7,\n+\t0x4bac4176, 0x3519617b, 0x1d9fb5bd, 0x632a95b0, 0x42eea6bf, 0x3c5b86b2,\n+\t0x14dd5274, 0x6a687279, 0x45d0fbf8, 0x3b65dbf5, 0x13e30f33, 0x6d562f3e,\n+\t0x506b692d, 0x2ede4920, 0x06589de6, 0x78edbdeb, 0x5755346a, 0x29e01467,\n+\t0x0166c0a1, 0x7fd3e0ac, 0x5e17d3a3, 0x20a2f3ae, 0x08242768, 0x76910765,\n+\t0x59298ee4, 0x279caee9, 0x0f1a7a2f, 0x71af5a22, 0x7560f609, 0x0bd5d604,\n+\t0x235302c2, 0x5de622cf, 0x725eab4e, 0x0ceb8b43, 0x246d5f85, 0x5ad87f88,\n+\t0x7b1c4c87, 0x05a96c8a, 0x2d2fb84c, 0x539a9841, 0x7c2211c0, 0x029731cd,\n+\t0x2a11e50b, 0x54a4c506, 0x69998315, 0x172ca318, 0x3faa77de, 0x411f57d3,\n+\t0x6ea7de52, 0x1012fe5f, 0x38942a99, 0x46210a94, 0x67e5399b, 0x19501996,\n+\t0x31d6cd50, 0x4f63ed5d, 0x60db64dc, 0x1e6e44d1, 0x36e89017, 0x485db01a,\n+\t0x3f77c841, 0x41c2e84c, 0x69443c8a, 0x17f11c87, 0x38499506, 0x46fcb50b,\n+\t0x6e7a61cd, 0x10cf41c0, 0x310b72cf, 0x4fbe52c2, 0x67388604, 0x198da609,\n+\t0x36352f88, 0x48800f85, 0x6006db43, 0x1eb3fb4e, 0x238ebd5d, 0x5d3b9d50,\n+\t0x75bd4996, 0x0b08699b, 0x24b0e01a, 0x5a05c017, 0x728314d1, 0x0c3634dc,\n+\t0x2df207d3, 0x534727de, 0x7bc1f318, 0x0574d315, 0x2acc5a94, 0x54797a99,\n+\t0x7cffae5f, 0x024a8e52, 0x06852279, 0x78300274, 0x50b6d6b2, 0x2e03f6bf,\n+\t0x01bb7f3e, 0x7f0e5f33, 0x57888bf5, 0x293dabf8, 0x08f998f7, 0x764cb8fa,\n+\t0x5eca6c3c, 0x207f4c31, 0x0fc7c5b0, 0x7172e5bd, 0x59f4317b, 0x27411176,\n+\t0x1a7c5765, 0x64c97768, 0x4c4fa3ae, 0x32fa83a3, 0x1d420a22, 0x63f72a2f,\n+\t0x4b71fee9, 0x35c4dee4, 0x1400edeb, 0x6ab5cde6, 0x42331920, 0x3c86392d,\n+\t0x133eb0ac, 0x6d8b90a1, 0x450d4467, 0x3bb8646a\n+};\n \n struct index_entry {\n \tconst unsigned char *ptr;\n@@ -42,13 +130,13 @@ struct index_entry {\n struct delta_index {\n \tconst void *src_buf;\n \tunsigned long src_size;\n-\tunsigned int hash_shift;\n+\tunsigned int hash_mask;\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, entries, *hash_count;\n+\tunsigned int i, hsize, hmask, entries, *hash_count;\n \tconst unsigned char *data, *buffer = buf;\n \tstruct delta_index *index;\n \tstruct index_entry *entry, **hash;\n@@ -57,12 +145,14 @@ struct delta_index * create_delta_index(\n \tif (!buf || !bufsize)\n \t\treturn NULL;\n \n-\t/* determine index hash size */\n-\tentries = bufsize  / BLK_SIZE;\n+\t/* Determine index hash size.  Note that indexing skips the\n+\t   first byte to allow for optimizing the rabin polynomial\n+\t   initialization in create_delta(). */\n+\tentries = (bufsize - 1)  / RABIN_WINDOW;\n \thsize = entries / 4;\n \tfor (i = 4; (1 << i) < hsize && i < 31; i++);\n \thsize = 1 << i;\n-\thshift = 32 - i;\n+\thmask = hsize - 1;\n \n \t/* allocate lookup index */\n \tmem = malloc(sizeof(*index) +\n@@ -78,7 +168,7 @@ struct delta_index * create_delta_index(\n \n \tindex->src_buf = buf;\n \tindex->src_size = bufsize;\n-\tindex->hash_shift = hshift;\n+\tindex->hash_mask = hmask;\n \tmemset(hash, 0, hsize * sizeof(*hash));\n \n \t/* allocate an array to count hash entries */\n@@ -89,17 +179,19 @@ struct delta_index * create_delta_index(\n \t}\n \n \t/* then populate the index */\n-\tdata = buffer + entries * BLK_SIZE - BLK_SIZE;\n+\tdata = buffer + entries * RABIN_WINDOW - RABIN_WINDOW;\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+\t\tunsigned int val = 0;\n+\t\tfor (i = 1; i <= RABIN_WINDOW; i++)\n+\t\t\tval = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];\n+\t\ti = val & hmask;\n+\t\tentry->ptr = data + RABIN_WINDOW;\n \t\tentry->val = val;\n \t\tentry->next = hash[i];\n \t\thash[i] = entry++;\n \t\thash_count[i]++;\n-\t\tdata -= BLK_SIZE;\n- \t}\n+\t\tdata -= RABIN_WINDOW;\n+\t}\n \n \t/*\n \t * Determine a limit on the number of entries in the same hash\n@@ -136,20 +228,18 @@ void free_delta_index(struct delta_index\n \tfree(index);\n }\n \n-/* provide the size of the copy opcode given the block offset and size */\n-#define COPYOP_SIZE(o, s) \\\n-    (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \\\n-     !!(s & 0xff) + !!(s & 0xff00) + 1)\n-\n-/* the maximum size for any opcode */\n-#define MAX_OP_SIZE COPYOP_SIZE(0xffffffff, 0xffffffff)\n+/*\n+ * The maximum size for any opcode sequence, including the initial header\n+ * plus rabin window plus biggest copy.\n+ */\n+#define MAX_OP_SIZE\t(5 + 5 + 1 + RABIN_WINDOW + 7) \n \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+\tunsigned int i, outpos, outsize, hash_mask, val;\n \tint inscnt;\n \tconst unsigned char *ref_data, *ref_top, *data, *top;\n \tunsigned char *out;\n@@ -185,14 +275,22 @@ create_delta(const struct delta_index *i\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+\thash_mask = index->hash_mask;\n+\n+\toutpos++;\n+\tval = 0;\n+\tfor (i = 0; i < RABIN_WINDOW && data < top; i++, data++) {\n+\t\tout[outpos++] = *data;\n+\t\tval = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];\n+\t}\n+\tinscnt = i;\n \n \twhile (data < top) {\n \t\tunsigned int moff = 0, msize = 0;\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\tval ^= U[data[-RABIN_WINDOW]];\n+\t\tval = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];\n+\t\ti = val & 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@@ -214,7 +312,7 @@ create_delta(const struct delta_index *i\n \t\t\t}\n \t\t}\n \n-\t\tif (!msize || msize < COPYOP_SIZE(moff, msize)) {\n+\t\tif (msize < 4) {\n \t\t\tif (!inscnt)\n \t\t\t\toutpos++;\n \t\t\tout[outpos++] = *data++;\n@@ -226,6 +324,20 @@ create_delta(const struct delta_index *i\n \t\t} else {\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@@ -270,9 +382,8 @@ create_delta(const struct delta_index *i\n \t\t\tif (max_size && outsize >= max_size)\n \t\t\t\toutsize = max_size + MAX_OP_SIZE + 1;\n \t\t\tif (max_size && outpos > max_size)\n-\t\t\t\tout = NULL;\n-\t\t\telse\n-\t\t\t\tout = realloc(out, outsize);\n+\t\t\t\tbreak;\n+\t\t\tout = realloc(out, outsize);\n \t\t\tif (!out) {\n \t\t\t\tfree(tmp);\n \t\t\t\treturn NULL;\n@@ -283,6 +394,11 @@ create_delta(const struct delta_index *i\n \tif (inscnt)\n \t\tout[outpos - inscnt - 1] = inscnt;\n \n+\tif (max_size && outpos > max_size) {\n+\t\tfree(out);\n+\t\treturn NULL;\n+\t}\n+\n \t*delta_size = outpos;\n \treturn out;\n }\n"}]}