Rev 1896 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 1896 | Rev 3926 | ||
|---|---|---|---|
| Line 1... | Line 1... | ||
| 1 | /* adler32.c -- compute the Adler-32 checksum of a data stream |
1 | /* adler32.c -- compute the Adler-32 checksum of a data stream |
| 2 | * Copyright (C) 1995-2007 Mark Adler |
2 | * Copyright (C) 1995-2011 Mark Adler |
| 3 | * For conditions of distribution and use, see copyright notice in zlib.h |
3 | * For conditions of distribution and use, see copyright notice in zlib.h |
| 4 | */ |
4 | */ |
| Line 5... | Line 5... | ||
| 5 | 5 | ||
| Line 6... | Line 6... | ||
| 6 | /* @(#) $Id$ */ |
6 | /* @(#) $Id$ */ |
| Line 7... | Line 7... | ||
| 7 | 7 | ||
| Line 8... | Line 8... | ||
| 8 | #include "zutil.h" |
8 | #include "zutil.h" |
| Line 9... | Line 9... | ||
| 9 | 9 | ||
| 10 | #define local static |
10 | #define local static |
| 11 | 11 | ||
| Line 12... | Line 12... | ||
| 12 | local uLong adler32_combine_(uLong adler1, uLong adler2, z_off64_t len2); |
12 | local uLong adler32_combine_ OF((uLong adler1, uLong adler2, z_off64_t len2)); |
| 13 | 13 | ||
| 14 | #define BASE 65521UL /* largest prime smaller than 65536 */ |
14 | #define BASE 65521 /* largest prime smaller than 65536 */ |
| 15 | #define NMAX 5552 |
15 | #define NMAX 5552 |
| 16 | /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ |
16 | /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ |
| Line 17... | Line 17... | ||
| 17 | 17 | ||
| - | 18 | #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} |
|
| 18 | #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} |
19 | #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); |
| - | 20 | #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); |
|
| - | 21 | #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); |
|
| - | 22 | #define DO16(buf) DO8(buf,0); DO8(buf,8); |
|
| - | 23 | ||
| - | 24 | /* use NO_DIVIDE if your processor does not do division in hardware -- |
|
| - | 25 | try it both ways to see which is faster */ |
|
| - | 26 | #ifdef NO_DIVIDE |
|
| - | 27 | /* note that this assumes BASE is 65521, where 65536 % 65521 == 15 |
|
| 19 | #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); |
28 | (thank you to John Reiser for pointing this out) */ |
| 20 | #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); |
29 | # define CHOP(a) \ |
| 21 | #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); |
- | |
| 22 | #define DO16(buf) DO8(buf,0); DO8(buf,8); |
- | |
| 23 | - | ||
| 24 | /* use NO_DIVIDE if your processor does not do division in hardware */ |
- | |
| 25 | #ifdef NO_DIVIDE |
- | |
| 26 | # define MOD(a) \ |
- | |
| 27 | do { \ |
- | |
| 28 | if (a >= (BASE << 16)) a -= (BASE << 16); \ |
- | |
| 29 | if (a >= (BASE << 15)) a -= (BASE << 15); \ |
- | |
| 30 | if (a >= (BASE << 14)) a -= (BASE << 14); \ |
30 | do { \ |
| 31 | if (a >= (BASE << 13)) a -= (BASE << 13); \ |
- | |
| 32 | if (a >= (BASE << 12)) a -= (BASE << 12); \ |
- | |
| 33 | if (a >= (BASE << 11)) a -= (BASE << 11); \ |
- | |
| 34 | if (a >= (BASE << 10)) a -= (BASE << 10); \ |
- | |
| 35 | if (a >= (BASE << 9)) a -= (BASE << 9); \ |
- | |
| 36 | if (a >= (BASE << 8)) a -= (BASE << 8); \ |
- | |
| 37 | if (a >= (BASE << 7)) a -= (BASE << 7); \ |
31 | unsigned long tmp = a >> 16; \ |
| 38 | if (a >= (BASE << 6)) a -= (BASE << 6); \ |
32 | a &= 0xffffUL; \ |
| 39 | if (a >= (BASE << 5)) a -= (BASE << 5); \ |
33 | a += (tmp << 4) - tmp; \ |
| 40 | if (a >= (BASE << 4)) a -= (BASE << 4); \ |
34 | } while (0) |
| - | 35 | # define MOD28(a) \ |
|
| - | 36 | do { \ |
|
| - | 37 | CHOP(a); \ |
|
| - | 38 | if (a >= BASE) a -= BASE; \ |
|
| - | 39 | } while (0) |
|
| 41 | if (a >= (BASE << 3)) a -= (BASE << 3); \ |
40 | # define MOD(a) \ |
| - | 41 | do { \ |
|
| 42 | if (a >= (BASE << 2)) a -= (BASE << 2); \ |
42 | CHOP(a); \ |
| - | 43 | MOD28(a); \ |
|
| - | 44 | } while (0) |
|
| 43 | if (a >= (BASE << 1)) a -= (BASE << 1); \ |
45 | # define MOD63(a) \ |
| - | 46 | do { /* this assumes a is not negative */ \ |
|
| - | 47 | z_off64_t tmp = a >> 32; \ |
|
| 44 | if (a >= BASE) a -= BASE; \ |
48 | a &= 0xffffffffL; \ |
| 45 | } while (0) |
49 | a += (tmp << 8) - (tmp << 5) + tmp; \ |
| 46 | # define MOD4(a) \ |
50 | tmp = a >> 16; \ |
| 47 | do { \ |
51 | a &= 0xffffL; \ |
| 48 | if (a >= (BASE << 4)) a -= (BASE << 4); \ |
52 | a += (tmp << 4) - tmp; \ |
| - | 53 | tmp = a >> 16; \ |
|
| 49 | if (a >= (BASE << 3)) a -= (BASE << 3); \ |
54 | a &= 0xffffL; \ |
| 50 | if (a >= (BASE << 2)) a -= (BASE << 2); \ |
55 | a += (tmp << 4) - tmp; \ |
| Line 51... | Line 56... | ||
| 51 | if (a >= (BASE << 1)) a -= (BASE << 1); \ |
56 | if (a >= BASE) a -= BASE; \ |
| 52 | if (a >= BASE) a -= BASE; \ |
57 | } while (0) |
| 53 | } while (0) |
58 | #else |
| Line 90... | Line 95... | ||
| 90 | adler += *buf++; |
95 | adler += *buf++; |
| 91 | sum2 += adler; |
96 | sum2 += adler; |
| 92 | } |
97 | } |
| 93 | if (adler >= BASE) |
98 | if (adler >= BASE) |
| 94 | adler -= BASE; |
99 | adler -= BASE; |
| 95 | MOD4(sum2); /* only added so many BASE's */ |
100 | MOD28(sum2); /* only added so many BASE's */ |
| 96 | return adler | (sum2 << 16); |
101 | return adler | (sum2 << 16); |
| 97 | } |
102 | } |
| Line 98... | Line 103... | ||
| 98 | 103 | ||
| 99 | /* do length NMAX blocks -- requires just one modulo operation */ |
104 | /* do length NMAX blocks -- requires just one modulo operation */ |
| Line 135... | Line 140... | ||
| 135 | { |
140 | { |
| 136 | unsigned long sum1; |
141 | unsigned long sum1; |
| 137 | unsigned long sum2; |
142 | unsigned long sum2; |
| 138 | unsigned rem; |
143 | unsigned rem; |
| Line -... | Line 144... | ||
| - | 144 | ||
| - | 145 | /* for negative len, return invalid adler32 as a clue for debugging */ |
|
| - | 146 | if (len2 < 0) |
|
| - | 147 | return 0xffffffffUL; |
|
| 139 | 148 | ||
| - | 149 | /* the derivation of this formula is left as an exercise for the reader */ |
|
| 140 | /* the derivation of this formula is left as an exercise for the reader */ |
150 | MOD63(len2); /* assumes len2 >= 0 */ |
| 141 | rem = (unsigned)(len2 % BASE); |
151 | rem = (unsigned)len2; |
| 142 | sum1 = adler1 & 0xffff; |
152 | sum1 = adler1 & 0xffff; |
| 143 | sum2 = rem * sum1; |
153 | sum2 = rem * sum1; |
| 144 | MOD(sum2); |
154 | MOD(sum2); |
| 145 | sum1 += (adler2 & 0xffff) + BASE - 1; |
155 | sum1 += (adler2 & 0xffff) + BASE - 1; |