diff options
Diffstat (limited to 'dep/src/zlib/crc32.c')
| -rw-r--r-- | dep/src/zlib/crc32.c | 56 |
1 files changed, 0 insertions, 56 deletions
diff --git a/dep/src/zlib/crc32.c b/dep/src/zlib/crc32.c index f658a9ef55e..8838c354a4e 100644 --- a/dep/src/zlib/crc32.c +++ b/dep/src/zlib/crc32.c @@ -8,9 +8,7 @@ * 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 @@ -18,18 +16,14 @@ 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 */ @@ -50,7 +44,6 @@ # endif # endif /* STDC */ #endif /* !NOBYFOUR */ - /* Definitions for doing the crc four data bytes at a time. */ #ifdef BYFOUR # define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \ @@ -63,14 +56,11 @@ #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)); - #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)); @@ -80,7 +70,6 @@ local void make_crc_table OF((void)); /* 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 @@ -88,7 +77,6 @@ local void make_crc_table OF((void)); 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 @@ -96,7 +84,6 @@ local void make_crc_table OF((void)); 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 @@ -111,18 +98,15 @@ local void make_crc_table() /* 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; @@ -130,7 +114,6 @@ local void make_crc_table() 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 */ @@ -144,7 +127,6 @@ local void make_crc_table() } } #endif /* BYFOUR */ - crc_table_empty = 0; } else { /* not first */ @@ -152,12 +134,10 @@ local void make_crc_table() 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"); @@ -178,27 +158,23 @@ local void make_crc_table() } #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() */ @@ -210,11 +186,9 @@ const unsigned long FAR * ZEXPORT get_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; @@ -222,16 +196,13 @@ unsigned long ZEXPORT crc32(crc, buf, len) unsigned 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); @@ -249,15 +220,12 @@ unsigned long ZEXPORT crc32(crc, buf, len) } 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; @@ -266,14 +234,12 @@ local unsigned long crc32_little(crc, buf, 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; @@ -284,20 +250,17 @@ local unsigned long crc32_little(crc, buf, len) 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; @@ -306,14 +269,12 @@ local unsigned long crc32_big(crc, buf, 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) { @@ -326,25 +287,20 @@ local unsigned long crc32_big(crc, buf, len) } 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) @@ -354,18 +310,15 @@ local unsigned long gf2_matrix_times(mat, vec) } 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]); } - /* ========================================================================= */ uLong ZEXPORT crc32_combine(crc1, crc2, len2) uLong crc1; @@ -376,11 +329,9 @@ uLong ZEXPORT crc32_combine(crc1, crc2, len2) 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 */ if (len2 == 0) return crc1; - /* put operator for one zero bit in odd */ odd[0] = 0xedb88320L; /* CRC-32 polynomial */ row = 1; @@ -388,13 +339,10 @@ uLong ZEXPORT crc32_combine(crc1, crc2, len2) 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 { @@ -403,20 +351,16 @@ uLong ZEXPORT crc32_combine(crc1, crc2, len2) 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; |