diff options
Diffstat (limited to 'crc32.c')
-rw-r--r-- | crc32.c | 244 |
1 files changed, 84 insertions, 160 deletions
@@ -103,19 +103,6 @@ | |||
103 | # define ARMCRC32 | 103 | # define ARMCRC32 |
104 | #endif | 104 | #endif |
105 | 105 | ||
106 | /* Local functions. */ | ||
107 | local z_crc_t multmodp OF((z_crc_t a, z_crc_t b)); | ||
108 | local z_crc_t x2nmodp OF((z_off64_t n, unsigned k)); | ||
109 | |||
110 | #if defined(W) && (!defined(ARMCRC32) || defined(DYNAMIC_CRC_TABLE)) | ||
111 | local z_word_t byte_swap OF((z_word_t word)); | ||
112 | #endif | ||
113 | |||
114 | #if defined(W) && !defined(ARMCRC32) | ||
115 | local z_crc_t crc_word OF((z_word_t data)); | ||
116 | local z_word_t crc_word_big OF((z_word_t data)); | ||
117 | #endif | ||
118 | |||
119 | #if defined(W) && (!defined(ARMCRC32) || defined(DYNAMIC_CRC_TABLE)) | 106 | #if defined(W) && (!defined(ARMCRC32) || defined(DYNAMIC_CRC_TABLE)) |
120 | /* | 107 | /* |
121 | Swap the bytes in a z_word_t to convert between little and big endian. Any | 108 | Swap the bytes in a z_word_t to convert between little and big endian. Any |
@@ -123,9 +110,7 @@ local z_crc_t x2nmodp OF((z_off64_t n, unsigned k)); | |||
123 | instruction, if one is available. This assumes that word_t is either 32 bits | 110 | instruction, if one is available. This assumes that word_t is either 32 bits |
124 | or 64 bits. | 111 | or 64 bits. |
125 | */ | 112 | */ |
126 | local z_word_t byte_swap(word) | 113 | local z_word_t byte_swap(z_word_t word) { |
127 | z_word_t word; | ||
128 | { | ||
129 | # if W == 8 | 114 | # if W == 8 |
130 | return | 115 | return |
131 | (word & 0xff00000000000000) >> 56 | | 116 | (word & 0xff00000000000000) >> 56 | |
@@ -146,24 +131,77 @@ local z_word_t byte_swap(word) | |||
146 | } | 131 | } |
147 | #endif | 132 | #endif |
148 | 133 | ||
134 | #ifdef DYNAMIC_CRC_TABLE | ||
135 | /* ========================================================================= | ||
136 | * Table of powers of x for combining CRC-32s, filled in by make_crc_table() | ||
137 | * below. | ||
138 | */ | ||
139 | local z_crc_t FAR x2n_table[32]; | ||
140 | #else | ||
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(). | ||
144 | */ | ||
145 | # include "crc32.h" | ||
146 | #endif | ||
147 | |||
149 | /* CRC polynomial. */ | 148 | /* CRC polynomial. */ |
150 | #define POLY 0xedb88320 /* p(x) reflected, with x^32 implied */ | 149 | #define POLY 0xedb88320 /* p(x) reflected, with x^32 implied */ |
151 | 150 | ||
152 | #ifdef DYNAMIC_CRC_TABLE | 151 | /* |
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. | ||
154 | */ | ||
155 | local z_crc_t multmodp(z_crc_t a, z_crc_t b) { | ||
156 | z_crc_t m, p; | ||
157 | |||
158 | m = (z_crc_t)1 << 31; | ||
159 | p = 0; | ||
160 | for (;;) { | ||
161 | if (a & m) { | ||
162 | p ^= b; | ||
163 | if ((a & (m - 1)) == 0) | ||
164 | break; | ||
165 | } | ||
166 | m >>= 1; | ||
167 | b = b & 1 ? (b >> 1) ^ POLY : b >> 1; | ||
168 | } | ||
169 | return p; | ||
170 | } | ||
153 | 171 | ||
172 | /* | ||
173 | Return x^(n * 2^k) modulo p(x). Requires that x2n_table[] has been | ||
174 | initialized. | ||
175 | */ | ||
176 | local z_crc_t x2nmodp(z_off64_t n, unsigned k) { | ||
177 | z_crc_t p; | ||
178 | |||
179 | p = (z_crc_t)1 << 31; /* x^0 == 1 */ | ||
180 | while (n) { | ||
181 | if (n & 1) | ||
182 | p = multmodp(x2n_table[k & 31], p); | ||
183 | n >>= 1; | ||
184 | k++; | ||
185 | } | ||
186 | return p; | ||
187 | } | ||
188 | |||
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. | ||
193 | */ | ||
154 | local z_crc_t FAR crc_table[256]; | 194 | local z_crc_t FAR crc_table[256]; |
155 | local z_crc_t FAR x2n_table[32]; | ||
156 | local void make_crc_table OF((void)); | ||
157 | #ifdef W | 195 | #ifdef W |
158 | local z_word_t FAR crc_big_table[256]; | 196 | local z_word_t FAR crc_big_table[256]; |
159 | local z_crc_t FAR crc_braid_table[W][256]; | 197 | local z_crc_t FAR crc_braid_table[W][256]; |
160 | local z_word_t FAR crc_braid_big_table[W][256]; | 198 | local z_word_t FAR crc_braid_big_table[W][256]; |
161 | local void braid OF((z_crc_t [][256], z_word_t [][256], int, int)); | 199 | local void braid(z_crc_t [][256], z_word_t [][256], int, int); |
162 | #endif | 200 | #endif |
163 | #ifdef MAKECRCH | 201 | #ifdef MAKECRCH |
164 | local void write_table OF((FILE *, const z_crc_t FAR *, int)); | 202 | local void write_table(FILE *, const z_crc_t FAR *, int); |
165 | local void write_table32hi OF((FILE *, const z_word_t FAR *, int)); | 203 | local void write_table32hi(FILE *, const z_word_t FAR *, int); |
166 | local void write_table64 OF((FILE *, const z_word_t FAR *, int)); | 204 | local void write_table64(FILE *, const z_word_t FAR *, int); |
167 | #endif /* MAKECRCH */ | 205 | #endif /* MAKECRCH */ |
168 | 206 | ||
169 | /* | 207 | /* |
@@ -176,7 +214,6 @@ local void make_crc_table OF((void)); | |||
176 | 214 | ||
177 | /* Definition of once functionality. */ | 215 | /* Definition of once functionality. */ |
178 | typedef struct once_s once_t; | 216 | typedef struct once_s once_t; |
179 | local void once OF((once_t *, void (*)(void))); | ||
180 | 217 | ||
181 | /* Check for the availability of atomics. */ | 218 | /* Check for the availability of atomics. */ |
182 | #if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \ | 219 | #if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \ |
@@ -196,10 +233,7 @@ struct once_s { | |||
196 | invoke once() at the same time. The state must be a once_t initialized with | 233 | invoke once() at the same time. The state must be a once_t initialized with |
197 | ONCE_INIT. | 234 | ONCE_INIT. |
198 | */ | 235 | */ |
199 | local void once(state, init) | 236 | local void once(once_t *state, void (*init)(void)) { |
200 | once_t *state; | ||
201 | void (*init)(void); | ||
202 | { | ||
203 | if (!atomic_load(&state->done)) { | 237 | if (!atomic_load(&state->done)) { |
204 | if (atomic_flag_test_and_set(&state->begun)) | 238 | if (atomic_flag_test_and_set(&state->begun)) |
205 | while (!atomic_load(&state->done)) | 239 | while (!atomic_load(&state->done)) |
@@ -222,10 +256,7 @@ struct once_s { | |||
222 | 256 | ||
223 | /* Test and set. Alas, not atomic, but tries to minimize the period of | 257 | /* Test and set. Alas, not atomic, but tries to minimize the period of |
224 | vulnerability. */ | 258 | vulnerability. */ |
225 | local int test_and_set OF((int volatile *)); | 259 | local int test_and_set(int volatile *flag) { |
226 | local int test_and_set(flag) | ||
227 | int volatile *flag; | ||
228 | { | ||
229 | int was; | 260 | int was; |
230 | 261 | ||
231 | was = *flag; | 262 | was = *flag; |
@@ -234,10 +265,7 @@ local int test_and_set(flag) | |||
234 | } | 265 | } |
235 | 266 | ||
236 | /* Run the provided init() function once. This is not thread-safe. */ | 267 | /* Run the provided init() function once. This is not thread-safe. */ |
237 | local void once(state, init) | 268 | local void once(once_t *state, void (*init)(void)) { |
238 | once_t *state; | ||
239 | void (*init)(void); | ||
240 | { | ||
241 | if (!state->done) { | 269 | if (!state->done) { |
242 | if (test_and_set(&state->begun)) | 270 | if (test_and_set(&state->begun)) |
243 | while (!state->done) | 271 | while (!state->done) |
@@ -279,8 +307,7 @@ local once_t made = ONCE_INIT; | |||
279 | combinations of CRC register values and incoming bytes. | 307 | combinations of CRC register values and incoming bytes. |
280 | */ | 308 | */ |
281 | 309 | ||
282 | local void make_crc_table() | 310 | local void make_crc_table(void) { |
283 | { | ||
284 | unsigned i, j, n; | 311 | unsigned i, j, n; |
285 | z_crc_t p; | 312 | z_crc_t p; |
286 | 313 | ||
@@ -447,11 +474,7 @@ local void make_crc_table() | |||
447 | Write the 32-bit values in table[0..k-1] to out, five per line in | 474 | Write the 32-bit values in table[0..k-1] to out, five per line in |
448 | hexadecimal separated by commas. | 475 | hexadecimal separated by commas. |
449 | */ | 476 | */ |
450 | local void write_table(out, table, k) | 477 | local void write_table(FILE *out, const z_crc_t FAR *table, int k) { |
451 | FILE *out; | ||
452 | const z_crc_t FAR *table; | ||
453 | int k; | ||
454 | { | ||
455 | int n; | 478 | int n; |
456 | 479 | ||
457 | for (n = 0; n < k; n++) | 480 | for (n = 0; n < k; n++) |
@@ -464,11 +487,7 @@ local void write_table(out, table, k) | |||
464 | Write the high 32-bits of each value in table[0..k-1] to out, five per line | 487 | Write the high 32-bits of each value in table[0..k-1] to out, five per line |
465 | in hexadecimal separated by commas. | 488 | in hexadecimal separated by commas. |
466 | */ | 489 | */ |
467 | local void write_table32hi(out, table, k) | 490 | local void write_table32hi(FILE *out, const z_word_t FAR *table, int k) { |
468 | FILE *out; | ||
469 | const z_word_t FAR *table; | ||
470 | int k; | ||
471 | { | ||
472 | int n; | 491 | int n; |
473 | 492 | ||
474 | for (n = 0; n < k; n++) | 493 | for (n = 0; n < k; n++) |
@@ -484,11 +503,7 @@ int k; | |||
484 | bits. If not, then the type cast and format string can be adjusted | 503 | bits. If not, then the type cast and format string can be adjusted |
485 | accordingly. | 504 | accordingly. |
486 | */ | 505 | */ |
487 | local void write_table64(out, table, k) | 506 | local void write_table64(FILE *out, const z_word_t FAR *table, int k) { |
488 | FILE *out; | ||
489 | const z_word_t FAR *table; | ||
490 | int k; | ||
491 | { | ||
492 | int n; | 507 | int n; |
493 | 508 | ||
494 | for (n = 0; n < k; n++) | 509 | for (n = 0; n < k; n++) |
@@ -498,8 +513,7 @@ local void write_table64(out, table, k) | |||
498 | } | 513 | } |
499 | 514 | ||
500 | /* Actually do the deed. */ | 515 | /* Actually do the deed. */ |
501 | int main() | 516 | int main(void) { |
502 | { | ||
503 | make_crc_table(); | 517 | make_crc_table(); |
504 | return 0; | 518 | return 0; |
505 | } | 519 | } |
@@ -511,12 +525,7 @@ int main() | |||
511 | Generate the little and big-endian braid tables for the given n and z_word_t | 525 | Generate the little and big-endian braid tables for the given n and z_word_t |
512 | size w. Each array must have room for w blocks of 256 elements. | 526 | size w. Each array must have room for w blocks of 256 elements. |
513 | */ | 527 | */ |
514 | local void braid(ltl, big, n, w) | 528 | local void braid(z_crc_t ltl[][256], z_word_t big[][256], int n, int w) { |
515 | z_crc_t ltl[][256]; | ||
516 | z_word_t big[][256]; | ||
517 | int n; | ||
518 | int w; | ||
519 | { | ||
520 | int k; | 529 | int k; |
521 | z_crc_t i, p, q; | 530 | z_crc_t i, p, q; |
522 | for (k = 0; k < w; k++) { | 531 | for (k = 0; k < w; k++) { |
@@ -531,69 +540,13 @@ local void braid(ltl, big, n, w) | |||
531 | } | 540 | } |
532 | #endif | 541 | #endif |
533 | 542 | ||
534 | #else /* !DYNAMIC_CRC_TABLE */ | ||
535 | /* ======================================================================== | ||
536 | * Tables for byte-wise and braided CRC-32 calculations, and a table of powers | ||
537 | * of x for combining CRC-32s, all made by make_crc_table(). | ||
538 | */ | ||
539 | #include "crc32.h" | ||
540 | #endif /* DYNAMIC_CRC_TABLE */ | 543 | #endif /* DYNAMIC_CRC_TABLE */ |
541 | 544 | ||
542 | /* ======================================================================== | ||
543 | * Routines used for CRC calculation. Some are also required for the table | ||
544 | * generation above. | ||
545 | */ | ||
546 | |||
547 | /* | ||
548 | Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial, | ||
549 | reflected. For speed, this requires that a not be zero. | ||
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 that x2n_table[] has been | ||
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 == 1 */ | ||
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 | /* ========================================================================= | 545 | /* ========================================================================= |
592 | * This function can be used by asm versions of crc32(), and to force the | 546 | * This function can be used by asm versions of crc32(), and to force the |
593 | * generation of the CRC tables in a threaded application. | 547 | * generation of the CRC tables in a threaded application. |
594 | */ | 548 | */ |
595 | const z_crc_t FAR * ZEXPORT get_crc_table() | 549 | const z_crc_t FAR * ZEXPORT get_crc_table(void) { |
596 | { | ||
597 | #ifdef DYNAMIC_CRC_TABLE | 550 | #ifdef DYNAMIC_CRC_TABLE |
598 | once(&made, make_crc_table); | 551 | once(&made, make_crc_table); |
599 | #endif /* DYNAMIC_CRC_TABLE */ | 552 | #endif /* DYNAMIC_CRC_TABLE */ |
@@ -619,11 +572,8 @@ const z_crc_t FAR * ZEXPORT get_crc_table() | |||
619 | #define Z_BATCH_ZEROS 0xa10d3d0c /* computed from Z_BATCH = 3990 */ | 572 | #define Z_BATCH_ZEROS 0xa10d3d0c /* computed from Z_BATCH = 3990 */ |
620 | #define Z_BATCH_MIN 800 /* fewest words in a final batch */ | 573 | #define Z_BATCH_MIN 800 /* fewest words in a final batch */ |
621 | 574 | ||
622 | unsigned long ZEXPORT crc32_z(crc, buf, len) | 575 | unsigned long ZEXPORT crc32_z(unsigned long crc, const unsigned char FAR *buf, |
623 | unsigned long crc; | 576 | z_size_t len) { |
624 | const unsigned char FAR *buf; | ||
625 | z_size_t len; | ||
626 | { | ||
627 | z_crc_t val; | 577 | z_crc_t val; |
628 | z_word_t crc1, crc2; | 578 | z_word_t crc1, crc2; |
629 | const z_word_t *word; | 579 | const z_word_t *word; |
@@ -723,18 +673,14 @@ unsigned long ZEXPORT crc32_z(crc, buf, len) | |||
723 | least-significant byte of the word as the first byte of data, without any pre | 673 | least-significant byte of the word as the first byte of data, without any pre |
724 | or post conditioning. This is used to combine the CRCs of each braid. | 674 | or post conditioning. This is used to combine the CRCs of each braid. |
725 | */ | 675 | */ |
726 | local z_crc_t crc_word(data) | 676 | local z_crc_t crc_word(z_word_t data) { |
727 | z_word_t data; | ||
728 | { | ||
729 | int k; | 677 | int k; |
730 | for (k = 0; k < W; k++) | 678 | for (k = 0; k < W; k++) |
731 | data = (data >> 8) ^ crc_table[data & 0xff]; | 679 | data = (data >> 8) ^ crc_table[data & 0xff]; |
732 | return (z_crc_t)data; | 680 | return (z_crc_t)data; |
733 | } | 681 | } |
734 | 682 | ||
735 | local z_word_t crc_word_big(data) | 683 | local z_word_t crc_word_big(z_word_t data) { |
736 | z_word_t data; | ||
737 | { | ||
738 | int k; | 684 | int k; |
739 | for (k = 0; k < W; k++) | 685 | for (k = 0; k < W; k++) |
740 | data = (data << 8) ^ | 686 | data = (data << 8) ^ |
@@ -745,11 +691,8 @@ local z_word_t crc_word_big(data) | |||
745 | #endif | 691 | #endif |
746 | 692 | ||
747 | /* ========================================================================= */ | 693 | /* ========================================================================= */ |
748 | unsigned long ZEXPORT crc32_z(crc, buf, len) | 694 | unsigned long ZEXPORT crc32_z(unsigned long crc, const unsigned char FAR *buf, |
749 | unsigned long crc; | 695 | z_size_t len) { |
750 | const unsigned char FAR *buf; | ||
751 | z_size_t len; | ||
752 | { | ||
753 | /* Return initial CRC, if requested. */ | 696 | /* Return initial CRC, if requested. */ |
754 | if (buf == Z_NULL) return 0; | 697 | if (buf == Z_NULL) return 0; |
755 | 698 | ||
@@ -1069,20 +1012,13 @@ unsigned long ZEXPORT crc32_z(crc, buf, len) | |||
1069 | #endif | 1012 | #endif |
1070 | 1013 | ||
1071 | /* ========================================================================= */ | 1014 | /* ========================================================================= */ |
1072 | unsigned long ZEXPORT crc32(crc, buf, len) | 1015 | unsigned long ZEXPORT crc32(unsigned long crc, const unsigned char FAR *buf, |
1073 | unsigned long crc; | 1016 | uInt len) { |
1074 | const unsigned char FAR *buf; | ||
1075 | uInt len; | ||
1076 | { | ||
1077 | return crc32_z(crc, buf, len); | 1017 | return crc32_z(crc, buf, len); |
1078 | } | 1018 | } |
1079 | 1019 | ||
1080 | /* ========================================================================= */ | 1020 | /* ========================================================================= */ |
1081 | uLong ZEXPORT crc32_combine64(crc1, crc2, len2) | 1021 | uLong ZEXPORT crc32_combine64(uLong crc1, uLong crc2, z_off64_t len2) { |
1082 | uLong crc1; | ||
1083 | uLong crc2; | ||
1084 | z_off64_t len2; | ||
1085 | { | ||
1086 | #ifdef DYNAMIC_CRC_TABLE | 1022 | #ifdef DYNAMIC_CRC_TABLE |
1087 | once(&made, make_crc_table); | 1023 | once(&made, make_crc_table); |
1088 | #endif /* DYNAMIC_CRC_TABLE */ | 1024 | #endif /* DYNAMIC_CRC_TABLE */ |
@@ -1090,18 +1026,12 @@ uLong ZEXPORT crc32_combine64(crc1, crc2, len2) | |||
1090 | } | 1026 | } |
1091 | 1027 | ||
1092 | /* ========================================================================= */ | 1028 | /* ========================================================================= */ |
1093 | uLong ZEXPORT crc32_combine(crc1, crc2, len2) | 1029 | uLong ZEXPORT crc32_combine(uLong crc1, uLong crc2, z_off_t len2) { |
1094 | uLong crc1; | ||
1095 | uLong crc2; | ||
1096 | z_off_t len2; | ||
1097 | { | ||
1098 | return crc32_combine64(crc1, crc2, (z_off64_t)len2); | 1030 | return crc32_combine64(crc1, crc2, (z_off64_t)len2); |
1099 | } | 1031 | } |
1100 | 1032 | ||
1101 | /* ========================================================================= */ | 1033 | /* ========================================================================= */ |
1102 | uLong ZEXPORT crc32_combine_gen64(len2) | 1034 | uLong ZEXPORT crc32_combine_gen64(z_off64_t len2) { |
1103 | z_off64_t len2; | ||
1104 | { | ||
1105 | #ifdef DYNAMIC_CRC_TABLE | 1035 | #ifdef DYNAMIC_CRC_TABLE |
1106 | once(&made, make_crc_table); | 1036 | once(&made, make_crc_table); |
1107 | #endif /* DYNAMIC_CRC_TABLE */ | 1037 | #endif /* DYNAMIC_CRC_TABLE */ |
@@ -1109,17 +1039,11 @@ uLong ZEXPORT crc32_combine_gen64(len2) | |||
1109 | } | 1039 | } |
1110 | 1040 | ||
1111 | /* ========================================================================= */ | 1041 | /* ========================================================================= */ |
1112 | uLong ZEXPORT crc32_combine_gen(len2) | 1042 | uLong ZEXPORT crc32_combine_gen(z_off_t len2) { |
1113 | z_off_t len2; | ||
1114 | { | ||
1115 | return crc32_combine_gen64((z_off64_t)len2); | 1043 | return crc32_combine_gen64((z_off64_t)len2); |
1116 | } | 1044 | } |
1117 | 1045 | ||
1118 | /* ========================================================================= */ | 1046 | /* ========================================================================= */ |
1119 | uLong ZEXPORT crc32_combine_op(crc1, crc2, op) | 1047 | uLong ZEXPORT crc32_combine_op(uLong crc1, uLong crc2, uLong op) { |
1120 | uLong crc1; | ||
1121 | uLong crc2; | ||
1122 | uLong op; | ||
1123 | { | ||
1124 | return multmodp(op, crc1) ^ (crc2 & 0xffffffff); | 1048 | return multmodp(op, crc1) ^ (crc2 & 0xffffffff); |
1125 | } | 1049 | } |