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