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