1/* crc32.c -- compute the CRC-32 of a data stream 2 * Copyright (C) 1995-2022 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 * 5 * This interleaved implementation of a CRC makes use of pipelined multiple 6 * arithmetic-logic units, commonly found in modern CPU cores. It is due to 7 * Kadatch and Jenkins (2010). See doc/crc-doc.1.0.pdf in this distribution. 8 */ 9 10/* @(#) Id */ 11 12/* 13 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore 14 protection on the static variables used to control the first-use generation 15 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should 16 first call get_crc_table() to initialize the tables before allowing more than 17 one thread to use crc32(). 18 19 MAKECRCH can be #defined to write out crc32.h. A main() routine is also 20 produced, so that this one source file can be compiled to an executable. 21 */ 22 23#ifdef MAKECRCH 24# include <stdio.h> 25# ifndef DYNAMIC_CRC_TABLE 26# define DYNAMIC_CRC_TABLE 27# endif /* !DYNAMIC_CRC_TABLE */ 28#endif /* MAKECRCH */ 29 30#include "zutil.h" /* for Z_U4, Z_U8, z_crc_t, and FAR definitions */ 31 32 /* 33 A CRC of a message is computed on N braids of words in the message, where 34 each word consists of W bytes (4 or 8). If N is 3, for example, then three 35 running sparse CRCs are calculated respectively on each braid, at these 36 indices in the array of words: 0, 3, 6, ..., 1, 4, 7, ..., and 2, 5, 8, ... 37 This is done starting at a word boundary, and continues until as many blocks 38 of N * W bytes as are available have been processed. The results are combined 39 into a single CRC at the end. For this code, N must be in the range 1..6 and 40 W must be 4 or 8. The upper limit on N can be increased if desired by adding 41 more #if blocks, extending the patterns apparent in the code. In addition, 42 crc32.h would need to be regenerated, if the maximum N value is increased. 43 44 N and W are chosen empirically by benchmarking the execution time on a given 45 processor. The choices for N and W below were based on testing on Intel Kaby 46 Lake i7, AMD Ryzen 7, ARM Cortex-A57, Sparc64-VII, PowerPC POWER9, and MIPS64 47 Octeon II processors. The Intel, AMD, and ARM processors were all fastest 48 with N=5, W=8. The Sparc, PowerPC, and MIPS64 were all fastest at N=5, W=4. 49 They were all tested with either gcc or clang, all using the -O3 optimization 50 level. Your mileage may vary. 51 */ 52 53/* Define N */ 54#ifdef Z_TESTN 55# define N Z_TESTN 56#else 57# define N 5 58#endif 59#if N < 1 || N > 6 60# error N must be in 1..6 61#endif 62 63/* 64 z_crc_t must be at least 32 bits. z_word_t must be at least as long as 65 z_crc_t. It is assumed here that z_word_t is either 32 bits or 64 bits, and 66 that bytes are eight bits. 67 */ 68 69/* 70 Define W and the associated z_word_t type. If W is not defined, then a 71 braided calculation is not used, and the associated tables and code are not 72 compiled. 73 */ 74#ifdef Z_TESTW 75# if Z_TESTW-1 != -1 76# define W Z_TESTW 77# endif 78#else 79# ifdef MAKECRCH 80# define W 8 /* required for MAKECRCH */ 81# else 82# if defined(__x86_64__) || defined(__aarch64__) 83# define W 8 84# else 85# define W 4 86# endif 87# endif 88#endif 89#ifdef W 90# if W == 8 && defined(Z_U8) 91 typedef Z_U8 z_word_t; 92# elif defined(Z_U4) 93# undef W 94# define W 4 95 typedef Z_U4 z_word_t; 96# else 97# undef W 98# endif 99#endif 100 101/* Local functions. */ 102local z_crc_t multmodp OF((z_crc_t a, z_crc_t b)); 103local z_crc_t x2nmodp OF((z_off64_t n, unsigned k)); 104 105/* If available, use the ARM processor CRC32 instruction. */ 106#if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32) && W == 8 107# define ARMCRC32 108#endif 109 110#if defined(W) && (!defined(ARMCRC32) || defined(DYNAMIC_CRC_TABLE)) 111/* 112 Swap the bytes in a z_word_t to convert between little and big endian. Any 113 self-respecting compiler will optimize this to a single machine byte-swap 114 instruction, if one is available. This assumes that word_t is either 32 bits 115 or 64 bits. 116 */ 117local z_word_t byte_swap(word) 118 z_word_t word; 119{ 120# if W == 8 121 return 122 (word & 0xff00000000000000) >> 56 | 123 (word & 0xff000000000000) >> 40 | 124 (word & 0xff0000000000) >> 24 | 125 (word & 0xff00000000) >> 8 | 126 (word & 0xff000000) << 8 | 127 (word & 0xff0000) << 24 | 128 (word & 0xff00) << 40 | 129 (word & 0xff) << 56; 130# else /* W == 4 */ 131 return 132 (word & 0xff000000) >> 24 | 133 (word & 0xff0000) >> 8 | 134 (word & 0xff00) << 8 | 135 (word & 0xff) << 24; 136# endif 137} 138#endif 139 140/* CRC polynomial. */ 141#define POLY 0xedb88320 /* p(x) reflected, with x^32 implied */ 142 143#ifdef DYNAMIC_CRC_TABLE 144 145local z_crc_t FAR crc_table[256]; 146local z_crc_t FAR x2n_table[32]; 147local void make_crc_table OF((void)); 148#ifdef W 149 local z_word_t FAR crc_big_table[256]; 150 local z_crc_t FAR crc_braid_table[W][256]; 151 local z_word_t FAR crc_braid_big_table[W][256]; 152 local void braid OF((z_crc_t [][256], z_word_t [][256], int, int)); 153#endif 154#ifdef MAKECRCH 155 local void write_table OF((FILE *, const z_crc_t FAR *, int)); 156 local void write_table32hi OF((FILE *, const z_word_t FAR *, int)); 157 local void write_table64 OF((FILE *, const z_word_t FAR *, int)); 158#endif /* MAKECRCH */ 159 160/* 161 Define a once() function depending on the availability of atomics. If this is 162 compiled with DYNAMIC_CRC_TABLE defined, and if CRCs will be computed in 163 multiple threads, and if atomics are not available, then get_crc_table() must 164 be called to initialize the tables and must return before any threads are 165 allowed to compute or combine CRCs. 166 */ 167 168/* Definition of once functionality. */ 169typedef struct once_s once_t; 170local void once OF((once_t *, void (*)(void))); 171 172/* Check for the availability of atomics. */ 173#if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \ 174 !defined(__STDC_NO_ATOMICS__) 175 176#include <stdatomic.h> 177 178/* Structure for once(), which must be initialized with ONCE_INIT. */ 179struct once_s { 180 atomic_flag begun; 181 atomic_int done; 182}; 183#define ONCE_INIT {ATOMIC_FLAG_INIT, 0} 184 185/* 186 Run the provided init() function exactly once, even if multiple threads 187 invoke once() at the same time. The state must be a once_t initialized with 188 ONCE_INIT. 189 */ 190local void once(state, init) 191 once_t *state; 192 void (*init)(void); 193{ 194 if (!atomic_load(&state->done)) { 195 if (atomic_flag_test_and_set(&state->begun)) 196 while (!atomic_load(&state->done)) 197 ; 198 else { 199 init(); 200 atomic_store(&state->done, 1); 201 } 202 } 203} 204 205#else /* no atomics */ 206 207/* Structure for once(), which must be initialized with ONCE_INIT. */ 208struct once_s { 209 volatile int begun; 210 volatile int done; 211}; 212#define ONCE_INIT {0, 0} 213 214/* Test and set. Alas, not atomic, but tries to minimize the period of 215 vulnerability. */ 216local int test_and_set OF((int volatile *)); 217local int test_and_set(flag) 218 int volatile *flag; 219{ 220 int was; 221 222 was = *flag; 223 *flag = 1; 224 return was; 225} 226 227/* Run the provided init() function once. This is not thread-safe. */ 228local void once(state, init) 229 once_t *state; 230 void (*init)(void); 231{ 232 if (!state->done) { 233 if (test_and_set(&state->begun)) 234 while (!state->done) 235 ; 236 else { 237 init(); 238 state->done = 1; 239 } 240 } 241} 242 243#endif 244 245/* State for once(). */ 246local once_t made = ONCE_INIT; 247 248/* 249 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: 250 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. 251 252 Polynomials over GF(2) are represented in binary, one bit per coefficient, 253 with the lowest powers in the most significant bit. Then adding polynomials 254 is just exclusive-or, and multiplying a polynomial by x is a right shift by 255 one. If we call the above polynomial p, and represent a byte as the 256 polynomial q, also with the lowest power in the most significant bit (so the 257 byte 0xb1 is the polynomial x^7+x^3+x^2+1), then the CRC is (q*x^32) mod p, 258 where a mod b means the remainder after dividing a by b. 259 260 This calculation is done using the shift-register method of multiplying and 261 taking the remainder. The register is initialized to zero, and for each 262 incoming bit, x^32 is added mod p to the register if the bit is a one (where 263 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by x 264 (which is shifting right by one and adding x^32 mod p if the bit shifted out 265 is a one). We start with the highest power (least significant bit) of q and 266 repeat for all eight bits of q. 267 268 The table is simply the CRC of all possible eight bit values. This is all the 269 information needed to generate CRCs on data a byte at a time for all 270 combinations of CRC register values and incoming bytes. 271 */ 272 273local void make_crc_table() 274{ 275 unsigned i, j, n; 276 z_crc_t p; 277 278 /* initialize the CRC of bytes tables */ 279 for (i = 0; i < 256; i++) { 280 p = i; 281 for (j = 0; j < 8; j++) 282 p = p & 1 ? (p >> 1) ^ POLY : p >> 1; 283 crc_table[i] = p; 284#ifdef W 285 crc_big_table[i] = byte_swap(p); 286#endif 287 } 288 289 /* initialize the x^2^n mod p(x) table */ 290 p = (z_crc_t)1 << 30; /* x^1 */ 291 x2n_table[0] = p; 292 for (n = 1; n < 32; n++) 293 x2n_table[n] = p = multmodp(p, p); 294 295#ifdef W 296 /* initialize the braiding tables -- needs x2n_table[] */ 297 braid(crc_braid_table, crc_braid_big_table, N, W); 298#endif 299 300#ifdef MAKECRCH 301 { 302 /* 303 The crc32.h header file contains tables for both 32-bit and 64-bit 304 z_word_t's, and so requires a 64-bit type be available. In that case, 305 z_word_t must be defined to be 64-bits. This code then also generates 306 and writes out the tables for the case that z_word_t is 32 bits. 307 */ 308#if !defined(W) || W != 8 309# error Need a 64-bit integer type in order to generate crc32.h. 310#endif 311 FILE *out; 312 int k, n; 313 z_crc_t ltl[8][256]; 314 z_word_t big[8][256]; 315 316 out = fopen("crc32.h", "w"); 317 if (out == NULL) return; 318 319 /* write out little-endian CRC table to crc32.h */ 320 fprintf(out, 321 "/* crc32.h -- tables for rapid CRC calculation\n" 322 " * Generated automatically by crc32.c\n */\n" 323 "\n" 324 "local const z_crc_t FAR crc_table[] = {\n" 325 " "); 326 write_table(out, crc_table, 256); 327 fprintf(out, 328 "};\n"); 329 330 /* write out big-endian CRC table for 64-bit z_word_t to crc32.h */ 331 fprintf(out, 332 "\n" 333 "#ifdef W\n" 334 "\n" 335 "#if W == 8\n" 336 "\n" 337 "local const z_word_t FAR crc_big_table[] = {\n" 338 " "); 339 write_table64(out, crc_big_table, 256); 340 fprintf(out, 341 "};\n"); 342 343 /* write out big-endian CRC table for 32-bit z_word_t to crc32.h */ 344 fprintf(out, 345 "\n" 346 "#else /* W == 4 */\n" 347 "\n" 348 "local const z_word_t FAR crc_big_table[] = {\n" 349 " "); 350 write_table32hi(out, crc_big_table, 256); 351 fprintf(out, 352 "};\n" 353 "\n" 354 "#endif\n"); 355 356 /* write out braid tables for each value of N */ 357 for (n = 1; n <= 6; n++) { 358 fprintf(out, 359 "\n" 360 "#if N == %d\n", n); 361 362 /* compute braid tables for this N and 64-bit word_t */ 363 braid(ltl, big, n, 8); 364 365 /* write out braid tables for 64-bit z_word_t to crc32.h */ 366 fprintf(out, 367 "\n" 368 "#if W == 8\n" 369 "\n" 370 "local const z_crc_t FAR crc_braid_table[][256] = {\n"); 371 for (k = 0; k < 8; k++) { 372 fprintf(out, " {"); 373 write_table(out, ltl[k], 256); 374 fprintf(out, "}%s", k < 7 ? ",\n" : ""); 375 } 376 fprintf(out, 377 "};\n" 378 "\n" 379 "local const z_word_t FAR crc_braid_big_table[][256] = {\n"); 380 for (k = 0; k < 8; k++) { 381 fprintf(out, " {"); 382 write_table64(out, big[k], 256); 383 fprintf(out, "}%s", k < 7 ? ",\n" : ""); 384 } 385 fprintf(out, 386 "};\n"); 387 388 /* compute braid tables for this N and 32-bit word_t */ 389 braid(ltl, big, n, 4); 390 391 /* write out braid tables for 32-bit z_word_t to crc32.h */ 392 fprintf(out, 393 "\n" 394 "#else /* W == 4 */\n" 395 "\n" 396 "local const z_crc_t FAR crc_braid_table[][256] = {\n"); 397 for (k = 0; k < 4; k++) { 398 fprintf(out, " {"); 399 write_table(out, ltl[k], 256); 400 fprintf(out, "}%s", k < 3 ? ",\n" : ""); 401 } 402 fprintf(out, 403 "};\n" 404 "\n" 405 "local const z_word_t FAR crc_braid_big_table[][256] = {\n"); 406 for (k = 0; k < 4; k++) { 407 fprintf(out, " {"); 408 write_table32hi(out, big[k], 256); 409 fprintf(out, "}%s", k < 3 ? ",\n" : ""); 410 } 411 fprintf(out, 412 "};\n" 413 "\n" 414 "#endif\n" 415 "\n" 416 "#endif\n"); 417 } 418 fprintf(out, 419 "\n" 420 "#endif\n"); 421 422 /* write out zeros operator table to crc32.h */ 423 fprintf(out, 424 "\n" 425 "local const z_crc_t FAR x2n_table[] = {\n" 426 " "); 427 write_table(out, x2n_table, 32); 428 fprintf(out, 429 "};\n"); 430 fclose(out); 431 } 432#endif /* MAKECRCH */ 433} 434 435#ifdef MAKECRCH 436 437/* 438 Write the 32-bit values in table[0..k-1] to out, five per line in 439 hexadecimal separated by commas. 440 */ 441local void write_table(out, table, k) 442 FILE *out; 443 const z_crc_t FAR *table; 444 int k; 445{ 446 int n; 447 448 for (n = 0; n < k; n++) 449 fprintf(out, "%s0x%08lx%s", n == 0 || n % 5 ? "" : " ", 450 (unsigned long)(table[n]), 451 n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", ")); 452} 453 454/* 455 Write the high 32-bits of each value in table[0..k-1] to out, five per line 456 in hexadecimal separated by commas. 457 */ 458local void write_table32hi(out, table, k) 459FILE *out; 460const z_word_t FAR *table; 461int k; 462{ 463 int n; 464 465 for (n = 0; n < k; n++) 466 fprintf(out, "%s0x%08lx%s", n == 0 || n % 5 ? "" : " ", 467 (unsigned long)(table[n] >> 32), 468 n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", ")); 469} 470 471/* 472 Write the 64-bit values in table[0..k-1] to out, three per line in 473 hexadecimal separated by commas. This assumes that if there is a 64-bit 474 type, then there is also a long long integer type, and it is at least 64 475 bits. If not, then the type cast and format string can be adjusted 476 accordingly. 477 */ 478local void write_table64(out, table, k) 479 FILE *out; 480 const z_word_t FAR *table; 481 int k; 482{ 483 int n; 484 485 for (n = 0; n < k; n++) 486 fprintf(out, "%s0x%016llx%s", n == 0 || n % 3 ? "" : " ", 487 (unsigned long long)(table[n]), 488 n == k - 1 ? "" : (n % 3 == 2 ? ",\n" : ", ")); 489} 490 491/* Actually do the deed. */ 492int main() 493{ 494 make_crc_table(); 495 return 0; 496} 497 498#endif /* MAKECRCH */ 499 500#ifdef W 501/* 502 Generate the little and big-endian braid tables for the given n and z_word_t 503 size w. Each array must have room for w blocks of 256 elements. 504 */ 505local void braid(ltl, big, n, w) 506 z_crc_t ltl[][256]; 507 z_word_t big[][256]; 508 int n; 509 int w; 510{ 511 int k; 512 z_crc_t i, p, q; 513 for (k = 0; k < w; k++) { 514 p = x2nmodp((n * w + 3 - k) << 3, 0); 515 ltl[k][0] = 0; 516 big[w - 1 - k][0] = 0; 517 for (i = 1; i < 256; i++) { 518 ltl[k][i] = q = multmodp(i << 24, p); 519 big[w - 1 - k][i] = byte_swap(q); 520 } 521 } 522} 523#endif 524 525#else /* !DYNAMIC_CRC_TABLE */ 526/* ======================================================================== 527 * Tables for byte-wise and braided CRC-32 calculations, and a table of powers 528 * of x for combining CRC-32s, all made by make_crc_table(). 529 */ 530#include "crc32.h" 531#endif /* DYNAMIC_CRC_TABLE */ 532 533/* ======================================================================== 534 * Routines used for CRC calculation. Some are also required for the table 535 * generation above. 536 */ 537 538/* 539 Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial, 540 reflected. For speed, this requires that a not be zero. 541 */ 542local z_crc_t multmodp(a, b) 543 z_crc_t a; 544 z_crc_t b; 545{ 546 z_crc_t m, p; 547 548 m = (z_crc_t)1 << 31; 549 p = 0; 550 for (;;) { 551 if (a & m) { 552 p ^= b; 553 if ((a & (m - 1)) == 0) 554 break; 555 } 556 m >>= 1; 557 b = b & 1 ? (b >> 1) ^ POLY : b >> 1; 558 } 559 return p; 560} 561 562/* 563 Return x^(n * 2^k) modulo p(x). Requires that x2n_table[] has been 564 initialized. 565 */ 566local z_crc_t x2nmodp(n, k) 567 z_off64_t n; 568 unsigned k; 569{ 570 z_crc_t p; 571 572 p = (z_crc_t)1 << 31; /* x^0 == 1 */ 573 while (n) { 574 if (n & 1) 575 p = multmodp(x2n_table[k & 31], p); 576 n >>= 1; 577 k++; 578 } 579 return p; 580} 581 582/* ========================================================================= 583 * This function can be used by asm versions of crc32(), and to force the 584 * generation of the CRC tables in a threaded application. 585 */ 586const z_crc_t FAR * ZEXPORT get_crc_table() 587{ 588#ifdef DYNAMIC_CRC_TABLE 589 once(&made, make_crc_table); 590#endif /* DYNAMIC_CRC_TABLE */ 591 return (const z_crc_t FAR *)crc_table; 592} 593 594/* ========================================================================= 595 * Use ARM machine instructions if available. This will compute the CRC about 596 * ten times faster than the braided calculation. This code does not check for 597 * the presence of the CRC instruction at run time. __ARM_FEATURE_CRC32 will 598 * only be defined if the compilation specifies an ARM processor architecture 599 * that has the instructions. For example, compiling with -march=armv8.1-a or 600 * -march=armv8-a+crc, or -march=native if the compile machine has the crc32 601 * instructions. 602 */ 603#ifdef ARMCRC32 604 605/* 606 Constants empirically determined to maximize speed. These values are from 607 measurements on a Cortex-A57. Your mileage may vary. 608 */ 609#define Z_BATCH 3990 /* number of words in a batch */ 610#define Z_BATCH_ZEROS 0xa10d3d0c /* computed from Z_BATCH = 3990 */ 611#define Z_BATCH_MIN 800 /* fewest words in a final batch */ 612 613unsigned long ZEXPORT crc32_z(crc, buf, len) 614 unsigned long crc; 615 const unsigned char FAR *buf; 616 z_size_t len; 617{ 618 z_crc_t val; 619 z_word_t crc1, crc2; 620 const z_word_t *word; 621 z_word_t val0, val1, val2; 622 z_size_t last, last2, i; 623 z_size_t num; 624 625 /* Return initial CRC, if requested. */ 626 if (buf == Z_NULL) return 0; 627 628#ifdef DYNAMIC_CRC_TABLE 629 once(&made, make_crc_table); 630#endif /* DYNAMIC_CRC_TABLE */ 631 632 /* Pre-condition the CRC */ 633 crc ^= 0xffffffff; 634 635 /* Compute the CRC up to a word boundary. */ 636 while (len && ((z_size_t)buf & 7) != 0) { 637 len--; 638 val = *buf++; 639 __asm__ volatile("crc32b %w0, %w0, %w1" : "+r"(crc) : "r"(val)); 640 } 641 642 /* Prepare to compute the CRC on full 64-bit words word[0..num-1]. */ 643 word = (z_word_t const *)buf; 644 num = len >> 3; 645 len &= 7; 646 647 /* Do three interleaved CRCs to realize the throughput of one crc32x 648 instruction per cycle. Each CRC is calcuated on Z_BATCH words. The three 649 CRCs are combined into a single CRC after each set of batches. */ 650 while (num >= 3 * Z_BATCH) { 651 crc1 = 0; 652 crc2 = 0; 653 for (i = 0; i < Z_BATCH; i++) { 654 val0 = word[i]; 655 val1 = word[i + Z_BATCH]; 656 val2 = word[i + 2 * Z_BATCH]; 657 __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0)); 658 __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc1) : "r"(val1)); 659 __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc2) : "r"(val2)); 660 } 661 word += 3 * Z_BATCH; 662 num -= 3 * Z_BATCH; 663 crc = multmodp(Z_BATCH_ZEROS, crc) ^ crc1; 664 crc = multmodp(Z_BATCH_ZEROS, crc) ^ crc2; 665 } 666 667 /* Do one last smaller batch with the remaining words, if there are enough 668 to pay for the combination of CRCs. */ 669 last = num / 3; 670 if (last >= Z_BATCH_MIN) { 671 last2 = last << 1; 672 crc1 = 0; 673 crc2 = 0; 674 for (i = 0; i < last; i++) { 675 val0 = word[i]; 676 val1 = word[i + last]; 677 val2 = word[i + last2]; 678 __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0)); 679 __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc1) : "r"(val1)); 680 __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc2) : "r"(val2)); 681 } 682 word += 3 * last; 683 num -= 3 * last; 684 val = x2nmodp(last, 6); 685 crc = multmodp(val, crc) ^ crc1; 686 crc = multmodp(val, crc) ^ crc2; 687 } 688 689 /* Compute the CRC on any remaining words. */ 690 for (i = 0; i < num; i++) { 691 val0 = word[i]; 692 __asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0)); 693 } 694 word += num; 695 696 /* Complete the CRC on any remaining bytes. */ 697 buf = (const unsigned char FAR *)word; 698 while (len) { 699 len--; 700 val = *buf++; 701 __asm__ volatile("crc32b %w0, %w0, %w1" : "+r"(crc) : "r"(val)); 702 } 703 704 /* Return the CRC, post-conditioned. */ 705 return crc ^ 0xffffffff; 706} 707 708#else 709 710#ifdef W 711 712/* 713 Return the CRC of the W bytes in the word_t data, taking the 714 least-significant byte of the word as the first byte of data, without any pre 715 or post conditioning. This is used to combine the CRCs of each braid. 716 */ 717local z_crc_t crc_word(data) 718 z_word_t data; 719{ 720 int k; 721 for (k = 0; k < W; k++) 722 data = (data >> 8) ^ crc_table[data & 0xff]; 723 return (z_crc_t)data; 724} 725 726local z_word_t crc_word_big(data) 727 z_word_t data; 728{ 729 int k; 730 for (k = 0; k < W; k++) 731 data = (data << 8) ^ 732 crc_big_table[(data >> ((W - 1) << 3)) & 0xff]; 733 return data; 734} 735 736#endif 737 738/* ========================================================================= */ 739unsigned long ZEXPORT crc32_z(crc, buf, len) 740 unsigned long crc; 741 const unsigned char FAR *buf; 742 z_size_t len; 743{ 744 /* Return initial CRC, if requested. */ 745 if (buf == Z_NULL) return 0; 746 747#ifdef DYNAMIC_CRC_TABLE 748 once(&made, make_crc_table); 749#endif /* DYNAMIC_CRC_TABLE */ 750 751 /* Pre-condition the CRC */ 752 crc ^= 0xffffffff; 753 754#ifdef W 755 756 /* If provided enough bytes, do a braided CRC calculation. */ 757 if (len >= N * W + W - 1) { 758 z_size_t blks; 759 z_word_t const *words; 760 unsigned endian; 761 int k; 762 763 /* Compute the CRC up to a z_word_t boundary. */ 764 while (len && ((z_size_t)buf & (W - 1)) != 0) { 765 len--; 766 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 767 } 768 769 /* Compute the CRC on as many N z_word_t blocks as are available. */ 770 blks = len / (N * W); 771 len -= blks * N * W; 772 words = (z_word_t const *)buf; 773 774 /* Do endian check at execution time instead of compile time, since ARM 775 processors can change the endianess at execution time. If the 776 compiler knows what the endianess will be, it can optimize out the 777 check and the unused branch. */ 778 endian = 1; 779 if (*(unsigned char *)&endian) { 780 /* Little endian. */ 781 782 z_crc_t crc0; 783 z_word_t word0; 784#if N > 1 785 z_crc_t crc1; 786 z_word_t word1; 787#if N > 2 788 z_crc_t crc2; 789 z_word_t word2; 790#if N > 3 791 z_crc_t crc3; 792 z_word_t word3; 793#if N > 4 794 z_crc_t crc4; 795 z_word_t word4; 796#if N > 5 797 z_crc_t crc5; 798 z_word_t word5; 799#endif 800#endif 801#endif 802#endif 803#endif 804 805 /* Initialize the CRC for each braid. */ 806 crc0 = crc; 807#if N > 1 808 crc1 = 0; 809#if N > 2 810 crc2 = 0; 811#if N > 3 812 crc3 = 0; 813#if N > 4 814 crc4 = 0; 815#if N > 5 816 crc5 = 0; 817#endif 818#endif 819#endif 820#endif 821#endif 822 823 /* 824 Process the first blks-1 blocks, computing the CRCs on each braid 825 independently. 826 */ 827 while (--blks) { 828 /* Load the word for each braid into registers. */ 829 word0 = crc0 ^ words[0]; 830#if N > 1 831 word1 = crc1 ^ words[1]; 832#if N > 2 833 word2 = crc2 ^ words[2]; 834#if N > 3 835 word3 = crc3 ^ words[3]; 836#if N > 4 837 word4 = crc4 ^ words[4]; 838#if N > 5 839 word5 = crc5 ^ words[5]; 840#endif 841#endif 842#endif 843#endif 844#endif 845 words += N; 846 847 /* Compute and update the CRC for each word. The loop should 848 get unrolled. */ 849 crc0 = crc_braid_table[0][word0 & 0xff]; 850#if N > 1 851 crc1 = crc_braid_table[0][word1 & 0xff]; 852#if N > 2 853 crc2 = crc_braid_table[0][word2 & 0xff]; 854#if N > 3 855 crc3 = crc_braid_table[0][word3 & 0xff]; 856#if N > 4 857 crc4 = crc_braid_table[0][word4 & 0xff]; 858#if N > 5 859 crc5 = crc_braid_table[0][word5 & 0xff]; 860#endif 861#endif 862#endif 863#endif 864#endif 865 for (k = 1; k < W; k++) { 866 crc0 ^= crc_braid_table[k][(word0 >> (k << 3)) & 0xff]; 867#if N > 1 868 crc1 ^= crc_braid_table[k][(word1 >> (k << 3)) & 0xff]; 869#if N > 2 870 crc2 ^= crc_braid_table[k][(word2 >> (k << 3)) & 0xff]; 871#if N > 3 872 crc3 ^= crc_braid_table[k][(word3 >> (k << 3)) & 0xff]; 873#if N > 4 874 crc4 ^= crc_braid_table[k][(word4 >> (k << 3)) & 0xff]; 875#if N > 5 876 crc5 ^= crc_braid_table[k][(word5 >> (k << 3)) & 0xff]; 877#endif 878#endif 879#endif 880#endif 881#endif 882 } 883 } 884 885 /* 886 Process the last block, combining the CRCs of the N braids at the 887 same time. 888 */ 889 crc = crc_word(crc0 ^ words[0]); 890#if N > 1 891 crc = crc_word(crc1 ^ words[1] ^ crc); 892#if N > 2 893 crc = crc_word(crc2 ^ words[2] ^ crc); 894#if N > 3 895 crc = crc_word(crc3 ^ words[3] ^ crc); 896#if N > 4 897 crc = crc_word(crc4 ^ words[4] ^ crc); 898#if N > 5 899 crc = crc_word(crc5 ^ words[5] ^ crc); 900#endif 901#endif 902#endif 903#endif 904#endif 905 words += N; 906 } 907 else { 908 /* Big endian. */ 909 910 z_word_t crc0, word0, comb; 911#if N > 1 912 z_word_t crc1, word1; 913#if N > 2 914 z_word_t crc2, word2; 915#if N > 3 916 z_word_t crc3, word3; 917#if N > 4 918 z_word_t crc4, word4; 919#if N > 5 920 z_word_t crc5, word5; 921#endif 922#endif 923#endif 924#endif 925#endif 926 927 /* Initialize the CRC for each braid. */ 928 crc0 = byte_swap(crc); 929#if N > 1 930 crc1 = 0; 931#if N > 2 932 crc2 = 0; 933#if N > 3 934 crc3 = 0; 935#if N > 4 936 crc4 = 0; 937#if N > 5 938 crc5 = 0; 939#endif 940#endif 941#endif 942#endif 943#endif 944 945 /* 946 Process the first blks-1 blocks, computing the CRCs on each braid 947 independently. 948 */ 949 while (--blks) { 950 /* Load the word for each braid into registers. */ 951 word0 = crc0 ^ words[0]; 952#if N > 1 953 word1 = crc1 ^ words[1]; 954#if N > 2 955 word2 = crc2 ^ words[2]; 956#if N > 3 957 word3 = crc3 ^ words[3]; 958#if N > 4 959 word4 = crc4 ^ words[4]; 960#if N > 5 961 word5 = crc5 ^ words[5]; 962#endif 963#endif 964#endif 965#endif 966#endif 967 words += N; 968 969 /* Compute and update the CRC for each word. The loop should 970 get unrolled. */ 971 crc0 = crc_braid_big_table[0][word0 & 0xff]; 972#if N > 1 973 crc1 = crc_braid_big_table[0][word1 & 0xff]; 974#if N > 2 975 crc2 = crc_braid_big_table[0][word2 & 0xff]; 976#if N > 3 977 crc3 = crc_braid_big_table[0][word3 & 0xff]; 978#if N > 4 979 crc4 = crc_braid_big_table[0][word4 & 0xff]; 980#if N > 5 981 crc5 = crc_braid_big_table[0][word5 & 0xff]; 982#endif 983#endif 984#endif 985#endif 986#endif 987 for (k = 1; k < W; k++) { 988 crc0 ^= crc_braid_big_table[k][(word0 >> (k << 3)) & 0xff]; 989#if N > 1 990 crc1 ^= crc_braid_big_table[k][(word1 >> (k << 3)) & 0xff]; 991#if N > 2 992 crc2 ^= crc_braid_big_table[k][(word2 >> (k << 3)) & 0xff]; 993#if N > 3 994 crc3 ^= crc_braid_big_table[k][(word3 >> (k << 3)) & 0xff]; 995#if N > 4 996 crc4 ^= crc_braid_big_table[k][(word4 >> (k << 3)) & 0xff]; 997#if N > 5 998 crc5 ^= crc_braid_big_table[k][(word5 >> (k << 3)) & 0xff]; 999#endif 1000#endif 1001#endif 1002#endif 1003#endif 1004 } 1005 } 1006 1007 /* 1008 Process the last block, combining the CRCs of the N braids at the 1009 same time. 1010 */ 1011 comb = crc_word_big(crc0 ^ words[0]); 1012#if N > 1 1013 comb = crc_word_big(crc1 ^ words[1] ^ comb); 1014#if N > 2 1015 comb = crc_word_big(crc2 ^ words[2] ^ comb); 1016#if N > 3 1017 comb = crc_word_big(crc3 ^ words[3] ^ comb); 1018#if N > 4 1019 comb = crc_word_big(crc4 ^ words[4] ^ comb); 1020#if N > 5 1021 comb = crc_word_big(crc5 ^ words[5] ^ comb); 1022#endif 1023#endif 1024#endif 1025#endif 1026#endif 1027 words += N; 1028 crc = byte_swap(comb); 1029 } 1030 1031 /* 1032 Update the pointer to the remaining bytes to process. 1033 */ 1034 buf = (unsigned char const *)words; 1035 } 1036 1037#endif /* W */ 1038 1039 /* Complete the computation of the CRC on any remaining bytes. */ 1040 while (len >= 8) { 1041 len -= 8; 1042 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1043 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1044 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1045 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1046 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1047 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1048 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1049 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1050 } 1051 while (len) { 1052 len--; 1053 crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff]; 1054 } 1055 1056 /* Return the CRC, post-conditioned. */ 1057 return crc ^ 0xffffffff; 1058} 1059 1060#endif 1061 1062/* ========================================================================= */ 1063unsigned long ZEXPORT crc32(crc, buf, len) 1064 unsigned long crc; 1065 const unsigned char FAR *buf; 1066 uInt len; 1067{ 1068 return crc32_z(crc, buf, len); 1069} 1070 1071/* ========================================================================= */ 1072uLong ZEXPORT crc32_combine64(crc1, crc2, len2) 1073 uLong crc1; 1074 uLong crc2; 1075 z_off64_t len2; 1076{ 1077#ifdef DYNAMIC_CRC_TABLE 1078 once(&made, make_crc_table); 1079#endif /* DYNAMIC_CRC_TABLE */ 1080 return multmodp(x2nmodp(len2, 3), crc1) ^ crc2; 1081} 1082 1083/* ========================================================================= */ 1084uLong ZEXPORT crc32_combine(crc1, crc2, len2) 1085 uLong crc1; 1086 uLong crc2; 1087 z_off_t len2; 1088{ 1089 return crc32_combine64(crc1, crc2, len2); 1090} 1091 1092/* ========================================================================= */ 1093uLong ZEXPORT crc32_combine_gen64(len2) 1094 z_off64_t len2; 1095{ 1096#ifdef DYNAMIC_CRC_TABLE 1097 once(&made, make_crc_table); 1098#endif /* DYNAMIC_CRC_TABLE */ 1099 return x2nmodp(len2, 3); 1100} 1101 1102/* ========================================================================= */ 1103uLong ZEXPORT crc32_combine_gen(len2) 1104 z_off_t len2; 1105{ 1106 return crc32_combine_gen64(len2); 1107} 1108 1109/* ========================================================================= */ 1110uLong crc32_combine_op(crc1, crc2, op) 1111 uLong crc1; 1112 uLong crc2; 1113 uLong op; 1114{ 1115 return multmodp(op, crc1) ^ crc2; 1116} 1117