From b48e01a24e16084c1a4105eb094c445ec51bb461 Mon Sep 17 00:00:00 2001 From: Josh MacDonald Date: Tue, 28 Oct 2014 22:22:36 -0700 Subject: Added 64-bit checksum for largewindow support; not ready --- xdelta3/py-compile | 1 - xdelta3/run_release.sh | 21 ++-- xdelta3/testing/checksum_test.cc | 230 +++++++++++++++++++++++++++--------- xdelta3/testing/checksum_test_c.c | 173 +++++++++++++++++++++++++++ xdelta3/testing/test.h | 6 +- xdelta3/xdelta3-hash.h | 142 ++++++++--------------- xdelta3/xdelta3-internal.h | 62 +++++++++- xdelta3/xdelta3-test.h | 44 ++++++- xdelta3/xdelta3.c | 238 +++++++++----------------------------- xdelta3/xdelta3.h | 10 +- 10 files changed, 572 insertions(+), 355 deletions(-) delete mode 120000 xdelta3/py-compile diff --git a/xdelta3/py-compile b/xdelta3/py-compile deleted file mode 120000 index f90bf99..0000000 --- a/xdelta3/py-compile +++ /dev/null @@ -1 +0,0 @@ -/usr/local/share/automake-1.11/py-compile \ No newline at end of file diff --git a/xdelta3/run_release.sh b/xdelta3/run_release.sh index d2ead52..7e841ab 100755 --- a/xdelta3/run_release.sh +++ b/xdelta3/run_release.sh @@ -1,17 +1,18 @@ #!/bin/sh +# Choose CC=clang CXX=clang++ - +# or #CC=gcc #CXX=g++ -# These are updated below -CFLAGS= -CXXFLAGS= +# These are updated below, +CFLAGS= # Do not set here +CXXFLAGS= # Do not set here # Place C/C++ common flags here -COMMON=-O3 +#COMMON=-O3 export CFLAGS export CXXFLAGS @@ -52,7 +53,7 @@ function buildit { D=build/$MACH/${sizebits}size-${offsetbits}off mkdir -p $D (cd $D && $SRCDIR/configure --prefix=$PWD/bin --enable-debug-symbols) - (cd $D && make xdelta3checksum) + #(cd $D && make all) #echo Running regtest. #(cd $D && ./xdelta3regtest) } @@ -64,10 +65,10 @@ function buildall { addflag -DXD3_USE_LARGEWINDOW64=0 buildit 32 32 - resetflag $MACH - addflag -DXD3_USE_LARGEFILE64=1 - addflag -DXD3_USE_LARGEWINDOW64=0 - buildit 32 64 + # resetflag $MACH + # addflag -DXD3_USE_LARGEFILE64=1 + # addflag -DXD3_USE_LARGEWINDOW64=0 + # buildit 32 64 resetflag $MACH addflag -DXD3_USE_LARGEFILE64=1 diff --git a/xdelta3/testing/checksum_test.cc b/xdelta3/testing/checksum_test.cc index b9a4b0b..353d705 100644 --- a/xdelta3/testing/checksum_test.cc +++ b/xdelta3/testing/checksum_test.cc @@ -7,6 +7,16 @@ #include #include +extern "C" { +uint32_t xd3_large32_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); +uint32_t xd3_large32_cksum_update_old (xd3_hash_cfg *cfg, uint32_t cksum, + const uint8_t *base, const usize_t look); + +uint64_t xd3_large64_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); +uint64_t xd3_large64_cksum_update_old (xd3_hash_cfg *cfg, uint64_t cksum, + const uint8_t *base, const usize_t look); +} + using std::list; using std::map; using std::vector; @@ -24,6 +34,14 @@ uint64_t good_64bit_values[] = { 7664345821815920749ULL, // ... }; +void print_header() { + static int hdr_cnt = 0; + if (hdr_cnt++ % 20 == 0) { + printf("Name\t\t\t\tConf\t\tCount\tUniq\tFull\tCover\tColls" + "\tMB/s\tIters\t#Colls\n"); + } +} + struct true_type { }; struct false_type { }; @@ -50,13 +68,6 @@ struct hhash { // shift "s" bits leaving the high bits as a hash value for } }; -template -struct nonhash { - Word operator()(const Word t, const Word h, const Word mask) { - return (t >> h) & mask; - } -}; - template Word good_word(); @@ -92,14 +103,18 @@ struct cksum_params { MEMBER struct rabin_karp : public cksum_params { // (a^cksum_size-1 c_0) + (a^cksum_size-2 c_1) ... - rabin_karp() { - multiplier = good_word(); - powers = new Word[CksumSize]; - powers[CksumSize - 1] = 1; + rabin_karp() + : powers(make_powers()), + product(powers[0] * good_word()), + incr_state(0) { } + + static Word* make_powers() { + Word *p = new Word[CksumSize]; + p[CksumSize - 1] = 1; for (int i = CksumSize - 2; i >= 0; i--) { - powers[i] = powers[i + 1] * multiplier; + p[i] = p[i + 1] * good_word(); } - product = powers[0] * multiplier; + return p; } ~rabin_karp() { @@ -120,21 +135,69 @@ struct rabin_karp : public cksum_params { } Word incr(const uint8_t *ptr) { - incr_state = multiplier * incr_state - + incr_state = good_word() * incr_state - product * (ptr[-1]) + (ptr[CksumSize - 1]); return incr_state; } - Word *powers; - Word product; - Word multiplier; - Word incr_state; + const Word *const powers; + const Word product; + Word incr_state; +}; + +MEMBER +struct with_stream : public cksum_params { + xd3_stream stream; + + with_stream() + { + xd3_config cfg; + memset (&stream, 0, sizeof (stream)); + xd3_init_config (&cfg, 0); + cfg.smatch_cfg = XD3_SMATCH_SOFT; + cfg.smatcher_soft.large_look = CksumSize; + cfg.smatcher_soft.large_step = CksumSkip; + cfg.smatcher_soft.small_look = 4; + cfg.smatcher_soft.small_chain = 4; + cfg.smatcher_soft.small_lchain = 4; + cfg.smatcher_soft.max_lazy = 4; + cfg.smatcher_soft.long_enough = 4; + CHECK_EQ(0, xd3_config_stream (&stream, &cfg)); + + CHECK_EQ(0, xd3_size_hashtable (&stream, + 1<<10 /* ignored */, + stream.smatcher.large_look, + & stream.large_hash)); + } + ~with_stream() + { + xd3_free_stream (&stream); + } +}; + +MEMBER +struct large64_cksum : public with_stream { + Word step(const uint8_t *ptr) { + return xd3_large64_cksum (&this->stream.large_hash, ptr, CksumSize); + } + + Word state0(const uint8_t *ptr) { + incr_state = step(ptr); + return incr_state; + } + + Word incr(const uint8_t *ptr) { + incr_state = xd3_large64_cksum_update (&this->stream.large_hash, incr_state, ptr - 1, CksumSize); + return incr_state; + } + + Word incr_state; }; MEMBER -struct large_cksum : public cksum_params { +struct large64_cksum_old : public with_stream { Word step(const uint8_t *ptr) { - return xd3_large_cksum (ptr, CksumSize); + return xd3_large64_cksum_old (&this->stream.large_hash, ptr, CksumSize); } Word state0(const uint8_t *ptr) { @@ -143,13 +206,67 @@ struct large_cksum : public cksum_params { } Word incr(const uint8_t *ptr) { - incr_state = xd3_large_cksum_update (incr_state, ptr - 1, CksumSize); + incr_state = xd3_large64_cksum_update_old (&this->stream.large_hash, incr_state, ptr - 1, CksumSize); return incr_state; } Word incr_state; }; +MEMBER +struct large32_cksum : public with_stream { + Word step(const uint8_t *ptr) { + return xd3_large32_cksum (&this->stream.large_hash, ptr, CksumSize); + } + + Word state0(const uint8_t *ptr) { + incr_state = step(ptr); + return incr_state; + } + + Word incr(const uint8_t *ptr) { + incr_state = xd3_large32_cksum_update (&this->stream.large_hash, incr_state, ptr - 1, CksumSize); + return incr_state; + } + + Word incr_state; +}; + +MEMBER +struct large32_cksum_old : public with_stream { + Word step(const uint8_t *ptr) { + return xd3_large32_cksum_old (&this->stream.large_hash, ptr, CksumSize); + } + + Word state0(const uint8_t *ptr) { + incr_state = step(ptr); + return incr_state; + } + + Word incr(const uint8_t *ptr) { + incr_state = xd3_large32_cksum_update_old (&this->stream.large_hash, incr_state, ptr - 1, CksumSize); + return incr_state; + } + + Word incr_state; +}; + +MEMBER +struct large_cksum + : std::conditional::value, + large32_cksum, + large64_cksum>::type +{ +}; + +MEMBER +struct large_cksum_old + : std::conditional::value, + large32_cksum_old, + large64_cksum_old>::type +{ +}; + // TESTS template @@ -193,13 +310,21 @@ struct file_stats { ptr_list &pl = table[word]; + int collisions = 0; for (ptr_iterator p_i = pl.begin(); p_i != pl.end(); ++p_i) { if (memcmp(*p_i, ptr, cksum_size) == 0) { return; } + collisions++; } + if (collisions >= 10000) + { + fprintf(stderr, "Something is not right, lots of collisions=%d\n", + collisions); + abort(); + } unique++; pl.push_back(ptr); @@ -320,7 +445,7 @@ struct test_result : public test_result_base { /* Fraction of distinct strings of length cksum_size which are not * represented in the hash table. */ double collisions() { - return (fstats.unique - fstats.unique_values) / fstats.unique; + return (fstats.unique - fstats.unique_values) / (double) fstats.unique; } usize_t colls() { return (fstats.unique - fstats.unique_values); @@ -375,13 +500,8 @@ struct test_result : public test_result_base { fprintf(stderr, "internal error: %d != %d\n", fstats.count, count()); abort(); } - { - static int hdr_cnt = 0; - if (hdr_cnt++ % 20 == 0) { - printf("Name\tConf\tCount\tUniq\tFull\tColl\tCov\tMB/s\tIters\n"); - } - } - printf("%s\t%d/%d/1<<%d\t%u\t%0.2f\t%.2f\t%.2f\t%.2f\t%.4f\t%u\n", + print_header(); + printf("%s\t%d/%d 2^%d\t%u\t%0.4f\t%.4f\t%.4f\t%.1e\t%.2f\t%u\t%u\n", test_name, Checksum::cksum_size, Checksum::cksum_skip, @@ -389,10 +509,11 @@ struct test_result : public test_result_base { count(), uniqueness(), fullness(), - collisions(), coverage(), + collisions(), 0.001 * accum_iters * test_size / accum_millis, - accum_iters); + accum_iters, + colls()); } usize_t size_log2 (usize_t slots) { @@ -445,8 +566,8 @@ struct test_result : public test_result_base { const uint8_t *ptr; const uint8_t *end; usize_t periods; - int last_offset; - int stop; + int64_t last_offset; + int64_t stop; test_size = buf_size; last_offset = buf_size - Checksum::cksum_size; @@ -472,7 +593,7 @@ struct test_result : public test_result_base { } else { ptr = buf + last_offset; end = buf + stop; - + for (; ptr != end; ptr -= Checksum::cksum_skip) { fstats.update(hash(cksum.step(ptr), s_bits, s_mask), ptr); } @@ -503,7 +624,6 @@ struct test_result : public test_result_base { } if (Checksum::cksum_skip == 1) { - new_table(n_incrs); for (usize_t i = 0; i < test_iters; i++) { @@ -516,7 +636,7 @@ struct test_result : public test_result_base { for (; ptr != end; ptr++) { typename Checksum::word_type w = cksum.incr(ptr); - assert(w == cksum.step(ptr)); + CHECK_EQ(w, cksum.step(ptr)); set_table_bit(hash(w, s_bits, s_mask)); } } @@ -586,30 +706,30 @@ int main(int argc, char** argv) { return 1; } -#define TEST(T,Z,S,H,C) \ - test_result,C>> \ - _rka_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C \ - ("rka_" #T "_" #Z "_" #S "_" #H "_" #C); \ - test_result,C>> \ - _xck_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C \ - ("xck_" #T "_" #Z "_" #S "_" #H "_" #C) - +#define TEST(T,Z,S,C) \ + test_result,C>> \ + _rka_ ## T ## _ ## Z ## _ ## S ## _ ## C \ + ("rka_" #T "_" #Z "_" #S "_" #C); \ + test_result,C>> \ + _xck_ ## T ## _ ## Z ## _ ## S ## _ ## C \ + ("xck_" #T "_" #Z "_" #S "_" #C); \ + test_result,C>> \ + _old_ ## T ## _ ## Z ## _ ## S ## _ ## C \ + ("old_" #T "_" #Z "_" #S "_" #C) #define TESTS(SIZE, SKIP) \ - TEST(uint32_t, SIZE, SKIP, nonhash, 1); \ - TEST(uint32_t, SIZE, SKIP, nonhash, 2); \ - TEST(uint32_t, SIZE, SKIP, hhash, 1); \ - TEST(uint32_t, SIZE, SKIP, hhash, 2); \ - TEST(uint64_t, SIZE, SKIP, nonhash, 1); \ - TEST(uint64_t, SIZE, SKIP, nonhash, 2); \ - TEST(uint64_t, SIZE, SKIP, hhash, 1); \ - TEST(uint64_t, SIZE, SKIP, hhash, 2) + TEST(uint32_t, SIZE, SKIP, 1); \ + TEST(uint32_t, SIZE, SKIP, 2); \ + TEST(uint64_t, SIZE, SKIP, 1); \ + TEST(uint64_t, SIZE, SKIP, 2) + TESTS(9, 1); TESTS(9, 9); - // TESTS(9, 15); + TESTS(15, 1); TESTS(15, 15); + TESTS(127, 1); TESTS(127, 127); - // TESTS(127, 211); + TESTS(211, 1); TESTS(211, 211); for (i = 1; i < argc; i++) { @@ -630,7 +750,7 @@ int main(int argc, char** argv) { test_result_base *test = *iter; test->reset(); - usize_t iters = 100; + usize_t iters = 200; long start_test = get_millisecs_now(); do { diff --git a/xdelta3/testing/checksum_test_c.c b/xdelta3/testing/checksum_test_c.c index 2b32019..8f0507a 100644 --- a/xdelta3/testing/checksum_test_c.c +++ b/xdelta3/testing/checksum_test_c.c @@ -1 +1,174 @@ #include "../xdelta3.c" + +// OLD CHECKSUM CODE + +#define PERMUTE32(x) (__single_hash32[x]) +#define PERMUTE64(x) (__single_hash64[x]) + +const uint16_t __single_hash32[256] = +{ + /* This hashes the input alphabet (Scheme SLIB pseudo-random). */ + 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46, + 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602, + 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6, + 0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a, + 0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58, + 0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b, + 0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94, + 0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176, + 0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743, + 0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6, + 0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227, + 0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d, + 0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a, + 0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31, + 0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9, + 0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6, + 0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f, + 0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f, + 0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49, + 0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037, + 0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad, + 0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f, + 0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d, + 0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b, + 0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624, + 0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272, + 0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806, + 0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050, + 0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113, + 0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2, + 0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25, + 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5 +}; + +const uint32_t __single_hash64[256] = +{ + /* http://random.org 2014.10.24 */ + 0xd25e9f0a, 0xb1af9d5e, 0xb753dfa2, 0x157050f7, /* 0 */ + 0xc84b072c, 0xdd14fe7c, 0xf92208c3, 0xdf08a0c0, + 0x63a5c118, 0x76f5d90f, 0xa2f8b93e, 0xb6c12d22, + 0xaf074957, 0x966fb7d9, 0x62f7b785, 0xb40e8a09, + 0x0a811d5d, 0x323a6daa, 0xb62f7c5b, 0xfdcb9a53, + 0xf25a9067, 0x4506bc7a, 0xff58a74b, 0x5ae62817, + 0x74097675, 0x722c0fd9, 0x116a2a66, 0x65f76728, + 0x72c79651, 0xe043cf9d, 0x64b867c7, 0x6604834f, + 0xcdca58a6, 0x0f164e2d, 0x24515f05, 0x632cdbf8, + 0x18091d4a, 0x3eff4128, 0x673d1c33, 0xd8e10c71, + 0x1a3edf11, 0xba52892f, 0xa56949e0, 0xf3e1dd77, /* 10 */ + 0x86fcbe3e, 0x138d66d0, 0x4fc98359, 0xc22e5dd6, + 0xc59f2267, 0x6c6dd739, 0xe03da190, 0x07e8469c, + 0xadcfb02c, 0x00d3b0d9, 0xa1f44918, 0x8bd84d87, + 0x08ec9ec1, 0xbbcd156f, 0xb57718e3, 0x3177e752, + 0xf52a4d70, 0xde7aaad9, 0x075f1da0, 0x21ba00c6, + 0xb9469a5c, 0xcf08d5ba, 0x91ac9edc, 0xc6167b63, + 0xc1974919, 0xc8c8d195, 0x4b1996dd, 0xeff8991c, + 0xf7f66c6b, 0x25b012e2, 0x59d12a98, 0xea40d3cc, + 0x41f9970b, 0xec48101a, 0xa3bdcf90, 0x99f16905, + 0x27af6c97, 0xc849af37, 0x49cad89b, 0xf48c2278, /* 20 */ + 0x5529c3d8, 0x9e7d6dce, 0x16feb52d, 0xf1b0aca1, + 0xaf28fccb, 0x48e4ce3c, 0xc4436617, 0x64524e3e, + 0x61806681, 0x6384f2d7, 0x1172880f, 0x34a5ef5f, + 0xcc8cc0a8, 0x66e8f100, 0x2866085f, 0xba9b1b2d, + 0x51285949, 0x2be4b574, 0x889b1ef5, 0x3dbe920d, + 0x9277a62f, 0x0584a9f6, 0x085d8fc4, 0x4b5d403d, + 0x4e46ca78, 0x3294c2f9, 0x29313e70, 0xe4f09b24, + 0xe73b331c, 0x072f5552, 0x2e390b78, 0xea0021ca, + 0xd8f40320, 0xed0e16fd, 0x7de9cf7a, 0xf17e3d6c, + 0x8df1bd85, 0x052cae67, 0x3486e512, 0x3a1c09b8, /* 30 */ + 0x6c2a7b4e, 0x83455753, 0xbc0353ac, 0x0ffe20b6, + 0x5fdcef85, 0x010f506c, 0x595ce972, 0xe28680d0, + 0xa7e216b2, 0xa392ee0f, 0x25b73faa, 0x2b1f4983, + 0xeeaefe98, 0x1d3d9cbc, 0x6aebe97b, 0x8b7b3584, + 0x9e6a9a07, 0xd37f1e99, 0x4ac2a441, 0x8ae9a213, + 0x7d0e27d7, 0x5de54b9a, 0x8621de1f, 0xf0f2f866, + 0xcb08d275, 0x49c3f87e, 0xd5ee68c1, 0x9802fc77, + 0x68be6c5e, 0x65aa8c27, 0xf423d5f7, 0x10ec5502, + 0x9909bce1, 0x509cdf1b, 0x338fea72, 0x2733e9bf, + 0xf92f4fd7, 0x87738ea2, 0x931a8bbc, 0x0a5c9155, /* 40 */ + 0xbe5edd9b, 0xadbf5838, 0x0338f8d2, 0x290da210, + 0x390c37d8, 0xe7cffae8, 0x20617ebe, 0x464322dd, + 0x7b3c4e78, 0xac142dcb, 0x2d5cef76, 0xd8fe49fc, + 0x60f4e9a9, 0x7473816f, 0x0dc35f39, 0x5eed80c1, + 0x0cb55ab6, 0x1d3ac541, 0x13c7f529, 0x7bffdf4a, + 0xe334785b, 0x85263ec1, 0xd132ae56, 0x7c868b9e, + 0x47f60638, 0x1012b979, 0x81c31dd3, 0x1af868c8, + 0x0c5d0742, 0xd1b3e1a2, 0x5873200a, 0xf848465c, + 0x0fc4d596, 0x609c18af, 0xc9f5a480, 0xd1a94a84, + 0xa1431a3f, 0x7de8bb1a, 0x25f1256b, 0x1dcc732c, /* 50 */ + 0x6aa1549a, 0xa2367281, 0x32f2a77e, 0x82e62a0f, + 0x045cbb56, 0x74b2027c, 0xd71a32d9, 0x022e7cb5, + 0xe99be177, 0x60222fdf, 0xd69681ca, 0x9008ee2c, + 0x32923db4, 0xcf82bf97, 0x38960a5b, 0xb3503d5b, + 0x9bd4c7f2, 0x33c029c8, 0x1ef504a3, 0xdb249d3b, + 0x91e89676, 0x4ca43b36, 0x9191433c, 0x465d5dc4, + 0xf4dcb118, 0x9d11dd00, 0xb592f058, 0xdbe5ce30, + 0x74790d92, 0x779850a8, 0x7180d25b, 0xfa951d99, + 0x5990935a, 0x921cb022, 0x3b7c39bc, 0x6a38a7c7, + 0xdc22703b, 0x142bab3b, 0x4e3d9479, 0x44bb8482, /* 60 */ + 0x8043abce, 0xfebe832a, 0x8e6a2f98, 0x4d43c4fe, + 0xd192a70a, 0x802f3c3a, 0x5d11bbab, 0x2665d241, + 0xb3f3a680, 0x3a8d223f, 0xcf82cdb4, 0x4ed28743, +}; + +uint64_t +xd3_large64_cksum_old (xd3_hash_cfg *ignore, const uint8_t *base, const usize_t look) +{ + static const uint64_t kBits = 32; + static const uint64_t kMask = 0xffffffff; + usize_t i = 0; + uint64_t low = 0; + uint64_t high = 0; + + for (; i < look; i += 1) + { + low += PERMUTE64(*base++); + high += low; + } + + return ((high & kMask) << kBits) | (low & kMask); +} + +uint64_t +xd3_large64_cksum_update_old (xd3_hash_cfg *ignore, const uint64_t cksum, + const uint8_t *base, const usize_t look) +{ + static const uint64_t kBits = 32; + static const uint64_t kMask = 0xffffffff; + uint64_t old_c = PERMUTE64(base[0]); + uint64_t new_c = PERMUTE64(base[look]); + uint64_t low = ((cksum & kMask) - old_c + new_c) & kMask; + uint64_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask; + return (high << kBits) | low; +} + +uint32_t +xd3_large32_cksum_old (xd3_hash_cfg *ignore, const uint8_t *base, const usize_t look) +{ + static const uint32_t kBits = 16; + static const uint32_t kMask = 0xffff; + usize_t i = 0; + uint32_t low = 0; + uint32_t high = 0; + + for (; i < look; i += 1) + { + low += PERMUTE32(*base++); + high += low; + } + + return ((high & kMask) << kBits) | (low & kMask); +} + +uint32_t +xd3_large32_cksum_update_old (xd3_hash_cfg *ignore, const uint32_t cksum, + const uint8_t *base, const usize_t look) +{ + static const uint32_t kBits = 16; + static const uint32_t kMask = 0xffff; + uint32_t old_c = PERMUTE32(base[0]); + uint32_t new_c = PERMUTE32(base[look]); + uint32_t low = ((cksum & kMask) - old_c + new_c) & kMask; + uint32_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask; + return (high << kBits) | low; +} diff --git a/xdelta3/testing/test.h b/xdelta3/testing/test.h index d1f1a22..30d13a3 100644 --- a/xdelta3/testing/test.h +++ b/xdelta3/testing/test.h @@ -18,8 +18,8 @@ extern "C" { #define CHECK_OP(x,y,OP) \ do { \ - typeof(x) _x(x); \ - typeof(x) _y(y); \ + __typeof__(x) _x(x); \ + __typeof__(x) _y(y); \ if (!(_x OP _y)) { \ cerr << __FILE__ << ":" << __LINE__ << " Check failed: " << #x " " #OP " " #y << endl; \ cerr << __FILE__ << ":" << __LINE__ << " Expected: " << _x << endl; \ @@ -68,5 +68,3 @@ pair make_pair(const T& t, const U& u) { using std::min; using std::max; - - diff --git a/xdelta3/xdelta3-hash.h b/xdelta3/xdelta3-hash.h index fd18099..2919b98 100644 --- a/xdelta3/xdelta3-hash.h +++ b/xdelta3/xdelta3-hash.h @@ -41,10 +41,11 @@ #define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4); #endif -/* This is a good hash multiplier for 32-bit LCGs: see "linear - * congruential generators of different sizes and good lattice +/* These are good hash multipliers for 32-bit and 64-bit LCGs: see + * "linear congruential generators of different sizes and good lattice * structure" */ -static const uint32_t hash_multiplier = 1597334677U; +#define xd3_hash_multiplier32 1597334677U +#define xd3_hash_multiplier64 1181783497276652981ULL /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */ static inline uint32_t @@ -53,7 +54,7 @@ xd3_scksum (uint32_t *state, const usize_t look) { UNALIGNED_READ32(state, base); - return (*state) * hash_multiplier; + return (*state) * xd3_hash_multiplier32; } static inline uint32_t xd3_small_cksum_update (uint32_t *state, @@ -61,112 +62,48 @@ xd3_small_cksum_update (uint32_t *state, usize_t look) { UNALIGNED_READ32(state, base+1); - return (*state) * hash_multiplier; + return (*state) * xd3_hash_multiplier32; } -static inline usize_t +#if XD3_ENCODER +inline usize_t xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) { return (cksum >> cfg->shift) ^ (cksum & cfg->mask); } -#if XD3_ENCODER -#define PERMUTE32(x) (__single_hash32[x]) -extern const uint16_t __single_hash32[256]; - inline uint32_t -xd3_large32_cksum (const uint8_t *seg, const usize_t ln) +xd3_large32_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look) { - static const uint32_t kBits = 16; - static const uint32_t kMask = 0xffff; - usize_t i = 0; - uint32_t low = 0; - uint32_t high = 0; - - for (; i < ln; i += 1) - { - low += PERMUTE32(*seg++); - high += low; - } - - return ((high & kMask) << kBits) | (low & kMask); + uint32_t h = 0; + for (usize_t i = 0; i < look; i++) { + h += base[i] * cfg->powers[i]; + } + return h; } inline uint32_t -xd3_large32_cksum_update (uint32_t cksum, - const uint8_t *base, - usize_t look) +xd3_large32_cksum_update (xd3_hash_cfg *cfg, const uint32_t cksum, + const uint8_t *base, const usize_t look) { - static const uint32_t kBits = 16; - static const uint32_t kMask = 0xffff; - uint32_t old_c = PERMUTE32(base[0]); - uint32_t new_c = PERMUTE32(base[look]); - uint32_t low = ((cksum & kMask) - old_c + new_c) & kMask; - uint32_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask; - return (high << kBits) | low; + return xd3_hash_multiplier32 * cksum - cfg->multiplier * base[0] + base[look]; } -#undef PERMUTE32 - -#define PERMUTE64(x) (__single_hash64[x]) -extern const uint32_t __single_hash64[256]; - inline uint64_t -xd3_large64_cksum (const uint8_t *seg, const usize_t len) +xd3_large64_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look) { - static const uint64_t kBits = 32; - static const uint64_t kMask = 0xffffffff; - usize_t i = 0; - uint64_t low = 0; - uint64_t high = 0; - - for (; i < len; i += 1) - { - low += PERMUTE64(*seg++); - high += low; - } - - return ((high & kMask) << kBits) | (low & kMask); + uint64_t h = 0; + for (usize_t i = 0; i < look; i++) { + h += base[i] * cfg->powers[i]; + } + return h; } inline uint64_t -xd3_large64_cksum_update (uint64_t cksum, - const uint8_t *base, - usize_t look) +xd3_large64_cksum_update (xd3_hash_cfg *cfg, const uint64_t cksum, + const uint8_t *base, const usize_t look) { - static const uint64_t kBits = 32; - static const uint64_t kMask = 0xffffffff; - uint64_t old_c = PERMUTE64(base[0]); - uint64_t new_c = PERMUTE64(base[look]); - uint64_t low = ((cksum & kMask) - old_c + new_c) & kMask; - uint64_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask; - return (high << kBits) | low; -} - -#undef PERMUTE64 - -inline usize_t -xd3_large_cksum (const uint8_t *seg, const usize_t len) -{ - if (SIZEOF_USIZE_T == 4) - { - return xd3_large32_cksum (seg, len); - } - else - { - return xd3_large64_cksum (seg, len); - } -} - -inline usize_t -xd3_large_cksum_update (usize_t cksum, - const uint8_t *base, - usize_t look) { -#if SIZEOF_USIZE_T == 4 - return xd3_large32_cksum_update (cksum, base, look); -#else - return xd3_large64_cksum_update (cksum, base, look); -#endif + return xd3_hash_multiplier64 * cksum - cfg->multiplier * base[0] + base[look]; } static usize_t @@ -179,9 +116,9 @@ xd3_size_hashtable_bits (usize_t slots) { if (slots < (1U << i)) { - /* TODO: this is compaction=1 in checksum_test.cc and maybe should - * not be fixed at -1. */ - bits = i - 1; + /* Note: this is the compaction=1 setting measured in + * checksum_test */ + bits = i - 1; break; } } @@ -189,9 +126,10 @@ xd3_size_hashtable_bits (usize_t slots) return bits; } -static void +int xd3_size_hashtable (xd3_stream *stream, usize_t slots, + usize_t look, xd3_hash_cfg *cfg) { usize_t bits = xd3_size_hashtable_bits (slots); @@ -199,7 +137,23 @@ xd3_size_hashtable (xd3_stream *stream, cfg->size = (1U << bits); cfg->mask = (cfg->size - 1); cfg->shift = (SIZEOF_USIZE_T * 8) - bits; + cfg->look = look; + + if ((cfg->powers = + (usize_t*) xd3_alloc0 (stream, look, sizeof (usize_t))) == NULL) + { + return ENOMEM; + } + + cfg->powers[look-1] = 1; + for (int i = look-2; i >= 0; i--) + { + cfg->powers[i] = cfg->powers[i+1] * xd3_hash_multiplier; + } + cfg->multiplier = cfg->powers[0] * xd3_hash_multiplier; + + return 0; } -#endif +#endif /* XD3_ENCODER */ #endif /* _XDELTA3_HASH_H_ */ diff --git a/xdelta3/xdelta3-internal.h b/xdelta3/xdelta3-internal.h index d9d56b9..d584141 100644 --- a/xdelta3/xdelta3-internal.h +++ b/xdelta3/xdelta3-internal.h @@ -64,6 +64,10 @@ int xd3_process_stream (int is_encode, int xd3_main_cmdline (int argc, char **argv); #endif +#if REGRESSION_TEST +int xd3_selftest (void); +#endif + /* main_file->mode values */ typedef enum { @@ -155,9 +159,59 @@ void xprintf(const char *fmt, ...) PRINTF_ATTRIBUTE(1,2); #define UINT64_MAX 18446744073709551615ULL #endif -usize_t xd3_large_cksum (const uint8_t *seg, const usize_t ln); -usize_t xd3_large_cksum_update (usize_t cksum, - const uint8_t *base, - usize_t look); +#define UINT32_OFLOW_MASK 0xfe000000U +#define UINT64_OFLOW_MASK 0xfe00000000000000ULL + +#if SIZEOF_USIZE_T == 4 +#define USIZE_T_MAX UINT32_MAX +#define xd3_decode_size xd3_decode_uint32_t +#define xd3_emit_size xd3_emit_uint32_t +#define xd3_sizeof_size xd3_sizeof_uint32_t +#define xd3_read_size xd3_read_uint32_t +#define xd3_large_cksum xd3_large32_cksum +#define xd3_large_cksum_update xd3_large32_cksum_update +#define xd3_hash_multiplier xd3_hash_multiplier32 +#elif SIZEOF_USIZE_T == 8 +#define USIZE_T_MAX UINT64_MAX +#define xd3_decode_size xd3_decode_uint64_t +#define xd3_emit_size xd3_emit_uint64_t +#define xd3_sizeof_size xd3_sizeof_uint64_t +#define xd3_read_size xd3_read_uint64_t +#define xd3_large_cksum xd3_large64_cksum +#define xd3_large_cksum_update xd3_large64_cksum_update +#define xd3_hash_multiplier xd3_hash_multiplier64 +#endif + +#if SIZEOF_XOFF_T == 4 +#define XOFF_T_MAX UINT32_MAX +#define xd3_decode_offset xd3_decode_uint32_t +#define xd3_emit_offset xd3_emit_uint32_t +#elif SIZEOF_XOFF_T == 8 +#define XOFF_T_MAX UINT64_MAX +#define xd3_decode_offset xd3_decode_uint64_t +#define xd3_emit_offset xd3_emit_uint64_t +#endif + +#define USIZE_T_OVERFLOW(a,b) ((USIZE_T_MAX - (usize_t) (a)) < (usize_t) (b)) +#define XOFF_T_OVERFLOW(a,b) ((XOFF_T_MAX - (xoff_t) (a)) < (xoff_t) (b)) + +int xd3_size_hashtable (xd3_stream *stream, + usize_t slots, + usize_t look, + xd3_hash_cfg *cfg); + +usize_t xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum); + +#if USE_UINT32 +uint32_t xd3_large32_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); +uint32_t xd3_large32_cksum_update (xd3_hash_cfg *cfg, uint32_t cksum, + const uint8_t *base, const usize_t look); +#endif /* USE_UINT32 */ + +#if USE_UINT64 +uint64_t xd3_large64_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); +uint64_t xd3_large64_cksum_update (xd3_hash_cfg *cfg, uint64_t cksum, + const uint8_t *base, const usize_t look); +#endif /* USE_UINT64 */ #endif /* XDELTA3_INTERNAL_H__ */ diff --git a/xdelta3/xdelta3-test.h b/xdelta3/xdelta3-test.h index 3d505fc..ccb158b 100644 --- a/xdelta3/xdelta3-test.h +++ b/xdelta3/xdelta3-test.h @@ -1556,6 +1556,45 @@ test_choose_instruction (xd3_stream *stream, int ignore) return 0; } +static int +test_checksum_step (xd3_stream *stream, int ignore) +{ + const int bufsize = 128; + uint8_t buf[bufsize]; + for (int i = 0; i < bufsize; i++) + { + buf[i] = mt_random (&static_mtrand) & 0xff; + } + + for (usize_t cksize = 4; cksize <= 32; cksize += 3) + { + xd3_hash_cfg h1; + usize_t x; + int ret; + + if ((ret = xd3_size_hashtable (stream, XD3_ALLOCSIZE, cksize, &h1)) != 0) + { + return ret; + } + + x = xd3_large_cksum (&h1, buf, cksize); + for (usize_t pos = 0; pos <= (bufsize - cksize); pos++) + { + usize_t y = xd3_large_cksum (&h1, buf + pos, cksize); + if (x != y) + { + stream->msg = "checksum != incremental checksum"; + return XD3_INTERNAL; + } + x = xd3_large_cksum_update (&h1, x, buf + pos, cksize); + } + + xd3_free (stream, h1.powers); + } + + return 0; +} + /*********************************************************************** 64BIT STREAMING ***********************************************************************/ @@ -2839,8 +2878,7 @@ test_in_memory (xd3_stream *stream, int ignore) TEST MAIN ***********************************************************************/ -static int -xd3_selftest (void) +int xd3_selftest (void) { #define DO_TEST(fn,flags,arg) \ do { \ @@ -2867,8 +2905,8 @@ xd3_selftest (void) DO_TEST (encode_decode_uint32_t, 0, 0); DO_TEST (encode_decode_uint64_t, 0, 0); DO_TEST (usize_t_overflow, 0, 0); + DO_TEST (checksum_step, 0, 0); DO_TEST (forward_match, 0, 0); - DO_TEST (address_cache, 0, 0); DO_TEST (string_matching, 0, 0); diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c index b8aa9eb..5c79f37 100644 --- a/xdelta3/xdelta3.c +++ b/xdelta3/xdelta3.c @@ -549,50 +549,6 @@ static int xd3_decode_allocate (xd3_stream *stream, usize_t size, static void* xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size); static void xd3_free (xd3_stream *stream, void *ptr); -#if USE_UINT32 -static int xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp, - const uint8_t *max, uint32_t *valp); -#endif -#if USE_UINT64 -static int xd3_read_uint64_t (xd3_stream *stream, const uint8_t **inpp, - const uint8_t *max, uint64_t *valp); -#endif -#if REGRESSION_TEST -static int xd3_selftest (void); -#endif - -/***********************************************************************/ - -#define UINT32_OFLOW_MASK 0xfe000000U -#define UINT64_OFLOW_MASK 0xfe00000000000000ULL - -#if SIZEOF_USIZE_T == 4 -#define USIZE_T_MAX UINT32_MAX -#define xd3_decode_size xd3_decode_uint32_t -#define xd3_emit_size xd3_emit_uint32_t -#define xd3_sizeof_size xd3_sizeof_uint32_t -#define xd3_read_size xd3_read_uint32_t -#elif SIZEOF_USIZE_T == 8 -#define USIZE_T_MAX UINT64_MAX -#define xd3_decode_size xd3_decode_uint64_t -#define xd3_emit_size xd3_emit_uint64_t -#define xd3_sizeof_size xd3_sizeof_uint64_t -#define xd3_read_size xd3_read_uint64_t -#endif - -#if SIZEOF_XOFF_T == 4 -#define XOFF_T_MAX UINT32_MAX -#define xd3_decode_offset xd3_decode_uint32_t -#define xd3_emit_offset xd3_emit_uint32_t -#elif SIZEOF_XOFF_T == 8 -#define XOFF_T_MAX UINT64_MAX -#define xd3_decode_offset xd3_decode_uint64_t -#define xd3_emit_offset xd3_emit_uint64_t -#endif - -#define USIZE_T_OVERFLOW(a,b) ((USIZE_T_MAX - (usize_t) (a)) < (usize_t) (b)) -#define XOFF_T_OVERFLOW(a,b) ((XOFF_T_MAX - (xoff_t) (a)) < (xoff_t) (b)) - const char* xd3_strerror (int ret) { switch (ret) @@ -798,112 +754,6 @@ const xd3_sec_type lzma_sec_type = #endif /* __XDELTA3_C_HEADER_PASS__ */ #ifdef __XDELTA3_C_INLINE_PASS__ -const uint16_t __single_hash32[256] = -{ - /* This hashes the input alphabet (Scheme SLIB pseudo-random). */ - 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46, - 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602, - 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6, - 0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a, - 0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58, - 0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b, - 0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94, - 0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176, - 0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743, - 0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6, - 0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227, - 0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d, - 0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a, - 0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31, - 0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9, - 0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6, - 0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f, - 0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f, - 0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49, - 0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037, - 0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad, - 0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f, - 0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d, - 0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b, - 0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624, - 0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272, - 0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806, - 0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050, - 0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113, - 0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2, - 0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25, - 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5 -}; - -const uint32_t __single_hash64[256] = -{ - /* http://random.org 2014.10.24 */ - 0xd25e9f0a, 0xb1af9d5e, 0xb753dfa2, 0x157050f7, /* 0 */ - 0xc84b072c, 0xdd14fe7c, 0xf92208c3, 0xdf08a0c0, - 0x63a5c118, 0x76f5d90f, 0xa2f8b93e, 0xb6c12d22, - 0xaf074957, 0x966fb7d9, 0x62f7b785, 0xb40e8a09, - 0x0a811d5d, 0x323a6daa, 0xb62f7c5b, 0xfdcb9a53, - 0xf25a9067, 0x4506bc7a, 0xff58a74b, 0x5ae62817, - 0x74097675, 0x722c0fd9, 0x116a2a66, 0x65f76728, - 0x72c79651, 0xe043cf9d, 0x64b867c7, 0x6604834f, - 0xcdca58a6, 0x0f164e2d, 0x24515f05, 0x632cdbf8, - 0x18091d4a, 0x3eff4128, 0x673d1c33, 0xd8e10c71, - 0x1a3edf11, 0xba52892f, 0xa56949e0, 0xf3e1dd77, /* 10 */ - 0x86fcbe3e, 0x138d66d0, 0x4fc98359, 0xc22e5dd6, - 0xc59f2267, 0x6c6dd739, 0xe03da190, 0x07e8469c, - 0xadcfb02c, 0x00d3b0d9, 0xa1f44918, 0x8bd84d87, - 0x08ec9ec1, 0xbbcd156f, 0xb57718e3, 0x3177e752, - 0xf52a4d70, 0xde7aaad9, 0x075f1da0, 0x21ba00c6, - 0xb9469a5c, 0xcf08d5ba, 0x91ac9edc, 0xc6167b63, - 0xc1974919, 0xc8c8d195, 0x4b1996dd, 0xeff8991c, - 0xf7f66c6b, 0x25b012e2, 0x59d12a98, 0xea40d3cc, - 0x41f9970b, 0xec48101a, 0xa3bdcf90, 0x99f16905, - 0x27af6c97, 0xc849af37, 0x49cad89b, 0xf48c2278, /* 20 */ - 0x5529c3d8, 0x9e7d6dce, 0x16feb52d, 0xf1b0aca1, - 0xaf28fccb, 0x48e4ce3c, 0xc4436617, 0x64524e3e, - 0x61806681, 0x6384f2d7, 0x1172880f, 0x34a5ef5f, - 0xcc8cc0a8, 0x66e8f100, 0x2866085f, 0xba9b1b2d, - 0x51285949, 0x2be4b574, 0x889b1ef5, 0x3dbe920d, - 0x9277a62f, 0x0584a9f6, 0x085d8fc4, 0x4b5d403d, - 0x4e46ca78, 0x3294c2f9, 0x29313e70, 0xe4f09b24, - 0xe73b331c, 0x072f5552, 0x2e390b78, 0xea0021ca, - 0xd8f40320, 0xed0e16fd, 0x7de9cf7a, 0xf17e3d6c, - 0x8df1bd85, 0x052cae67, 0x3486e512, 0x3a1c09b8, /* 30 */ - 0x6c2a7b4e, 0x83455753, 0xbc0353ac, 0x0ffe20b6, - 0x5fdcef85, 0x010f506c, 0x595ce972, 0xe28680d0, - 0xa7e216b2, 0xa392ee0f, 0x25b73faa, 0x2b1f4983, - 0xeeaefe98, 0x1d3d9cbc, 0x6aebe97b, 0x8b7b3584, - 0x9e6a9a07, 0xd37f1e99, 0x4ac2a441, 0x8ae9a213, - 0x7d0e27d7, 0x5de54b9a, 0x8621de1f, 0xf0f2f866, - 0xcb08d275, 0x49c3f87e, 0xd5ee68c1, 0x9802fc77, - 0x68be6c5e, 0x65aa8c27, 0xf423d5f7, 0x10ec5502, - 0x9909bce1, 0x509cdf1b, 0x338fea72, 0x2733e9bf, - 0xf92f4fd7, 0x87738ea2, 0x931a8bbc, 0x0a5c9155, /* 40 */ - 0xbe5edd9b, 0xadbf5838, 0x0338f8d2, 0x290da210, - 0x390c37d8, 0xe7cffae8, 0x20617ebe, 0x464322dd, - 0x7b3c4e78, 0xac142dcb, 0x2d5cef76, 0xd8fe49fc, - 0x60f4e9a9, 0x7473816f, 0x0dc35f39, 0x5eed80c1, - 0x0cb55ab6, 0x1d3ac541, 0x13c7f529, 0x7bffdf4a, - 0xe334785b, 0x85263ec1, 0xd132ae56, 0x7c868b9e, - 0x47f60638, 0x1012b979, 0x81c31dd3, 0x1af868c8, - 0x0c5d0742, 0xd1b3e1a2, 0x5873200a, 0xf848465c, - 0x0fc4d596, 0x609c18af, 0xc9f5a480, 0xd1a94a84, - 0xa1431a3f, 0x7de8bb1a, 0x25f1256b, 0x1dcc732c, /* 50 */ - 0x6aa1549a, 0xa2367281, 0x32f2a77e, 0x82e62a0f, - 0x045cbb56, 0x74b2027c, 0xd71a32d9, 0x022e7cb5, - 0xe99be177, 0x60222fdf, 0xd69681ca, 0x9008ee2c, - 0x32923db4, 0xcf82bf97, 0x38960a5b, 0xb3503d5b, - 0x9bd4c7f2, 0x33c029c8, 0x1ef504a3, 0xdb249d3b, - 0x91e89676, 0x4ca43b36, 0x9191433c, 0x465d5dc4, - 0xf4dcb118, 0x9d11dd00, 0xb592f058, 0xdbe5ce30, - 0x74790d92, 0x779850a8, 0x7180d25b, 0xfa951d99, - 0x5990935a, 0x921cb022, 0x3b7c39bc, 0x6a38a7c7, - 0xdc22703b, 0x142bab3b, 0x4e3d9479, 0x44bb8482, /* 60 */ - 0x8043abce, 0xfebe832a, 0x8e6a2f98, 0x4d43c4fe, - 0xd192a70a, 0x802f3c3a, 0x5d11bbab, 0x2665d241, - 0xb3f3a680, 0x3a8d223f, 0xcf82cdb4, 0x4ed28743, -}; - /**************************************************************** Instruction tables *****************************************************************/ @@ -1499,55 +1349,59 @@ xd3_emit_bytes (xd3_stream *stream, \ return xd3_emit_bytes (stream, output, buf + bufi, 10 - bufi) -#define IF_SIZEOF32(x) if (num < (1U << (7 * (x)))) return (x); -#define IF_SIZEOF64(x) if (num < (1ULL << (7 * (x)))) return (x); - #if USE_UINT32 usize_t xd3_sizeof_uint32_t (uint32_t num) { +#define IF_SIZEOF32(x) if (num < (1U << (7 * (x)))) return (x); IF_SIZEOF32(1); IF_SIZEOF32(2); IF_SIZEOF32(3); IF_SIZEOF32(4); +#undef IF_SIZEOF32 return 5; } int xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val) -{ DECODE_INTEGER_TYPE (uint32_t, stream->dec_32part, UINT32_OFLOW_MASK); } +{ + DECODE_INTEGER_TYPE (uint32_t, stream->dec_32part, UINT32_OFLOW_MASK); +} int xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp, const uint8_t *max, uint32_t *valp) -{ READ_INTEGER_TYPE (uint32_t, UINT32_OFLOW_MASK); } +{ + READ_INTEGER_TYPE (uint32_t, UINT32_OFLOW_MASK); +} #if XD3_ENCODER int xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num) -{ EMIT_INTEGER_TYPE (); } -#endif -#endif +{ + EMIT_INTEGER_TYPE (); +} +#endif /* XD3_ENCODER */ +#endif /* USE_UINT32 */ #if USE_UINT64 int xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val) -{ DECODE_INTEGER_TYPE (uint64_t, stream->dec_64part, UINT64_OFLOW_MASK); } - -#if XD3_ENCODER -int -xd3_emit_uint64_t (xd3_stream *stream, xd3_output **output, uint64_t num) -{ EMIT_INTEGER_TYPE (); } -#endif +{ + DECODE_INTEGER_TYPE (uint64_t, stream->dec_64part, UINT64_OFLOW_MASK); +} int xd3_read_uint64_t (xd3_stream *stream, const uint8_t **inpp, const uint8_t *max, uint64_t *valp) -{ READ_INTEGER_TYPE (uint64_t, UINT64_OFLOW_MASK); } +{ + READ_INTEGER_TYPE (uint64_t, UINT64_OFLOW_MASK); +} usize_t xd3_sizeof_uint64_t (uint64_t num) { +#define IF_SIZEOF64(x) if (num < (1ULL << (7 * (x)))) return (x); IF_SIZEOF64(1); IF_SIZEOF64(2); IF_SIZEOF64(3); @@ -1557,11 +1411,18 @@ xd3_sizeof_uint64_t (uint64_t num) IF_SIZEOF64(7); IF_SIZEOF64(8); IF_SIZEOF64(9); - +#undef IF_SIZEOF64 return 10; } -#endif +#if XD3_ENCODER +int +xd3_emit_uint64_t (xd3_stream *stream, xd3_output **output, uint64_t num) +{ + EMIT_INTEGER_TYPE (); +} +#endif /* XD3_ENCODER */ +#endif /* USE_UINT64 */ /*********************************************************************** Address cache stuff @@ -1928,11 +1789,13 @@ xd3_free_stream (xd3_stream *stream) xd3_free (stream, tmp); } +#if XD3_ENCODER xd3_free (stream, stream->large_table); xd3_free (stream, stream->small_table); + xd3_free (stream, stream->large_hash.powers); + xd3_free (stream, stream->small_hash.powers); xd3_free (stream, stream->small_prev); -#if XD3_ENCODER { int i; for (i = 0; i < ENC_SECTS; i += 1) @@ -3158,7 +3021,7 @@ xd3_emit_hdr (xd3_stream *stream) inst_len = xd3_sizeof_output (INST_HEAD (stream)); addr_len = xd3_sizeof_output (ADDR_HEAD (stream)); - /* The enc_len field is a redundency for future extensions.*/ + /* The enc_len field is a redundency for future extensions. */ enc_len = (1 + (xd3_sizeof_size (tgt_len) + xd3_sizeof_size (data_len) + xd3_sizeof_size (inst_len) + @@ -3299,6 +3162,7 @@ xd3_alloc_iopt (xd3_stream *stream, usize_t elts) static int xd3_encode_init (xd3_stream *stream, int full_init) { + int ret; int i; if (full_init) @@ -3315,9 +3179,13 @@ xd3_encode_init (xd3_stream *stream, int full_init) usize_t hash_values = stream->src->max_winsize / stream->smatcher.large_step; - xd3_size_hashtable (stream, - hash_values, - & stream->large_hash); + if ((ret = xd3_size_hashtable (stream, + hash_values, + stream->smatcher.large_look, + & stream->large_hash))) + { + return ret; + } } if (small_comp) @@ -3328,9 +3196,13 @@ xd3_encode_init (xd3_stream *stream, int full_init) * sense. @@@ */ usize_t hash_values = stream->winsize; - xd3_size_hashtable (stream, - hash_values, - & stream->small_hash); + if ((ret = xd3_size_hashtable (stream, + hash_values, + stream->smatcher.small_look, + & stream->small_hash))) + { + return ret; + } } } @@ -4627,7 +4499,7 @@ xd3_verify_large_state (xd3_stream *stream, const uint8_t *inp, usize_t x_cksum) { - usize_t cksum = xd3_large_cksum (inp, stream->smatcher.large_look); + usize_t cksum = xd3_large_cksum (&stream->large_hash, inp, stream->smatcher.large_look); XD3_ASSERT (cksum == x_cksum); } static void @@ -4771,8 +4643,12 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) do { - usize_t cksum = xd3_large_cksum (stream->src->curblk + blkpos, - stream->smatcher.large_look); + /* TODO: This would be significantly faster if the compiler + * knew stream->smatcher.large_look (which the template for + * xd3_string_match_* allows). */ + usize_t cksum = xd3_large_cksum (&stream->large_hash, + stream->src->curblk + blkpos, + stream->smatcher.large_look); usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum); stream->large_table[hval] = @@ -4934,7 +4810,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) return ret; } - lcksum = xd3_large_cksum (inp, LLOOK); + lcksum = xd3_large_cksum (&stream->large_hash, inp, LLOOK); } /* TRYLAZYLEN: True if a certain length match should be followed by @@ -5110,7 +4986,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) if (DO_LARGE && (stream->input_position + LLOOK < stream->avail_in)) { - lcksum = xd3_large_cksum_update (lcksum, inp, LLOOK); + lcksum = xd3_large_cksum_update (&stream->large_hash, lcksum, inp, LLOOK); } } diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h index 1fd55b0..7b63b9c 100644 --- a/xdelta3/xdelta3.h +++ b/xdelta3/xdelta3.h @@ -658,9 +658,13 @@ struct _xd3_smatcher /* hash table size & power-of-two hash function. */ struct _xd3_hash_cfg { - usize_t size; - usize_t shift; - usize_t mask; + usize_t size; // Number of buckets + usize_t shift; + usize_t mask; + usize_t look; // How wide is this checksum + usize_t multiplier; // K * powers[0] + usize_t *powers; // Array of [0,look) where powers[look-1] == 1 + // and powers[N] = powers[N+1]*K (Rabin-Karp) }; /* the sprev list */ -- cgit v1.2.3