Annotation of embedaddon/rsync/zlib/adler32.c, revision 1.1.1.2
1.1 misho 1: /* adler32.c -- compute the Adler-32 checksum of a data stream
1.1.1.2 ! misho 2: * Copyright (C) 1995-2011 Mark Adler
1.1 misho 3: * For conditions of distribution and use, see copyright notice in zlib.h
4: */
5:
6: /* @(#) $Id$ */
7:
1.1.1.2 ! misho 8: #include "zutil.h"
1.1 misho 9:
1.1.1.2 ! misho 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 */
1.1 misho 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:
1.1.1.2 ! misho 24: /* use NO_DIVIDE if your processor does not do division in hardware --
! 25: try it both ways to see which is faster */
1.1 misho 26: #ifdef NO_DIVIDE
1.1.1.2 ! misho 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) \
1.1 misho 30: do { \
1.1.1.2 ! misho 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); \
1.1 misho 38: if (a >= BASE) a -= BASE; \
39: } while (0)
1.1.1.2 ! misho 40: # define MOD(a) \
1.1 misho 41: do { \
1.1.1.2 ! misho 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; \
1.1 misho 56: if (a >= BASE) a -= BASE; \
57: } while (0)
58: #else
59: # define MOD(a) a %= BASE
1.1.1.2 ! misho 60: # define MOD28(a) a %= BASE
! 61: # define MOD63(a) a %= BASE
1.1 misho 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;
1.1.1.2 ! misho 100: MOD28(sum2); /* only added so many BASE's */
1.1 misho 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: /* ========================================================================= */
1.1.1.2 ! misho 136: local uLong adler32_combine_(adler1, adler2, len2)
1.1 misho 137: uLong adler1;
138: uLong adler2;
1.1.1.2 ! misho 139: z_off64_t len2;
1.1 misho 140: {
141: unsigned long sum1;
142: unsigned long sum2;
143: unsigned rem;
144:
1.1.1.2 ! misho 145: /* for negative len, return invalid adler32 as a clue for debugging */
! 146: if (len2 < 0)
! 147: return 0xffffffffUL;
! 148:
1.1 misho 149: /* the derivation of this formula is left as an exercise for the reader */
1.1.1.2 ! misho 150: MOD63(len2); /* assumes len2 >= 0 */
! 151: rem = (unsigned)len2;
1.1 misho 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;
1.1.1.2 ! misho 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;
1.1 misho 161: return sum1 | (sum2 << 16);
162: }
1.1.1.2 ! misho 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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to adler32.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync / zlib