diff options
author | Josh MacDonald <josh.macdonald@gmail.com> | 2014-10-25 22:39:52 -0700 |
---|---|---|
committer | Josh MacDonald <josh.macdonald@gmail.com> | 2014-10-25 22:39:52 -0700 |
commit | 496dc7140e18747d00be720978202915d68ded99 (patch) | |
tree | d8df7b8f8b4d989840b1ea78628033047150bdfb /xdelta3 | |
parent | ee2d187cc451a277606e4a3452fdc510ac14b19a (diff) |
Checksum test cleanups & dev
Diffstat (limited to 'xdelta3')
-rw-r--r-- | xdelta3/Makefile.am | 2 | ||||
-rwxr-xr-x | xdelta3/run_release.sh | 22 | ||||
-rw-r--r-- | xdelta3/testing/checksum_test.cc | 242 | ||||
-rw-r--r-- | xdelta3/testing/checksum_test_c.c | 1 | ||||
-rw-r--r-- | xdelta3/xdelta3-hash.h | 141 | ||||
-rw-r--r-- | xdelta3/xdelta3-internal.h | 22 | ||||
-rw-r--r-- | xdelta3/xdelta3.c | 133 | ||||
-rw-r--r-- | xdelta3/xdelta3.h | 6 |
8 files changed, 333 insertions, 236 deletions
diff --git a/xdelta3/Makefile.am b/xdelta3/Makefile.am index a60f337..d485333 100644 --- a/xdelta3/Makefile.am +++ b/xdelta3/Makefile.am | |||
@@ -42,7 +42,7 @@ xdelta3checksum_SOURCES = $(common_SOURCES) \ | |||
42 | # Note: for extra sanity checks, enable -Wconversion. Note there | 42 | # Note: for extra sanity checks, enable -Wconversion. Note there |
43 | # are a lot of false positives. | 43 | # are a lot of false positives. |
44 | WFLAGS = -Wall -Wshadow -fno-builtin -Wextra -Wsign-compare \ | 44 | WFLAGS = -Wall -Wshadow -fno-builtin -Wextra -Wsign-compare \ |
45 | -Wno-unused-parameter # -Weverything #-Wconversion | 45 | -Wno-unused-parameter # -Wconversion |
46 | 46 | ||
47 | 47 | ||
48 | C_WFLAGS = $(WFLAGS) -pedantic -std=c99 | 48 | C_WFLAGS = $(WFLAGS) -pedantic -std=c99 |
diff --git a/xdelta3/run_release.sh b/xdelta3/run_release.sh index 3060f96..d2ead52 100755 --- a/xdelta3/run_release.sh +++ b/xdelta3/run_release.sh | |||
@@ -1,10 +1,18 @@ | |||
1 | #!/bin/sh | 1 | #!/bin/sh |
2 | 2 | ||
3 | CFLAGS=-O2 | ||
4 | CXXFLAGS=-O2 | ||
5 | CC=clang | 3 | CC=clang |
6 | CXX=clang++ | 4 | CXX=clang++ |
7 | 5 | ||
6 | #CC=gcc | ||
7 | #CXX=g++ | ||
8 | |||
9 | # These are updated below | ||
10 | CFLAGS= | ||
11 | CXXFLAGS= | ||
12 | |||
13 | # Place C/C++ common flags here | ||
14 | COMMON=-O3 | ||
15 | |||
8 | export CFLAGS | 16 | export CFLAGS |
9 | export CXXFLAGS | 17 | export CXXFLAGS |
10 | export CC | 18 | export CC |
@@ -25,9 +33,9 @@ rm -rf build | |||
25 | # autoconf | 33 | # autoconf |
26 | 34 | ||
27 | function resetflag { | 35 | function resetflag { |
28 | CFLAGS="-$1 -I$LIBBASE/$MACH/include" | 36 | CFLAGS="$COMMON -$1 -I$LIBBASE/$MACH/include" |
29 | CXXFLAGS="-$1 -I$LIBBASE/$MACH/include" | 37 | CXXFLAGS="$COMMON -$1 -I$LIBBASE/$MACH/include" |
30 | LDFLAGS="-$1 -L$LIBBASE/$MACH/lib" | 38 | LDFLAGS="$COMMON -$1 -L$LIBBASE/$MACH/lib" |
31 | } | 39 | } |
32 | 40 | ||
33 | function addflag { | 41 | function addflag { |
@@ -44,7 +52,7 @@ function buildit { | |||
44 | D=build/$MACH/${sizebits}size-${offsetbits}off | 52 | D=build/$MACH/${sizebits}size-${offsetbits}off |
45 | mkdir -p $D | 53 | mkdir -p $D |
46 | (cd $D && $SRCDIR/configure --prefix=$PWD/bin --enable-debug-symbols) | 54 | (cd $D && $SRCDIR/configure --prefix=$PWD/bin --enable-debug-symbols) |
47 | (cd $D && make && make install) | 55 | (cd $D && make xdelta3checksum) |
48 | #echo Running regtest. | 56 | #echo Running regtest. |
49 | #(cd $D && ./xdelta3regtest) | 57 | #(cd $D && ./xdelta3regtest) |
50 | } | 58 | } |
@@ -67,5 +75,5 @@ function buildall { | |||
67 | buildit 64 64 | 75 | buildit 64 64 |
68 | } | 76 | } |
69 | 77 | ||
70 | buildall m32 | ||
71 | buildall m64 | 78 | buildall m64 |
79 | buildall m32 | ||
diff --git a/xdelta3/testing/checksum_test.cc b/xdelta3/testing/checksum_test.cc index 9937f14..b9a4b0b 100644 --- a/xdelta3/testing/checksum_test.cc +++ b/xdelta3/testing/checksum_test.cc | |||
@@ -28,37 +28,32 @@ struct true_type { }; | |||
28 | struct false_type { }; | 28 | struct false_type { }; |
29 | 29 | ||
30 | template <typename Word> | 30 | template <typename Word> |
31 | int bitsof(); | 31 | usize_t bitsof(); |
32 | 32 | ||
33 | template<> | 33 | template<> |
34 | int bitsof<uint32_t>() { | 34 | usize_t bitsof<uint32_t>() { |
35 | return 32; | 35 | return 32; |
36 | } | 36 | } |
37 | 37 | ||
38 | template<> | 38 | template<> |
39 | int bitsof<uint64_t>() { | 39 | usize_t bitsof<uint64_t>() { |
40 | return 64; | 40 | return 64; |
41 | } | 41 | } |
42 | 42 | ||
43 | struct plain { | 43 | template <typename Word> |
44 | usize_t operator()(const uint8_t &c) { | 44 | struct hhash { // shift "s" bits leaving the high bits as a hash value for |
45 | return c; | 45 | // this checksum, which are the most "distant" in terms of the |
46 | } | 46 | // spectral test for the rabin_karp MLCG. For short windows, |
47 | }; | 47 | // the high bits aren't enough, XOR "mask" worth of these in. |
48 | 48 | Word operator()(const Word t, const Word s, const Word mask) { | |
49 | struct randperm { | 49 | return (t >> s) ^ (t & mask); |
50 | usize_t operator()(const uint8_t &c) { | ||
51 | return __single_hash[c]; | ||
52 | } | 50 | } |
53 | }; | 51 | }; |
54 | 52 | ||
55 | template <typename Word> | 53 | template <typename Word> |
56 | struct hhash { // take "h" of the high-bits as a hash value for this | 54 | struct nonhash { |
57 | // checksum, which are the most "distant" in terms of the | 55 | Word operator()(const Word t, const Word h, const Word mask) { |
58 | // spectral test for the rabin_karp MLCG. For short windows, | 56 | return (t >> h) & mask; |
59 | // the high bits aren't enough, XOR "mask" worth of these in. | ||
60 | Word operator()(const Word& t, const int &h, const int &mask) { | ||
61 | return (t >> h) ^ (t & mask); | ||
62 | } | 57 | } |
63 | }; | 58 | }; |
64 | 59 | ||
@@ -77,18 +72,16 @@ uint64_t good_word<uint64_t>() { | |||
77 | 72 | ||
78 | // CLASSES | 73 | // CLASSES |
79 | 74 | ||
80 | #define SELF Word, CksumSize, CksumSkip, Permute, Hash, Compaction | 75 | #define SELF Word, CksumSize, CksumSkip, Hash, Compaction |
81 | #define MEMBER template <typename Word, \ | 76 | #define MEMBER template <typename Word, \ |
82 | int CksumSize, \ | 77 | int CksumSize, \ |
83 | int CksumSkip, \ | 78 | int CksumSkip, \ |
84 | typename Permute, \ | ||
85 | typename Hash, \ | 79 | typename Hash, \ |
86 | int Compaction> | 80 | int Compaction> |
87 | 81 | ||
88 | MEMBER | 82 | MEMBER |
89 | struct cksum_params { | 83 | struct cksum_params { |
90 | typedef Word word_type; | 84 | typedef Word word_type; |
91 | typedef Permute permute_type; | ||
92 | typedef Hash hash_type; | 85 | typedef Hash hash_type; |
93 | 86 | ||
94 | static const int cksum_size = CksumSize; | 87 | static const int cksum_size = CksumSize; |
@@ -116,7 +109,7 @@ struct rabin_karp : public cksum_params<SELF> { | |||
116 | Word step(const uint8_t *ptr) { | 109 | Word step(const uint8_t *ptr) { |
117 | Word h = 0; | 110 | Word h = 0; |
118 | for (int i = 0; i < CksumSize; i++) { | 111 | for (int i = 0; i < CksumSize; i++) { |
119 | h += Permute()(ptr[i]) * powers[i]; | 112 | h += (ptr[i]) * powers[i]; |
120 | } | 113 | } |
121 | return h; | 114 | return h; |
122 | } | 115 | } |
@@ -128,8 +121,7 @@ struct rabin_karp : public cksum_params<SELF> { | |||
128 | 121 | ||
129 | Word incr(const uint8_t *ptr) { | 122 | Word incr(const uint8_t *ptr) { |
130 | incr_state = multiplier * incr_state - | 123 | incr_state = multiplier * incr_state - |
131 | product * Permute()(ptr[-1]) + | 124 | product * (ptr[-1]) + (ptr[CksumSize - 1]); |
132 | Permute()(ptr[CksumSize - 1]); | ||
133 | return incr_state; | 125 | return incr_state; |
134 | } | 126 | } |
135 | 127 | ||
@@ -140,7 +132,7 @@ struct rabin_karp : public cksum_params<SELF> { | |||
140 | }; | 132 | }; |
141 | 133 | ||
142 | MEMBER | 134 | MEMBER |
143 | struct adler32_cksum : public cksum_params<SELF> { | 135 | struct large_cksum : public cksum_params<SELF> { |
144 | Word step(const uint8_t *ptr) { | 136 | Word step(const uint8_t *ptr) { |
145 | return xd3_large_cksum (ptr, CksumSize); | 137 | return xd3_large_cksum (ptr, CksumSize); |
146 | } | 138 | } |
@@ -168,15 +160,15 @@ struct file_stats { | |||
168 | typedef typename table_type::iterator table_iterator; | 160 | typedef typename table_type::iterator table_iterator; |
169 | typedef typename ptr_list::iterator ptr_iterator; | 161 | typedef typename ptr_list::iterator ptr_iterator; |
170 | 162 | ||
171 | int CksumSize; | 163 | usize_t cksum_size; |
172 | int cksum_skip; | 164 | usize_t cksum_skip; |
173 | int unique; | 165 | usize_t unique; |
174 | int unique_values; | 166 | usize_t unique_values; |
175 | int count; | 167 | usize_t count; |
176 | table_type table; | 168 | table_type table; |
177 | 169 | ||
178 | file_stats(int size, int skip) | 170 | file_stats(usize_t size, usize_t skip) |
179 | : CksumSize(size), | 171 | : cksum_size(size), |
180 | cksum_skip(skip), | 172 | cksum_skip(skip), |
181 | unique(0), | 173 | unique(0), |
182 | unique_values(0), | 174 | unique_values(0), |
@@ -204,7 +196,7 @@ struct file_stats { | |||
204 | for (ptr_iterator p_i = pl.begin(); | 196 | for (ptr_iterator p_i = pl.begin(); |
205 | p_i != pl.end(); | 197 | p_i != pl.end(); |
206 | ++p_i) { | 198 | ++p_i) { |
207 | if (memcmp(*p_i, ptr, CksumSize) == 0) { | 199 | if (memcmp(*p_i, ptr, cksum_size) == 0) { |
208 | return; | 200 | return; |
209 | } | 201 | } |
210 | } | 202 | } |
@@ -228,28 +220,20 @@ struct test_result_base { | |||
228 | } | 220 | } |
229 | virtual void reset() = 0; | 221 | virtual void reset() = 0; |
230 | virtual void print() = 0; | 222 | virtual void print() = 0; |
231 | virtual void get(const uint8_t* buf, const int buf_size, int iters) = 0; | 223 | virtual void get(const uint8_t* buf, const size_t buf_size, |
224 | usize_t iters) = 0; | ||
232 | virtual void stat() = 0; | 225 | virtual void stat() = 0; |
233 | virtual int count() = 0; | 226 | virtual usize_t count() = 0; |
234 | virtual int dups() = 0; | 227 | virtual usize_t dups() = 0; |
235 | virtual double uniqueness() = 0; | 228 | virtual double uniqueness() = 0; |
236 | virtual double fullness() = 0; | 229 | virtual double fullness() = 0; |
237 | virtual double collisions() = 0; | 230 | virtual double collisions() = 0; |
238 | virtual double coverage() = 0; | 231 | virtual double coverage() = 0; |
239 | virtual double compression() = 0; | 232 | virtual double compression() = 0; |
240 | virtual double time() = 0; | 233 | virtual double time() = 0; |
241 | virtual double score() = 0; | ||
242 | virtual void set_score(double min_dups_frac, double min_time) = 0; | ||
243 | virtual double total_time() = 0; | 234 | virtual double total_time() = 0; |
244 | virtual int total_count() = 0; | 235 | virtual usize_t total_count() = 0; |
245 | virtual int total_dups() = 0; | 236 | virtual usize_t total_dups() = 0; |
246 | }; | ||
247 | |||
248 | struct compare_h { | ||
249 | bool operator()(test_result_base *a, | ||
250 | test_result_base *b) { | ||
251 | return a->score() < b->score(); | ||
252 | } | ||
253 | }; | 237 | }; |
254 | 238 | ||
255 | template <typename Checksum> | 239 | template <typename Checksum> |
@@ -257,25 +241,24 @@ struct test_result : public test_result_base { | |||
257 | Checksum cksum; | 241 | Checksum cksum; |
258 | const char *test_name; | 242 | const char *test_name; |
259 | file_stats<typename Checksum::word_type> fstats; | 243 | file_stats<typename Checksum::word_type> fstats; |
260 | int test_size; | 244 | usize_t test_size; |
261 | int n_steps; | 245 | usize_t n_steps; |
262 | int n_incrs; | 246 | usize_t n_incrs; |
263 | int s_bits; | 247 | typename Checksum::word_type s_bits; |
264 | int s_mask; | 248 | typename Checksum::word_type s_mask; |
265 | int t_entries; | 249 | usize_t t_entries; |
266 | int h_bits; | 250 | usize_t h_bits; |
267 | int h_buckets_full; | 251 | usize_t h_buckets_full; |
268 | double h_score; | ||
269 | char *hash_table; | 252 | char *hash_table; |
270 | long accum_millis; | 253 | long accum_millis; |
271 | int accum_iters; | 254 | usize_t accum_iters; |
272 | 255 | ||
273 | // These are not reset | 256 | // These are not reset |
274 | double accum_time; | 257 | double accum_time; |
275 | int accum_count; | 258 | usize_t accum_count; |
276 | int accum_dups; | 259 | usize_t accum_dups; |
277 | int accum_colls; | 260 | usize_t accum_colls; |
278 | int accum_size; | 261 | size_t accum_size; |
279 | 262 | ||
280 | test_result(const char *name) | 263 | test_result(const char *name) |
281 | : test_name(name), | 264 | : test_name(name), |
@@ -297,18 +280,18 @@ struct test_result : public test_result_base { | |||
297 | 280 | ||
298 | void reset() { | 281 | void reset() { |
299 | // size of file | 282 | // size of file |
300 | test_size = -1; | 283 | test_size = 0; |
301 | 284 | ||
302 | // count | 285 | // count |
303 | n_steps = -1; | 286 | n_steps = 0; |
304 | n_incrs = -1; | 287 | n_incrs = 0; |
305 | 288 | ||
306 | // four values used by new_table()/summarize_table() | 289 | // four values used by new_table()/summarize_table() |
307 | s_bits = -1; | 290 | s_bits = 0; |
308 | s_mask = -1; | 291 | s_mask = 0; |
309 | t_entries = -1; | 292 | t_entries = 0; |
310 | h_bits = -1; | 293 | h_bits = 0; |
311 | h_buckets_full = -1; | 294 | h_buckets_full = 0; |
312 | 295 | ||
313 | accum_millis = 0; | 296 | accum_millis = 0; |
314 | accum_iters = 0; | 297 | accum_iters = 0; |
@@ -322,7 +305,7 @@ struct test_result : public test_result_base { | |||
322 | } | 305 | } |
323 | } | 306 | } |
324 | 307 | ||
325 | int count() { | 308 | usize_t count() { |
326 | if (Checksum::cksum_skip == 1) { | 309 | if (Checksum::cksum_skip == 1) { |
327 | return n_incrs; | 310 | return n_incrs; |
328 | } else { | 311 | } else { |
@@ -330,12 +313,17 @@ struct test_result : public test_result_base { | |||
330 | } | 313 | } |
331 | } | 314 | } |
332 | 315 | ||
333 | int dups() { | 316 | usize_t dups() { |
334 | return fstats.count - fstats.unique; | 317 | return fstats.count - fstats.unique; |
335 | } | 318 | } |
336 | 319 | ||
337 | int colls() { | 320 | /* Fraction of distinct strings of length cksum_size which are not |
338 | return fstats.unique - fstats.unique_values; | 321 | * represented in the hash table. */ |
322 | double collisions() { | ||
323 | return (fstats.unique - fstats.unique_values) / fstats.unique; | ||
324 | } | ||
325 | usize_t colls() { | ||
326 | return (fstats.unique - fstats.unique_values); | ||
339 | } | 327 | } |
340 | 328 | ||
341 | double uniqueness() { | 329 | double uniqueness() { |
@@ -346,10 +334,6 @@ struct test_result : public test_result_base { | |||
346 | return (double) h_buckets_full / (1 << h_bits); | 334 | return (double) h_buckets_full / (1 << h_bits); |
347 | } | 335 | } |
348 | 336 | ||
349 | double collisions() { | ||
350 | return (double) colls() / fstats.unique; | ||
351 | } | ||
352 | |||
353 | double coverage() { | 337 | double coverage() { |
354 | return (double) h_buckets_full / uniqueness() / count(); | 338 | return (double) h_buckets_full / uniqueness() / count(); |
355 | } | 339 | } |
@@ -362,28 +346,19 @@ struct test_result : public test_result_base { | |||
362 | return (double) accum_millis / accum_iters; | 346 | return (double) accum_millis / accum_iters; |
363 | } | 347 | } |
364 | 348 | ||
365 | double score() { | ||
366 | return h_score; | ||
367 | } | ||
368 | |||
369 | void set_score(double min_compression, double min_time) { | ||
370 | h_score = (compression() - 0.99 * min_compression) | ||
371 | * (time() - 0.99 * min_time); | ||
372 | } | ||
373 | |||
374 | double total_time() { | 349 | double total_time() { |
375 | return accum_time; | 350 | return accum_time; |
376 | } | 351 | } |
377 | 352 | ||
378 | int total_count() { | 353 | usize_t total_count() { |
379 | return accum_count; | 354 | return accum_count; |
380 | } | 355 | } |
381 | 356 | ||
382 | int total_dups() { | 357 | usize_t total_dups() { |
383 | return accum_dups; | 358 | return accum_dups; |
384 | } | 359 | } |
385 | 360 | ||
386 | int total_colls() { | 361 | usize_t total_colls() { |
387 | return accum_dups; | 362 | return accum_dups; |
388 | } | 363 | } |
389 | 364 | ||
@@ -400,26 +375,29 @@ struct test_result : public test_result_base { | |||
400 | fprintf(stderr, "internal error: %d != %d\n", fstats.count, count()); | 375 | fprintf(stderr, "internal error: %d != %d\n", fstats.count, count()); |
401 | abort(); | 376 | abort(); |
402 | } | 377 | } |
403 | printf("%s: (%u#%u) count %u uniq %0.2f%% full %u (%0.4f%% coll %0.4f%%) " | 378 | { |
404 | "covers %0.2f%% w/ 2^%d @ %.4f MB/s %u iters\n", | 379 | static int hdr_cnt = 0; |
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", | ||
405 | test_name, | 385 | test_name, |
406 | Checksum::cksum_size, | 386 | Checksum::cksum_size, |
407 | Checksum::cksum_skip, | 387 | Checksum::cksum_skip, |
408 | count(), | ||
409 | 100.0 * uniqueness(), | ||
410 | h_buckets_full, | ||
411 | 100.0 * fullness(), | ||
412 | 100.0 * collisions(), | ||
413 | 100.0 * coverage(), | ||
414 | h_bits, | 388 | h_bits, |
389 | count(), | ||
390 | uniqueness(), | ||
391 | fullness(), | ||
392 | collisions(), | ||
393 | coverage(), | ||
415 | 0.001 * accum_iters * test_size / accum_millis, | 394 | 0.001 * accum_iters * test_size / accum_millis, |
416 | accum_iters); | 395 | accum_iters); |
417 | } | 396 | } |
418 | 397 | ||
419 | int size_log2 (int slots) | 398 | usize_t size_log2 (usize_t slots) { |
420 | { | 399 | usize_t bits = bitsof<typename Checksum::word_type>() - 1; |
421 | int bits = bitsof<typename Checksum::word_type>() - 1; | 400 | usize_t i; |
422 | int i; | ||
423 | 401 | ||
424 | for (i = 3; i <= bits; i += 1) { | 402 | for (i = 3; i <= bits; i += 1) { |
425 | if (slots <= (1 << i)) { | 403 | if (slots <= (1 << i)) { |
@@ -430,31 +408,31 @@ struct test_result : public test_result_base { | |||
430 | return bits; | 408 | return bits; |
431 | } | 409 | } |
432 | 410 | ||
433 | void new_table(int entries) { | 411 | void new_table(usize_t entries) { |
434 | t_entries = entries; | 412 | t_entries = entries; |
435 | h_bits = size_log2(entries); | 413 | h_bits = size_log2(entries); |
436 | 414 | ||
437 | int n = 1 << h_bits; | 415 | usize_t n = 1 << h_bits; |
438 | 416 | ||
439 | s_bits = bitsof<typename Checksum::word_type>() - h_bits; | 417 | s_bits = bitsof<typename Checksum::word_type>() - h_bits; |
440 | s_mask = n - 1; | 418 | s_mask = n - 1U; |
441 | 419 | ||
442 | hash_table = new char[n / 8]; | 420 | hash_table = new char[n / 8]; |
443 | memset(hash_table, 0, n / 8); | 421 | memset(hash_table, 0, n / 8); |
444 | } | 422 | } |
445 | 423 | ||
446 | int get_table_bit(int i) { | 424 | int get_table_bit(usize_t i) { |
447 | return hash_table[i/8] & (1 << i%8); | 425 | return hash_table[i/8] & (1 << i%8); |
448 | } | 426 | } |
449 | 427 | ||
450 | int set_table_bit(int i) { | 428 | int set_table_bit(usize_t i) { |
451 | return hash_table[i/8] |= (1 << i%8); | 429 | return hash_table[i/8] |= (1 << i%8); |
452 | } | 430 | } |
453 | 431 | ||
454 | void summarize_table() { | 432 | void summarize_table() { |
455 | int n = 1 << h_bits; | 433 | usize_t n = 1 << h_bits; |
456 | int f = 0; | 434 | usize_t f = 0; |
457 | for (int i = 0; i < n; i++) { | 435 | for (usize_t i = 0; i < n; i++) { |
458 | if (get_table_bit(i)) { | 436 | if (get_table_bit(i)) { |
459 | f++; | 437 | f++; |
460 | } | 438 | } |
@@ -462,12 +440,12 @@ struct test_result : public test_result_base { | |||
462 | h_buckets_full = f; | 440 | h_buckets_full = f; |
463 | } | 441 | } |
464 | 442 | ||
465 | void get(const uint8_t* buf, const int buf_size, int test_iters) { | 443 | void get(const uint8_t* buf, const size_t buf_size, usize_t test_iters) { |
466 | typename Checksum::hash_type hash; | 444 | typename Checksum::hash_type hash; |
467 | const uint8_t *ptr; | 445 | const uint8_t *ptr; |
468 | const uint8_t *end; | 446 | const uint8_t *end; |
447 | usize_t periods; | ||
469 | int last_offset; | 448 | int last_offset; |
470 | int periods; | ||
471 | int stop; | 449 | int stop; |
472 | 450 | ||
473 | test_size = buf_size; | 451 | test_size = buf_size; |
@@ -488,7 +466,7 @@ struct test_result : public test_result_base { | |||
488 | // Compute file stats once. | 466 | // Compute file stats once. |
489 | if (fstats.unique_values == 0) { | 467 | if (fstats.unique_values == 0) { |
490 | if (Checksum::cksum_skip == 1) { | 468 | if (Checksum::cksum_skip == 1) { |
491 | for (int i = 0; i <= buf_size - Checksum::cksum_size; i++) { | 469 | for (size_t i = 0; i <= buf_size - Checksum::cksum_size; i++) { |
492 | fstats.update(hash(cksum.step(buf + i), s_bits, s_mask), buf + i); | 470 | fstats.update(hash(cksum.step(buf + i), s_bits, s_mask), buf + i); |
493 | } | 471 | } |
494 | } else { | 472 | } else { |
@@ -507,7 +485,7 @@ struct test_result : public test_result_base { | |||
507 | if (Checksum::cksum_skip != 1) { | 485 | if (Checksum::cksum_skip != 1) { |
508 | new_table(n_steps); | 486 | new_table(n_steps); |
509 | 487 | ||
510 | for (int i = 0; i < test_iters; i++) { | 488 | for (usize_t i = 0; i < test_iters; i++) { |
511 | ptr = buf + last_offset; | 489 | ptr = buf + last_offset; |
512 | end = buf + stop; | 490 | end = buf + stop; |
513 | 491 | ||
@@ -528,7 +506,7 @@ struct test_result : public test_result_base { | |||
528 | 506 | ||
529 | new_table(n_incrs); | 507 | new_table(n_incrs); |
530 | 508 | ||
531 | for (int i = 0; i < test_iters; i++) { | 509 | for (usize_t i = 0; i < test_iters; i++) { |
532 | ptr = buf; | 510 | ptr = buf; |
533 | end = buf + stop; | 511 | end = buf + stop; |
534 | 512 | ||
@@ -608,29 +586,31 @@ int main(int argc, char** argv) { | |||
608 | return 1; | 586 | return 1; |
609 | } | 587 | } |
610 | 588 | ||
611 | #define TEST(T,Z,S,P,H,C) \ | 589 | #define TEST(T,Z,S,H,C) \ |
612 | test_result<rabin_karp<T,Z,S,P,H<T>,C>> \ | 590 | test_result<rabin_karp<T,Z,S,H<T>,C>> \ |
613 | _rka_ ## T ## _ ## Z ## _ ## S ## _ ## P ## _ ## H ## _ ## C \ | 591 | _rka_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C \ |
614 | ("rka_" #T "_" #Z "_" #S "_" #P "_" #H "_" #C); \ | 592 | ("rka_" #T "_" #Z "_" #S "_" #H "_" #C); \ |
615 | test_result<adler32_cksum<T,Z,S,P,H<T>,C>> \ | 593 | test_result<large_cksum<T,Z,S,H<T>,C>> \ |
616 | _a32_ ## T ## _ ## Z ## _ ## S ## _ ## P ## _ ## H ## _ ## C \ | 594 | _xck_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C \ |
617 | ("a32_" #T "_" #Z "_" #S "_" #P "_" #H "_" #C) | 595 | ("xck_" #T "_" #Z "_" #S "_" #H "_" #C) |
618 | 596 | ||
619 | 597 | ||
620 | #define TESTS(SIZE, SKIP) \ | 598 | #define TESTS(SIZE, SKIP) \ |
621 | TEST(uint32_t, SIZE, SKIP, randperm, hhash, 1); \ | 599 | TEST(uint32_t, SIZE, SKIP, nonhash, 1); \ |
622 | TEST(uint32_t, SIZE, SKIP, plain, hhash, 1); \ | 600 | TEST(uint32_t, SIZE, SKIP, nonhash, 2); \ |
623 | TEST(uint32_t, SIZE, SKIP, randperm, hhash, 2); \ | 601 | TEST(uint32_t, SIZE, SKIP, hhash, 1); \ |
624 | TEST(uint32_t, SIZE, SKIP, plain, hhash, 2); \ | 602 | TEST(uint32_t, SIZE, SKIP, hhash, 2); \ |
625 | TEST(uint32_t, SIZE, SKIP, randperm, hhash, 3); \ | 603 | TEST(uint64_t, SIZE, SKIP, nonhash, 1); \ |
626 | TEST(uint32_t, SIZE, SKIP, plain, hhash, 3) | 604 | TEST(uint64_t, SIZE, SKIP, nonhash, 2); \ |
605 | TEST(uint64_t, SIZE, SKIP, hhash, 1); \ | ||
606 | TEST(uint64_t, SIZE, SKIP, hhash, 2) | ||
627 | 607 | ||
628 | // TESTS(9, 9); | 608 | TESTS(9, 9); |
629 | // TESTS(9, 15); | 609 | // TESTS(9, 15); |
630 | // TESTS(15, 15); | 610 | TESTS(15, 15); |
631 | TESTS(127, 127); | 611 | TESTS(127, 127); |
632 | // TESTS(127, 211); | 612 | // TESTS(127, 211); |
633 | // TESTS(211, 211); | 613 | TESTS(211, 211); |
634 | 614 | ||
635 | for (i = 1; i < argc; i++) { | 615 | for (i = 1; i < argc; i++) { |
636 | if ((ret = read_whole_file(argv[i], | 616 | if ((ret = read_whole_file(argv[i], |
@@ -650,7 +630,7 @@ int main(int argc, char** argv) { | |||
650 | test_result_base *test = *iter; | 630 | test_result_base *test = *iter; |
651 | test->reset(); | 631 | test->reset(); |
652 | 632 | ||
653 | int iters = 100; | 633 | usize_t iters = 100; |
654 | long start_test = get_millisecs_now(); | 634 | long start_test = get_millisecs_now(); |
655 | 635 | ||
656 | do { | 636 | do { |
diff --git a/xdelta3/testing/checksum_test_c.c b/xdelta3/testing/checksum_test_c.c new file mode 100644 index 0000000..2b32019 --- /dev/null +++ b/xdelta3/testing/checksum_test_c.c | |||
@@ -0,0 +1 @@ | |||
#include "../xdelta3.c" | |||
diff --git a/xdelta3/xdelta3-hash.h b/xdelta3/xdelta3-hash.h index bcdddc3..fd18099 100644 --- a/xdelta3/xdelta3-hash.h +++ b/xdelta3/xdelta3-hash.h | |||
@@ -1,5 +1,6 @@ | |||
1 | /* xdelta 3 - delta compression tools and library | 1 | /* xdelta 3 - delta compression tools and library |
2 | * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007. Joshua P. MacDonald | 2 | * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, 2011, 2012, 2014. |
3 | * Joshua P. MacDonald | ||
3 | * | 4 | * |
4 | * This program is free software; you can redistribute it and/or modify | 5 | * This program is free software; you can redistribute it and/or modify |
5 | * it under the terms of the GNU General Public License as published by | 6 | * it under the terms of the GNU General Public License as published by |
@@ -34,37 +35,17 @@ | |||
34 | #define SMALL_HASH_DEBUG2(s,inp) | 35 | #define SMALL_HASH_DEBUG2(s,inp) |
35 | #endif /* XD3_DEBUG */ | 36 | #endif /* XD3_DEBUG */ |
36 | 37 | ||
37 | /* This is a good hash multiplier for 32-bit LCGs: see "linear | ||
38 | * congruential generators of different sizes and good lattice | ||
39 | * structure" */ | ||
40 | static const uint32_t hash_multiplier = 1597334677U; | ||
41 | |||
42 | /*********************************************************************** | ||
43 | Permute stuff | ||
44 | ***********************************************************************/ | ||
45 | |||
46 | /* Update the checksum state. */ | ||
47 | #if ADLER_LARGE_CKSUM | ||
48 | inline uint32_t | ||
49 | xd3_large_cksum_update (uint32_t cksum, | ||
50 | const uint8_t *base, | ||
51 | usize_t look) { | ||
52 | uint32_t old_c = PERMUTE(base[0]); | ||
53 | uint32_t new_c = PERMUTE(base[look]); | ||
54 | uint32_t low = ((cksum & 0xffff) - old_c + new_c) & 0xffff; | ||
55 | uint32_t high = ((cksum >> 16) - (old_c * look) + low) & 0xffff; | ||
56 | return (high << 16) | low; | ||
57 | } | ||
58 | #else | ||
59 | /* TODO: revisit this topic */ | ||
60 | #endif | ||
61 | |||
62 | #if UNALIGNED_OK | 38 | #if UNALIGNED_OK |
63 | #define UNALIGNED_READ32(dest,src) (*(dest)) = (*(uint32_t*)(src)) | 39 | #define UNALIGNED_READ32(dest,src) (*(dest)) = (*(uint32_t*)(src)) |
64 | #else | 40 | #else |
65 | #define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4); | 41 | #define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4); |
66 | #endif | 42 | #endif |
67 | 43 | ||
44 | /* This is a good hash multiplier for 32-bit LCGs: see "linear | ||
45 | * congruential generators of different sizes and good lattice | ||
46 | * structure" */ | ||
47 | static const uint32_t hash_multiplier = 1597334677U; | ||
48 | |||
68 | /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */ | 49 | /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */ |
69 | static inline uint32_t | 50 | static inline uint32_t |
70 | xd3_scksum (uint32_t *state, | 51 | xd3_scksum (uint32_t *state, |
@@ -83,41 +64,111 @@ xd3_small_cksum_update (uint32_t *state, | |||
83 | return (*state) * hash_multiplier; | 64 | return (*state) * hash_multiplier; |
84 | } | 65 | } |
85 | 66 | ||
86 | /*********************************************************************** | ||
87 | Ctable stuff | ||
88 | ***********************************************************************/ | ||
89 | |||
90 | static inline usize_t | 67 | static inline usize_t |
91 | xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) | 68 | xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum) |
92 | { | 69 | { |
93 | return (cksum >> cfg->shift) ^ (cksum & cfg->mask); | 70 | return (cksum >> cfg->shift) ^ (cksum & cfg->mask); |
94 | } | 71 | } |
95 | 72 | ||
96 | /*********************************************************************** | 73 | #if XD3_ENCODER |
97 | Cksum function | 74 | #define PERMUTE32(x) (__single_hash32[x]) |
98 | ***********************************************************************/ | 75 | extern const uint16_t __single_hash32[256]; |
99 | 76 | ||
100 | #if ADLER_LARGE_CKSUM | 77 | inline uint32_t |
101 | inline usize_t | 78 | xd3_large32_cksum (const uint8_t *seg, const usize_t ln) |
102 | xd3_large_cksum (const uint8_t *seg, const usize_t ln) | ||
103 | { | 79 | { |
80 | static const uint32_t kBits = 16; | ||
81 | static const uint32_t kMask = 0xffff; | ||
104 | usize_t i = 0; | 82 | usize_t i = 0; |
105 | uint32_t low = 0; | 83 | uint32_t low = 0; |
106 | uint32_t high = 0; | 84 | uint32_t high = 0; |
107 | 85 | ||
108 | for (; i < ln; i += 1) | 86 | for (; i < ln; i += 1) |
109 | { | 87 | { |
110 | low += PERMUTE(*seg++); | 88 | low += PERMUTE32(*seg++); |
89 | high += low; | ||
90 | } | ||
91 | |||
92 | return ((high & kMask) << kBits) | (low & kMask); | ||
93 | } | ||
94 | |||
95 | inline uint32_t | ||
96 | xd3_large32_cksum_update (uint32_t cksum, | ||
97 | const uint8_t *base, | ||
98 | usize_t look) | ||
99 | { | ||
100 | static const uint32_t kBits = 16; | ||
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 | } | ||
108 | |||
109 | #undef PERMUTE32 | ||
110 | |||
111 | #define PERMUTE64(x) (__single_hash64[x]) | ||
112 | extern const uint32_t __single_hash64[256]; | ||
113 | |||
114 | inline uint64_t | ||
115 | xd3_large64_cksum (const uint8_t *seg, const usize_t len) | ||
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 < len; i += 1) | ||
124 | { | ||
125 | low += PERMUTE64(*seg++); | ||
111 | high += low; | 126 | high += low; |
112 | } | 127 | } |
113 | 128 | ||
114 | return ((high & 0xffff) << 16) | (low & 0xffff); | 129 | return ((high & kMask) << kBits) | (low & kMask); |
130 | } | ||
131 | |||
132 | inline uint64_t | ||
133 | xd3_large64_cksum_update (uint64_t cksum, | ||
134 | const uint8_t *base, | ||
135 | usize_t look) | ||
136 | { | ||
137 | static const uint64_t kBits = 32; | ||
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 | } | ||
115 | } | 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); | ||
116 | #else | 167 | #else |
117 | /* TODO */ | 168 | return xd3_large64_cksum_update (cksum, base, look); |
118 | #endif | 169 | #endif |
170 | } | ||
119 | 171 | ||
120 | #if XD3_ENCODER | ||
121 | static usize_t | 172 | static usize_t |
122 | xd3_size_hashtable_bits (usize_t slots) | 173 | xd3_size_hashtable_bits (usize_t slots) |
123 | { | 174 | { |
@@ -139,16 +190,16 @@ xd3_size_hashtable_bits (usize_t slots) | |||
139 | } | 190 | } |
140 | 191 | ||
141 | static void | 192 | static void |
142 | xd3_size_hashtable (xd3_stream *stream, | 193 | xd3_size_hashtable (xd3_stream *stream, |
143 | usize_t slots, | 194 | usize_t slots, |
144 | xd3_hash_cfg *cfg) | 195 | xd3_hash_cfg *cfg) |
145 | { | 196 | { |
146 | usize_t bits = xd3_size_hashtable_bits (slots); | 197 | usize_t bits = xd3_size_hashtable_bits (slots); |
147 | 198 | ||
148 | cfg->size = (1 << bits); | 199 | cfg->size = (1U << bits); |
149 | cfg->mask = (cfg->size - 1); | 200 | cfg->mask = (cfg->size - 1); |
150 | cfg->shift = (SIZEOF_USIZE_T * 8) - bits; | 201 | cfg->shift = (SIZEOF_USIZE_T * 8) - bits; |
151 | } | 202 | } |
152 | #endif | ||
153 | 203 | ||
154 | #endif | 204 | #endif |
205 | #endif /* _XDELTA3_HASH_H_ */ | ||
diff --git a/xdelta3/xdelta3-internal.h b/xdelta3/xdelta3-internal.h index 773a8e4..d9d56b9 100644 --- a/xdelta3/xdelta3-internal.h +++ b/xdelta3/xdelta3-internal.h | |||
@@ -1,5 +1,5 @@ | |||
1 | /* xdelta3 - delta compression tools and library | 1 | /* xdelta3 - delta compression tools and library |
2 | * Copyright (C) 2011, 2012 Joshua P. MacDonald | 2 | * Copyright (C) 2011, 2012, 2014 Joshua P. MacDonald |
3 | * | 3 | * |
4 | * This program is free software; you can redistribute it and/or modify | 4 | * This program is free software; you can redistribute it and/or modify |
5 | * it under the terms of the GNU General Public License as published by | 5 | * it under the terms of the GNU General Public License as published by |
@@ -47,9 +47,6 @@ void main_free (void *ptr); | |||
47 | int test_compare_files (const char* f0, const char* f1); | 47 | int test_compare_files (const char* f0, const char* f1); |
48 | usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno); | 48 | usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno); |
49 | xoff_t xd3_source_eof(const xd3_source *src); | 49 | xoff_t xd3_source_eof(const xd3_source *src); |
50 | uint32_t xd3_large_cksum_update (uint32_t cksum, | ||
51 | const uint8_t *base, | ||
52 | usize_t look); | ||
53 | int xd3_encode_init_full (xd3_stream *stream); | 50 | int xd3_encode_init_full (xd3_stream *stream); |
54 | usize_t xd3_pow2_roundup (usize_t x); | 51 | usize_t xd3_pow2_roundup (usize_t x); |
55 | long get_millisecs_now (); | 52 | long get_millisecs_now (); |
@@ -158,18 +155,9 @@ void xprintf(const char *fmt, ...) PRINTF_ATTRIBUTE(1,2); | |||
158 | #define UINT64_MAX 18446744073709551615ULL | 155 | #define UINT64_MAX 18446744073709551615ULL |
159 | #endif | 156 | #endif |
160 | 157 | ||
161 | /* TODO Eliminate this framework... */ | ||
162 | #define HASH_PERMUTE 1 /* The input is permuted by random nums */ | ||
163 | #define ADLER_LARGE_CKSUM 1 /* Adler checksum vs. RK checksum */ | ||
164 | |||
165 | #if HASH_PERMUTE == 0 | ||
166 | #define PERMUTE(x) (x) | ||
167 | #else | ||
168 | #define PERMUTE(x) (__single_hash[x]) | ||
169 | |||
170 | extern const uint16_t __single_hash[256]; | ||
171 | #endif | ||
172 | |||
173 | usize_t xd3_large_cksum (const uint8_t *seg, const usize_t ln); | 158 | usize_t xd3_large_cksum (const uint8_t *seg, const usize_t ln); |
159 | usize_t xd3_large_cksum_update (usize_t cksum, | ||
160 | const uint8_t *base, | ||
161 | usize_t look); | ||
174 | 162 | ||
175 | #endif // XDELTA3_INTERNAL_H__ | 163 | #endif /* XDELTA3_INTERNAL_H__ */ |
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c index 5f52ad9..b8aa9eb 100644 --- a/xdelta3/xdelta3.c +++ b/xdelta3/xdelta3.c | |||
@@ -535,7 +535,7 @@ static void xd3_verify_run_state (xd3_stream *stream, | |||
535 | uint8_t *x_run_c); | 535 | uint8_t *x_run_c); |
536 | static void xd3_verify_large_state (xd3_stream *stream, | 536 | static void xd3_verify_large_state (xd3_stream *stream, |
537 | const uint8_t *inp, | 537 | const uint8_t *inp, |
538 | uint32_t x_cksum); | 538 | usize_t x_cksum); |
539 | static void xd3_verify_small_state (xd3_stream *stream, | 539 | static void xd3_verify_small_state (xd3_stream *stream, |
540 | const uint8_t *inp, | 540 | const uint8_t *inp, |
541 | uint32_t x_cksum); | 541 | uint32_t x_cksum); |
@@ -567,17 +567,17 @@ static int xd3_selftest (void); | |||
567 | #define UINT64_OFLOW_MASK 0xfe00000000000000ULL | 567 | #define UINT64_OFLOW_MASK 0xfe00000000000000ULL |
568 | 568 | ||
569 | #if SIZEOF_USIZE_T == 4 | 569 | #if SIZEOF_USIZE_T == 4 |
570 | #define USIZE_T_MAX UINT32_MAX | 570 | #define USIZE_T_MAX UINT32_MAX |
571 | #define xd3_decode_size xd3_decode_uint32_t | 571 | #define xd3_decode_size xd3_decode_uint32_t |
572 | #define xd3_emit_size xd3_emit_uint32_t | 572 | #define xd3_emit_size xd3_emit_uint32_t |
573 | #define xd3_sizeof_size xd3_sizeof_uint32_t | 573 | #define xd3_sizeof_size xd3_sizeof_uint32_t |
574 | #define xd3_read_size xd3_read_uint32_t | 574 | #define xd3_read_size xd3_read_uint32_t |
575 | #elif SIZEOF_USIZE_T == 8 | 575 | #elif SIZEOF_USIZE_T == 8 |
576 | #define USIZE_T_MAX UINT64_MAX | 576 | #define USIZE_T_MAX UINT64_MAX |
577 | #define xd3_decode_size xd3_decode_uint64_t | 577 | #define xd3_decode_size xd3_decode_uint64_t |
578 | #define xd3_emit_size xd3_emit_uint64_t | 578 | #define xd3_emit_size xd3_emit_uint64_t |
579 | #define xd3_sizeof_size xd3_sizeof_uint64_t | 579 | #define xd3_sizeof_size xd3_sizeof_uint64_t |
580 | #define xd3_read_size xd3_read_uint64_t | 580 | #define xd3_read_size xd3_read_uint64_t |
581 | #endif | 581 | #endif |
582 | 582 | ||
583 | #if SIZEOF_XOFF_T == 4 | 583 | #if SIZEOF_XOFF_T == 4 |
@@ -798,10 +798,9 @@ const xd3_sec_type lzma_sec_type = | |||
798 | #endif /* __XDELTA3_C_HEADER_PASS__ */ | 798 | #endif /* __XDELTA3_C_HEADER_PASS__ */ |
799 | #ifdef __XDELTA3_C_INLINE_PASS__ | 799 | #ifdef __XDELTA3_C_INLINE_PASS__ |
800 | 800 | ||
801 | const uint16_t __single_hash[256] = | 801 | const uint16_t __single_hash32[256] = |
802 | { | 802 | { |
803 | /* Random numbers generated using SLIB's pseudo-random number generator. | 803 | /* This hashes the input alphabet (Scheme SLIB pseudo-random). */ |
804 | * This hashes the input alphabet. */ | ||
805 | 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46, | 804 | 0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46, |
806 | 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602, | 805 | 0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602, |
807 | 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6, | 806 | 0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6, |
@@ -836,6 +835,75 @@ const uint16_t __single_hash[256] = | |||
836 | 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5 | 835 | 0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5 |
837 | }; | 836 | }; |
838 | 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 | |||
839 | /**************************************************************** | 907 | /**************************************************************** |
840 | Instruction tables | 908 | Instruction tables |
841 | *****************************************************************/ | 909 | *****************************************************************/ |
@@ -952,7 +1020,7 @@ xd3_build_code_table (const xd3_code_table_desc *desc, xd3_dinst *tbl) | |||
952 | { | 1020 | { |
953 | uint8_t size1, size2; | 1021 | uint8_t size1, size2; |
954 | uint8_t mode; | 1022 | uint8_t mode; |
955 | usize_t cpy_modes = 2 + desc->near_modes + desc->same_modes; | 1023 | usize_t cpy_modes = 2U + desc->near_modes + desc->same_modes; |
956 | xd3_dinst *d = tbl; | 1024 | xd3_dinst *d = tbl; |
957 | 1025 | ||
958 | (d++)->type1 = XD3_RUN; | 1026 | (d++)->type1 = XD3_RUN; |
@@ -968,7 +1036,7 @@ xd3_build_code_table (const xd3_code_table_desc *desc, xd3_dinst *tbl) | |||
968 | { | 1036 | { |
969 | (d++)->type1 = XD3_CPY + mode; | 1037 | (d++)->type1 = XD3_CPY + mode; |
970 | 1038 | ||
971 | for (size1 = MIN_MATCH; size1 < MIN_MATCH + desc->cpy_sizes; | 1039 | for (size1 = MIN_MATCH; size1 < MIN_MATCH + desc->cpy_sizes; |
972 | size1 += 1, d += 1) | 1040 | size1 += 1, d += 1) |
973 | { | 1041 | { |
974 | d->type1 = XD3_CPY + mode; | 1042 | d->type1 = XD3_CPY + mode; |
@@ -1078,8 +1146,8 @@ xd3_choose_instruction (xd3_rinst *prev, xd3_rinst *inst) | |||
1078 | if ( (inst->size <= 6) && | 1146 | if ( (inst->size <= 6) && |
1079 | (mode <= 5) ) | 1147 | (mode <= 5) ) |
1080 | { | 1148 | { |
1081 | prev->code2 = (uint8_t)(163 + (mode * 12) + | 1149 | prev->code2 = (uint8_t)(163 + (mode * 12) + |
1082 | (3 * (prev->size - 1)) + | 1150 | (3 * (prev->size - 1)) + |
1083 | (inst->size - 4)); | 1151 | (inst->size - 4)); |
1084 | XD3_ASSERT (prev->code2 <= 234); | 1152 | XD3_ASSERT (prev->code2 <= 234); |
1085 | } | 1153 | } |
@@ -1358,10 +1426,10 @@ xd3_emit_bytes (xd3_stream *stream, | |||
1358 | Integer encoder/decoder functions | 1426 | Integer encoder/decoder functions |
1359 | **********************************************************************/ | 1427 | **********************************************************************/ |
1360 | 1428 | ||
1361 | #define DECODE_INTEGER_TYPE(PART,OFLOW) \ | 1429 | #define DECODE_INTEGER_TYPE(TYPE,PART,OFLOW) \ |
1362 | while (stream->avail_in != 0) \ | 1430 | while (stream->avail_in != 0) \ |
1363 | { \ | 1431 | { \ |
1364 | usize_t next = stream->next_in[0]; \ | 1432 | TYPE next = stream->next_in[0]; \ |
1365 | \ | 1433 | \ |
1366 | DECODE_INPUT(1); \ | 1434 | DECODE_INPUT(1); \ |
1367 | \ | 1435 | \ |
@@ -1386,8 +1454,8 @@ xd3_emit_bytes (xd3_stream *stream, | |||
1386 | 1454 | ||
1387 | #define READ_INTEGER_TYPE(TYPE, OFLOW) \ | 1455 | #define READ_INTEGER_TYPE(TYPE, OFLOW) \ |
1388 | TYPE val = 0; \ | 1456 | TYPE val = 0; \ |
1457 | TYPE next; \ | ||
1389 | const uint8_t *inp = (*inpp); \ | 1458 | const uint8_t *inp = (*inpp); \ |
1390 | usize_t next; \ | ||
1391 | \ | 1459 | \ |
1392 | do \ | 1460 | do \ |
1393 | { \ | 1461 | { \ |
@@ -1447,7 +1515,7 @@ xd3_sizeof_uint32_t (uint32_t num) | |||
1447 | 1515 | ||
1448 | int | 1516 | int |
1449 | xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val) | 1517 | xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val) |
1450 | { DECODE_INTEGER_TYPE (stream->dec_32part, UINT32_OFLOW_MASK); } | 1518 | { DECODE_INTEGER_TYPE (uint32_t, stream->dec_32part, UINT32_OFLOW_MASK); } |
1451 | 1519 | ||
1452 | int | 1520 | int |
1453 | xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp, | 1521 | xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp, |
@@ -1464,7 +1532,7 @@ xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num) | |||
1464 | #if USE_UINT64 | 1532 | #if USE_UINT64 |
1465 | int | 1533 | int |
1466 | xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val) | 1534 | xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val) |
1467 | { DECODE_INTEGER_TYPE (stream->dec_64part, UINT64_OFLOW_MASK); } | 1535 | { DECODE_INTEGER_TYPE (uint64_t, stream->dec_64part, UINT64_OFLOW_MASK); } |
1468 | 1536 | ||
1469 | #if XD3_ENCODER | 1537 | #if XD3_ENCODER |
1470 | int | 1538 | int |
@@ -2525,7 +2593,8 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst) | |||
2525 | { | 2593 | { |
2526 | if (stream->iout->code2 != 0) | 2594 | if (stream->iout->code2 != 0) |
2527 | { | 2595 | { |
2528 | if ((ret = xd3_emit_double (stream, stream->iout, inst, stream->iout->code2))) { return ret; } | 2596 | if ((ret = xd3_emit_double (stream, stream->iout, inst, |
2597 | stream->iout->code2))) { return ret; } | ||
2529 | 2598 | ||
2530 | xd3_iopt_free_nonadd (stream, stream->iout); | 2599 | xd3_iopt_free_nonadd (stream, stream->iout); |
2531 | xd3_iopt_free_nonadd (stream, inst); | 2600 | xd3_iopt_free_nonadd (stream, inst); |
@@ -3612,7 +3681,7 @@ xd3_process_stream (int is_encode, | |||
3612 | case XD3_OUTPUT: { /* memcpy below */ break; } | 3681 | case XD3_OUTPUT: { /* memcpy below */ break; } |
3613 | case XD3_INPUT: { | 3682 | case XD3_INPUT: { |
3614 | n = min(stream->winsize, input_size - ipos); | 3683 | n = min(stream->winsize, input_size - ipos); |
3615 | if (n == 0) | 3684 | if (n == 0) |
3616 | { | 3685 | { |
3617 | goto done; | 3686 | goto done; |
3618 | } | 3687 | } |
@@ -3948,13 +4017,13 @@ xd3_srcwin_setup (xd3_stream *stream) | |||
3948 | 4017 | ||
3949 | if (src->eof_known) | 4018 | if (src->eof_known) |
3950 | { | 4019 | { |
3951 | /* Note: if the source size is known, we must reduce srclen or | 4020 | /* Note: if the source size is known, we must reduce srclen or |
3952 | * code that expects to pass a single block w/ getblk == NULL | 4021 | * code that expects to pass a single block w/ getblk == NULL |
3953 | * will not function, as the code will return GETSRCBLK asking | 4022 | * will not function, as the code will return GETSRCBLK asking |
3954 | * for the second block. */ | 4023 | * for the second block. */ |
3955 | src->srclen = min (src->srclen, xd3_source_eof(src) - src->srcbase); | 4024 | src->srclen = min (src->srclen, xd3_source_eof(src) - src->srcbase); |
3956 | } | 4025 | } |
3957 | 4026 | ||
3958 | IF_DEBUG1 (DP(RINT "[srcwin_setup_constrained] base %llu len %llu\n", | 4027 | IF_DEBUG1 (DP(RINT "[srcwin_setup_constrained] base %llu len %llu\n", |
3959 | src->srcbase, src->srclen)); | 4028 | src->srcbase, src->srclen)); |
3960 | 4029 | ||
@@ -4545,7 +4614,7 @@ xd3_smatch (xd3_stream *stream, | |||
4545 | static void | 4614 | static void |
4546 | xd3_verify_small_state (xd3_stream *stream, | 4615 | xd3_verify_small_state (xd3_stream *stream, |
4547 | const uint8_t *inp, | 4616 | const uint8_t *inp, |
4548 | uint32_t x_cksum) | 4617 | uint32_t x_cksum) |
4549 | { | 4618 | { |
4550 | uint32_t state; | 4619 | uint32_t state; |
4551 | uint32_t cksum = xd3_scksum (&state, inp, stream->smatcher.small_look); | 4620 | uint32_t cksum = xd3_scksum (&state, inp, stream->smatcher.small_look); |
@@ -4556,9 +4625,9 @@ xd3_verify_small_state (xd3_stream *stream, | |||
4556 | static void | 4625 | static void |
4557 | xd3_verify_large_state (xd3_stream *stream, | 4626 | xd3_verify_large_state (xd3_stream *stream, |
4558 | const uint8_t *inp, | 4627 | const uint8_t *inp, |
4559 | uint32_t x_cksum) | 4628 | usize_t x_cksum) |
4560 | { | 4629 | { |
4561 | uint32_t cksum = xd3_large_cksum (inp, stream->smatcher.large_look); | 4630 | usize_t cksum = xd3_large_cksum (inp, stream->smatcher.large_look); |
4562 | XD3_ASSERT (cksum == x_cksum); | 4631 | XD3_ASSERT (cksum == x_cksum); |
4563 | } | 4632 | } |
4564 | static void | 4633 | static void |
@@ -4702,7 +4771,7 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4702 | 4771 | ||
4703 | do | 4772 | do |
4704 | { | 4773 | { |
4705 | uint32_t cksum = xd3_large_cksum (stream->src->curblk + blkpos, | 4774 | usize_t cksum = xd3_large_cksum (stream->src->curblk + blkpos, |
4706 | stream->smatcher.large_look); | 4775 | stream->smatcher.large_look); |
4707 | usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum); | 4776 | usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum); |
4708 | 4777 | ||
@@ -4795,7 +4864,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) | |||
4795 | const uint8_t *inp; | 4864 | const uint8_t *inp; |
4796 | uint32_t scksum = 0; | 4865 | uint32_t scksum = 0; |
4797 | uint32_t scksum_state = 0; | 4866 | uint32_t scksum_state = 0; |
4798 | uint32_t lcksum = 0; | 4867 | usize_t lcksum = 0; |
4799 | usize_t sinx; | 4868 | usize_t sinx; |
4800 | usize_t linx; | 4869 | usize_t linx; |
4801 | uint8_t run_c; | 4870 | uint8_t run_c; |
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h index 31603f0..1fd55b0 100644 --- a/xdelta3/xdelta3.h +++ b/xdelta3/xdelta3.h | |||
@@ -1,6 +1,6 @@ | |||
1 | /* xdelta 3 - delta compression tools and library | 1 | /* xdelta 3 - delta compression tools and library |
2 | * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, | 2 | * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, |
3 | * 2008, 2009, 2010, 2011, 2012, 2013. Joshua P. MacDonald | 3 | * 2008, 2009, 2010, 2011, 2012, 2013, 2014. Joshua P. MacDonald |
4 | * | 4 | * |
5 | * This program is free software; you can redistribute it and/or modify | 5 | * This program is free software; you can redistribute it and/or modify |
6 | * it under the terms of the GNU General Public License as published by | 6 | * it under the terms of the GNU General Public License as published by |
@@ -720,7 +720,7 @@ struct _xd3_config | |||
720 | xd3_alloc_func *alloc; | 720 | xd3_alloc_func *alloc; |
721 | xd3_free_func *freef; | 721 | xd3_free_func *freef; |
722 | void *opaque; /* Not used. */ | 722 | void *opaque; /* Not used. */ |
723 | int flags; /* stream->flags are initialized | 723 | uint32_t flags; /* stream->flags are initialized |
724 | * from xd3_config & never | 724 | * from xd3_config & never |
725 | * modified by the library. Use | 725 | * modified by the library. Use |
726 | * xd3_set_flags to modify flags | 726 | * xd3_set_flags to modify flags |
@@ -1249,7 +1249,7 @@ const char* xd3_strerror (int ret); | |||
1249 | specified flags. */ | 1249 | specified flags. */ |
1250 | static inline | 1250 | static inline |
1251 | void xd3_init_config (xd3_config *config, | 1251 | void xd3_init_config (xd3_config *config, |
1252 | int flags) | 1252 | uint32_t flags) |
1253 | { | 1253 | { |
1254 | memset (config, 0, sizeof (*config)); | 1254 | memset (config, 0, sizeof (*config)); |
1255 | config->flags = flags; | 1255 | config->flags = flags; |