Geant4 Cross Reference

Cross-Referencing   Geant4
Geant4/externals/zlib/src/crc32.c

Version: [ ReleaseNotes ] [ 1.0 ] [ 1.1 ] [ 2.0 ] [ 3.0 ] [ 3.1 ] [ 3.2 ] [ 4.0 ] [ 4.0.p1 ] [ 4.0.p2 ] [ 4.1 ] [ 4.1.p1 ] [ 5.0 ] [ 5.0.p1 ] [ 5.1 ] [ 5.1.p1 ] [ 5.2 ] [ 5.2.p1 ] [ 5.2.p2 ] [ 6.0 ] [ 6.0.p1 ] [ 6.1 ] [ 6.2 ] [ 6.2.p1 ] [ 6.2.p2 ] [ 7.0 ] [ 7.0.p1 ] [ 7.1 ] [ 7.1.p1 ] [ 8.0 ] [ 8.0.p1 ] [ 8.1 ] [ 8.1.p1 ] [ 8.1.p2 ] [ 8.2 ] [ 8.2.p1 ] [ 8.3 ] [ 8.3.p1 ] [ 8.3.p2 ] [ 9.0 ] [ 9.0.p1 ] [ 9.0.p2 ] [ 9.1 ] [ 9.1.p1 ] [ 9.1.p2 ] [ 9.1.p3 ] [ 9.2 ] [ 9.2.p1 ] [ 9.2.p2 ] [ 9.2.p3 ] [ 9.2.p4 ] [ 9.3 ] [ 9.3.p1 ] [ 9.3.p2 ] [ 9.4 ] [ 9.4.p1 ] [ 9.4.p2 ] [ 9.4.p3 ] [ 9.4.p4 ] [ 9.5 ] [ 9.5.p1 ] [ 9.5.p2 ] [ 9.6 ] [ 9.6.p1 ] [ 9.6.p2 ] [ 9.6.p3 ] [ 9.6.p4 ] [ 10.0 ] [ 10.0.p1 ] [ 10.0.p2 ] [ 10.0.p3 ] [ 10.0.p4 ] [ 10.1 ] [ 10.1.p1 ] [ 10.1.p2 ] [ 10.1.p3 ] [ 10.2 ] [ 10.2.p1 ] [ 10.2.p2 ] [ 10.2.p3 ] [ 10.3 ] [ 10.3.p1 ] [ 10.3.p2 ] [ 10.3.p3 ] [ 10.4 ] [ 10.4.p1 ] [ 10.4.p2 ] [ 10.4.p3 ] [ 10.5 ] [ 10.5.p1 ] [ 10.6 ] [ 10.6.p1 ] [ 10.6.p2 ] [ 10.6.p3 ] [ 10.7 ] [ 10.7.p1 ] [ 10.7.p2 ] [ 10.7.p3 ] [ 10.7.p4 ] [ 11.0 ] [ 11.0.p1 ] [ 11.0.p2 ] [ 11.0.p3, ] [ 11.0.p4 ] [ 11.1 ] [ 11.1.1 ] [ 11.1.2 ] [ 11.1.3 ] [ 11.2 ] [ 11.2.1 ] [ 11.2.2 ] [ 11.3.0 ]

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