diff options
Diffstat (limited to 'xdelta3')
l--------- | xdelta3/py-compile | 1 | ||||
-rwxr-xr-x | xdelta3/run_release.sh | 21 | ||||
-rw-r--r-- | xdelta3/testing/checksum_test.cc | 230 | ||||
-rw-r--r-- | xdelta3/testing/checksum_test_c.c | 173 | ||||
-rw-r--r-- | xdelta3/testing/test.h | 6 | ||||
-rw-r--r-- | xdelta3/xdelta3-hash.h | 142 | ||||
-rw-r--r-- | xdelta3/xdelta3-internal.h | 62 | ||||
-rw-r--r-- | xdelta3/xdelta3-test.h | 44 | ||||
-rw-r--r-- | xdelta3/xdelta3.c | 238 | ||||
-rw-r--r-- | xdelta3/xdelta3.h | 10 |
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 | ||
3 | CC=clang | 4 | CC=clang |
4 | CXX=clang++ | 5 | CXX=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, |
10 | CFLAGS= | 11 | CFLAGS= # Do not set here |
11 | CXXFLAGS= | 12 | CXXFLAGS= # Do not set here |
12 | 13 | ||
13 | # Place C/C++ common flags here | 14 | # Place C/C++ common flags here |
14 | COMMON=-O3 | 15 | #COMMON=-O3 |
15 | 16 | ||
16 | export CFLAGS | 17 | export CFLAGS |
17 | export CXXFLAGS | 18 | export 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 | ||
10 | extern "C" { | ||
11 | uint32_t xd3_large32_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); | ||
12 | uint32_t xd3_large32_cksum_update_old (xd3_hash_cfg *cfg, uint32_t cksum, | ||
13 | const uint8_t *base, const usize_t look); | ||
14 | |||
15 | uint64_t xd3_large64_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); | ||
16 | uint64_t xd3_large64_cksum_update_old (xd3_hash_cfg *cfg, uint64_t cksum, | ||
17 | const uint8_t *base, const usize_t look); | ||
18 | } | ||
19 | |||
10 | using std::list; | 20 | using std::list; |
11 | using std::map; | 21 | using std::map; |
12 | using std::vector; | 22 | using std::vector; |
@@ -24,6 +34,14 @@ uint64_t good_64bit_values[] = { | |||
24 | 7664345821815920749ULL, // ... | 34 | 7664345821815920749ULL, // ... |
25 | }; | 35 | }; |
26 | 36 | ||
37 | void 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 | |||
27 | struct true_type { }; | 45 | struct true_type { }; |
28 | struct false_type { }; | 46 | struct 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 | ||
53 | template <typename Word> | 71 | template <typename Word> |
54 | struct nonhash { | ||
55 | Word operator()(const Word t, const Word h, const Word mask) { | ||
56 | return (t >> h) & mask; | ||
57 | } | ||
58 | }; | ||
59 | |||
60 | template <typename Word> | ||
61 | Word good_word(); | 72 | Word good_word(); |
62 | 73 | ||
63 | template<> | 74 | template<> |
@@ -92,14 +103,18 @@ struct cksum_params { | |||
92 | MEMBER | 103 | MEMBER |
93 | struct rabin_karp : public cksum_params<SELF> { | 104 | struct 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 | |||
148 | MEMBER | ||
149 | struct 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 | |||
178 | MEMBER | ||
179 | struct 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 | ||
134 | MEMBER | 197 | MEMBER |
135 | struct large_cksum : public cksum_params<SELF> { | 198 | struct 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 | ||
216 | MEMBER | ||
217 | struct 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 | |||
235 | MEMBER | ||
236 | struct 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 | |||
254 | MEMBER | ||
255 | struct large_cksum | ||
256 | : std::conditional<std::is_same<Word, uint32_t>::value, | ||
257 | large32_cksum<SELF>, | ||
258 | large64_cksum<SELF>>::type | ||
259 | { | ||
260 | }; | ||
261 | |||
262 | MEMBER | ||
263 | struct 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 | ||
155 | template <typename Word> | 272 | template <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 | |||
8 | const 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 | |||
45 | const 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 | |||
114 | uint64_t | ||
115 | xd3_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 | |||
132 | uint64_t | ||
133 | xd3_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 | |||
145 | uint32_t | ||
146 | xd3_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 | |||
163 | uint32_t | ||
164 | xd3_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 | ||
69 | using std::min; | 69 | using std::min; |
70 | using std::max; | 70 | using 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" */ |
47 | static 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) */ |
50 | static inline uint32_t | 51 | static 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 | } |
58 | static inline uint32_t | 59 | static inline uint32_t |
59 | xd3_small_cksum_update (uint32_t *state, | 60 | xd3_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 | ||
67 | static inline usize_t | 68 | #if XD3_ENCODER |
69 | inline usize_t | ||
68 | xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) | 70 | xd3_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]) | ||
75 | extern const uint16_t __single_hash32[256]; | ||
76 | |||
77 | inline uint32_t | 75 | inline uint32_t |
78 | xd3_large32_cksum (const uint8_t *seg, const usize_t ln) | 76 | xd3_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 | ||
95 | inline uint32_t | 85 | inline uint32_t |
96 | xd3_large32_cksum_update (uint32_t cksum, | 86 | xd3_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]) | ||
112 | extern const uint32_t __single_hash64[256]; | ||
113 | |||
114 | inline uint64_t | 92 | inline uint64_t |
115 | xd3_large64_cksum (const uint8_t *seg, const usize_t len) | 93 | xd3_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 | ||
132 | inline uint64_t | 102 | inline uint64_t |
133 | xd3_large64_cksum_update (uint64_t cksum, | 103 | xd3_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 | |||
148 | inline usize_t | ||
149 | xd3_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 | |||
161 | inline usize_t | ||
162 | xd3_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 | ||
172 | static usize_t | 109 | static 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 | ||
192 | static void | 129 | int |
193 | xd3_size_hashtable (xd3_stream *stream, | 130 | xd3_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, | |||
64 | int xd3_main_cmdline (int argc, char **argv); | 64 | int xd3_main_cmdline (int argc, char **argv); |
65 | #endif | 65 | #endif |
66 | 66 | ||
67 | #if REGRESSION_TEST | ||
68 | int xd3_selftest (void); | ||
69 | #endif | ||
70 | |||
67 | /* main_file->mode values */ | 71 | /* main_file->mode values */ |
68 | typedef enum | 72 | typedef 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 | ||
158 | usize_t xd3_large_cksum (const uint8_t *seg, const usize_t ln); | 162 | #define UINT32_OFLOW_MASK 0xfe000000U |
159 | usize_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 | |||
198 | int xd3_size_hashtable (xd3_stream *stream, | ||
199 | usize_t slots, | ||
200 | usize_t look, | ||
201 | xd3_hash_cfg *cfg); | ||
202 | |||
203 | usize_t xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum); | ||
204 | |||
205 | #if USE_UINT32 | ||
206 | uint32_t xd3_large32_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); | ||
207 | uint32_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 | ||
212 | uint64_t xd3_large64_cksum (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look); | ||
213 | uint64_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 | ||
1559 | static int | ||
1560 | test_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 | ||
2842 | static int | 2881 | int xd3_selftest (void) |
2843 | xd3_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, | |||
549 | static void* xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size); | 549 | static void* xd3_alloc (xd3_stream *stream, usize_t elts, usize_t size); |
550 | static void xd3_free (xd3_stream *stream, void *ptr); | 550 | static void xd3_free (xd3_stream *stream, void *ptr); |
551 | 551 | ||
552 | #if USE_UINT32 | ||
553 | static 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 | ||
557 | static 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 | ||
561 | static 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 | |||
596 | const char* xd3_strerror (int ret) | 552 | const 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 | ||
801 | const 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 | |||
838 | const 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 |
1506 | usize_t | 1353 | usize_t |
1507 | xd3_sizeof_uint32_t (uint32_t num) | 1354 | xd3_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 | ||
1516 | int | 1365 | int |
1517 | xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val) | 1366 | xd3_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 | ||
1520 | int | 1371 | int |
1521 | xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp, | 1372 | xd3_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 |
1526 | int | 1379 | int |
1527 | xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num) | 1380 | xd3_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 |
1533 | int | 1388 | int |
1534 | xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val) | 1389 | xd3_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 | } |
1538 | int | ||
1539 | xd3_emit_uint64_t (xd3_stream *stream, xd3_output **output, uint64_t num) | ||
1540 | { EMIT_INTEGER_TYPE (); } | ||
1541 | #endif | ||
1542 | 1393 | ||
1543 | int | 1394 | int |
1544 | xd3_read_uint64_t (xd3_stream *stream, const uint8_t **inpp, | 1395 | xd3_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 | ||
1548 | usize_t | 1401 | usize_t |
1549 | xd3_sizeof_uint64_t (uint64_t num) | 1402 | xd3_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 |
1419 | int | ||
1420 | xd3_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) | |||
3299 | static int | 3162 | static int |
3300 | xd3_encode_init (xd3_stream *stream, int full_init) | 3163 | xd3_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 | } |
4633 | static void | 4505 | static 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. */ |
659 | struct _xd3_hash_cfg | 659 | struct _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 */ |