1d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans/* crc32.c -- compute the CRC-32 of a data stream 2d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler 3d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * For conditions of distribution and use, see copyright notice in zlib.h 4d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * 5d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster 6d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing 7d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * tables for updating the shift register in one step with three exclusive-ors 8d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * instead of four steps with four exclusive-ors. This results in about a 9d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. 10d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans */ 11d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 12d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans/* @(#) $Id$ */ 13d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 14d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans/* 15d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 16d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans protection on the static variables used to control the first-use generation 17d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 18d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans first call get_crc_table() to initialize the tables before allowing more than 19d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans one thread to use crc32(). 20d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 21d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h. 22d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans */ 23d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 24d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#ifdef MAKECRCH 25d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans# include <stdio.h> 26d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans# ifndef DYNAMIC_CRC_TABLE 27d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans# define DYNAMIC_CRC_TABLE 28d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans# endif /* !DYNAMIC_CRC_TABLE */ 29d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#endif /* MAKECRCH */ 30d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 31d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#include "zutil.h" /* for STDC and FAR definitions */ 32d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 33d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#define local static 34d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 35d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans/* Definitions for doing the crc four data bytes at a time. */ 36d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#if !defined(NOBYFOUR) && defined(Z_U4) 37d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans# define BYFOUR 38d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#endif 39d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#ifdef BYFOUR 40d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans local unsigned long crc32_little OF((unsigned long, 41d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans const unsigned char FAR *, unsigned)); 425a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans local unsigned long crc32_big OF((unsigned long, 435a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans const unsigned char FAR *, unsigned)); 445a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans# define TBLS 8 455a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#else 465a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans# define TBLS 1 475a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#endif /* BYFOUR */ 485a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 495a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans/* Local functions for crc concatenation */ 505a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal unsigned long gf2_matrix_times OF((unsigned long *mat, 515a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans unsigned long vec)); 525a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); 535a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); 545a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 555a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 565a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#ifdef DYNAMIC_CRC_TABLE 575a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 585a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal volatile int crc_table_empty = 1; 595a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal z_crc_t FAR crc_table[TBLS][256]; 605a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal void make_crc_table OF((void)); 615a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#ifdef MAKECRCH 625a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans local void write_table OF((FILE *, const z_crc_t FAR *)); 635a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#endif /* MAKECRCH */ 645a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans/* 655a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 665a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 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. 675a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 685a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans Polynomials over GF(2) are represented in binary, one bit per coefficient, 695a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans with the lowest powers in the most significant bit. Then adding polynomials 705a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans is just exclusive-or, and multiplying a polynomial by x is a right shift by 715a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans one. If we call the above polynomial p, and represent a byte as the 725a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans polynomial q, also with the lowest power in the most significant bit (so the 735a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, 745a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans where a mod b means the remainder after dividing a by b. 755a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 765a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans This calculation is done using the shift-register method of multiplying and 775a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans taking the remainder. The register is initialized to zero, and for each 785a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans incoming bit, x^32 is added mod p to the register if the bit is a one (where 795a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by 805a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans x (which is shifting right by one and adding x^32 mod p if the bit shifted 815a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans out is a one). We start with the highest power (least significant bit) of 825a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans q and repeat for all eight bits of q. 835a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 845a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans The first table is simply the CRC of all possible eight bit values. This is 855a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans all the information needed to generate CRCs on data a byte at a time for all 865a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans combinations of CRC register values and incoming bytes. The remaining tables 875a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans allow for word-at-a-time CRC calculation for both big-endian and little- 885a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans endian machines, where a word is four bytes. 895a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans*/ 905a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal void make_crc_table() 915a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans{ 925a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans z_crc_t c; 935a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans int n, k; 945a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans z_crc_t poly; /* polynomial exclusive-or pattern */ 955a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans /* terms of polynomial defining this crc (except x^32): */ 965a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans static volatile int first = 1; /* flag to limit concurrent making */ 975a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; 9863b08f67da4f4c8cea919bbea3adeebd46000b24Mike Hommey 9933b16c7fbbcf6e2ccfc4d518f0d63a2ea6ceb5d4Mike Hommey /* See if another task is already doing this (not thread-safe, but better 1005a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans than nothing -- significantly reduces duration of vulnerability in 1015a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans case the advice about DYNAMIC_CRC_TABLE is ignored) */ 1025a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans if (first) { 1035a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans first = 0; 1045a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 1055a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans /* make exclusive-or pattern from polynomial (0xedb88320UL) */ 1065a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans poly = 0; 1075a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) 1085a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans poly |= (z_crc_t)1 << (31 - p[n]); 1095a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 1105a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans /* generate a crc for every 8-bit value */ 1115a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans for (n = 0; n < 256; n++) { 1125a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans c = (z_crc_t)n; 1135a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans for (k = 0; k < 8; k++) 1145a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans c = c & 1 ? poly ^ (c >> 1) : c >> 1; 1155a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans crc_table[0][n] = c; 116ada8447cf6fb2c1f976b6311dade2e91026b3d83Jason Evans } 1175a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 1185a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#ifdef BYFOUR 1195a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans /* generate crc for each value followed by one, two, and three zeros, 1205a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans and then the byte reversal of those as well as the first table */ 1215a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans for (n = 0; n < 256; n++) { 1225a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans c = crc_table[0][n]; 1235a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans crc_table[4][n] = ZSWAP32(c); 1245a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans for (k = 1; k < 4; k++) { 1255a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans c = crc_table[0][c & 0xff] ^ (c >> 8); 1265a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans crc_table[k][n] = c; 1275a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans crc_table[k + 4][n] = ZSWAP32(c); 1285a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans } 1295a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans } 1305a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#endif /* BYFOUR */ 1315a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 1325a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans crc_table_empty = 0; 1335a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans } 1345a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans else { /* not first */ 1355a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans /* wait for the other guy to finish (not efficient, but rare) */ 1365a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans while (crc_table_empty) 137e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans ; 1385a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans } 1395a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 140e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans#ifdef MAKECRCH 141ada8447cf6fb2c1f976b6311dade2e91026b3d83Jason Evans /* write out CRC tables to crc32.h */ 142e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans { 1435a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans FILE *out; 1445a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans 145e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans out = fopen("crc32.h", "w"); 1465a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans if (out == NULL) return; 1475a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); 1485a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); 149e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans fprintf(out, "local const z_crc_t FAR "); 1505a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); 1515a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans write_table(out, crc_table[0]); 1525a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans# ifdef BYFOUR 1535a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans fprintf(out, "#ifdef BYFOUR\n"); 1545a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans for (k = 1; k < 8; k++) { 1555a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans fprintf(out, " },\n {\n"); 156e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans write_table(out, crc_table[k]); 157e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans } 158e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans fprintf(out, "#endif\n"); 159e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans# endif /* BYFOUR */ 160e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans fprintf(out, " }\n};\n"); 161e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans fclose(out); 162e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans } 16333b16c7fbbcf6e2ccfc4d518f0d63a2ea6ceb5d4Mike Hommey#endif /* MAKECRCH */ 16463b08f67da4f4c8cea919bbea3adeebd46000b24Mike Hommey} 16533b16c7fbbcf6e2ccfc4d518f0d63a2ea6ceb5d4Mike Hommey 166e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans#ifdef MAKECRCH 1675a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evanslocal void write_table( 1685a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans FILE *out, 1695a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans const z_crc_t FAR *table) 170e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans{ 1715a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans int n; 172d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 173d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans for (n = 0; n < 256; n++) 174d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", 175d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans (unsigned long)(table[n]), 176d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); 177d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans} 178d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#endif /* MAKECRCH */ 179d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans 1805a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans#else /* !DYNAMIC_CRC_TABLE */ 1815a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans/* ======================================================================== 1825a658b9c7517d62fa39759f5ff6119d26dfc4cb7Jason Evans * Tables of CRC-32s of all single-byte values, made by make_crc_table(). 183e935c07e0066e5c7b8ae51e68ebcc4321eabcb7cJason Evans */ 184d82a5e6a34f20698ab9368bb2b4953b81d175552Jason Evans#include "crc32.h" 185#endif /* DYNAMIC_CRC_TABLE */ 186 187/* ========================================================================= 188 * This function can be used by asm versions of crc32() 189 */ 190const z_crc_t FAR * ZEXPORT get_crc_table() 191{ 192#ifdef DYNAMIC_CRC_TABLE 193 if (crc_table_empty) 194 make_crc_table(); 195#endif /* DYNAMIC_CRC_TABLE */ 196 return (const z_crc_t FAR *)crc_table; 197} 198 199/* ========================================================================= */ 200#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) 201#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 202 203/* ========================================================================= */ 204unsigned long ZEXPORT crc32( 205 unsigned long crc, 206 const unsigned char FAR *buf, 207 uInt len) 208{ 209 if (buf == Z_NULL) return 0UL; 210 211#ifdef DYNAMIC_CRC_TABLE 212 if (crc_table_empty) 213 make_crc_table(); 214#endif /* DYNAMIC_CRC_TABLE */ 215 216#ifdef BYFOUR 217 if (sizeof(void *) == sizeof(ptrdiff_t)) { 218 z_crc_t endian; 219 220 endian = 1; 221 if (*((unsigned char *)(&endian))) 222 return crc32_little(crc, buf, len); 223 else 224 return crc32_big(crc, buf, len); 225 } 226#endif /* BYFOUR */ 227 crc = crc ^ 0xffffffffUL; 228 while (len >= 8) { 229 DO8; 230 len -= 8; 231 } 232 if (len) do { 233 DO1; 234 } while (--len); 235 return crc ^ 0xffffffffUL; 236} 237 238#ifdef BYFOUR 239 240/* ========================================================================= */ 241#define DOLIT4 c ^= *buf4++; \ 242 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ 243 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] 244#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 245 246/* ========================================================================= */ 247local unsigned long crc32_little( 248 unsigned long crc, 249 const unsigned char FAR *buf, 250 unsigned len) 251{ 252 register z_crc_t c; 253 register const z_crc_t FAR *buf4; 254 255 c = (z_crc_t)crc; 256 c = ~c; 257 while (len && ((ptrdiff_t)buf & 3)) { 258 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 259 len--; 260 } 261 262 buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 263 while (len >= 32) { 264 DOLIT32; 265 len -= 32; 266 } 267 while (len >= 4) { 268 DOLIT4; 269 len -= 4; 270 } 271 buf = (const unsigned char FAR *)buf4; 272 273 if (len) do { 274 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); 275 } while (--len); 276 c = ~c; 277 return (unsigned long)c; 278} 279 280/* ========================================================================= */ 281#define DOBIG4 c ^= *++buf4; \ 282 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ 283 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] 284#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 285 286/* ========================================================================= */ 287local unsigned long crc32_big( 288 unsigned long crc, 289 const unsigned char FAR *buf, 290 unsigned len) 291{ 292 register z_crc_t c; 293 register const z_crc_t FAR *buf4; 294 295 c = ZSWAP32((z_crc_t)crc); 296 c = ~c; 297 while (len && ((ptrdiff_t)buf & 3)) { 298 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 299 len--; 300 } 301 302 buf4 = (const z_crc_t FAR *)(const void FAR *)buf; 303 buf4--; 304 while (len >= 32) { 305 DOBIG32; 306 len -= 32; 307 } 308 while (len >= 4) { 309 DOBIG4; 310 len -= 4; 311 } 312 buf4++; 313 buf = (const unsigned char FAR *)buf4; 314 315 if (len) do { 316 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); 317 } while (--len); 318 c = ~c; 319 return (unsigned long)(ZSWAP32(c)); 320} 321 322#endif /* BYFOUR */ 323 324#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */ 325 326/* ========================================================================= */ 327local unsigned long gf2_matrix_times( 328 unsigned long *mat, 329 unsigned long vec) 330{ 331 unsigned long sum; 332 333 sum = 0; 334 while (vec) { 335 if (vec & 1) 336 sum ^= *mat; 337 vec >>= 1; 338 mat++; 339 } 340 return sum; 341} 342 343/* ========================================================================= */ 344local void gf2_matrix_square( 345 unsigned long *square, 346 unsigned long *mat) 347{ 348 int n; 349 350 for (n = 0; n < GF2_DIM; n++) 351 square[n] = gf2_matrix_times(mat, mat[n]); 352} 353 354/* ========================================================================= */ 355local uLong crc32_combine_( 356 uLong crc1, 357 uLong crc2, 358 z_off64_t len2) 359{ 360 int n; 361 unsigned long row; 362 unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */ 363 unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */ 364 365 /* degenerate case (also disallow negative lengths) */ 366 if (len2 <= 0) 367 return crc1; 368 369 /* put operator for one zero bit in odd */ 370 odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 371 row = 1; 372 for (n = 1; n < GF2_DIM; n++) { 373 odd[n] = row; 374 row <<= 1; 375 } 376 377 /* put operator for two zero bits in even */ 378 gf2_matrix_square(even, odd); 379 380 /* put operator for four zero bits in odd */ 381 gf2_matrix_square(odd, even); 382 383 /* apply len2 zeros to crc1 (first square will put the operator for one 384 zero byte, eight zero bits, in even) */ 385 do { 386 /* apply zeros operator for this bit of len2 */ 387 gf2_matrix_square(even, odd); 388 if (len2 & 1) 389 crc1 = gf2_matrix_times(even, crc1); 390 len2 >>= 1; 391 392 /* if no more bits set, then done */ 393 if (len2 == 0) 394 break; 395 396 /* another iteration of the loop with odd and even swapped */ 397 gf2_matrix_square(odd, even); 398 if (len2 & 1) 399 crc1 = gf2_matrix_times(odd, crc1); 400 len2 >>= 1; 401 402 /* if no more bits set, then done */ 403 } while (len2 != 0); 404 405 /* return combined crc */ 406 crc1 ^= crc2; 407 return crc1; 408} 409 410/* ========================================================================= */ 411uLong ZEXPORT crc32_combine( 412 uLong crc1, 413 uLong crc2, 414 z_off_t len2) 415{ 416 return crc32_combine_(crc1, crc2, len2); 417} 418 419uLong ZEXPORT crc32_combine64( 420 uLong crc1, 421 uLong crc2, 422 z_off64_t len2) 423{ 424 return crc32_combine_(crc1, crc2, len2); 425} 426