XRootD
XrdOucCRC32C.cc
Go to the documentation of this file.
1 /* crc32c.c -- compute CRC-32C using the Intel crc32 instruction
2  * Copyright (C) 2013, 2015 Mark Adler
3  * Version 1.3 31 Dec 2015 Mark Adler
4  */
5 
6 /*
7  This software is provided 'as-is', without any express or implied
8  warranty. In no event will the author be held liable for any damages
9  arising from the use of this software.
10 
11  Permission is granted to anyone to use this software for any purpose,
12  including commercial applications, and to alter it and redistribute it
13  freely, subject to the following restrictions:
14 
15  1. The origin of this software must not be misrepresented; you must not
16  claim that you wrote the original software. If you use this software
17  in a product, an acknowledgment in the product documentation would be
18  appreciated but is not required.
19  2. Altered source versions must be plainly marked as such, and must not be
20  misrepresented as being the original software.
21  3. This notice may not be removed or altered from any source distribution.
22 
23  Mark Adler
24  madler@alumni.caltech.edu
25  */
26 
27 /* Use hardware CRC instruction on Intel SSE 4.2 processors. This computes a
28  CRC-32C, *not* the CRC-32 used by Ethernet and zip, gzip, etc. A software
29  version is provided as a fall-back, as well as for speed comparisons. */
30 
31 /* Version history:
32  1.0 10 Feb 2013 First version
33  1.1 1 Aug 2013 Correct comments on why three crc instructions in parallel
34  1.2 1 Nov 2015 Add const qualifier to avoid compiler warning
35  Load entire input into memory (test code)
36  Argument gives number of times to repeat (test code)
37  Argument < 0 forces software implementation (test code)
38  1.3 31 Dec 2015 Check for Intel architecture using compiler macro
39  Support big-endian processors in software calculation
40  Add header for external use
41  */
42 
43 /* Modification history:
44  22 Nov 2019 Rename orignal crc32.c to XrdOucCRC32.cc and crc32c.h to
45  XrdOucCRC32C.hh with corresponding change to include
46  statement herein. Add required casts to allow C++
47  compilation.
48  28 Oct 2026 Add a hardware version for ARMv8 processors.
49  */
50 
51 #include <pthread.h>
52 #include "XrdOuc/XrdOucCRC32C.hh"
53 
54 /* Little-endian 64-bit ARM processors may provide the ARMv8 crc32c
55  instructions, mandatory since ARMv8.1 and optional in ARMv8.0. */
56 #if defined(__aarch64__) && !defined(__AARCH64EB__)
57 #define CRC32C_HW_ARM
58 #include <arm_acle.h>
59 #include <cstring>
60 #if !defined(__ARM_FEATURE_CRC32) && defined(__linux__)
61 #include <sys/auxv.h>
62 #include <asm/hwcap.h>
63 #endif
64 #endif
65 
66 /* CRC-32C (iSCSI) polynomial in reversed bit order. */
67 #define POLY 0x82f63b78
68 
69 #if defined(__x86_64__) || defined(CRC32C_HW_ARM)
70 
71 /* Shift tables shared by the hardware CRC-32C implementations. */
72 
73 /* Multiply a matrix times a vector over the Galois field of two elements,
74  GF(2). Each element is a bit in an unsigned integer. mat must have at
75  least as many entries as the power of two for most significant one bit in
76  vec. */
77 static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec) {
78  uint32_t sum = 0;
79  while (vec) {
80  if (vec & 1)
81  sum ^= *mat;
82  vec >>= 1;
83  mat++;
84  }
85  return sum;
86 }
87 
88 /* Multiply a matrix by itself over GF(2). Both mat and square must have 32
89  rows. */
90 static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat) {
91  for (unsigned n = 0; n < 32; n++)
92  square[n] = gf2_matrix_times(mat, mat[n]);
93 }
94 
95 /* Construct an operator to apply len zeros to a crc. len must be a power of
96  two. If len is not a power of two, then the result is the same as for the
97  largest power of two less than len. The result for len == 0 is the same as
98  for len == 1. A version of this routine could be easily written for any
99  len, but that is not needed for this application. */
100 static void crc32c_zeros_op(uint32_t *even, size_t len) {
101  uint32_t odd[32]; /* odd-power-of-two zeros operator */
102 
103  /* put operator for one zero bit in odd */
104  odd[0] = POLY; /* CRC-32C polynomial */
105  uint32_t row = 1;
106  for (unsigned n = 1; n < 32; n++) {
107  odd[n] = row;
108  row <<= 1;
109  }
110 
111  /* put operator for two zero bits in even */
112  gf2_matrix_square(even, odd);
113 
114  /* put operator for four zero bits in odd */
115  gf2_matrix_square(odd, even);
116 
117  /* first square will put the operator for one zero byte (eight zero bits),
118  in even -- next square puts operator for two zero bytes in odd, and so
119  on, until len has been rotated down to zero */
120  do {
121  gf2_matrix_square(even, odd);
122  len >>= 1;
123  if (len == 0)
124  return;
125  gf2_matrix_square(odd, even);
126  len >>= 1;
127  } while (len);
128 
129  /* answer ended up in odd -- copy to even */
130  for (unsigned n = 0; n < 32; n++)
131  even[n] = odd[n];
132 }
133 
134 /* Take a length and build four lookup tables for applying the zeros operator
135  for that length, byte-by-byte on the operand. */
136 static void crc32c_zeros(uint32_t zeros[][256], size_t len) {
137  uint32_t op[32];
138 
139  crc32c_zeros_op(op, len);
140  for (unsigned n = 0; n < 256; n++) {
141  zeros[0][n] = gf2_matrix_times(op, n);
142  zeros[1][n] = gf2_matrix_times(op, n << 8);
143  zeros[2][n] = gf2_matrix_times(op, n << 16);
144  zeros[3][n] = gf2_matrix_times(op, n << 24);
145  }
146 }
147 
148 /* Apply the zeros operator table to crc. */
149 static inline uint32_t crc32c_shift(uint32_t zeros[][256], uint32_t crc) {
150  return zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^
151  zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24];
152 }
153 
154 /* Block sizes for three-way parallel crc computation. LONG and SHORT must
155  both be powers of two. The associated string constants must be set
156  accordingly, for use in constructing the assembler instructions. */
157 #define LONG 8192
158 #define LONGx1 "8192"
159 #define LONGx2 "16384"
160 #define SHORT 256
161 #define SHORTx1 "256"
162 #define SHORTx2 "512"
163 
164 /* Tables for hardware crc that shift a crc by LONG and SHORT zeros. */
165 static pthread_once_t crc32c_once_hw = PTHREAD_ONCE_INIT;
166 static uint32_t crc32c_long[4][256];
167 static uint32_t crc32c_short[4][256];
168 
169 /* Initialize tables for shifting crcs. */
170 static void crc32c_init_hw(void) {
171  crc32c_zeros(crc32c_long, LONG);
172  crc32c_zeros(crc32c_short, SHORT);
173 }
174 
175 #endif /* __x86_64__ || CRC32C_HW_ARM */
176 
177 #ifdef __x86_64__
178 
179 /* Compute CRC-32C using the Intel hardware instruction. */
180 static uint32_t crc32c_hw(uint32_t crc, void const *buf, size_t len) {
181  /* populate shift tables the first time through */
182  pthread_once(&crc32c_once_hw, crc32c_init_hw);
183 
184  /* pre-process the crc */
185  crc = ~crc;
186  uint64_t crc0 = crc; /* 64-bits for crc32q instruction */
187 
188  /* the crc32 instructions accept unaligned operands, so the data pointer is
189  not first brought to an eight-byte boundary: doing that a byte at a time
190  costs more than it saves */
191  unsigned char const *next = (unsigned char const *)buf;
192 
193  /* compute the crc on sets of LONG*3 bytes, executing three independent crc
194  instructions, each on LONG bytes -- this is optimized for the Nehalem,
195  Westmere, Sandy Bridge, and Ivy Bridge architectures, which have a
196  throughput of one crc per cycle, but a latency of three cycles */
197  while (len >= LONG*3) {
198  uint64_t crc1 = 0;
199  uint64_t crc2 = 0;
200  unsigned char const * const end = next + LONG;
201  do {
202  __asm__("crc32q\t" "(%3), %0\n\t"
203  "crc32q\t" LONGx1 "(%3), %1\n\t"
204  "crc32q\t" LONGx2 "(%3), %2"
205  : "=r"(crc0), "=r"(crc1), "=r"(crc2)
206  : "r"(next), "0"(crc0), "1"(crc1), "2"(crc2));
207  next += 8;
208  } while (next < end);
209  crc0 = crc32c_shift(crc32c_long, crc0) ^ crc1;
210  crc0 = crc32c_shift(crc32c_long, crc0) ^ crc2;
211  next += LONG*2;
212  len -= LONG*3;
213  }
214 
215  /* do the same thing, but now on SHORT*3 blocks for the remaining data less
216  than a LONG*3 block */
217  while (len >= SHORT*3) {
218  uint64_t crc1 = 0;
219  uint64_t crc2 = 0;
220  unsigned char const * const end = next + SHORT;
221  do {
222  __asm__("crc32q\t" "(%3), %0\n\t"
223  "crc32q\t" SHORTx1 "(%3), %1\n\t"
224  "crc32q\t" SHORTx2 "(%3), %2"
225  : "=r"(crc0), "=r"(crc1), "=r"(crc2)
226  : "r"(next), "0"(crc0), "1"(crc1), "2"(crc2));
227  next += 8;
228  } while (next < end);
229  crc0 = crc32c_shift(crc32c_short, crc0) ^ crc1;
230  crc0 = crc32c_shift(crc32c_short, crc0) ^ crc2;
231  next += SHORT*2;
232  len -= SHORT*3;
233  }
234 
235  /* compute the crc on the remaining eight-byte units less than a SHORT*3
236  block */
237  {
238  unsigned char const * const end = next + (len - (len & 7));
239  while (next < end) {
240  __asm__("crc32q\t" "(%1), %0"
241  : "=r"(crc0)
242  : "r"(next), "0"(crc0));
243  next += 8;
244  }
245  len &= 7;
246  }
247 
248  /* compute the crc for up to seven trailing bytes, four, two and one byte at
249  a time */
250  crc = crc0;
251  if (len & 4) {
252  __asm__("crc32l\t" "(%1), %0"
253  : "=r"(crc)
254  : "r"(next), "0"(crc));
255  next += 4;
256  }
257  if (len & 2) {
258  __asm__("crc32w\t" "(%1), %0"
259  : "=r"(crc)
260  : "r"(next), "0"(crc));
261  next += 2;
262  }
263  if (len & 1) {
264  __asm__("crc32b\t" "(%1), %0"
265  : "=r"(crc)
266  : "r"(next), "0"(crc));
267  }
268 
269  /* return a post-processed crc */
270  return ~crc;
271 }
272 
273 /* Check for SSE 4.2. SSE 4.2 was first supported in Nehalem processors
274  introduced in November, 2008. This does not check for the existence of the
275  cpuid instruction itself, which was introduced on the 486SL in 1992, so this
276  will fail on earlier x86 processors. cpuid works on all Pentium and later
277  processors. */
278 #define SSE42(have) \
279  do { \
280  uint32_t eax, ecx; \
281  eax = 1; \
282  __asm__("cpuid" \
283  : "=c"(ecx) \
284  : "a"(eax) \
285  : "%ebx", "%edx"); \
286  (have) = (ecx >> 20) & 1; \
287  } while (0)
288 
289 static int crc32c_have_sse42(void) {
290  int sse42;
291 
292  SSE42(sse42);
293  return sse42;
294 }
295 
296 /* Compute a CRC-32C. If the crc32 instruction is available, use the hardware
297  version. Otherwise, use the software version. The cpuid check is done only
298  once, since cpuid is slow and traps to the hypervisor in virtual machines. */
299 uint32_t crc32c(uint32_t crc, void const *buf, size_t len) {
300  static const int sse42 = crc32c_have_sse42();
301 
302  return sse42 ? crc32c_hw(crc, buf, len) : crc32c_sw(crc, buf, len);
303 }
304 
305 #elif defined(CRC32C_HW_ARM)
306 
307 /* The crc32c intrinsics need the crc extension: enable it for the functions
308  using them when it is not enabled for the whole compilation unit. */
309 #ifdef __ARM_FEATURE_CRC32
310 #define CRC32C_TARGET_CRC
311 #else
312 #define CRC32C_TARGET_CRC __attribute__((target("+crc")))
313 #endif
314 
315 /* Load eight bytes from a possibly unaligned address. */
316 static inline uint64_t crc32c_load64(unsigned char const *next) {
317  uint64_t word;
318  memcpy(&word, next, sizeof(word));
319  return word;
320 }
321 
322 /* Compute CRC-32C using the ARMv8 hardware instructions, with the same
323  three-way parallel scheme as on x86 to hide the latency of the crc32cx
324  instruction. */
325 CRC32C_TARGET_CRC
326 static uint32_t crc32c_hw(uint32_t crc, void const *buf, size_t len) {
327  /* populate shift tables the first time through */
328  pthread_once(&crc32c_once_hw, crc32c_init_hw);
329 
330  uint32_t crc0 = ~crc;
331  unsigned char const *next = (unsigned char const *)buf;
332 
333  /* compute the crc on sets of LONG*3 bytes, three independent crc
334  instructions at a time, each on LONG bytes */
335  while (len >= LONG*3) {
336  uint32_t crc1 = 0;
337  uint32_t crc2 = 0;
338  unsigned char const * const end = next + LONG;
339  do {
340  crc0 = __crc32cd(crc0, crc32c_load64(next));
341  crc1 = __crc32cd(crc1, crc32c_load64(next + LONG));
342  crc2 = __crc32cd(crc2, crc32c_load64(next + LONG*2));
343  next += 8;
344  } while (next < end);
345  crc0 = crc32c_shift(crc32c_long, crc0) ^ crc1;
346  crc0 = crc32c_shift(crc32c_long, crc0) ^ crc2;
347  next += LONG*2;
348  len -= LONG*3;
349  }
350 
351  /* do the same thing, but now on SHORT*3 blocks for the remaining data less
352  than a LONG*3 block */
353  while (len >= SHORT*3) {
354  uint32_t crc1 = 0;
355  uint32_t crc2 = 0;
356  unsigned char const * const end = next + SHORT;
357  do {
358  crc0 = __crc32cd(crc0, crc32c_load64(next));
359  crc1 = __crc32cd(crc1, crc32c_load64(next + SHORT));
360  crc2 = __crc32cd(crc2, crc32c_load64(next + SHORT*2));
361  next += 8;
362  } while (next < end);
363  crc0 = crc32c_shift(crc32c_short, crc0) ^ crc1;
364  crc0 = crc32c_shift(crc32c_short, crc0) ^ crc2;
365  next += SHORT*2;
366  len -= SHORT*3;
367  }
368 
369  /* compute the crc on the remaining eight-byte units less than a SHORT*3
370  block */
371  while (len >= 8) {
372  crc0 = __crc32cd(crc0, crc32c_load64(next));
373  next += 8;
374  len -= 8;
375  }
376 
377  /* compute the crc for up to seven trailing bytes, four, two and one byte at
378  a time */
379  if (len & 4) {
380  uint32_t word;
381  memcpy(&word, next, sizeof(word));
382  crc0 = __crc32cw(crc0, word);
383  next += 4;
384  }
385  if (len & 2) {
386  uint16_t half;
387  memcpy(&half, next, sizeof(half));
388  crc0 = __crc32ch(crc0, half);
389  next += 2;
390  }
391  if (len & 1)
392  crc0 = __crc32cb(crc0, *next);
393 
394  /* return a post-processed crc */
395  return ~crc0;
396 }
397 
398 /* Check for the crc32c instructions: known at compile time when the crc
399  extension is enabled, otherwise asked from the kernel on Linux. */
400 static int crc32c_have_crc(void) {
401 #if defined(__ARM_FEATURE_CRC32)
402  return 1;
403 #elif defined(__linux__) && defined(HWCAP_CRC32)
404  return (getauxval(AT_HWCAP) & HWCAP_CRC32) != 0;
405 #else
406  return 0;
407 #endif
408 }
409 
410 /* Compute a CRC-32C. If the crc32c instructions are available, use the
411  hardware version. Otherwise, use the software version. The check is done
412  only once. */
413 uint32_t crc32c(uint32_t crc, void const *buf, size_t len) {
414  static const int hw = crc32c_have_crc();
415 
416  return hw ? crc32c_hw(crc, buf, len) : crc32c_sw(crc, buf, len);
417 }
418 
419 #else /* !__x86_64__ && !CRC32C_HW_ARM */
420 
421 uint32_t crc32c(uint32_t crc, void const *buf, size_t len) {
422  return crc32c_sw(crc, buf, len);
423 }
424 
425 #endif
426 
427 /* Construct table for software CRC-32C little-endian calculation. */
428 static pthread_once_t crc32c_once_little = PTHREAD_ONCE_INIT;
429 static uint32_t crc32c_table_little[8][256];
430 static void crc32c_init_sw_little(void) {
431  for (unsigned n = 0; n < 256; n++) {
432  uint32_t crc = n;
433  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
434  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
435  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
436  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
437  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
438  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
439  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
440  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
441  crc32c_table_little[0][n] = crc;
442  }
443  for (unsigned n = 0; n < 256; n++) {
444  uint32_t crc = crc32c_table_little[0][n];
445  for (unsigned k = 1; k < 8; k++) {
446  crc = crc32c_table_little[0][crc & 0xff] ^ (crc >> 8);
447  crc32c_table_little[k][n] = crc;
448  }
449  }
450 }
451 
452 /* Compute a CRC-32C in software assuming a little-endian architecture,
453  constructing the required table if that hasn't already been done. */
454 uint32_t crc32c_sw_little(uint32_t crc, void const *buf, size_t len) {
455  unsigned char const *next = (unsigned char const *)buf;
456 
458  crc = ~crc;
459  while (len && ((uintptr_t)next & 7) != 0) {
460  crc = crc32c_table_little[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
461  len--;
462  }
463  if (len >= 8) {
464  uint64_t crcw = crc;
465  do {
466  crcw ^= *(uint64_t const *)next;
467  crcw = crc32c_table_little[7][crcw & 0xff] ^
468  crc32c_table_little[6][(crcw >> 8) & 0xff] ^
469  crc32c_table_little[5][(crcw >> 16) & 0xff] ^
470  crc32c_table_little[4][(crcw >> 24) & 0xff] ^
471  crc32c_table_little[3][(crcw >> 32) & 0xff] ^
472  crc32c_table_little[2][(crcw >> 40) & 0xff] ^
473  crc32c_table_little[1][(crcw >> 48) & 0xff] ^
474  crc32c_table_little[0][crcw >> 56];
475  next += 8;
476  len -= 8;
477  } while (len >= 8);
478  crc = crcw;
479  }
480  while (len) {
481  crc = crc32c_table_little[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
482  len--;
483  }
484  return ~crc;
485 }
486 
487 /* Swap the bytes in a uint64_t. (Only for big-endian.) */
488 #if defined(__has_builtin) || (defined(__GNUC__) && \
489  (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)))
490 # define swap __builtin_bswap64
491 #else
492 static inline uint64_t swap(uint64_t x) {
493  x = ((x << 8) & 0xff00ff00ff00ff00) | ((x >> 8) & 0xff00ff00ff00ff);
494  x = ((x << 16) & 0xffff0000ffff0000) | ((x >> 16) & 0xffff0000ffff);
495  return (x << 32) | (x >> 32);
496 }
497 #endif
498 
499 /* Construct tables for software CRC-32C big-endian calculation. */
500 static pthread_once_t crc32c_once_big = PTHREAD_ONCE_INIT;
501 static uint32_t crc32c_table_big_byte[256];
502 static uint64_t crc32c_table_big[8][256];
503 static void crc32c_init_sw_big(void) {
504  for (unsigned n = 0; n < 256; n++) {
505  uint32_t crc = n;
506  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
507  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
508  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
509  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
510  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
511  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
512  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
513  crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
514  crc32c_table_big_byte[n] = crc;
515  }
516  for (unsigned n = 0; n < 256; n++) {
517  uint32_t crc = crc32c_table_big_byte[n];
518  crc32c_table_big[0][n] = swap(crc);
519  for (unsigned k = 1; k < 8; k++) {
520  crc = crc32c_table_big_byte[crc & 0xff] ^ (crc >> 8);
521  crc32c_table_big[k][n] = swap(crc);
522  }
523  }
524 }
525 
526 /* Compute a CRC-32C in software assuming a big-endian architecture,
527  constructing the required tables if that hasn't already been done. */
528 uint32_t crc32c_sw_big(uint32_t crc, void const *buf, size_t len) {
529  unsigned char const *next = (unsigned char const *)buf;
530 
531  pthread_once(&crc32c_once_big, crc32c_init_sw_big);
532  crc = ~crc;
533  while (len && ((uintptr_t)next & 7) != 0) {
534  crc = crc32c_table_big_byte[(crc ^ *next++) & 0xff] ^ (crc >> 8);
535  len--;
536  }
537  if (len >= 8) {
538  uint64_t crcw = swap(crc);
539  do {
540  crcw ^= *(uint64_t const *)next;
541  crcw = crc32c_table_big[0][crcw & 0xff] ^
542  crc32c_table_big[1][(crcw >> 8) & 0xff] ^
543  crc32c_table_big[2][(crcw >> 16) & 0xff] ^
544  crc32c_table_big[3][(crcw >> 24) & 0xff] ^
545  crc32c_table_big[4][(crcw >> 32) & 0xff] ^
546  crc32c_table_big[5][(crcw >> 40) & 0xff] ^
547  crc32c_table_big[6][(crcw >> 48) & 0xff] ^
548  crc32c_table_big[7][(crcw >> 56)];
549  next += 8;
550  len -= 8;
551  } while (len >= 8);
552  crc = swap(crcw);
553  }
554  while (len) {
555  crc = crc32c_table_big_byte[(crc ^ *next++) & 0xff] ^ (crc >> 8);
556  len--;
557  }
558  return ~crc;
559 }
560 
561 /* Table-driven software CRC-32C. This is about 15 times slower than using the
562  hardware instructions. Determine the endianess of the processor and proceed
563  accordingly. Ideally the endianess will be determined at compile time, in
564  which case the unused functions and tables for the other endianess will be
565  removed by the optimizer. If not, then the proper routines and tables will
566  be used, even if the endianess is changed mid-stream. (Yes, there are
567  processors that permit that -- go figure.) */
568 uint32_t crc32c_sw(uint32_t crc, void const *buf, size_t len) {
569  static int const little = 1;
570  if (*(char const *)&little)
571  return crc32c_sw_little(crc, buf, len);
572  else
573  return crc32c_sw_big(crc, buf, len);
574 }
575 
576 /******************************************************************************/
577 /* c r c 3 2 c _ c o m b i n e */
578 /******************************************************************************/
579 
581 uint32_t crc32c_combine(uint32_t crcA, uint32_t crcB, size_t lengthB)
582 {
583  // Original source from Stephan Brumme
584  // https://github.com/stbrumme/crc32
585  // https://create.stephan-brumme.com/crc32/
586  // based on Mark Adler's crc_combine from
587  // https://github.com/madler/pigz/blob/master/pigz.c
588 
589  // main idea:
590  // - if you have two equally-sized blocks A and B,
591  // then you can create a block C = A ^ B
592  // which has the property crc(C) = crc(A) ^ crc(B)
593  // - if you append length(B) zeros to A and call it A' (think of it as AAAA000)
594  // and prepend length(A) zeros to B and call it B' (think of it as 0000BBB)
595  // then exists a C' = A' ^ B'
596  // - remember: if you XOR someting with zero, it remains unchanged: X ^ 0 = X
597  // - that means C' = A concat B so that crc(A concat B) = crc(C') = crc(A') ^ crc(B')
598  // - the trick is to compute crc(A') based on crc(A)
599  // and crc(B') based on crc(B)
600  // - since B' starts with many zeros, the crc of those initial zeros is still zero
601  // - that means crc(B') = crc(B)
602  // - unfortunately the trailing zeros of A' change the crc, so usually crc(A') != crc(A)
603  // - the following code is a fast algorithm to compute crc(A')
604  // - starting with crc(A) and appending length(B) zeros, needing just log2(length(B)) iterations
605  // - the details are explained by the original author at
606  // https://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream/23126768
607  //
608  // notes:
609  // - I squeezed everything into one function to keep global namespace clean (original code two helper functions)
610  // - most original comments are still in place, I added comments where these helper functions where made inline code
611  // - performance-wise there isn't any differenze to the original zlib/pigz code
612 
613  // degenerated case
614  if (lengthB == 0)
615  return crcA;
616 
618  const uint32_t CrcBits = 32;
619 
620  uint32_t odd [CrcBits]; // odd-power-of-two zeros operator
621  uint32_t even[CrcBits]; // even-power-of-two zeros operator
622 
623  // put operator for one zero bit in odd
624  odd[0] = POLY; // CRC-32 polynomial
625  for (int i = 1; i < (int)CrcBits; i++)
626  odd[i] = 1 << (i - 1);
627 
628  // put operator for two zero bits in even
629  // same as gf2_matrix_square(even, odd);
630  for (int i = 0; i < (int)CrcBits; i++)
631  {
632  uint32_t vec = odd[i];
633  even[i] = 0;
634  for (int j = 0; vec != 0; j++, vec >>= 1)
635  if (vec & 1)
636  even[i] ^= odd[j];
637  }
638  // put operator for four zero bits in odd
639  // same as gf2_matrix_square(odd, even);
640  for (int i = 0; i < (int)CrcBits; i++)
641  {
642  uint32_t vec = even[i];
643  odd[i] = 0;
644  for (int j = 0; vec != 0; j++, vec >>= 1)
645  if (vec & 1)
646  odd[i] ^= even[j];
647  }
648 
649  // the following loop becomes much shorter if I keep swapping even and odd
650  uint32_t* a = even;
651  uint32_t* b = odd;
652  // apply secondLength zeros to firstCrc32
653  for (; lengthB > 0; lengthB >>= 1)
654  {
655  // same as gf2_matrix_square(a, b);
656  for (int i = 0; i < (int)CrcBits; i++)
657  {
658  uint32_t vec = b[i];
659  a[i] = 0;
660  for (int j = 0; vec != 0; j++, vec >>= 1)
661  if (vec & 1)
662  a[i] ^= b[j];
663  }
664 
665  // apply zeros operator for this bit
666  if (lengthB & 1)
667  {
668  // same as firstCrc32 = gf2_matrix_times(a, firstCrc32);
669  uint32_t sum = 0;
670  for (int i = 0; crcA != 0; i++, crcA >>= 1)
671  if (crcA & 1)
672  sum ^= a[i];
673  crcA = sum;
674  }
675 
676  // switch even and odd
677  uint32_t* t = a; a = b; b = t;
678  }
679 
680  // return combined crc
681  return crcA ^ crcB;
682 }
683 
684 /******************************************************************************/
685 /* m a i n */
686 /******************************************************************************/
687 
688 #ifdef TEST
689 
690 #include <cstdio>
691 #include <cstdlib>
692 #include "load.h"
693 
694 int main(int argc, char **argv) {
695  /* interpret argument */
696  if (argc > 2) {
697  fputs("only one argument permitted\n", stderr);
698  return 1;
699  }
700  long rep = argc == 1 ? 1 : strtol(argv[1], NULL, 10);
701  if (rep == 0) {
702  fputs("usage: crc32c [[-]nnn] < data\n"
703  " where nnn is the number of times to repeat\n"
704  " negative forces the software implementation\n", stderr);
705  return 0;
706  }
707  int sw = rep < 0;
708  if (sw)
709  rep = -rep;
710 
711  /* read input */
712  void *dat = NULL;
713  size_t size, len;
714  int ret = load(stdin, 0, &dat, &size, &len);
715  if (ret) {
716  fputs("error reading from stdin\n", stderr);
717  return 1;
718  }
719 
720  /* compute crc rep times */
721  uint32_t crc;
722  do {
723  crc = sw ? crc32c_sw(0, dat, len) : crc32c(0, dat, len);
724  } while (--rep);
725 
726  /* show crc */
727  printf("0x%08x\n", crc);
728 
729  /* clean up */
730  free(dat);
731  return 0;
732 }
733 
734 #endif /* TEST */
int main(int argc, char *argv[])
Definition: XrdMain.cc:161
static pthread_once_t crc32c_once_little
uint32_t crc32c(uint32_t crc, void const *buf, size_t len)
static uint64_t swap(uint64_t x)
uint32_t crc32c_sw_big(uint32_t crc, void const *buf, size_t len)
uint32_t crc32c_sw(uint32_t crc, void const *buf, size_t len)
static uint64_t crc32c_table_big[8][256]
static void crc32c_init_sw_little(void)
static uint32_t crc32c_table_big_byte[256]
static void crc32c_init_sw_big(void)
#define POLY
Definition: XrdOucCRC32C.cc:67
uint32_t crc32c_sw_little(uint32_t crc, void const *buf, size_t len)
static uint32_t crc32c_table_little[8][256]
static pthread_once_t crc32c_once_big
uint32_t crc32c_combine(uint32_t crcA, uint32_t crcB, size_t lengthB)
merge two CRC32 such that result = crc32(dataB, lengthB, crc32(dataA, lengthA))