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-2011, 2016 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 local uLong adler32_combine_ OF((uLong adler1, uLong adler2, z_off64_t len2));
35
36 #define BASE 65521U /* largest prime smaller than 65536 */
37 #define NMAX 5552
38 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
39
40 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
41 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
42 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
43 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
44 #define DO16(buf) DO8(buf,0); DO8(buf,8);
45
46 /* use NO_DIVIDE if your processor does not do division in hardware --
47 try it both ways to see which is faster */
48 #ifdef NO_DIVIDE
49 /* note that this assumes BASE is 65521, where 65536 % 65521 == 15
50 (thank you to John Reiser for pointing this out) */
51 # define CHOP(a) \
52 do { \
53 unsigned long tmp = a >> 16; \
54 a &= 0xffffUL; \
55 a += (tmp << 4) - tmp; \
56 } while (0)
57 # define MOD28(a) \
58 do { \
59 CHOP(a); \
60 if (a >= BASE) a -= BASE; \
61 } while (0)
62 # define MOD(a) \
63 do { \
64 CHOP(a); \
65 MOD28(a); \
66 } while (0)
67 # define MOD63(a) \
68 do { /* this assumes a is not negative */ \
69 z_off64_t tmp = a >> 32; \
70 a &= 0xffffffffL; \
71 a += (tmp << 8) - (tmp << 5) + tmp; \
72 tmp = a >> 16; \
73 a &= 0xffffL; \
74 a += (tmp << 4) - tmp; \
75 tmp = a >> 16; \
76 a &= 0xffffL; \
77 a += (tmp << 4) - tmp; \
78 if (a >= BASE) a -= BASE; \
79 } while (0)
80 #else
81 # define MOD(a) a %= BASE
82 # define MOD28(a) a %= BASE
83 # define MOD63(a) a %= BASE
84 #endif
85
86 /* ========================================================================= */
87 uLong ZEXPORT adler32_z(adler, buf, len)
88 uLong adler;
89 const Bytef *buf;
90 z_size_t len;
91 {
92 unsigned long sum2;
93 unsigned n;
94
95 /* split Adler-32 into component sums */
96 sum2 = (adler >> 16) & 0xffff;
97 adler &= 0xffff;
98
99 /* in case user likes doing a byte at a time, keep it fast */
100 if (len == 1) {
101 adler += buf[0];
102 if (adler >= BASE)
103 adler -= BASE;
104 sum2 += adler;
105 if (sum2 >= BASE)
106 sum2 -= BASE;
107 return adler | (sum2 << 16);
108 }
109
110 /* initial Adler-32 value (deferred check for len == 1 speed) */
111 if (buf == Z_NULL)
112 return 1L;
113
114 /* in case short lengths are provided, keep it somewhat fast */
115 if (len < 16) {
116 while (len--) {
117 adler += *buf++;
118 sum2 += adler;
119 }
120 if (adler >= BASE)
121 adler -= BASE;
122 MOD28(sum2); /* only added so many BASE's */
123 return adler | (sum2 << 16);
124 }
125
126 /* do length NMAX blocks -- requires just one modulo operation */
127 while (len >= NMAX) {
128 len -= NMAX;
129 n = NMAX / 16; /* NMAX is divisible by 16 */
130 do {
131 DO16(buf); /* 16 sums unrolled */
132 buf += 16;
133 } while (--n);
134 MOD(adler);
135 MOD(sum2);
136 }
137
138 /* do remaining bytes (less than NMAX, still just one modulo) */
139 if (len) { /* avoid modulos if none remaining */
140 while (len >= 16) {
141 len -= 16;
142 DO16(buf);
143 buf += 16;
144 }
145 while (len--) {
146 adler += *buf++;
147 sum2 += adler;
148 }
149 MOD(adler);
150 MOD(sum2);
151 }
152
153 /* return recombined sums */
154 return adler | (sum2 << 16);
155 }
156
157 /* ========================================================================= */
158 uLong ZEXPORT adler32(adler, buf, len)
159 uLong adler;
160 const Bytef *buf;
161 uInt len;
162 {
163 return adler32_z(adler, buf, len);
164 }
165
166 /* ========================================================================= */
167 local uLong adler32_combine_(adler1, adler2, len2)
168 uLong adler1;
169 uLong adler2;
170 z_off64_t len2;
171 {
172 unsigned long sum1;
173 unsigned long sum2;
174 unsigned rem;
175
176 /* for negative len, return invalid adler32 as a clue for debugging */
177 if (len2 < 0)
178 return 0xffffffffUL;
179
180 /* the derivation of this formula is left as an exercise for the reader */
181 MOD63(len2); /* assumes len2 >= 0 */
182 rem = (unsigned)len2;
183 sum1 = adler1 & 0xffff;
184 sum2 = rem * sum1;
185 MOD(sum2);
186 sum1 += (adler2 & 0xffff) + BASE - 1;
187 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
188 if (sum1 >= BASE) sum1 -= BASE;
189 if (sum1 >= BASE) sum1 -= BASE;
190 if (sum2 >= ((unsigned long)BASE << 1)) sum2 -= ((unsigned long)BASE << 1);
191 if (sum2 >= BASE) sum2 -= BASE;
192 return sum1 | (sum2 << 16);
193 }
194
195 /* ========================================================================= */
196 uLong ZEXPORT adler32_combine(adler1, adler2, len2)
197 uLong adler1;
198 uLong adler2;
199 z_off_t len2;
200 {
201 return adler32_combine_(adler1, adler2, len2);
202 }
203
204 uLong ZEXPORT adler32_combine64(adler1, adler2, len2)
205 uLong adler1;
206 uLong adler2;
207 z_off64_t len2;
208 {
209 return adler32_combine_(adler1, adler2, len2);
210 }