/* crc32.c -- compute the CRC-32 of a data stream | |
* Copyright (C) 1995-2005 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)+(((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)); | |
#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; | |
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); | |
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]); | |
} | |
/* ========================================================================= */ | |
uLong ZEXPORT crc32_combine(crc1, crc2, len2) | |
uLong crc1; | |
uLong crc2; | |
z_off_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 */ | |
if (len2 == 0) | |
return crc1; | |
/* put operator for one zero bit in odd */ | |
odd[0] = 0xedb88320L; /* 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; | |
} |