1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* crc32.c -- compute the CRC-32 of a data stream 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * For conditions of distribution and use, see copyright notice in zlib.h 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * tables for updating the shift register in one step with three exclusive-ors 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * instead of four steps with four exclusive-ors. This results in about a 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* @(#) $Id$ */ 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov protection on the static variables used to control the first-use generation 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov first call get_crc_table() to initialize the tables before allowing more than 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov one thread to use crc32(). 20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 21ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h. 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef MAKECRCH 25ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# include <stdio.h> 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# ifndef DYNAMIC_CRC_TABLE 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# define DYNAMIC_CRC_TABLE 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# endif /* !DYNAMIC_CRC_TABLE */ 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* MAKECRCH */ 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "zutil.h" /* for STDC and FAR definitions */ 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define local static 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Definitions for doing the crc four data bytes at a time. */ 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#if !defined(NOBYFOUR) && defined(Z_U4) 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# define BYFOUR 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef BYFOUR 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov local unsigned long crc32_little OF((unsigned long, 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const unsigned char FAR *, unsigned)); 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov local unsigned long crc32_big OF((unsigned long, 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const unsigned char FAR *, unsigned)); 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# define TBLS 8 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# define TBLS 1 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* BYFOUR */ 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Local functions for crc concatenation */ 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal unsigned long gf2_matrix_times OF((unsigned long *mat, 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long vec)); 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DYNAMIC_CRC_TABLE 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal volatile int crc_table_empty = 1; 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal z_crc_t FAR crc_table[TBLS][256]; 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void make_crc_table OF((void)); 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef MAKECRCH 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov local void write_table OF((FILE *, const z_crc_t FAR *)); 63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* MAKECRCH */ 64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* 65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 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. 67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Polynomials over GF(2) are represented in binary, one bit per coefficient, 69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov with the lowest powers in the most significant bit. Then adding polynomials 70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov is just exclusive-or, and multiplying a polynomial by x is a right shift by 71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov one. If we call the above polynomial p, and represent a byte as the 72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov polynomial q, also with the lowest power in the most significant bit (so the 73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov where a mod b means the remainder after dividing a by b. 75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov This calculation is done using the shift-register method of multiplying and 77ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov taking the remainder. The register is initialized to zero, and for each 78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov incoming bit, x^32 is added mod p to the register if the bit is a one (where 79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov x (which is shifting right by one and adding x^32 mod p if the bit shifted 81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov out is a one). We start with the highest power (least significant bit) of 82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q and repeat for all eight bits of q. 83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov The first table is simply the CRC of all possible eight bit values. This is 85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov all the information needed to generate CRCs on data a byte at a time for all 86ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov combinations of CRC register values and incoming bytes. The remaining tables 87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov allow for word-at-a-time CRC calculation for both big-endian and little- 88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov endian machines, where a word is four bytes. 89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov*/ 90ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void make_crc_table() 91ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov z_crc_t c; 93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n, k; 94ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov z_crc_t poly; /* polynomial exclusive-or pattern */ 95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* terms of polynomial defining this crc (except x^32): */ 96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static volatile int first = 1; /* flag to limit concurrent making */ 97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* See if another task is already doing this (not thread-safe, but better 100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov than nothing -- significantly reduces duration of vulnerability in 101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov case the advice about DYNAMIC_CRC_TABLE is ignored) */ 102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (first) { 103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov first = 0; 104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov poly = 0; 107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) 108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov poly |= (z_crc_t)1 << (31 - p[n]); 109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* generate a crc for every 8-bit value */ 111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < 256; n++) { 112ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = (z_crc_t)n; 113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (k = 0; k < 8; k++) 114ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = c & 1 ? poly ^ (c >> 1) : c >> 1; 115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc_table[0][n] = c; 116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 117ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 118ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef BYFOUR 119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* generate crc for each value followed by one, two, and three zeros, 120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov and then the byte reversal of those as well as the first table */ 121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < 256; n++) { 122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[0][n]; 123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc_table[4][n] = ZSWAP32(c); 124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (k = 1; k < 4; k++) { 125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[0][c & 0xff] ^ (c >> 8); 126ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc_table[k][n] = c; 127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc_table[k + 4][n] = ZSWAP32(c); 128ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* BYFOUR */ 131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc_table_empty = 0; 133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else { /* not first */ 135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* wait for the other guy to finish (not efficient, but rare) */ 136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (crc_table_empty) 137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ; 138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef MAKECRCH 141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* write out CRC tables to crc32.h */ 142ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 143ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FILE *out; 144ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 145ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov out = fopen("crc32.h", "w"); 146ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (out == NULL) return; 147ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 148ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 149ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, "local const z_crc_t FAR "); 150ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 151ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov write_table(out, crc_table[0]); 152ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# ifdef BYFOUR 153ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, "#ifdef BYFOUR\n"); 154ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (k = 1; k < 8; k++) { 155ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, " },\n {\n"); 156ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov write_table(out, crc_table[k]); 157ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 158ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, "#endif\n"); 159ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov# endif /* BYFOUR */ 160ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, " }\n};\n"); 161ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fclose(out); 162ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 163ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* MAKECRCH */ 164ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 165ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 166ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef MAKECRCH 167ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void write_table( 168ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FILE *out, 169ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const z_crc_t FAR *table) 170ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 171ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; 172ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 173ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < 256; n++) 174ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", 175ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (unsigned long)(table[n]), 176ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 177ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 178ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* MAKECRCH */ 179ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 180ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else /* !DYNAMIC_CRC_TABLE */ 181ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ======================================================================== 182ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 183ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 184ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "crc32.h" 185ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* DYNAMIC_CRC_TABLE */ 186ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 187ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= 188ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov * This function can be used by asm versions of crc32() 189ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov */ 190ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovconst z_crc_t FAR * ZEXPORT get_crc_table() 191ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 192ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DYNAMIC_CRC_TABLE 193ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (crc_table_empty) 194ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov make_crc_table(); 195ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* DYNAMIC_CRC_TABLE */ 196ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (const z_crc_t FAR *)crc_table; 197ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 198ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 199ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 200ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 201ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 202ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 203ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 204ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovunsigned long ZEXPORT crc32( 205ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long crc, 206ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const unsigned char FAR *buf, 207ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uInt len) 208ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 209ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (buf == Z_NULL) return 0UL; 210ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 211ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef DYNAMIC_CRC_TABLE 212ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (crc_table_empty) 213ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov make_crc_table(); 214ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* DYNAMIC_CRC_TABLE */ 215ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 216ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef BYFOUR 217ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (sizeof(void *) == sizeof(ptrdiff_t)) { 218ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov z_crc_t endian; 219ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 220ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov endian = 1; 221ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (*((unsigned char *)(&endian))) 222ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return crc32_little(crc, buf, len); 223ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else 224ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return crc32_big(crc, buf, len); 225ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 226ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* BYFOUR */ 227ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc = crc ^ 0xffffffffUL; 228ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len >= 8) { 229ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DO8; 230ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len -= 8; 231ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 232ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len) do { 233ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DO1; 234ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (--len); 235ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return crc ^ 0xffffffffUL; 236ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 237ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 238ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef BYFOUR 239ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 240ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 241ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define DOLIT4 c ^= *buf4++; \ 242ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 243ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 244ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 245ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 246ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 247ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal unsigned long crc32_little( 248ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long crc, 249ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const unsigned char FAR *buf, 250ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned len) 251ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 252ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov register z_crc_t c; 253ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov register const z_crc_t FAR *buf4; 254ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 255ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = (z_crc_t)crc; 256ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = ~c; 257ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len && ((ptrdiff_t)buf & 3)) { 258ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 259ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len--; 260ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 261ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 262ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 263ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len >= 32) { 264ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DOLIT32; 265ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len -= 32; 266ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 267ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len >= 4) { 268ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DOLIT4; 269ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len -= 4; 270ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 271ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov buf = (const unsigned char FAR *)buf4; 272ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 273ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len) do { 274ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 275ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (--len); 276ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = ~c; 277ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (unsigned long)c; 278ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 279ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 280ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 281ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define DOBIG4 c ^= *++buf4; \ 282ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 283ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 284ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 285ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 286ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 287ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal unsigned long crc32_big( 288ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long crc, 289ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov const unsigned char FAR *buf, 290ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned len) 291ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 292ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov register z_crc_t c; 293ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov register const z_crc_t FAR *buf4; 294ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 295ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = ZSWAP32((z_crc_t)crc); 296ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = ~c; 297ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len && ((ptrdiff_t)buf & 3)) { 298ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 299ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len--; 300ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 301ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 302ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 303ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov buf4--; 304ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len >= 32) { 305ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DOBIG32; 306ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len -= 32; 307ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 308ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (len >= 4) { 309ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov DOBIG4; 310ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len -= 4; 311ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 312ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov buf4++; 313ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov buf = (const unsigned char FAR *)buf4; 314ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 315ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len) do { 316ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 317ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (--len); 318ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c = ~c; 319ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return (unsigned long)(ZSWAP32(c)); 320ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 321ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 322ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif /* BYFOUR */ 323ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 324ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 325ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 326ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 327ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal unsigned long gf2_matrix_times( 328ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long *mat, 329ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long vec) 330ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 331ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long sum; 332ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 333ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov sum = 0; 334ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while (vec) { 335ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (vec & 1) 336ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov sum ^= *mat; 337ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov vec >>= 1; 338ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov mat++; 339ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 340ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return sum; 341ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 342ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 343ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 344ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal void gf2_matrix_square( 345ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long *square, 346ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long *mat) 347ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 348ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; 349ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 350ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 0; n < GF2_DIM; n++) 351ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov square[n] = gf2_matrix_times(mat, mat[n]); 352ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 353ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 354ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 355ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganovlocal uLong crc32_combine_( 356ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uLong crc1, 357ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uLong crc2, 358ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov z_off64_t len2) 359ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 360ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov int n; 361ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long row; 362ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 363ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 364ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 365ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* degenerate case (also disallow negative lengths) */ 366ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len2 <= 0) 367ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return crc1; 368ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 369ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* put operator for one zero bit in odd */ 370ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 371ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov row = 1; 372ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for (n = 1; n < GF2_DIM; n++) { 373ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov odd[n] = row; 374ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov row <<= 1; 375ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 376ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 377ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* put operator for two zero bits in even */ 378ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gf2_matrix_square(even, odd); 379ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 380ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* put operator for four zero bits in odd */ 381ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gf2_matrix_square(odd, even); 382ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 383ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* apply len2 zeros to crc1 (first square will put the operator for one 384ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov zero byte, eight zero bits, in even) */ 385ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov do { 386ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* apply zeros operator for this bit of len2 */ 387ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gf2_matrix_square(even, odd); 388ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len2 & 1) 389ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc1 = gf2_matrix_times(even, crc1); 390ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len2 >>= 1; 391ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 392ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* if no more bits set, then done */ 393ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len2 == 0) 394ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 395ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 396ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* another iteration of the loop with odd and even swapped */ 397ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov gf2_matrix_square(odd, even); 398ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if (len2 & 1) 399ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc1 = gf2_matrix_times(odd, crc1); 400ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov len2 >>= 1; 401ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 402ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* if no more bits set, then done */ 403ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } while (len2 != 0); 404ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 405ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* return combined crc */ 406ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov crc1 ^= crc2; 407ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return crc1; 408ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 409ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 410ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ========================================================================= */ 411ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovuLong ZEXPORT crc32_combine( 412ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uLong crc1, 413ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uLong crc2, 414ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov z_off_t len2) 415ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 416ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return crc32_combine_(crc1, crc2, len2); 417ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 418ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 419ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovuLong ZEXPORT crc32_combine64( 420ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uLong crc1, 421ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uLong crc2, 422ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov z_off64_t len2) 423ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov{ 424ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return crc32_combine_(crc1, crc2, len2); 425ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov} 426