1/* adler32.c -- compute the Adler-32 checksum of a data stream
2 * Copyright (C) 1995-2004 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */
5
6/* @(#) $Id$ */
7
8#define ZLIB_INTERNAL
9#include "zlib.h"
10
11#define BASE 65521UL    /* largest prime smaller than 65536 */
12#define NMAX 5552
13/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
14
15#define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
16#define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
17#define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
18#define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
19#define DO16(buf)   DO8(buf,0); DO8(buf,8);
20
21/* use NO_DIVIDE if your processor does not do division in hardware */
22#ifdef NO_DIVIDE
23#  define MOD(a) \
24    do { \
25        if (a >= (BASE << 16)) a -= (BASE << 16); \
26        if (a >= (BASE << 15)) a -= (BASE << 15); \
27        if (a >= (BASE << 14)) a -= (BASE << 14); \
28        if (a >= (BASE << 13)) a -= (BASE << 13); \
29        if (a >= (BASE << 12)) a -= (BASE << 12); \
30        if (a >= (BASE << 11)) a -= (BASE << 11); \
31        if (a >= (BASE << 10)) a -= (BASE << 10); \
32        if (a >= (BASE << 9)) a -= (BASE << 9); \
33        if (a >= (BASE << 8)) a -= (BASE << 8); \
34        if (a >= (BASE << 7)) a -= (BASE << 7); \
35        if (a >= (BASE << 6)) a -= (BASE << 6); \
36        if (a >= (BASE << 5)) a -= (BASE << 5); \
37        if (a >= (BASE << 4)) a -= (BASE << 4); \
38        if (a >= (BASE << 3)) a -= (BASE << 3); \
39        if (a >= (BASE << 2)) a -= (BASE << 2); \
40        if (a >= (BASE << 1)) a -= (BASE << 1); \
41        if (a >= BASE) a -= BASE; \
42    } while (0)
43#  define MOD4(a) \
44    do { \
45        if (a >= (BASE << 4)) a -= (BASE << 4); \
46        if (a >= (BASE << 3)) a -= (BASE << 3); \
47        if (a >= (BASE << 2)) a -= (BASE << 2); \
48        if (a >= (BASE << 1)) a -= (BASE << 1); \
49        if (a >= BASE) a -= BASE; \
50    } while (0)
51#else
52#  define MOD(a) a %= BASE
53#  define MOD4(a) a %= BASE
54#endif
55
56/* ========================================================================= */
57
58/*
59   The adler32 code below computes, in effect,
60
61   uLong high = 0;
62   uLong low  = 1;
63   for (j = 0; j < len; j++) {
64     low  = (low  + buf[j]) % BASE;
65     high = (high + low) % BASE;
66   }
67   checksum = (high << 16) | low;
68
69   Both 16-bit halves of the checksum are between 0 and BASE-1 (inclusive).
70   Hence, the minimum possible checksum value is 0, and the maximum is
71   ((BASE-1) << 16) | (BASE-1).  Applications may have reserved values
72   outside this range to carry special meanings.
73
74   NOTE: If adler32() is changed in ANY way, be absolutely sure that the
75   change will NOT cause checksums previously stored to not match the data
76   they were originally intended to match, or expand the range in such a
77   way that values reserved by applications to carry special meanings now
78   become checksums of valid data.  Also, be sure to change adler32_range()
79   accordingly.
80
81   This explanation and adler32_range() are not part of original software
82   distribution.  They are added at Google (2006) in accordance with the
83   copyright notice in zlib.h, which permits alteration and redistribution
84   of the original software provided, among other things, that altered
85   source versions must be plainly marked as such and not misrepresented as
86   being the original software.
87*/
88
89void ZEXPORT adler32_range(min, max)
90    uLong *min;
91    uLong *max;
92{
93    *min = 0L;
94    *max = ((BASE-1) << 16) | (BASE-1);
95}
96
97uLong ZEXPORT adler32(adler, buf, len)
98    uLong adler;
99    const Bytef *buf;
100    uInt len;
101{
102    unsigned long sum2;
103    unsigned n;
104
105    /* split Adler-32 into component sums */
106    sum2 = (adler >> 16) & 0xffff;
107    adler &= 0xffff;
108
109    /* in case user likes doing a byte at a time, keep it fast */
110    if (len == 1) {
111        adler += buf[0];
112        if (adler >= BASE)
113            adler -= BASE;
114        sum2 += adler;
115        if (sum2 >= BASE)
116            sum2 -= BASE;
117        return adler | (sum2 << 16);
118    }
119
120    /* initial Adler-32 value (deferred check for len == 1 speed) */
121    if (buf == Z_NULL)
122        return 1L;
123
124    /* in case short lengths are provided, keep it somewhat fast */
125    if (len < 16) {
126        while (len--) {
127            adler += *buf++;
128            sum2 += adler;
129        }
130        if (adler >= BASE)
131            adler -= BASE;
132        MOD4(sum2);             /* only added so many BASE's */
133        return adler | (sum2 << 16);
134    }
135
136    /* do length NMAX blocks -- requires just one modulo operation */
137    while (len >= NMAX) {
138        len -= NMAX;
139        n = NMAX / 16;          /* NMAX is divisible by 16 */
140        do {
141            DO16(buf);          /* 16 sums unrolled */
142            buf += 16;
143        } while (--n);
144        MOD(adler);
145        MOD(sum2);
146    }
147
148    /* do remaining bytes (less than NMAX, still just one modulo) */
149    if (len) {                  /* avoid modulos if none remaining */
150        while (len >= 16) {
151            len -= 16;
152            DO16(buf);
153            buf += 16;
154        }
155        while (len--) {
156            adler += *buf++;
157            sum2 += adler;
158        }
159        MOD(adler);
160        MOD(sum2);
161    }
162
163    /* return recombined sums */
164    return adler | (sum2 << 16);
165}
166
167/* ========================================================================= */
168uLong ZEXPORT adler32_combine(adler1, adler2, len2)
169    uLong adler1;
170    uLong adler2;
171    z_off_t len2;
172{
173    unsigned long sum1;
174    unsigned long sum2;
175    unsigned rem;
176
177    /* the derivation of this formula is left as an exercise for the reader */
178    rem = (unsigned)(len2 % BASE);
179    sum1 = adler1 & 0xffff;
180    sum2 = rem * sum1;
181    MOD(sum2);
182    sum1 += (adler2 & 0xffff) + BASE - 1;
183    sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
184    if (sum1 >= BASE) sum1 -= BASE;
185    if (sum1 >= BASE) sum1 -= BASE;
186    if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1);
187    if (sum2 >= BASE) sum2 -= BASE;
188    return sum1 | (sum2 << 16);
189}
190