File indexing completed on 2024-03-24 03:51:12
0001 /* crc32.c -- compute the CRC-32 of a data stream 0002 * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler 0003 * For conditions of distribution and use, see copyright notice in zlib.h 0004 * 0005 * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 0006 * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 0007 * tables for updating the shift register in one step with three exclusive-ors 0008 * instead of four steps with four exclusive-ors. This results in about a 0009 * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 0010 */ 0011 0012 /* @(#) $Id$ */ 0013 0014 /* 0015 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 0016 protection on the static variables used to control the first-use generation 0017 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 0018 first call get_crc_table() to initialize the tables before allowing more than 0019 one thread to use crc32(). 0020 0021 DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h. 0022 */ 0023 0024 #ifdef MAKECRCH 0025 # include <stdio.h> 0026 # ifndef DYNAMIC_CRC_TABLE 0027 # define DYNAMIC_CRC_TABLE 0028 # endif /* !DYNAMIC_CRC_TABLE */ 0029 #endif /* MAKECRCH */ 0030 0031 #include "zutil.h" /* for STDC and FAR definitions */ 0032 0033 #define local static 0034 0035 /* Definitions for doing the crc four data bytes at a time. */ 0036 #if !defined(NOBYFOUR) && defined(Z_U4) 0037 # define BYFOUR 0038 #endif 0039 #ifdef BYFOUR 0040 local unsigned long crc32_little OF((unsigned long, 0041 const unsigned char FAR *, unsigned)); 0042 local unsigned long crc32_big OF((unsigned long, 0043 const unsigned char FAR *, unsigned)); 0044 # define TBLS 8 0045 #else 0046 # define TBLS 1 0047 #endif /* BYFOUR */ 0048 0049 /* Local functions for crc concatenation */ 0050 local unsigned long gf2_matrix_times OF((unsigned long *mat, 0051 unsigned long vec)); 0052 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 0053 local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); 0054 0055 0056 #ifdef DYNAMIC_CRC_TABLE 0057 0058 local volatile int crc_table_empty = 1; 0059 local z_crc_t FAR crc_table[TBLS][256]; 0060 local void make_crc_table OF((void)); 0061 #ifdef MAKECRCH 0062 local void write_table OF((FILE *, const z_crc_t FAR *)); 0063 #endif /* MAKECRCH */ 0064 /* 0065 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 0066 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. 0067 0068 Polynomials over GF(2) are represented in binary, one bit per coefficient, 0069 with the lowest powers in the most significant bit. Then adding polynomials 0070 is just exclusive-or, and multiplying a polynomial by x is a right shift by 0071 one. If we call the above polynomial p, and represent a byte as the 0072 polynomial q, also with the lowest power in the most significant bit (so the 0073 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 0074 where a mod b means the remainder after dividing a by b. 0075 0076 This calculation is done using the shift-register method of multiplying and 0077 taking the remainder. The register is initialized to zero, and for each 0078 incoming bit, x^32 is added mod p to the register if the bit is a one (where 0079 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 0080 x (which is shifting right by one and adding x^32 mod p if the bit shifted 0081 out is a one). We start with the highest power (least significant bit) of 0082 q and repeat for all eight bits of q. 0083 0084 The first table is simply the CRC of all possible eight bit values. This is 0085 all the information needed to generate CRCs on data a byte at a time for all 0086 combinations of CRC register values and incoming bytes. The remaining tables 0087 allow for word-at-a-time CRC calculation for both big-endian and little- 0088 endian machines, where a word is four bytes. 0089 */ 0090 local void make_crc_table() 0091 { 0092 z_crc_t c; 0093 int n, k; 0094 z_crc_t poly; /* polynomial exclusive-or pattern */ 0095 /* terms of polynomial defining this crc (except x^32): */ 0096 static volatile int first = 1; /* flag to limit concurrent making */ 0097 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 0098 0099 /* See if another task is already doing this (not thread-safe, but better 0100 than nothing -- significantly reduces duration of vulnerability in 0101 case the advice about DYNAMIC_CRC_TABLE is ignored) */ 0102 if (first) { 0103 first = 0; 0104 0105 /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 0106 poly = 0; 0107 for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) 0108 poly |= (z_crc_t)1 << (31 - p[n]); 0109 0110 /* generate a crc for every 8-bit value */ 0111 for (n = 0; n < 256; n++) { 0112 c = (z_crc_t)n; 0113 for (k = 0; k < 8; k++) 0114 c = c & 1 ? poly ^ (c >> 1) : c >> 1; 0115 crc_table[0][n] = c; 0116 } 0117 0118 #ifdef BYFOUR 0119 /* generate crc for each value followed by one, two, and three zeros, 0120 and then the byte reversal of those as well as the first table */ 0121 for (n = 0; n < 256; n++) { 0122 c = crc_table[0][n]; 0123 crc_table[4][n] = ZSWAP32(c); 0124 for (k = 1; k < 4; k++) { 0125 c = crc_table[0][c & 0xff] ^ (c >> 8); 0126 crc_table[k][n] = c; 0127 crc_table[k + 4][n] = ZSWAP32(c); 0128 } 0129 } 0130 #endif /* BYFOUR */ 0131 0132 crc_table_empty = 0; 0133 } 0134 else { /* not first */ 0135 /* wait for the other guy to finish (not efficient, but rare) */ 0136 while (crc_table_empty) 0137 ; 0138 } 0139 0140 #ifdef MAKECRCH 0141 /* write out CRC tables to crc32.h */ 0142 { 0143 FILE *out; 0144 0145 out = fopen("crc32.h", "w"); 0146 if (out == NULL) return; 0147 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 0148 fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 0149 fprintf(out, "local const z_crc_t FAR "); 0150 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 0151 write_table(out, crc_table[0]); 0152 # ifdef BYFOUR 0153 fprintf(out, "#ifdef BYFOUR\n"); 0154 for (k = 1; k < 8; k++) { 0155 fprintf(out, " },\n {\n"); 0156 write_table(out, crc_table[k]); 0157 } 0158 fprintf(out, "#endif\n"); 0159 # endif /* BYFOUR */ 0160 fprintf(out, " }\n};\n"); 0161 fclose(out); 0162 } 0163 #endif /* MAKECRCH */ 0164 } 0165 0166 #ifdef MAKECRCH 0167 local void write_table(out, table) 0168 FILE *out; 0169 const z_crc_t FAR *table; 0170 { 0171 int n; 0172 0173 for (n = 0; n < 256; n++) 0174 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", 0175 (unsigned long)(table[n]), 0176 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 0177 } 0178 #endif /* MAKECRCH */ 0179 0180 #else /* !DYNAMIC_CRC_TABLE */ 0181 /* ======================================================================== 0182 * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 0183 */ 0184 #include "crc32.h" 0185 #endif /* DYNAMIC_CRC_TABLE */ 0186 0187 /* ========================================================================= 0188 * This function can be used by asm versions of crc32() 0189 */ 0190 const z_crc_t FAR * ZEXPORT get_crc_table() 0191 { 0192 #ifdef DYNAMIC_CRC_TABLE 0193 if (crc_table_empty) 0194 make_crc_table(); 0195 #endif /* DYNAMIC_CRC_TABLE */ 0196 return (const z_crc_t FAR *)crc_table; 0197 } 0198 0199 /* ========================================================================= */ 0200 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 0201 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 0202 0203 /* ========================================================================= */ 0204 unsigned long ZEXPORT crc32(crc, buf, len) 0205 unsigned long crc; 0206 const unsigned char FAR *buf; 0207 uInt len; 0208 { 0209 if (buf == Z_NULL) return 0UL; 0210 0211 #ifdef DYNAMIC_CRC_TABLE 0212 if (crc_table_empty) 0213 make_crc_table(); 0214 #endif /* DYNAMIC_CRC_TABLE */ 0215 0216 #ifdef BYFOUR 0217 if (sizeof(void *) == sizeof(ptrdiff_t)) { 0218 z_crc_t endian; 0219 0220 endian = 1; 0221 if (*((unsigned char *)(&endian))) 0222 return crc32_little(crc, buf, len); 0223 else 0224 return crc32_big(crc, buf, len); 0225 } 0226 #endif /* BYFOUR */ 0227 crc = crc ^ 0xffffffffUL; 0228 while (len >= 8) { 0229 DO8; 0230 len -= 8; 0231 } 0232 if (len) do { 0233 DO1; 0234 } while (--len); 0235 return crc ^ 0xffffffffUL; 0236 } 0237 0238 #ifdef BYFOUR 0239 0240 /* ========================================================================= */ 0241 #define DOLIT4 c ^= *buf4++; \ 0242 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 0243 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 0244 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 0245 0246 /* ========================================================================= */ 0247 local unsigned long crc32_little(crc, buf, len) 0248 unsigned long crc; 0249 const unsigned char FAR *buf; 0250 unsigned len; 0251 { 0252 register z_crc_t c; 0253 register const z_crc_t FAR *buf4; 0254 0255 c = (z_crc_t)crc; 0256 c = ~c; 0257 while (len && ((ptrdiff_t)buf & 3)) { 0258 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 0259 len--; 0260 } 0261 0262 buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 0263 while (len >= 32) { 0264 DOLIT32; 0265 len -= 32; 0266 } 0267 while (len >= 4) { 0268 DOLIT4; 0269 len -= 4; 0270 } 0271 buf = (const unsigned char FAR *)buf4; 0272 0273 if (len) do { 0274 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 0275 } while (--len); 0276 c = ~c; 0277 return (unsigned long)c; 0278 } 0279 0280 /* ========================================================================= */ 0281 #define DOBIG4 c ^= *++buf4; \ 0282 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 0283 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 0284 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 0285 0286 /* ========================================================================= */ 0287 local unsigned long crc32_big(crc, buf, len) 0288 unsigned long crc; 0289 const unsigned char FAR *buf; 0290 unsigned len; 0291 { 0292 register z_crc_t c; 0293 register const z_crc_t FAR *buf4; 0294 0295 c = ZSWAP32((z_crc_t)crc); 0296 c = ~c; 0297 while (len && ((ptrdiff_t)buf & 3)) { 0298 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 0299 len--; 0300 } 0301 0302 buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 0303 buf4--; 0304 while (len >= 32) { 0305 DOBIG32; 0306 len -= 32; 0307 } 0308 while (len >= 4) { 0309 DOBIG4; 0310 len -= 4; 0311 } 0312 buf4++; 0313 buf = (const unsigned char FAR *)buf4; 0314 0315 if (len) do { 0316 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 0317 } while (--len); 0318 c = ~c; 0319 return (unsigned long)(ZSWAP32(c)); 0320 } 0321 0322 #endif /* BYFOUR */ 0323 0324 #define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 0325 0326 /* ========================================================================= */ 0327 local unsigned long gf2_matrix_times(mat, vec) 0328 unsigned long *mat; 0329 unsigned long vec; 0330 { 0331 unsigned long sum; 0332 0333 sum = 0; 0334 while (vec) { 0335 if (vec & 1) 0336 sum ^= *mat; 0337 vec >>= 1; 0338 mat++; 0339 } 0340 return sum; 0341 } 0342 0343 /* ========================================================================= */ 0344 local void gf2_matrix_square(square, mat) 0345 unsigned long *square; 0346 unsigned long *mat; 0347 { 0348 int n; 0349 0350 for (n = 0; n < GF2_DIM; n++) 0351 square[n] = gf2_matrix_times(mat, mat[n]); 0352 } 0353 0354 /* ========================================================================= */ 0355 local uLong crc32_combine_(crc1, crc2, len2) 0356 uLong crc1; 0357 uLong crc2; 0358 z_off64_t len2; 0359 { 0360 int n; 0361 unsigned long row; 0362 unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 0363 unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 0364 0365 /* degenerate case (also disallow negative lengths) */ 0366 if (len2 <= 0) 0367 return crc1; 0368 0369 /* put operator for one zero bit in odd */ 0370 odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 0371 row = 1; 0372 for (n = 1; n < GF2_DIM; n++) { 0373 odd[n] = row; 0374 row <<= 1; 0375 } 0376 0377 /* put operator for two zero bits in even */ 0378 gf2_matrix_square(even, odd); 0379 0380 /* put operator for four zero bits in odd */ 0381 gf2_matrix_square(odd, even); 0382 0383 /* apply len2 zeros to crc1 (first square will put the operator for one 0384 zero byte, eight zero bits, in even) */ 0385 do { 0386 /* apply zeros operator for this bit of len2 */ 0387 gf2_matrix_square(even, odd); 0388 if (len2 & 1) 0389 crc1 = gf2_matrix_times(even, crc1); 0390 len2 >>= 1; 0391 0392 /* if no more bits set, then done */ 0393 if (len2 == 0) 0394 break; 0395 0396 /* another iteration of the loop with odd and even swapped */ 0397 gf2_matrix_square(odd, even); 0398 if (len2 & 1) 0399 crc1 = gf2_matrix_times(odd, crc1); 0400 len2 >>= 1; 0401 0402 /* if no more bits set, then done */ 0403 } while (len2 != 0); 0404 0405 /* return combined crc */ 0406 crc1 ^= crc2; 0407 return crc1; 0408 } 0409 0410 /* ========================================================================= */ 0411 uLong ZEXPORT crc32_combine(crc1, crc2, len2) 0412 uLong crc1; 0413 uLong crc2; 0414 z_off_t len2; 0415 { 0416 return crc32_combine_(crc1, crc2, len2); 0417 } 0418 0419 uLong ZEXPORT crc32_combine64(crc1, crc2, len2) 0420 uLong crc1; 0421 uLong crc2; 0422 z_off64_t len2; 0423 { 0424 return crc32_combine_(crc1, crc2, len2); 0425 }