Rev 1896 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1896 | serge | 1 | /* adler32.c -- compute the Adler-32 checksum of a data stream |
3926 | Serge | 2 | * Copyright (C) 1995-2011 Mark Adler |
1896 | serge | 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 | |||
3926 | Serge | 12 | local uLong adler32_combine_ OF((uLong adler1, uLong adler2, z_off64_t len2)); |
1896 | serge | 13 | |
3926 | Serge | 14 | #define BASE 65521 /* largest prime smaller than 65536 */ |
1896 | serge | 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 | |||
3926 | Serge | 24 | /* use NO_DIVIDE if your processor does not do division in hardware -- |
25 | try it both ways to see which is faster */ |
||
1896 | serge | 26 | #ifdef NO_DIVIDE |
3926 | Serge | 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) \ |
||
1896 | serge | 30 | do { \ |
3926 | Serge | 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); \ |
||
1896 | serge | 38 | if (a >= BASE) a -= BASE; \ |
39 | } while (0) |
||
3926 | Serge | 40 | # define MOD(a) \ |
1896 | serge | 41 | do { \ |
3926 | Serge | 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; \ |
||
1896 | serge | 56 | if (a >= BASE) a -= BASE; \ |
57 | } while (0) |
||
58 | #else |
||
59 | # define MOD(a) a %= BASE |
||
3926 | Serge | 60 | # define MOD28(a) a %= BASE |
61 | # define MOD63(a) a %= BASE |
||
1896 | serge | 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; |
||
3926 | Serge | 100 | MOD28(sum2); /* only added so many BASE's */ |
1896 | serge | 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 | |||
3926 | Serge | 145 | /* for negative len, return invalid adler32 as a clue for debugging */ |
146 | if (len2 < 0) |
||
147 | return 0xffffffffUL; |
||
148 | |||
1896 | serge | 149 | /* the derivation of this formula is left as an exercise for the reader */ |
3926 | Serge | 150 | MOD63(len2); /* assumes len2 >= 0 */ |
151 | rem = (unsigned)len2; |
||
1896 | serge | 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 | }><>><>><>>><>><>>><>><>><>><>><>><>=> |