25 # ifndef DYNAMIC_CRC_TABLE
26 # define DYNAMIC_CRC_TABLE
60 # error N must be in 1..6
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;
102 #if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32) && W == 8
106 #if defined(W) && (!defined(ARMCRC32) || defined(DYNAMIC_CRC_TABLE))
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
149 #define POLY 0xedb88320
163 if ((a & (m - 1)) == 0)
167 b = b & 1 ? (b >> 1) ^
POLY : b >> 1;
189 #ifdef DYNAMIC_CRC_TABLE
196 local z_word_t
FAR crc_big_table[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);
203 local void write_table32hi(FILE *,
const z_word_t
FAR *,
int);
204 local void write_table64(FILE *,
const z_word_t
FAR *,
int);
216 typedef struct once_s once_t;
219 #if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \
220 !defined(__STDC_NO_ATOMICS__)
222 #include <stdatomic.h>
229 #define ONCE_INIT {ATOMIC_FLAG_INIT, 0}
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);
255 #define ONCE_INIT {0, 0}
259 local int test_and_set(
int volatile *flag) {
268 local void once(once_t *state,
void (*init)(
void)) {
270 if (test_and_set(&state->begun))
283 local once_t made = ONCE_INIT;
310 local void make_crc_table(
void) {
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);
328 for (n = 1; n < 32; n++)
333 braid(crc_braid_table, crc_braid_big_table,
N,
W);
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;
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"
373 "local const z_word_t FAR crc_big_table[] = {\n"
375 write_table64(out, crc_big_table, 256);
382 "#else /* W == 4 */\n"
384 "local const z_word_t FAR crc_big_table[] = {\n"
386 write_table32hi(out, crc_big_table, 256);
393 for (n = 1; n <= 6; n++) {
399 braid(ltl, big, n, 8);
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" :
"");
425 braid(ltl, big, n, 4);
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" :
"");
461 "local const z_crc_t FAR x2n_table[] = {\n"
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" :
", "));
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" :
", "));
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" :
", "));
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);
550 #ifdef DYNAMIC_CRC_TABLE
551 once(&made, make_crc_table);
572 #define Z_BATCH_ZEROS 0xa10d3d0c
573 #define Z_BATCH_MIN 800
579 const z_word_t *word;
580 z_word_t val0, val1, val2;
585 if (buf ==
Z_NULL)
return 0;
587 #ifdef DYNAMIC_CRC_TABLE
588 once(&made, make_crc_table);
592 crc = (~crc) & 0xffffffff;
595 while (len && ((
z_size_t)buf & 7) != 0) {
598 __asm__
volatile(
"crc32b %w0, %w0, %w1" :
"+r"(crc) :
"r"(val));
602 word = (z_word_t
const *)buf;
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;
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));
649 for (i = 0; i < num; i++) {
651 __asm__
volatile(
"crc32x %w0, %w0, %x1" :
"+r"(crc) :
"r"(val0));
656 buf = (
const unsigned char FAR *)word;
660 __asm__
volatile(
"crc32b %w0, %w0, %w1" :
"+r"(crc) :
"r"(val));
664 return crc ^ 0xffffffff;
678 for (k = 0; k <
W; k++)
679 data = (data >> 8) ^
crc_table[data & 0xff];
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];
697 if (buf ==
Z_NULL)
return 0;
699 #ifdef DYNAMIC_CRC_TABLE
700 once(&made, make_crc_table);
704 crc = (~crc) & 0xffffffff;
709 if (len >=
N * W + W - 1) {
711 z_word_t
const *words;
716 while (len && ((
z_size_t)buf & (W - 1)) != 0) {
718 crc = (crc >> 8) ^
crc_table[(crc ^ *buf++) & 0xff];
722 blks = len / (
N *
W);
724 words = (z_word_t
const *)buf;
731 if (*(
unsigned char *)&endian) {
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];
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];
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;
880 crc0 = byte_swap(crc);
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];
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];
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);
986 buf = (
unsigned char const *)words;
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];
1009 return crc ^ 0xffffffff;
1017 return crc32_z(crc, buf, len);
1022 #ifdef DYNAMIC_CRC_TABLE
1023 once(&made, make_crc_table);
1035 #ifdef DYNAMIC_CRC_TABLE
1036 once(&made, make_crc_table);
1048 return multmodp(op, crc1) ^ (crc2 & 0xffffffff);
local const z_crc_t FAR crc_table[]
local const z_crc_t FAR x2n_table[]
uLong ZEXPORT crc32_combine_gen64(z_off64_t len2)
uLong ZEXPORT crc32_combine_gen(z_off_t len2)
unsigned long ZEXPORT crc32_z(unsigned long crc, const unsigned char FAR *buf, z_size_t len)
uLong ZEXPORT crc32_combine(uLong crc1, uLong crc2, z_off_t len2)
local z_crc_t multmodp(z_crc_t a, z_crc_t b)
unsigned long ZEXPORT crc32(unsigned long crc, const unsigned char FAR *buf, uInt len)
const z_crc_t FAR *ZEXPORT get_crc_table(void)
int main(int argc, char *argv[])
uLong ZEXPORT crc32_combine64(uLong crc1, uLong crc2, z_off64_t len2)
uLong ZEXPORT crc32_combine_op(uLong crc1, uLong crc2, uLong op)
local z_crc_t x2nmodp(z_off64_t n, unsigned k)