117651Speter/* crc32.c -- compute the CRC-32 of a data stream 2237410Sdelphij * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler 3131380Stjr * For conditions of distribution and use, see copyright notice in zlib.h 4131380Stjr * 5131380Stjr * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 6131380Stjr * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 7131380Stjr * tables for updating the shift register in one step with three exclusive-ors 8157046Sdes * instead of four steps with four exclusive-ors. This results in about a 9157046Sdes * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 1017651Speter */ 1117651Speter 12146081Skientzle/* @(#) $Id$ */ 1317651Speter 14146081Skientzle/* 15146081Skientzle Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 16146081Skientzle protection on the static variables used to control the first-use generation 17146081Skientzle of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 18146081Skientzle first call get_crc_table() to initialize the tables before allowing more than 19146081Skientzle one thread to use crc32(). 20237410Sdelphij 21237410Sdelphij DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h. 22146081Skientzle */ 23146081Skientzle 24131380Stjr#ifdef MAKECRCH 25131380Stjr# include <stdio.h> 26131380Stjr# ifndef DYNAMIC_CRC_TABLE 27131380Stjr# define DYNAMIC_CRC_TABLE 28131380Stjr# endif /* !DYNAMIC_CRC_TABLE */ 29131380Stjr#endif /* MAKECRCH */ 3017651Speter 31131380Stjr#include "zutil.h" /* for STDC and FAR definitions */ 32131380Stjr 3317651Speter#define local static 3417651Speter 35131380Stjr/* Definitions for doing the crc four data bytes at a time. */ 36237410Sdelphij#if !defined(NOBYFOUR) && defined(Z_U4) 37237410Sdelphij# define BYFOUR 38237410Sdelphij#endif 39131380Stjr#ifdef BYFOUR 40131380Stjr local unsigned long crc32_little OF((unsigned long, 41131380Stjr const unsigned char FAR *, unsigned)); 42131380Stjr local unsigned long crc32_big OF((unsigned long, 43131380Stjr const unsigned char FAR *, unsigned)); 44131380Stjr# define TBLS 8 45131380Stjr#else 46131380Stjr# define TBLS 1 47131380Stjr#endif /* BYFOUR */ 48131380Stjr 49157046Sdes/* Local functions for crc concatenation */ 50157046Sdeslocal unsigned long gf2_matrix_times OF((unsigned long *mat, 51157046Sdes unsigned long vec)); 52157046Sdeslocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 53237410Sdelphijlocal uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); 54157046Sdes 55205471Sdelphij 5617651Speter#ifdef DYNAMIC_CRC_TABLE 5717651Speter 58146081Skientzlelocal volatile int crc_table_empty = 1; 59237410Sdelphijlocal z_crc_t FAR crc_table[TBLS][256]; 6017651Speterlocal void make_crc_table OF((void)); 61131380Stjr#ifdef MAKECRCH 62237410Sdelphij local void write_table OF((FILE *, const z_crc_t FAR *)); 63131380Stjr#endif /* MAKECRCH */ 6417651Speter/* 65131380Stjr Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 6617651Speter 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. 6717651Speter 6817651Speter Polynomials over GF(2) are represented in binary, one bit per coefficient, 6917651Speter with the lowest powers in the most significant bit. Then adding polynomials 7017651Speter is just exclusive-or, and multiplying a polynomial by x is a right shift by 7117651Speter one. If we call the above polynomial p, and represent a byte as the 7217651Speter polynomial q, also with the lowest power in the most significant bit (so the 7317651Speter byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 7417651Speter where a mod b means the remainder after dividing a by b. 7517651Speter 7617651Speter This calculation is done using the shift-register method of multiplying and 7717651Speter taking the remainder. The register is initialized to zero, and for each 7817651Speter incoming bit, x^32 is added mod p to the register if the bit is a one (where 7917651Speter x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 8017651Speter x (which is shifting right by one and adding x^32 mod p if the bit shifted 8117651Speter out is a one). We start with the highest power (least significant bit) of 8217651Speter q and repeat for all eight bits of q. 8317651Speter 84131380Stjr The first table is simply the CRC of all possible eight bit values. This is 85131380Stjr all the information needed to generate CRCs on data a byte at a time for all 86131380Stjr combinations of CRC register values and incoming bytes. The remaining tables 87131380Stjr allow for word-at-a-time CRC calculation for both big-endian and little- 88131380Stjr endian machines, where a word is four bytes. 8917651Speter*/ 9017651Speterlocal void make_crc_table() 9117651Speter{ 92237410Sdelphij z_crc_t c; 93131380Stjr int n, k; 94237410Sdelphij z_crc_t poly; /* polynomial exclusive-or pattern */ 95131380Stjr /* terms of polynomial defining this crc (except x^32): */ 96146081Skientzle static volatile int first = 1; /* flag to limit concurrent making */ 97131380Stjr static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 9817651Speter 99146081Skientzle /* See if another task is already doing this (not thread-safe, but better 100146081Skientzle than nothing -- significantly reduces duration of vulnerability in 101146081Skientzle case the advice about DYNAMIC_CRC_TABLE is ignored) */ 102146081Skientzle if (first) { 103146081Skientzle first = 0; 104131380Stjr 105146081Skientzle /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 106237410Sdelphij poly = 0; 107237410Sdelphij for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) 108237410Sdelphij poly |= (z_crc_t)1 << (31 - p[n]); 109131380Stjr 110146081Skientzle /* generate a crc for every 8-bit value */ 111146081Skientzle for (n = 0; n < 256; n++) { 112237410Sdelphij c = (z_crc_t)n; 113146081Skientzle for (k = 0; k < 8; k++) 114146081Skientzle c = c & 1 ? poly ^ (c >> 1) : c >> 1; 115146081Skientzle crc_table[0][n] = c; 116146081Skientzle } 117146081Skientzle 118131380Stjr#ifdef BYFOUR 119146081Skientzle /* generate crc for each value followed by one, two, and three zeros, 120146081Skientzle and then the byte reversal of those as well as the first table */ 121146081Skientzle for (n = 0; n < 256; n++) { 122146081Skientzle c = crc_table[0][n]; 123237410Sdelphij crc_table[4][n] = ZSWAP32(c); 124146081Skientzle for (k = 1; k < 4; k++) { 125146081Skientzle c = crc_table[0][c & 0xff] ^ (c >> 8); 126146081Skientzle crc_table[k][n] = c; 127237410Sdelphij crc_table[k + 4][n] = ZSWAP32(c); 128146081Skientzle } 129131380Stjr } 130131380Stjr#endif /* BYFOUR */ 131131380Stjr 132146081Skientzle crc_table_empty = 0; 133146081Skientzle } 134146081Skientzle else { /* not first */ 135146081Skientzle /* wait for the other guy to finish (not efficient, but rare) */ 136146081Skientzle while (crc_table_empty) 137146081Skientzle ; 138146081Skientzle } 139131380Stjr 140131380Stjr#ifdef MAKECRCH 141131380Stjr /* write out CRC tables to crc32.h */ 142131380Stjr { 143131380Stjr FILE *out; 144131380Stjr 145131380Stjr out = fopen("crc32.h", "w"); 146131380Stjr if (out == NULL) return; 147131380Stjr fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 148131380Stjr fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 149237410Sdelphij fprintf(out, "local const z_crc_t FAR "); 150131380Stjr fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 151131380Stjr write_table(out, crc_table[0]); 152131380Stjr# ifdef BYFOUR 153131380Stjr fprintf(out, "#ifdef BYFOUR\n"); 154131380Stjr for (k = 1; k < 8; k++) { 155131380Stjr fprintf(out, " },\n {\n"); 156131380Stjr write_table(out, crc_table[k]); 157131380Stjr } 158131380Stjr fprintf(out, "#endif\n"); 159131380Stjr# endif /* BYFOUR */ 160131380Stjr fprintf(out, " }\n};\n"); 161131380Stjr fclose(out); 162131380Stjr } 163131380Stjr#endif /* MAKECRCH */ 16417651Speter} 165131380Stjr 166131380Stjr#ifdef MAKECRCH 167131380Stjrlocal void write_table(out, table) 168131380Stjr FILE *out; 169237410Sdelphij const z_crc_t FAR *table; 170131380Stjr{ 171131380Stjr int n; 172131380Stjr 173131380Stjr for (n = 0; n < 256; n++) 174237410Sdelphij fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", 175237410Sdelphij (unsigned long)(table[n]), 176131380Stjr n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 177131380Stjr} 178131380Stjr#endif /* MAKECRCH */ 179131380Stjr 180131380Stjr#else /* !DYNAMIC_CRC_TABLE */ 18117651Speter/* ======================================================================== 182131380Stjr * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 18317651Speter */ 184131380Stjr#include "crc32.h" 185131380Stjr#endif /* DYNAMIC_CRC_TABLE */ 18617651Speter 18717651Speter/* ========================================================================= 18817651Speter * This function can be used by asm versions of crc32() 18917651Speter */ 190237410Sdelphijconst z_crc_t FAR * ZEXPORT get_crc_table() 19117651Speter{ 19217651Speter#ifdef DYNAMIC_CRC_TABLE 193146081Skientzle if (crc_table_empty) 194146081Skientzle make_crc_table(); 195131380Stjr#endif /* DYNAMIC_CRC_TABLE */ 196237410Sdelphij return (const z_crc_t FAR *)crc_table; 19717651Speter} 19817651Speter 19917651Speter/* ========================================================================= */ 200131380Stjr#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 201131380Stjr#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 20217651Speter 20317651Speter/* ========================================================================= */ 204131380Stjrunsigned long ZEXPORT crc32(crc, buf, len) 205131380Stjr unsigned long crc; 206131380Stjr const unsigned char FAR *buf; 207206002Sdelphij uInt len; 20817651Speter{ 209131380Stjr if (buf == Z_NULL) return 0UL; 210131380Stjr 21117651Speter#ifdef DYNAMIC_CRC_TABLE 21217651Speter if (crc_table_empty) 213131380Stjr make_crc_table(); 214131380Stjr#endif /* DYNAMIC_CRC_TABLE */ 215131380Stjr 216131380Stjr#ifdef BYFOUR 217131380Stjr if (sizeof(void *) == sizeof(ptrdiff_t)) { 218237410Sdelphij z_crc_t endian; 219131380Stjr 220131380Stjr endian = 1; 221131380Stjr if (*((unsigned char *)(&endian))) 222131380Stjr return crc32_little(crc, buf, len); 223131380Stjr else 224131380Stjr return crc32_big(crc, buf, len); 22517651Speter } 226131380Stjr#endif /* BYFOUR */ 227131380Stjr crc = crc ^ 0xffffffffUL; 228131380Stjr while (len >= 8) { 229131380Stjr DO8; 230131380Stjr len -= 8; 231131380Stjr } 23217651Speter if (len) do { 233131380Stjr DO1; 23417651Speter } while (--len); 235131380Stjr return crc ^ 0xffffffffUL; 23617651Speter} 237131380Stjr 238131380Stjr#ifdef BYFOUR 239131380Stjr 240131380Stjr/* ========================================================================= */ 241131380Stjr#define DOLIT4 c ^= *buf4++; \ 242131380Stjr c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 243131380Stjr crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 244131380Stjr#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 245131380Stjr 246131380Stjr/* ========================================================================= */ 247131380Stjrlocal unsigned long crc32_little(crc, buf, len) 248131380Stjr unsigned long crc; 249131380Stjr const unsigned char FAR *buf; 250131380Stjr unsigned len; 251131380Stjr{ 252237410Sdelphij register z_crc_t c; 253237410Sdelphij register const z_crc_t FAR *buf4; 254131380Stjr 255237410Sdelphij c = (z_crc_t)crc; 256131380Stjr c = ~c; 257131380Stjr while (len && ((ptrdiff_t)buf & 3)) { 258131380Stjr c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 259131380Stjr len--; 260131380Stjr } 261131380Stjr 262237410Sdelphij buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 263131380Stjr while (len >= 32) { 264131380Stjr DOLIT32; 265131380Stjr len -= 32; 266131380Stjr } 267131380Stjr while (len >= 4) { 268131380Stjr DOLIT4; 269131380Stjr len -= 4; 270131380Stjr } 271131380Stjr buf = (const unsigned char FAR *)buf4; 272131380Stjr 273131380Stjr if (len) do { 274131380Stjr c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 275131380Stjr } while (--len); 276131380Stjr c = ~c; 277131380Stjr return (unsigned long)c; 278131380Stjr} 279131380Stjr 280131380Stjr/* ========================================================================= */ 281131380Stjr#define DOBIG4 c ^= *++buf4; \ 282131380Stjr c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 283131380Stjr crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 284131380Stjr#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 285131380Stjr 286131380Stjr/* ========================================================================= */ 287131380Stjrlocal unsigned long crc32_big(crc, buf, len) 288131380Stjr unsigned long crc; 289131380Stjr const unsigned char FAR *buf; 290131380Stjr unsigned len; 291131380Stjr{ 292237410Sdelphij register z_crc_t c; 293237410Sdelphij register const z_crc_t FAR *buf4; 294131380Stjr 295237410Sdelphij c = ZSWAP32((z_crc_t)crc); 296131380Stjr c = ~c; 297131380Stjr while (len && ((ptrdiff_t)buf & 3)) { 298131380Stjr c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 299131380Stjr len--; 300131380Stjr } 301131380Stjr 302237410Sdelphij buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 303131380Stjr buf4--; 304131380Stjr while (len >= 32) { 305131380Stjr DOBIG32; 306131380Stjr len -= 32; 307131380Stjr } 308131380Stjr while (len >= 4) { 309131380Stjr DOBIG4; 310131380Stjr len -= 4; 311131380Stjr } 312131380Stjr buf4++; 313131380Stjr buf = (const unsigned char FAR *)buf4; 314131380Stjr 315131380Stjr if (len) do { 316131380Stjr c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 317131380Stjr } while (--len); 318131380Stjr c = ~c; 319237410Sdelphij return (unsigned long)(ZSWAP32(c)); 320131380Stjr} 321131380Stjr 322131380Stjr#endif /* BYFOUR */ 323157046Sdes 324157046Sdes#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 325157046Sdes 326157046Sdes/* ========================================================================= */ 327157046Sdeslocal unsigned long gf2_matrix_times(mat, vec) 328157046Sdes unsigned long *mat; 329157046Sdes unsigned long vec; 330157046Sdes{ 331157046Sdes unsigned long sum; 332157046Sdes 333157046Sdes sum = 0; 334157046Sdes while (vec) { 335157046Sdes if (vec & 1) 336157046Sdes sum ^= *mat; 337157046Sdes vec >>= 1; 338157046Sdes mat++; 339157046Sdes } 340157046Sdes return sum; 341157046Sdes} 342157046Sdes 343157046Sdes/* ========================================================================= */ 344157046Sdeslocal void gf2_matrix_square(square, mat) 345157046Sdes unsigned long *square; 346157046Sdes unsigned long *mat; 347157046Sdes{ 348157046Sdes int n; 349157046Sdes 350157046Sdes for (n = 0; n < GF2_DIM; n++) 351157046Sdes square[n] = gf2_matrix_times(mat, mat[n]); 352157046Sdes} 353157046Sdes 354157046Sdes/* ========================================================================= */ 355205471Sdelphijlocal uLong crc32_combine_(crc1, crc2, len2) 356157046Sdes uLong crc1; 357157046Sdes uLong crc2; 358205471Sdelphij z_off64_t len2; 359157046Sdes{ 360157046Sdes int n; 361157046Sdes unsigned long row; 362157046Sdes unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 363157046Sdes unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 364157046Sdes 365205471Sdelphij /* degenerate case (also disallow negative lengths) */ 366205471Sdelphij if (len2 <= 0) 367157046Sdes return crc1; 368157046Sdes 369157046Sdes /* put operator for one zero bit in odd */ 370205471Sdelphij odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 371157046Sdes row = 1; 372157046Sdes for (n = 1; n < GF2_DIM; n++) { 373157046Sdes odd[n] = row; 374157046Sdes row <<= 1; 375157046Sdes } 376157046Sdes 377157046Sdes /* put operator for two zero bits in even */ 378157046Sdes gf2_matrix_square(even, odd); 379157046Sdes 380157046Sdes /* put operator for four zero bits in odd */ 381157046Sdes gf2_matrix_square(odd, even); 382157046Sdes 383157046Sdes /* apply len2 zeros to crc1 (first square will put the operator for one 384157046Sdes zero byte, eight zero bits, in even) */ 385157046Sdes do { 386157046Sdes /* apply zeros operator for this bit of len2 */ 387157046Sdes gf2_matrix_square(even, odd); 388157046Sdes if (len2 & 1) 389157046Sdes crc1 = gf2_matrix_times(even, crc1); 390157046Sdes len2 >>= 1; 391157046Sdes 392157046Sdes /* if no more bits set, then done */ 393157046Sdes if (len2 == 0) 394157046Sdes break; 395157046Sdes 396157046Sdes /* another iteration of the loop with odd and even swapped */ 397157046Sdes gf2_matrix_square(odd, even); 398157046Sdes if (len2 & 1) 399157046Sdes crc1 = gf2_matrix_times(odd, crc1); 400157046Sdes len2 >>= 1; 401157046Sdes 402157046Sdes /* if no more bits set, then done */ 403157046Sdes } while (len2 != 0); 404157046Sdes 405157046Sdes /* return combined crc */ 406157046Sdes crc1 ^= crc2; 407157046Sdes return crc1; 408157046Sdes} 409205471Sdelphij 410205471Sdelphij/* ========================================================================= */ 411205471SdelphijuLong ZEXPORT crc32_combine(crc1, crc2, len2) 412205471Sdelphij uLong crc1; 413205471Sdelphij uLong crc2; 414205471Sdelphij z_off_t len2; 415205471Sdelphij{ 416205471Sdelphij return crc32_combine_(crc1, crc2, len2); 417205471Sdelphij} 418205471Sdelphij 419205471SdelphijuLong ZEXPORT crc32_combine64(crc1, crc2, len2) 420205471Sdelphij uLong crc1; 421205471Sdelphij uLong crc2; 422205471Sdelphij z_off64_t len2; 423205471Sdelphij{ 424205471Sdelphij return crc32_combine_(crc1, crc2, len2); 425205471Sdelphij} 426