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
34local 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/* ========================================================================= */
87uLong 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/* ========================================================================= */
158uLong 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/* ========================================================================= */
167local 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/* ========================================================================= */
196uLong 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
204uLong 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}
211