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