1 /* crc32.c -- compute the CRC-32 of a data stream
2 * Copyright (C) 1995-2022 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
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.
13 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
14 protection on the static variables used to control the first-use generation
15 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
16 first call get_crc_table() to initialize the tables before allowing more than
17 one thread to use crc32().
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.
25 # ifndef DYNAMIC_CRC_TABLE
26 # define DYNAMIC_CRC_TABLE
27 # endif /* !DYNAMIC_CRC_TABLE */
30 #include "zutil.h" /* for Z_U4, Z_U8, z_crc_t, and FAR definitions */
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.
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.
60 # error N must be in 1..6
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.
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
80 # define W 8 /* required for MAKECRCH */
82 # if defined(__x86_64__) || defined(__aarch64__)
90 # if W == 8 && defined(Z_U8)
91 typedef Z_U8 z_word_t
;
95 typedef Z_U4 z_word_t
;
101 /* If available, use the ARM processor CRC32 instruction. */
102 #if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32) && W == 8
106 #if defined(W) && (!defined(ARMCRC32) || defined(DYNAMIC_CRC_TABLE))
108 Swap the bytes in a z_word_t to convert between little and big endian. Any
109 self-respecting compiler will optimize this to a single machine byte-swap
110 instruction, if one is available. This assumes that word_t is either 32 bits
113 local z_word_t
byte_swap(z_word_t word
) {
116 (word
& 0xff00000000000000) >> 56 |
117 (word
& 0xff000000000000) >> 40 |
118 (word
& 0xff0000000000) >> 24 |
119 (word
& 0xff00000000) >> 8 |
120 (word
& 0xff000000) << 8 |
121 (word
& 0xff0000) << 24 |
122 (word
& 0xff00) << 40 |
126 (word
& 0xff000000) >> 24 |
127 (word
& 0xff0000) >> 8 |
128 (word
& 0xff00) << 8 |
134 #ifdef DYNAMIC_CRC_TABLE
135 /* =========================================================================
136 * Table of powers of x for combining CRC-32s, filled in by make_crc_table()
139 local z_crc_t FAR x2n_table
[32];
141 /* =========================================================================
142 * Tables for byte-wise and braided CRC-32 calculations, and a table of powers
143 * of x for combining CRC-32s, all made by make_crc_table().
148 /* CRC polynomial. */
149 #define POLY 0xedb88320 /* p(x) reflected, with x^32 implied */
152 Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial,
153 reflected. For speed, this requires that a not be zero.
155 local z_crc_t
multmodp(z_crc_t a
, z_crc_t b
) {
158 m
= (z_crc_t
)1 << 31;
163 if ((a
& (m
- 1)) == 0)
167 b
= b
& 1 ? (b
>> 1) ^ POLY
: b
>> 1;
173 Return x^(n * 2^k) modulo p(x). Requires that x2n_table[] has been
176 local z_crc_t
x2nmodp(z_off64_t n
, unsigned k
) {
179 p
= (z_crc_t
)1 << 31; /* x^0 == 1 */
182 p
= multmodp(x2n_table
[k
& 31], p
);
189 #ifdef DYNAMIC_CRC_TABLE
190 /* =========================================================================
191 * Build the tables for byte-wise and braided CRC-32 calculations, and a table
192 * of powers of x for combining CRC-32s.
194 local z_crc_t FAR crc_table
[256];
196 local z_word_t FAR crc_big_table
[256];
197 local z_crc_t FAR crc_braid_table
[W
][256];
198 local z_word_t FAR crc_braid_big_table
[W
][256];
199 local
void braid(z_crc_t
[][256], z_word_t
[][256], int, int);
202 local
void write_table(FILE *, const z_crc_t FAR
*, int);
203 local
void write_table32hi(FILE *, const z_word_t FAR
*, int);
204 local
void write_table64(FILE *, const z_word_t FAR
*, int);
205 #endif /* MAKECRCH */
208 Define a once() function depending on the availability of atomics. If this is
209 compiled with DYNAMIC_CRC_TABLE defined, and if CRCs will be computed in
210 multiple threads, and if atomics are not available, then get_crc_table() must
211 be called to initialize the tables and must return before any threads are
212 allowed to compute or combine CRCs.
215 /* Definition of once functionality. */
216 typedef struct once_s once_t
;
218 /* Check for the availability of atomics. */
219 #if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \
220 !defined(__STDC_NO_ATOMICS__)
222 #include <stdatomic.h>
224 /* Structure for once(), which must be initialized with ONCE_INIT. */
229 #define ONCE_INIT {ATOMIC_FLAG_INIT, 0}
232 Run the provided init() function exactly once, even if multiple threads
233 invoke once() at the same time. The state must be a once_t initialized with
236 local
void once(once_t
*state
, void (*init
)(void)) {
237 if (!atomic_load(&state
->done
)) {
238 if (atomic_flag_test_and_set(&state
->begun
))
239 while (!atomic_load(&state
->done
))
243 atomic_store(&state
->done
, 1);
248 #else /* no atomics */
250 /* Structure for once(), which must be initialized with ONCE_INIT. */
255 #define ONCE_INIT {0, 0}
257 /* Test and set. Alas, not atomic, but tries to minimize the period of
259 local
int test_and_set(int volatile *flag
) {
267 /* Run the provided init() function once. This is not thread-safe. */
268 local
void once(once_t
*state
, void (*init
)(void)) {
270 if (test_and_set(&state
->begun
))
282 /* State for once(). */
283 local once_t made
= ONCE_INIT
;
286 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
287 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.
289 Polynomials over GF(2) are represented in binary, one bit per coefficient,
290 with the lowest powers in the most significant bit. Then adding polynomials
291 is just exclusive-or, and multiplying a polynomial by x is a right shift by
292 one. If we call the above polynomial p, and represent a byte as the
293 polynomial q, also with the lowest power in the most significant bit (so the
294 byte 0xb1 is the polynomial x^7+x^3+x^2+1), then the CRC is (q*x^32) mod p,
295 where a mod b means the remainder after dividing a by b.
297 This calculation is done using the shift-register method of multiplying and
298 taking the remainder. The register is initialized to zero, and for each
299 incoming bit, x^32 is added mod p to the register if the bit is a one (where
300 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by x
301 (which is shifting right by one and adding x^32 mod p if the bit shifted out
302 is a one). We start with the highest power (least significant bit) of q and
303 repeat for all eight bits of q.
305 The table is simply the CRC of all possible eight bit values. This is all the
306 information needed to generate CRCs on data a byte at a time for all
307 combinations of CRC register values and incoming bytes.
310 local
void make_crc_table(void) {
314 /* initialize the CRC of bytes tables */
315 for (i
= 0; i
< 256; i
++) {
317 for (j
= 0; j
< 8; j
++)
318 p
= p
& 1 ? (p
>> 1) ^ POLY
: p
>> 1;
321 crc_big_table
[i
] = byte_swap(p
);
325 /* initialize the x^2^n mod p(x) table */
326 p
= (z_crc_t
)1 << 30; /* x^1 */
328 for (n
= 1; n
< 32; n
++)
329 x2n_table
[n
] = p
= multmodp(p
, p
);
332 /* initialize the braiding tables -- needs x2n_table[] */
333 braid(crc_braid_table
, crc_braid_big_table
, N
, W
);
339 The crc32.h header file contains tables for both 32-bit and 64-bit
340 z_word_t's, and so requires a 64-bit type be available. In that case,
341 z_word_t must be defined to be 64-bits. This code then also generates
342 and writes out the tables for the case that z_word_t is 32 bits.
344 #if !defined(W) || W != 8
345 # error Need a 64-bit integer type in order to generate crc32.h.
350 z_word_t big
[8][256];
352 out
= fopen("crc32.h", "w");
353 if (out
== NULL
) return;
355 /* write out little-endian CRC table to crc32.h */
357 "/* crc32.h -- tables for rapid CRC calculation\n"
358 " * Generated automatically by crc32.c\n */\n"
360 "local const z_crc_t FAR crc_table[] = {\n"
362 write_table(out
, crc_table
, 256);
366 /* write out big-endian CRC table for 64-bit z_word_t to crc32.h */
373 "local const z_word_t FAR crc_big_table[] = {\n"
375 write_table64(out
, crc_big_table
, 256);
379 /* write out big-endian CRC table for 32-bit z_word_t to crc32.h */
382 "#else /* W == 4 */\n"
384 "local const z_word_t FAR crc_big_table[] = {\n"
386 write_table32hi(out
, crc_big_table
, 256);
392 /* write out braid tables for each value of N */
393 for (n
= 1; n
<= 6; n
++) {
398 /* compute braid tables for this N and 64-bit word_t */
399 braid(ltl
, big
, n
, 8);
401 /* write out braid tables for 64-bit z_word_t to crc32.h */
406 "local const z_crc_t FAR crc_braid_table[][256] = {\n");
407 for (k
= 0; k
< 8; k
++) {
409 write_table(out
, ltl
[k
], 256);
410 fprintf(out
, "}%s", k
< 7 ? ",\n" : "");
415 "local const z_word_t FAR crc_braid_big_table[][256] = {\n");
416 for (k
= 0; k
< 8; k
++) {
418 write_table64(out
, big
[k
], 256);
419 fprintf(out
, "}%s", k
< 7 ? ",\n" : "");
424 /* compute braid tables for this N and 32-bit word_t */
425 braid(ltl
, big
, n
, 4);
427 /* write out braid tables for 32-bit z_word_t to crc32.h */
430 "#else /* W == 4 */\n"
432 "local const z_crc_t FAR crc_braid_table[][256] = {\n");
433 for (k
= 0; k
< 4; k
++) {
435 write_table(out
, ltl
[k
], 256);
436 fprintf(out
, "}%s", k
< 3 ? ",\n" : "");
441 "local const z_word_t FAR crc_braid_big_table[][256] = {\n");
442 for (k
= 0; k
< 4; k
++) {
444 write_table32hi(out
, big
[k
], 256);
445 fprintf(out
, "}%s", k
< 3 ? ",\n" : "");
458 /* write out zeros operator table to crc32.h */
461 "local const z_crc_t FAR x2n_table[] = {\n"
463 write_table(out
, x2n_table
, 32);
468 #endif /* MAKECRCH */
474 Write the 32-bit values in table[0..k-1] to out, five per line in
475 hexadecimal separated by commas.
477 local
void write_table(FILE *out
, const z_crc_t FAR
*table
, int k
) {
480 for (n
= 0; n
< k
; n
++)
481 fprintf(out
, "%s0x%08lx%s", n
== 0 || n
% 5 ? "" : " ",
482 (unsigned long)(table
[n
]),
483 n
== k
- 1 ? "" : (n
% 5 == 4 ? ",\n" : ", "));
487 Write the high 32-bits of each value in table[0..k-1] to out, five per line
488 in hexadecimal separated by commas.
490 local
void write_table32hi(FILE *out
, const z_word_t FAR
*table
, int k
) {
493 for (n
= 0; n
< k
; n
++)
494 fprintf(out
, "%s0x%08lx%s", n
== 0 || n
% 5 ? "" : " ",
495 (unsigned long)(table
[n
] >> 32),
496 n
== k
- 1 ? "" : (n
% 5 == 4 ? ",\n" : ", "));
500 Write the 64-bit values in table[0..k-1] to out, three per line in
501 hexadecimal separated by commas. This assumes that if there is a 64-bit
502 type, then there is also a long long integer type, and it is at least 64
503 bits. If not, then the type cast and format string can be adjusted
506 local
void write_table64(FILE *out
, const z_word_t FAR
*table
, int k
) {
509 for (n
= 0; n
< k
; n
++)
510 fprintf(out
, "%s0x%016llx%s", n
== 0 || n
% 3 ? "" : " ",
511 (unsigned long long)(table
[n
]),
512 n
== k
- 1 ? "" : (n
% 3 == 2 ? ",\n" : ", "));
515 /* Actually do the deed. */
521 #endif /* MAKECRCH */
525 Generate the little and big-endian braid tables for the given n and z_word_t
526 size w. Each array must have room for w blocks of 256 elements.
528 local
void braid(z_crc_t ltl
[][256], z_word_t big
[][256], int n
, int w
) {
531 for (k
= 0; k
< w
; k
++) {
532 p
= x2nmodp((n
* w
+ 3 - k
) << 3, 0);
534 big
[w
- 1 - k
][0] = 0;
535 for (i
= 1; i
< 256; i
++) {
536 ltl
[k
][i
] = q
= multmodp(i
<< 24, p
);
537 big
[w
- 1 - k
][i
] = byte_swap(q
);
543 #endif /* DYNAMIC_CRC_TABLE */
545 /* =========================================================================
546 * This function can be used by asm versions of crc32(), and to force the
547 * generation of the CRC tables in a threaded application.
549 const z_crc_t FAR
* ZEXPORT
get_crc_table(void) {
550 #ifdef DYNAMIC_CRC_TABLE
551 once(&made
, make_crc_table
);
552 #endif /* DYNAMIC_CRC_TABLE */
553 return (const z_crc_t FAR
*)crc_table
;
556 /* =========================================================================
557 * Use ARM machine instructions if available. This will compute the CRC about
558 * ten times faster than the braided calculation. This code does not check for
559 * the presence of the CRC instruction at run time. __ARM_FEATURE_CRC32 will
560 * only be defined if the compilation specifies an ARM processor architecture
561 * that has the instructions. For example, compiling with -march=armv8.1-a or
562 * -march=armv8-a+crc, or -march=native if the compile machine has the crc32
568 Constants empirically determined to maximize speed. These values are from
569 measurements on a Cortex-A57. Your mileage may vary.
571 #define Z_BATCH 3990 /* number of words in a batch */
572 #define Z_BATCH_ZEROS 0xa10d3d0c /* computed from Z_BATCH = 3990 */
573 #define Z_BATCH_MIN 800 /* fewest words in a final batch */
575 unsigned long ZEXPORT
crc32_z(unsigned long crc
, const unsigned char FAR
*buf
,
579 const z_word_t
*word
;
580 z_word_t val0
, val1
, val2
;
581 z_size_t last
, last2
, i
;
584 /* Return initial CRC, if requested. */
585 if (buf
== Z_NULL
) return 0;
587 #ifdef DYNAMIC_CRC_TABLE
588 once(&made
, make_crc_table
);
589 #endif /* DYNAMIC_CRC_TABLE */
591 /* Pre-condition the CRC */
592 crc
= (~crc
) & 0xffffffff;
594 /* Compute the CRC up to a word boundary. */
595 while (len
&& ((z_size_t
)buf
& 7) != 0) {
598 __asm__
volatile("crc32b %w0, %w0, %w1" : "+r"(crc
) : "r"(val
));
601 /* Prepare to compute the CRC on full 64-bit words word[0..num-1]. */
602 word
= (z_word_t
const *)buf
;
606 /* Do three interleaved CRCs to realize the throughput of one crc32x
607 instruction per cycle. Each CRC is calculated on Z_BATCH words. The
608 three CRCs are combined into a single CRC after each set of batches. */
609 while (num
>= 3 * Z_BATCH
) {
612 for (i
= 0; i
< Z_BATCH
; i
++) {
614 val1
= word
[i
+ Z_BATCH
];
615 val2
= word
[i
+ 2 * Z_BATCH
];
616 __asm__
volatile("crc32x %w0, %w0, %x1" : "+r"(crc
) : "r"(val0
));
617 __asm__
volatile("crc32x %w0, %w0, %x1" : "+r"(crc1
) : "r"(val1
));
618 __asm__
volatile("crc32x %w0, %w0, %x1" : "+r"(crc2
) : "r"(val2
));
622 crc
= multmodp(Z_BATCH_ZEROS
, crc
) ^ crc1
;
623 crc
= multmodp(Z_BATCH_ZEROS
, crc
) ^ crc2
;
626 /* Do one last smaller batch with the remaining words, if there are enough
627 to pay for the combination of CRCs. */
629 if (last
>= Z_BATCH_MIN
) {
633 for (i
= 0; i
< last
; i
++) {
635 val1
= word
[i
+ last
];
636 val2
= word
[i
+ last2
];
637 __asm__
volatile("crc32x %w0, %w0, %x1" : "+r"(crc
) : "r"(val0
));
638 __asm__
volatile("crc32x %w0, %w0, %x1" : "+r"(crc1
) : "r"(val1
));
639 __asm__
volatile("crc32x %w0, %w0, %x1" : "+r"(crc2
) : "r"(val2
));
643 val
= x2nmodp(last
, 6);
644 crc
= multmodp(val
, crc
) ^ crc1
;
645 crc
= multmodp(val
, crc
) ^ crc2
;
648 /* Compute the CRC on any remaining words. */
649 for (i
= 0; i
< num
; i
++) {
651 __asm__
volatile("crc32x %w0, %w0, %x1" : "+r"(crc
) : "r"(val0
));
655 /* Complete the CRC on any remaining bytes. */
656 buf
= (const unsigned char FAR
*)word
;
660 __asm__
volatile("crc32b %w0, %w0, %w1" : "+r"(crc
) : "r"(val
));
663 /* Return the CRC, post-conditioned. */
664 return crc
^ 0xffffffff;
672 Return the CRC of the W bytes in the word_t data, taking the
673 least-significant byte of the word as the first byte of data, without any pre
674 or post conditioning. This is used to combine the CRCs of each braid.
676 local z_crc_t
crc_word(z_word_t data
) {
678 for (k
= 0; k
< W
; k
++)
679 data
= (data
>> 8) ^ crc_table
[data
& 0xff];
680 return (z_crc_t
)data
;
683 local z_word_t
crc_word_big(z_word_t data
) {
685 for (k
= 0; k
< W
; k
++)
687 crc_big_table
[(data
>> ((W
- 1) << 3)) & 0xff];
693 /* ========================================================================= */
694 unsigned long ZEXPORT
crc32_z(unsigned long crc
, const unsigned char FAR
*buf
,
696 /* Return initial CRC, if requested. */
697 if (buf
== Z_NULL
) return 0;
699 #ifdef DYNAMIC_CRC_TABLE
700 once(&made
, make_crc_table
);
701 #endif /* DYNAMIC_CRC_TABLE */
703 /* Pre-condition the CRC */
704 crc
= (~crc
) & 0xffffffff;
708 /* If provided enough bytes, do a braided CRC calculation. */
709 if (len
>= N
* W
+ W
- 1) {
711 z_word_t
const *words
;
715 /* Compute the CRC up to a z_word_t boundary. */
716 while (len
&& ((z_size_t
)buf
& (W
- 1)) != 0) {
718 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
721 /* Compute the CRC on as many N z_word_t blocks as are available. */
722 blks
= len
/ (N
* W
);
724 words
= (z_word_t
const *)buf
;
726 /* Do endian check at execution time instead of compile time, since ARM
727 processors can change the endianness at execution time. If the
728 compiler knows what the endianness will be, it can optimize out the
729 check and the unused branch. */
731 if (*(unsigned char *)&endian
) {
757 /* Initialize the CRC for each braid. */
776 Process the first blks-1 blocks, computing the CRCs on each braid
780 /* Load the word for each braid into registers. */
781 word0
= crc0
^ words
[0];
783 word1
= crc1
^ words
[1];
785 word2
= crc2
^ words
[2];
787 word3
= crc3
^ words
[3];
789 word4
= crc4
^ words
[4];
791 word5
= crc5
^ words
[5];
799 /* Compute and update the CRC for each word. The loop should
801 crc0
= crc_braid_table
[0][word0
& 0xff];
803 crc1
= crc_braid_table
[0][word1
& 0xff];
805 crc2
= crc_braid_table
[0][word2
& 0xff];
807 crc3
= crc_braid_table
[0][word3
& 0xff];
809 crc4
= crc_braid_table
[0][word4
& 0xff];
811 crc5
= crc_braid_table
[0][word5
& 0xff];
817 for (k
= 1; k
< W
; k
++) {
818 crc0
^= crc_braid_table
[k
][(word0
>> (k
<< 3)) & 0xff];
820 crc1
^= crc_braid_table
[k
][(word1
>> (k
<< 3)) & 0xff];
822 crc2
^= crc_braid_table
[k
][(word2
>> (k
<< 3)) & 0xff];
824 crc3
^= crc_braid_table
[k
][(word3
>> (k
<< 3)) & 0xff];
826 crc4
^= crc_braid_table
[k
][(word4
>> (k
<< 3)) & 0xff];
828 crc5
^= crc_braid_table
[k
][(word5
>> (k
<< 3)) & 0xff];
838 Process the last block, combining the CRCs of the N braids at the
841 crc
= crc_word(crc0
^ words
[0]);
843 crc
= crc_word(crc1
^ words
[1] ^ crc
);
845 crc
= crc_word(crc2
^ words
[2] ^ crc
);
847 crc
= crc_word(crc3
^ words
[3] ^ crc
);
849 crc
= crc_word(crc4
^ words
[4] ^ crc
);
851 crc
= crc_word(crc5
^ words
[5] ^ crc
);
862 z_word_t crc0
, word0
, comb
;
864 z_word_t crc1
, word1
;
866 z_word_t crc2
, word2
;
868 z_word_t crc3
, word3
;
870 z_word_t crc4
, word4
;
872 z_word_t crc5
, word5
;
879 /* Initialize the CRC for each braid. */
880 crc0
= byte_swap(crc
);
898 Process the first blks-1 blocks, computing the CRCs on each braid
902 /* Load the word for each braid into registers. */
903 word0
= crc0
^ words
[0];
905 word1
= crc1
^ words
[1];
907 word2
= crc2
^ words
[2];
909 word3
= crc3
^ words
[3];
911 word4
= crc4
^ words
[4];
913 word5
= crc5
^ words
[5];
921 /* Compute and update the CRC for each word. The loop should
923 crc0
= crc_braid_big_table
[0][word0
& 0xff];
925 crc1
= crc_braid_big_table
[0][word1
& 0xff];
927 crc2
= crc_braid_big_table
[0][word2
& 0xff];
929 crc3
= crc_braid_big_table
[0][word3
& 0xff];
931 crc4
= crc_braid_big_table
[0][word4
& 0xff];
933 crc5
= crc_braid_big_table
[0][word5
& 0xff];
939 for (k
= 1; k
< W
; k
++) {
940 crc0
^= crc_braid_big_table
[k
][(word0
>> (k
<< 3)) & 0xff];
942 crc1
^= crc_braid_big_table
[k
][(word1
>> (k
<< 3)) & 0xff];
944 crc2
^= crc_braid_big_table
[k
][(word2
>> (k
<< 3)) & 0xff];
946 crc3
^= crc_braid_big_table
[k
][(word3
>> (k
<< 3)) & 0xff];
948 crc4
^= crc_braid_big_table
[k
][(word4
>> (k
<< 3)) & 0xff];
950 crc5
^= crc_braid_big_table
[k
][(word5
>> (k
<< 3)) & 0xff];
960 Process the last block, combining the CRCs of the N braids at the
963 comb
= crc_word_big(crc0
^ words
[0]);
965 comb
= crc_word_big(crc1
^ words
[1] ^ comb
);
967 comb
= crc_word_big(crc2
^ words
[2] ^ comb
);
969 comb
= crc_word_big(crc3
^ words
[3] ^ comb
);
971 comb
= crc_word_big(crc4
^ words
[4] ^ comb
);
973 comb
= crc_word_big(crc5
^ words
[5] ^ comb
);
980 crc
= byte_swap(comb
);
984 Update the pointer to the remaining bytes to process.
986 buf
= (unsigned char const *)words
;
991 /* Complete the computation of the CRC on any remaining bytes. */
994 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
995 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
996 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
997 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
998 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
999 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
1000 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
1001 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
1005 crc
= (crc
>> 8) ^ crc_table
[(crc
^ *buf
++) & 0xff];
1008 /* Return the CRC, post-conditioned. */
1009 return crc
^ 0xffffffff;
1014 /* ========================================================================= */
1015 unsigned long ZEXPORT
crc32(unsigned long crc
, const unsigned char FAR
*buf
,
1017 return crc32_z(crc
, buf
, len
);
1020 /* ========================================================================= */
1021 uLong ZEXPORT
crc32_combine64(uLong crc1
, uLong crc2
, z_off64_t len2
) {
1022 #ifdef DYNAMIC_CRC_TABLE
1023 once(&made
, make_crc_table
);
1024 #endif /* DYNAMIC_CRC_TABLE */
1025 return multmodp(x2nmodp(len2
, 3), crc1
) ^ (crc2
& 0xffffffff);
1028 /* ========================================================================= */
1029 uLong ZEXPORT
crc32_combine(uLong crc1
, uLong crc2
, z_off_t len2
) {
1030 return crc32_combine64(crc1
, crc2
, (z_off64_t
)len2
);
1033 /* ========================================================================= */
1034 uLong ZEXPORT
crc32_combine_gen64(z_off64_t len2
) {
1035 #ifdef DYNAMIC_CRC_TABLE
1036 once(&made
, make_crc_table
);
1037 #endif /* DYNAMIC_CRC_TABLE */
1038 return x2nmodp(len2
, 3);
1041 /* ========================================================================= */
1042 uLong ZEXPORT
crc32_combine_gen(z_off_t len2
) {
1043 return crc32_combine_gen64((z_off64_t
)len2
);
1046 /* ========================================================================= */
1047 uLong ZEXPORT
crc32_combine_op(uLong crc1
, uLong crc2
, uLong op
) {
1048 return multmodp(op
, crc1
) ^ (crc2
& 0xffffffff);