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 }