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}