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 * 2^k) modulo p(x). Requires that x2n_table[] has been
 534   initialized.
 535  */
 536 local z_crc_t x2nmodp(n, k)
 537     z_off64_t n;
 538     unsigned k;
 539 {
 540     z_crc_t p;
 541
 542     p = (z_crc_t)1 << 31;           /* x^0 == 1 */
 543     while (n) {
 544         if (n & 1)
 545             p = multmodp(x2n_table[k & 31], p);
 546         n >>= 1;
 547         k++;
 548     }
 549     return p;
 550 }
 551
 552 #ifdef W
 553
 554 /*
 555   Swap the bytes in a z_word_t to convert between little and big endian. Any
 556   self-respecting compiler will optimize this to a single machine byte-swap
 557   instruction, if one is available. This assumes that word_t is either 32 bits
 558   or 64 bits.
 559  */
 560 local z_word_t byte_swap(word)
 561     z_word_t word;
 562 {
 563 #if W == 8
 564     return
 565         (word & 0xff00000000000000) >> 56 |
 566         (word & 0xff000000000000) >> 40 |
 567         (word & 0xff0000000000) >> 24 |
 568         (word & 0xff00000000) >> 8 |
 569         (word & 0xff000000) << 8 |
 570         (word & 0xff0000) << 24 |
 571         (word & 0xff00) << 40 |
 572         (word & 0xff) << 56;
 573 #else   /* W == 4 */
 574     return
 575         (word & 0xff000000) >> 24 |
 576         (word & 0xff0000) >> 8 |
 577         (word & 0xff00) << 8 |
 578         (word & 0xff) << 24;
 579 #endif
 580 }
 581
 582 /*
 583   Return the CRC of the W bytes in the word_t data, taking the
 584   least-significant byte of the word as the first byte of data, without any pre
 585   or post conditioning. This is used to combine the CRCs of each braid.
 586  */
 587 local z_crc_t crc_word(data)
 588     z_word_t data;
 589 {
 590     int k;
 591     for (k = 0; k < W; k++)
 592         data = (data >> 8) ^ crc_table[data & 0xff];
 593     return (z_crc_t)data;
 594 }
 595
 596 local z_word_t crc_word_big(data)
 597     z_word_t data;
 598 {
 599     int k;
 600     for (k = 0; k < W; k++)
 601         data = (data << 8) ^
 602             crc_big_table[(data >> ((W - 1) << 3)) & 0xff];
 603     return data;
 604 }
 605
 606 #endif /* W */
 607
 608 /* =========================================================================
 609  * This function can be used by asm versions of crc32(), and to force the
 610  * generation of the CRC tables in a threaded application.
 611  */
 612 const z_crc_t FAR * ZEXPORT get_crc_table()
 613 {
 614 #ifdef DYNAMIC_CRC_TABLE
 615     once(&made, make_crc_table);
 616 #endif /* DYNAMIC_CRC_TABLE */
 617     return (const z_crc_t FAR *)crc_table;
 618 }
 619
 620 /* ========================================================================= */
 621 unsigned long ZEXPORT crc32_z(crc, buf, len)
 622     unsigned long crc;
 623     const unsigned char FAR *buf;
 624     z_size_t len;
 625 {
 626     /* Return initial CRC, if requested. */
 627     if (buf == Z_NULL) return 0;
 628
 629 #ifdef DYNAMIC_CRC_TABLE
 630     once(&made, make_crc_table);
 631 #endif /* DYNAMIC_CRC_TABLE */
 632
 633     /* Pre-condition the CRC */
 634     crc ^= 0xffffffff;
 635
 636 #ifdef W
 637
 638     /* If provided enough bytes, do a braided CRC calculation. */
 639     if (len >= N * W + W - 1) {
 640         z_size_t blks;
 641         z_word_t const *words;
 642         unsigned endian;
 643         int k;
 644
 645         /* Compute the CRC up to a z_word_t boundary. */
 646         while (len && ((z_size_t)buf & (W - 1)) != 0) {
 647             len--;
 648             crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 649         }
 650
 651         /* Compute the CRC on as many N z_word_t blocks as are available. */
 652         blks = len / (N * W);
 653         len -= blks * N * W;
 654         words = (z_word_t const *)buf;
 655
 656         /* Do endian check at execution time instead of compile time, since ARM
 657            processors can change the endianess at execution time. If the
 658            compiler knows what the endianess will be, it can optimize out the
 659            check and the unused branch. */
 660         endian = 1;
 661         if (*(unsigned char *)&endian) {
 662             /* Little endian. */
 663
 664             z_crc_t crc0;
 665             z_word_t word0;
 666 #if N > 1
 667             z_crc_t crc1;
 668             z_word_t word1;
 669 #if N > 2
 670             z_crc_t crc2;
 671             z_word_t word2;
 672 #if N > 3
 673             z_crc_t crc3;
 674             z_word_t word3;
 675 #if N > 4
 676             z_crc_t crc4;
 677             z_word_t word4;
 678 #if N > 5
 679             z_crc_t crc5;
 680             z_word_t word5;
 681 #endif
 682 #endif
 683 #endif
 684 #endif
 685 #endif
 686
 687             /* Initialize the CRC for each braid. */
 688             crc0 = crc;
 689 #if N > 1
 690             crc1 = 0;
 691 #if N > 2
 692             crc2 = 0;
 693 #if N > 3
 694             crc3 = 0;
 695 #if N > 4
 696             crc4 = 0;
 697 #if N > 5
 698             crc5 = 0;
 699 #endif
 700 #endif
 701 #endif
 702 #endif
 703 #endif
 704
 705             /*
 706               Process the first blks-1 blocks, computing the CRCs on each braid
 707               independently.
 708              */
 709             while (--blks) {
 710                 /* Load the word for each braid into registers. */
 711                 word0 = crc0 ^ words[0];
 712 #if N > 1
 713                 word1 = crc1 ^ words[1];
 714 #if N > 2
 715                 word2 = crc2 ^ words[2];
 716 #if N > 3
 717                 word3 = crc3 ^ words[3];
 718 #if N > 4
 719                 word4 = crc4 ^ words[4];
 720 #if N > 5
 721                 word5 = crc5 ^ words[5];
 722 #endif
 723 #endif
 724 #endif
 725 #endif
 726 #endif
 727                 words += N;
 728
 729                 /* Compute and update the CRC for each word. The loop should
 730                    get unrolled. */
 731                 crc0 = crc_braid_table[0][word0 & 0xff];
 732 #if N > 1
 733                 crc1 = crc_braid_table[0][word1 & 0xff];
 734 #if N > 2
 735                 crc2 = crc_braid_table[0][word2 & 0xff];
 736 #if N > 3
 737                 crc3 = crc_braid_table[0][word3 & 0xff];
 738 #if N > 4
 739                 crc4 = crc_braid_table[0][word4 & 0xff];
 740 #if N > 5
 741                 crc5 = crc_braid_table[0][word5 & 0xff];
 742 #endif
 743 #endif
 744 #endif
 745 #endif
 746 #endif
 747                 for (k = 1; k < W; k++) {
 748                     crc0 ^= crc_braid_table[k][(word0 >> (k << 3)) & 0xff];
 749 #if N > 1
 750                     crc1 ^= crc_braid_table[k][(word1 >> (k << 3)) & 0xff];
 751 #if N > 2
 752                     crc2 ^= crc_braid_table[k][(word2 >> (k << 3)) & 0xff];
 753 #if N > 3
 754                     crc3 ^= crc_braid_table[k][(word3 >> (k << 3)) & 0xff];
 755 #if N > 4
 756                     crc4 ^= crc_braid_table[k][(word4 >> (k << 3)) & 0xff];
 757 #if N > 5
 758                     crc5 ^= crc_braid_table[k][(word5 >> (k << 3)) & 0xff];
 759 #endif
 760 #endif
 761 #endif
 762 #endif
 763 #endif
 764                 }
 765             }
 766
 767             /*
 768               Process the last block, combining the CRCs of the N braids at the
 769               same time.
 770              */
 771             crc = crc_word(crc0 ^ words[0]);
 772 #if N > 1
 773             crc = crc_word(crc1 ^ words[1] ^ crc);
 774 #if N > 2
 775             crc = crc_word(crc2 ^ words[2] ^ crc);
 776 #if N > 3
 777             crc = crc_word(crc3 ^ words[3] ^ crc);
 778 #if N > 4
 779             crc = crc_word(crc4 ^ words[4] ^ crc);
 780 #if N > 5
 781             crc = crc_word(crc5 ^ words[5] ^ crc);
 782 #endif
 783 #endif
 784 #endif
 785 #endif
 786 #endif
 787             words += N;
 788         }
 789         else {
 790             /* Big endian. */
 791
 792             z_word_t crc0, word0, comb;
 793 #if N > 1
 794             z_word_t crc1, word1;
 795 #if N > 2
 796             z_word_t crc2, word2;
 797 #if N > 3
 798             z_word_t crc3, word3;
 799 #if N > 4
 800             z_word_t crc4, word4;
 801 #if N > 5
 802             z_word_t crc5, word5;
 803 #endif
 804 #endif
 805 #endif
 806 #endif
 807 #endif
 808
 809             /* Initialize the CRC for each braid. */
 810             crc0 = byte_swap(crc);
 811 #if N > 1
 812             crc1 = 0;
 813 #if N > 2
 814             crc2 = 0;
 815 #if N > 3
 816             crc3 = 0;
 817 #if N > 4
 818             crc4 = 0;
 819 #if N > 5
 820             crc5 = 0;
 821 #endif
 822 #endif
 823 #endif
 824 #endif
 825 #endif
 826
 827             /*
 828               Process the first blks-1 blocks, computing the CRCs on each braid
 829               independently.
 830              */
 831             while (--blks) {
 832                 /* Load the word for each braid into registers. */
 833                 word0 = crc0 ^ words[0];
 834 #if N > 1
 835                 word1 = crc1 ^ words[1];
 836 #if N > 2
 837                 word2 = crc2 ^ words[2];
 838 #if N > 3
 839                 word3 = crc3 ^ words[3];
 840 #if N > 4
 841                 word4 = crc4 ^ words[4];
 842 #if N > 5
 843                 word5 = crc5 ^ words[5];
 844 #endif
 845 #endif
 846 #endif
 847 #endif
 848 #endif
 849                 words += N;
 850
 851                 /* Compute and update the CRC for each word. The loop should
 852                    get unrolled. */
 853                 crc0 = crc_braid_big_table[0][word0 & 0xff];
 854 #if N > 1
 855                 crc1 = crc_braid_big_table[0][word1 & 0xff];
 856 #if N > 2
 857                 crc2 = crc_braid_big_table[0][word2 & 0xff];
 858 #if N > 3
 859                 crc3 = crc_braid_big_table[0][word3 & 0xff];
 860 #if N > 4
 861                 crc4 = crc_braid_big_table[0][word4 & 0xff];
 862 #if N > 5
 863                 crc5 = crc_braid_big_table[0][word5 & 0xff];
 864 #endif
 865 #endif
 866 #endif
 867 #endif
 868 #endif
 869                 for (k = 1; k < W; k++) {
 870                     crc0 ^= crc_braid_big_table[k][(word0 >> (k << 3)) & 0xff];
 871 #if N > 1
 872                     crc1 ^= crc_braid_big_table[k][(word1 >> (k << 3)) & 0xff];
 873 #if N > 2
 874                     crc2 ^= crc_braid_big_table[k][(word2 >> (k << 3)) & 0xff];
 875 #if N > 3
 876                     crc3 ^= crc_braid_big_table[k][(word3 >> (k << 3)) & 0xff];
 877 #if N > 4
 878                     crc4 ^= crc_braid_big_table[k][(word4 >> (k << 3)) & 0xff];
 879 #if N > 5
 880                     crc5 ^= crc_braid_big_table[k][(word5 >> (k << 3)) & 0xff];
 881 #endif
 882 #endif
 883 #endif
 884 #endif
 885 #endif
 886                 }
 887             }
 888
 889             /*
 890               Process the last block, combining the CRCs of the N braids at the
 891               same time.
 892              */
 893             comb = crc_word_big(crc0 ^ words[0]);
 894 #if N > 1
 895             comb = crc_word_big(crc1 ^ words[1] ^ comb);
 896 #if N > 2
 897             comb = crc_word_big(crc2 ^ words[2] ^ comb);
 898 #if N > 3
 899             comb = crc_word_big(crc3 ^ words[3] ^ comb);
 900 #if N > 4
 901             comb = crc_word_big(crc4 ^ words[4] ^ comb);
 902 #if N > 5
 903             comb = crc_word_big(crc5 ^ words[5] ^ comb);
 904 #endif
 905 #endif
 906 #endif
 907 #endif
 908 #endif
 909             words += N;
 910             crc = byte_swap(comb);
 911         }
 912
 913         /*
 914           Update the pointer to the remaining bytes to process.
 915          */
 916         buf = (unsigned char const *)words;
 917     }
 918
 919 #endif /* W */
 920
 921     /* Complete the computation of the CRC on any remaining bytes. */
 922     while (len >= 8) {
 923         len -= 8;
 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         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 932     }
 933     while (len) {
 934         len--;
 935         crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
 936     }
 937
 938     /* Return the CRC, post-conditioned. */
 939     return crc ^ 0xffffffff;
 940 }
 941
 942 /* ========================================================================= */
 943 unsigned long ZEXPORT crc32(crc, buf, len)
 944     unsigned long crc;
 945     const unsigned char FAR *buf;
 946     uInt len;
 947 {
 948     return crc32_z(crc, buf, len);
 949 }
 950
 951 /* ========================================================================= */
 952 uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
 953     uLong crc1;
 954     uLong crc2;
 955     z_off64_t len2;
 956 {
 957 #ifdef DYNAMIC_CRC_TABLE
 958     once(&made, make_crc_table);
 959 #endif /* DYNAMIC_CRC_TABLE */
 960     return multmodp(x2nmodp(len2, 3), crc1) ^ crc2;
 961 }
 962
 963 /* ========================================================================= */
 964 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
 965     uLong crc1;
 966     uLong crc2;
 967     z_off_t len2;
 968 {
 969     return crc32_combine64(crc1, crc2, len2);
 970 }
 971
 972 /* ========================================================================= */
 973 uLong ZEXPORT crc32_combine_gen64(len2)
 974     z_off64_t len2;
 975 {
 976 #ifdef DYNAMIC_CRC_TABLE
 977     once(&made, make_crc_table);
 978 #endif /* DYNAMIC_CRC_TABLE */
 979     return x2nmodp(len2, 3);
 980 }
 981
 982 /* ========================================================================= */
 983 uLong ZEXPORT crc32_combine_gen(len2)
 984     z_off_t len2;
 985 {
 986     return crc32_combine_gen64(len2);
 987 }
 988
 989 /* ========================================================================= */
 990 uLong crc32_combine_op(crc1, crc2, op)
 991     uLong crc1;
 992     uLong crc2;
 993     uLong op;
 994 {
 995     return multmodp(op, crc1) ^ crc2;
 996 }