1/* crc32.c -- compute the CRC-32 of a data stream 2 * Copyright (C) 1995-2006, 2010 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 * 5 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 6 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 7 * tables for updating the shift register in one step with three exclusive-ors 8 * instead of four steps with four exclusive-ors. This results in about a 9 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 10 */ 11 12/* @(#) $Id$ */ 13 14/* 15 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 16 protection on the static variables used to control the first-use generation 17 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 18 first call get_crc_table() to initialize the tables before allowing more than 19 one thread to use crc32(). 20 */ 21 22 23#ifdef MAKECRCH 24# include <stdio.h> 25# ifndef DYNAMIC_CRC_TABLE 26# define DYNAMIC_CRC_TABLE 27# endif /* !DYNAMIC_CRC_TABLE */ 28#endif /* MAKECRCH */ 29 30#include "zutil.h" /* for STDC and FAR definitions */ 31 32#define local static 33 34/* Find a four-byte integer type for crc32_little() and crc32_big(). */ 35#ifndef NOBYFOUR 36# ifdef STDC /* need ANSI C limits.h to determine sizes */ 37# include <limits.h> 38# define BYFOUR 39# if (UINT_MAX == 0xffffffffUL) 40 typedef unsigned int u4; 41# else 42# if (ULONG_MAX == 0xffffffffUL) 43 typedef unsigned long u4; 44# else 45# if (USHRT_MAX == 0xffffffffUL) 46 typedef unsigned short u4; 47# else 48# undef BYFOUR /* can't find a four-byte integer type! */ 49# endif 50# endif 51# endif 52# endif /* STDC */ 53#endif /* !NOBYFOUR */ 54 55/* Definitions for doing the crc four data bytes at a time. */ 56#ifdef BYFOUR 57# define REV(w) ((((w)>>24)&0xff)+(((w)>>8)&0xff00)+ \ 58 (((w)&0xff00)<<8)+(((w)&0xff)<<24)) 59 local unsigned long crc32_little OF((unsigned long, 60 const unsigned char FAR *, unsigned)); 61 local unsigned long crc32_big OF((unsigned long, 62 const unsigned char FAR *, unsigned)); 63# define TBLS 8 64#else 65# define TBLS 1 66#endif /* BYFOUR */ 67 68/* Local functions for crc concatenation */ 69local unsigned long gf2_matrix_times OF((unsigned long *mat, 70 unsigned long vec)); 71local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 72local uLong crc32_combine_(uLong crc1, uLong crc2, z_off64_t len2); 73 74 75#ifdef DYNAMIC_CRC_TABLE 76 77local volatile int crc_table_empty = 1; 78local unsigned long FAR crc_table[TBLS][256]; 79local void make_crc_table OF((void)); 80#ifdef MAKECRCH 81 local void write_table OF((FILE *, const unsigned long FAR *)); 82#endif /* MAKECRCH */ 83/* 84 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 85 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. 86 87 Polynomials over GF(2) are represented in binary, one bit per coefficient, 88 with the lowest powers in the most significant bit. Then adding polynomials 89 is just exclusive-or, and multiplying a polynomial by x is a right shift by 90 one. If we call the above polynomial p, and represent a byte as the 91 polynomial q, also with the lowest power in the most significant bit (so the 92 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 93 where a mod b means the remainder after dividing a by b. 94 95 This calculation is done using the shift-register method of multiplying and 96 taking the remainder. The register is initialized to zero, and for each 97 incoming bit, x^32 is added mod p to the register if the bit is a one (where 98 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 99 x (which is shifting right by one and adding x^32 mod p if the bit shifted 100 out is a one). We start with the highest power (least significant bit) of 101 q and repeat for all eight bits of q. 102 103 The first table is simply the CRC of all possible eight bit values. This is 104 all the information needed to generate CRCs on data a byte at a time for all 105 combinations of CRC register values and incoming bytes. The remaining tables 106 allow for word-at-a-time CRC calculation for both big-endian and little- 107 endian machines, where a word is four bytes. 108*/ 109local void make_crc_table() 110{ 111 unsigned long c; 112 int n, k; 113 unsigned long poly; /* polynomial exclusive-or pattern */ 114 /* terms of polynomial defining this crc (except x^32): */ 115 static volatile int first = 1; /* flag to limit concurrent making */ 116 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 117 118 /* See if another task is already doing this (not thread-safe, but better 119 than nothing -- significantly reduces duration of vulnerability in 120 case the advice about DYNAMIC_CRC_TABLE is ignored) */ 121 if (first) { 122 first = 0; 123 124 /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 125 poly = 0UL; 126 for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) 127 poly |= 1UL << (31 - p[n]); 128 129 /* generate a crc for every 8-bit value */ 130 for (n = 0; n < 256; n++) { 131 c = (unsigned long)n; 132 for (k = 0; k < 8; k++) 133 c = c & 1 ? poly ^ (c >> 1) : c >> 1; 134 crc_table[0][n] = c; 135 } 136 137#ifdef BYFOUR 138 /* generate crc for each value followed by one, two, and three zeros, 139 and then the byte reversal of those as well as the first table */ 140 for (n = 0; n < 256; n++) { 141 c = crc_table[0][n]; 142 crc_table[4][n] = REV(c); 143 for (k = 1; k < 4; k++) { 144 c = crc_table[0][c & 0xff] ^ (c >> 8); 145 crc_table[k][n] = c; 146 crc_table[k + 4][n] = REV(c); 147 } 148 } 149#endif /* BYFOUR */ 150 151 crc_table_empty = 0; 152 } 153 else { /* not first */ 154 /* wait for the other guy to finish (not efficient, but rare) */ 155 while (crc_table_empty) 156 ; 157 } 158 159#ifdef MAKECRCH 160 /* write out CRC tables to crc32.h */ 161 { 162 FILE *out; 163 164 out = fopen("crc32.h", "w"); 165 if (out == NULL) return; 166 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 167 fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 168 fprintf(out, "local const unsigned long FAR "); 169 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 170 write_table(out, crc_table[0]); 171# ifdef BYFOUR 172 fprintf(out, "#ifdef BYFOUR\n"); 173 for (k = 1; k < 8; k++) { 174 fprintf(out, " },\n {\n"); 175 write_table(out, crc_table[k]); 176 } 177 fprintf(out, "#endif\n"); 178# endif /* BYFOUR */ 179 fprintf(out, " }\n};\n"); 180 fclose(out); 181 } 182#endif /* MAKECRCH */ 183} 184 185#ifdef MAKECRCH 186local void write_table(out, table) 187 FILE *out; 188 const unsigned long FAR *table; 189{ 190 int n; 191 192 for (n = 0; n < 256; n++) 193 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], 194 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 195} 196#endif /* MAKECRCH */ 197 198#else /* !DYNAMIC_CRC_TABLE */ 199/* ======================================================================== 200 * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 201 */ 202#include "crc32.h" 203#endif /* DYNAMIC_CRC_TABLE */ 204 205/* ========================================================================= 206 * This function can be used by asm versions of crc32() 207 */ 208const unsigned long FAR * ZEXPORT get_crc_table() 209{ 210#ifdef DYNAMIC_CRC_TABLE 211 if (crc_table_empty) 212 make_crc_table(); 213#endif /* DYNAMIC_CRC_TABLE */ 214 return (const unsigned long FAR *)crc_table; 215} 216 217/* ========================================================================= */ 218#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 219#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 220 221/* ========================================================================= */ 222unsigned long ZEXPORT crc32(crc, buf, len) 223 unsigned long crc; 224 const unsigned char FAR *buf; 225 uInt len; 226{ 227 if (buf == Z_NULL) return 0UL; 228 229#ifdef DYNAMIC_CRC_TABLE 230 if (crc_table_empty) 231 make_crc_table(); 232#endif /* DYNAMIC_CRC_TABLE */ 233 234#ifdef BYFOUR 235 if (sizeof(void *) == sizeof(ptrdiff_t)) { 236 u4 endian; 237 238 endian = 1; 239 if (*((unsigned char *)(&endian))) 240 return crc32_little(crc, buf, len); 241 else 242 return crc32_big(crc, buf, len); 243 } 244#endif /* BYFOUR */ 245 crc = crc ^ 0xffffffffUL; 246 while (len >= 8) { 247 DO8; 248 len -= 8; 249 } 250 if (len) do { 251 DO1; 252 } while (--len); 253 return crc ^ 0xffffffffUL; 254} 255 256 257#ifdef BYFOUR 258 259/* ========================================================================= */ 260#define DOLIT4 c ^= *buf4++; \ 261 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 262 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 263#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 264 265/* ========================================================================= */ 266local unsigned long crc32_little(crc, buf, len) 267 unsigned long crc; 268 const unsigned char FAR *buf; 269 unsigned len; 270{ 271 register u4 c; 272 register const u4 FAR *buf4; 273 274 c = (u4)crc; 275 c = ~c; 276 while (len && ((ptrdiff_t)buf & 3)) { 277 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 278 len--; 279 } 280 281 buf4 = (const u4 FAR *)(const void FAR *)buf; 282 while (len >= 32) { 283 DOLIT32; 284 len -= 32; 285 } 286 while (len >= 4) { 287 DOLIT4; 288 len -= 4; 289 } 290 buf = (const unsigned char FAR *)buf4; 291 292 if (len) do { 293 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 294 } while (--len); 295 c = ~c; 296 return (unsigned long)c; 297} 298 299/* ========================================================================= */ 300#define DOBIG4 c ^= *++buf4; \ 301 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 302 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 303#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 304 305/* ========================================================================= */ 306local unsigned long crc32_big(crc, buf, len) 307 unsigned long crc; 308 const unsigned char FAR *buf; 309 unsigned len; 310{ 311 register u4 c; 312 register const u4 FAR *buf4; 313 314 c = REV((u4)crc); 315 c = ~c; 316 while (len && ((ptrdiff_t)buf & 3)) { 317 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 318 len--; 319 } 320 321 buf4 = (const u4 FAR *)(const void FAR *)buf; 322 buf4--; 323 while (len >= 32) { 324 DOBIG32; 325 len -= 32; 326 } 327 while (len >= 4) { 328 DOBIG4; 329 len -= 4; 330 } 331 buf4++; 332 buf = (const unsigned char FAR *)buf4; 333 334 if (len) do { 335 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 336 } while (--len); 337 c = ~c; 338 return (unsigned long)(REV(c)); 339} 340 341#endif /* BYFOUR */ 342 343#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 344 345/* ========================================================================= */ 346local unsigned long gf2_matrix_times(mat, vec) 347 unsigned long *mat; 348 unsigned long vec; 349{ 350 unsigned long sum; 351 352 sum = 0; 353 while (vec) { 354 if (vec & 1) 355 sum ^= *mat; 356 vec >>= 1; 357 mat++; 358 } 359 return sum; 360} 361 362/* ========================================================================= */ 363local void gf2_matrix_square(square, mat) 364 unsigned long *square; 365 unsigned long *mat; 366{ 367 int n; 368 369 for (n = 0; n < GF2_DIM; n++) 370 square[n] = gf2_matrix_times(mat, mat[n]); 371} 372 373/* ========================================================================= */ 374local uLong crc32_combine_(crc1, crc2, len2) 375 uLong crc1; 376 uLong crc2; 377 z_off64_t len2; 378{ 379 int n; 380 unsigned long row; 381 unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 382 unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 383 384 /* degenerate case (also disallow negative lengths) */ 385 if (len2 <= 0) 386 return crc1; 387 388 /* put operator for one zero bit in odd */ 389 odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 390 row = 1; 391 for (n = 1; n < GF2_DIM; n++) { 392 odd[n] = row; 393 row <<= 1; 394 } 395 396 /* put operator for two zero bits in even */ 397 gf2_matrix_square(even, odd); 398 399 /* put operator for four zero bits in odd */ 400 gf2_matrix_square(odd, even); 401 402 /* apply len2 zeros to crc1 (first square will put the operator for one 403 zero byte, eight zero bits, in even) */ 404 do { 405 /* apply zeros operator for this bit of len2 */ 406 gf2_matrix_square(even, odd); 407 if (len2 & 1) 408 crc1 = gf2_matrix_times(even, crc1); 409 len2 >>= 1; 410 411 /* if no more bits set, then done */ 412 if (len2 == 0) 413 break; 414 415 /* another iteration of the loop with odd and even swapped */ 416 gf2_matrix_square(odd, even); 417 if (len2 & 1) 418 crc1 = gf2_matrix_times(odd, crc1); 419 len2 >>= 1; 420 421 /* if no more bits set, then done */ 422 } while (len2 != 0); 423 424 /* return combined crc */ 425 crc1 ^= crc2; 426 return crc1; 427} 428 429/* ========================================================================= */ 430uLong ZEXPORT crc32_combine(crc1, crc2, len2) 431 uLong crc1; 432 uLong crc2; 433 z_off_t len2; 434{ 435 return crc32_combine_(crc1, crc2, len2); 436} 437 438uLong ZEXPORT crc32_combine64(crc1, crc2, len2) 439 uLong crc1; 440 uLong crc2; 441 z_off64_t len2; 442{ 443 return crc32_combine_(crc1, crc2, len2); 444} 445