crc32.c

   1 /* crc32.c -- compute the CRC-32 of a data stream
   2  * Copyright (C) 1995-2006, 2010, 2011, 2012, 2016, 2018 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. */
 102 local z_crc_t multmodp OF((z_crc_t a, z_crc_t b));
 103 local z_crc_t x2nmodp OF((z_off64_t n, unsigned k));
 104 #ifdef W
 105    local z_word_t byte_swap OF((z_word_t word));
 106    local z_crc_t crc_word OF((z_word_t data));
 107    local z_word_t crc_word_big OF((z_word_t data));
 108 #endif /* W */
 109
 110 /* CRC polynomial. */
 111 #define POLY 0xedb88320         /* p(x) reflected, with x^32 implied */
 112
 113 #ifdef DYNAMIC_CRC_TABLE
 114
 115 local z_crc_t FAR crc_table[256];
 116 local z_crc_t FAR x2n_table[32];
 117 local void make_crc_table OF((void));
 118 #ifdef W
 119    local z_word_t FAR crc_big_table[256];
 120    local z_crc_t FAR crc_braid_table[W][256];
 121    local z_word_t FAR crc_braid_big_table[W][256];
 122    local void braid OF((z_crc_t [][256], z_word_t [][256], int, int));
 123 #endif
 124 #ifdef MAKECRCH
 125    local void write_table OF((FILE *, const z_crc_t FAR *, int));
 126    local void write_table32hi OF((FILE *, const z_word_t FAR *, int));
 127    local void write_table64 OF((FILE *, const z_word_t FAR *, int));
 128 #endif /* MAKECRCH */
 129
 130 /*
 131   Define a once() function depending on the availability of atomics. If this is
 132   compiled with DYNAMIC_CRC_TABLE defined, and if CRCs will be computed in
 133   multiple threads, and if atomics are not available, then get_crc_table() must
 134   be called to initialize the tables and must return before any threads are
 135   allowed to compute or combine CRCs.
 136  */
 137
 138 /* Definition of once functionality. */
 139 typedef struct once_s once_t;
 140 local void once OF((once_t *, void (*)(void)));
 141
 142 /* Check for the availability of atomics. */
 143 #if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \
 144     !defined(__STDC_NO_ATOMICS__)
 145
 146 #include <stdatomic.h>
 147
 148 /* Structure for once(), which must be initialized with ONCE_INIT. */
 149 struct once_s {
 150     atomic_flag begun;
 151     atomic_int done;
 152 };
 153 #define ONCE_INIT {ATOMIC_FLAG_INIT, 0}
 154
 155 /*
 156   Run the provided init() function exactly once, even if multiple threads
 157   invoke once() at the same time. The state must be a once_t initialized with
 158   ONCE_INIT.
 159  */
 160 local void once(state, init)
 161     once_t *state;
 162     void (*init)(void);
 163 {
 164     if (!atomic_load(&state->done)) {
 165         if (atomic_flag_test_and_set(&state->begun))
 166             while (!atomic_load(&state->done))
 167                 ;
 168         else {
 169             init();
 170             atomic_store(&state->done, 1);
 171         }
 172     }
 173 }
 174
 175 #else   /* no atomics */
 176
 177 /* Structure for once(), which must be initialized with ONCE_INIT. */
 178 struct once_s {
 179     volatile int begun;
 180     volatile int done;
 181 };
 182 #define ONCE_INIT {0, 0}
 183
 184 /* Test and set. Alas, not atomic, but tries to minimize the period of
 185    vulnerability. */
 186 local int test_and_set OF((int volatile *));
 187 local int test_and_set(flag)
 188     int volatile *flag;
 189 {
 190     int was;
 191
 192     was = *flag;
 193     *flag = 1;
 194     return was;
 195 }
 196
 197 /* Run the provided init() function once. This is not thread-safe. */
 198 local void once(state, init)
 199     once_t *state;
 200     void (*init)(void);
 201 {
 202     if (!state->done) {
 203         if (test_and_set(&state->begun))
 204             while (!state->done)
 205                 ;
 206         else {
 207             init();
 208             state->done = 1;
 209         }
 210     }
 211 }
 212
 213 #endif
 214
 215 /* State for once(). */
 216 local once_t made = ONCE_INIT;
 217
 218 /*
 219   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
 220   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.
 221
 222   Polynomials over GF(2) are represented in binary, one bit per coefficient,
 223   with the lowest powers in the most significant bit. Then adding polynomials
 224   is just exclusive-or, and multiplying a polynomial by x is a right shift by
 225   one. If we call the above polynomial p, and represent a byte as the
 226   polynomial q, also with the lowest power in the most significant bit (so the
 227   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
 228   where a mod b means the remainder after dividing a by b.
 229
 230   This calculation is done using the shift-register method of multiplying and
 231   taking the remainder. The register is initialized to zero, and for each
 232   incoming bit, x^32 is added mod p to the register if the bit is a one (where
 233   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by x
 234   (which is shifting right by one and adding x^32 mod p if the bit shifted out
 235   is a one). We start with the highest power (least significant bit) of q and
 236   repeat for all eight bits of q.
 237
 238   The table is simply the CRC of all possible eight bit values. This is all the
 239   information needed to generate CRCs on data a byte at a time for all
 240   combinations of CRC register values and incoming bytes.
 241  */
 242
 243 local void make_crc_table()
 244 {
 245     unsigned i, j, n;
 246     z_crc_t p;
 247
 248     /* initialize the CRC of bytes tables */
 249     for (i = 0; i < 256; i++) {
 250         p = i;
 251         for (j = 0; j < 8; j++)
 252             p = p & 1 ? (p >> 1) ^ POLY : p >> 1;
 253         crc_table[i] = p;
 254 #ifdef W
 255         crc_big_table[i] = byte_swap(p);
 256 #endif
 257     }
 258
 259     /* initialize the x^2^n mod p(x) table */
 260     p = (z_crc_t)1 << 30;         /* x^1 */
 261     x2n_table[0] = p;
 262     for (n = 1; n < 32; n++)
 263         x2n_table[n] = p = multmodp(p, p);
 264
 265 #ifdef W
 266     /* initialize the braiding tables -- needs x2n_table[] */
 267     braid(crc_braid_table, crc_braid_big_table, N, W);
 268 #endif
 269
 270 #ifdef MAKECRCH
 271     {
 272         /*
 273           The crc32.h header file contains tables for both 32-bit and 64-bit
 274           z_word_t's, and so requires a 64-bit type be available. In that case,
 275           z_word_t must be defined to be 64-bits. This code then also generates
 276           and writes out the tables for the case that z_word_t is 32 bits.
 277          */
 278 #if !defined(W) || W != 8
 279 #  error Need a 64-bit integer type in order to generate crc32.h.
 280 #endif
 281         FILE *out;
 282         int k, n;
 283         z_crc_t ltl[8][256];
 284         z_word_t big[8][256];
 285
 286         out = fopen("crc32.h", "w");
 287         if (out == NULL) return;
 288
 289         /* write out little-endian CRC table to crc32.h */
 290         fprintf(out,
 291             "/* crc32.h -- tables for rapid CRC calculation\n"
 292             " * Generated automatically by crc32.c\n */\n"
 293             "\n"
 294             "local const z_crc_t FAR crc_table[] = {\n"
 295             "    ");
 296         write_table(out, crc_table, 256);
 297         fprintf(out,
 298             "};\n");
 299
 300         /* write out big-endian CRC table for 64-bit z_word_t to crc32.h */
 301         fprintf(out,
 302             "\n"
 303             "#ifdef W\n"
 304             "\n"
 305             "#if W == 8\n"
 306             "\n"
 307             "local const z_word_t FAR crc_big_table[] = {\n"
 308             "    ");
 309         write_table64(out, crc_big_table, 256);
 310         fprintf(out,
 311             "};\n");
 312
 313         /* write out big-endian CRC table for 32-bit z_word_t to crc32.h */
 314         fprintf(out,
 315             "\n"
 316             "#else /* W == 4 */\n"
 317             "\n"
 318             "local const z_word_t FAR crc_big_table[] = {\n"
 319             "    ");
 320         write_table32hi(out, crc_big_table, 256);
 321         fprintf(out,
 322             "};\n"
 323             "\n"
 324             "#endif\n");
 325
 326         /* write out braid tables for each value of N */
 327         for (n = 1; n <= 6; n++) {
 328             fprintf(out,
 329             "\n"
 330             "#if N == %d\n", n);
 331
 332             /* compute braid tables for this N and 64-bit word_t */
 333             braid(ltl, big, n, 8);
 334
 335             /* write out braid tables for 64-bit z_word_t to crc32.h */
 336             fprintf(out,
 337             "\n"
 338             "#if W == 8\n"
 339             "\n"
 340             "local const z_crc_t FAR crc_braid_table[][256] = {\n");
 341             for (k = 0; k < 8; k++) {
 342                 fprintf(out, "   {");
 343                 write_table(out, ltl[k], 256);
 344                 fprintf(out, "}%s", k < 7 ? ",\n" : "");
 345             }
 346             fprintf(out,
 347             "};\n"
 348             "\n"
 349             "local const z_word_t FAR crc_braid_big_table[][256] = {\n");
 350             for (k = 0; k < 8; k++) {
 351                 fprintf(out, "   {");
 352                 write_table64(out, big[k], 256);
 353                 fprintf(out, "}%s", k < 7 ? ",\n" : "");
 354             }
 355             fprintf(out,
 356             "};\n");
 357
 358             /* compute braid tables for this N and 32-bit word_t */
 359             braid(ltl, big, n, 4);
 360
 361             /* write out braid tables for 32-bit z_word_t to crc32.h */
 362             fprintf(out,
 363             "\n"
 364             "#else /* W == 4 */\n"
 365             "\n"
 366             "local const z_crc_t FAR crc_braid_table[][256] = {\n");
 367             for (k = 0; k < 4; k++) {
 368                 fprintf(out, "   {");
 369                 write_table(out, ltl[k], 256);
 370                 fprintf(out, "}%s", k < 3 ? ",\n" : "");
 371             }
 372             fprintf(out,
 373             "};\n"
 374             "\n"
 375             "local const z_word_t FAR crc_braid_big_table[][256] = {\n");
 376             for (k = 0; k < 4; k++) {
 377                 fprintf(out, "   {");
 378                 write_table32hi(out, big[k], 256);
 379                 fprintf(out, "}%s", k < 3 ? ",\n" : "");
 380             }
 381             fprintf(out,
 382             "};\n"
 383             "\n"
 384             "#endif\n"
 385             "\n"
 386             "#endif\n");
 387         }
 388         fprintf(out,
 389             "\n"
 390             "#endif\n");
 391
 392         /* write out zeros operator table to crc32.h */
 393         fprintf(out,
 394             "\n"
 395             "local const z_crc_t FAR x2n_table[] = {\n"
 396             "    ");
 397         write_table(out, x2n_table, 32);
 398         fprintf(out,
 399             "};\n");
 400         fclose(out);
 401     }
 402 #endif /* MAKECRCH */
 403 }
 404
 405 #ifdef MAKECRCH
 406
 407 /*
 408    Write the 32-bit values in table[0..k-1] to out, five per line in
 409    hexadecimal separated by commas.
 410  */
 411 local void write_table(out, table, k)
 412     FILE *out;
 413     const z_crc_t FAR *table;
 414     int k;
 415 {
 416     int n;
 417
 418     for (n = 0; n < k; n++)
 419         fprintf(out, "%s0x%08lx%s", n == 0 || n % 5 ? "" : "    ",
 420                 (unsigned long)(table[n]),
 421                 n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", "));
 422 }
 423
 424 /*
 425    Write the high 32-bits of each value in table[0..k-1] to out, five per line
 426    in hexadecimal separated by commas.
 427  */
 428 local void write_table32hi(out, table, k)
 429 FILE *out;
 430 const z_word_t FAR *table;
 431 int k;
 432 {
 433     int n;
 434
 435     for (n = 0; n < k; n++)
 436         fprintf(out, "%s0x%08lx%s", n == 0 || n % 5 ? "" : "    ",
 437                 (unsigned long)(table[n] >> 32),
 438                 n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", "));
 439 }
 440
 441 /*
 442   Write the 64-bit values in table[0..k-1] to out, three per line in
 443   hexadecimal separated by commas. This assumes that if there is a 64-bit
 444   type, then there is also a long long integer type, and it is at least 64
 445   bits. If not, then the type cast and format string can be adjusted
 446   accordingly.
 447  */
 448 local void write_table64(out, table, k)
 449     FILE *out;
 450     const z_word_t FAR *table;
 451     int k;
 452 {
 453     int n;
 454
 455     for (n = 0; n < k; n++)
 456         fprintf(out, "%s0x%016llx%s", n == 0 || n % 3 ? "" : "    ",
 457                 (unsigned long long)(table[n]),
 458                 n == k - 1 ? "" : (n % 3 == 2 ? ",\n" : ", "));
 459 }
 460
 461 /* Actually do the deed. */
 462 int main()
 463 {
 464     make_crc_table();
 465     return 0;
 466 }
 467
 468 #endif /* MAKECRCH */
 469
 470 #ifdef W
 471 /*
 472   Generate the little and big-endian braid tables for the given n and z_word_t
 473   size w. Each array must have room for w blocks of 256 elements.
 474  */
 475 local void braid(ltl, big, n, w)
 476     z_crc_t ltl[][256];
 477     z_word_t big[][256];
 478     int n;
 479     int w;
 480 {
 481     int k;
 482     z_crc_t i, p, q;
 483     for (k = 0; k < w; k++) {
 484         p = x2nmodp((n * w + 3 - k) << 3, 0);
 485         ltl[k][0] = 0;
 486         big[w - 1 - k][0] = 0;
 487         for (i = 1; i < 256; i++) {
 488             ltl[k][i] = q = multmodp(i << 24, p);
 489             big[w - 1 - k][i] = byte_swap(q);
 490         }
 491     }
 492 }
 493 #endif
 494
 495 #else /* !DYNAMIC_CRC_TABLE */
 496 /* ========================================================================
 497  * Tables for byte-wise and braided CRC-32 calculations, and a table of powers
 498  * of x for combining CRC-32s, all made by make_crc_table().
 499  */
 500 #include "crc32.h"
 501 #endif /* DYNAMIC_CRC_TABLE */
 502
 503 /* ========================================================================
 504  * Routines used for CRC calculation. Some are also required for the table
 505  * generation above.
 506  */
 507
 508 /*
 509   Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial,
 510   reflected. For speed, this requires that a not be zero.
 511  */
 512 local z_crc_t multmodp(a, b)
 513     z_crc_t a;
 514     z_crc_t b;
 515 {
 516     z_crc_t m, p;
 517
 518     m = (z_crc_t)1 << 31;
 519     p = 0;
 520     for (;;) {
 521         if (a & m) {
 522             p ^= b;
 523             if ((a & (m - 1)) == 0)
 524                 break;
 525         }
 526         m >>= 1;
 527         b = b & 1 ? (b >> 1) ^ POLY : b >> 1;
 528     }
 529     return p;
 530 }
 531
 532 /*
 533   Return x^(n+k) modulo p(x). Requires that x2n_table[] has been initialized.
 534  */
 535 local z_crc_t x2nmodp(n, k)
 536     z_off64_t n;
 537     unsigned k;
 538 {
 539     z_crc_t p;
 540
 541     p = (z_crc_t)1 << 31;           /* x^0 == 1 */
 542     while (n) {
 543         if (n & 1)
 544             p = multmodp(x2n_table[k & 31], p);
 545         n >>= 1;
 546         k++;
 547     }
 548     return p;
 549 }
 550
 551 #ifdef W
 552
 553 /*
 554   Swap the bytes in a z_word_t to convert between little and big endian. Any
 555   self-respecting compiler will optimize this to a single machine byte-swap
 556   instruction, if one is available. This assumes that word_t is either 32 bits
 557   or 64 bits.
 558  */
 559 local z_word_t byte_swap(word)
 560     z_word_t word;
 561 {
 562 #if W == 8
 563     return
 564         (word & 0xff00000000000000) >> 56 |
 565         (word & 0xff000000000000) >> 40 |
 566         (word & 0xff0000000000) >> 24 |
 567         (word & 0xff00000000) >> 8 |
 568         (word & 0xff000000) << 8 |
 569         (word & 0xff0000) << 24 |
 570         (word & 0xff00) << 40 |
 571         (word & 0xff) << 56;
 572 #else   /* W == 4 */
 573     return
 574         (word & 0xff000000) >> 24 |
 575         (word & 0xff0000) >> 8 |
 576         (word & 0xff00) << 8 |
 577         (word & 0xff) << 24;
 578 #endif
 579 }
 580
 581 /*
 582   Return the CRC of the W bytes in the word_t data, taking the
 583   least-significant byte of the word as the first byte of data, without any pre
 584   or post conditioning. This is used to combine the CRCs of each braid.
 585  */
 586 local z_crc_t crc_word(data)
 587     z_word_t data;
 588 {
 589     int k;
 590     for (k = 0; k < W; k++)
 591         data = (data >> 8) ^ crc_table[data & 0xff];
 592     return (z_crc_t)data;
 593 }
 594
 595 local z_word_t crc_word_big(data)
 596     z_word_t data;
 597 {
 598     int k;
 599     for (k = 0; k < W; k++)
 600         data = (data << 8) ^
 601             crc_big_table[(data >> ((W - 1) << 3)) & 0xff];
 602     return data;
 603 }
 604
 605 #endif /* W */
 606
 607 /* =========================================================================
 608  * This function can be used by asm versions of crc32(), and to force the
 609  * generation of the CRC tables in a threaded application.
 610  */
 611 const z_crc_t FAR * ZEXPORT get_crc_table()
 612 {
 613 #ifdef DYNAMIC_CRC_TABLE
 614     once(&made, make_crc_table);
 615 #endif /* DYNAMIC_CRC_TABLE */
 616     return (const z_crc_t FAR *)crc_table;
 617 }
 618
 619 /* ========================================================================= */
 620 unsigned long ZEXPORT crc32_z(crc, buf, len)
 621     unsigned long crc;
 622     const unsigned char FAR *buf;
 623     z_size_t len;
 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 #ifdef W
 636
 637     /* If provided enough bytes, do a braided CRC calculation. */
 638     if (len >= N * W + W - 1) {
 639         z_size_t blks;
 640         z_word_t const *words;
 641         unsigned endian;
 642         int k;
 643
 644         /* Compute the CRC up to a z_word_t boundary. */
 645         while (len && ((z_size_t)buf & (W - 1)) != 0) {
 646             len--;
 647             crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 648         }
 649
 650         /* Compute the CRC on as many N z_word_t blocks as are available. */
 651         blks = len / (N * W);
 652         len -= blks * N * W;
 653         words = (z_word_t const *)buf;
 654
 655         /* Do endian check at execution time instead of compile time, since ARM
 656            processors can change the endianess at execution time. If the
 657            compiler knows what the endianess will be, it can optimize out the
 658            check and the unused branch. */
 659         endian = 1;
 660         if (*(unsigned char *)&endian) {
 661             /* Little endian. */
 662
 663             z_crc_t crc0;
 664             z_word_t word0;
 665 #if N > 1
 666             z_crc_t crc1;
 667             z_word_t word1;
 668 #if N > 2
 669             z_crc_t crc2;
 670             z_word_t word2;
 671 #if N > 3
 672             z_crc_t crc3;
 673             z_word_t word3;
 674 #if N > 4
 675             z_crc_t crc4;
 676             z_word_t word4;
 677 #if N > 5
 678             z_crc_t crc5;
 679             z_word_t word5;
 680 #endif
 681 #endif
 682 #endif
 683 #endif
 684 #endif
 685
 686             /* Initialize the CRC for each braid. */
 687             crc0 = crc;
 688 #if N > 1
 689             crc1 = 0;
 690 #if N > 2
 691             crc2 = 0;
 692 #if N > 3
 693             crc3 = 0;
 694 #if N > 4
 695             crc4 = 0;
 696 #if N > 5
 697             crc5 = 0;
 698 #endif
 699 #endif
 700 #endif
 701 #endif
 702 #endif
 703
 704             /*
 705               Process the first blks-1 blocks, computing the CRCs on each braid
 706               independently.
 707              */
 708             while (--blks) {
 709                 /* Load the word for each braid into registers. */
 710                 word0 = crc0 ^ words[0];
 711 #if N > 1
 712                 word1 = crc1 ^ words[1];
 713 #if N > 2
 714                 word2 = crc2 ^ words[2];
 715 #if N > 3
 716                 word3 = crc3 ^ words[3];
 717 #if N > 4
 718                 word4 = crc4 ^ words[4];
 719 #if N > 5
 720                 word5 = crc5 ^ words[5];
 721 #endif
 722 #endif
 723 #endif
 724 #endif
 725 #endif
 726                 words += N;
 727
 728                 /* Compute and update the CRC for each word. The loop should
 729                    get unrolled. */
 730                 crc0 = crc_braid_table[0][word0 & 0xff];
 731 #if N > 1
 732                 crc1 = crc_braid_table[0][word1 & 0xff];
 733 #if N > 2
 734                 crc2 = crc_braid_table[0][word2 & 0xff];
 735 #if N > 3
 736                 crc3 = crc_braid_table[0][word3 & 0xff];
 737 #if N > 4
 738                 crc4 = crc_braid_table[0][word4 & 0xff];
 739 #if N > 5
 740                 crc5 = crc_braid_table[0][word5 & 0xff];
 741 #endif
 742 #endif
 743 #endif
 744 #endif
 745 #endif
 746                 for (k = 1; k < W; k++) {
 747                     crc0 ^= crc_braid_table[k][(word0 >> (k << 3)) & 0xff];
 748 #if N > 1
 749                     crc1 ^= crc_braid_table[k][(word1 >> (k << 3)) & 0xff];
 750 #if N > 2
 751                     crc2 ^= crc_braid_table[k][(word2 >> (k << 3)) & 0xff];
 752 #if N > 3
 753                     crc3 ^= crc_braid_table[k][(word3 >> (k << 3)) & 0xff];
 754 #if N > 4
 755                     crc4 ^= crc_braid_table[k][(word4 >> (k << 3)) & 0xff];
 756 #if N > 5
 757                     crc5 ^= crc_braid_table[k][(word5 >> (k << 3)) & 0xff];
 758 #endif
 759 #endif
 760 #endif
 761 #endif
 762 #endif
 763                 }
 764             }
 765
 766             /*
 767               Process the last block, combining the CRCs of the N braids at the
 768               same time.
 769              */
 770             crc = crc_word(crc0 ^ words[0]);
 771 #if N > 1
 772             crc = crc_word(crc1 ^ words[1] ^ crc);
 773 #if N > 2
 774             crc = crc_word(crc2 ^ words[2] ^ crc);
 775 #if N > 3
 776             crc = crc_word(crc3 ^ words[3] ^ crc);
 777 #if N > 4
 778             crc = crc_word(crc4 ^ words[4] ^ crc);
 779 #if N > 5
 780             crc = crc_word(crc5 ^ words[5] ^ crc);
 781 #endif
 782 #endif
 783 #endif
 784 #endif
 785 #endif
 786             words += N;
 787         }
 788         else {
 789             /* Big endian. */
 790
 791             z_word_t crc0, word0, comb;
 792 #if N > 1
 793             z_word_t crc1, word1;
 794 #if N > 2
 795             z_word_t crc2, word2;
 796 #if N > 3
 797             z_word_t crc3, word3;
 798 #if N > 4
 799             z_word_t crc4, word4;
 800 #if N > 5
 801             z_word_t crc5, word5;
 802 #endif
 803 #endif
 804 #endif
 805 #endif
 806 #endif
 807
 808             /* Initialize the CRC for each braid. */
 809             crc0 = byte_swap(crc);
 810 #if N > 1
 811             crc1 = 0;
 812 #if N > 2
 813             crc2 = 0;
 814 #if N > 3
 815             crc3 = 0;
 816 #if N > 4
 817             crc4 = 0;
 818 #if N > 5
 819             crc5 = 0;
 820 #endif
 821 #endif
 822 #endif
 823 #endif
 824 #endif
 825
 826             /*
 827               Process the first blks-1 blocks, computing the CRCs on each braid
 828               independently.
 829              */
 830             while (--blks) {
 831                 /* Load the word for each braid into registers. */
 832                 word0 = crc0 ^ words[0];
 833 #if N > 1
 834                 word1 = crc1 ^ words[1];
 835 #if N > 2
 836                 word2 = crc2 ^ words[2];
 837 #if N > 3
 838                 word3 = crc3 ^ words[3];
 839 #if N > 4
 840                 word4 = crc4 ^ words[4];
 841 #if N > 5
 842                 word5 = crc5 ^ words[5];
 843 #endif
 844 #endif
 845 #endif
 846 #endif
 847 #endif
 848                 words += N;
 849
 850                 /* Compute and update the CRC for each word. The loop should
 851                    get unrolled. */
 852                 crc0 = crc_braid_big_table[0][word0 & 0xff];
 853 #if N > 1
 854                 crc1 = crc_braid_big_table[0][word1 & 0xff];
 855 #if N > 2
 856                 crc2 = crc_braid_big_table[0][word2 & 0xff];
 857 #if N > 3
 858                 crc3 = crc_braid_big_table[0][word3 & 0xff];
 859 #if N > 4
 860                 crc4 = crc_braid_big_table[0][word4 & 0xff];
 861 #if N > 5
 862                 crc5 = crc_braid_big_table[0][word5 & 0xff];
 863 #endif
 864 #endif
 865 #endif
 866 #endif
 867 #endif
 868                 for (k = 1; k < W; k++) {
 869                     crc0 ^= crc_braid_big_table[k][(word0 >> (k << 3)) & 0xff];
 870 #if N > 1
 871                     crc1 ^= crc_braid_big_table[k][(word1 >> (k << 3)) & 0xff];
 872 #if N > 2
 873                     crc2 ^= crc_braid_big_table[k][(word2 >> (k << 3)) & 0xff];
 874 #if N > 3
 875                     crc3 ^= crc_braid_big_table[k][(word3 >> (k << 3)) & 0xff];
 876 #if N > 4
 877                     crc4 ^= crc_braid_big_table[k][(word4 >> (k << 3)) & 0xff];
 878 #if N > 5
 879                     crc5 ^= crc_braid_big_table[k][(word5 >> (k << 3)) & 0xff];
 880 #endif
 881 #endif
 882 #endif
 883 #endif
 884 #endif
 885                 }
 886             }
 887
 888             /*
 889               Process the last block, combining the CRCs of the N braids at the
 890               same time.
 891              */
 892             comb = crc_word_big(crc0 ^ words[0]);
 893 #if N > 1
 894             comb = crc_word_big(crc1 ^ words[1] ^ comb);
 895 #if N > 2
 896             comb = crc_word_big(crc2 ^ words[2] ^ comb);
 897 #if N > 3
 898             comb = crc_word_big(crc3 ^ words[3] ^ comb);
 899 #if N > 4
 900             comb = crc_word_big(crc4 ^ words[4] ^ comb);
 901 #if N > 5
 902             comb = crc_word_big(crc5 ^ words[5] ^ comb);
 903 #endif
 904 #endif
 905 #endif
 906 #endif
 907 #endif
 908             words += N;
 909             crc = byte_swap(comb);
 910         }
 911
 912         /*
 913           Update the pointer to the remaining bytes to process.
 914          */
 915         buf = (unsigned char const *)words;
 916     }
 917
 918 #endif /* W */
 919
 920     /* Complete the computation of the CRC on any remaining bytes. */
 921     while (len >= 8) {
 922         len -= 8;
 923         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 924         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 925         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 926         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 927         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 928         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 929         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 930         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 931     }
 932     while (len) {
 933         len--;
 934         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 935     }
 936
 937     /* Return the CRC, post-conditioned. */
 938     return crc ^ 0xffffffff;
 939 }
 940
 941 /* ========================================================================= */
 942 unsigned long ZEXPORT crc32(crc, buf, len)
 943     unsigned long crc;
 944     const unsigned char FAR *buf;
 945     uInt len;
 946 {
 947     return crc32_z(crc, buf, len);
 948 }
 949
 950 /* ========================================================================= */
 951 uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
 952     uLong crc1;
 953     uLong crc2;
 954     z_off64_t len2;
 955 {
 956 #ifdef DYNAMIC_CRC_TABLE
 957     once(&made, make_crc_table);
 958 #endif /* DYNAMIC_CRC_TABLE */
 959     return multmodp(x2nmodp(len2, 3), crc1) ^ crc2;
 960 }
 961
 962 /* ========================================================================= */
 963 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
 964     uLong crc1;
 965     uLong crc2;
 966     z_off_t len2;
 967 {
 968     return crc32_combine64(crc1, crc2, len2);
 969 }
 970
 971 /* ========================================================================= */
 972 uLong ZEXPORT crc32_combine_gen64(len2)
 973     z_off64_t len2;
 974 {
 975 #ifdef DYNAMIC_CRC_TABLE
 976     once(&made, make_crc_table);
 977 #endif /* DYNAMIC_CRC_TABLE */
 978     return x2nmodp(len2, 3);
 979 }
 980
 981 /* ========================================================================= */
 982 uLong ZEXPORT crc32_combine_gen(len2)
 983     z_off_t len2;
 984 {
 985     return crc32_combine_gen64(len2);
 986 }
 987
 988 /* ========================================================================= */
 989 uLong crc32_combine_op(crc1, crc2, op)
 990     uLong crc1;
 991     uLong crc2;
 992     uLong op;
 993 {
 994     return multmodp(op, crc1) ^ crc2;
 995 }