summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJosh MacDonald <josh.macdonald@gmail.com>2014-10-28 22:22:36 -0700
committerJosh MacDonald <josh.macdonald@gmail.com>2014-10-28 22:22:36 -0700
commitb48e01a24e16084c1a4105eb094c445ec51bb461 (patch)
tree50439719a0d679293118358938f31a2ed131efc2
parent496dc7140e18747d00be720978202915d68ded99 (diff)
Added 64-bit checksum for largewindow support; not ready
Diffstat
l---------xdelta3/py-compile1
-rwxr-xr-xxdelta3/run_release.sh21
-rw-r--r--xdelta3/testing/checksum_test.cc230
-rw-r--r--xdelta3/testing/checksum_test_c.c173
-rw-r--r--xdelta3/testing/test.h6
-rw-r--r--xdelta3/xdelta3-hash.h142
-rw-r--r--xdelta3/xdelta3-internal.h62
-rw-r--r--xdelta3/xdelta3-test.h44
-rw-r--r--xdelta3/xdelta3.c238
-rw-r--r--xdelta3/xdelta3.h10
10 files changed, 572 insertions, 355 deletions
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 @@
1/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 @@
1#!/bin/sh 1#!/bin/sh
2 2
3# Choose
3CC=clang 4CC=clang
4CXX=clang++ 5CXX=clang++
5 6# or
6#CC=gcc 7#CC=gcc
7#CXX=g++ 8#CXX=g++
8 9
9# These are updated below 10# These are updated below,
10CFLAGS= 11CFLAGS= # Do not set here
11CXXFLAGS= 12CXXFLAGS= # Do not set here
12 13
13# Place C/C++ common flags here 14# Place C/C++ common flags here
14COMMON=-O3 15#COMMON=-O3
15 16
16export CFLAGS 17export CFLAGS
17export CXXFLAGS 18export CXXFLAGS
@@ -52,7 +53,7 @@ function buildit {
52 D=build/$MACH/${sizebits}size-${offsetbits}off 53 D=build/$MACH/${sizebits}size-${offsetbits}off
53 mkdir -p $D 54 mkdir -p $D
54 (cd $D && $SRCDIR/configure --prefix=$PWD/bin --enable-debug-symbols) 55 (cd $D && $SRCDIR/configure --prefix=$PWD/bin --enable-debug-symbols)
55 (cd $D && make xdelta3checksum) 56 #(cd $D && make all)
56 #echo Running regtest. 57 #echo Running regtest.
57 #(cd $D && ./xdelta3regtest) 58 #(cd $D && ./xdelta3regtest)
58} 59}
@@ -64,10 +65,10 @@ function buildall {
64 addflag -DXD3_USE_LARGEWINDOW64=0 65 addflag -DXD3_USE_LARGEWINDOW64=0
65 buildit 32 32 66 buildit 32 32
66 67
67 resetflag $MACH 68 # resetflag $MACH
68 addflag -DXD3_USE_LARGEFILE64=1 69 # addflag -DXD3_USE_LARGEFILE64=1
69 addflag -DXD3_USE_LARGEWINDOW64=0 70 # addflag -DXD3_USE_LARGEWINDOW64=0
70 buildit 32 64 71 # buildit 32 64
71 72
72 resetflag $MACH 73 resetflag $MACH
73 addflag -DXD3_USE_LARGEFILE64=1 74 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 @@
7#include <map> 7#include <map>
8#include <algorithm> 8#include <algorithm>
9 9
10extern "C" {
11uint32_t xd3_large32_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look);
12uint32_t xd3_large32_cksum_update_old (xd3_hash_cfg *cfg, uint32_t cksum,
13 const uint8_t *base, const usize_t look);
14
15uint64_t xd3_large64_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look);
16uint64_t xd3_large64_cksum_update_old (xd3_hash_cfg *cfg, uint64_t cksum,
17 const uint8_t *base, const usize_t look);
18}
19
10using std::list; 20using std::list;
11using std::map; 21using std::map;
12using std::vector; 22using std::vector;
@@ -24,6 +34,14 @@ uint64_t good_64bit_values[] = {
24 7664345821815920749ULL, // ... 34 7664345821815920749ULL, // ...
25}; 35};
26 36
37void print_header() {
38 static int hdr_cnt = 0;
39 if (hdr_cnt++ % 20 == 0) {
40 printf("Name\t\t\t\tConf\t\tCount\tUniq\tFull\tCover\tColls"
41 "\tMB/s\tIters\t#Colls\n");
42 }
43}
44
27struct true_type { }; 45struct true_type { };
28struct false_type { }; 46struct false_type { };
29 47
@@ -51,13 +69,6 @@ struct hhash { // shift "s" bits leaving the high bits as a hash value for
51}; 69};
52 70
53template <typename Word> 71template <typename Word>
54struct nonhash {
55 Word operator()(const Word t, const Word h, const Word mask) {
56 return (t >> h) & mask;
57 }
58};
59
60template <typename Word>
61Word good_word(); 72Word good_word();
62 73
63template<> 74template<>
@@ -92,14 +103,18 @@ struct cksum_params {
92MEMBER 103MEMBER
93struct rabin_karp : public cksum_params<SELF> { 104struct rabin_karp : public cksum_params<SELF> {
94 // (a^cksum_size-1 c_0) + (a^cksum_size-2 c_1) ... 105 // (a^cksum_size-1 c_0) + (a^cksum_size-2 c_1) ...
95 rabin_karp() { 106 rabin_karp()
96 multiplier = good_word<Word>(); 107 : powers(make_powers()),
97 powers = new Word[CksumSize]; 108 product(powers[0] * good_word<Word>()),
98 powers[CksumSize - 1] = 1; 109 incr_state(0) { }
110
111 static Word* make_powers() {
112 Word *p = new Word[CksumSize];
113 p[CksumSize - 1] = 1;
99 for (int i = CksumSize - 2; i >= 0; i--) { 114 for (int i = CksumSize - 2; i >= 0; i--) {
100 powers[i] = powers[i + 1] * multiplier; 115 p[i] = p[i + 1] * good_word<Word>();
101 } 116 }
102 product = powers[0] * multiplier; 117 return p;
103 } 118 }
104 119
105 ~rabin_karp() { 120 ~rabin_karp() {
@@ -120,21 +135,69 @@ struct rabin_karp : public cksum_params<SELF> {
120 } 135 }
121 136
122 Word incr(const uint8_t *ptr) { 137 Word incr(const uint8_t *ptr) {
123 incr_state = multiplier * incr_state - 138 incr_state = good_word<Word>() * incr_state -
124 product * (ptr[-1]) + (ptr[CksumSize - 1]); 139 product * (ptr[-1]) + (ptr[CksumSize - 1]);
125 return incr_state; 140 return incr_state;
126 } 141 }
127 142
128 Word *powers; 143 const Word *const powers;
129 Word product; 144 const Word product;
130 Word multiplier; 145 Word incr_state;
131 Word incr_state; 146};
147
148MEMBER
149struct with_stream : public cksum_params<SELF> {
150 xd3_stream stream;
151
152 with_stream()
153 {
154 xd3_config cfg;
155 memset (&stream, 0, sizeof (stream));
156 xd3_init_config (&cfg, 0);
157 cfg.smatch_cfg = XD3_SMATCH_SOFT;
158 cfg.smatcher_soft.large_look = CksumSize;
159 cfg.smatcher_soft.large_step = CksumSkip;
160 cfg.smatcher_soft.small_look = 4;
161 cfg.smatcher_soft.small_chain = 4;
162 cfg.smatcher_soft.small_lchain = 4;
163 cfg.smatcher_soft.max_lazy = 4;
164 cfg.smatcher_soft.long_enough = 4;
165 CHECK_EQ(0, xd3_config_stream (&stream, &cfg));
166
167 CHECK_EQ(0, xd3_size_hashtable (&stream,
168 1<<10 /* ignored */,
169 stream.smatcher.large_look,
170 & stream.large_hash));
171 }
172 ~with_stream()
173 {
174 xd3_free_stream (&stream);
175 }
176};
177
178MEMBER
179struct large64_cksum : public with_stream<SELF> {
180 Word step(const uint8_t *ptr) {
181 return xd3_large64_cksum (&this->stream.large_hash, ptr, CksumSize);
182 }
183
184 Word state0(const uint8_t *ptr) {
185 incr_state = step(ptr);
186 return incr_state;
187 }
188
189 Word incr(const uint8_t *ptr) {
190 incr_state = xd3_large64_cksum_update (&this->stream.large_hash, incr_state, ptr - 1, CksumSize);
191 return incr_state;
192 }
193
194 Word incr_state;
132}; 195};
133 196
134MEMBER 197MEMBER
135struct large_cksum : public cksum_params<SELF> { 198struct large64_cksum_old : public with_stream<SELF> {
136 Word step(const uint8_t *ptr) { 199 Word step(const uint8_t *ptr) {
137 return xd3_large_cksum (ptr, CksumSize); 200 return xd3_large64_cksum_old (&this->stream.large_hash, ptr, CksumSize);
138 } 201 }
139 202
140 Word state0(const uint8_t *ptr) { 203 Word state0(const uint8_t *ptr) {
@@ -143,13 +206,67 @@ struct large_cksum : public cksum_params<SELF> {
143 } 206 }
144 207
145 Word incr(const uint8_t *ptr) { 208 Word incr(const uint8_t *ptr) {
146 incr_state = xd3_large_cksum_update (incr_state, ptr - 1, CksumSize); 209 incr_state = xd3_large64_cksum_update_old (&this->stream.large_hash, incr_state, ptr - 1, CksumSize);
147 return incr_state; 210 return incr_state;
148 } 211 }
149 212
150 Word incr_state; 213 Word incr_state;
151}; 214};
152 215
216MEMBER
217struct large32_cksum : public with_stream<SELF> {
218 Word step(const uint8_t *ptr) {
219 return xd3_large32_cksum (&this->stream.large_hash, ptr, CksumSize);
220 }
221
222 Word state0(const uint8_t *ptr) {
223 incr_state = step(ptr);
224 return incr_state;
225 }
226
227 Word incr(const uint8_t *ptr) {
228 incr_state = xd3_large32_cksum_update (&this->stream.large_hash, incr_state, ptr - 1, CksumSize);
229 return incr_state;
230 }
231
232 Word incr_state;
233};
234
235MEMBER
236struct large32_cksum_old : public with_stream<SELF> {
237 Word step(const uint8_t *ptr) {
238 return xd3_large32_cksum_old (&this->stream.large_hash, ptr, CksumSize);
239 }
240
241 Word state0(const uint8_t *ptr) {
242 incr_state = step(ptr);
243 return incr_state;
244 }
245
246 Word incr(const uint8_t *ptr) {
247 incr_state = xd3_large32_cksum_update_old (&this->stream.large_hash, incr_state, ptr - 1, CksumSize);
248 return incr_state;
249 }
250
251 Word incr_state;
252};
253
254MEMBER
255struct large_cksum
256 : std::conditional<std::is_same<Word, uint32_t>::value,
257 large32_cksum<SELF>,
258 large64_cksum<SELF>>::type
259{
260};
261
262MEMBER
263struct large_cksum_old
264 : std::conditional<std::is_same<Word, uint32_t>::value,
265 large32_cksum_old<SELF>,
266 large64_cksum_old<SELF>>::type
267{
268};
269
153// TESTS 270// TESTS
154 271
155template <typename Word> 272template <typename Word>
@@ -193,13 +310,21 @@ struct file_stats {
193 310
194 ptr_list &pl = table[word]; 311 ptr_list &pl = table[word];
195 312
313 int collisions = 0;
196 for (ptr_iterator p_i = pl.begin(); 314 for (ptr_iterator p_i = pl.begin();
197 p_i != pl.end(); 315 p_i != pl.end();
198 ++p_i) { 316 ++p_i) {
199 if (memcmp(*p_i, ptr, cksum_size) == 0) { 317 if (memcmp(*p_i, ptr, cksum_size) == 0) {
200 return; 318 return;
201 } 319 }
320 collisions++;
202 } 321 }
322 if (collisions >= 10000)
323 {
324 fprintf(stderr, "Something is not right, lots of collisions=%d\n",
325 collisions);
326 abort();
327 }
203 328
204 unique++; 329 unique++;
205 pl.push_back(ptr); 330 pl.push_back(ptr);
@@ -320,7 +445,7 @@ struct test_result : public test_result_base {
320 /* Fraction of distinct strings of length cksum_size which are not 445 /* Fraction of distinct strings of length cksum_size which are not
321 * represented in the hash table. */ 446 * represented in the hash table. */
322 double collisions() { 447 double collisions() {
323 return (fstats.unique - fstats.unique_values) / fstats.unique; 448 return (fstats.unique - fstats.unique_values) / (double) fstats.unique;
324 } 449 }
325 usize_t colls() { 450 usize_t colls() {
326 return (fstats.unique - fstats.unique_values); 451 return (fstats.unique - fstats.unique_values);
@@ -375,13 +500,8 @@ struct test_result : public test_result_base {
375 fprintf(stderr, "internal error: %d != %d\n", fstats.count, count()); 500 fprintf(stderr, "internal error: %d != %d\n", fstats.count, count());
376 abort(); 501 abort();
377 } 502 }
378 { 503 print_header();
379 static int hdr_cnt = 0; 504 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",
380 if (hdr_cnt++ % 20 == 0) {
381 printf("Name\tConf\tCount\tUniq\tFull\tColl\tCov\tMB/s\tIters\n");
382 }
383 }
384 printf("%s\t%d/%d/1<<%d\t%u\t%0.2f\t%.2f\t%.2f\t%.2f\t%.4f\t%u\n",
385 test_name, 505 test_name,
386 Checksum::cksum_size, 506 Checksum::cksum_size,
387 Checksum::cksum_skip, 507 Checksum::cksum_skip,
@@ -389,10 +509,11 @@ struct test_result : public test_result_base {
389 count(), 509 count(),
390 uniqueness(), 510 uniqueness(),
391 fullness(), 511 fullness(),
392 collisions(),
393 coverage(), 512 coverage(),
513 collisions(),
394 0.001 * accum_iters * test_size / accum_millis, 514 0.001 * accum_iters * test_size / accum_millis,
395 accum_iters); 515 accum_iters,
516 colls());
396 } 517 }
397 518
398 usize_t size_log2 (usize_t slots) { 519 usize_t size_log2 (usize_t slots) {
@@ -445,8 +566,8 @@ struct test_result : public test_result_base {
445 const uint8_t *ptr; 566 const uint8_t *ptr;
446 const uint8_t *end; 567 const uint8_t *end;
447 usize_t periods; 568 usize_t periods;
448 int last_offset; 569 int64_t last_offset;
449 int stop; 570 int64_t stop;
450 571
451 test_size = buf_size; 572 test_size = buf_size;
452 last_offset = buf_size - Checksum::cksum_size; 573 last_offset = buf_size - Checksum::cksum_size;
@@ -472,7 +593,7 @@ struct test_result : public test_result_base {
472 } else { 593 } else {
473 ptr = buf + last_offset; 594 ptr = buf + last_offset;
474 end = buf + stop; 595 end = buf + stop;
475 596
476 for (; ptr != end; ptr -= Checksum::cksum_skip) { 597 for (; ptr != end; ptr -= Checksum::cksum_skip) {
477 fstats.update(hash(cksum.step(ptr), s_bits, s_mask), ptr); 598 fstats.update(hash(cksum.step(ptr), s_bits, s_mask), ptr);
478 } 599 }
@@ -503,7 +624,6 @@ struct test_result : public test_result_base {
503 } 624 }
504 625
505 if (Checksum::cksum_skip == 1) { 626 if (Checksum::cksum_skip == 1) {
506
507 new_table(n_incrs); 627 new_table(n_incrs);
508 628
509 for (usize_t i = 0; i < test_iters; i++) { 629 for (usize_t i = 0; i < test_iters; i++) {
@@ -516,7 +636,7 @@ struct test_result : public test_result_base {
516 636
517 for (; ptr != end; ptr++) { 637 for (; ptr != end; ptr++) {
518 typename Checksum::word_type w = cksum.incr(ptr); 638 typename Checksum::word_type w = cksum.incr(ptr);
519 assert(w == cksum.step(ptr)); 639 CHECK_EQ(w, cksum.step(ptr));
520 set_table_bit(hash(w, s_bits, s_mask)); 640 set_table_bit(hash(w, s_bits, s_mask));
521 } 641 }
522 } 642 }
@@ -586,30 +706,30 @@ int main(int argc, char** argv) {
586 return 1; 706 return 1;
587 } 707 }
588 708
589#define TEST(T,Z,S,H,C) \ 709#define TEST(T,Z,S,C) \
590 test_result<rabin_karp<T,Z,S,H<T>,C>> \ 710 test_result<rabin_karp<T,Z,S,hhash<T>,C>> \
591 _rka_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C \ 711 _rka_ ## T ## _ ## Z ## _ ## S ## _ ## C \
592 ("rka_" #T "_" #Z "_" #S "_" #H "_" #C); \ 712 ("rka_" #T "_" #Z "_" #S "_" #C); \
593 test_result<large_cksum<T,Z,S,H<T>,C>> \ 713 test_result<large_cksum<T,Z,S,hhash<T>,C>> \
594 _xck_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C \ 714 _xck_ ## T ## _ ## Z ## _ ## S ## _ ## C \
595 ("xck_" #T "_" #Z "_" #S "_" #H "_" #C) 715 ("xck_" #T "_" #Z "_" #S "_" #C); \
596 716 test_result<large_cksum_old<T,Z,S,hhash<T>,C>> \
717 _old_ ## T ## _ ## Z ## _ ## S ## _ ## C \
718 ("old_" #T "_" #Z "_" #S "_" #C)
597 719
598#define TESTS(SIZE, SKIP) \ 720#define TESTS(SIZE, SKIP) \
599 TEST(uint32_t, SIZE, SKIP, nonhash, 1); \ 721 TEST(uint32_t, SIZE, SKIP, 1); \
600 TEST(uint32_t, SIZE, SKIP, nonhash, 2); \ 722 TEST(uint32_t, SIZE, SKIP, 2); \
601 TEST(uint32_t, SIZE, SKIP, hhash, 1); \ 723 TEST(uint64_t, SIZE, SKIP, 1); \
602 TEST(uint32_t, SIZE, SKIP, hhash, 2); \ 724 TEST(uint64_t, SIZE, SKIP, 2)
603 TEST(uint64_t, SIZE, SKIP, nonhash, 1); \
604 TEST(uint64_t, SIZE, SKIP, nonhash, 2); \
605 TEST(uint64_t, SIZE, SKIP, hhash, 1); \
606 TEST(uint64_t, SIZE, SKIP, hhash, 2)
607 725
726 TESTS(9, 1);
608 TESTS(9, 9); 727 TESTS(9, 9);
609 // TESTS(9, 15); 728 TESTS(15, 1);
610 TESTS(15, 15); 729 TESTS(15, 15);
730 TESTS(127, 1);
611 TESTS(127, 127); 731 TESTS(127, 127);
612 // TESTS(127, 211); 732 TESTS(211, 1);
613 TESTS(211, 211); 733 TESTS(211, 211);
614 734
615 for (i = 1; i < argc; i++) { 735 for (i = 1; i < argc; i++) {
@@ -630,7 +750,7 @@ int main(int argc, char** argv) {
630 test_result_base *test = *iter; 750 test_result_base *test = *iter;
631 test->reset(); 751 test->reset();
632 752
633 usize_t iters = 100; 753 usize_t iters = 200;
634 long start_test = get_millisecs_now(); 754 long start_test = get_millisecs_now();
635 755
636 do { 756 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 @@
1#include "../xdelta3.c" 1#include "../xdelta3.c"
2
3// OLD CHECKSUM CODE
4
5#define PERMUTE32(x) (__single_hash32[x])
6#define PERMUTE64(x) (__single_hash64[x])
7
8const uint16_t __single_hash32[256] =
9{
10 /* This hashes the input alphabet (Scheme SLIB pseudo-random). */
11 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46,
12 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602,
13 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6,
14 0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a,
15 0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58,
16 0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b,
17 0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94,
18 0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176,
19 0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743,
20 0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6,
21 0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227,
22 0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d,
23 0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a,
24 0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31,
25 0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9,
26 0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6,
27 0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f,
28 0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f,
29 0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49,
30 0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037,
31 0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad,
32 0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f,
33 0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d,
34 0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b,
35 0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624,
36 0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272,
37 0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806,
38 0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050,
39 0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113,
40 0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2,
41 0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25,
42 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5
43};
44
45const uint32_t __single_hash64[256] =
46{
47 /* http://random.org 2014.10.24 */
48 0xd25e9f0a, 0xb1af9d5e, 0xb753dfa2, 0x157050f7, /* 0 */
49 0xc84b072c, 0xdd14fe7c, 0xf92208c3, 0xdf08a0c0,
50 0x63a5c118, 0x76f5d90f, 0xa2f8b93e, 0xb6c12d22,
51 0xaf074957, 0x966fb7d9, 0x62f7b785, 0xb40e8a09,
52 0x0a811d5d, 0x323a6daa, 0xb62f7c5b, 0xfdcb9a53,
53 0xf25a9067, 0x4506bc7a, 0xff58a74b, 0x5ae62817,
54 0x74097675, 0x722c0fd9, 0x116a2a66, 0x65f76728,
55 0x72c79651, 0xe043cf9d, 0x64b867c7, 0x6604834f,
56 0xcdca58a6, 0x0f164e2d, 0x24515f05, 0x632cdbf8,
57 0x18091d4a, 0x3eff4128, 0x673d1c33, 0xd8e10c71,
58 0x1a3edf11, 0xba52892f, 0xa56949e0, 0xf3e1dd77, /* 10 */
59 0x86fcbe3e, 0x138d66d0, 0x4fc98359, 0xc22e5dd6,
60 0xc59f2267, 0x6c6dd739, 0xe03da190, 0x07e8469c,
61 0xadcfb02c, 0x00d3b0d9, 0xa1f44918, 0x8bd84d87,
62 0x08ec9ec1, 0xbbcd156f, 0xb57718e3, 0x3177e752,
63 0xf52a4d70, 0xde7aaad9, 0x075f1da0, 0x21ba00c6,
64 0xb9469a5c, 0xcf08d5ba, 0x91ac9edc, 0xc6167b63,
65 0xc1974919, 0xc8c8d195, 0x4b1996dd, 0xeff8991c,
66 0xf7f66c6b, 0x25b012e2, 0x59d12a98, 0xea40d3cc,
67 0x41f9970b, 0xec48101a, 0xa3bdcf90, 0x99f16905,
68 0x27af6c97, 0xc849af37, 0x49cad89b, 0xf48c2278, /* 20 */
69 0x5529c3d8, 0x9e7d6dce, 0x16feb52d, 0xf1b0aca1,
70 0xaf28fccb, 0x48e4ce3c, 0xc4436617, 0x64524e3e,
71 0x61806681, 0x6384f2d7, 0x1172880f, 0x34a5ef5f,
72 0xcc8cc0a8, 0x66e8f100, 0x2866085f, 0xba9b1b2d,
73 0x51285949, 0x2be4b574, 0x889b1ef5, 0x3dbe920d,
74 0x9277a62f, 0x0584a9f6, 0x085d8fc4, 0x4b5d403d,
75 0x4e46ca78, 0x3294c2f9, 0x29313e70, 0xe4f09b24,
76 0xe73b331c, 0x072f5552, 0x2e390b78, 0xea0021ca,
77 0xd8f40320, 0xed0e16fd, 0x7de9cf7a, 0xf17e3d6c,
78 0x8df1bd85, 0x052cae67, 0x3486e512, 0x3a1c09b8, /* 30 */
79 0x6c2a7b4e, 0x83455753, 0xbc0353ac, 0x0ffe20b6,
80 0x5fdcef85, 0x010f506c, 0x595ce972, 0xe28680d0,
81 0xa7e216b2, 0xa392ee0f, 0x25b73faa, 0x2b1f4983,
82 0xeeaefe98, 0x1d3d9cbc, 0x6aebe97b, 0x8b7b3584,
83 0x9e6a9a07, 0xd37f1e99, 0x4ac2a441, 0x8ae9a213,
84 0x7d0e27d7, 0x5de54b9a, 0x8621de1f, 0xf0f2f866,
85 0xcb08d275, 0x49c3f87e, 0xd5ee68c1, 0x9802fc77,
86 0x68be6c5e, 0x65aa8c27, 0xf423d5f7, 0x10ec5502,
87 0x9909bce1, 0x509cdf1b, 0x338fea72, 0x2733e9bf,
88 0xf92f4fd7, 0x87738ea2, 0x931a8bbc, 0x0a5c9155, /* 40 */
89 0xbe5edd9b, 0xadbf5838, 0x0338f8d2, 0x290da210,
90 0x390c37d8, 0xe7cffae8, 0x20617ebe, 0x464322dd,
91 0x7b3c4e78, 0xac142dcb, 0x2d5cef76, 0xd8fe49fc,
92 0x60f4e9a9, 0x7473816f, 0x0dc35f39, 0x5eed80c1,
93 0x0cb55ab6, 0x1d3ac541, 0x13c7f529, 0x7bffdf4a,
94 0xe334785b, 0x85263ec1, 0xd132ae56, 0x7c868b9e,
95 0x47f60638, 0x1012b979, 0x81c31dd3, 0x1af868c8,
96 0x0c5d0742, 0xd1b3e1a2, 0x5873200a, 0xf848465c,
97 0x0fc4d596, 0x609c18af, 0xc9f5a480, 0xd1a94a84,
98 0xa1431a3f, 0x7de8bb1a, 0x25f1256b, 0x1dcc732c, /* 50 */
99 0x6aa1549a, 0xa2367281, 0x32f2a77e, 0x82e62a0f,
100 0x045cbb56, 0x74b2027c, 0xd71a32d9, 0x022e7cb5,
101 0xe99be177, 0x60222fdf, 0xd69681ca, 0x9008ee2c,
102 0x32923db4, 0xcf82bf97, 0x38960a5b, 0xb3503d5b,
103 0x9bd4c7f2, 0x33c029c8, 0x1ef504a3, 0xdb249d3b,
104 0x91e89676, 0x4ca43b36, 0x9191433c, 0x465d5dc4,
105 0xf4dcb118, 0x9d11dd00, 0xb592f058, 0xdbe5ce30,
106 0x74790d92, 0x779850a8, 0x7180d25b, 0xfa951d99,
107 0x5990935a, 0x921cb022, 0x3b7c39bc, 0x6a38a7c7,
108 0xdc22703b, 0x142bab3b, 0x4e3d9479, 0x44bb8482, /* 60 */
109 0x8043abce, 0xfebe832a, 0x8e6a2f98, 0x4d43c4fe,
110 0xd192a70a, 0x802f3c3a, 0x5d11bbab, 0x2665d241,
111 0xb3f3a680, 0x3a8d223f, 0xcf82cdb4, 0x4ed28743,
112};
113
114uint64_t
115xd3_large64_cksum_old (xd3_hash_cfg *ignore, const uint8_t *base, const usize_t look)
116{
117 static const uint64_t kBits = 32;
118 static const uint64_t kMask = 0xffffffff;
119 usize_t i = 0;
120 uint64_t low = 0;
121 uint64_t high = 0;
122
123 for (; i < look; i += 1)
124 {
125 low += PERMUTE64(*base++);
126 high += low;
127 }
128
129 return ((high & kMask) << kBits) | (low & kMask);
130}
131
132uint64_t
133xd3_large64_cksum_update_old (xd3_hash_cfg *ignore, const uint64_t cksum,
134 const uint8_t *base, const usize_t look)
135{
136 static const uint64_t kBits = 32;
137 static const uint64_t kMask = 0xffffffff;
138 uint64_t old_c = PERMUTE64(base[0]);
139 uint64_t new_c = PERMUTE64(base[look]);
140 uint64_t low = ((cksum & kMask) - old_c + new_c) & kMask;
141 uint64_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask;
142 return (high << kBits) | low;
143}
144
145uint32_t
146xd3_large32_cksum_old (xd3_hash_cfg *ignore, const uint8_t *base, const usize_t look)
147{
148 static const uint32_t kBits = 16;
149 static const uint32_t kMask = 0xffff;
150 usize_t i = 0;
151 uint32_t low = 0;
152 uint32_t high = 0;
153
154 for (; i < look; i += 1)
155 {
156 low += PERMUTE32(*base++);
157 high += low;
158 }
159
160 return ((high & kMask) << kBits) | (low & kMask);
161}
162
163uint32_t
164xd3_large32_cksum_update_old (xd3_hash_cfg *ignore, const uint32_t cksum,
165 const uint8_t *base, const usize_t look)
166{
167 static const uint32_t kBits = 16;
168 static const uint32_t kMask = 0xffff;
169 uint32_t old_c = PERMUTE32(base[0]);
170 uint32_t new_c = PERMUTE32(base[look]);
171 uint32_t low = ((cksum & kMask) - old_c + new_c) & kMask;
172 uint32_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask;
173 return (high << kBits) | low;
174}
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" {
18 18
19#define CHECK_OP(x,y,OP) \ 19#define CHECK_OP(x,y,OP) \
20 do { \ 20 do { \
21 typeof(x) _x(x); \ 21 __typeof__(x) _x(x); \
22 typeof(x) _y(y); \ 22 __typeof__(x) _y(y); \
23 if (!(_x OP _y)) { \ 23 if (!(_x OP _y)) { \
24 cerr << __FILE__ << ":" << __LINE__ << " Check failed: " << #x " " #OP " " #y << endl; \ 24 cerr << __FILE__ << ":" << __LINE__ << " Check failed: " << #x " " #OP " " #y << endl; \
25 cerr << __FILE__ << ":" << __LINE__ << " Expected: " << _x << endl; \ 25 cerr << __FILE__ << ":" << __LINE__ << " Expected: " << _x << endl; \
@@ -68,5 +68,3 @@ pair<T, U> make_pair(const T& t, const U& u) {
68 68
69using std::min; 69using std::min;
70using std::max; 70using std::max;
71
72
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 @@
41#define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4); 41#define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4);
42#endif 42#endif
43 43
44/* This is a good hash multiplier for 32-bit LCGs: see "linear 44/* These are good hash multipliers for 32-bit and 64-bit LCGs: see
45 * congruential generators of different sizes and good lattice 45 * "linear congruential generators of different sizes and good lattice
46 * structure" */ 46 * structure" */
47static const uint32_t hash_multiplier = 1597334677U; 47#define xd3_hash_multiplier32 1597334677U
48#define xd3_hash_multiplier64 1181783497276652981ULL
48 49
49/* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */ 50/* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */
50static inline uint32_t 51static inline uint32_t
@@ -53,7 +54,7 @@ xd3_scksum (uint32_t *state,
53 const usize_t look) 54 const usize_t look)
54{ 55{
55 UNALIGNED_READ32(state, base); 56 UNALIGNED_READ32(state, base);
56 return (*state) * hash_multiplier; 57 return (*state) * xd3_hash_multiplier32;
57} 58}
58static inline uint32_t 59static inline uint32_t
59xd3_small_cksum_update (uint32_t *state, 60xd3_small_cksum_update (uint32_t *state,
@@ -61,112 +62,48 @@ xd3_small_cksum_update (uint32_t *state,
61 usize_t look) 62 usize_t look)
62{ 63{
63 UNALIGNED_READ32(state, base+1); 64 UNALIGNED_READ32(state, base+1);
64 return (*state) * hash_multiplier; 65 return (*state) * xd3_hash_multiplier32;
65} 66}
66 67
67static inline usize_t 68#if XD3_ENCODER
69inline usize_t
68xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) 70xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum)
69{ 71{
70 return (cksum >> cfg->shift) ^ (cksum & cfg->mask); 72 return (cksum >> cfg->shift) ^ (cksum & cfg->mask);
71} 73}
72 74
73#if XD3_ENCODER
74#define PERMUTE32(x) (__single_hash32[x])
75extern const uint16_t __single_hash32[256];
76
77inline uint32_t 75inline uint32_t
78xd3_large32_cksum (const uint8_t *seg, const usize_t ln) 76xd3_large32_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look)
79{ 77{
80 static const uint32_t kBits = 16; 78 uint32_t h = 0;
81 static const uint32_t kMask = 0xffff; 79 for (usize_t i = 0; i < look; i++) {
82 usize_t i = 0; 80 h += base[i] * cfg->powers[i];
83 uint32_t low = 0; 81 }
84 uint32_t high = 0; 82 return h;
85
86 for (; i < ln; i += 1)
87 {
88 low += PERMUTE32(*seg++);
89 high += low;
90 }
91
92 return ((high & kMask) << kBits) | (low & kMask);
93} 83}
94 84
95inline uint32_t 85inline uint32_t
96xd3_large32_cksum_update (uint32_t cksum, 86xd3_large32_cksum_update (xd3_hash_cfg *cfg, const uint32_t cksum,
97 const uint8_t *base, 87 const uint8_t *base, const usize_t look)
98 usize_t look)
99{ 88{
100 static const uint32_t kBits = 16; 89 return xd3_hash_multiplier32 * cksum - cfg->multiplier * base[0] + base[look];
101 static const uint32_t kMask = 0xffff;
102 uint32_t old_c = PERMUTE32(base[0]);
103 uint32_t new_c = PERMUTE32(base[look]);
104 uint32_t low = ((cksum & kMask) - old_c + new_c) & kMask;
105 uint32_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask;
106 return (high << kBits) | low;
107} 90}
108 91
109#undef PERMUTE32
110
111#define PERMUTE64(x) (__single_hash64[x])
112extern const uint32_t __single_hash64[256];
113
114inline uint64_t 92inline uint64_t
115xd3_large64_cksum (const uint8_t *seg, const usize_t len) 93xd3_large64_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look)
116{ 94{
117 static const uint64_t kBits = 32; 95 uint64_t h = 0;
118 static const uint64_t kMask = 0xffffffff; 96 for (usize_t i = 0; i < look; i++) {
119 usize_t i = 0; 97 h += base[i] * cfg->powers[i];
120 uint64_t low = 0; 98 }
121 uint64_t high = 0; 99 return h;
122
123 for (; i < len; i += 1)
124 {
125 low += PERMUTE64(*seg++);
126 high += low;
127 }
128
129 return ((high & kMask) << kBits) | (low & kMask);
130} 100}
131 101
132inline uint64_t 102inline uint64_t
133xd3_large64_cksum_update (uint64_t cksum, 103xd3_large64_cksum_update (xd3_hash_cfg *cfg, const uint64_t cksum,
134 const uint8_t *base, 104 const uint8_t *base, const usize_t look)
135 usize_t look)
136{ 105{
137 static const uint64_t kBits = 32; 106 return xd3_hash_multiplier64 * cksum - cfg->multiplier * base[0] + base[look];
138 static const uint64_t kMask = 0xffffffff;
139 uint64_t old_c = PERMUTE64(base[0]);
140 uint64_t new_c = PERMUTE64(base[look]);
141 uint64_t low = ((cksum & kMask) - old_c + new_c) & kMask;
142 uint64_t high = ((cksum >> kBits) - (old_c * look) + low) & kMask;
143 return (high << kBits) | low;
144}
145
146#undef PERMUTE64
147
148inline usize_t
149xd3_large_cksum (const uint8_t *seg, const usize_t len)
150{
151 if (SIZEOF_USIZE_T == 4)
152 {
153 return xd3_large32_cksum (seg, len);
154 }
155 else
156 {
157 return xd3_large64_cksum (seg, len);
158 }
159}
160
161inline usize_t
162xd3_large_cksum_update (usize_t cksum,
163 const uint8_t *base,
164 usize_t look) {
165#if SIZEOF_USIZE_T == 4
166 return xd3_large32_cksum_update (cksum, base, look);
167#else
168 return xd3_large64_cksum_update (cksum, base, look);
169#endif
170} 107}
171 108
172static usize_t 109static usize_t
@@ -179,9 +116,9 @@ xd3_size_hashtable_bits (usize_t slots)
179 { 116 {
180 if (slots < (1U << i)) 117 if (slots < (1U << i))
181 { 118 {
182 /* TODO: this is compaction=1 in checksum_test.cc and maybe should 119 /* Note: this is the compaction=1 setting measured in
183 * not be fixed at -1. */ 120 * checksum_test */
184 bits = i - 1; 121 bits = i - 1;
185 break; 122 break;
186 } 123 }
187 } 124 }
@@ -189,9 +126,10 @@ xd3_size_hashtable_bits (usize_t slots)
189 return bits; 126 return bits;
190} 127}
191 128
192static void 129int
193xd3_size_hashtable (xd3_stream *stream, 130xd3_size_hashtable (xd3_stream *stream,
194 usize_t slots, 131 usize_t slots,
132 usize_t look,
195 xd3_hash_cfg *cfg) 133 xd3_hash_cfg *cfg)
196{ 134{
197 usize_t bits = xd3_size_hashtable_bits (slots); 135 usize_t bits = xd3_size_hashtable_bits (slots);
@@ -199,7 +137,23 @@ xd3_size_hashtable (xd3_stream *stream,
199 cfg->size = (1U << bits); 137 cfg->size = (1U << bits);
200 cfg->mask = (cfg->size - 1); 138 cfg->mask = (cfg->size - 1);
201 cfg->shift = (SIZEOF_USIZE_T * 8) - bits; 139 cfg->shift = (SIZEOF_USIZE_T * 8) - bits;
140 cfg->look = look;
141
142 if ((cfg->powers =
143 (usize_t*) xd3_alloc0 (stream, look, sizeof (usize_t))) == NULL)
144 {
145 return ENOMEM;
146 }
147
148 cfg->powers[look-1] = 1;
149 for (int i = look-2; i >= 0; i--)
150 {
151 cfg->powers[i] = cfg->powers[i+1] * xd3_hash_multiplier;
152 }
153 cfg->multiplier = cfg->powers[0] * xd3_hash_multiplier;
154
155 return 0;
202} 156}
203 157
204#endif 158#endif /* XD3_ENCODER */
205#endif /* _XDELTA3_HASH_H_ */ 159#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,
64int xd3_main_cmdline (int argc, char **argv); 64int xd3_main_cmdline (int argc, char **argv);
65#endif 65#endif
66 66
67#if REGRESSION_TEST
68int xd3_selftest (void);
69#endif
70
67/* main_file->mode values */ 71/* main_file->mode values */
68typedef enum 72typedef enum
69{ 73{
@@ -155,9 +159,59 @@ void xprintf(const char *fmt, ...) PRINTF_ATTRIBUTE(1,2);
155#define UINT64_MAX 18446744073709551615ULL 159#define UINT64_MAX 18446744073709551615ULL
156#endif 160#endif
157 161
158usize_t xd3_large_cksum (const uint8_t *seg, const usize_t ln); 162#define UINT32_OFLOW_MASK 0xfe000000U
159usize_t xd3_large_cksum_update (usize_t cksum, 163#define UINT64_OFLOW_MASK 0xfe00000000000000ULL
160 const uint8_t *base, 164
161 usize_t look); 165#if SIZEOF_USIZE_T == 4
166#define USIZE_T_MAX UINT32_MAX
167#define xd3_decode_size xd3_decode_uint32_t
168#define xd3_emit_size xd3_emit_uint32_t
169#define xd3_sizeof_size xd3_sizeof_uint32_t
170#define xd3_read_size xd3_read_uint32_t
171#define xd3_large_cksum xd3_large32_cksum
172#define xd3_large_cksum_update xd3_large32_cksum_update
173#define xd3_hash_multiplier xd3_hash_multiplier32
174#elif SIZEOF_USIZE_T == 8
175#define USIZE_T_MAX UINT64_MAX
176#define xd3_decode_size xd3_decode_uint64_t
177#define xd3_emit_size xd3_emit_uint64_t
178#define xd3_sizeof_size xd3_sizeof_uint64_t
179#define xd3_read_size xd3_read_uint64_t
180#define xd3_large_cksum xd3_large64_cksum
181#define xd3_large_cksum_update xd3_large64_cksum_update
182#define xd3_hash_multiplier xd3_hash_multiplier64
183#endif
184
185#if SIZEOF_XOFF_T == 4
186#define XOFF_T_MAX UINT32_MAX
187#define xd3_decode_offset xd3_decode_uint32_t
188#define xd3_emit_offset xd3_emit_uint32_t
189#elif SIZEOF_XOFF_T == 8
190#define XOFF_T_MAX UINT64_MAX
191#define xd3_decode_offset xd3_decode_uint64_t
192#define xd3_emit_offset xd3_emit_uint64_t
193#endif
194
195#define USIZE_T_OVERFLOW(a,b) ((USIZE_T_MAX - (usize_t) (a)) < (usize_t) (b))
196#define XOFF_T_OVERFLOW(a,b) ((XOFF_T_MAX - (xoff_t) (a)) < (xoff_t) (b))
197
198int xd3_size_hashtable (xd3_stream *stream,
199 usize_t slots,
200 usize_t look,
201 xd3_hash_cfg *cfg);
202
203usize_t xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum);
204
205#if USE_UINT32
206uint32_t xd3_large32_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look);
207uint32_t xd3_large32_cksum_update (xd3_hash_cfg *cfg, uint32_t cksum,
208 const uint8_t *base, const usize_t look);
209#endif /* USE_UINT32 */
210
211#if USE_UINT64
212uint64_t xd3_large64_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look);
213uint64_t xd3_large64_cksum_update (xd3_hash_cfg *cfg, uint64_t cksum,
214 const uint8_t *base, const usize_t look);
215#endif /* USE_UINT64 */
162 216
163#endif /* XDELTA3_INTERNAL_H__ */ 217#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)
1556 return 0; 1556 return 0;
1557} 1557}
1558 1558
1559static int
1560test_checksum_step (xd3_stream *stream, int ignore)
1561{
1562 const int bufsize = 128;
1563 uint8_t buf[bufsize];
1564 for (int i = 0; i < bufsize; i++)
1565 {
1566 buf[i] = mt_random (&static_mtrand) & 0xff;
1567 }
1568
1569 for (usize_t cksize = 4; cksize <= 32; cksize += 3)
1570 {
1571 xd3_hash_cfg h1;
1572 usize_t x;
1573 int ret;
1574
1575 if ((ret = xd3_size_hashtable (stream, XD3_ALLOCSIZE, cksize, &h1)) != 0)
1576 {
1577 return ret;
1578 }
1579
1580 x = xd3_large_cksum (&h1, buf, cksize);
1581 for (usize_t pos = 0; pos <= (bufsize - cksize); pos++)
1582 {
1583 usize_t y = xd3_large_cksum (&h1, buf + pos, cksize);
1584 if (x != y)
1585 {
1586 stream->msg = "checksum != incremental checksum";
1587 return XD3_INTERNAL;
1588 }
1589 x = xd3_large_cksum_update (&h1, x, buf + pos, cksize);
1590 }
1591
1592 xd3_free (stream, h1.powers);
1593 }
1594
1595 return 0;
1596}
1597
1559/*********************************************************************** 1598/***********************************************************************
1560 64BIT STREAMING 1599 64BIT STREAMING
1561 ***********************************************************************/ 1600 ***********************************************************************/
@@ -2839,8 +2878,7 @@ test_in_memory (xd3_stream *stream, int ignore)
2839 TEST MAIN 2878 TEST MAIN
2840 ***********************************************************************/ 2879 ***********************************************************************/
2841 2880
2842static int 2881int xd3_selftest (void)
2843xd3_selftest (void)
2844{ 2882{
2845#define DO_TEST(fn,flags,arg) \ 2883#define DO_TEST(fn,flags,arg) \
2846 do { \ 2884 do { \
@@ -2867,8 +2905,8 @@ xd3_selftest (void)
2867 DO_TEST (encode_decode_uint32_t, 0, 0); 2905 DO_TEST (encode_decode_uint32_t, 0, 0);
2868 DO_TEST (encode_decode_uint64_t, 0, 0); 2906 DO_TEST (encode_decode_uint64_t, 0, 0);
2869 DO_TEST (usize_t_overflow, 0, 0); 2907 DO_TEST (usize_t_overflow, 0, 0);
2908 DO_TEST (checksum_step, 0, 0);
2870 DO_TEST (forward_match, 0, 0); 2909 DO_TEST (forward_match, 0, 0);
2871
2872 DO_TEST (address_cache, 0, 0); 2910 DO_TEST (address_cache, 0, 0);
2873 2911
2874 DO_TEST (string_matching, 0, 0); 2912 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,
549static void* xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size); 549static void* xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size);
550static void xd3_free (xd3_stream *stream, void *ptr); 550static void xd3_free (xd3_stream *stream, void *ptr);
551 551
552#if USE_UINT32
553static int xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp,
554 const uint8_t *max, uint32_t *valp);
555#endif
556#if USE_UINT64
557static int xd3_read_uint64_t (xd3_stream *stream, const uint8_t **inpp,
558 const uint8_t *max, uint64_t *valp);
559#endif
560#if REGRESSION_TEST
561static int xd3_selftest (void);
562#endif
563
564/***********************************************************************/
565
566#define UINT32_OFLOW_MASK 0xfe000000U
567#define UINT64_OFLOW_MASK 0xfe00000000000000ULL
568
569#if SIZEOF_USIZE_T == 4
570#define USIZE_T_MAX UINT32_MAX
571#define xd3_decode_size xd3_decode_uint32_t
572#define xd3_emit_size xd3_emit_uint32_t
573#define xd3_sizeof_size xd3_sizeof_uint32_t
574#define xd3_read_size xd3_read_uint32_t
575#elif SIZEOF_USIZE_T == 8
576#define USIZE_T_MAX UINT64_MAX
577#define xd3_decode_size xd3_decode_uint64_t
578#define xd3_emit_size xd3_emit_uint64_t
579#define xd3_sizeof_size xd3_sizeof_uint64_t
580#define xd3_read_size xd3_read_uint64_t
581#endif
582
583#if SIZEOF_XOFF_T == 4
584#define XOFF_T_MAX UINT32_MAX
585#define xd3_decode_offset xd3_decode_uint32_t
586#define xd3_emit_offset xd3_emit_uint32_t
587#elif SIZEOF_XOFF_T == 8
588#define XOFF_T_MAX UINT64_MAX
589#define xd3_decode_offset xd3_decode_uint64_t
590#define xd3_emit_offset xd3_emit_uint64_t
591#endif
592
593#define USIZE_T_OVERFLOW(a,b) ((USIZE_T_MAX - (usize_t) (a)) < (usize_t) (b))
594#define XOFF_T_OVERFLOW(a,b) ((XOFF_T_MAX - (xoff_t) (a)) < (xoff_t) (b))
595
596const char* xd3_strerror (int ret) 552const char* xd3_strerror (int ret)
597{ 553{
598 switch (ret) 554 switch (ret)
@@ -798,112 +754,6 @@ const xd3_sec_type lzma_sec_type =
798#endif /* __XDELTA3_C_HEADER_PASS__ */ 754#endif /* __XDELTA3_C_HEADER_PASS__ */
799#ifdef __XDELTA3_C_INLINE_PASS__ 755#ifdef __XDELTA3_C_INLINE_PASS__
800 756
801const uint16_t __single_hash32[256] =
802{
803 /* This hashes the input alphabet (Scheme SLIB pseudo-random). */
804 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46,
805 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602,
806 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6,
807 0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a,
808 0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58,
809 0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b,
810 0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94,
811 0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176,
812 0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743,
813 0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6,
814 0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227,
815 0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d,
816 0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a,
817 0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31,
818 0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9,
819 0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6,
820 0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f,
821 0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f,
822 0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49,
823 0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037,
824 0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad,
825 0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f,
826 0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d,
827 0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b,
828 0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624,
829 0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272,
830 0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806,
831 0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050,
832 0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113,
833 0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2,
834 0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25,
835 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5
836};
837
838const uint32_t __single_hash64[256] =
839{
840 /* http://random.org 2014.10.24 */
841 0xd25e9f0a, 0xb1af9d5e, 0xb753dfa2, 0x157050f7, /* 0 */
842 0xc84b072c, 0xdd14fe7c, 0xf92208c3, 0xdf08a0c0,
843 0x63a5c118, 0x76f5d90f, 0xa2f8b93e, 0xb6c12d22,
844 0xaf074957, 0x966fb7d9, 0x62f7b785, 0xb40e8a09,
845 0x0a811d5d, 0x323a6daa, 0xb62f7c5b, 0xfdcb9a53,
846 0xf25a9067, 0x4506bc7a, 0xff58a74b, 0x5ae62817,
847 0x74097675, 0x722c0fd9, 0x116a2a66, 0x65f76728,
848 0x72c79651, 0xe043cf9d, 0x64b867c7, 0x6604834f,
849 0xcdca58a6, 0x0f164e2d, 0x24515f05, 0x632cdbf8,
850 0x18091d4a, 0x3eff4128, 0x673d1c33, 0xd8e10c71,
851 0x1a3edf11, 0xba52892f, 0xa56949e0, 0xf3e1dd77, /* 10 */
852 0x86fcbe3e, 0x138d66d0, 0x4fc98359, 0xc22e5dd6,
853 0xc59f2267, 0x6c6dd739, 0xe03da190, 0x07e8469c,
854 0xadcfb02c, 0x00d3b0d9, 0xa1f44918, 0x8bd84d87,
855 0x08ec9ec1, 0xbbcd156f, 0xb57718e3, 0x3177e752,
856 0xf52a4d70, 0xde7aaad9, 0x075f1da0, 0x21ba00c6,
857 0xb9469a5c, 0xcf08d5ba, 0x91ac9edc, 0xc6167b63,
858 0xc1974919, 0xc8c8d195, 0x4b1996dd, 0xeff8991c,
859 0xf7f66c6b, 0x25b012e2, 0x59d12a98, 0xea40d3cc,
860 0x41f9970b, 0xec48101a, 0xa3bdcf90, 0x99f16905,
861 0x27af6c97, 0xc849af37, 0x49cad89b, 0xf48c2278, /* 20 */
862 0x5529c3d8, 0x9e7d6dce, 0x16feb52d, 0xf1b0aca1,
863 0xaf28fccb, 0x48e4ce3c, 0xc4436617, 0x64524e3e,
864 0x61806681, 0x6384f2d7, 0x1172880f, 0x34a5ef5f,
865 0xcc8cc0a8, 0x66e8f100, 0x2866085f, 0xba9b1b2d,
866 0x51285949, 0x2be4b574, 0x889b1ef5, 0x3dbe920d,
867 0x9277a62f, 0x0584a9f6, 0x085d8fc4, 0x4b5d403d,
868 0x4e46ca78, 0x3294c2f9, 0x29313e70, 0xe4f09b24,
869 0xe73b331c, 0x072f5552, 0x2e390b78, 0xea0021ca,
870 0xd8f40320, 0xed0e16fd, 0x7de9cf7a, 0xf17e3d6c,
871 0x8df1bd85, 0x052cae67, 0x3486e512, 0x3a1c09b8, /* 30 */
872 0x6c2a7b4e, 0x83455753, 0xbc0353ac, 0x0ffe20b6,
873 0x5fdcef85, 0x010f506c, 0x595ce972, 0xe28680d0,
874 0xa7e216b2, 0xa392ee0f, 0x25b73faa, 0x2b1f4983,
875 0xeeaefe98, 0x1d3d9cbc, 0x6aebe97b, 0x8b7b3584,
876 0x9e6a9a07, 0xd37f1e99, 0x4ac2a441, 0x8ae9a213,
877 0x7d0e27d7, 0x5de54b9a, 0x8621de1f, 0xf0f2f866,
878 0xcb08d275, 0x49c3f87e, 0xd5ee68c1, 0x9802fc77,
879 0x68be6c5e, 0x65aa8c27, 0xf423d5f7, 0x10ec5502,
880 0x9909bce1, 0x509cdf1b, 0x338fea72, 0x2733e9bf,
881 0xf92f4fd7, 0x87738ea2, 0x931a8bbc, 0x0a5c9155, /* 40 */
882 0xbe5edd9b, 0xadbf5838, 0x0338f8d2, 0x290da210,
883 0x390c37d8, 0xe7cffae8, 0x20617ebe, 0x464322dd,
884 0x7b3c4e78, 0xac142dcb, 0x2d5cef76, 0xd8fe49fc,
885 0x60f4e9a9, 0x7473816f, 0x0dc35f39, 0x5eed80c1,
886 0x0cb55ab6, 0x1d3ac541, 0x13c7f529, 0x7bffdf4a,
887 0xe334785b, 0x85263ec1, 0xd132ae56, 0x7c868b9e,
888 0x47f60638, 0x1012b979, 0x81c31dd3, 0x1af868c8,
889 0x0c5d0742, 0xd1b3e1a2, 0x5873200a, 0xf848465c,
890 0x0fc4d596, 0x609c18af, 0xc9f5a480, 0xd1a94a84,
891 0xa1431a3f, 0x7de8bb1a, 0x25f1256b, 0x1dcc732c, /* 50 */
892 0x6aa1549a, 0xa2367281, 0x32f2a77e, 0x82e62a0f,
893 0x045cbb56, 0x74b2027c, 0xd71a32d9, 0x022e7cb5,
894 0xe99be177, 0x60222fdf, 0xd69681ca, 0x9008ee2c,
895 0x32923db4, 0xcf82bf97, 0x38960a5b, 0xb3503d5b,
896 0x9bd4c7f2, 0x33c029c8, 0x1ef504a3, 0xdb249d3b,
897 0x91e89676, 0x4ca43b36, 0x9191433c, 0x465d5dc4,
898 0xf4dcb118, 0x9d11dd00, 0xb592f058, 0xdbe5ce30,
899 0x74790d92, 0x779850a8, 0x7180d25b, 0xfa951d99,
900 0x5990935a, 0x921cb022, 0x3b7c39bc, 0x6a38a7c7,
901 0xdc22703b, 0x142bab3b, 0x4e3d9479, 0x44bb8482, /* 60 */
902 0x8043abce, 0xfebe832a, 0x8e6a2f98, 0x4d43c4fe,
903 0xd192a70a, 0x802f3c3a, 0x5d11bbab, 0x2665d241,
904 0xb3f3a680, 0x3a8d223f, 0xcf82cdb4, 0x4ed28743,
905};
906
907/**************************************************************** 757/****************************************************************
908 Instruction tables 758 Instruction tables
909 *****************************************************************/ 759 *****************************************************************/
@@ -1499,55 +1349,59 @@ xd3_emit_bytes (xd3_stream *stream,
1499 \ 1349 \
1500 return xd3_emit_bytes (stream, output, buf + bufi, 10 - bufi) 1350 return xd3_emit_bytes (stream, output, buf + bufi, 10 - bufi)
1501 1351
1502#define IF_SIZEOF32(x) if (num < (1U << (7 * (x)))) return (x);
1503#define IF_SIZEOF64(x) if (num < (1ULL << (7 * (x)))) return (x);
1504
1505#if USE_UINT32 1352#if USE_UINT32
1506usize_t 1353usize_t
1507xd3_sizeof_uint32_t (uint32_t num) 1354xd3_sizeof_uint32_t (uint32_t num)
1508{ 1355{
1356#define IF_SIZEOF32(x) if (num < (1U << (7 * (x)))) return (x);
1509 IF_SIZEOF32(1); 1357 IF_SIZEOF32(1);
1510 IF_SIZEOF32(2); 1358 IF_SIZEOF32(2);
1511 IF_SIZEOF32(3); 1359 IF_SIZEOF32(3);
1512 IF_SIZEOF32(4); 1360 IF_SIZEOF32(4);
1361#undef IF_SIZEOF32
1513 return 5; 1362 return 5;
1514} 1363}
1515 1364
1516int 1365int
1517xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val) 1366xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val)
1518{ DECODE_INTEGER_TYPE (uint32_t, stream->dec_32part, UINT32_OFLOW_MASK); } 1367{
1368 DECODE_INTEGER_TYPE (uint32_t, stream->dec_32part, UINT32_OFLOW_MASK);
1369}
1519 1370
1520int 1371int
1521xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp, 1372xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp,
1522 const uint8_t *max, uint32_t *valp) 1373 const uint8_t *max, uint32_t *valp)
1523{ READ_INTEGER_TYPE (uint32_t, UINT32_OFLOW_MASK); } 1374{
1375 READ_INTEGER_TYPE (uint32_t, UINT32_OFLOW_MASK);
1376}
1524 1377
1525#if XD3_ENCODER 1378#if XD3_ENCODER
1526int 1379int
1527xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num) 1380xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num)
1528{ EMIT_INTEGER_TYPE (); } 1381{
1529#endif 1382 EMIT_INTEGER_TYPE ();
1530#endif 1383}
1384#endif /* XD3_ENCODER */
1385#endif /* USE_UINT32 */
1531 1386
1532#if USE_UINT64 1387#if USE_UINT64
1533int 1388int
1534xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val) 1389xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val)
1535{ DECODE_INTEGER_TYPE (uint64_t, stream->dec_64part, UINT64_OFLOW_MASK); } 1390{
1536 1391 DECODE_INTEGER_TYPE (uint64_t, stream->dec_64part, UINT64_OFLOW_MASK);
1537#if XD3_ENCODER 1392}
1538int
1539xd3_emit_uint64_t (xd3_stream *stream, xd3_output **output, uint64_t num)
1540{ EMIT_INTEGER_TYPE (); }
1541#endif
1542 1393
1543int 1394int
1544xd3_read_uint64_t (xd3_stream *stream, const uint8_t **inpp, 1395xd3_read_uint64_t (xd3_stream *stream, const uint8_t **inpp,
1545 const uint8_t *max, uint64_t *valp) 1396 const uint8_t *max, uint64_t *valp)
1546{ READ_INTEGER_TYPE (uint64_t, UINT64_OFLOW_MASK); } 1397{
1398 READ_INTEGER_TYPE (uint64_t, UINT64_OFLOW_MASK);
1399}
1547 1400
1548usize_t 1401usize_t
1549xd3_sizeof_uint64_t (uint64_t num) 1402xd3_sizeof_uint64_t (uint64_t num)
1550{ 1403{
1404#define IF_SIZEOF64(x) if (num < (1ULL << (7 * (x)))) return (x);
1551 IF_SIZEOF64(1); 1405 IF_SIZEOF64(1);
1552 IF_SIZEOF64(2); 1406 IF_SIZEOF64(2);
1553 IF_SIZEOF64(3); 1407 IF_SIZEOF64(3);
@@ -1557,11 +1411,18 @@ xd3_sizeof_uint64_t (uint64_t num)
1557 IF_SIZEOF64(7); 1411 IF_SIZEOF64(7);
1558 IF_SIZEOF64(8); 1412 IF_SIZEOF64(8);
1559 IF_SIZEOF64(9); 1413 IF_SIZEOF64(9);
1560 1414#undef IF_SIZEOF64
1561 return 10; 1415 return 10;
1562} 1416}
1563 1417
1564#endif 1418#if XD3_ENCODER
1419int
1420xd3_emit_uint64_t (xd3_stream *stream, xd3_output **output, uint64_t num)
1421{
1422 EMIT_INTEGER_TYPE ();
1423}
1424#endif /* XD3_ENCODER */
1425#endif /* USE_UINT64 */
1565 1426
1566/*********************************************************************** 1427/***********************************************************************
1567 Address cache stuff 1428 Address cache stuff
@@ -1928,11 +1789,13 @@ xd3_free_stream (xd3_stream *stream)
1928 xd3_free (stream, tmp); 1789 xd3_free (stream, tmp);
1929 } 1790 }
1930 1791
1792#if XD3_ENCODER
1931 xd3_free (stream, stream->large_table); 1793 xd3_free (stream, stream->large_table);
1932 xd3_free (stream, stream->small_table); 1794 xd3_free (stream, stream->small_table);
1795 xd3_free (stream, stream->large_hash.powers);
1796 xd3_free (stream, stream->small_hash.powers);
1933 xd3_free (stream, stream->small_prev); 1797 xd3_free (stream, stream->small_prev);
1934 1798
1935#if XD3_ENCODER
1936 { 1799 {
1937 int i; 1800 int i;
1938 for (i = 0; i < ENC_SECTS; i += 1) 1801 for (i = 0; i < ENC_SECTS; i += 1)
@@ -3158,7 +3021,7 @@ xd3_emit_hdr (xd3_stream *stream)
3158 inst_len = xd3_sizeof_output (INST_HEAD (stream)); 3021 inst_len = xd3_sizeof_output (INST_HEAD (stream));
3159 addr_len = xd3_sizeof_output (ADDR_HEAD (stream)); 3022 addr_len = xd3_sizeof_output (ADDR_HEAD (stream));
3160 3023
3161 /* The enc_len field is a redundency for future extensions.*/ 3024 /* The enc_len field is a redundency for future extensions. */
3162 enc_len = (1 + (xd3_sizeof_size (tgt_len) + 3025 enc_len = (1 + (xd3_sizeof_size (tgt_len) +
3163 xd3_sizeof_size (data_len) + 3026 xd3_sizeof_size (data_len) +
3164 xd3_sizeof_size (inst_len) + 3027 xd3_sizeof_size (inst_len) +
@@ -3299,6 +3162,7 @@ xd3_alloc_iopt (xd3_stream *stream, usize_t elts)
3299static int 3162static int
3300xd3_encode_init (xd3_stream *stream, int full_init) 3163xd3_encode_init (xd3_stream *stream, int full_init)
3301{ 3164{
3165 int ret;
3302 int i; 3166 int i;
3303 3167
3304 if (full_init) 3168 if (full_init)
@@ -3315,9 +3179,13 @@ xd3_encode_init (xd3_stream *stream, int full_init)
3315 usize_t hash_values = stream->src->max_winsize / 3179 usize_t hash_values = stream->src->max_winsize /
3316 stream->smatcher.large_step; 3180 stream->smatcher.large_step;
3317 3181
3318 xd3_size_hashtable (stream, 3182 if ((ret = xd3_size_hashtable (stream,
3319 hash_values, 3183 hash_values,
3320 & stream->large_hash); 3184 stream->smatcher.large_look,
3185 & stream->large_hash)))
3186 {
3187 return ret;
3188 }
3321 } 3189 }
3322 3190
3323 if (small_comp) 3191 if (small_comp)
@@ -3328,9 +3196,13 @@ xd3_encode_init (xd3_stream *stream, int full_init)
3328 * sense. @@@ */ 3196 * sense. @@@ */
3329 usize_t hash_values = stream->winsize; 3197 usize_t hash_values = stream->winsize;
3330 3198
3331 xd3_size_hashtable (stream, 3199 if ((ret = xd3_size_hashtable (stream,
3332 hash_values, 3200 hash_values,
3333 & stream->small_hash); 3201 stream->smatcher.small_look,
3202 & stream->small_hash)))
3203 {
3204 return ret;
3205 }
3334 } 3206 }
3335 } 3207 }
3336 3208
@@ -4627,7 +4499,7 @@ xd3_verify_large_state (xd3_stream *stream,
4627 const uint8_t *inp, 4499 const uint8_t *inp,
4628 usize_t x_cksum) 4500 usize_t x_cksum)
4629{ 4501{
4630 usize_t cksum = xd3_large_cksum (inp, stream->smatcher.large_look); 4502 usize_t cksum = xd3_large_cksum (&stream->large_hash, inp, stream->smatcher.large_look);
4631 XD3_ASSERT (cksum == x_cksum); 4503 XD3_ASSERT (cksum == x_cksum);
4632} 4504}
4633static void 4505static void
@@ -4771,8 +4643,12 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
4771 4643
4772 do 4644 do
4773 { 4645 {
4774 usize_t cksum = xd3_large_cksum (stream->src->curblk + blkpos, 4646 /* TODO: This would be significantly faster if the compiler
4775 stream->smatcher.large_look); 4647 * knew stream->smatcher.large_look (which the template for
4648 * xd3_string_match_* allows). */
4649 usize_t cksum = xd3_large_cksum (&stream->large_hash,
4650 stream->src->curblk + blkpos,
4651 stream->smatcher.large_look);
4776 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum); 4652 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum);
4777 4653
4778 stream->large_table[hval] = 4654 stream->large_table[hval] =
@@ -4934,7 +4810,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4934 return ret; 4810 return ret;
4935 } 4811 }
4936 4812
4937 lcksum = xd3_large_cksum (inp, LLOOK); 4813 lcksum = xd3_large_cksum (&stream->large_hash, inp, LLOOK);
4938 } 4814 }
4939 4815
4940 /* TRYLAZYLEN: True if a certain length match should be followed by 4816 /* TRYLAZYLEN: True if a certain length match should be followed by
@@ -5110,7 +4986,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
5110 4986
5111 if (DO_LARGE && (stream->input_position + LLOOK < stream->avail_in)) 4987 if (DO_LARGE && (stream->input_position + LLOOK < stream->avail_in))
5112 { 4988 {
5113 lcksum = xd3_large_cksum_update (lcksum, inp, LLOOK); 4989 lcksum = xd3_large_cksum_update (&stream->large_hash, lcksum, inp, LLOOK);
5114 } 4990 }
5115 } 4991 }
5116 4992
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
658/* hash table size & power-of-two hash function. */ 658/* hash table size & power-of-two hash function. */
659struct _xd3_hash_cfg 659struct _xd3_hash_cfg
660{ 660{
661 usize_t size; 661 usize_t size; // Number of buckets
662 usize_t shift; 662 usize_t shift;
663 usize_t mask; 663 usize_t mask;
664 usize_t look; // How wide is this checksum
665 usize_t multiplier; // K * powers[0]
666 usize_t *powers; // Array of [0,look) where powers[look-1] == 1
667 // and powers[N] = powers[N+1]*K (Rabin-Karp)
664}; 668};
665 669
666/* the sprev list */ 670/* the sprev list */
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-08 07:40:50 +0000