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