view release on metacpan or  search on metacpan

uulib/crc32.c  view on Meta::CPAN

            }
          else
            {
              uint32_t one   = *current++ ^ ecb_bswap32(crc);
              uint32_t two   = *current++;
              uint32_t three = *current++;
              uint32_t four  = *current++;
              crc = crc32_lookup[ 0][ four         & 0xFF] ^
                    crc32_lookup[ 1][(four  >>  8) & 0xFF] ^
                    crc32_lookup[ 2][(four  >> 16) & 0xFF] ^
                    crc32_lookup[ 3][(four  >> 24) & 0xFF] ^
                    crc32_lookup[ 4][ three        & 0xFF] ^
                    crc32_lookup[ 5][(three >>  8) & 0xFF] ^
                    crc32_lookup[ 6][(three >> 16) & 0xFF] ^
                    crc32_lookup[ 7][(three >> 24) & 0xFF] ^
                    crc32_lookup[ 8][ two          & 0xFF] ^
                    crc32_lookup[ 9][(two   >>  8) & 0xFF] ^
                    crc32_lookup[10][(two   >> 16) & 0xFF] ^
                    crc32_lookup[11][(two   >> 24) & 0xFF] ^
                    crc32_lookup[12][ one          & 0xFF] ^
                    crc32_lookup[13][(one   >>  8) & 0xFF] ^
                    crc32_lookup[14][(one   >> 16) & 0xFF] ^
                    crc32_lookup[15][(one   >> 24) & 0xFF];
            }
        }

        len -= bytes_at_once;
    }

    const uint8_t* current_char = (const uint8_t*) current;
    /* remaining 1 to 15 bytes (standard algorithm) */
    while (len-- != 0)
        crc = (crc >> 8) ^ crc32_lookup[0][(crc & 0xFF) ^ *current_char++];

    return ~crc;
}

/* merge two CRC32 such that result = crc32(dataB, lengthB, crc32(dataA, lengthA)) */
uint32_t uu_crc32_combine(uint32_t crcA, uint32_t crcB, size_t lengthB)
{
  int i;
  /*
   * 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;

  /* CRC32 => 32 bits */
  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] = Polynomial;
  for (i = 1; i < CrcBits; i++)
    odd[i] = 1 << (i - 1);

  /* put operator for two zero bits in even */
  /* same as gf2_matrix_square(even, odd); */
  for (i = 0; i < CrcBits; i++)
  {
    int j;
    uint32_t vec = odd[i];
    even[i] = 0;
    for (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 (i = 0; i < CrcBits; i++)
  {
    int j;
    uint32_t vec = even[i];
    odd[i] = 0;
    for (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 (i = 0; i < CrcBits; i++)
    {
      int j;
      uint32_t vec = b[i];
      a[i] = 0;
      for (j = 0; vec != 0; j++, vec >>= 1)