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