1 /* crc32.c -- compute the CRC-32 of a data stream 2 * Copyright (C) 1995-2003 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 * 5 * Thanks to Rodney Brown 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 about a factor 9 * 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 #ifdef MAKECRCH 23 # include 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 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 #ifdef DYNAMIC_CRC_TABLE 68 69 local volatile int crc_table_empty = 1; 70 local unsigned long FAR crc_table[TBLS][256]; 71 local void make_crc_table OF((void)); 72 #ifdef MAKECRCH 73 local void write_table OF((FILE *, const unsigned long FAR *)); 74 #endif /* MAKECRCH */ 75 76 /* 77 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 78 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. 79 80 Polynomials over GF(2) are represented in binary, one bit per coefficient, 81 with the lowest powers in the most significant bit. Then adding polynomials 82 is just exclusive-or, and multiplying a polynomial by x is a right shift by 83 one. If we call the above polynomial p, and represent a byte as the 84 polynomial q, also with the lowest power in the most significant bit (so the 85 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 86 where a mod b means the remainder after dividing a by b. 87 88 This calculation is done using the shift-register method of multiplying and 89 taking the remainder. The register is initialized to zero, and for each 90 incoming bit, x^32 is added mod p to the register if the bit is a one (where 91 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 92 x (which is shifting right by one and adding x^32 mod p if the bit shifted 93 out is a one). We start with the highest power (least significant bit) of 94 q and repeat for all eight bits of q. 95 96 The first table is simply the CRC of all possible eight bit values. This is 97 all the information needed to generate CRCs on data a byte at a time for all 98 combinations of CRC register values and incoming bytes. The remaining tables 99 allow for word-at-a-time CRC calculation for both big-endian and little- 100 endian machines, where a word is four bytes. 101 */ 102 local void make_crc_table() 103 { 104 unsigned long c; 105 int n, k; 106 unsigned long poly; /* polynomial exclusive-or pattern */ 107 /* terms of polynomial defining this crc (except x^32): */ 108 static volatile int first = 1; /* flag to limit concurrent making */ 109 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 110 111 /* See if another task is already doing this (not thread-safe, but better 112 than nothing -- significantly reduces duration of vulnerability in 113 case the advice about DYNAMIC_CRC_TABLE is ignored) */ 114 if (first) { 115 first = 0; 116 117 /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 118 poly = 0UL; 119 for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) 120 poly |= 1UL << (31 - p[n]); 121 122 /* generate a crc for every 8-bit value */ 123 for (n = 0; n < 256; n++) { 124 c = (unsigned long)n; 125 for (k = 0; k < 8; k++) 126 c = c & 1 ? poly ^ (c >> 1) : c >> 1; 127 crc_table[0][n] = c; 128 } 129 130 #ifdef BYFOUR 131 /* generate crc for each value followed by one, two, and three zeros, 132 and then the byte reversal of those as well as the first table */ 133 for (n = 0; n < 256; n++) { 134 c = crc_table[0][n]; 135 crc_table[4][n] = REV(c); 136 for (k = 1; k < 4; k++) { 137 c = crc_table[0][c & 0xff] ^ (c >> 8); 138 crc_table[k][n] = c; 139 crc_table[k + 4][n] = REV(c); 140 } 141 } 142 #endif /* BYFOUR */ 143 144 crc_table_empty = 0; 145 } 146 else { /* not first */ 147 /* wait for the other guy to finish (not efficient, but rare) */ 148 while (crc_table_empty) 149 ; 150 } 151 152 #ifdef MAKECRCH 153 /* write out CRC tables to crc32.h */ 154 { 155 FILE *out; 156 157 out = fopen("crc32.h", "w"); 158 if (out == NULL) return; 159 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 160 fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 161 fprintf(out, "local const unsigned long FAR "); 162 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 163 write_table(out, crc_table[0]); 164 # ifdef BYFOUR 165 fprintf(out, "#ifdef BYFOUR\n"); 166 for (k = 1; k < 8; k++) { 167 fprintf(out, " },\n {\n"); 168 write_table(out, crc_table[k]); 169 } 170 fprintf(out, "#endif\n"); 171 # endif /* BYFOUR */ 172 fprintf(out, " }\n};\n"); 173 fclose(out); 174 } 175 #endif /* MAKECRCH */ 176 } 177 178 #ifdef MAKECRCH 179 local void write_table(out, table) 180 FILE *out; 181 const unsigned long FAR *table; 182 { 183 int n; 184 185 for (n = 0; n < 256; n++) 186 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], 187 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 188 } 189 #endif /* MAKECRCH */ 190 191 #else /* !DYNAMIC_CRC_TABLE */ 192 /* ======================================================================== 193 * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 194 */ 195 #include "crc32.h" 196 #endif /* DYNAMIC_CRC_TABLE */ 197 198 /* ========================================================================= 199 * This function can be used by asm versions of crc32() 200 */ 201 const unsigned long FAR * ZEXPORT get_crc_table() 202 ###### { 203 #ifdef DYNAMIC_CRC_TABLE 204 if (crc_table_empty) 205 make_crc_table(); 206 #endif /* DYNAMIC_CRC_TABLE */ 207 ###### return (const unsigned long FAR *)crc_table; 208 } 209 210 /* ========================================================================= */ 211 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 212 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 213 214 /* ========================================================================= */ 215 unsigned long ZEXPORT crc32(crc, buf, len) 216 unsigned long crc; 217 const unsigned char FAR *buf; 218 unsigned len; 219 393 { 220 393 if (buf == Z_NULL) return 0UL; 221 222 #ifdef DYNAMIC_CRC_TABLE 223 if (crc_table_empty) 224 make_crc_table(); 225 #endif /* DYNAMIC_CRC_TABLE */ 226 227 #ifdef BYFOUR 228 305 if (sizeof(void *) == sizeof(ptrdiff_t)) { 229 305 u4 endian; 230 231 305 endian = 1; 232 305 if (*((unsigned char *)(&endian))) 233 305 return crc32_little(crc, buf, len); 234 else 235 ###### return crc32_big(crc, buf, len); 236 } 237 #endif /* BYFOUR */ 238 393 crc = crc ^ 0xffffffffUL; 239 393 while (len >= 8) { 240 393 DO8; 241 393 len -= 8; 242 } 243 393 if (len) do { 244 393 DO1; 245 393 } while (--len); 246 393 return crc ^ 0xffffffffUL; 247 } 248 249 #ifdef BYFOUR 250 251 /* ========================================================================= */ 252 #define DOLIT4 c ^= *buf4++; \ 253 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 254 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 255 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 256 257 /* ========================================================================= */ 258 local unsigned long crc32_little(crc, buf, len) 259 unsigned long crc; 260 const unsigned char FAR *buf; 261 unsigned len; 262 305 { 263 305 register u4 c; 264 305 register const u4 FAR *buf4; 265 266 305 c = (u4)crc; 267 305 c = ~c; 268 305 while (len && ((ptrdiff_t)buf & 3)) { 269 ###### c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 270 ###### len--; 271 } 272 273 305 buf4 = (const u4 FAR *)buf; 274 18591 while (len >= 32) { 275 18286 DOLIT32; 276 18286 len -= 32; 277 } 278 669 while (len >= 4) { 279 364 DOLIT4; 280 364 len -= 4; 281 } 282 305 buf = (const unsigned char FAR *)buf4; 283 284 305 if (len) do { 285 145 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 286 145 } while (--len); 287 305 c = ~c; 288 305 return (unsigned long)c; 289 } 290 291 /* ========================================================================= */ 292 #define DOBIG4 c ^= *++buf4; \ 293 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 294 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 295 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 296 297 /* ========================================================================= */ 298 local unsigned long crc32_big(crc, buf, len) 299 unsigned long crc; 300 const unsigned char FAR *buf; 301 unsigned len; 302 ###### { 303 ###### register u4 c; 304 ###### register const u4 FAR *buf4; 305 306 ###### c = REV((u4)crc); 307 ###### c = ~c; 308 ###### while (len && ((ptrdiff_t)buf & 3)) { 309 ###### c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 310 ###### len--; 311 } 312 313 ###### buf4 = (const u4 FAR *)buf; 314 ###### buf4--; 315 ###### while (len >= 32) { 316 ###### DOBIG32; 317 ###### len -= 32; 318 } 319 ###### while (len >= 4) { 320 ###### DOBIG4; 321 ###### len -= 4; 322 } 323 ###### buf4++; 324 ###### buf = (const unsigned char FAR *)buf4; 325 326 ###### if (len) do { 327 ###### c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 328 ###### } while (--len); 329 ###### c = ~c; 330 ###### return (unsigned long)(REV(c)); 331 } 332 333 #endif /* BYFOUR */