Line | Count | Source (jump to first uncovered line) |
1 | | /* adler32.c -- compute the Adler-32 checksum of a data stream |
2 | | * Copyright (C) 1995-2011, 2016 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 | 63.2M | #define BASE 65521U /* largest prime smaller than 65536 */ |
11 | 35.9M | #define NMAX 5552 |
12 | | /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ |
13 | | |
14 | 50.4G | #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} |
15 | 25.2G | #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); |
16 | 12.6G | #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); |
17 | 6.30G | #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); |
18 | 3.15G | #define DO16(buf) DO8(buf,0); DO8(buf,8); |
19 | | |
20 | | /* use NO_DIVIDE if your processor does not do division in hardware -- |
21 | | try it both ways to see which is faster */ |
22 | | #ifdef NO_DIVIDE |
23 | | /* note that this assumes BASE is 65521, where 65536 % 65521 == 15 |
24 | | (thank you to John Reiser for pointing this out) */ |
25 | | # define CHOP(a) \ |
26 | | do { \ |
27 | | unsigned long tmp = a >> 16; \ |
28 | | a &= 0xffffUL; \ |
29 | | a += (tmp << 4) - tmp; \ |
30 | | } while (0) |
31 | | # define MOD28(a) \ |
32 | | do { \ |
33 | | CHOP(a); \ |
34 | | if (a >= BASE) a -= BASE; \ |
35 | | } while (0) |
36 | | # define MOD(a) \ |
37 | | do { \ |
38 | | CHOP(a); \ |
39 | | MOD28(a); \ |
40 | | } while (0) |
41 | | # define MOD63(a) \ |
42 | | do { /* this assumes a is not negative */ \ |
43 | | z_off64_t tmp = a >> 32; \ |
44 | | a &= 0xffffffffL; \ |
45 | | a += (tmp << 8) - (tmp << 5) + tmp; \ |
46 | | tmp = a >> 16; \ |
47 | | a &= 0xffffL; \ |
48 | | a += (tmp << 4) - tmp; \ |
49 | | tmp = a >> 16; \ |
50 | | a &= 0xffffL; \ |
51 | | a += (tmp << 4) - tmp; \ |
52 | | if (a >= BASE) a -= BASE; \ |
53 | | } while (0) |
54 | | #else |
55 | 37.1M | # define MOD(a) a %= BASE |
56 | 11.0M | # define MOD28(a) a %= BASE |
57 | 0 | # define MOD63(a) a %= BASE |
58 | | #endif |
59 | | |
60 | | /* ========================================================================= */ |
61 | 30.7M | uLong ZEXPORT adler32_z(uLong adler, const Bytef *buf, z_size_t len) { |
62 | 30.7M | unsigned long sum2; |
63 | 30.7M | unsigned n; |
64 | | |
65 | | /* split Adler-32 into component sums */ |
66 | 30.7M | sum2 = (adler >> 16) & 0xffff; |
67 | 30.7M | adler &= 0xffff; |
68 | | |
69 | | /* in case user likes doing a byte at a time, keep it fast */ |
70 | 30.7M | if (len == 1) { |
71 | 1.78M | adler += buf[0]; |
72 | 1.78M | if (adler >= BASE) |
73 | 1.25k | adler -= BASE; |
74 | 1.78M | sum2 += adler; |
75 | 1.78M | if (sum2 >= BASE) |
76 | 336k | sum2 -= BASE; |
77 | 1.78M | return adler | (sum2 << 16); |
78 | 1.78M | } |
79 | | |
80 | | /* initial Adler-32 value (deferred check for len == 1 speed) */ |
81 | 28.9M | if (buf == Z_NULL) |
82 | 8.01M | return 1L; |
83 | | |
84 | | /* in case short lengths are provided, keep it somewhat fast */ |
85 | 20.9M | if (len < 16) { |
86 | 76.8M | while (len--) { |
87 | 65.7M | adler += *buf++; |
88 | 65.7M | sum2 += adler; |
89 | 65.7M | } |
90 | 11.0M | if (adler >= BASE) |
91 | 15.6k | adler -= BASE; |
92 | 11.0M | MOD28(sum2); /* only added so many BASE's */ |
93 | 11.0M | return adler | (sum2 << 16); |
94 | 11.0M | } |
95 | | |
96 | | /* do length NMAX blocks -- requires just one modulo operation */ |
97 | 18.5M | while (len >= NMAX) { |
98 | 8.68M | len -= NMAX; |
99 | 8.68M | n = NMAX / 16; /* NMAX is divisible by 16 */ |
100 | 3.01G | do { |
101 | 3.01G | DO16(buf); /* 16 sums unrolled */ |
102 | 3.01G | buf += 16; |
103 | 3.01G | } while (--n); |
104 | 8.68M | MOD(adler); |
105 | 8.68M | MOD(sum2); |
106 | 8.68M | } |
107 | | |
108 | | /* do remaining bytes (less than NMAX, still just one modulo) */ |
109 | 9.87M | if (len) { /* avoid modulos if none remaining */ |
110 | 144M | while (len >= 16) { |
111 | 135M | len -= 16; |
112 | 135M | DO16(buf); |
113 | 135M | buf += 16; |
114 | 135M | } |
115 | 48.6M | while (len--) { |
116 | 38.8M | adler += *buf++; |
117 | 38.8M | sum2 += adler; |
118 | 38.8M | } |
119 | 9.87M | MOD(adler); |
120 | 9.87M | MOD(sum2); |
121 | 9.87M | } |
122 | | |
123 | | /* return recombined sums */ |
124 | 9.87M | return adler | (sum2 << 16); |
125 | 20.9M | } |
126 | | |
127 | | /* ========================================================================= */ |
128 | 30.7M | uLong ZEXPORT adler32(uLong adler, const Bytef *buf, uInt len) { |
129 | 30.7M | return adler32_z(adler, buf, len); |
130 | 30.7M | } |
131 | | |
132 | | /* ========================================================================= */ |
133 | 0 | local uLong adler32_combine_(uLong adler1, uLong adler2, z_off64_t len2) { |
134 | 0 | unsigned long sum1; |
135 | 0 | unsigned long sum2; |
136 | 0 | unsigned rem; |
137 | | |
138 | | /* for negative len, return invalid adler32 as a clue for debugging */ |
139 | 0 | if (len2 < 0) |
140 | 0 | return 0xffffffffUL; |
141 | | |
142 | | /* the derivation of this formula is left as an exercise for the reader */ |
143 | 0 | MOD63(len2); /* assumes len2 >= 0 */ |
144 | 0 | rem = (unsigned)len2; |
145 | 0 | sum1 = adler1 & 0xffff; |
146 | 0 | sum2 = rem * sum1; |
147 | 0 | MOD(sum2); |
148 | 0 | sum1 += (adler2 & 0xffff) + BASE - 1; |
149 | 0 | sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; |
150 | 0 | if (sum1 >= BASE) sum1 -= BASE; |
151 | 0 | if (sum1 >= BASE) sum1 -= BASE; |
152 | 0 | if (sum2 >= ((unsigned long)BASE << 1)) sum2 -= ((unsigned long)BASE << 1); |
153 | 0 | if (sum2 >= BASE) sum2 -= BASE; |
154 | 0 | return sum1 | (sum2 << 16); |
155 | 0 | } |
156 | | |
157 | | /* ========================================================================= */ |
158 | 0 | uLong ZEXPORT adler32_combine(uLong adler1, uLong adler2, z_off_t len2) { |
159 | 0 | return adler32_combine_(adler1, adler2, len2); |
160 | 0 | } |
161 | | |
162 | 0 | uLong ZEXPORT adler32_combine64(uLong adler1, uLong adler2, z_off64_t len2) { |
163 | 0 | return adler32_combine_(adler1, adler2, len2); |
164 | 0 | } |