diff options
author | josh.macdonald <jmacd@users.noreply.github.com> | 2007-11-26 12:15:18 +0000 |
---|---|---|
committer | josh.macdonald <jmacd@users.noreply.github.com> | 2007-11-26 12:15:18 +0000 |
commit | ce6a092d2ac6723acd4de0b89a7832a027722027 (patch) | |
tree | 1b2dda028daf9a690a6ba971cd936aa0a985c9f5 | |
parent | d8d2ab4c809485480727ee7a943163f272d22b11 (diff) |
The rabin-karp checksum looks better in testing but doesn't really
seem to improve things in practice. Removed HASH_PRIME.
-rwxr-xr-x | xdelta3/examples/Makefile | 2 | ||||
-rw-r--r-- | xdelta3/examples/checksum_test.cc | 163 | ||||
-rw-r--r-- | xdelta3/xdelta3-hash.h | 104 | ||||
-rw-r--r-- | xdelta3/xdelta3-main.h | 4 | ||||
-rw-r--r-- | xdelta3/xdelta3.c | 46 | ||||
-rw-r--r-- | xdelta3/xdelta3.h | 3 |
6 files changed, 190 insertions, 132 deletions
diff --git a/xdelta3/examples/Makefile b/xdelta3/examples/Makefile index f1caa57..7bc575c 100755 --- a/xdelta3/examples/Makefile +++ b/xdelta3/examples/Makefile | |||
@@ -1,4 +1,4 @@ | |||
1 | #CFLAGS = -g -Wall -I.. -DXD3_DEBUG=1 | 1 | #CFLAGS = -g -Wall -I.. -DXD3_DEBUG=1 -DNDEBUG=0 |
2 | CFLAGS = -O3 -Wall -I.. -DXD3_DEBUG=0 -fno-builtin -DNDEBUG=1 | 2 | CFLAGS = -O3 -Wall -I.. -DXD3_DEBUG=0 -fno-builtin -DNDEBUG=1 |
3 | # -pg | 3 | # -pg |
4 | 4 | ||
diff --git a/xdelta3/examples/checksum_test.cc b/xdelta3/examples/checksum_test.cc index 40e2df1..15c6087 100644 --- a/xdelta3/examples/checksum_test.cc +++ b/xdelta3/examples/checksum_test.cc | |||
@@ -48,12 +48,6 @@ struct plain { | |||
48 | } | 48 | } |
49 | }; | 49 | }; |
50 | 50 | ||
51 | struct permute { | ||
52 | int operator()(const uint8_t &c) { | ||
53 | return __single_hash[c]; | ||
54 | } | ||
55 | }; | ||
56 | |||
57 | template <typename Word> | 51 | template <typename Word> |
58 | struct hhash { // take "h" of the high-bits as a hash value for this | 52 | struct hhash { // take "h" of the high-bits as a hash value for this |
59 | // checksum, which are the most "distant" in terms of the | 53 | // checksum, which are the most "distant" in terms of the |
@@ -152,6 +146,34 @@ struct rabin_karp { | |||
152 | Word incr_state; | 146 | Word incr_state; |
153 | }; | 147 | }; |
154 | 148 | ||
149 | MEMBER | ||
150 | struct adler32_cksum { | ||
151 | typedef Word word_type; | ||
152 | typedef Permute permute_type; | ||
153 | typedef Hash hash_type; | ||
154 | |||
155 | enum { cksum_size = CksumSize, | ||
156 | cksum_skip = CksumSkip, | ||
157 | compaction = Compaction, | ||
158 | }; | ||
159 | |||
160 | Word step(const uint8_t *ptr) { | ||
161 | return xd3_lcksum (ptr, cksum_size); | ||
162 | } | ||
163 | |||
164 | Word state0(const uint8_t *ptr) { | ||
165 | incr_state = step(ptr); | ||
166 | return incr_state; | ||
167 | } | ||
168 | |||
169 | Word incr(const uint8_t *ptr) { | ||
170 | LARGE_CKSUM_UPDATE(incr_state, ptr - 1, cksum_size); | ||
171 | return incr_state; | ||
172 | } | ||
173 | |||
174 | Word incr_state; | ||
175 | }; | ||
176 | |||
155 | // TESTS | 177 | // TESTS |
156 | 178 | ||
157 | template <typename Word> | 179 | template <typename Word> |
@@ -222,12 +244,15 @@ struct test_result_base { | |||
222 | } | 244 | } |
223 | virtual void reset() = 0; | 245 | virtual void reset() = 0; |
224 | virtual void print() = 0; | 246 | virtual void print() = 0; |
225 | virtual void print_accum() = 0; | ||
226 | virtual void get(const uint8_t* buf, const int buf_size, int iters) = 0; | 247 | virtual void get(const uint8_t* buf, const int buf_size, int iters) = 0; |
227 | virtual void stat() = 0; | 248 | virtual void stat() = 0; |
228 | virtual int count() = 0; | 249 | virtual int count() = 0; |
229 | virtual int dups() = 0; | 250 | virtual int dups() = 0; |
230 | virtual double uniqueness() = 0; | 251 | virtual double uniqueness() = 0; |
252 | virtual double fullness() = 0; | ||
253 | virtual double collisions() = 0; | ||
254 | virtual double coverage() = 0; | ||
255 | virtual double compression() = 0; | ||
231 | virtual double time() = 0; | 256 | virtual double time() = 0; |
232 | virtual double score() = 0; | 257 | virtual double score() = 0; |
233 | virtual void set_score(double min_dups_frac, double min_time) = 0; | 258 | virtual void set_score(double min_dups_frac, double min_time) = 0; |
@@ -345,6 +370,18 @@ struct test_result : public test_result_base { | |||
345 | return (double) h_buckets_full / (1 << h_bits); | 370 | return (double) h_buckets_full / (1 << h_bits); |
346 | } | 371 | } |
347 | 372 | ||
373 | double collisions() { | ||
374 | return (double) colls() / fstats.unique; | ||
375 | } | ||
376 | |||
377 | double coverage() { | ||
378 | return (double) h_buckets_full / uniqueness() / count(); | ||
379 | } | ||
380 | |||
381 | double compression() { | ||
382 | return 1.0 - coverage(); | ||
383 | } | ||
384 | |||
348 | double time() { | 385 | double time() { |
349 | return (double) accum_millis / accum_iters; | 386 | return (double) accum_millis / accum_iters; |
350 | } | 387 | } |
@@ -353,8 +390,9 @@ struct test_result : public test_result_base { | |||
353 | return h_score; | 390 | return h_score; |
354 | } | 391 | } |
355 | 392 | ||
356 | void set_score(double min_uniqueness, double min_time) { | 393 | void set_score(double min_compression, double min_time) { |
357 | h_score = time(); | 394 | h_score = (compression() - 0.99 * min_compression) |
395 | * (time() - 0.99 * min_time); | ||
358 | } | 396 | } |
359 | 397 | ||
360 | double total_time() { | 398 | double total_time() { |
@@ -381,29 +419,21 @@ struct test_result : public test_result_base { | |||
381 | accum_size += test_size; | 419 | accum_size += test_size; |
382 | } | 420 | } |
383 | 421 | ||
384 | void print_accum() { | ||
385 | printf("%s: (%u#%u) count %u dups %0.2f%% %.4f MB/s score %0.6f\n", | ||
386 | test_name, | ||
387 | cksum_size, | ||
388 | cksum_skip, | ||
389 | total_count(), | ||
390 | 100.0 * total_dups() / total_count(), | ||
391 | 0.001 * accum_size / time(), | ||
392 | h_score); | ||
393 | } | ||
394 | |||
395 | void print() { | 422 | void print() { |
396 | if (fstats.count != count()) { | 423 | if (fstats.count != count()) { |
397 | fprintf(stderr, "internal error: %d != %d\n", fstats.count, count()); | 424 | fprintf(stderr, "internal error: %d != %d\n", fstats.count, count()); |
398 | abort(); | 425 | abort(); |
399 | } | 426 | } |
400 | printf("%s: (%u#%u) count %u uniq %0.2f%% full %0.4f%% of 1<<%d @ %.4f MB/s %u iters\n", | 427 | printf("%s: (%u#%u) count %u uniq %0.2f%% full %u (%0.4f%% coll %0.4f%%) covers %0.2f%% w/ 2^%d @ %.4f MB/s %u iters\n", |
401 | test_name, | 428 | test_name, |
402 | cksum_size, | 429 | cksum_size, |
403 | cksum_skip, | 430 | cksum_skip, |
404 | count(), | 431 | count(), |
405 | 100.0 * uniqueness(), | 432 | 100.0 * uniqueness(), |
433 | h_buckets_full, | ||
406 | 100.0 * fullness(), | 434 | 100.0 * fullness(), |
435 | 100.0 * collisions(), | ||
436 | 100.0 * coverage(), | ||
407 | h_bits, | 437 | h_bits, |
408 | 0.001 * accum_iters * test_size / accum_millis, | 438 | 0.001 * accum_iters * test_size / accum_millis, |
409 | accum_iters); | 439 | accum_iters); |
@@ -457,6 +487,7 @@ struct test_result : public test_result_base { | |||
457 | 487 | ||
458 | void get(const uint8_t* buf, const int buf_size, int test_iters) { | 488 | void get(const uint8_t* buf, const int buf_size, int test_iters) { |
459 | rabin_karp<SELF> test; | 489 | rabin_karp<SELF> test; |
490 | //adler32_cksum<SELF> test; | ||
460 | hash_type hash; | 491 | hash_type hash; |
461 | const uint8_t *ptr; | 492 | const uint8_t *ptr; |
462 | const uint8_t *end; | 493 | const uint8_t *end; |
@@ -545,6 +576,17 @@ struct test_result : public test_result_base { | |||
545 | } | 576 | } |
546 | }; | 577 | }; |
547 | 578 | ||
579 | template <typename Word> | ||
580 | void print_array(const char *tname) { | ||
581 | printf("static const %s hash_multiplier[64] = {\n", tname); | ||
582 | Word p = 1; | ||
583 | for (int i = 0; i < 64; i++) { | ||
584 | printf(" %uU,\n", p); | ||
585 | p *= good_word<Word>(); | ||
586 | } | ||
587 | printf("};\n", tname); | ||
588 | } | ||
589 | |||
548 | int main(int argc, char** argv) { | 590 | int main(int argc, char** argv) { |
549 | int i; | 591 | int i; |
550 | uint8_t *buf = NULL; | 592 | uint8_t *buf = NULL; |
@@ -556,21 +598,42 @@ int main(int argc, char** argv) { | |||
556 | return 1; | 598 | return 1; |
557 | } | 599 | } |
558 | 600 | ||
601 | //print_array<uint32_t>("uint32_t"); | ||
602 | |||
559 | #define TEST(T,Z,S,P,H,C) test_result<T,Z,S,P,H<T>,C> \ | 603 | #define TEST(T,Z,S,P,H,C) test_result<T,Z,S,P,H<T>,C> \ |
560 | _ ## T ## _ ## Z ## _ ## S ## _ ## P ## _ ## H ## _ ## C \ | 604 | _ ## T ## _ ## Z ## _ ## S ## _ ## P ## _ ## H ## _ ## C \ |
561 | (#T "_" #Z "_" #S "_" #P "_" #H "_" #C) | 605 | (#T "_" #Z "_" #S "_" #P "_" #H "_" #C) |
562 | 606 | ||
607 | #if 0 | ||
608 | |||
609 | TEST(uint32_t, 4, SKIP, plain, hhash, 0); /* x */ \ | ||
610 | TEST(uint32_t, 4, SKIP, plain, hhash, 1); /* x */ \ | ||
611 | TEST(uint32_t, 4, SKIP, plain, hhash, 2); /* x */ \ | ||
612 | TEST(uint32_t, 4, SKIP, plain, hhash, 3); /* x */ \ | ||
613 | |||
614 | #endif | ||
615 | |||
563 | #define TESTS(SKIP) \ | 616 | #define TESTS(SKIP) \ |
617 | TEST(uint32_t, 9, SKIP, plain, hhash, 0); /* x */ \ | ||
618 | TEST(uint32_t, 9, SKIP, plain, hhash, 1); /* x */ \ | ||
619 | TEST(uint32_t, 9, SKIP, plain, hhash, 2); /* x */ \ | ||
620 | TEST(uint32_t, 9, SKIP, plain, hhash, 3) | ||
621 | |||
622 | #define TESTS_ALL(SKIP) \ | ||
564 | TEST(uint32_t, 3, SKIP, plain, hhash, 0); \ | 623 | TEST(uint32_t, 3, SKIP, plain, hhash, 0); \ |
565 | TEST(uint32_t, 3, SKIP, plain, hhash, 1); \ | 624 | TEST(uint32_t, 3, SKIP, plain, hhash, 1); \ |
566 | TEST(uint32_t, 4, SKIP, plain, hhash, 0); /* x */ \ | 625 | TEST(uint32_t, 4, SKIP, plain, hhash, 0); /* x */ \ |
567 | TEST(uint32_t, 4, SKIP, plain, hhash, 1); /* x */ \ | 626 | TEST(uint32_t, 4, SKIP, plain, hhash, 1); /* x */ \ |
627 | TEST(uint32_t, 4, SKIP, plain, hhash, 2); /* x */ \ | ||
628 | TEST(uint32_t, 4, SKIP, plain, hhash, 3); /* x */ \ | ||
568 | TEST(uint32_t, 5, SKIP, plain, hhash, 0); \ | 629 | TEST(uint32_t, 5, SKIP, plain, hhash, 0); \ |
569 | TEST(uint32_t, 5, SKIP, plain, hhash, 1); \ | 630 | TEST(uint32_t, 5, SKIP, plain, hhash, 1); \ |
570 | TEST(uint32_t, 8, SKIP, plain, hhash, 0); \ | 631 | TEST(uint32_t, 8, SKIP, plain, hhash, 0); \ |
571 | TEST(uint32_t, 8, SKIP, plain, hhash, 1); \ | 632 | TEST(uint32_t, 8, SKIP, plain, hhash, 1); \ |
572 | TEST(uint32_t, 9, SKIP, plain, hhash, 0); /* x */ \ | 633 | TEST(uint32_t, 9, SKIP, plain, hhash, 0); /* x */ \ |
573 | TEST(uint32_t, 9, SKIP, plain, hhash, 1); /* x */ \ | 634 | TEST(uint32_t, 9, SKIP, plain, hhash, 1); /* x */ \ |
635 | TEST(uint32_t, 9, SKIP, plain, hhash, 2); /* x */ \ | ||
636 | TEST(uint32_t, 9, SKIP, plain, hhash, 3); /* x */ \ | ||
574 | TEST(uint32_t, 11, SKIP, plain, hhash, 0); /* x */ \ | 637 | TEST(uint32_t, 11, SKIP, plain, hhash, 0); /* x */ \ |
575 | TEST(uint32_t, 11, SKIP, plain, hhash, 1); /* x */ \ | 638 | TEST(uint32_t, 11, SKIP, plain, hhash, 1); /* x */ \ |
576 | TEST(uint32_t, 13, SKIP, plain, hhash, 0); \ | 639 | TEST(uint32_t, 13, SKIP, plain, hhash, 0); \ |
@@ -584,24 +647,22 @@ int main(int argc, char** argv) { | |||
584 | TEST(uint32_t, 34, SKIP, plain, hhash, 0); \ | 647 | TEST(uint32_t, 34, SKIP, plain, hhash, 0); \ |
585 | TEST(uint32_t, 34, SKIP, plain, hhash, 1); \ | 648 | TEST(uint32_t, 34, SKIP, plain, hhash, 1); \ |
586 | TEST(uint32_t, 55, SKIP, plain, hhash, 0); \ | 649 | TEST(uint32_t, 55, SKIP, plain, hhash, 0); \ |
587 | TEST(uint32_t, 55, SKIP, plain, hhash, 1); \ | 650 | TEST(uint32_t, 55, SKIP, plain, hhash, 1) |
588 | TEST(uint32_t, 89, SKIP, plain, hhash, 0); \ | ||
589 | TEST(uint32_t, 89, SKIP, plain, hhash, 1) | ||
590 | 651 | ||
591 | TESTS(1); // * | 652 | TESTS(1); // * |
592 | TESTS(2); // * | 653 | // TESTS(2); // * |
593 | TESTS(3); // * | 654 | // TESTS(3); // * |
594 | TESTS(5); // * | 655 | // TESTS(5); // * |
595 | TESTS(8); // * | 656 | // TESTS(8); // * |
596 | TESTS(9); | 657 | // TESTS(9); |
597 | TESTS(11); | 658 | // TESTS(11); |
598 | TESTS(13); // * | 659 | // TESTS(13); // * |
599 | TESTS(15); | 660 | TESTS(15); |
600 | TESTS(16); | 661 | // TESTS(16); |
601 | TESTS(21); // * | 662 | // TESTS(21); // * |
602 | TESTS(34); // * | 663 | // TESTS(34); // * |
603 | TESTS(55); // * | 664 | // TESTS(55); // * |
604 | TESTS(89); // * | 665 | // TESTS(89); // * |
605 | 666 | ||
606 | for (i = 1; i < argc; i++) { | 667 | for (i = 1; i < argc; i++) { |
607 | if ((ret = read_whole_file(argv[i], | 668 | if ((ret = read_whole_file(argv[i], |
@@ -614,7 +675,7 @@ int main(int argc, char** argv) { | |||
614 | argv[i], buf_len); | 675 | argv[i], buf_len); |
615 | 676 | ||
616 | double min_time = -1.0; | 677 | double min_time = -1.0; |
617 | double min_uniqueness = 0.0; | 678 | double min_compression = 0.0; |
618 | 679 | ||
619 | for (vector<test_result_base*>::iterator i = all_tests.begin(); | 680 | for (vector<test_result_base*>::iterator i = all_tests.begin(); |
620 | i != all_tests.end(); ++i) { | 681 | i != all_tests.end(); ++i) { |
@@ -633,7 +694,7 @@ int main(int argc, char** argv) { | |||
633 | test->stat(); | 694 | test->stat(); |
634 | 695 | ||
635 | if (min_time < 0.0) { | 696 | if (min_time < 0.0) { |
636 | min_uniqueness = test->uniqueness(); | 697 | min_compression = test->compression(); |
637 | min_time = test->time(); | 698 | min_time = test->time(); |
638 | } | 699 | } |
639 | 700 | ||
@@ -641,26 +702,26 @@ int main(int argc, char** argv) { | |||
641 | min_time = test->time(); | 702 | min_time = test->time(); |
642 | } | 703 | } |
643 | 704 | ||
644 | if (min_uniqueness > test->uniqueness()) { | 705 | if (min_compression > test->compression()) { |
645 | min_uniqueness = test->uniqueness(); | 706 | min_compression = test->compression(); |
646 | } | 707 | } |
647 | 708 | ||
648 | test->print(); | 709 | test->print(); |
649 | } | 710 | } |
650 | 711 | ||
651 | for (vector<test_result_base*>::iterator i = all_tests.begin(); | 712 | // for (vector<test_result_base*>::iterator i = all_tests.begin(); |
652 | i != all_tests.end(); ++i) { | 713 | // i != all_tests.end(); ++i) { |
653 | test_result_base *test = *i; | 714 | // test_result_base *test = *i; |
654 | test->set_score(min_uniqueness, min_time); | 715 | // test->set_score(min_compression, min_time); |
655 | } | 716 | // } |
656 | 717 | ||
657 | sort(all_tests.begin(), all_tests.end(), compare_h()); | 718 | // sort(all_tests.begin(), all_tests.end(), compare_h()); |
658 | 719 | ||
659 | for (vector<test_result_base*>::iterator i = all_tests.begin(); | 720 | // for (vector<test_result_base*>::iterator i = all_tests.begin(); |
660 | i != all_tests.end(); ++i) { | 721 | // i != all_tests.end(); ++i) { |
661 | test_result_base *test = *i; | 722 | // test_result_base *test = *i; |
662 | test->print_accum(); | 723 | // test->print(); |
663 | } | 724 | // } |
664 | 725 | ||
665 | free(buf); | 726 | free(buf); |
666 | buf = NULL; | 727 | buf = NULL; |
diff --git a/xdelta3/xdelta3-hash.h b/xdelta3/xdelta3-hash.h index 5d12804..462c323 100644 --- a/xdelta3/xdelta3-hash.h +++ b/xdelta3/xdelta3-hash.h | |||
@@ -41,8 +41,7 @@ | |||
41 | else { run_c = (c); run_l = 1; } } while (0) | 41 | else { run_c = (c); run_l = 1; } } while (0) |
42 | 42 | ||
43 | /* Update the checksum state. */ | 43 | /* Update the checksum state. */ |
44 | #define OLD_LARGE_CKSUM 1 | 44 | #if ADLER_LARGE_CKSUM |
45 | #if OLD_LARGE_CKSUM | ||
46 | #define LARGE_CKSUM_UPDATE(cksum,base,look) \ | 45 | #define LARGE_CKSUM_UPDATE(cksum,base,look) \ |
47 | do { \ | 46 | do { \ |
48 | uint32_t old_c = PERMUTE((base)[0]); \ | 47 | uint32_t old_c = PERMUTE((base)[0]); \ |
@@ -52,16 +51,41 @@ | |||
52 | (cksum) = (high << 16) | low; \ | 51 | (cksum) = (high << 16) | low; \ |
53 | } while (0) | 52 | } while (0) |
54 | #else | 53 | #else |
55 | #define LARGE_CKSUM_UPDATE(cksum,base,look) \ | 54 | |
55 | // This is a table of powers of 1597334677 (a good MLCG multiplier for 32-bit | ||
56 | // modular arithmetic). TODO: add citation for "linear congruential | ||
57 | // generators of different sizes and good lattice structure" | ||
58 | static const uint32_t hash_multiplier = 1597334677U; | ||
59 | static const uint32_t hash_multiplier_powers[64] = { | ||
60 | 1U, 1597334677U, 1664532153U, 1152009645U, | ||
61 | 438510001U, 2554380293U, 2226829033U, 2237430173U, | ||
62 | 785718369U, 1614047349U, 2189918233U, 3004453517U, | ||
63 | 2504269841U, 1873956325U, 3298675273U, 184041597U, | ||
64 | 412048577U, 513892437U, 1512523129U, 420197229U, | ||
65 | 3195470449U, 3365769157U, 782672297U, 1830755165U, | ||
66 | 3607904545U, 2926038069U, 2592473U, 2764040269U, | ||
67 | 2237745361U, 1146488229U, 3329146121U, 975735357U, | ||
68 | 4047063425U, 3720555541U, 992599097U, 2284876077U, | ||
69 | 1371042609U, 2776575877U, 857709673U, 1933315357U, | ||
70 | 18085345U, 3544121333U, 2019536281U, 657247757U, | ||
71 | 3376546193U, 235703653U, 3581067209U, 1515267069U, | ||
72 | 2578040385U, 3954624469U, 25854713U, 2236907245U, | ||
73 | 3587404785U, 2101452613U, 498181929U, 2150584029U, | ||
74 | 1830304417U, 3629515701U, 1929108569U, 4095149005U, | ||
75 | 3948038737U, 2377245989U, 565564041U, 309202365U, | ||
76 | }; | ||
77 | |||
78 | #define LARGE_CKSUM_UPDATE(cksum,base,look) \ | ||
56 | do { \ | 79 | do { \ |
57 | // linear congruential generators of different | 80 | cksum = (cksum * hash_multiplier) - \ |
58 | // sizes and good lattice structure | 81 | (hash_multiplier_powers[look] * PERMUTE(base[0])) + \ |
59 | } while (1) | 82 | PERMUTE(base[look]); \ |
83 | } while (0) | ||
60 | #endif | 84 | #endif |
61 | 85 | ||
62 | /* Multiply and add hash function */ | ||
63 | #if ARITH_SMALL_CKSUM | 86 | #if ARITH_SMALL_CKSUM |
64 | #define SMALL_CKSUM_UPDATE(cksum,base,look) (cksum) = ((*(unsigned long*)(base+1)) * 71143) | 87 | #define SMALL_CKSUM_UPDATE(cksum,base,look) \ |
88 | (cksum) = ((*(uint32_t*)(base+1)) * 1597334677U) | ||
65 | #else | 89 | #else |
66 | #define SMALL_CKSUM_UPDATE LARGE_CKSUM_UPDATE | 90 | #define SMALL_CKSUM_UPDATE LARGE_CKSUM_UPDATE |
67 | #endif | 91 | #endif |
@@ -118,40 +142,17 @@ static const uint16_t __single_hash[256] = | |||
118 | Ctable stuff | 142 | Ctable stuff |
119 | ***********************************************************************/ | 143 | ***********************************************************************/ |
120 | 144 | ||
121 | #if HASH_PRIME | ||
122 | static const usize_t __primes[] = | ||
123 | { | ||
124 | 11, 19, 37, 73, 109, | ||
125 | 163, 251, 367, 557, 823, | ||
126 | 1237, 1861, 2777, 4177, 6247, | ||
127 | 9371, 14057, 21089, 31627, 47431, | ||
128 | 71143, 106721, 160073, 240101, 360163, | ||
129 | 540217, 810343, 1215497, 1823231, 2734867, | ||
130 | 4102283, 6153409, 9230113, 13845163, 20767711, | ||
131 | 31151543, 46727321, 70090921, 105136301, 157704401, | ||
132 | 236556601, 354834919, 532252367, 798378509, 1197567719, | ||
133 | 1796351503 | ||
134 | }; | ||
135 | |||
136 | static const usize_t __nprimes = SIZEOF_ARRAY (__primes); | ||
137 | #endif | ||
138 | |||
139 | static inline usize_t | 145 | static inline usize_t |
140 | xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) | 146 | xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) |
141 | { | 147 | { |
142 | #if HASH_PRIME | ||
143 | /* If the table is prime compute the modulus. */ | ||
144 | return (cksum % cfg->size); | ||
145 | #else | ||
146 | /* If the table is power-of-two compute the mask.*/ | ||
147 | return (cksum ^ (cksum >> cfg->shift)) & cfg->mask; | 148 | return (cksum ^ (cksum >> cfg->shift)) & cfg->mask; |
148 | #endif | ||
149 | } | 149 | } |
150 | 150 | ||
151 | /*********************************************************************** | 151 | /*********************************************************************** |
152 | Cksum function | 152 | Cksum function |
153 | ***********************************************************************/ | 153 | ***********************************************************************/ |
154 | 154 | ||
155 | #if ADLER_LARGE_CKSUM | ||
155 | static inline uint32_t | 156 | static inline uint32_t |
156 | xd3_lcksum (const uint8_t *seg, const int ln) | 157 | xd3_lcksum (const uint8_t *seg, const int ln) |
157 | { | 158 | { |
@@ -167,6 +168,18 @@ xd3_lcksum (const uint8_t *seg, const int ln) | |||
167 | 168 | ||
168 | return ((high & 0xffff) << 16) | (low & 0xffff); | 169 | return ((high & 0xffff) << 16) | (low & 0xffff); |
169 | } | 170 | } |
171 | #else | ||
172 | static inline uint32_t | ||
173 | xd3_lcksum (const uint8_t *seg, const int ln) | ||
174 | { | ||
175 | int i, j; | ||
176 | uint32_t h = 0; | ||
177 | for (i = 0, j = ln - 1; i < ln; ++i, --j) { | ||
178 | h += PERMUTE(seg[i]) * hash_multiplier_powers[j]; | ||
179 | } | ||
180 | return h; | ||
181 | } | ||
182 | #endif | ||
170 | 183 | ||
171 | #if ARITH_SMALL_CKSUM | 184 | #if ARITH_SMALL_CKSUM |
172 | static inline usize_t | 185 | static inline usize_t |
@@ -182,7 +195,6 @@ xd3_scksum (const uint8_t *seg, const int ln) | |||
182 | #endif | 195 | #endif |
183 | 196 | ||
184 | #if XD3_ENCODER | 197 | #if XD3_ENCODER |
185 | #if !HASH_PRIME | ||
186 | static usize_t | 198 | static usize_t |
187 | xd3_size_log2 (usize_t slots) | 199 | xd3_size_log2 (usize_t slots) |
188 | { | 200 | { |
@@ -193,7 +205,8 @@ xd3_size_log2 (usize_t slots) | |||
193 | { | 205 | { |
194 | if (slots < (1U << i)) | 206 | if (slots < (1U << i)) |
195 | { | 207 | { |
196 | bits = i-1; | 208 | bits = i-1; /* TODO: this is compaction=1 in checksum_test.cc and |
209 | * should not be fixed at 1. */ | ||
197 | break; | 210 | break; |
198 | } | 211 | } |
199 | } | 212 | } |
@@ -201,37 +214,18 @@ xd3_size_log2 (usize_t slots) | |||
201 | return bits; | 214 | return bits; |
202 | } | 215 | } |
203 | #endif | 216 | #endif |
204 | #endif | ||
205 | 217 | ||
206 | static void | 218 | static void |
207 | xd3_size_hashtable (xd3_stream *stream, | 219 | xd3_size_hashtable (xd3_stream *stream, |
208 | usize_t slots, | 220 | usize_t slots, |
209 | xd3_hash_cfg *cfg) | 221 | xd3_hash_cfg *cfg) |
210 | { | 222 | { |
211 | /* initialize ctable: the number of hash buckets is computed from the table | ||
212 | * of primes or the nearest power-of-two, in both cases rounding down in | ||
213 | * favor of using less memory. */ | ||
214 | |||
215 | #if HASH_PRIME | ||
216 | usize_t i; | ||
217 | |||
218 | cfg->size = __primes[__nprimes-1]; | ||
219 | |||
220 | for (i = 1; i < __nprimes; i += 1) | ||
221 | { | ||
222 | if (slots < __primes[i]) | ||
223 | { | ||
224 | cfg->size = __primes[i-1]; | ||
225 | break; | ||
226 | } | ||
227 | } | ||
228 | #else | ||
229 | int bits = xd3_size_log2 (slots); | 223 | int bits = xd3_size_log2 (slots); |
230 | 224 | ||
225 | /* TODO: there's a 32-bit assumption here */ | ||
231 | cfg->size = (1 << bits); | 226 | cfg->size = (1 << bits); |
232 | cfg->mask = (cfg->size - 1); | 227 | cfg->mask = (cfg->size - 1); |
233 | cfg->shift = min (32 - bits, 16); | 228 | cfg->shift = 32 - bits; |
234 | #endif | ||
235 | } | 229 | } |
236 | 230 | ||
237 | #endif | 231 | #endif |
diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h index 5c02a75..58f4d31 100644 --- a/xdelta3/xdelta3-main.h +++ b/xdelta3/xdelta3-main.h | |||
@@ -375,9 +375,9 @@ main_config (void) | |||
375 | DP(RINT "XD3_HARDMAXWINSIZE=%d\n", XD3_HARDMAXWINSIZE); | 375 | DP(RINT "XD3_HARDMAXWINSIZE=%d\n", XD3_HARDMAXWINSIZE); |
376 | DP(RINT "sizeof(int)=%d\n", sizeof(int)); | 376 | DP(RINT "sizeof(int)=%d\n", sizeof(int)); |
377 | DP(RINT "sizeof(uint32_t)=%d\n", sizeof(uint32_t)); | 377 | DP(RINT "sizeof(uint32_t)=%d\n", sizeof(uint32_t)); |
378 | DP(RINT "sizeof(uint64_t)=%d\n", sizeof(uint64_t)); | 378 | DP(RINT "sizeof(uint64_t)=%d\n", sizeof(uint64_t)); |
379 | DP(RINT "sizeof(usize_t)=%d\n", sizeof(usize_t)); | 379 | DP(RINT "sizeof(usize_t)=%d\n", sizeof(usize_t)); |
380 | DP(RINT "sizeof(xoff_t)=%d\n", sizeof(xoff_t)); | 380 | DP(RINT "sizeof(xoff_t)=%d\n", sizeof(xoff_t)); |
381 | 381 | ||
382 | return EXIT_SUCCESS; | 382 | return EXIT_SUCCESS; |
383 | } | 383 | } |
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c index 723a62a..8c14ef2 100644 --- a/xdelta3/xdelta3.c +++ b/xdelta3/xdelta3.c | |||
@@ -337,7 +337,7 @@ typedef enum { | |||
337 | 337 | ||
338 | typedef enum { | 338 | typedef enum { |
339 | SEC_NOFLAGS = 0, | 339 | SEC_NOFLAGS = 0, |
340 | SEC_COUNT_FREQS = (1 << 0), /* OPT: Not implemented: Could eliminate first pass of Huffman... */ | 340 | SEC_COUNT_FREQS = (1 << 0), /* Note: Not implemented: eliminate 1st Huffman pass. */ |
341 | } xd3_secondary_flags; | 341 | } xd3_secondary_flags; |
342 | 342 | ||
343 | typedef enum { | 343 | typedef enum { |
@@ -378,34 +378,40 @@ XD3_MAKELIST(xd3_rlist, xd3_rinst, link); | |||
378 | #define CODE_TABLE_STRING_SIZE (6 * 256) /* Should fit a code table string. */ | 378 | #define CODE_TABLE_STRING_SIZE (6 * 256) /* Should fit a code table string. */ |
379 | #define CODE_TABLE_VCDIFF_SIZE (6 * 256) /* Should fit a compressed code table string */ | 379 | #define CODE_TABLE_VCDIFF_SIZE (6 * 256) /* Should fit a compressed code table string */ |
380 | 380 | ||
381 | #define SECONDARY_ANY (SECONDARY_DJW || SECONDARY_FGK) /* True if any secondary compressor is used. */ | 381 | #define SECONDARY_ANY (SECONDARY_DJW || SECONDARY_FGK) |
382 | 382 | ||
383 | #define ALPHABET_SIZE 256 /* Used in test code--size of the secondary compressor alphabet. */ | 383 | #define ALPHABET_SIZE 256 /* Used in test code--size of the secondary |
384 | * compressor alphabet. */ | ||
384 | 385 | ||
385 | #define HASH_PRIME 0 /* Old hashing experiments */ | 386 | #define HASH_PERMUTE 1 /* The input is permuted by random nums */ |
386 | #define HASH_PERMUTE 1 | 387 | #define ARITH_SMALL_CKSUM 1 /* Simple small checksum function -- faster than RK */ |
387 | #define ARITH_SMALL_CKSUM 1 | 388 | #define ADLER_LARGE_CKSUM 1 /* Adler checksum vs. RK checksum */ |
388 | 389 | ||
389 | #define HASH_CKOFFSET 1U /* Table entries distinguish "no-entry" from offset 0 using this offset. */ | 390 | #define HASH_CKOFFSET 1U /* Table entries distinguish "no-entry" from |
391 | * offset 0 using this offset. */ | ||
390 | 392 | ||
391 | #define MIN_SMALL_LOOK 2U /* Match-optimization stuff. */ | 393 | #define MIN_SMALL_LOOK 2U /* Match-optimization stuff. */ |
392 | #define MIN_LARGE_LOOK 2U | 394 | #define MIN_LARGE_LOOK 2U |
393 | #define MIN_MATCH_OFFSET 1U | 395 | #define MIN_MATCH_OFFSET 1U |
394 | #define MAX_MATCH_SPLIT 18U /* VCDIFF code table: 18 is the default limit for direct-coded ADD sizes */ | 396 | #define MAX_MATCH_SPLIT 18U /* VCDIFF code table: 18 is the default limit |
395 | 397 | * for direct-coded ADD sizes */ | |
396 | #define LEAST_MATCH_INCR 0 /* The least number of bytes an overlapping match must beat | 398 | |
397 | * the preceding match by. This is a bias for the lazy | 399 | #define LEAST_MATCH_INCR 0 /* The least number of bytes an overlapping |
398 | * match optimization. A non-zero value means that an | 400 | * match must beat the preceding match by. This |
399 | * adjacent match has to be better by more than the step | 401 | * is a bias for the lazy match optimization. A |
402 | * non-zero value means that an adjacent match | ||
403 | * has to be better by more than the step | ||
400 | * between them. 0. */ | 404 | * between them. 0. */ |
401 | 405 | ||
402 | #define MIN_MATCH 4U /* VCDIFF code table: MIN_MATCH=4 */ | 406 | #define MIN_MATCH 4U /* VCDIFF code table: MIN_MATCH=4 */ |
403 | #define MIN_ADD 1U /* 1 */ | 407 | #define MIN_ADD 1U /* 1 */ |
404 | #define MIN_RUN 8U /* The shortest run, if it is shorter than this an immediate | 408 | #define MIN_RUN 8U /* The shortest run, if it is shorter than this |
405 | * add/copy will be just as good. ADD1/COPY6 = 1I+1D+1A bytes, | 409 | * an immediate add/copy will be just as good. |
406 | * RUN18 = 1I+1D+1A. */ | 410 | * ADD1/COPY6 = 1I+1D+1A bytes, RUN18 = |
411 | * 1I+1D+1A. */ | ||
407 | 412 | ||
408 | #define MAX_MODES 9 /* Maximum number of nodes used for compression--does not limit decompression. */ | 413 | #define MAX_MODES 9 /* Maximum number of nodes used for |
414 | * compression--does not limit decompression. */ | ||
409 | 415 | ||
410 | #define ENC_SECTS 4 /* Number of separate output sections. */ | 416 | #define ENC_SECTS 4 /* Number of separate output sections. */ |
411 | 417 | ||
@@ -5067,12 +5073,6 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) | |||
5067 | 5073 | ||
5068 | IF_DEBUG (xd3_verify_large_state (stream, inp, lcksum)); | 5074 | IF_DEBUG (xd3_verify_large_state (stream, inp, lcksum)); |
5069 | 5075 | ||
5070 | /* Note: To handle large checksum duplicates, this code | ||
5071 | * should be rearranged to resemble the small_match case | ||
5072 | * more. But how much of the code can be truly shared? The | ||
5073 | * main difference is the need for xd3_source_extend_match | ||
5074 | * to work outside of xd3_string_match, in the case where | ||
5075 | * inputs are identical. */ | ||
5076 | if (stream->large_table[linx] != 0) | 5076 | if (stream->large_table[linx] != 0) |
5077 | { | 5077 | { |
5078 | /* the match_setup will fail if the source window has | 5078 | /* the match_setup will fail if the source window has |
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h index 1dda36e..48d766f 100644 --- a/xdelta3/xdelta3.h +++ b/xdelta3/xdelta3.h | |||
@@ -119,6 +119,9 @@ typedef ULONGLONG uint64_t; | |||
119 | #define XD3_USE_LARGEFILE64 1 | 119 | #define XD3_USE_LARGEFILE64 1 |
120 | #endif | 120 | #endif |
121 | 121 | ||
122 | /* TODO: note that SIZEOF_USIZE_T is never set to 8, although it should be for | ||
123 | * a 64bit platform. OTOH, may be that using 32bits is appropriate even on a | ||
124 | * 64bit platform because we allocate large arrays of these values. */ | ||
122 | #if XD3_USE_LARGEFILE64 | 125 | #if XD3_USE_LARGEFILE64 |
123 | #define __USE_FILE_OFFSET64 1 /* GLIBC: for 64bit fileops, ... ? */ | 126 | #define __USE_FILE_OFFSET64 1 /* GLIBC: for 64bit fileops, ... ? */ |
124 | typedef uint64_t xoff_t; | 127 | typedef uint64_t xoff_t; |