dvander@27: /* crc32.c -- compute the CRC-32 of a data stream dvander@27: * Copyright (C) 1995-2005 Mark Adler dvander@27: * For conditions of distribution and use, see copyright notice in zlib.h dvander@27: * dvander@27: * Thanks to Rodney Brown for his contribution of faster dvander@27: * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing dvander@27: * tables for updating the shift register in one step with three exclusive-ors dvander@27: * instead of four steps with four exclusive-ors. This results in about a dvander@27: * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. dvander@27: */ dvander@27: dvander@27: /* @(#) $Id$ */ dvander@27: dvander@27: /* dvander@27: Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore dvander@27: protection on the static variables used to control the first-use generation dvander@27: of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should dvander@27: first call get_crc_table() to initialize the tables before allowing more than dvander@27: one thread to use crc32(). dvander@27: */ dvander@27: dvander@27: #ifdef MAKECRCH dvander@27: # include dvander@27: # ifndef DYNAMIC_CRC_TABLE dvander@27: # define DYNAMIC_CRC_TABLE dvander@27: # endif /* !DYNAMIC_CRC_TABLE */ dvander@27: #endif /* MAKECRCH */ dvander@27: dvander@27: #include "zutil.h" /* for STDC and FAR definitions */ dvander@27: dvander@27: #define local static dvander@27: dvander@27: /* Find a four-byte integer type for crc32_little() and crc32_big(). */ dvander@27: #ifndef NOBYFOUR dvander@27: # ifdef STDC /* need ANSI C limits.h to determine sizes */ dvander@27: # include dvander@27: # define BYFOUR dvander@27: # if (UINT_MAX == 0xffffffffUL) dvander@27: typedef unsigned int u4; dvander@27: # else dvander@27: # if (ULONG_MAX == 0xffffffffUL) dvander@27: typedef unsigned long u4; dvander@27: # else dvander@27: # if (USHRT_MAX == 0xffffffffUL) dvander@27: typedef unsigned short u4; dvander@27: # else dvander@27: # undef BYFOUR /* can't find a four-byte integer type! */ dvander@27: # endif dvander@27: # endif dvander@27: # endif dvander@27: # endif /* STDC */ dvander@27: #endif /* !NOBYFOUR */ dvander@27: dvander@27: /* Definitions for doing the crc four data bytes at a time. */ dvander@27: #ifdef BYFOUR dvander@27: # define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \ dvander@27: (((w)&0xff00)<<8)+(((w)&0xff)<<24)) dvander@27: local unsigned long crc32_little OF((unsigned long, dvander@27: const unsigned char FAR *, unsigned)); dvander@27: local unsigned long crc32_big OF((unsigned long, dvander@27: const unsigned char FAR *, unsigned)); dvander@27: # define TBLS 8 dvander@27: #else dvander@27: # define TBLS 1 dvander@27: #endif /* BYFOUR */ dvander@27: dvander@27: /* Local functions for crc concatenation */ dvander@27: local unsigned long gf2_matrix_times OF((unsigned long *mat, dvander@27: unsigned long vec)); dvander@27: local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); dvander@27: dvander@27: #ifdef DYNAMIC_CRC_TABLE dvander@27: dvander@27: local volatile int crc_table_empty = 1; dvander@27: local unsigned long FAR crc_table[TBLS][256]; dvander@27: local void make_crc_table OF((void)); dvander@27: #ifdef MAKECRCH dvander@27: local void write_table OF((FILE *, const unsigned long FAR *)); dvander@27: #endif /* MAKECRCH */ dvander@27: /* dvander@27: Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: dvander@27: 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. dvander@27: dvander@27: Polynomials over GF(2) are represented in binary, one bit per coefficient, dvander@27: with the lowest powers in the most significant bit. Then adding polynomials dvander@27: is just exclusive-or, and multiplying a polynomial by x is a right shift by dvander@27: one. If we call the above polynomial p, and represent a byte as the dvander@27: polynomial q, also with the lowest power in the most significant bit (so the dvander@27: byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, dvander@27: where a mod b means the remainder after dividing a by b. dvander@27: dvander@27: This calculation is done using the shift-register method of multiplying and dvander@27: taking the remainder. The register is initialized to zero, and for each dvander@27: incoming bit, x^32 is added mod p to the register if the bit is a one (where dvander@27: x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by dvander@27: x (which is shifting right by one and adding x^32 mod p if the bit shifted dvander@27: out is a one). We start with the highest power (least significant bit) of dvander@27: q and repeat for all eight bits of q. dvander@27: dvander@27: The first table is simply the CRC of all possible eight bit values. This is dvander@27: all the information needed to generate CRCs on data a byte at a time for all dvander@27: combinations of CRC register values and incoming bytes. The remaining tables dvander@27: allow for word-at-a-time CRC calculation for both big-endian and little- dvander@27: endian machines, where a word is four bytes. dvander@27: */ dvander@27: local void make_crc_table() dvander@27: { dvander@27: unsigned long c; dvander@27: int n, k; dvander@27: unsigned long poly; /* polynomial exclusive-or pattern */ dvander@27: /* terms of polynomial defining this crc (except x^32): */ dvander@27: static volatile int first = 1; /* flag to limit concurrent making */ dvander@27: static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; dvander@27: dvander@27: /* See if another task is already doing this (not thread-safe, but better dvander@27: than nothing -- significantly reduces duration of vulnerability in dvander@27: case the advice about DYNAMIC_CRC_TABLE is ignored) */ dvander@27: if (first) { dvander@27: first = 0; dvander@27: dvander@27: /* make exclusive-or pattern from polynomial (0xedb88320UL) */ dvander@27: poly = 0UL; dvander@27: for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) dvander@27: poly |= 1UL << (31 - p[n]); dvander@27: dvander@27: /* generate a crc for every 8-bit value */ dvander@27: for (n = 0; n < 256; n++) { dvander@27: c = (unsigned long)n; dvander@27: for (k = 0; k < 8; k++) dvander@27: c = c & 1 ? poly ^ (c >> 1) : c >> 1; dvander@27: crc_table[0][n] = c; dvander@27: } dvander@27: dvander@27: #ifdef BYFOUR dvander@27: /* generate crc for each value followed by one, two, and three zeros, dvander@27: and then the byte reversal of those as well as the first table */ dvander@27: for (n = 0; n < 256; n++) { dvander@27: c = crc_table[0][n]; dvander@27: crc_table[4][n] = REV(c); dvander@27: for (k = 1; k < 4; k++) { dvander@27: c = crc_table[0][c & 0xff] ^ (c >> 8); dvander@27: crc_table[k][n] = c; dvander@27: crc_table[k + 4][n] = REV(c); dvander@27: } dvander@27: } dvander@27: #endif /* BYFOUR */ dvander@27: dvander@27: crc_table_empty = 0; dvander@27: } dvander@27: else { /* not first */ dvander@27: /* wait for the other guy to finish (not efficient, but rare) */ dvander@27: while (crc_table_empty) dvander@27: ; dvander@27: } dvander@27: dvander@27: #ifdef MAKECRCH dvander@27: /* write out CRC tables to crc32.h */ dvander@27: { dvander@27: FILE *out; dvander@27: dvander@27: out = fopen("crc32.h", "w"); dvander@27: if (out == NULL) return; dvander@27: fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); dvander@27: fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); dvander@27: fprintf(out, "local const unsigned long FAR "); dvander@27: fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); dvander@27: write_table(out, crc_table[0]); dvander@27: # ifdef BYFOUR dvander@27: fprintf(out, "#ifdef BYFOUR\n"); dvander@27: for (k = 1; k < 8; k++) { dvander@27: fprintf(out, " },\n {\n"); dvander@27: write_table(out, crc_table[k]); dvander@27: } dvander@27: fprintf(out, "#endif\n"); dvander@27: # endif /* BYFOUR */ dvander@27: fprintf(out, " }\n};\n"); dvander@27: fclose(out); dvander@27: } dvander@27: #endif /* MAKECRCH */ dvander@27: } dvander@27: dvander@27: #ifdef MAKECRCH dvander@27: local void write_table(out, table) dvander@27: FILE *out; dvander@27: const unsigned long FAR *table; dvander@27: { dvander@27: int n; dvander@27: dvander@27: for (n = 0; n < 256; n++) dvander@27: fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], dvander@27: n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); dvander@27: } dvander@27: #endif /* MAKECRCH */ dvander@27: dvander@27: #else /* !DYNAMIC_CRC_TABLE */ dvander@27: /* ======================================================================== dvander@27: * Tables of CRC-32s of all single-byte values, made by make_crc_table(). dvander@27: */ dvander@27: #include "crc32.h" dvander@27: #endif /* DYNAMIC_CRC_TABLE */ dvander@27: dvander@27: /* ========================================================================= dvander@27: * This function can be used by asm versions of crc32() dvander@27: */ dvander@27: const unsigned long FAR * ZEXPORT get_crc_table() dvander@27: { dvander@27: #ifdef DYNAMIC_CRC_TABLE dvander@27: if (crc_table_empty) dvander@27: make_crc_table(); dvander@27: #endif /* DYNAMIC_CRC_TABLE */ dvander@27: return (const unsigned long FAR *)crc_table; dvander@27: } dvander@27: dvander@27: /* ========================================================================= */ dvander@27: #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) dvander@27: #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 dvander@27: dvander@27: /* ========================================================================= */ dvander@27: unsigned long ZEXPORT crc32(crc, buf, len) dvander@27: unsigned long crc; dvander@27: const unsigned char FAR *buf; dvander@27: unsigned len; dvander@27: { dvander@27: if (buf == Z_NULL) return 0UL; dvander@27: dvander@27: #ifdef DYNAMIC_CRC_TABLE dvander@27: if (crc_table_empty) dvander@27: make_crc_table(); dvander@27: #endif /* DYNAMIC_CRC_TABLE */ dvander@27: dvander@27: #ifdef BYFOUR dvander@27: if (sizeof(void *) == sizeof(ptrdiff_t)) { dvander@27: u4 endian; dvander@27: dvander@27: endian = 1; dvander@27: if (*((unsigned char *)(&endian))) dvander@27: return crc32_little(crc, buf, len); dvander@27: else dvander@27: return crc32_big(crc, buf, len); dvander@27: } dvander@27: #endif /* BYFOUR */ dvander@27: crc = crc ^ 0xffffffffUL; dvander@27: while (len >= 8) { dvander@27: DO8; dvander@27: len -= 8; dvander@27: } dvander@27: if (len) do { dvander@27: DO1; dvander@27: } while (--len); dvander@27: return crc ^ 0xffffffffUL; dvander@27: } dvander@27: dvander@27: #ifdef BYFOUR dvander@27: dvander@27: /* ========================================================================= */ dvander@27: #define DOLIT4 c ^= *buf4++; \ dvander@27: c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ dvander@27: crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] dvander@27: #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 dvander@27: dvander@27: /* ========================================================================= */ dvander@27: local unsigned long crc32_little(crc, buf, len) dvander@27: unsigned long crc; dvander@27: const unsigned char FAR *buf; dvander@27: unsigned len; dvander@27: { dvander@27: register u4 c; dvander@27: register const u4 FAR *buf4; dvander@27: dvander@27: c = (u4)crc; dvander@27: c = ~c; dvander@27: while (len && ((ptrdiff_t)buf & 3)) { dvander@27: c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); dvander@27: len--; dvander@27: } dvander@27: dvander@27: buf4 = (const u4 FAR *)(const void FAR *)buf; dvander@27: while (len >= 32) { dvander@27: DOLIT32; dvander@27: len -= 32; dvander@27: } dvander@27: while (len >= 4) { dvander@27: DOLIT4; dvander@27: len -= 4; dvander@27: } dvander@27: buf = (const unsigned char FAR *)buf4; dvander@27: dvander@27: if (len) do { dvander@27: c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); dvander@27: } while (--len); dvander@27: c = ~c; dvander@27: return (unsigned long)c; dvander@27: } dvander@27: dvander@27: /* ========================================================================= */ dvander@27: #define DOBIG4 c ^= *++buf4; \ dvander@27: c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ dvander@27: crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] dvander@27: #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 dvander@27: dvander@27: /* ========================================================================= */ dvander@27: local unsigned long crc32_big(crc, buf, len) dvander@27: unsigned long crc; dvander@27: const unsigned char FAR *buf; dvander@27: unsigned len; dvander@27: { dvander@27: register u4 c; dvander@27: register const u4 FAR *buf4; dvander@27: dvander@27: c = REV((u4)crc); dvander@27: c = ~c; dvander@27: while (len && ((ptrdiff_t)buf & 3)) { dvander@27: c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); dvander@27: len--; dvander@27: } dvander@27: dvander@27: buf4 = (const u4 FAR *)(const void FAR *)buf; dvander@27: buf4--; dvander@27: while (len >= 32) { dvander@27: DOBIG32; dvander@27: len -= 32; dvander@27: } dvander@27: while (len >= 4) { dvander@27: DOBIG4; dvander@27: len -= 4; dvander@27: } dvander@27: buf4++; dvander@27: buf = (const unsigned char FAR *)buf4; dvander@27: dvander@27: if (len) do { dvander@27: c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); dvander@27: } while (--len); dvander@27: c = ~c; dvander@27: return (unsigned long)(REV(c)); dvander@27: } dvander@27: dvander@27: #endif /* BYFOUR */ dvander@27: dvander@27: #define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ dvander@27: dvander@27: /* ========================================================================= */ dvander@27: local unsigned long gf2_matrix_times(mat, vec) dvander@27: unsigned long *mat; dvander@27: unsigned long vec; dvander@27: { dvander@27: unsigned long sum; dvander@27: dvander@27: sum = 0; dvander@27: while (vec) { dvander@27: if (vec & 1) dvander@27: sum ^= *mat; dvander@27: vec >>= 1; dvander@27: mat++; dvander@27: } dvander@27: return sum; dvander@27: } dvander@27: dvander@27: /* ========================================================================= */ dvander@27: local void gf2_matrix_square(square, mat) dvander@27: unsigned long *square; dvander@27: unsigned long *mat; dvander@27: { dvander@27: int n; dvander@27: dvander@27: for (n = 0; n < GF2_DIM; n++) dvander@27: square[n] = gf2_matrix_times(mat, mat[n]); dvander@27: } dvander@27: dvander@27: /* ========================================================================= */ dvander@27: uLong ZEXPORT crc32_combine(crc1, crc2, len2) dvander@27: uLong crc1; dvander@27: uLong crc2; dvander@27: z_off_t len2; dvander@27: { dvander@27: int n; dvander@27: unsigned long row; dvander@27: unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ dvander@27: unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ dvander@27: dvander@27: /* degenerate case */ dvander@27: if (len2 == 0) dvander@27: return crc1; dvander@27: dvander@27: /* put operator for one zero bit in odd */ dvander@27: odd[0] = 0xedb88320L; /* CRC-32 polynomial */ dvander@27: row = 1; dvander@27: for (n = 1; n < GF2_DIM; n++) { dvander@27: odd[n] = row; dvander@27: row <<= 1; dvander@27: } dvander@27: dvander@27: /* put operator for two zero bits in even */ dvander@27: gf2_matrix_square(even, odd); dvander@27: dvander@27: /* put operator for four zero bits in odd */ dvander@27: gf2_matrix_square(odd, even); dvander@27: dvander@27: /* apply len2 zeros to crc1 (first square will put the operator for one dvander@27: zero byte, eight zero bits, in even) */ dvander@27: do { dvander@27: /* apply zeros operator for this bit of len2 */ dvander@27: gf2_matrix_square(even, odd); dvander@27: if (len2 & 1) dvander@27: crc1 = gf2_matrix_times(even, crc1); dvander@27: len2 >>= 1; dvander@27: dvander@27: /* if no more bits set, then done */ dvander@27: if (len2 == 0) dvander@27: break; dvander@27: dvander@27: /* another iteration of the loop with odd and even swapped */ dvander@27: gf2_matrix_square(odd, even); dvander@27: if (len2 & 1) dvander@27: crc1 = gf2_matrix_times(odd, crc1); dvander@27: len2 >>= 1; dvander@27: dvander@27: /* if no more bits set, then done */ dvander@27: } while (len2 != 0); dvander@27: dvander@27: /* return combined crc */ dvander@27: crc1 ^= crc2; dvander@27: return crc1; dvander@27: }