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