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