# Python code coverage for Modules/zlib/crc32.c

# | count | content |
---|---|---|

1 | n/a | /* crc32.c -- compute the CRC-32 of a data stream |

2 | n/a | * Copyright (C) 1995-2006, 2010, 2011, 2012, 2016 Mark Adler |

3 | n/a | * For conditions of distribution and use, see copyright notice in zlib.h |

4 | n/a | * |

5 | n/a | * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster |

6 | n/a | * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing |

7 | n/a | * tables for updating the shift register in one step with three exclusive-ors |

8 | n/a | * instead of four steps with four exclusive-ors. This results in about a |

9 | n/a | * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. |

10 | n/a | */ |

11 | n/a | |

12 | n/a | /* @(#) $Id$ */ |

13 | n/a | |

14 | n/a | /* |

15 | n/a | Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore |

16 | n/a | protection on the static variables used to control the first-use generation |

17 | n/a | of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should |

18 | n/a | first call get_crc_table() to initialize the tables before allowing more than |

19 | n/a | one thread to use crc32(). |

20 | n/a | |

21 | n/a | DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h. |

22 | n/a | */ |

23 | n/a | |

24 | n/a | #ifdef MAKECRCH |

25 | n/a | # include <stdio.h> |

26 | n/a | # ifndef DYNAMIC_CRC_TABLE |

27 | n/a | # define DYNAMIC_CRC_TABLE |

28 | n/a | # endif /* !DYNAMIC_CRC_TABLE */ |

29 | n/a | #endif /* MAKECRCH */ |

30 | n/a | |

31 | n/a | #include "zutil.h" /* for STDC and FAR definitions */ |

32 | n/a | |

33 | n/a | /* Definitions for doing the crc four data bytes at a time. */ |

34 | n/a | #if !defined(NOBYFOUR) && defined(Z_U4) |

35 | n/a | # define BYFOUR |

36 | n/a | #endif |

37 | n/a | #ifdef BYFOUR |

38 | n/a | local unsigned long crc32_little OF((unsigned long, |

39 | n/a | const unsigned char FAR *, z_size_t)); |

40 | n/a | local unsigned long crc32_big OF((unsigned long, |

41 | n/a | const unsigned char FAR *, z_size_t)); |

42 | n/a | # define TBLS 8 |

43 | n/a | #else |

44 | n/a | # define TBLS 1 |

45 | n/a | #endif /* BYFOUR */ |

46 | n/a | |

47 | n/a | /* Local functions for crc concatenation */ |

48 | n/a | local unsigned long gf2_matrix_times OF((unsigned long *mat, |

49 | n/a | unsigned long vec)); |

50 | n/a | local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); |

51 | n/a | local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); |

52 | n/a | |

53 | n/a | |

54 | n/a | #ifdef DYNAMIC_CRC_TABLE |

55 | n/a | |

56 | n/a | local volatile int crc_table_empty = 1; |

57 | n/a | local z_crc_t FAR crc_table[TBLS][256]; |

58 | n/a | local void make_crc_table OF((void)); |

59 | n/a | #ifdef MAKECRCH |

60 | n/a | local void write_table OF((FILE *, const z_crc_t FAR *)); |

61 | n/a | #endif /* MAKECRCH */ |

62 | n/a | /* |

63 | n/a | Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: |

64 | n/a | x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1. |

65 | n/a | |

66 | n/a | Polynomials over GF(2) are represented in binary, one bit per coefficient, |

67 | n/a | with the lowest powers in the most significant bit. Then adding polynomials |

68 | n/a | is just exclusive-or, and multiplying a polynomial by x is a right shift by |

69 | n/a | one. If we call the above polynomial p, and represent a byte as the |

70 | n/a | polynomial q, also with the lowest power in the most significant bit (so the |

71 | n/a | byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, |

72 | n/a | where a mod b means the remainder after dividing a by b. |

73 | n/a | |

74 | n/a | This calculation is done using the shift-register method of multiplying and |

75 | n/a | taking the remainder. The register is initialized to zero, and for each |

76 | n/a | incoming bit, x^32 is added mod p to the register if the bit is a one (where |

77 | n/a | x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by |

78 | n/a | x (which is shifting right by one and adding x^32 mod p if the bit shifted |

79 | n/a | out is a one). We start with the highest power (least significant bit) of |

80 | n/a | q and repeat for all eight bits of q. |

81 | n/a | |

82 | n/a | The first table is simply the CRC of all possible eight bit values. This is |

83 | n/a | all the information needed to generate CRCs on data a byte at a time for all |

84 | n/a | combinations of CRC register values and incoming bytes. The remaining tables |

85 | n/a | allow for word-at-a-time CRC calculation for both big-endian and little- |

86 | n/a | endian machines, where a word is four bytes. |

87 | n/a | */ |

