liberasurecode  1.2.0
Erasure Code API library
 All Data Structures Files Functions Variables Typedefs Macros
crc32.c
Go to the documentation of this file.
1 /*-
2  * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or
3  * code or tables extracted from it, as desired without restriction.
4  *
5  * First, the polynomial itself and its table of feedback terms. The
6  * polynomial is
7  * 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+X^0
8  *
9  * Note that we take it "backwards" and put the highest-order term in
10  * the lowest-order bit. The X^32 term is "implied"; the LSB is the
11  * X^31 term, etc. The X^0 term (usually shown as "+1") results in
12  * the MSB being 1
13  *
14  * Note that the usual hardware shift register implementation, which
15  * is what we're using (we're merely optimizing it by doing eight-bit
16  * chunks at a time) shifts bits into the lowest-order term. In our
17  * implementation, that means shifting towards the right. Why do we
18  * do it this way? Because the calculated CRC must be transmitted in
19  * order from highest-order term to lowest-order term. UARTs transmit
20  * characters in order from LSB to MSB. By storing the CRC this way
21  * we hand it to the UART in the order low-byte to high-byte; the UART
22  * sends each low-bit to hight-bit; and the result is transmission bit
23  * by bit from highest- to lowest-order term without requiring any bit
24  * shuffling on our part. Reception works similarly
25  *
26  * The feedback terms table consists of 256, 32-bit entries. Notes
27  *
28  * The table can be generated at runtime if desired; code to do so
29  * is shown later. It might not be obvious, but the feedback
30  * terms simply represent the results of eight shift/xor opera
31  * tions for all combinations of data and CRC register values
32  *
33  * The values must be right-shifted by eight bits by the "updcrc
34  * logic; the shift must be unsigned (bring in zeroes). On some
35  * hardware you could probably optimize the shift in assembler by
36  * using byte-swap instructions
37  * polynomial $edb88320
38  *
39  *
40  * CRC32 code derived from work by Gary S. Brown.
41  */
42 
43 #include <sys/param.h>
44 
45 #if defined(INTEL_SSE4)
46 #include <nmmintrin.h>
47 
48 int
49 crc32(int crc, const void *buf, size_t size)
50 {
51  unsigned long long *current = (unsigned long long*)buf;
52  unsigned char *current_char;
53 
54  crc = crc ^ ~0U;
55 
56  while(size >= 8) {
57  crc = _mm_crc32_u64(crc, *current++);
58  size -= 8;
59  }
60 
61  current_char = (unsigned char*)current;
62  while (size--) {
63  crc = _mm_crc32_u8(crc, *current_char++);
64  }
65  return crc ^ ~0U;
66 }
67 #else
68 
69 static int crc32_tab[] = {
70  0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
71  0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
72  0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
73  0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
74  0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
75  0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
76  0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
77  0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
78  0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
79  0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
80  0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
81  0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
82  0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
83  0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
84  0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
85  0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
86  0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
87  0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
88  0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
89  0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
90  0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
91  0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
92  0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
93  0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
94  0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
95  0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
96  0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
97  0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
98  0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
99  0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
100  0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
101  0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
102  0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
103  0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
104  0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
105  0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
106  0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
107  0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
108  0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
109  0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
110  0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
111  0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
112  0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
113 };
114 
115 // Use same polynomial as Intel's SSE4 instruction!
116 #define POLY_CRC_32 0x11EDC6F41
117 
118 int
119 crc32(int crc, const void *buf, size_t size)
120 {
121  const char *p;
122 
123  p = buf;
124  crc = crc ^ ~0U;
125 
126  while (size--)
127  crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
128 
129  return crc ^ ~0U;
130 }
131 #endif
132 
static int crc32_tab[]
Definition: crc32.c:69
int crc32(int crc, const void *buf, size_t size)
Definition: crc32.c:119