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; |