CRC on C++11

「Ｃ言語による最新アルゴリズム辞典」の CRC の項目を見ると CRC32 と CRC16 がほぼ同じに見えた。 そこで、共通部分を括り出してみようと C++ で書き始めたところ、補助テーブルの生成はコンパイル時に終えてしまいたいという欲が出てきた。

そのため、初めて C++11 の機能を使ったコードを書いた。 初めての記念にブログに残すことにする。

コンパイル結果を眺めた感じではちゃんとコンパイル時に配列が生成できているように見えるけれど、本当にこれで正しいのかあまり自信はない。

// crc.h
uint_least32_t crc32(int n, unsigned char c[], uint_least32_t start=0xFFFFFFFFUL);
uint_least16_t crc16(int n, unsigned char c[], uint_least16_t start=0xFFFFU);

// crc.cpp
#include <climits>
#include <cstdint>
#include <array>
using namespace std;

template<class T, T poly>
constexpr T crc_table_element(T r, unsigned int j=0) {
  return j<CHAR_BIT ? crc_table_element<T, poly>(r&1 ? (r>>1)^poly : r>>1, j+1) : r;
}

template<class T, T poly, unsigned int count, bool flag>
struct make_crc_table_helper;
 
template<class T, T poly, unsigned int count>
struct make_crc_table_helper<T, poly, count, false> {
  template<typename ... U>
  constexpr static array<T, UCHAR_MAX+1> invoke(U ... args) {
    return make_crc_table_helper<T, poly, count+1, (count==UCHAR_MAX)>::invoke(args..., crc_table_element<T,poly>(count));
  }
};

template<class T, T poly, unsigned int count>
struct make_crc_table_helper<T, poly, count, true> {
  template<typename ... U>
  constexpr static array<T, UCHAR_MAX+1> invoke(U ... args) {
    return array<T, UCHAR_MAX+1>{args ...};
  }
};

template<class T, T poly>
constexpr array<T, UCHAR_MAX+1> make_crc_table(void) {
  return make_crc_table_helper<T, poly, 0, false>::invoke();
}

template<class T, array<T, UCHAR_MAX+1>& table, T def>
T crc(int n, unsigned char c[], T start=def) {
  T r=def;
  while (--n >= 0)
    r = (r >> CHAR_BIT) ^ table[(unsigned char)(r&0xFF) ^ *c++];
  return r^def;
}

#define CRCPOLY32 0xEDB88320UL
#define CRCPOLY16 0x8408U

auto crc32_table = make_crc_table<uint_least32_t, CRCPOLY32>();
auto crc16_table = make_crc_table<uint_least16_t, CRCPOLY16>();

uint_least32_t crc32(int n, unsigned char c[], uint_least32_t start) {
  return crc<uint_least32_t, crc32_table, 0xFFFFFFFFU>(n, c);
}

uint_least16_t crc16(int n, unsigned char c[], uint_least16_t start) {
  return crc<uint_least16_t, crc16_table, 0xFFFFU>(n, c);
}

一応、使用例も載せておこう。

#include <cstdio>
#include <cstdint>
#include "crc.h"
using namespace std;

int main(void) {
  static unsigned char s[] = "Hello, world!";

  printf("crc16(%s) = %04X\n", s, crc16(13, s));  // => 1EB5
  printf("crc32(%s) = %08lX\n", s, crc32(13, s)); // => EBE6C6E6
  return 0;
}

もう少し綺麗に書けそうな気もしなくもないが、今の私ではこれが精一杯な感じ。

Document ID: 6b48715bf9dc960a83e5cd2d581f4b56