1e89516f0SMike Frysinger /* adler32.c -- compute the Adler-32 checksum of a data stream
2e89516f0SMike Frysinger * Copyright (C) 1995-2004 Mark Adler
3e89516f0SMike Frysinger * For conditions of distribution and use, see copyright notice in zlib.h
4e89516f0SMike Frysinger */
5e89516f0SMike Frysinger
6e89516f0SMike Frysinger /* @(#) $Id$ */
7e89516f0SMike Frysinger
8e89516f0SMike Frysinger #define ZLIB_INTERNAL
9e89516f0SMike Frysinger #include "zlib.h"
10e89516f0SMike Frysinger
11e89516f0SMike Frysinger #define BASE 65521UL /* largest prime smaller than 65536 */
12e89516f0SMike Frysinger #define NMAX 5552
13e89516f0SMike Frysinger /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
14e89516f0SMike Frysinger
15e89516f0SMike Frysinger #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
16e89516f0SMike Frysinger #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
17e89516f0SMike Frysinger #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
18e89516f0SMike Frysinger #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
19e89516f0SMike Frysinger #define DO16(buf) DO8(buf,0); DO8(buf,8);
20e89516f0SMike Frysinger
21e89516f0SMike Frysinger /* use NO_DIVIDE if your processor does not do division in hardware */
22e89516f0SMike Frysinger #ifdef NO_DIVIDE
23e89516f0SMike Frysinger # define MOD(a) \
24e89516f0SMike Frysinger do { \
25e89516f0SMike Frysinger if (a >= (BASE << 16)) a -= (BASE << 16); \
26e89516f0SMike Frysinger if (a >= (BASE << 15)) a -= (BASE << 15); \
27e89516f0SMike Frysinger if (a >= (BASE << 14)) a -= (BASE << 14); \
28e89516f0SMike Frysinger if (a >= (BASE << 13)) a -= (BASE << 13); \
29e89516f0SMike Frysinger if (a >= (BASE << 12)) a -= (BASE << 12); \
30e89516f0SMike Frysinger if (a >= (BASE << 11)) a -= (BASE << 11); \
31e89516f0SMike Frysinger if (a >= (BASE << 10)) a -= (BASE << 10); \
32e89516f0SMike Frysinger if (a >= (BASE << 9)) a -= (BASE << 9); \
33e89516f0SMike Frysinger if (a >= (BASE << 8)) a -= (BASE << 8); \
34e89516f0SMike Frysinger if (a >= (BASE << 7)) a -= (BASE << 7); \
35e89516f0SMike Frysinger if (a >= (BASE << 6)) a -= (BASE << 6); \
36e89516f0SMike Frysinger if (a >= (BASE << 5)) a -= (BASE << 5); \
37e89516f0SMike Frysinger if (a >= (BASE << 4)) a -= (BASE << 4); \
38e89516f0SMike Frysinger if (a >= (BASE << 3)) a -= (BASE << 3); \
39e89516f0SMike Frysinger if (a >= (BASE << 2)) a -= (BASE << 2); \
40e89516f0SMike Frysinger if (a >= (BASE << 1)) a -= (BASE << 1); \
41e89516f0SMike Frysinger if (a >= BASE) a -= BASE; \
42e89516f0SMike Frysinger } while (0)
43e89516f0SMike Frysinger # define MOD4(a) \
44e89516f0SMike Frysinger do { \
45e89516f0SMike Frysinger if (a >= (BASE << 4)) a -= (BASE << 4); \
46e89516f0SMike Frysinger if (a >= (BASE << 3)) a -= (BASE << 3); \
47e89516f0SMike Frysinger if (a >= (BASE << 2)) a -= (BASE << 2); \
48e89516f0SMike Frysinger if (a >= (BASE << 1)) a -= (BASE << 1); \
49e89516f0SMike Frysinger if (a >= BASE) a -= BASE; \
50e89516f0SMike Frysinger } while (0)
51e89516f0SMike Frysinger #else
52e89516f0SMike Frysinger # define MOD(a) a %= BASE
53e89516f0SMike Frysinger # define MOD4(a) a %= BASE
54e89516f0SMike Frysinger #endif
55e89516f0SMike Frysinger
56e89516f0SMike Frysinger /* ========================================================================= */
adler32(uLong adler,const Bytef * buf,uInt len)57*ee820b5eSKim Phillips uLong ZEXPORT adler32(uLong adler, const Bytef *buf, uInt len)
58e89516f0SMike Frysinger {
59e89516f0SMike Frysinger unsigned long sum2;
60e89516f0SMike Frysinger unsigned n;
61e89516f0SMike Frysinger
62e89516f0SMike Frysinger /* split Adler-32 into component sums */
63e89516f0SMike Frysinger sum2 = (adler >> 16) & 0xffff;
64e89516f0SMike Frysinger adler &= 0xffff;
65e89516f0SMike Frysinger
66e89516f0SMike Frysinger /* in case user likes doing a byte at a time, keep it fast */
67e89516f0SMike Frysinger if (len == 1) {
68e89516f0SMike Frysinger adler += buf[0];
69e89516f0SMike Frysinger if (adler >= BASE)
70e89516f0SMike Frysinger adler -= BASE;
71e89516f0SMike Frysinger sum2 += adler;
72e89516f0SMike Frysinger if (sum2 >= BASE)
73e89516f0SMike Frysinger sum2 -= BASE;
74e89516f0SMike Frysinger return adler | (sum2 << 16);
75e89516f0SMike Frysinger }
76e89516f0SMike Frysinger
77e89516f0SMike Frysinger /* initial Adler-32 value (deferred check for len == 1 speed) */
78e89516f0SMike Frysinger if (buf == Z_NULL)
79e89516f0SMike Frysinger return 1L;
80e89516f0SMike Frysinger
81e89516f0SMike Frysinger /* in case short lengths are provided, keep it somewhat fast */
82e89516f0SMike Frysinger if (len < 16) {
83e89516f0SMike Frysinger while (len--) {
84e89516f0SMike Frysinger adler += *buf++;
85e89516f0SMike Frysinger sum2 += adler;
86e89516f0SMike Frysinger }
87e89516f0SMike Frysinger if (adler >= BASE)
88e89516f0SMike Frysinger adler -= BASE;
89e89516f0SMike Frysinger MOD4(sum2); /* only added so many BASE's */
90e89516f0SMike Frysinger return adler | (sum2 << 16);
91e89516f0SMike Frysinger }
92e89516f0SMike Frysinger
93e89516f0SMike Frysinger /* do length NMAX blocks -- requires just one modulo operation */
94e89516f0SMike Frysinger while (len >= NMAX) {
95e89516f0SMike Frysinger len -= NMAX;
96e89516f0SMike Frysinger n = NMAX / 16; /* NMAX is divisible by 16 */
97e89516f0SMike Frysinger do {
98e89516f0SMike Frysinger DO16(buf); /* 16 sums unrolled */
99e89516f0SMike Frysinger buf += 16;
100e89516f0SMike Frysinger } while (--n);
101e89516f0SMike Frysinger MOD(adler);
102e89516f0SMike Frysinger MOD(sum2);
103e89516f0SMike Frysinger }
104e89516f0SMike Frysinger
105e89516f0SMike Frysinger /* do remaining bytes (less than NMAX, still just one modulo) */
106e89516f0SMike Frysinger if (len) { /* avoid modulos if none remaining */
107e89516f0SMike Frysinger while (len >= 16) {
108e89516f0SMike Frysinger len -= 16;
109e89516f0SMike Frysinger DO16(buf);
110e89516f0SMike Frysinger buf += 16;
111e89516f0SMike Frysinger }
112e89516f0SMike Frysinger while (len--) {
113e89516f0SMike Frysinger adler += *buf++;
114e89516f0SMike Frysinger sum2 += adler;
115e89516f0SMike Frysinger }
116e89516f0SMike Frysinger MOD(adler);
117e89516f0SMike Frysinger MOD(sum2);
118e89516f0SMike Frysinger }
119e89516f0SMike Frysinger
120e89516f0SMike Frysinger /* return recombined sums */
121e89516f0SMike Frysinger return adler | (sum2 << 16);
122e89516f0SMike Frysinger }
123