line |
stmt |
bran |
cond |
sub |
time |
code |
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$ */ |
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
|
682752
|
|
|
|
|
uLong ZEXPORT adler32( |
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
|
682752
|
|
|
|
|
sum2 = (adler >> 16) & 0xffff; |
75
|
682752
|
|
|
|
|
adler &= 0xffff; |
76
|
|
|
|
|
|
|
77
|
|
|
|
|
|
/* in case user likes doing a byte at a time, keep it fast */ |
78
|
682752
|
|
|
|
|
if (len == 1) { |
79
|
211168
|
|
|
|
|
adler += buf[0]; |
80
|
211168
|
|
|
|
|
if (adler >= BASE) |
81
|
302
|
|
|
|
|
adler -= BASE; |
82
|
211168
|
|
|
|
|
sum2 += adler; |
83
|
211168
|
|
|
|
|
if (sum2 >= BASE) |
84
|
99852
|
|
|
|
|
sum2 -= BASE; |
85
|
211168
|
|
|
|
|
return adler | (sum2 << 16); |
86
|
|
|
|
|
|
} |
87
|
|
|
|
|
|
|
88
|
|
|
|
|
|
/* initial Adler-32 value (deferred check for len == 1 speed) */ |
89
|
471584
|
|
|
|
|
if (buf == Z_NULL) |
90
|
|
|
|
|
|
return 1L; |
91
|
|
|
|
|
|
|
92
|
|
|
|
|
|
/* in case short lengths are provided, keep it somewhat fast */ |
93
|
442336
|
|
|
|
|
if (len < 16) { |
94
|
1889094
|
|
|
|
|
while (len--) { |
95
|
1472302
|
|
|
|
|
adler += *buf++; |
96
|
1472302
|
|
|
|
|
sum2 += adler; |
97
|
|
|
|
|
|
} |
98
|
416792
|
|
|
|
|
if (adler >= BASE) |
99
|
1320
|
|
|
|
|
adler -= BASE; |
100
|
416792
|
|
|
|
|
MOD28(sum2); /* only added so many BASE's */ |
101
|
416792
|
|
|
|
|
return adler | (sum2 << 16); |
102
|
|
|
|
|
|
} |
103
|
|
|
|
|
|
|
104
|
|
|
|
|
|
/* do length NMAX blocks -- requires just one modulo operation */ |
105
|
26680
|
|
|
|
|
while (len >= NMAX) { |
106
|
1136
|
|
|
|
|
len -= NMAX; |
107
|
|
|
|
|
|
n = NMAX / 16; /* NMAX is divisible by 16 */ |
108
|
|
|
|
|
|
do { |
109
|
394192
|
|
|
|
|
DO16(buf); /* 16 sums unrolled */ |
110
|
394192
|
|
|
|
|
buf += 16; |
111
|
394192
|
|
|
|
|
} while (--n); |
112
|
1136
|
|
|
|
|
MOD(adler); |
113
|
1136
|
|
|
|
|
MOD(sum2); |
114
|
|
|
|
|
|
} |
115
|
|
|
|
|
|
|
116
|
|
|
|
|
|
/* do remaining bytes (less than NMAX, still just one modulo) */ |
117
|
25544
|
|
|
|
|
if (len) { /* avoid modulos if none remaining */ |
118
|
1400398
|
|
|
|
|
while (len >= 16) { |
119
|
1374854
|
|
|
|
|
len -= 16; |
120
|
1374854
|
|
|
|
|
DO16(buf); |
121
|
1374854
|
|
|
|
|
buf += 16; |
122
|
|
|
|
|
|
} |
123
|
152124
|
|
|
|
|
while (len--) { |
124
|
126580
|
|
|
|
|
adler += *buf++; |
125
|
126580
|
|
|
|
|
sum2 += adler; |
126
|
|
|
|
|
|
} |
127
|
25544
|
|
|
|
|
MOD(adler); |
128
|
25544
|
|
|
|
|
MOD(sum2); |
129
|
|
|
|
|
|
} |
130
|
|
|
|
|
|
|
131
|
|
|
|
|
|
/* return recombined sums */ |
132
|
25544
|
|
|
|
|
return adler | (sum2 << 16); |
133
|
|
|
|
|
|
} |
134
|
|
|
|
|
|
|
135
|
|
|
|
|
|
/* ========================================================================= */ |
136
|
0
|
|
|
|
|
local uLong adler32_combine_( |
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
|
0
|
|
|
|
|
if (len2 < 0) |
147
|
|
|
|
|
|
return 0xffffffffUL; |
148
|
|
|
|
|
|
|
149
|
|
|
|
|
|
/* the derivation of this formula is left as an exercise for the reader */ |
150
|
0
|
|
|
|
|
MOD63(len2); /* assumes len2 >= 0 */ |
151
|
0
|
|
|
|
|
rem = (unsigned)len2; |
152
|
0
|
|
|
|
|
sum1 = adler1 & 0xffff; |
153
|
0
|
|
|
|
|
sum2 = rem * sum1; |
154
|
0
|
|
|
|
|
MOD(sum2); |
155
|
0
|
|
|
|
|
sum1 += (adler2 & 0xffff) + BASE - 1; |
156
|
0
|
|
|
|
|
sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; |
157
|
0
|
|
|
|
|
if (sum1 >= BASE) sum1 -= BASE; |
158
|
0
|
|
|
|
|
if (sum1 >= BASE) sum1 -= BASE; |
159
|
0
|
|
|
|
|
if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1); |
160
|
0
|
|
|
|
|
if (sum2 >= BASE) sum2 -= BASE; |
161
|
0
|
|
|
|
|
return sum1 | (sum2 << 16); |
162
|
|
|
|
|
|
} |
163
|
|
|
|
|
|
|
164
|
|
|
|
|
|
/* ========================================================================= */ |
165
|
0
|
|
|
|
|
uLong ZEXPORT adler32_combine( |
166
|
|
|
|
|
|
uLong adler1, |
167
|
|
|
|
|
|
uLong adler2, |
168
|
|
|
|
|
|
z_off_t len2) |
169
|
|
|
|
|
|
{ |
170
|
0
|
|
|
|
|
return adler32_combine_(adler1, adler2, len2); |
171
|
|
|
|
|
|
} |
172
|
|
|
|
|
|
|
173
|
0
|
|
|
|
|
uLong ZEXPORT adler32_combine64( |
174
|
|
|
|
|
|
uLong adler1, |
175
|
|
|
|
|
|
uLong adler2, |
176
|
|
|
|
|
|
z_off64_t len2) |
177
|
|
|
|
|
|
{ |
178
|
0
|
|
|
|
|
return adler32_combine_(adler1, adler2, len2); |
179
|
|
|
|
|
|
} |