Line data Source code
1 : // CRC32C code taken from
2 : // http://stackoverflow.com/questions/17645167/implementing-sse-4-2s-crc32c-in-software/17646775#17646775
3 : // on 29 July 2015
4 : //
5 : // See also:
6 : // https://tools.ietf.org/html/rfc3309
7 : // https://tools.ietf.org/html/rfc3720#appendix-B.4
8 : // and
9 : // http://stackoverflow.com/questions/20963944/test-vectors-for-crc32c
10 : //
11 :
12 : #include "crc32c.h"
13 :
14 : #if defined(__SSE__) && defined(__x86_64__)
15 : #define HAVE_HWCRC32C 1
16 : #endif
17 :
18 : #ifdef __ARM_FEATURE_CRC32
19 : #include <arm_acle.h>
20 : #endif
21 :
22 : /* crc32c.c -- compute CRC-32C using the Intel crc32 instruction
23 : * Copyright (C) 2013 Mark Adler
24 : * Version 1.1 1 Aug 2013 Mark Adler
25 : */
26 :
27 : /*
28 : This software is provided 'as-is', without any express or implied
29 : warranty. In no event will the author be held liable for any damages
30 : arising from the use of this software.
31 :
32 : Permission is granted to anyone to use this software for any purpose,
33 : including commercial applications, and to alter it and redistribute it
34 : freely, subject to the following restrictions:
35 :
36 : 1. The origin of this software must not be misrepresented; you must not
37 : claim that you wrote the original software. If you use this software
38 : in a product, an acknowledgment in the product documentation would be
39 : appreciated but is not required.
40 : 2. Altered source versions must be plainly marked as such, and must not be
41 : misrepresented as being the original software.
42 : 3. This notice may not be removed or altered from any source distribution.
43 :
44 : Mark Adler
45 : madler@alumni.caltech.edu
46 : */
47 :
48 : /* Use hardware CRC instruction on Intel SSE 4.2 processors. This computes a
49 : CRC-32C, *not* the CRC-32 used by Ethernet and zip, gzip, etc. A software
50 : version is provided as a fall-back, as well as for speed comparisons. */
51 :
52 : /* Version history:
53 : 1.0 10 Feb 2013 First version
54 : 1.1 1 Aug 2013 Correct comments on why three crc instructions in parallel
55 : */
56 :
57 : #include <stdio.h>
58 : #include <stdlib.h>
59 : #include <stdint.h>
60 : #include <unistd.h>
61 : #include <pthread.h>
62 :
63 : /* CRC-32C (iSCSI) polynomial in reversed bit order. */
64 : #define POLY 0x82f63b78
65 :
66 : /* Table for a quadword-at-a-time software crc. */
67 : static pthread_once_t crc32c_once_sw = PTHREAD_ONCE_INIT;
68 : static uint32_t crc32c_table[8][256];
69 :
70 : /* Construct table for software CRC-32C calculation. */
71 0 : static void crc32c_init_sw(void)
72 : {
73 : uint32_t n, crc, k;
74 :
75 0 : for (n = 0; n < 256; n++) {
76 0 : crc = n;
77 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
78 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
79 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
80 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
81 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
82 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
83 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
84 0 : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
85 0 : crc32c_table[0][n] = crc;
86 : }
87 0 : for (n = 0; n < 256; n++) {
88 0 : crc = crc32c_table[0][n];
89 0 : for (k = 1; k < 8; k++) {
90 0 : crc = crc32c_table[0][crc & 0xff] ^ (crc >> 8);
91 0 : crc32c_table[k][n] = crc;
92 : }
93 : }
94 0 : }
95 :
96 : /* Table-driven software version as a fall-back. This is about 15 times slower
97 : than using the hardware instructions. This assumes little-endian integers,
98 : as is the case on Intel processors that the assembler code here is for. */
99 0 : uint32_t crc32c_sw(uint32_t crci, const void *buf, size_t len)
100 : {
101 0 : const unsigned char *next = (const unsigned char*)buf;
102 : uint64_t crc;
103 :
104 0 : pthread_once(&crc32c_once_sw, crc32c_init_sw);
105 0 : crc = crci ^ 0xffffffff;
106 0 : while (len && ((uintptr_t)next & 7) != 0) {
107 0 : crc = crc32c_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
108 0 : len--;
109 : }
110 0 : while (len >= 8) {
111 0 : crc ^= *(uint64_t *)next;
112 0 : crc = crc32c_table[7][crc & 0xff] ^
113 0 : crc32c_table[6][(crc >> 8) & 0xff] ^
114 0 : crc32c_table[5][(crc >> 16) & 0xff] ^
115 0 : crc32c_table[4][(crc >> 24) & 0xff] ^
116 0 : crc32c_table[3][(crc >> 32) & 0xff] ^
117 0 : crc32c_table[2][(crc >> 40) & 0xff] ^
118 0 : crc32c_table[1][(crc >> 48) & 0xff] ^
119 0 : crc32c_table[0][crc >> 56];
120 0 : next += 8;
121 0 : len -= 8;
122 : }
123 0 : while (len) {
124 0 : crc = crc32c_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
125 0 : len--;
126 : }
127 0 : return (uint32_t)crc ^ 0xffffffff;
128 : }
129 :
130 : /* Multiply a matrix times a vector over the Galois field of two elements,
131 : GF(2). Each element is a bit in an unsigned integer. mat must have at
132 : least as many entries as the power of two for most significant one bit in
133 : vec. */
134 0 : static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec)
135 : {
136 : uint32_t sum;
137 :
138 0 : sum = 0;
139 0 : while (vec) {
140 0 : if (vec & 1)
141 0 : sum ^= *mat;
142 0 : vec >>= 1;
143 0 : mat++;
144 : }
145 0 : return sum;
146 : }
147 :
148 : /* Multiply a matrix by itself over GF(2). Both mat and square must have 32
149 : rows. */
150 0 : static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat)
151 : {
152 : int n;
153 :
154 0 : for (n = 0; n < 32; n++)
155 0 : square[n] = gf2_matrix_times(mat, mat[n]);
156 0 : }
157 :
158 : #ifdef HAVE_HWCRC32C
159 :
160 : /* Construct an operator to apply len zeros to a crc. len must be a power of
161 : two. If len is not a power of two, then the result is the same as for the
162 : largest power of two less than len. The result for len == 0 is the same as
163 : for len == 1. A version of this routine could be easily written for any
164 : len, but that is not needed for this application. */
165 0 : static void crc32c_zeros_op(uint32_t *even, size_t len)
166 : {
167 : int n;
168 : uint32_t row;
169 : uint32_t odd[32]; /* odd-power-of-two zeros operator */
170 :
171 : /* put operator for one zero bit in odd */
172 0 : odd[0] = POLY; /* CRC-32C polynomial */
173 0 : row = 1;
174 0 : for (n = 1; n < 32; n++) {
175 0 : odd[n] = row;
176 0 : row <<= 1;
177 : }
178 :
179 : /* put operator for two zero bits in even */
180 0 : gf2_matrix_square(even, odd);
181 :
182 : /* put operator for four zero bits in odd */
183 0 : gf2_matrix_square(odd, even);
184 :
185 : /* first square will put the operator for one zero byte (eight zero bits),
186 : in even -- next square puts operator for two zero bytes in odd, and so
187 : on, until len has been rotated down to zero */
188 : do {
189 0 : gf2_matrix_square(even, odd);
190 0 : len >>= 1;
191 0 : if (len == 0)
192 0 : return;
193 0 : gf2_matrix_square(odd, even);
194 0 : len >>= 1;
195 0 : } while (len);
196 :
197 : /* answer ended up in odd -- copy to even */
198 0 : for (n = 0; n < 32; n++)
199 0 : even[n] = odd[n];
200 : }
201 :
202 : /* Take a length and build four lookup tables for applying the zeros operator
203 : for that length, byte-by-byte on the operand. */
204 0 : static void crc32c_zeros(uint32_t zeros[][256], size_t len)
205 : {
206 : uint32_t n;
207 : uint32_t op[32];
208 :
209 0 : crc32c_zeros_op(op, len);
210 0 : for (n = 0; n < 256; n++) {
211 0 : zeros[0][n] = gf2_matrix_times(op, n);
212 0 : zeros[1][n] = gf2_matrix_times(op, n << 8);
213 0 : zeros[2][n] = gf2_matrix_times(op, n << 16);
214 0 : zeros[3][n] = gf2_matrix_times(op, n << 24);
215 : }
216 0 : }
217 :
218 : #endif
219 :
220 : /* Apply the zeros operator table to crc. */
221 0 : static inline uint32_t crc32c_shift(uint32_t zeros[][256], uint32_t crc)
222 : {
223 0 : return zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^
224 0 : zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24];
225 : }
226 :
227 : /* Block sizes for three-way parallel crc computation. LONG and SHORT must
228 : both be powers of two. The associated string constants must be set
229 : accordingly, for use in constructing the assembler instructions. */
230 : #define LONG 8192
231 : #define LONGx1 "8192"
232 : #define LONGx2 "16384"
233 : #define SHORT 256
234 : #define SHORTx1 "256"
235 : #define SHORTx2 "512"
236 :
237 : #ifdef HAVE_HWCRC32C
238 :
239 : /* Tables for hardware crc that shift a crc by LONG and SHORT zeros. */
240 : static pthread_once_t crc32c_once_hw = PTHREAD_ONCE_INIT;
241 : static uint32_t crc32c_long[4][256];
242 : static uint32_t crc32c_short[4][256];
243 :
244 : /* Initialize tables for shifting crcs. */
245 0 : static void crc32c_init_hw(void)
246 : {
247 0 : crc32c_zeros(crc32c_long, LONG);
248 0 : crc32c_zeros(crc32c_short, SHORT);
249 0 : }
250 :
251 : /* Compute CRC-32C using the Intel hardware instruction. */
252 0 : uint32_t crc32c_hw(uint32_t crc, const void *buf, size_t len)
253 : {
254 0 : const unsigned char *next = (const unsigned char*)buf;
255 : const unsigned char *end;
256 : uint64_t crc0, crc1, crc2; /* need to be 64 bits for crc32q */
257 :
258 : /* populate shift tables the first time through */
259 0 : pthread_once(&crc32c_once_hw, crc32c_init_hw);
260 :
261 : /* pre-process the crc */
262 0 : crc0 = crc ^ 0xffffffff;
263 :
264 : /* compute the crc for up to seven leading bytes to bring the data pointer
265 : to an eight-byte boundary */
266 0 : while (len && ((uintptr_t)next & 7) != 0) {
267 0 : __asm__("crc32b\t" "(%1), %0"
268 : : "=r"(crc0)
269 : : "r"(next), "0"(crc0));
270 0 : next++;
271 0 : len--;
272 : }
273 :
274 : /* compute the crc on sets of LONG*3 bytes, executing three independent crc
275 : instructions, each on LONG bytes -- this is optimized for the Nehalem,
276 : Westmere, Sandy Bridge, and Ivy Bridge architectures, which have a
277 : throughput of one crc per cycle, but a latency of three cycles */
278 0 : while (len >= LONG*3) {
279 0 : crc1 = 0;
280 0 : crc2 = 0;
281 0 : end = next + LONG;
282 : do {
283 0 : __asm__("crc32q\t" "(%3), %0\n\t"
284 : "crc32q\t" LONGx1 "(%3), %1\n\t"
285 : "crc32q\t" LONGx2 "(%3), %2"
286 : : "=r"(crc0), "=r"(crc1), "=r"(crc2)
287 : : "r"(next), "0"(crc0), "1"(crc1), "2"(crc2));
288 0 : next += 8;
289 0 : } while (next < end);
290 0 : crc0 = crc32c_shift(crc32c_long, crc0) ^ crc1;
291 0 : crc0 = crc32c_shift(crc32c_long, crc0) ^ crc2;
292 0 : next += LONG*2;
293 0 : len -= LONG*3;
294 : }
295 :
296 : /* do the same thing, but now on SHORT*3 blocks for the remaining data less
297 : than a LONG*3 block */
298 0 : while (len >= SHORT*3) {
299 0 : crc1 = 0;
300 0 : crc2 = 0;
301 0 : end = next + SHORT;
302 : do {
303 0 : __asm__("crc32q\t" "(%3), %0\n\t"
304 : "crc32q\t" SHORTx1 "(%3), %1\n\t"
305 : "crc32q\t" SHORTx2 "(%3), %2"
306 : : "=r"(crc0), "=r"(crc1), "=r"(crc2)
307 : : "r"(next), "0"(crc0), "1"(crc1), "2"(crc2));
308 0 : next += 8;
309 0 : } while (next < end);
310 0 : crc0 = crc32c_shift(crc32c_short, crc0) ^ crc1;
311 0 : crc0 = crc32c_shift(crc32c_short, crc0) ^ crc2;
312 0 : next += SHORT*2;
313 0 : len -= SHORT*3;
314 : }
315 :
316 : /* compute the crc on the remaining eight-byte units less than a SHORT*3
317 : block */
318 0 : end = next + (len - (len & 7));
319 0 : while (next < end) {
320 0 : __asm__("crc32q\t" "(%1), %0"
321 : : "=r"(crc0)
322 : : "r"(next), "0"(crc0));
323 0 : next += 8;
324 : }
325 0 : len &= 7;
326 :
327 : /* compute the crc for up to seven trailing bytes */
328 0 : while (len) {
329 0 : __asm__("crc32b\t" "(%1), %0"
330 : : "=r"(crc0)
331 : : "r"(next), "0"(crc0));
332 0 : next++;
333 0 : len--;
334 : }
335 :
336 : /* return a post-processed crc */
337 0 : return (uint32_t)crc0 ^ 0xffffffff;
338 : }
339 :
340 : /* Check for SSE 4.2. SSE 4.2 was first supported in Nehalem processors
341 : introduced in November, 2008. This does not check for the existence of the
342 : cpuid instruction itself, which was introduced on the 486SL in 1992, so this
343 : will fail on earlier x86 processors. cpuid works on all Pentium and later
344 : processors. */
345 : #define SSE42(have) \
346 : do { \
347 : uint32_t eax, ecx; \
348 : eax = 1; \
349 : __asm__("cpuid" \
350 : : "=c"(ecx) \
351 : : "a"(eax) \
352 : : "%ebx", "%edx"); \
353 : (have) = (ecx >> 20) & 1; \
354 : } while (0)
355 :
356 : #endif // HAVE_HWCRC32C
357 :
358 : #ifdef __ARM_FEATURE_CRC32
359 :
360 : uint32_t crc32c_arm_hw(uint32_t crc, const void *buf, size_t len)
361 : {
362 : crc = ~crc;
363 : uint8_t *pd = (uint8_t *)buf;
364 :
365 : // Align data if it's not aligned
366 : while (((uintptr_t)pd & 7) && len > 0) {
367 : crc = __crc32cb(crc, *(uint8_t *)pd);
368 : pd++;
369 : len--;
370 : }
371 :
372 : while (len >= 8) {
373 : crc = __crc32cd(crc, *(uint64_t *)pd);
374 : pd += 8;
375 : len -= 8;
376 : }
377 :
378 : while (len > 0) {
379 : crc = __crc32cb(crc, *(uint8_t *)pd);
380 : pd++;
381 : len--;
382 : }
383 :
384 : return ~crc;
385 : }
386 :
387 : #endif
388 :
389 : /* Compute a CRC-32C. If the crc32 instruction is available, use the hardware
390 : version. Otherwise, use the software version. */
391 0 : uint32_t crc32c(uint32_t crc, const void *buf, size_t len)
392 : {
393 : #ifdef HAVE_HWCRC32C
394 : int sse42;
395 :
396 0 : SSE42(sse42);
397 0 : return sse42 ? crc32c_hw(crc, buf, len) : crc32c_sw(crc, buf, len);
398 : #elif defined(__ARM_FEATURE_CRC32)
399 : return crc32c_arm_hw(crc, buf, len);
400 : #else
401 : #warning Hardware accelerated CRC32C is not available.
402 : return crc32c_sw(crc, buf, len);
403 : #endif // HAVE_HWCRC32C
404 : }
405 :
406 : #ifdef TEST
407 :
408 : #define SIZE (262144*3)
409 : #define CHUNK SIZE
410 :
411 : int main(int argc, char **argv)
412 : {
413 : char *buf;
414 : ssize_t got;
415 : size_t off, n;
416 : uint32_t crc;
417 :
418 : (void)argv;
419 : crc = 0;
420 : buf = (char*)malloc(SIZE);
421 : if (buf == NULL) {
422 : fputs("out of memory", stderr);
423 : return 1;
424 : }
425 : while ((got = read(0, buf, SIZE)) > 0) {
426 : off = 0;
427 : do {
428 : n = (size_t)got - off;
429 : if (n > CHUNK)
430 : n = CHUNK;
431 : crc = argc > 1 ? crc32c_sw(crc, buf + off, n) :
432 : crc32c(crc, buf + off, n);
433 : off += n;
434 : } while (off < (size_t)got);
435 : }
436 : free(buf);
437 : if (got == -1) {
438 : fputs("read error\n", stderr);
439 : return 1;
440 : }
441 : printf("%08x\n", crc);
442 : return 0;
443 : }
444 :
445 : #endif /* TEST */
|
