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