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