88 | n/a | local void make_crc_table() |

89 | n/a | { |

90 | n/a | z_crc_t c; |

91 | n/a | int n, k; |

92 | n/a | z_crc_t poly; /* polynomial exclusive-or pattern */ |

93 | n/a | /* terms of polynomial defining this crc (except x^32): */ |

94 | n/a | static volatile int first = 1; /* flag to limit concurrent making */ |

95 | n/a | static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; |

96 | n/a | |

97 | n/a | /* See if another task is already doing this (not thread-safe, but better |

98 | n/a | than nothing -- significantly reduces duration of vulnerability in |

99 | n/a | case the advice about DYNAMIC_CRC_TABLE is ignored) */ |

100 | n/a | if (first) { |

101 | n/a | first = 0; |

102 | n/a | |

103 | n/a | /* make exclusive-or pattern from polynomial (0xedb88320UL) */ |

104 | n/a | poly = 0; |

105 | n/a | for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) |

106 | n/a | poly |= (z_crc_t)1 << (31 - p[n]); |

107 | n/a | |

108 | n/a | /* generate a crc for every 8-bit value */ |

109 | n/a | for (n = 0; n < 256; n++) { |

110 | n/a | c = (z_crc_t)n; |

111 | n/a | for (k = 0; k < 8; k++) |

112 | n/a | c = c & 1 ? poly ^ (c >> 1) : c >> 1; |

113 | n/a | crc_table[0][n] = c; |

114 | n/a | } |

115 | n/a | |

116 | n/a | #ifdef BYFOUR |

117 | n/a | /* generate crc for each value followed by one, two, and three zeros, |

118 | n/a | and then the byte reversal of those as well as the first table */ |

119 | n/a | for (n = 0; n < 256; n++) { |

120 | n/a | c = crc_table[0][n]; |

121 | n/a | crc_table[4][n] = ZSWAP32(c); |

122 | n/a | for (k = 1; k < 4; k++) { |

123 | n/a | c = crc_table[0][c & 0xff] ^ (c >> 8); |

124 | n/a | crc_table[k][n] = c; |

125 | n/a | crc_table[k + 4][n] = ZSWAP32(c); |

126 | n/a | } |

127 | n/a | } |

128 | n/a | #endif /* BYFOUR */ |

129 | n/a | |

130 | n/a | crc_table_empty = 0; |

131 | n/a | } |

132 | n/a | else { /* not first */ |

133 | n/a | /* wait for the other guy to finish (not efficient, but rare) */ |

134 | n/a | while (crc_table_empty) |

135 | n/a | ; |

136 | n/a | } |

137 | n/a | |

138 | n/a | #ifdef MAKECRCH |

139 | n/a | /* write out CRC tables to crc32.h */ |

140 | n/a | { |

141 | n/a | FILE *out; |

142 | n/a | |

143 | n/a | out = fopen("crc32.h", "w"); |

144 | n/a | if (out == NULL) return; |

145 | n/a | fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); |

146 | n/a | fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); |

147 | n/a | fprintf(out, "local const z_crc_t FAR "); |

148 | n/a | fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); |

149 | n/a | write_table(out, crc_table[0]); |

150 | n/a | # ifdef BYFOUR |

151 | n/a | fprintf(out, "#ifdef BYFOUR\n"); |

152 | n/a | for (k = 1; k < 8; k++) { |

153 | n/a | fprintf(out, " },\n {\n"); |

154 | n/a | write_table(out, crc_table[k]); |

155 | n/a | } |

156 | n/a | fprintf(out, "#endif\n"); |

157 | n/a | # endif /* BYFOUR */ |

