带查找表的crc32

Question

// --已编辑

目前，硬件函数(__builtin_ia32_crc32qi和__builtin_ia32_crc32di)用于crc32，__builtin_ia32_crc32di返回64位。然后，将64位修剪为32位。现有数据就是基于这个逻辑的。https://gcc.gnu.org/onlinedocs/gcc-4.9.2/gcc/X86-Built-in-Functions.html

uint32_t calculateCrc32(uint32_t init, const uint8_t* buf, size_t size) {
  uint32_t crc32 = init;
  const uint8_t* pos = buf;
  const uint8_t* end = buf + size;

  // byte-wise crc
  while (((uint64_t)pos) % sizeof(uint64_t) && pos < end) {
    crc32 = __builtin_ia32_crc32qi(crc32, *pos);
    ++pos;
  }

  // 8-bytes-wise
  while (((uint64_t)pos) <
         (((uint64_t)end) / sizeof(uint64_t)) * sizeof(uint64_t)) {
    crc32 = __builtin_ia32_crc32di(crc32, *(uint64_t*)pos);
    pos += sizeof(uint64_t);
  }

  // byte-wise crc for remaining
  while (pos < end) {
    crc32 = __builtin_ia32_crc32qi(crc32, *pos);
    ++pos;
  }

  return crc32;
}

我正在尝试实现一个查找表版本。我所做的是: 1)首先生成一个查找表2)进行表查找

uint8_t kCrc32tab[256];
for (int i=0; i < 256; ++i) {
  uint8_t buf = i;
  kCrc32tab[i] = calculateCrc32(0xFF, &buf, 1);
} 

uint32_t crc32WithLookup(uint32_t crc32_init, const uint8_t* buf, size_t size) {
   uint32_t crc32 = crc32_init;
   for (std::size_t i = 0; i < size; i++) {
        uint8_t key = (crc32 ^ buf[i]) & 0xFF;
        crc32 = kCrc32tab[key] ^ (crc32 >> 8);
    }
    return crc32;
}

然而，crc32WithLookup和calculateCrc32的crc32结果是不同的。有什么建议吗？

redis中的查找示例：https://github.com/redis/redis/blob/unstable/src/crc16.c

Answer 1

该CRC-32通常被称为CRC-32C (在所提供的代码之外，初始值和最终异或是0xffffffff)。

您的代码中有两个错误。该表必须为32位值，并且CRC的初始值为零。所以你需要uint32_t kCrc32tab[256];和kCrc32tab[i] = calculateCrc32(0, &buf, 1);。

This answer为硬件和软件版本的CRC计算提供了更高级和更快的代码。