Lines Matching +full:p +full:- +full:256
1 /* crc32.c -- compute the CRC-32 of a data stream
2 * Copyright (C) 1995-2022 Mark Adler
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.
14 protection on the static variables used to control the first-use generation
46 Lake i7, AMD Ryzen 7, ARM Cortex-A57, Sparc64-VII, PowerPC POWER9, and MIPS64
49 They were all tested with either gcc or clang, all using the -O3 optimization
75 # if Z_TESTW-1 != -1
109 self-respecting compiler will optimize this to a single machine byte-swap
136 * Table of powers of x for combining CRC-32s, filled in by make_crc_table()
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().
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,
156 z_crc_t m, p; in multmodp() local
159 p = 0; in multmodp()
162 p ^= b; in multmodp()
163 if ((a & (m - 1)) == 0) in multmodp()
169 return p; in multmodp()
173 Return x^(n * 2^k) modulo p(x). Requires that x2n_table[] has been
177 z_crc_t p; in x2nmodp() local
179 p = (z_crc_t)1 << 31; /* x^0 == 1 */ in x2nmodp()
182 p = multmodp(x2n_table[k & 31], p); in x2nmodp()
186 return p; in x2nmodp()
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);
237 if (!atomic_load(&state->done)) { in once()
238 if (atomic_flag_test_and_set(&state->begun)) in once()
239 while (!atomic_load(&state->done)) in once()
243 atomic_store(&state->done, 1); in once()
267 /* Run the provided init() function once. This is not thread-safe. */
269 if (!state->done) { in once()
270 if (test_and_set(&state->begun)) in once()
271 while (!state->done) in once()
275 state->done = 1; in once()
286 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
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
294 byte 0xb1 is the polynomial x^7+x^3+x^2+1), then the CRC is (q*x^32) mod p,
297 This calculation is done using the shift-register method of multiplying and
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
312 z_crc_t p; in make_crc_table() local
315 for (i = 0; i < 256; i++) { in make_crc_table()
316 p = i; in make_crc_table()
318 p = p & 1 ? (p >> 1) ^ POLY : p >> 1; in make_crc_table()
319 crc_table[i] = p; in make_crc_table()
321 crc_big_table[i] = byte_swap(p); in make_crc_table()
325 /* initialize the x^2^n mod p(x) table */ in make_crc_table()
326 p = (z_crc_t)1 << 30; /* x^1 */ in make_crc_table()
327 x2n_table[0] = p; in make_crc_table()
329 x2n_table[n] = p = multmodp(p, p); in make_crc_table()
332 /* initialize the braiding tables -- needs x2n_table[] */ in make_crc_table()
339 The crc32.h header file contains tables for both 32-bit and 64-bit in make_crc_table()
340 z_word_t's, and so requires a 64-bit type be available. In that case, in make_crc_table()
341 z_word_t must be defined to be 64-bits. This code then also generates in make_crc_table()
345 # error Need a 64-bit integer type in order to generate crc32.h. in make_crc_table()
349 z_crc_t ltl[8][256]; in make_crc_table()
350 z_word_t big[8][256]; in make_crc_table()
355 /* write out little-endian CRC table to crc32.h */ in make_crc_table()
357 "/* crc32.h -- tables for rapid CRC calculation\n" in make_crc_table()
362 write_table(out, crc_table, 256); in make_crc_table()
366 /* write out big-endian CRC table for 64-bit z_word_t to crc32.h */ in make_crc_table()
375 write_table64(out, crc_big_table, 256); in make_crc_table()
379 /* write out big-endian CRC table for 32-bit z_word_t to crc32.h */ in make_crc_table()
386 write_table32hi(out, crc_big_table, 256); in make_crc_table()
398 /* compute braid tables for this N and 64-bit word_t */ in make_crc_table()
401 /* write out braid tables for 64-bit z_word_t to crc32.h */ in make_crc_table()
406 "local const z_crc_t FAR crc_braid_table[][256] = {\n"); in make_crc_table()
409 write_table(out, ltl[k], 256); in make_crc_table()
415 "local const z_word_t FAR crc_braid_big_table[][256] = {\n"); in make_crc_table()
418 write_table64(out, big[k], 256); in make_crc_table()
424 /* compute braid tables for this N and 32-bit word_t */ in make_crc_table()
427 /* write out braid tables for 32-bit z_word_t to crc32.h */ in make_crc_table()
432 "local const z_crc_t FAR crc_braid_table[][256] = {\n"); in make_crc_table()
435 write_table(out, ltl[k], 256); in make_crc_table()
441 "local const z_word_t FAR crc_braid_big_table[][256] = {\n"); in make_crc_table()
444 write_table32hi(out, big[k], 256); in make_crc_table()
474 Write the 32-bit values in table[0..k-1] to out, five per line in
483 n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", ")); in write_table()
487 Write the high 32-bits of each value in table[0..k-1] to out, five per line
496 n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", ")); in write_table32hi()
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
512 n == k - 1 ? "" : (n % 3 == 2 ? ",\n" : ", ")); in write_table64()
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) { in braid() argument
530 z_crc_t i, p, q; in braid() local
532 p = x2nmodp((n * w + 3 - k) << 3, 0); in braid()
534 big[w - 1 - k][0] = 0; in braid()
535 for (i = 1; i < 256; i++) { in braid()
536 ltl[k][i] = q = multmodp(i << 24, p); in braid()
537 big[w - 1 - k][i] = byte_swap(q); in braid()
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
569 measurements on a Cortex-A57. Your mileage may vary.
591 /* Pre-condition the CRC */ in crc32_z()
596 len--; in crc32_z()
601 /* Prepare to compute the CRC on full 64-bit words word[0..num-1]. */ in crc32_z()
621 num -= 3 * Z_BATCH; in crc32_z()
642 num -= 3 * last; in crc32_z()
658 len--; in crc32_z()
663 /* Return the CRC, post-conditioned. */ in crc32_z()
673 least-significant byte of the word as the first byte of data, without any pre
687 crc_big_table[(data >> ((W - 1) << 3)) & 0xff]; in crc_word_big()
703 /* Pre-condition the CRC */ in crc32_z()
709 if (len >= N * W + W - 1) { in crc32_z()
716 while (len && ((z_size_t)buf & (W - 1)) != 0) { in crc32_z()
717 len--; in crc32_z()
723 len -= blks * N * W; in crc32_z()
776 Process the first blks-1 blocks, computing the CRCs on each braid in crc32_z()
779 while (--blks) { in crc32_z()
898 Process the first blks-1 blocks, computing the CRCs on each braid in crc32_z()
901 while (--blks) { in crc32_z()
993 len -= 8; in crc32_z()
1004 len--; in crc32_z()
1008 /* Return the CRC, post-conditioned. */ in crc32_z()