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