XRootD
XrdOucCRC32C.cc File Reference
#include <pthread.h>
#include "XrdOuc/XrdOucCRC32C.hh"
+ Include dependency graph for XrdOucCRC32C.cc:

Go to the source code of this file.

Macros

#define POLY   0x82f63b78
 

Functions

uint32_t crc32c (uint32_t crc, void const *buf, size_t len)
 
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)) More...
 
static void crc32c_init_sw_big (void)
 
static void crc32c_init_sw_little (void)
 
uint32_t crc32c_sw (uint32_t crc, void const *buf, size_t len)
 
uint32_t crc32c_sw_big (uint32_t crc, void const *buf, size_t len)
 
uint32_t crc32c_sw_little (uint32_t crc, void const *buf, size_t len)
 
static uint64_t swap (uint64_t x)
 

Variables

static pthread_once_t crc32c_once_big = PTHREAD_ONCE_INIT
 
static pthread_once_t crc32c_once_little = PTHREAD_ONCE_INIT
 
static uint64_t crc32c_table_big [8][256]
 
static uint32_t crc32c_table_big_byte [256]
 
static uint32_t crc32c_table_little [8][256]
 

Macro Definition Documentation

◆ POLY

#define POLY   0x82f63b78

Definition at line 67 of file XrdOucCRC32C.cc.

Function Documentation

◆ crc32c()

uint32_t crc32c ( uint32_t  crc,
void const *  buf,
size_t  len 
)

Definition at line 421 of file XrdOucCRC32C.cc.

421  {
422  return crc32c_sw(crc, buf, len);
423 }
uint32_t crc32c_sw(uint32_t crc, void const *buf, size_t len)

References crc32c_sw().

Referenced by XrdEc::ObjCfg::ObjCfg(), XrdOucCRC::Calc32C(), XrdPfc::Info::CalcCksumStore(), XrdPfc::Info::CalcCksumSyncedAndAStats(), XrdOssCsiPages::FetchRangeUnaligned_postblock(), XrdOssCsiPages::FetchRangeUnaligned_preblock(), XrdOssCsiPages::StoreRangeUnaligned_postblock(), XrdOssCsiPages::StoreRangeUnaligned_preblock(), XrdOssCsiPages::truncate(), XrdOssCsiPages::UpdateRangeHoleUntilPage(), and XrdOucCRC::Ver32C().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ crc32c_combine()

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))

CRC32 => 32 bits

Definition at line 581 of file XrdOucCRC32C.cc.

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 }
#define POLY
Definition: XrdOucCRC32C.cc:67

References POLY.

Referenced by XrdOucCRC::Combine32C().

+ Here is the caller graph for this function:

◆ crc32c_init_sw_big()

static void crc32c_init_sw_big ( void  )
static

Definition at line 503 of file XrdOucCRC32C.cc.

503  {
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 }
static uint64_t swap(uint64_t x)
static uint64_t crc32c_table_big[8][256]
static uint32_t crc32c_table_big_byte[256]

References crc32c_table_big, crc32c_table_big_byte, POLY, and swap().

Referenced by crc32c_sw_big().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ crc32c_init_sw_little()

static void crc32c_init_sw_little ( void  )
static

Definition at line 430 of file XrdOucCRC32C.cc.

430  {
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 }
static uint32_t crc32c_table_little[8][256]

References crc32c_table_little, and POLY.

Referenced by crc32c_sw_little().

+ Here is the caller graph for this function:

◆ crc32c_sw()

uint32_t crc32c_sw ( uint32_t  crc,
void const *  buf,
size_t  len 
)

Definition at line 568 of file XrdOucCRC32C.cc.

568  {
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 }
uint32_t crc32c_sw_big(uint32_t crc, void const *buf, size_t len)
uint32_t crc32c_sw_little(uint32_t crc, void const *buf, size_t len)

References crc32c_sw_big(), and crc32c_sw_little().

Referenced by crc32c().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ crc32c_sw_big()

uint32_t crc32c_sw_big ( uint32_t  crc,
void const *  buf,
size_t  len 
)

Definition at line 528 of file XrdOucCRC32C.cc.

528  {
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 }
static void crc32c_init_sw_big(void)
static pthread_once_t crc32c_once_big

References crc32c_init_sw_big(), crc32c_once_big, crc32c_table_big, crc32c_table_big_byte, and swap().

Referenced by crc32c_sw().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ crc32c_sw_little()

uint32_t crc32c_sw_little ( uint32_t  crc,
void const *  buf,
size_t  len 
)

Definition at line 454 of file XrdOucCRC32C.cc.

454  {
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 }
static pthread_once_t crc32c_once_little
static void crc32c_init_sw_little(void)

References crc32c_init_sw_little(), crc32c_once_little, and crc32c_table_little.

Referenced by crc32c_sw().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ swap()

static uint64_t swap ( uint64_t  x)
inlinestatic

Definition at line 492 of file XrdOucCRC32C.cc.

492  {
493  x = ((x << 8) & 0xff00ff00ff00ff00) | ((x >> 8) & 0xff00ff00ff00ff);
494  x = ((x << 16) & 0xffff0000ffff0000) | ((x >> 16) & 0xffff0000ffff);
495  return (x << 32) | (x >> 32);
496 }

Referenced by crc32c_init_sw_big(), crc32c_sw_big(), and XrdCl::StreamMutex::UnLock().

+ Here is the caller graph for this function:

Variable Documentation

◆ crc32c_once_big

pthread_once_t crc32c_once_big = PTHREAD_ONCE_INIT
static

Definition at line 500 of file XrdOucCRC32C.cc.

Referenced by crc32c_sw_big().

◆ crc32c_once_little

pthread_once_t crc32c_once_little = PTHREAD_ONCE_INIT
static

Definition at line 428 of file XrdOucCRC32C.cc.

Referenced by crc32c_sw_little().

◆ crc32c_table_big

uint64_t crc32c_table_big[8][256]
static

Definition at line 502 of file XrdOucCRC32C.cc.

Referenced by crc32c_init_sw_big(), and crc32c_sw_big().

◆ crc32c_table_big_byte

uint32_t crc32c_table_big_byte[256]
static

Definition at line 501 of file XrdOucCRC32C.cc.

Referenced by crc32c_init_sw_big(), and crc32c_sw_big().

◆ crc32c_table_little

uint32_t crc32c_table_little[8][256]
static

Definition at line 429 of file XrdOucCRC32C.cc.

Referenced by crc32c_init_sw_little(), and crc32c_sw_little().