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
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
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().
163             if ((a & (m - 1)) == 0)  in multmodp()
191  * Build the tables for byte-wise and braided CRC-32 calculations, and a table
192  * of powers of x for combining CRC-32s.
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
297   This calculation is done using the shift-register method of multiplying and
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()
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()
366         /* write out big-endian CRC table for 64-bit z_word_t to crc32.h */  in make_crc_table()
379         /* write out big-endian CRC table for 32-bit z_word_t to crc32.h */  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()
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()
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
532         p = x2nmodp((n * w + 3 - k) << 3, 0);  in braid()
534         big[w - 1 - k][0] = 0;  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()