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