File:
[ELWIX - Embedded LightWeight unIX -] /
embedaddon /
sudo /
zlib /
adler32.c
Revision
1.1.1.2 (vendor branch):
download - view:
text,
annotated -
select for diffs -
revision graph
Mon Jul 22 10:46:14 2013 UTC (11 years, 1 month ago) by
misho
Branches:
sudo,
MAIN
CVS tags:
v1_8_8p0,
v1_8_8,
v1_8_7p0,
v1_8_7,
v1_8_5p1,
v1_8_10p3_0,
v1_8_10p3,
HEAD
1.8.7
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: adler32.c,v 1.1.1.2 2013/07/22 10:46:14 misho Exp $ */
7:
8: #include "zutil.h"
9:
10: #define local static
11:
12: local 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: /* ========================================================================= */
65: uLong 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: /* ========================================================================= */
136: local 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: /* ========================================================================= */
165: uLong 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:
173: uLong 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: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>