2a60e63ce06684b7e9a6a74a07ccffe339a6bbb4Neil Madden

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunnington

124697010df6ca68fe3ecd0c6f5a77bf59777354Andrew Forrest

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington#ifdef MAKECRCH

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington# include <stdio.h>

0fb4093da08d574d3d1b661d4425dfbac8e02aabJames Phillpotts# ifndef DYNAMIC_CRC_TABLE

0fb4093da08d574d3d1b661d4425dfbac8e02aabJames Phillpotts# define DYNAMIC_CRC_TABLE

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington# endif /* !DYNAMIC_CRC_TABLE */

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington#endif /* MAKECRCH */

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunnington#include "zutil.h" /* for STDC and FAR definitions */

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunnington

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunnington#define local static

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunnington

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunnington#if !defined(NOBYFOUR) && defined(Z_U4)

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington# define BYFOUR

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington#endif

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington#ifdef BYFOUR

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington local unsigned long crc32_little OF((unsigned long,

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington const unsigned char FAR *, unsigned));

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington local unsigned long crc32_big OF((unsigned long,

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington const unsigned char FAR *, unsigned));

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington# define TBLS 8

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington#else

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington# define TBLS 1

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington#endif /* BYFOUR */

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunningtonlocal unsigned long gf2_matrix_times OF((unsigned long *mat,

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington unsigned long vec));

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunningtonlocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunningtonlocal uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington

c49a898cb851f8fef7d7a6a9501c66b8f03ae05cPhill Cunnington#ifdef DYNAMIC_CRC_TABLE

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunnington

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunningtonlocal volatile int crc_table_empty = 1;

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunningtonlocal z_crc_t FAR crc_table[TBLS][256];

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunningtonlocal void make_crc_table OF((void));

2a60e63ce06684b7e9a6a74a07ccffe339a6bbb4Neil Madden#ifdef MAKECRCH

124697010df6ca68fe3ecd0c6f5a77bf59777354Andrew Forrest local void write_table OF((FILE *, const z_crc_t FAR *));

124697010df6ca68fe3ecd0c6f5a77bf59777354Andrew Forrest#endif /* MAKECRCH */

91a599b60b62e70c63f6f698aaac20b41ba12941Phill Cunningtonlocal void make_crc_table()

{

z_crc_t c;

int n, k;

z_crc_t 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

if (first) {

first = 0;

/* make exclusive-or pattern from polynomial (0xedb88320UL) */

poly = 0;

for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)

poly |= (z_crc_t)1 << (31 - p[n]);

/* generate a crc for every 8-bit value */

for (n = 0; n < 256; n++) {

c = (z_crc_t)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,

for (n = 0; n < 256; n++) {

c = crc_table[0][n];

crc_table[4][n] = ZSWAP32(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] = ZSWAP32(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 z_crc_t 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 z_crc_t FAR *table;

{

int n;

for (n = 0; n < 256; n++)

fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ",

(unsigned long)(table[n]),

n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));

}

#endif /* MAKECRCH */

#else /* !DYNAMIC_CRC_TABLE */

#include "crc32.h"

#endif /* DYNAMIC_CRC_TABLE */

const z_crc_t FAR * ZEXPORT get_crc_table()

{

#ifdef DYNAMIC_CRC_TABLE

if (crc_table_empty)

make_crc_table();

#endif /* DYNAMIC_CRC_TABLE */

return (const z_crc_t 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)) {

z_crc_t 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 z_crc_t c;

register const z_crc_t FAR *buf4;

c = (z_crc_t)crc;

c = ~c;

while (len && ((ptrdiff_t)buf & 3)) {

c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);

len--;

}

buf4 = (const z_crc_t 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 z_crc_t c;

register const z_crc_t FAR *buf4;

c = ZSWAP32((z_crc_t)crc);

c = ~c;

while (len && ((ptrdiff_t)buf & 3)) {

c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);

len--;

}

buf4 = (const z_crc_t 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)(ZSWAP32(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

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);

}