CRC32 Implementation

CRC32 値の計算で除数に 0x4C11DB7、生成多項式に

$$ x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 $$

を使うのが性能が良いらしい。

生成多項式の各次数は (1 << 32) | 0x4C11DB7 を 2 進数にした 1 0000 0100 1100 0001 0001 1101 1011 0111 の 33 bits で値が 1 の桁を取り出したものに相当している。

CRC32 の C での実装例は PNG の RFC にあり、C++ だと例えば以下のようになる。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <cinttypes>

typedef unsigned long* CRCTable;

void makeCRCTable(CRCTable table)
{
  for (auto n = 0; n < 256; n++) {
    auto c = static_cast<unsigned long>(n);

    for (auto k = 0; k < 8; k++) {
      if (c & 1) {
        c = 0xedb88320L ^ (c >> 1);
      } else {
        c = c >> 1;
      }
    }
    table[n] = c;
  }
}

unsigned long updateCRC(CRCTable table, unsigned long crc, const std::vector<unsigned char>& buf)
{
  unsigned long c = crc;
  
  for (std::size_t n = 0, len = buf.size(); n < len; n++) {
    c = table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
  }

  return c;
}

unsigned long computeCRC32(const std::vector<unsigned char>& buf)
{
  static unsigned long table[256];
  static bool isComputed = false;

  if (!isComputed) {
    makeCRCTable(table);
    isComputed = true;
  }
  
  return updateCRC(table, 0xffffffffL, buf) ^ 0xffffffffL;
}

int main( void )
{
  using namespace std;

  vector<unsigned char> buf
    {
     0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39
    };

  auto crc = computeCRC32(buf);

  printf("0x%llx\n", crc);
  
  return 0;
}

Comments

comments powered by Disqus