158 | n/a | fprintf(out, " }\n};\n"); |

159 | n/a | fclose(out); |

160 | n/a | } |

161 | n/a | #endif /* MAKECRCH */ |

162 | n/a | } |

163 | n/a | |

164 | n/a | #ifdef MAKECRCH |

165 | n/a | local void write_table(out, table) |

166 | n/a | FILE *out; |

167 | n/a | const z_crc_t FAR *table; |

168 | n/a | { |

169 | n/a | int n; |

170 | n/a | |

171 | n/a | for (n = 0; n < 256; n++) |

172 | n/a | fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", |

173 | n/a | (unsigned long)(table[n]), |

174 | n/a | n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); |

175 | n/a | } |

176 | n/a | #endif /* MAKECRCH */ |

177 | n/a | |

178 | n/a | #else /* !DYNAMIC_CRC_TABLE */ |

179 | n/a | /* ======================================================================== |

180 | n/a | * Tables of CRC-32s of all single-byte values, made by make_crc_table(). |

181 | n/a | */ |

182 | n/a | #include "crc32.h" |

183 | n/a | #endif /* DYNAMIC_CRC_TABLE */ |

184 | n/a | |

185 | n/a | /* ========================================================================= |

186 | n/a | * This function can be used by asm versions of crc32() |

187 | n/a | */ |

188 | n/a | const z_crc_t FAR * ZEXPORT get_crc_table() |

189 | n/a | { |

190 | n/a | #ifdef DYNAMIC_CRC_TABLE |

191 | n/a | if (crc_table_empty) |

192 | n/a | make_crc_table(); |

193 | n/a | #endif /* DYNAMIC_CRC_TABLE */ |

194 | n/a | return (const z_crc_t FAR *)crc_table; |

195 | n/a | } |

196 | n/a | |

197 | n/a | /* ========================================================================= */ |

198 | n/a | #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) |

199 | n/a | #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 |

200 | n/a | |

201 | n/a | /* ========================================================================= */ |

202 | n/a | unsigned long ZEXPORT crc32_z(crc, buf, len) |

203 | n/a | unsigned long crc; |

204 | n/a | const unsigned char FAR *buf; |

205 | n/a | z_size_t len; |

206 | n/a | { |

207 | n/a | if (buf == Z_NULL) return 0UL; |

208 | n/a | |

209 | n/a | #ifdef DYNAMIC_CRC_TABLE |

210 | n/a | if (crc_table_empty) |

211 | n/a | make_crc_table(); |

212 | n/a | #endif /* DYNAMIC_CRC_TABLE */ |

213 | n/a | |

214 | n/a | #ifdef BYFOUR |

215 | n/a | if (sizeof(void *) == sizeof(ptrdiff_t)) { |

216 | n/a | z_crc_t endian; |

217 | n/a | |

218 | n/a | endian = 1; |

219 | n/a | if (*((unsigned char *)(&endian))) |

220 | n/a | return crc32_little(crc, buf, len); |

221 | n/a | else |

222 | n/a | return crc32_big(crc, buf, len); |

223 | n/a | } |

224 | n/a | #endif /* BYFOUR */ |

225 | n/a | crc = crc ^ 0xffffffffUL; |

226 | n/a | while (len >= 8) { |

227 | n/a | DO8; |

228 | n/a | len -= 8; |

229 | n/a | } |

230 | n/a | if (len) do { |

231 | n/a | DO1; |

232 | n/a | } while (--len); |

233 | n/a | return crc ^ 0xffffffffUL; |

234 | n/a | } |

235 | n/a | |

236 | n/a | /* ========================================================================= */ |

237 | n/a | unsigned long ZEXPORT crc32(crc, buf, len) |

238 | n/a | unsigned long crc; |

239 | n/a | const unsigned char FAR *buf; |

240 | n/a | uInt len; |

241 | n/a | { |

242 | n/a | return crc32_z(crc, buf, len); |

243 | n/a | } |

244 | n/a | |

245 | n/a | #ifdef BYFOUR |

246 | n/a | |

