adler32.c

filter: Statementstmt 93.4% 57 / 61 Branchbran 79.4% 27 / 34 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 88.4% 84 / 95 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« trees.c ↑ Summary crc32.c »
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 #define BASE 65521U /* largest prime smaller than 65536 */
11 #define NMAX 5552
12 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
13  
14 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
15 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
16 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
17 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
18 #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 # define MOD(a) a %= BASE
56 # define MOD28(a) a %= BASE
57 # define MOD63(a) a %= BASE
58 #endif
59  
60 /* ========================================================================= */
61 50691 uLong ZEXPORT adler32_z(uLong adler, const Bytef *buf, z_size_t len) {
62 unsigned long sum2;
63 unsigned n;
64  
65 /* split Adler-32 into component sums */
66 50691 sum2 = (adler >> 16) & 0xffff;
67 50691 adler &= 0xffff;
68  
69 /* in case user likes doing a byte at a time, keep it fast */
70 50691 ▶ if (len == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (len == 1) { 50388 303 50691
71 50388 adler += buf[0];
72 50388 ▶ if (adler >= BASE)
Branch: 1 branch
BranchTrueFalseTotal
if (adler >= BASE) 97 50291 50388
73 97 adler -= BASE;
74 50388 sum2 += adler;
75 50388 ▶ if (sum2 >= BASE)
Branch: 1 branch
BranchTrueFalseTotal
if (sum2 >= BASE) 24949 25439 50388
76 24949 sum2 -= BASE;
77 50388 return adler | (sum2 << 16);
78 }
79  
80 /* initial Adler-32 value (deferred check for len == 1 speed) */
81 303 ▶ if (buf == Z_NULL)
Branch: 1 branch
BranchTrueFalseTotal
if (buf == Z_NULL) 98 205 303
82 98 return 1L;
83  
84 /* in case short lengths are provided, keep it somewhat fast */
85 205 ▶ if (len < 16) {
Branch: 1 branch
BranchTrueFalseTotal
if (len < 16) { 33 172 205
86 417 ▶ while (len--) {
Branch: 1 branch
BranchTrueFalseTotal
while (len--) { 384 33 417
87 384 adler += *buf++;
88 384 sum2 += adler;
89 }
90 33 ▶ if (adler >= BASE)
Branch: 1 branch
BranchTrueFalseTotal
if (adler >= BASE) 0 33 33
91 0 adler -= BASE;
92 33 MOD28(sum2); /* only added so many BASE's */
93 33 return adler | (sum2 << 16);
94 }
95  
96 /* do length NMAX blocks -- requires just one modulo operation */
97 269 ▶ while (len >= NMAX) {
Branch: 1 branch
BranchTrueFalseTotal
while (len >= NMAX) { 97 172 269
98 97 len -= NMAX;
99 97 n = NMAX / 16; /* NMAX is divisible by 16 */
100 do {
101 33659 DO16(buf); /* 16 sums unrolled */
102 33659 buf += 16;
103 33659 ▶ } while (--n);
Branch: 1 branch
BranchTrueFalseTotal
} while (--n); 33562 97 33659
104 97 MOD(adler);
105 97 MOD(sum2);
106 }
107  
108 /* do remaining bytes (less than NMAX, still just one modulo) */
109 172 ▶ if (len) { /* avoid modulos if none remaining */
Branch: 1 branch
BranchTrueFalseTotal
if (len) { /* avoid modulos if none remaining */ 172 0 172
110 17556 ▶ while (len >= 16) {
Branch: 1 branch
BranchTrueFalseTotal
while (len >= 16) { 17384 172 17556
111 17384 len -= 16;
112 17384 DO16(buf);
113 17384 buf += 16;
114 }
115 882 ▶ while (len--) {
Branch: 1 branch
BranchTrueFalseTotal
while (len--) { 710 172 882
116 710 adler += *buf++;
117 710 sum2 += adler;
118 }
119 172 MOD(adler);
120 172 MOD(sum2);
121 }
122  
123 /* return recombined sums */
124 172 return adler | (sum2 << 16);
125 }
126  
127 /* ========================================================================= */
128 50691 uLong ZEXPORT adler32(uLong adler, const Bytef *buf, uInt len) {
129 50691 return adler32_z(adler, buf, len);
130 }
131  
132 /* ========================================================================= */
133 1 local uLong adler32_combine_(uLong adler1, uLong adler2, z_off64_t len2) {
134 unsigned long sum1;
135 unsigned long sum2;
136 unsigned rem;
137  
138 /* for negative len, return invalid adler32 as a clue for debugging */
139 1 ▶ if (len2 < 0)
Branch: 1 branch
BranchTrueFalseTotal
if (len2 < 0) 0 1 1
140 0 return 0xffffffffUL;
141  
142 /* the derivation of this formula is left as an exercise for the reader */
143 1 MOD63(len2); /* assumes len2 >= 0 */
144 1 rem = (unsigned)len2;
145 1 sum1 = adler1 & 0xffff;
146 1 sum2 = rem * sum1;
147 1 MOD(sum2);
148 1 sum1 += (adler2 & 0xffff) + BASE - 1;
149 1 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
150 1 ▶ if (sum1 >= BASE) sum1 -= BASE;
Branch: 1 branch
BranchTrueFalseTotal
if (sum1 >= BASE) sum1 -= BASE; 1 0 1
151 1 ▶ if (sum1 >= BASE) sum1 -= BASE;
Branch: 1 branch
BranchTrueFalseTotal
if (sum1 >= BASE) sum1 -= BASE; 0 1 1
152 1 ▶ if (sum2 >= ((unsigned long)BASE << 1)) sum2 -= ((unsigned long)BASE << 1);
Branch: 1 branch
BranchTrueFalseTotal
if (sum2 >= ((unsigned long)BASE << 1)) sum2 -= ((unsigned long)BASE << 1); 0 1 1
153 1 ▶ if (sum2 >= BASE) sum2 -= BASE;
Branch: 1 branch
BranchTrueFalseTotal
if (sum2 >= BASE) sum2 -= BASE; 1 0 1
154 1 return sum1 | (sum2 << 16);
155 }
156  
157 /* ========================================================================= */
158 1 uLong ZEXPORT adler32_combine(uLong adler1, uLong adler2, z_off_t len2) {
159 1 return adler32_combine_(adler1, adler2, len2);
160 }
161  
162 0 uLong ZEXPORT adler32_combine64(uLong adler1, uLong adler2, z_off64_t len2) {
163 0 return adler32_combine_(adler1, adler2, len2);
164 }
« trees.c ↑ Summary crc32.c »