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