247 | n/a | /* |

248 | n/a | This BYFOUR code accesses the passed unsigned char * buffer with a 32-bit |

249 | n/a | integer pointer type. This violates the strict aliasing rule, where a |

250 | n/a | compiler can assume, for optimization purposes, that two pointers to |

251 | n/a | fundamentally different types won't ever point to the same memory. This can |

252 | n/a | manifest as a problem only if one of the pointers is written to. This code |

253 | n/a | only reads from those pointers. So long as this code remains isolated in |

254 | n/a | this compilation unit, there won't be a problem. For this reason, this code |

255 | n/a | should not be copied and pasted into a compilation unit in which other code |

256 | n/a | writes to the buffer that is passed to these routines. |

257 | n/a | */ |

258 | n/a | |

259 | n/a | /* ========================================================================= */ |

260 | n/a | #define DOLIT4 c ^= *buf4++; \ |

261 | n/a | c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ |

262 | n/a | crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] |

263 | n/a | #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 |

264 | n/a | |

265 | n/a | /* ========================================================================= */ |

266 | n/a | local unsigned long crc32_little(crc, buf, len) |

267 | n/a | unsigned long crc; |

268 | n/a | const unsigned char FAR *buf; |

269 | n/a | z_size_t len; |

270 | n/a | { |

271 | n/a | register z_crc_t c; |

272 | n/a | register const z_crc_t FAR *buf4; |

273 | n/a | |

274 | n/a | c = (z_crc_t)crc; |

275 | n/a | c = ~c; |

276 | n/a | while (len && ((ptrdiff_t)buf & 3)) { |

277 | n/a | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); |

278 | n/a | len--; |

279 | n/a | } |

280 | n/a | |

281 | n/a | buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |

282 | n/a | while (len >= 32) { |

283 | n/a | DOLIT32; |

284 | n/a | len -= 32; |

285 | n/a | } |

286 | n/a | while (len >= 4) { |

287 | n/a | DOLIT4; |

288 | n/a | len -= 4; |

289 | n/a | } |

290 | n/a | buf = (const unsigned char FAR *)buf4; |

291 | n/a | |

292 | n/a | if (len) do { |

293 | n/a | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); |

294 | n/a | } while (--len); |

295 | n/a | c = ~c; |

296 | n/a | return (unsigned long)c; |

297 | n/a | } |

298 | n/a | |

299 | n/a | /* ========================================================================= */ |

300 | n/a | #define DOBIG4 c ^= *buf4++; \ |

301 | n/a | c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ |

302 | n/a | crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] |

303 | n/a | #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 |

304 | n/a | |

305 | n/a | /* ========================================================================= */ |

306 | n/a | local unsigned long crc32_big(crc, buf, len) |

307 | n/a | unsigned long crc; |

308 | n/a | const unsigned char FAR *buf; |

309 | n/a | z_size_t len; |

310 | n/a | { |

311 | n/a | register z_crc_t c; |

312 | n/a | register const z_crc_t FAR *buf4; |

313 | n/a | |

314 | n/a | c = ZSWAP32((z_crc_t)crc); |

315 | n/a | c = ~c; |

316 | n/a | while (len && ((ptrdiff_t)buf & 3)) { |

317 | n/a | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |

318 | n/a | len--; |

319 | n/a | } |

320 | n/a | |

321 | n/a | buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |

322 | n/a | while (len >= 32) { |

323 | n/a | DOBIG32; |

324 | n/a | len -= 32; |

325 | n/a | } |

326 | n/a | while (len >= 4) { |

327 | n/a | DOBIG4; |

328 | n/a | len -= 4; |

329 | n/a | } |

330 | n/a | buf = (const unsigned char FAR *)buf4; |

331 | n/a | |

332 | n/a | if (len) do { |

333 | n/a | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |

334 | n/a | } while (--len); |

335 | n/a | c = ~c; |

336 | n/a | return (unsigned long)(ZSWAP32(c)); |

337 | n/a | } |

338 | n/a | |

339 | n/a | #endif /* BYFOUR */ |

340 | n/a | |

341 | n/a | #define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ |

342 | n/a | |

343 | n/a | /* ========================================================================= */ |

344 | n/a | local unsigned long gf2_matrix_times(mat, vec) |

345 | n/a | unsigned long *mat; |

346 | n/a | unsigned long vec; |

