|
1 /* |
|
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
|
3 * |
|
4 * This code is free software; you can redistribute it and/or modify it |
|
5 * under the terms of the GNU General Public License version 2 only, as |
|
6 * published by the Free Software Foundation. Oracle designates this |
|
7 * particular file as subject to the "Classpath" exception as provided |
|
8 * by Oracle in the LICENSE file that accompanied this code. |
|
9 * |
|
10 * This code is distributed in the hope that it will be useful, but WITHOUT |
|
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
13 * version 2 for more details (a copy is included in the LICENSE file that |
|
14 * accompanied this code). |
|
15 * |
|
16 * You should have received a copy of the GNU General Public License version |
|
17 * 2 along with this work; if not, write to the Free Software Foundation, |
|
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
19 * |
|
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
21 * or visit www.oracle.com if you need additional information or have any |
|
22 * questions. |
|
23 */ |
|
24 |
|
25 /* adler32.c -- compute the Adler-32 checksum of a data stream |
|
26 * Copyright (C) 1995-2007 Mark Adler |
|
27 * For conditions of distribution and use, see copyright notice in zlib.h |
|
28 */ |
|
29 |
|
30 /* @(#) $Id$ */ |
|
31 |
|
32 #include "zutil.h" |
|
33 |
|
34 #define local static |
|
35 |
|
36 local uLong adler32_combine_(uLong adler1, uLong adler2, z_off64_t len2); |
|
37 |
|
38 #define BASE 65521UL /* largest prime smaller than 65536 */ |
|
39 #define NMAX 5552 |
|
40 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ |
|
41 |
|
42 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} |
|
43 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); |
|
44 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); |
|
45 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); |
|
46 #define DO16(buf) DO8(buf,0); DO8(buf,8); |
|
47 |
|
48 /* use NO_DIVIDE if your processor does not do division in hardware */ |
|
49 #ifdef NO_DIVIDE |
|
50 # define MOD(a) \ |
|
51 do { \ |
|
52 if (a >= (BASE << 16)) a -= (BASE << 16); \ |
|
53 if (a >= (BASE << 15)) a -= (BASE << 15); \ |
|
54 if (a >= (BASE << 14)) a -= (BASE << 14); \ |
|
55 if (a >= (BASE << 13)) a -= (BASE << 13); \ |
|
56 if (a >= (BASE << 12)) a -= (BASE << 12); \ |
|
57 if (a >= (BASE << 11)) a -= (BASE << 11); \ |
|
58 if (a >= (BASE << 10)) a -= (BASE << 10); \ |
|
59 if (a >= (BASE << 9)) a -= (BASE << 9); \ |
|
60 if (a >= (BASE << 8)) a -= (BASE << 8); \ |
|
61 if (a >= (BASE << 7)) a -= (BASE << 7); \ |
|
62 if (a >= (BASE << 6)) a -= (BASE << 6); \ |
|
63 if (a >= (BASE << 5)) a -= (BASE << 5); \ |
|
64 if (a >= (BASE << 4)) a -= (BASE << 4); \ |
|
65 if (a >= (BASE << 3)) a -= (BASE << 3); \ |
|
66 if (a >= (BASE << 2)) a -= (BASE << 2); \ |
|
67 if (a >= (BASE << 1)) a -= (BASE << 1); \ |
|
68 if (a >= BASE) a -= BASE; \ |
|
69 } while (0) |
|
70 # define MOD4(a) \ |
|
71 do { \ |
|
72 if (a >= (BASE << 4)) a -= (BASE << 4); \ |
|
73 if (a >= (BASE << 3)) a -= (BASE << 3); \ |
|
74 if (a >= (BASE << 2)) a -= (BASE << 2); \ |
|
75 if (a >= (BASE << 1)) a -= (BASE << 1); \ |
|
76 if (a >= BASE) a -= BASE; \ |
|
77 } while (0) |
|
78 #else |
|
79 # define MOD(a) a %= BASE |
|
80 # define MOD4(a) a %= BASE |
|
81 #endif |
|
82 |
|
83 /* ========================================================================= */ |
|
84 uLong ZEXPORT adler32(adler, buf, len) |
|
85 uLong adler; |
|
86 const Bytef *buf; |
|
87 uInt len; |
|
88 { |
|
89 unsigned long sum2; |
|
90 unsigned n; |
|
91 |
|
92 /* split Adler-32 into component sums */ |
|
93 sum2 = (adler >> 16) & 0xffff; |
|
94 adler &= 0xffff; |
|
95 |
|
96 /* in case user likes doing a byte at a time, keep it fast */ |
|
97 if (len == 1) { |
|
98 adler += buf[0]; |
|
99 if (adler >= BASE) |
|
100 adler -= BASE; |
|
101 sum2 += adler; |
|
102 if (sum2 >= BASE) |
|
103 sum2 -= BASE; |
|
104 return adler | (sum2 << 16); |
|
105 } |
|
106 |
|
107 /* initial Adler-32 value (deferred check for len == 1 speed) */ |
|
108 if (buf == Z_NULL) |
|
109 return 1L; |
|
110 |
|
111 /* in case short lengths are provided, keep it somewhat fast */ |
|
112 if (len < 16) { |
|
113 while (len--) { |
|
114 adler += *buf++; |
|
115 sum2 += adler; |
|
116 } |
|
117 if (adler >= BASE) |
|
118 adler -= BASE; |
|
119 MOD4(sum2); /* only added so many BASE's */ |
|
120 return adler | (sum2 << 16); |
|
121 } |
|
122 |
|
123 /* do length NMAX blocks -- requires just one modulo operation */ |
|
124 while (len >= NMAX) { |
|
125 len -= NMAX; |
|
126 n = NMAX / 16; /* NMAX is divisible by 16 */ |
|
127 do { |
|
128 DO16(buf); /* 16 sums unrolled */ |
|
129 buf += 16; |
|
130 } while (--n); |
|
131 MOD(adler); |
|
132 MOD(sum2); |
|
133 } |
|
134 |
|
135 /* do remaining bytes (less than NMAX, still just one modulo) */ |
|
136 if (len) { /* avoid modulos if none remaining */ |
|
137 while (len >= 16) { |
|
138 len -= 16; |
|
139 DO16(buf); |
|
140 buf += 16; |
|
141 } |
|
142 while (len--) { |
|
143 adler += *buf++; |
|
144 sum2 += adler; |
|
145 } |
|
146 MOD(adler); |
|
147 MOD(sum2); |
|
148 } |
|
149 |
|
150 /* return recombined sums */ |
|
151 return adler | (sum2 << 16); |
|
152 } |
|
153 |
|
154 /* ========================================================================= */ |
|
155 local uLong adler32_combine_(adler1, adler2, len2) |
|
156 uLong adler1; |
|
157 uLong adler2; |
|
158 z_off64_t len2; |
|
159 { |
|
160 unsigned long sum1; |
|
161 unsigned long sum2; |
|
162 unsigned rem; |
|
163 |
|
164 /* the derivation of this formula is left as an exercise for the reader */ |
|
165 rem = (unsigned)(len2 % BASE); |
|
166 sum1 = adler1 & 0xffff; |
|
167 sum2 = rem * sum1; |
|
168 MOD(sum2); |
|
169 sum1 += (adler2 & 0xffff) + BASE - 1; |
|
170 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; |
|
171 if (sum1 >= BASE) sum1 -= BASE; |
|
172 if (sum1 >= BASE) sum1 -= BASE; |
|
173 if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1); |
|
174 if (sum2 >= BASE) sum2 -= BASE; |
|
175 return sum1 | (sum2 << 16); |
|
176 } |
|
177 |
|
178 /* ========================================================================= */ |
|
179 uLong ZEXPORT adler32_combine(adler1, adler2, len2) |
|
180 uLong adler1; |
|
181 uLong adler2; |
|
182 z_off_t len2; |
|
183 { |
|
184 return adler32_combine_(adler1, adler2, len2); |
|
185 } |
|
186 |
|
187 uLong ZEXPORT adler32_combine64(adler1, adler2, len2) |
|
188 uLong adler1; |
|
189 uLong adler2; |
|
190 z_off64_t len2; |
|
191 { |
|
192 return adler32_combine_(adler1, adler2, len2); |
|
193 } |