1168404Spjd/* 2168404Spjd * Copyright 2007 Sun Microsystems, Inc. All rights reserved. 3168404Spjd * Use is subject to license terms. 4168404Spjd */ 5168404Spjd 6168404Spjd/* crc32.c -- compute the CRC-32 of a data stream 7168404Spjd * Copyright (C) 1995-2005 Mark Adler 8168404Spjd * For conditions of distribution and use, see copyright notice in zlib.h 9168404Spjd * 10168404Spjd * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 11168404Spjd * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 12168404Spjd * tables for updating the shift register in one step with three exclusive-ors 13168404Spjd * instead of four steps with four exclusive-ors. This results in about a 14168404Spjd * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 15168404Spjd */ 16168404Spjd 17168404Spjd#pragma ident "%Z%%M% %I% %E% SMI" 18168404Spjd 19168404Spjd/* 20168404Spjd Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 21168404Spjd protection on the static variables used to control the first-use generation 22168404Spjd of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 23168404Spjd first call get_crc_table() to initialize the tables before allowing more than 24168404Spjd one thread to use crc32(). 25168404Spjd */ 26168404Spjd 27168404Spjd#ifdef MAKECRCH 28168404Spjd# include <stdio.h> 29168404Spjd# ifndef DYNAMIC_CRC_TABLE 30168404Spjd# define DYNAMIC_CRC_TABLE 31168404Spjd# endif /* !DYNAMIC_CRC_TABLE */ 32168404Spjd#endif /* MAKECRCH */ 33168404Spjd 34168404Spjd#include "zutil.h" /* for STDC and FAR definitions */ 35168404Spjd 36168404Spjd#define local static 37168404Spjd 38168404Spjd/* Find a four-byte integer type for crc32_little() and crc32_big(). */ 39168404Spjd#ifndef NOBYFOUR 40168404Spjd# ifdef STDC /* need ANSI C limits.h to determine sizes */ 41168404Spjd# include <limits.h> 42168404Spjd# define BYFOUR 43168404Spjd# if (UINT_MAX == 0xffffffffUL) 44168404Spjd typedef unsigned int u4; 45168404Spjd# else 46168404Spjd# if (ULONG_MAX == 0xffffffffUL) 47168404Spjd typedef unsigned long u4; 48168404Spjd# else 49168404Spjd# if (USHRT_MAX == 0xffffffffUL) 50168404Spjd typedef unsigned short u4; 51168404Spjd# else 52168404Spjd# undef BYFOUR /* can't find a four-byte integer type! */ 53168404Spjd# endif 54168404Spjd# endif 55168404Spjd# endif 56168404Spjd# endif /* STDC */ 57168404Spjd#endif /* !NOBYFOUR */ 58168404Spjd 59168404Spjd/* Definitions for doing the crc four data bytes at a time. */ 60168404Spjd#ifdef BYFOUR 61168404Spjd# define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \ 62168404Spjd (((w)&0xff00)<<8)+(((w)&0xff)<<24)) 63168404Spjd local unsigned long crc32_little OF((unsigned long, 64168404Spjd const unsigned char FAR *, unsigned)); 65168404Spjd local unsigned long crc32_big OF((unsigned long, 66168404Spjd const unsigned char FAR *, unsigned)); 67168404Spjd# define TBLS 8 68168404Spjd#else 69168404Spjd# define TBLS 1 70168404Spjd#endif /* BYFOUR */ 71168404Spjd 72168404Spjd/* Local functions for crc concatenation */ 73168404Spjdlocal unsigned long gf2_matrix_times OF((unsigned long *mat, 74168404Spjd unsigned long vec)); 75168404Spjdlocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 76168404Spjd 77168404Spjd#ifdef DYNAMIC_CRC_TABLE 78168404Spjd 79168404Spjdlocal volatile int crc_table_empty = 1; 80168404Spjdlocal unsigned long FAR crc_table[TBLS][256]; 81168404Spjdlocal void make_crc_table OF((void)); 82168404Spjd#ifdef MAKECRCH 83168404Spjd local void write_table OF((FILE *, const unsigned long FAR *)); 84168404Spjd#endif /* MAKECRCH */ 85168404Spjd/* 86168404Spjd Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 87168404Spjd 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. 88168404Spjd 89168404Spjd Polynomials over GF(2) are represented in binary, one bit per coefficient, 90168404Spjd with the lowest powers in the most significant bit. Then adding polynomials 91168404Spjd is just exclusive-or, and multiplying a polynomial by x is a right shift by 92168404Spjd one. If we call the above polynomial p, and represent a byte as the 93168404Spjd polynomial q, also with the lowest power in the most significant bit (so the 94168404Spjd byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 95168404Spjd where a mod b means the remainder after dividing a by b. 96168404Spjd 97168404Spjd This calculation is done using the shift-register method of multiplying and 98168404Spjd taking the remainder. The register is initialized to zero, and for each 99168404Spjd incoming bit, x^32 is added mod p to the register if the bit is a one (where 100168404Spjd x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 101168404Spjd x (which is shifting right by one and adding x^32 mod p if the bit shifted 102168404Spjd out is a one). We start with the highest power (least significant bit) of 103168404Spjd q and repeat for all eight bits of q. 104168404Spjd 105168404Spjd The first table is simply the CRC of all possible eight bit values. This is 106168404Spjd all the information needed to generate CRCs on data a byte at a time for all 107168404Spjd combinations of CRC register values and incoming bytes. The remaining tables 108168404Spjd allow for word-at-a-time CRC calculation for both big-endian and little- 109168404Spjd endian machines, where a word is four bytes. 110168404Spjd*/ 111168404Spjdlocal void make_crc_table() 112168404Spjd{ 113168404Spjd unsigned long c; 114168404Spjd int n, k; 115168404Spjd unsigned long poly; /* polynomial exclusive-or pattern */ 116168404Spjd /* terms of polynomial defining this crc (except x^32): */ 117168404Spjd static volatile int first = 1; /* flag to limit concurrent making */ 118168404Spjd static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 119168404Spjd 120168404Spjd /* See if another task is already doing this (not thread-safe, but better 121168404Spjd than nothing -- significantly reduces duration of vulnerability in 122168404Spjd case the advice about DYNAMIC_CRC_TABLE is ignored) */ 123168404Spjd if (first) { 124168404Spjd first = 0; 125168404Spjd 126168404Spjd /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 127168404Spjd poly = 0UL; 128168404Spjd for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) 129168404Spjd poly |= 1UL << (31 - p[n]); 130168404Spjd 131168404Spjd /* generate a crc for every 8-bit value */ 132168404Spjd for (n = 0; n < 256; n++) { 133168404Spjd c = (unsigned long)n; 134168404Spjd for (k = 0; k < 8; k++) 135168404Spjd c = c & 1 ? poly ^ (c >> 1) : c >> 1; 136168404Spjd crc_table[0][n] = c; 137168404Spjd } 138168404Spjd 139168404Spjd#ifdef BYFOUR 140168404Spjd /* generate crc for each value followed by one, two, and three zeros, 141168404Spjd and then the byte reversal of those as well as the first table */ 142168404Spjd for (n = 0; n < 256; n++) { 143168404Spjd c = crc_table[0][n]; 144168404Spjd crc_table[4][n] = REV(c); 145168404Spjd for (k = 1; k < 4; k++) { 146168404Spjd c = crc_table[0][c & 0xff] ^ (c >> 8); 147168404Spjd crc_table[k][n] = c; 148168404Spjd crc_table[k + 4][n] = REV(c); 149168404Spjd } 150168404Spjd } 151168404Spjd#endif /* BYFOUR */ 152168404Spjd 153168404Spjd crc_table_empty = 0; 154168404Spjd } 155168404Spjd else { /* not first */ 156168404Spjd /* wait for the other guy to finish (not efficient, but rare) */ 157168404Spjd while (crc_table_empty) 158168404Spjd ; 159168404Spjd } 160168404Spjd 161168404Spjd#ifdef MAKECRCH 162168404Spjd /* write out CRC tables to crc32.h */ 163168404Spjd { 164168404Spjd FILE *out; 165168404Spjd 166168404Spjd out = fopen("crc32.h", "w"); 167168404Spjd if (out == NULL) return; 168168404Spjd fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 169168404Spjd fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 170168404Spjd fprintf(out, "local const unsigned long FAR "); 171168404Spjd fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 172168404Spjd write_table(out, crc_table[0]); 173168404Spjd# ifdef BYFOUR 174168404Spjd fprintf(out, "#ifdef BYFOUR\n"); 175168404Spjd for (k = 1; k < 8; k++) { 176168404Spjd fprintf(out, " },\n {\n"); 177168404Spjd write_table(out, crc_table[k]); 178168404Spjd } 179168404Spjd fprintf(out, "#endif\n"); 180168404Spjd# endif /* BYFOUR */ 181168404Spjd fprintf(out, " }\n};\n"); 182168404Spjd fclose(out); 183168404Spjd } 184168404Spjd#endif /* MAKECRCH */ 185168404Spjd} 186168404Spjd 187168404Spjd#ifdef MAKECRCH 188168404Spjdlocal void write_table(out, table) 189168404Spjd FILE *out; 190168404Spjd const unsigned long FAR *table; 191168404Spjd{ 192168404Spjd int n; 193168404Spjd 194168404Spjd for (n = 0; n < 256; n++) 195168404Spjd fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], 196168404Spjd n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 197168404Spjd} 198168404Spjd#endif /* MAKECRCH */ 199168404Spjd 200168404Spjd#else /* !DYNAMIC_CRC_TABLE */ 201168404Spjd/* ======================================================================== 202168404Spjd * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 203168404Spjd */ 204168404Spjd#include "crc32.h" 205168404Spjd#endif /* DYNAMIC_CRC_TABLE */ 206168404Spjd 207168404Spjd/* ========================================================================= 208168404Spjd * This function can be used by asm versions of crc32() 209168404Spjd */ 210168404Spjdconst unsigned long FAR * ZEXPORT get_crc_table() 211168404Spjd{ 212168404Spjd#ifdef DYNAMIC_CRC_TABLE 213168404Spjd if (crc_table_empty) 214168404Spjd make_crc_table(); 215168404Spjd#endif /* DYNAMIC_CRC_TABLE */ 216168404Spjd return (const unsigned long FAR *)crc_table; 217168404Spjd} 218168404Spjd 219168404Spjd/* ========================================================================= */ 220168404Spjd#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 221168404Spjd#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 222168404Spjd 223168404Spjd/* ========================================================================= */ 224168404Spjdunsigned long ZEXPORT crc32(crc, buf, len) 225168404Spjd unsigned long crc; 226168404Spjd const unsigned char FAR *buf; 227168404Spjd unsigned len; 228168404Spjd{ 229168404Spjd if (buf == Z_NULL) return 0UL; 230168404Spjd 231168404Spjd#ifdef DYNAMIC_CRC_TABLE 232168404Spjd if (crc_table_empty) 233168404Spjd make_crc_table(); 234168404Spjd#endif /* DYNAMIC_CRC_TABLE */ 235168404Spjd 236168404Spjd#ifdef BYFOUR 237168404Spjd if (sizeof(void *) == sizeof(ptrdiff_t)) { 238168404Spjd u4 endian; 239168404Spjd 240168404Spjd endian = 1; 241168404Spjd if (*((unsigned char *)(&endian))) 242168404Spjd return crc32_little(crc, buf, len); 243168404Spjd else 244168404Spjd return crc32_big(crc, buf, len); 245168404Spjd } 246168404Spjd#endif /* BYFOUR */ 247168404Spjd crc = crc ^ 0xffffffffUL; 248168404Spjd while (len >= 8) { 249168404Spjd DO8; 250168404Spjd len -= 8; 251168404Spjd } 252168404Spjd if (len) do { 253168404Spjd DO1; 254168404Spjd } while (--len); 255168404Spjd return crc ^ 0xffffffffUL; 256168404Spjd} 257168404Spjd 258168404Spjd#ifdef BYFOUR 259168404Spjd 260168404Spjd/* ========================================================================= */ 261168404Spjd#define DOLIT4 c ^= *buf4++; \ 262168404Spjd c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 263168404Spjd crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 264168404Spjd#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 265168404Spjd 266168404Spjd/* ========================================================================= */ 267168404Spjdlocal unsigned long crc32_little(crc, buf, len) 268168404Spjd unsigned long crc; 269168404Spjd const unsigned char FAR *buf; 270168404Spjd unsigned len; 271168404Spjd{ 272168404Spjd register u4 c; 273168404Spjd register const u4 FAR *buf4; 274168404Spjd 275168404Spjd c = (u4)crc; 276168404Spjd c = ~c; 277168404Spjd while (len && ((ptrdiff_t)buf & 3)) { 278168404Spjd c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 279168404Spjd len--; 280168404Spjd } 281168404Spjd 282168404Spjd buf4 = (const u4 FAR *)(const void FAR *)buf; 283168404Spjd while (len >= 32) { 284168404Spjd DOLIT32; 285168404Spjd len -= 32; 286168404Spjd } 287168404Spjd while (len >= 4) { 288168404Spjd DOLIT4; 289168404Spjd len -= 4; 290168404Spjd } 291168404Spjd buf = (const unsigned char FAR *)buf4; 292168404Spjd 293168404Spjd if (len) do { 294168404Spjd c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 295168404Spjd } while (--len); 296168404Spjd c = ~c; 297168404Spjd return (unsigned long)c; 298168404Spjd} 299168404Spjd 300168404Spjd/* ========================================================================= */ 301168404Spjd#define DOBIG4 c ^= *++buf4; \ 302168404Spjd c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 303168404Spjd crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 304168404Spjd#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 305168404Spjd 306168404Spjd/* ========================================================================= */ 307168404Spjdlocal unsigned long crc32_big(crc, buf, len) 308168404Spjd unsigned long crc; 309168404Spjd const unsigned char FAR *buf; 310168404Spjd unsigned len; 311168404Spjd{ 312168404Spjd register u4 c; 313168404Spjd register const u4 FAR *buf4; 314168404Spjd 315168404Spjd c = REV((u4)crc); 316168404Spjd c = ~c; 317168404Spjd while (len && ((ptrdiff_t)buf & 3)) { 318168404Spjd c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 319168404Spjd len--; 320168404Spjd } 321168404Spjd 322168404Spjd buf4 = (const u4 FAR *)(const void FAR *)buf; 323168404Spjd buf4--; 324168404Spjd while (len >= 32) { 325168404Spjd DOBIG32; 326168404Spjd len -= 32; 327168404Spjd } 328168404Spjd while (len >= 4) { 329168404Spjd DOBIG4; 330168404Spjd len -= 4; 331168404Spjd } 332168404Spjd buf4++; 333168404Spjd buf = (const unsigned char FAR *)buf4; 334168404Spjd 335168404Spjd if (len) do { 336168404Spjd c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 337168404Spjd } while (--len); 338168404Spjd c = ~c; 339168404Spjd return (unsigned long)(REV(c)); 340168404Spjd} 341168404Spjd 342168404Spjd#endif /* BYFOUR */ 343168404Spjd 344168404Spjd#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 345168404Spjd 346168404Spjd/* ========================================================================= */ 347168404Spjdlocal unsigned long gf2_matrix_times(mat, vec) 348168404Spjd unsigned long *mat; 349168404Spjd unsigned long vec; 350168404Spjd{ 351168404Spjd unsigned long sum; 352168404Spjd 353168404Spjd sum = 0; 354168404Spjd while (vec) { 355168404Spjd if (vec & 1) 356168404Spjd sum ^= *mat; 357168404Spjd vec >>= 1; 358168404Spjd mat++; 359168404Spjd } 360168404Spjd return sum; 361168404Spjd} 362168404Spjd 363168404Spjd/* ========================================================================= */ 364168404Spjdlocal void gf2_matrix_square(square, mat) 365168404Spjd unsigned long *square; 366168404Spjd unsigned long *mat; 367168404Spjd{ 368168404Spjd int n; 369168404Spjd 370168404Spjd for (n = 0; n < GF2_DIM; n++) 371168404Spjd square[n] = gf2_matrix_times(mat, mat[n]); 372168404Spjd} 373168404Spjd 374168404Spjd/* ========================================================================= */ 375168404SpjduLong ZEXPORT crc32_combine(crc1, crc2, len2) 376168404Spjd uLong crc1; 377168404Spjd uLong crc2; 378168404Spjd z_off_t len2; 379168404Spjd{ 380168404Spjd int n; 381168404Spjd unsigned long row; 382168404Spjd unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 383168404Spjd unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 384168404Spjd 385168404Spjd /* degenerate case */ 386168404Spjd if (len2 == 0) 387168404Spjd return crc1; 388168404Spjd 389168404Spjd /* put operator for one zero bit in odd */ 390168404Spjd odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 391168404Spjd row = 1; 392168404Spjd for (n = 1; n < GF2_DIM; n++) { 393168404Spjd odd[n] = row; 394168404Spjd row <<= 1; 395168404Spjd } 396168404Spjd 397168404Spjd /* put operator for two zero bits in even */ 398168404Spjd gf2_matrix_square(even, odd); 399168404Spjd 400168404Spjd /* put operator for four zero bits in odd */ 401168404Spjd gf2_matrix_square(odd, even); 402168404Spjd 403168404Spjd /* apply len2 zeros to crc1 (first square will put the operator for one 404168404Spjd zero byte, eight zero bits, in even) */ 405168404Spjd do { 406168404Spjd /* apply zeros operator for this bit of len2 */ 407168404Spjd gf2_matrix_square(even, odd); 408168404Spjd if (len2 & 1) 409168404Spjd crc1 = gf2_matrix_times(even, crc1); 410168404Spjd len2 >>= 1; 411168404Spjd 412168404Spjd /* if no more bits set, then done */ 413168404Spjd if (len2 == 0) 414168404Spjd break; 415168404Spjd 416168404Spjd /* another iteration of the loop with odd and even swapped */ 417168404Spjd gf2_matrix_square(odd, even); 418168404Spjd if (len2 & 1) 419168404Spjd crc1 = gf2_matrix_times(odd, crc1); 420168404Spjd len2 >>= 1; 421168404Spjd 422168404Spjd /* if no more bits set, then done */ 423168404Spjd } while (len2 != 0); 424168404Spjd 425168404Spjd /* return combined crc */ 426168404Spjd crc1 ^= crc2; 427168404Spjd return crc1; 428168404Spjd} 429