src/zlib/crc32.c

/* crc32.c -- compute the CRC-32 of a data stream
 * Copyright (C) 1995-2003 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 about a factor
 * of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
 */

/* @(#) $Id$ */

#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 */

#ifdef DYNAMIC_CRC_TABLE

local 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 const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

    /* 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;

#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 *)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 *)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 */
Commit	Line	Data
	1	/* crc32.c -- compute the CRC-32 of a data stream
	2	* Copyright (C) 1995-2003 Mark Adler
	3	* For conditions of distribution and use, see copyright notice in zlib.h
	4	*
	5	* Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
	6	* CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
	7	* tables for updating the shift register in one step with three exclusive-ors
	8	* instead of four steps with four exclusive-ors. This results about a factor
	9	* of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
	10	*/
	11
	12	/* @(#) $Id$ */
	13
	14	#ifdef MAKECRCH
	15	# include <stdio.h>
	16	# ifndef DYNAMIC_CRC_TABLE
	17	# define DYNAMIC_CRC_TABLE
	18	# endif /* !DYNAMIC_CRC_TABLE */
	19	#endif /* MAKECRCH */
	20
	21	#include "zutil.h" /* for STDC and FAR definitions */
	22
	23	#define local static
	24
	25	/* Find a four-byte integer type for crc32_little() and crc32_big(). */
	26	#ifndef NOBYFOUR
	27	# ifdef STDC /* need ANSI C limits.h to determine sizes */
	28	# include <limits.h>
	29	# define BYFOUR
	30	# if (UINT_MAX == 0xffffffffUL)
	31	typedef unsigned int u4;
	32	# else
	33	# if (ULONG_MAX == 0xffffffffUL)
	34	typedef unsigned long u4;
	35	# else
	36	# if (USHRT_MAX == 0xffffffffUL)
	37	typedef unsigned short u4;
	38	# else
	39	# undef BYFOUR /* can't find a four-byte integer type! */
	40	# endif
	41	# endif
	42	# endif
	43	# endif /* STDC */
	44	#endif /* !NOBYFOUR */
	45
	46	/* Definitions for doing the crc four data bytes at a time. */
	47	#ifdef BYFOUR
	48	# define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
	49	(((w)&0xff00)<<8)+(((w)&0xff)<<24))
	50	local unsigned long crc32_little OF((unsigned long,
	51	const unsigned char FAR *, unsigned));
	52	local unsigned long crc32_big OF((unsigned long,
	53	const unsigned char FAR *, unsigned));
	54	# define TBLS 8
	55	#else
	56	# define TBLS 1
	57	#endif /* BYFOUR */
	58
	59	#ifdef DYNAMIC_CRC_TABLE
	60
	61	local int crc_table_empty = 1;
	62	local unsigned long FAR crc_table[TBLS][256];
	63	local void make_crc_table OF((void));
	64	#ifdef MAKECRCH
	65	local void write_table OF((FILE , const unsigned long FAR ));
	66	#endif /* MAKECRCH */
	67
	68	/*
	69	Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
	70	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.
	71
	72	Polynomials over GF(2) are represented in binary, one bit per coefficient,
	73	with the lowest powers in the most significant bit. Then adding polynomials
	74	is just exclusive-or, and multiplying a polynomial by x is a right shift by
	75	one. If we call the above polynomial p, and represent a byte as the
	76	polynomial q, also with the lowest power in the most significant bit (so the
	77	byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
	78	where a mod b means the remainder after dividing a by b.
	79
	80	This calculation is done using the shift-register method of multiplying and
	81	taking the remainder. The register is initialized to zero, and for each
	82	incoming bit, x^32 is added mod p to the register if the bit is a one (where
	83	x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
	84	x (which is shifting right by one and adding x^32 mod p if the bit shifted
	85	out is a one). We start with the highest power (least significant bit) of
	86	q and repeat for all eight bits of q.
	87
	88	The first table is simply the CRC of all possible eight bit values. This is
	89	all the information needed to generate CRCs on data a byte at a time for all
	90	combinations of CRC register values and incoming bytes. The remaining tables
	91	allow for word-at-a-time CRC calculation for both big-endian and little-
	92	endian machines, where a word is four bytes.
	93	*/
	94	local void make_crc_table()
	95	{
	96	unsigned long c;
	97	int n, k;
	98	unsigned long poly; /* polynomial exclusive-or pattern */
	99	/* terms of polynomial defining this crc (except x^32): */
	100	static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
	101
	102	/* make exclusive-or pattern from polynomial (0xedb88320UL) */
	103	poly = 0UL;
	104	for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
	105	poly \|= 1UL << (31 - p[n]);
	106
	107	/* generate a crc for every 8-bit value */
	108	for (n = 0; n < 256; n++) {
	109	c = (unsigned long)n;
	110	for (k = 0; k < 8; k++)
	111	c = c & 1 ? poly ^ (c >> 1) : c >> 1;
	112	crc_table[0][n] = c;
	113	}
	114
	115	#ifdef BYFOUR
	116	/* generate crc for each value followed by one, two, and three zeros, and
	117	then the byte reversal of those as well as the first table */
	118	for (n = 0; n < 256; n++) {
	119	c = crc_table[0][n];
	120	crc_table[4][n] = REV(c);
	121	for (k = 1; k < 4; k++) {
	122	c = crc_table[0][c & 0xff] ^ (c >> 8);
	123	crc_table[k][n] = c;
	124	crc_table[k + 4][n] = REV(c);
	125	}
	126	}
	127	#endif /* BYFOUR */
	128
	129	crc_table_empty = 0;
	130
	131	#ifdef MAKECRCH
	132	/* write out CRC tables to crc32.h */
	133	{
	134	FILE *out;
	135
	136	out = fopen("crc32.h", "w");
	137	if (out == NULL) return;
	138	fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
	139	fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
	140	fprintf(out, "local const unsigned long FAR ");
	141	fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
	142	write_table(out, crc_table[0]);
	143	# ifdef BYFOUR
	144	fprintf(out, "#ifdef BYFOUR\n");
	145	for (k = 1; k < 8; k++) {
	146	fprintf(out, " },\n {\n");
	147	write_table(out, crc_table[k]);
	148	}
	149	fprintf(out, "#endif\n");
	150	# endif /* BYFOUR */
	151	fprintf(out, " }\n};\n");
	152	fclose(out);
	153	}
	154	#endif /* MAKECRCH */
	155	}
	156
	157	#ifdef MAKECRCH
	158	local void write_table(out, table)
	159	FILE *out;
	160	const unsigned long FAR *table;
	161	{
	162	int n;
	163
	164	for (n = 0; n < 256; n++)
	165	fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n],
	166	n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
	167	}
	168	#endif /* MAKECRCH */
	169
	170	#else /* !DYNAMIC_CRC_TABLE */
	171	/* ========================================================================
	172	* Tables of CRC-32s of all single-byte values, made by make_crc_table().
	173	*/
	174	#include "crc32.h"
	175	#endif /* DYNAMIC_CRC_TABLE */
	176
	177	/* =========================================================================
	178	* This function can be used by asm versions of crc32()
	179	*/
	180	const unsigned long FAR * ZEXPORT get_crc_table()
	181	{
	182	#ifdef DYNAMIC_CRC_TABLE
	183	if (crc_table_empty) make_crc_table();
	184	#endif /* DYNAMIC_CRC_TABLE */
	185	return (const unsigned long FAR *)crc_table;
	186	}
	187
	188	/* ========================================================================= */
	189	#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
	190	#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
	191
	192	/* ========================================================================= */
	193	unsigned long ZEXPORT crc32(crc, buf, len)
	194	unsigned long crc;
	195	const unsigned char FAR *buf;
	196	unsigned len;
	197	{
	198	if (buf == Z_NULL) return 0UL;
	199
	200	#ifdef DYNAMIC_CRC_TABLE
	201	if (crc_table_empty)
	202	make_crc_table();
	203	#endif /* DYNAMIC_CRC_TABLE */
	204
	205	#ifdef BYFOUR
	206	if (sizeof(void *) == sizeof(ptrdiff_t)) {
	207	u4 endian;
	208
	209	endian = 1;
	210	if (((unsigned char )(&endian)))
	211	return crc32_little(crc, buf, len);
	212	else
	213	return crc32_big(crc, buf, len);
	214	}
	215	#endif /* BYFOUR */
	216	crc = crc ^ 0xffffffffUL;
	217	while (len >= 8) {
	218	DO8;
	219	len -= 8;
	220	}
	221	if (len) do {
	222	DO1;
	223	} while (--len);
	224	return crc ^ 0xffffffffUL;
	225	}
	226
	227	#ifdef BYFOUR
	228
	229	/* ========================================================================= */
	230	#define DOLIT4 c ^= *buf4++; \
	231	c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
	232	crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
	233	#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
	234
	235	/* ========================================================================= */
	236	local unsigned long crc32_little(crc, buf, len)
	237	unsigned long crc;
	238	const unsigned char FAR *buf;
	239	unsigned len;
	240	{
	241	register u4 c;
	242	register const u4 FAR *buf4;
	243
	244	c = (u4)crc;
	245	c = ~c;
	246	while (len && ((ptrdiff_t)buf & 3)) {
	247	c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
	248	len--;
	249	}
	250
	251	buf4 = (const u4 FAR *)buf;
	252	while (len >= 32) {
	253	DOLIT32;
	254	len -= 32;
	255	}
	256	while (len >= 4) {
	257	DOLIT4;
	258	len -= 4;
	259	}
	260	buf = (const unsigned char FAR *)buf4;
	261
	262	if (len) do {
	263	c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
	264	} while (--len);
	265	c = ~c;
	266	return (unsigned long)c;
	267	}
	268
	269	/* ========================================================================= */
	270	#define DOBIG4 c ^= *++buf4; \
	271	c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
	272	crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
	273	#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
	274
	275	/* ========================================================================= */
	276	local unsigned long crc32_big(crc, buf, len)
	277	unsigned long crc;
	278	const unsigned char FAR *buf;
	279	unsigned len;
	280	{
	281	register u4 c;
	282	register const u4 FAR *buf4;
	283
	284	c = REV((u4)crc);
	285	c = ~c;
	286	while (len && ((ptrdiff_t)buf & 3)) {
	287	c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
	288	len--;
	289	}
	290
	291	buf4 = (const u4 FAR *)buf;
	292	buf4--;
	293	while (len >= 32) {
	294	DOBIG32;
	295	len -= 32;
	296	}
	297	while (len >= 4) {
	298	DOBIG4;
	299	len -= 4;
	300	}
	301	buf4++;
	302	buf = (const unsigned char FAR *)buf4;
	303
	304	if (len) do {
	305	c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
	306	} while (--len);
	307	c = ~c;
	308	return (unsigned long)(REV(c));
	309	}
	310
	311	#endif /* BYFOUR */