OLD | NEW |
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-2011 Mark Adler | 2 * Copyright (C) 1995-2007 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 */ |
5 | 5 |
6 /* @(#) $Id$ */ | 6 /* @(#) $Id$ */ |
7 | 7 |
8 #include "zutil.h" | 8 #include "zutil.h" |
9 | 9 |
10 #define local static | 10 #define local static |
11 | 11 |
12 local uLong adler32_combine_ OF((uLong adler1, uLong adler2, z_off64_t len2)); | 12 local uLong adler32_combine_(uLong adler1, uLong adler2, z_off64_t len2); |
13 | 13 |
14 #define BASE 65521 /* largest prime smaller than 65536 */ | 14 #define BASE 65521UL /* 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 */ |
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); | 19 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); |
20 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); | 20 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); |
21 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); | 21 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); |
22 #define DO16(buf) DO8(buf,0); DO8(buf,8); | 22 #define DO16(buf) DO8(buf,0); DO8(buf,8); |
23 | 23 |
24 /* use NO_DIVIDE if your processor does not do division in hardware -- | 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 | 25 #ifdef NO_DIVIDE |
27 /* note that this assumes BASE is 65521, where 65536 % 65521 == 15 | 26 # define MOD(a) \ |
28 (thank you to John Reiser for pointing this out) */ | |
29 # define CHOP(a) \ | |
30 do { \ | 27 do { \ |
31 unsigned long tmp = a >> 16; \ | 28 if (a >= (BASE << 16)) a -= (BASE << 16); \ |
32 a &= 0xffffUL; \ | 29 if (a >= (BASE << 15)) a -= (BASE << 15); \ |
33 a += (tmp << 4) - tmp; \ | 30 if (a >= (BASE << 14)) a -= (BASE << 14); \ |
34 } while (0) | 31 if (a >= (BASE << 13)) a -= (BASE << 13); \ |
35 # define MOD28(a) \ | 32 if (a >= (BASE << 12)) a -= (BASE << 12); \ |
36 do { \ | 33 if (a >= (BASE << 11)) a -= (BASE << 11); \ |
37 CHOP(a); \ | 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); \ |
| 38 if (a >= (BASE << 6)) a -= (BASE << 6); \ |
| 39 if (a >= (BASE << 5)) a -= (BASE << 5); \ |
| 40 if (a >= (BASE << 4)) a -= (BASE << 4); \ |
| 41 if (a >= (BASE << 3)) a -= (BASE << 3); \ |
| 42 if (a >= (BASE << 2)) a -= (BASE << 2); \ |
| 43 if (a >= (BASE << 1)) a -= (BASE << 1); \ |
38 if (a >= BASE) a -= BASE; \ | 44 if (a >= BASE) a -= BASE; \ |
39 } while (0) | 45 } while (0) |
40 # define MOD(a) \ | 46 # define MOD4(a) \ |
41 do { \ | 47 do { \ |
42 CHOP(a); \ | 48 if (a >= (BASE << 4)) a -= (BASE << 4); \ |
43 MOD28(a); \ | 49 if (a >= (BASE << 3)) a -= (BASE << 3); \ |
44 } while (0) | 50 if (a >= (BASE << 2)) a -= (BASE << 2); \ |
45 # define MOD63(a) \ | 51 if (a >= (BASE << 1)) a -= (BASE << 1); \ |
46 do { /* this assumes a is not negative */ \ | |
47 z_off64_t tmp = a >> 32; \ | |
48 a &= 0xffffffffL; \ | |
49 a += (tmp << 8) - (tmp << 5) + tmp; \ | |
50 tmp = a >> 16; \ | |
51 a &= 0xffffL; \ | |
52 a += (tmp << 4) - tmp; \ | |
53 tmp = a >> 16; \ | |
54 a &= 0xffffL; \ | |
55 a += (tmp << 4) - tmp; \ | |
56 if (a >= BASE) a -= BASE; \ | 52 if (a >= BASE) a -= BASE; \ |
57 } while (0) | 53 } while (0) |
58 #else | 54 #else |
59 # define MOD(a) a %= BASE | 55 # define MOD(a) a %= BASE |
60 # define MOD28(a) a %= BASE | 56 # define MOD4(a) a %= BASE |
61 # define MOD63(a) a %= BASE | |
62 #endif | 57 #endif |
63 | 58 |
64 /* ========================================================================= */ | 59 /* ========================================================================= */ |
65 uLong ZEXPORT adler32(adler, buf, len) | 60 uLong ZEXPORT adler32(adler, buf, len) |
66 uLong adler; | 61 uLong adler; |
67 const Bytef *buf; | 62 const Bytef *buf; |
68 uInt len; | 63 uInt len; |
69 { | 64 { |
70 unsigned long sum2; | 65 unsigned long sum2; |
71 unsigned n; | 66 unsigned n; |
(...skipping 18 matching lines...) Expand all Loading... |
90 return 1L; | 85 return 1L; |
91 | 86 |
92 /* in case short lengths are provided, keep it somewhat fast */ | 87 /* in case short lengths are provided, keep it somewhat fast */ |
93 if (len < 16) { | 88 if (len < 16) { |
94 while (len--) { | 89 while (len--) { |
95 adler += *buf++; | 90 adler += *buf++; |
96 sum2 += adler; | 91 sum2 += adler; |
97 } | 92 } |
98 if (adler >= BASE) | 93 if (adler >= BASE) |
99 adler -= BASE; | 94 adler -= BASE; |
100 MOD28(sum2); /* only added so many BASE's */ | 95 MOD4(sum2); /* only added so many BASE's */ |
101 return adler | (sum2 << 16); | 96 return adler | (sum2 << 16); |
102 } | 97 } |
103 | 98 |
104 /* do length NMAX blocks -- requires just one modulo operation */ | 99 /* do length NMAX blocks -- requires just one modulo operation */ |
105 while (len >= NMAX) { | 100 while (len >= NMAX) { |
106 len -= NMAX; | 101 len -= NMAX; |
107 n = NMAX / 16; /* NMAX is divisible by 16 */ | 102 n = NMAX / 16; /* NMAX is divisible by 16 */ |
108 do { | 103 do { |
109 DO16(buf); /* 16 sums unrolled */ | 104 DO16(buf); /* 16 sums unrolled */ |
110 buf += 16; | 105 buf += 16; |
(...skipping 24 matching lines...) Expand all Loading... |
135 /* ========================================================================= */ | 130 /* ========================================================================= */ |
136 local uLong adler32_combine_(adler1, adler2, len2) | 131 local uLong adler32_combine_(adler1, adler2, len2) |
137 uLong adler1; | 132 uLong adler1; |
138 uLong adler2; | 133 uLong adler2; |
139 z_off64_t len2; | 134 z_off64_t len2; |
140 { | 135 { |
141 unsigned long sum1; | 136 unsigned long sum1; |
142 unsigned long sum2; | 137 unsigned long sum2; |
143 unsigned rem; | 138 unsigned rem; |
144 | 139 |
145 /* for negative len, return invalid adler32 as a clue for debugging */ | |
146 if (len2 < 0) | |
147 return 0xffffffffUL; | |
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; | |
152 sum1 = adler1 & 0xffff; | 142 sum1 = adler1 & 0xffff; |
153 sum2 = rem * sum1; | 143 sum2 = rem * sum1; |
154 MOD(sum2); | 144 MOD(sum2); |
155 sum1 += (adler2 & 0xffff) + BASE - 1; | 145 sum1 += (adler2 & 0xffff) + BASE - 1; |
156 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; | 146 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; |
157 if (sum1 >= BASE) sum1 -= BASE; | 147 if (sum1 >= BASE) sum1 -= BASE; |
158 if (sum1 >= BASE) sum1 -= BASE; | 148 if (sum1 >= BASE) sum1 -= BASE; |
159 if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1); | 149 if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1); |
160 if (sum2 >= BASE) sum2 -= BASE; | 150 if (sum2 >= BASE) sum2 -= BASE; |
161 return sum1 | (sum2 << 16); | 151 return sum1 | (sum2 << 16); |
162 } | 152 } |
163 | 153 |
164 /* ========================================================================= */ | 154 /* ========================================================================= */ |
165 uLong ZEXPORT adler32_combine(adler1, adler2, len2) | 155 uLong ZEXPORT adler32_combine(adler1, adler2, len2) |
166 uLong adler1; | 156 uLong adler1; |
167 uLong adler2; | 157 uLong adler2; |
168 z_off_t len2; | 158 z_off_t len2; |
169 { | 159 { |
170 return adler32_combine_(adler1, adler2, len2); | 160 return adler32_combine_(adler1, adler2, len2); |
171 } | 161 } |
172 | 162 |
173 uLong ZEXPORT adler32_combine64(adler1, adler2, len2) | 163 uLong ZEXPORT adler32_combine64(adler1, adler2, len2) |
174 uLong adler1; | 164 uLong adler1; |
175 uLong adler2; | 165 uLong adler2; |
176 z_off64_t len2; | 166 z_off64_t len2; |
177 { | 167 { |
178 return adler32_combine_(adler1, adler2, len2); | 168 return adler32_combine_(adler1, adler2, len2); |
179 } | 169 } |
OLD | NEW |