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
13b8382935SToomas 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
54b8382935SToomas 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
59*148fd93eSToomas Soome #endif
60b8382935SToomas 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 */
66b8382935SToomas 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
76*148fd93eSToomas 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));
102*148fd93eSToomas 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
136*148fd93eSToomas 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,
250b8382935SToomas 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
252b8382935SToomas 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
258b8382935SToomas 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.
264b8382935SToomas 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.
268b8382935SToomas 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);
291b8382935SToomas 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
296b8382935SToomas 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" : "");
372b8382935SToomas 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");
414*148fd93eSToomas 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" : ", "));
449b8382935SToomas 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;
493*148fd93eSToomas 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
597*148fd93eSToomas 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;
610*148fd93eSToomas 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;
620*148fd93eSToomas Soome
621*148fd93eSToomas Soome #ifdef DYNAMIC_CRC_TABLE
622*148fd93eSToomas Soome once(&made, make_crc_table);
623*148fd93eSToomas Soome #endif /* DYNAMIC_CRC_TABLE */
624*148fd93eSToomas Soome
625*148fd93eSToomas Soome /* Pre-condition the CRC */
626*148fd93eSToomas Soome crc = (~crc) & 0xffffffff;
627*148fd93eSToomas 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));
633*148fd93eSToomas 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;
658*148fd93eSToomas Soome }
659*148fd93eSToomas 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;
699*148fd93eSToomas Soome }
700*148fd93eSToomas Soome
701*148fd93eSToomas Soome #else
702*148fd93eSToomas Soome
703*148fd93eSToomas Soome #ifdef W
704*148fd93eSToomas Soome
705*148fd93eSToomas 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.
709*148fd93eSToomas 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 }
717*148fd93eSToomas 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)730b8382935SToomas Soome unsigned long ZEXPORT crc32_z(unsigned long crc, const unsigned char FAR *buf,
731b8382935SToomas 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
736b8382935SToomas Soome #ifdef DYNAMIC_CRC_TABLE
737*148fd93eSToomas Soome once(&made, make_crc_table);
738b8382935SToomas 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
744*148fd93eSToomas 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;
751*148fd93eSToomas 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 }
757*148fd93eSToomas 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. */
767b8382935SToomas 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
871b8382935SToomas 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;
1024*148fd93eSToomas Soome }
1025*148fd93eSToomas Soome
1026*148fd93eSToomas Soome #endif /* W */
1027*148fd93eSToomas Soome
1028*148fd93eSToomas Soome /* Complete the computation of the CRC on any remaining bytes. */
1029b8382935SToomas Soome while (len >= 8) {
1030b8382935SToomas 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;
1047*148fd93eSToomas Soome }
1048*148fd93eSToomas Soome
1049*148fd93eSToomas Soome #endif
1050*148fd93eSToomas Soome
1051b8382935SToomas Soome /* ========================================================================= */
crc32(unsigned long crc,const unsigned char FAR * buf,uInt len)1052b8382935SToomas Soome unsigned long ZEXPORT crc32(unsigned long crc, const unsigned char FAR *buf,
1053b8382935SToomas Soome uInt len)
1054b8382935SToomas Soome {
1055b8382935SToomas 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)1068b8382935SToomas Soome uLong ZEXPORT crc32_combine(uLong crc1, uLong crc2, z_off_t len2)
1069b8382935SToomas Soome {
1070*148fd93eSToomas Soome return crc32_combine64(crc1, crc2, len2);
1071b8382935SToomas 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)
1075b8382935SToomas 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);
1080*148fd93eSToomas Soome }
1081*148fd93eSToomas Soome
1082*148fd93eSToomas Soome /* ========================================================================= */
crc32_combine_gen(z_off_t len2)1083*148fd93eSToomas Soome uLong ZEXPORT crc32_combine_gen(z_off_t len2)
1084*148fd93eSToomas Soome {
1085*148fd93eSToomas Soome return crc32_combine_gen64(len2);
1086*148fd93eSToomas Soome }
1087*148fd93eSToomas 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)
1090*148fd93eSToomas Soome {
1091*148fd93eSToomas Soome return multmodp(op, crc1) ^ (crc2 & 0xffffffff);
1092b8382935SToomas Soome }
1093