347 | n/a | { |

348 | n/a | unsigned long sum; |

349 | n/a | |

350 | n/a | sum = 0; |

351 | n/a | while (vec) { |

352 | n/a | if (vec & 1) |

353 | n/a | sum ^= *mat; |

354 | n/a | vec >>= 1; |

355 | n/a | mat++; |

356 | n/a | } |

357 | n/a | return sum; |

358 | n/a | } |

359 | n/a | |

360 | n/a | /* ========================================================================= */ |

361 | n/a | local void gf2_matrix_square(square, mat) |

362 | n/a | unsigned long *square; |

363 | n/a | unsigned long *mat; |

364 | n/a | { |

365 | n/a | int n; |

366 | n/a | |

367 | n/a | for (n = 0; n < GF2_DIM; n++) |

368 | n/a | square[n] = gf2_matrix_times(mat, mat[n]); |

369 | n/a | } |

370 | n/a | |

371 | n/a | /* ========================================================================= */ |

372 | n/a | local uLong crc32_combine_(crc1, crc2, len2) |

373 | n/a | uLong crc1; |

374 | n/a | uLong crc2; |

375 | n/a | z_off64_t len2; |

376 | n/a | { |

377 | n/a | int n; |

378 | n/a | unsigned long row; |

379 | n/a | unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ |

380 | n/a | unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ |

381 | n/a | |

382 | n/a | /* degenerate case (also disallow negative lengths) */ |

383 | n/a | if (len2 <= 0) |

384 | n/a | return crc1; |

385 | n/a | |

386 | n/a | /* put operator for one zero bit in odd */ |

387 | n/a | odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ |

388 | n/a | row = 1; |

389 | n/a | for (n = 1; n < GF2_DIM; n++) { |

390 | n/a | odd[n] = row; |

391 | n/a | row <<= 1; |

392 | n/a | } |

393 | n/a | |

394 | n/a | /* put operator for two zero bits in even */ |

395 | n/a | gf2_matrix_square(even, odd); |

396 | n/a | |

397 | n/a | /* put operator for four zero bits in odd */ |

398 | n/a | gf2_matrix_square(odd, even); |

399 | n/a | |

400 | n/a | /* apply len2 zeros to crc1 (first square will put the operator for one |

401 | n/a | zero byte, eight zero bits, in even) */ |

402 | n/a | do { |

403 | n/a | /* apply zeros operator for this bit of len2 */ |

404 | n/a | gf2_matrix_square(even, odd); |

405 | n/a | if (len2 & 1) |

406 | n/a | crc1 = gf2_matrix_times(even, crc1); |

407 | n/a | len2 >>= 1; |

408 | n/a | |

409 | n/a | /* if no more bits set, then done */ |

410 | n/a | if (len2 == 0) |

411 | n/a | break; |

412 | n/a | |

413 | n/a | /* another iteration of the loop with odd and even swapped */ |

414 | n/a | gf2_matrix_square(odd, even); |

415 | n/a | if (len2 & 1) |

416 | n/a | crc1 = gf2_matrix_times(odd, crc1); |

417 | n/a | len2 >>= 1; |

418 | n/a | |

419 | n/a | /* if no more bits set, then done */ |

420 | n/a | } while (len2 != 0); |

421 | n/a | |

422 | n/a | /* return combined crc */ |

423 | n/a | crc1 ^= crc2; |

424 | n/a | return crc1; |

425 | n/a | } |

426 | n/a | |

427 | n/a | /* ========================================================================= */ |

428 | n/a | uLong ZEXPORT crc32_combine(crc1, crc2, len2) |

429 | n/a | uLong crc1; |

430 | n/a | uLong crc2; |

431 | n/a | z_off_t len2; |

432 | n/a | { |

433 | n/a | return crc32_combine_(crc1, crc2, len2); |

434 | n/a | } |

435 | n/a | |

436 | n/a | uLong ZEXPORT crc32_combine64(crc1, crc2, len2) |

437 | n/a | uLong crc1; |

438 | n/a | uLong crc2; |

439 | n/a | z_off64_t len2; |

440 | n/a | { |

441 | n/a | return crc32_combine_(crc1, crc2, len2); |

442 | n/a | } |