176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* crc32.c -- compute the CRC-32 of a data stream 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Copyright (C) 1995-2006, 2010 Mark Adler 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * For conditions of distribution and use, see copyright notice in zlib.h 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * tables for updating the shift register in one step with three exclusive-ors 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * instead of four steps with four exclusive-ors. This results in about a 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* @(#) $Id$ */ 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman protection on the static variables used to control the first-use generation 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman first call get_crc_table() to initialize the tables before allowing more than 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman one thread to use crc32(). 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef MAKECRCH 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# include <stdio.h> 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# ifndef DYNAMIC_CRC_TABLE 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# define DYNAMIC_CRC_TABLE 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# endif /* !DYNAMIC_CRC_TABLE */ 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* MAKECRCH */ 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include "zutil.h" /* for STDC and FAR definitions */ 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define local static 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* Find a four-byte integer type for crc32_little() and crc32_big(). */ 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifndef NOBYFOUR 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# ifdef STDC /* need ANSI C limits.h to determine sizes */ 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# include <limits.h> 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# define BYFOUR 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# if (UINT_MAX == 0xffffffffUL) 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman typedef unsigned int u4; 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# else 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# if (ULONG_MAX == 0xffffffffUL) 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman typedef unsigned long u4; 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# else 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# if (USHRT_MAX == 0xffffffffUL) 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman typedef unsigned short u4; 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# else 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# undef BYFOUR /* can't find a four-byte integer type! */ 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# endif 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# endif 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# endif 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# endif /* STDC */ 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* !NOBYFOUR */ 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* Definitions for doing the crc four data bytes at a time. */ 5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef BYFOUR 5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# define REV(w) ((((w)>>24)&0xff)+(((w)>>8)&0xff00)+ \ 5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (((w)&0xff00)<<8)+(((w)&0xff)<<24)) 5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman local unsigned long crc32_little OF((unsigned long, 5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const unsigned char FAR *, unsigned)); 6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman local unsigned long crc32_big OF((unsigned long, 6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const unsigned char FAR *, unsigned)); 6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# define TBLS 8 6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#else 6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# define TBLS 1 6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* BYFOUR */ 6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* Local functions for crc concatenation */ 6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal unsigned long gf2_matrix_times OF((unsigned long *mat, 6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long vec)); 7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal uLong crc32_combine_(uLong crc1, uLong crc2, z_off64_t len2); 7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DYNAMIC_CRC_TABLE 7576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal volatile int crc_table_empty = 1; 7776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal unsigned long FAR crc_table[TBLS][256]; 7876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal void make_crc_table OF((void)); 7976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef MAKECRCH 8076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman local void write_table OF((FILE *, const unsigned long FAR *)); 8176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* MAKECRCH */ 8276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 8376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 8476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 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. 8576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 8676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman Polynomials over GF(2) are represented in binary, one bit per coefficient, 8776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman with the lowest powers in the most significant bit. Then adding polynomials 8876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman is just exclusive-or, and multiplying a polynomial by x is a right shift by 8976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman one. If we call the above polynomial p, and represent a byte as the 9076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman polynomial q, also with the lowest power in the most significant bit (so the 9176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 9276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman where a mod b means the remainder after dividing a by b. 9376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman This calculation is done using the shift-register method of multiplying and 9576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman taking the remainder. The register is initialized to zero, and for each 9676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman incoming bit, x^32 is added mod p to the register if the bit is a one (where 9776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 9876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman x (which is shifting right by one and adding x^32 mod p if the bit shifted 9976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman out is a one). We start with the highest power (least significant bit) of 10076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman q and repeat for all eight bits of q. 10176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman The first table is simply the CRC of all possible eight bit values. This is 10376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman all the information needed to generate CRCs on data a byte at a time for all 10476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman combinations of CRC register values and incoming bytes. The remaining tables 10576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman allow for word-at-a-time CRC calculation for both big-endian and little- 10676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman endian machines, where a word is four bytes. 10776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman*/ 10876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal void make_crc_table() 10976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 11076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long c; 11176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int n, k; 11276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long poly; /* polynomial exclusive-or pattern */ 11376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* terms of polynomial defining this crc (except x^32): */ 11476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman static volatile int first = 1; /* flag to limit concurrent making */ 11576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 11676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* See if another task is already doing this (not thread-safe, but better 11876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman than nothing -- significantly reduces duration of vulnerability in 11976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman case the advice about DYNAMIC_CRC_TABLE is ignored) */ 12076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (first) { 12176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman first = 0; 12276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 12476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman poly = 0UL; 12576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) 12676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman poly |= 1UL << (31 - p[n]); 12776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 12876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* generate a crc for every 8-bit value */ 12976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (n = 0; n < 256; n++) { 13076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = (unsigned long)n; 13176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (k = 0; k < 8; k++) 13276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = c & 1 ? poly ^ (c >> 1) : c >> 1; 13376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc_table[0][n] = c; 13476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 13576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef BYFOUR 13776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* generate crc for each value followed by one, two, and three zeros, 13876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman and then the byte reversal of those as well as the first table */ 13976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (n = 0; n < 256; n++) { 14076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[0][n]; 14176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc_table[4][n] = REV(c); 14276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (k = 1; k < 4; k++) { 14376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[0][c & 0xff] ^ (c >> 8); 14476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc_table[k][n] = c; 14576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc_table[k + 4][n] = REV(c); 14676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 14776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 14876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* BYFOUR */ 14976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc_table_empty = 0; 15176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 15276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else { /* not first */ 15376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* wait for the other guy to finish (not efficient, but rare) */ 15476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (crc_table_empty) 15576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ; 15676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 15776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef MAKECRCH 15976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* write out CRC tables to crc32.h */ 16076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 16176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman FILE *out; 16276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 16376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman out = fopen("crc32.h", "w"); 16476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (out == NULL) return; 16576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 16676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 16776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, "local const unsigned long FAR "); 16876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 16976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman write_table(out, crc_table[0]); 17076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# ifdef BYFOUR 17176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, "#ifdef BYFOUR\n"); 17276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (k = 1; k < 8; k++) { 17376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, " },\n {\n"); 17476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman write_table(out, crc_table[k]); 17576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 17676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, "#endif\n"); 17776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman# endif /* BYFOUR */ 17876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, " }\n};\n"); 17976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fclose(out); 18076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 18176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* MAKECRCH */ 18276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 18376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 18476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef MAKECRCH 18576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal void write_table(out, table) 18676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman FILE *out; 18776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const unsigned long FAR *table; 18876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 18976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int n; 19076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 19176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (n = 0; n < 256; n++) 19276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], 19376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 19476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 19576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* MAKECRCH */ 19676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 19776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#else /* !DYNAMIC_CRC_TABLE */ 19876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ======================================================================== 19976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 20076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 20176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include "crc32.h" 20276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* DYNAMIC_CRC_TABLE */ 20376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 20476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= 20576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * This function can be used by asm versions of crc32() 20676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 20776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanconst unsigned long FAR * ZEXPORT get_crc_table() 20876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 20976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DYNAMIC_CRC_TABLE 21076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (crc_table_empty) 21176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman make_crc_table(); 21276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* DYNAMIC_CRC_TABLE */ 21376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return (const unsigned long FAR *)crc_table; 21476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 21576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 21676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 21776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 21876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 21976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 22076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 22176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanunsigned long ZEXPORT crc32(crc, buf, len) 22276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long crc; 22376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const unsigned char FAR *buf; 22476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uInt len; 22576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 22676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (buf == Z_NULL) return 0UL; 22776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 22876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef DYNAMIC_CRC_TABLE 22976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (crc_table_empty) 23076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman make_crc_table(); 23176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* DYNAMIC_CRC_TABLE */ 23276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 23376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef BYFOUR 23476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (sizeof(void *) == sizeof(ptrdiff_t)) { 23576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman u4 endian; 23676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 23776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman endian = 1; 23876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (*((unsigned char *)(&endian))) 23976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return crc32_little(crc, buf, len); 24076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 24176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return crc32_big(crc, buf, len); 24276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 24376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* BYFOUR */ 24476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc = crc ^ 0xffffffffUL; 24576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (len >= 8) { 24676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DO8; 24776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len -= 8; 24876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 24976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (len) do { 25076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DO1; 25176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } while (--len); 25276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return crc ^ 0xffffffffUL; 25376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 25476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 25576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef BYFOUR 25676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 25776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 25876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define DOLIT4 c ^= *buf4++; \ 25976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 26076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 26176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 26276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 26376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 26476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal unsigned long crc32_little(crc, buf, len) 26576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long crc; 26676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const unsigned char FAR *buf; 26776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned len; 26876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 26976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman register u4 c; 27076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman register const u4 FAR *buf4; 27176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 27276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = (u4)crc; 27376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = ~c; 27476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (len && ((ptrdiff_t)buf & 3)) { 27576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 27676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len--; 27776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 27876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 27976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman buf4 = (const u4 FAR *)(const void FAR *)buf; 28076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (len >= 32) { 28176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DOLIT32; 28276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len -= 32; 28376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 28476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (len >= 4) { 28576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DOLIT4; 28676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len -= 4; 28776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 28876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman buf = (const unsigned char FAR *)buf4; 28976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 29076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (len) do { 29176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 29276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } while (--len); 29376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = ~c; 29476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return (unsigned long)c; 29576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 29676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 29776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 29876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define DOBIG4 c ^= *++buf4; \ 29976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 30076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 30176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 30276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 30376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 30476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal unsigned long crc32_big(crc, buf, len) 30576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long crc; 30676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman const unsigned char FAR *buf; 30776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned len; 30876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 30976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman register u4 c; 31076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman register const u4 FAR *buf4; 31176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 31276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = REV((u4)crc); 31376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = ~c; 31476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (len && ((ptrdiff_t)buf & 3)) { 31576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 31676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len--; 31776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 31876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 31976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman buf4 = (const u4 FAR *)(const void FAR *)buf; 32076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman buf4--; 32176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (len >= 32) { 32276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DOBIG32; 32376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len -= 32; 32476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 32576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (len >= 4) { 32676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman DOBIG4; 32776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len -= 4; 32876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 32976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman buf4++; 33076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman buf = (const unsigned char FAR *)buf4; 33176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 33276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (len) do { 33376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 33476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } while (--len); 33576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman c = ~c; 33676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return (unsigned long)(REV(c)); 33776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 33876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 33976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* BYFOUR */ 34076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 34176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 34276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 34376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 34476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal unsigned long gf2_matrix_times(mat, vec) 34576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long *mat; 34676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long vec; 34776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 34876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long sum; 34976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 35076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sum = 0; 35176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (vec) { 35276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (vec & 1) 35376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman sum ^= *mat; 35476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman vec >>= 1; 35576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman mat++; 35676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 35776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return sum; 35876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 35976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 36076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 36176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal void gf2_matrix_square(square, mat) 36276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long *square; 36376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long *mat; 36476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 36576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int n; 36676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 36776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (n = 0; n < GF2_DIM; n++) 36876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman square[n] = gf2_matrix_times(mat, mat[n]); 36976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 37076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 37176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 37276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanlocal uLong crc32_combine_(crc1, crc2, len2) 37376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uLong crc1; 37476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uLong crc2; 37576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman z_off64_t len2; 37676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 37776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman int n; 37876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long row; 37976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 38076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 38176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 38276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* degenerate case (also disallow negative lengths) */ 38376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (len2 <= 0) 38476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return crc1; 38576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 38676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* put operator for one zero bit in odd */ 38776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 38876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman row = 1; 38976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman for (n = 1; n < GF2_DIM; n++) { 39076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman odd[n] = row; 39176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman row <<= 1; 39276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 39376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 39476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* put operator for two zero bits in even */ 39576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman gf2_matrix_square(even, odd); 39676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 39776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* put operator for four zero bits in odd */ 39876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman gf2_matrix_square(odd, even); 39976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 40076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* apply len2 zeros to crc1 (first square will put the operator for one 40176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman zero byte, eight zero bits, in even) */ 40276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman do { 40376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* apply zeros operator for this bit of len2 */ 40476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman gf2_matrix_square(even, odd); 40576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (len2 & 1) 40676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc1 = gf2_matrix_times(even, crc1); 40776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len2 >>= 1; 40876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 40976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* if no more bits set, then done */ 41076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (len2 == 0) 41176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman break; 41276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 41376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* another iteration of the loop with odd and even swapped */ 41476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman gf2_matrix_square(odd, even); 41576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (len2 & 1) 41676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc1 = gf2_matrix_times(odd, crc1); 41776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman len2 >>= 1; 41876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 41976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* if no more bits set, then done */ 42076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } while (len2 != 0); 42176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 42276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* return combined crc */ 42376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman crc1 ^= crc2; 42476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return crc1; 42576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 42676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 42776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ========================================================================= */ 42876d05dc695b06c4e987bb8078f78032441e1430cGreg HartmanuLong ZEXPORT crc32_combine(crc1, crc2, len2) 42976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uLong crc1; 43076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uLong crc2; 43176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman z_off_t len2; 43276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 43376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return crc32_combine_(crc1, crc2, len2); 43476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 43576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 43676d05dc695b06c4e987bb8078f78032441e1430cGreg HartmanuLong ZEXPORT crc32_combine64(crc1, crc2, len2) 43776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uLong crc1; 43876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman uLong crc2; 43976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman z_off64_t len2; 44076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 44176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return crc32_combine_(crc1, crc2, len2); 44276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 443