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