crc32.c revision 146081
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 <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 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 <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#ifdef DYNAMIC_CRC_TABLE 68 69local volatile int crc_table_empty = 1; 70local unsigned long FAR crc_table[TBLS][256]; 71local 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*/ 102local 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 179local 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 */ 201const 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/* ========================================================================= */ 215unsigned long ZEXPORT crc32(crc, buf, len) 216 unsigned long crc; 217 const unsigned char FAR *buf; 218 unsigned len; 219{ 220 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 if (sizeof(void *) == sizeof(ptrdiff_t)) { 229 u4 endian; 230 231 endian = 1; 232 if (*((unsigned char *)(&endian))) 233 return crc32_little(crc, buf, len); 234 else 235 return crc32_big(crc, buf, len); 236 } 237#endif /* BYFOUR */ 238 crc = crc ^ 0xffffffffUL; 239 while (len >= 8) { 240 DO8; 241 len -= 8; 242 } 243 if (len) do { 244 DO1; 245 } while (--len); 246 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/* ========================================================================= */ 258local unsigned long crc32_little(crc, buf, len) 259 unsigned long crc; 260 const unsigned char FAR *buf; 261 unsigned len; 262{ 263 register u4 c; 264 register const u4 FAR *buf4; 265 266 c = (u4)crc; 267 c = ~c; 268 while (len && ((ptrdiff_t)buf & 3)) { 269 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 270 len--; 271 } 272 273 buf4 = (const u4 FAR *)buf; 274 while (len >= 32) { 275 DOLIT32; 276 len -= 32; 277 } 278 while (len >= 4) { 279 DOLIT4; 280 len -= 4; 281 } 282 buf = (const unsigned char FAR *)buf4; 283 284 if (len) do { 285 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 286 } while (--len); 287 c = ~c; 288 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/* ========================================================================= */ 298local 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 */ 334