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 54 of file XrdOucCRC32C.cc.

Function Documentation

crc32c()

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

Definition at line 277 of file XrdOucCRC32C.cc.

                                                           {
    return crc32c_sw(crc, buf, 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 437 of file XrdOucCRC32C.cc.

{
  // Original source from Stephan Brumme
  // https://github.com/stbrumme/crc32
  // https://create.stephan-brumme.com/crc32/
  // based on Mark Adler's crc_combine from
  // https://github.com/madler/pigz/blob/master/pigz.c
 
  // main idea:
  // - if you have two equally-sized blocks A and B,
  //   then you can create a block C = A ^ B
  //   which has the property crc(C) = crc(A) ^ crc(B)
  // - if you append length(B) zeros to A and call it A' (think of it as AAAA000)
  //   and   prepend length(A) zeros to B and call it B' (think of it as 0000BBB)
  //   then exists a C' = A' ^ B'
  // - remember: if you XOR someting with zero, it remains unchanged: X ^ 0 = X
  // - that means C' = A concat B so that crc(A concat B) = crc(C') = crc(A') ^ crc(B')
  // - the trick is to compute crc(A') based on crc(A)
  //                       and crc(B') based on crc(B)
  // - since B' starts with many zeros, the crc of those initial zeros is still zero
  // - that means crc(B') = crc(B)
  // - unfortunately the trailing zeros of A' change the crc, so usually crc(A') != crc(A)
  // - the following code is a fast algorithm to compute crc(A')
  // - starting with crc(A) and appending length(B) zeros, needing just log2(length(B)) iterations
  // - the details are explained by the original author at
  //   https://stackoverflow.com/questions/23122312/crc-calculation-of-a-mostly-static-data-stream/23126768
  //
  // notes:
  // - I squeezed everything into one function to keep global namespace clean (original code two helper functions)
  // - most original comments are still in place, I added comments where these helper functions where made inline code
  // - performance-wise there isn't any differenze to the original zlib/pigz code
 
  // degenerated case
  if (lengthB == 0)
    return crcA;
 
  const uint32_t CrcBits = 32;
 
  uint32_t odd [CrcBits]; // odd-power-of-two  zeros operator
  uint32_t even[CrcBits]; // even-power-of-two zeros operator
 
  // put operator for one zero bit in odd
  odd[0] = POLY;          // CRC-32 polynomial
  for (int i = 1; i < (int)CrcBits; i++)
    odd[i] = 1 << (i - 1);
 
  // put operator for two zero bits in even
  // same as gf2_matrix_square(even, odd);
  for (int i = 0; i < (int)CrcBits; i++)
  {
    uint32_t vec = odd[i];
    even[i] = 0;
    for (int j = 0; vec != 0; j++, vec >>= 1)
      if (vec & 1)
        even[i] ^= odd[j];
  }
  // put operator for four zero bits in odd
  // same as gf2_matrix_square(odd, even);
  for (int i = 0; i < (int)CrcBits; i++)
  {
    uint32_t vec = even[i];
    odd[i] = 0;
    for (int j = 0; vec != 0; j++, vec >>= 1)
      if (vec & 1)
        odd[i] ^= even[j];
  }
 
  // the following loop becomes much shorter if I keep swapping even and odd
  uint32_t* a = even;
  uint32_t* b = odd;
  // apply secondLength zeros to firstCrc32
  for (; lengthB > 0; lengthB >>= 1)
  {
    // same as gf2_matrix_square(a, b);
    for (int i = 0; i < (int)CrcBits; i++)
    {
      uint32_t vec = b[i];
      a[i] = 0;
      for (int j = 0; vec != 0; j++, vec >>= 1)
        if (vec & 1)
          a[i] ^= b[j];
    }
 
    // apply zeros operator for this bit
    if (lengthB & 1)
    {
      // same as firstCrc32 = gf2_matrix_times(a, firstCrc32);
      uint32_t sum = 0;
      for (int i = 0; crcA != 0; i++, crcA >>= 1)
        if (crcA & 1)
          sum ^= a[i];
      crcA = sum;
    }
 
    // switch even and odd
    uint32_t* t = a; a = b; b = t;
  }
 
  // return combined crc
  return crcA ^ crcB;
}

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 359 of file XrdOucCRC32C.cc.

                                     {
    for (unsigned n = 0; n < 256; n++) {
        uint32_t crc = n;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc32c_table_big_byte[n] = crc;
    }
    for (unsigned n = 0; n < 256; n++) {
        uint32_t crc = crc32c_table_big_byte[n];
        crc32c_table_big[0][n] = swap(crc);
        for (unsigned k = 1; k < 8; k++) {
            crc = crc32c_table_big_byte[crc & 0xff] ^ (crc >> 8);
            crc32c_table_big[k][n] = swap(crc);
        }
    }
}

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 286 of file XrdOucCRC32C.cc.

                                        {
    for (unsigned n = 0; n < 256; n++) {
        uint32_t crc = n;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
        crc32c_table_little[0][n] = crc;
    }
    for (unsigned n = 0; n < 256; n++) {
        uint32_t crc = crc32c_table_little[0][n];
        for (unsigned k = 1; k < 8; k++) {
            crc = crc32c_table_little[0][crc & 0xff] ^ (crc >> 8);
            crc32c_table_little[k][n] = crc;
        }
    }
}

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 424 of file XrdOucCRC32C.cc.

                                                              {
    static int const little = 1;
    if (*(char const *)&little)
        return crc32c_sw_little(crc, buf, len);
    else
        return crc32c_sw_big(crc, buf, 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 384 of file XrdOucCRC32C.cc.

                                                                  {
    unsigned char const *next = (unsigned char const *)buf;
 
    pthread_once(&crc32c_once_big, crc32c_init_sw_big);
    crc = ~crc;
    while (len && ((uintptr_t)next & 7) != 0) {
        crc = crc32c_table_big_byte[(crc ^ *next++) & 0xff] ^ (crc >> 8);
        len--;
    }
    if (len >= 8) {
        uint64_t crcw = swap(crc);
        do {
            crcw ^= *(uint64_t const *)next;
            crcw = crc32c_table_big[0][crcw & 0xff] ^
                   crc32c_table_big[1][(crcw >> 8) & 0xff] ^
                   crc32c_table_big[2][(crcw >> 16) & 0xff] ^
                   crc32c_table_big[3][(crcw >> 24) & 0xff] ^
                   crc32c_table_big[4][(crcw >> 32) & 0xff] ^
                   crc32c_table_big[5][(crcw >> 40) & 0xff] ^
                   crc32c_table_big[6][(crcw >> 48) & 0xff] ^
                   crc32c_table_big[7][(crcw >> 56)];
            next += 8;
            len -= 8;
        } while (len >= 8);
        crc = swap(crcw);
    }
    while (len) {
        crc = crc32c_table_big_byte[(crc ^ *next++) & 0xff] ^ (crc >> 8);
        len--;
    }
    return ~crc;
}

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 310 of file XrdOucCRC32C.cc.

                                                                     {
    unsigned char const *next = (unsigned char const *)buf;
 
    pthread_once(&crc32c_once_little, crc32c_init_sw_little);
    crc = ~crc;
    while (len && ((uintptr_t)next & 7) != 0) {
        crc = crc32c_table_little[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
        len--;
    }
    if (len >= 8) {
        uint64_t crcw = crc;
        do {
            crcw ^= *(uint64_t const *)next;
            crcw = crc32c_table_little[7][crcw & 0xff] ^
                   crc32c_table_little[6][(crcw >> 8) & 0xff] ^
                   crc32c_table_little[5][(crcw >> 16) & 0xff] ^
                   crc32c_table_little[4][(crcw >> 24) & 0xff] ^
                   crc32c_table_little[3][(crcw >> 32) & 0xff] ^
                   crc32c_table_little[2][(crcw >> 40) & 0xff] ^
                   crc32c_table_little[1][(crcw >> 48) & 0xff] ^
                   crc32c_table_little[0][crcw >> 56];
            next += 8;
            len -= 8;
        } while (len >= 8);
        crc = crcw;
    }
    while (len) {
        crc = crc32c_table_little[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
        len--;
    }
    return ~crc;
}

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 348 of file XrdOucCRC32C.cc.

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

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 356 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 284 of file XrdOucCRC32C.cc.

Referenced by crc32c_sw_little().

crc32c_table_big

uint64_t crc32c_table_big[8][256]

static

Definition at line 358 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 357 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 285 of file XrdOucCRC32C.cc.

Referenced by crc32c_init_sw_little(), and crc32c_sw_little().