とりあえず、CRC値を計算するためのコードを示す。
CRCを計算するフリーソフト2つと出力が一致したので、多分あってると思う。
#include <cstdio> class CRC32 { unsigned long table[256]; public: unsigned long calc(void *d, int len) { unsigned char *c = (unsigned char *)d; unsigned long x = 0xffffffff; for (int i = 0; i < len; i++){ x = (x >> 8) ^ table[(x & 0xff) ^ c[i]]; } return x ^ 0xffffffff; } CRC32() { const unsigned long poly = 0xedb88320;//CRC-32-IEEE 802.3 for (int i = 0; i < 256; i++){ unsigned long x = i; for (int j = 0; j < 8; j++){ unsigned long t = x & 1; x >>= 1; if (t) x ^= poly; } table[i] = x; } } }; int main(){ CRC32 crc; printf("%x\n", crc.calc("abcd", 4)); return 0; }
データを長桁数の数と見て、それをある数で割った余りを計算してチェックサムとする。
その割る数は、ここでは0x104c11db7（32bitではギリギリ表せない）で、
ソースコード中にある定数0xedb88320は、その下位32bitである0x04c11db7の
ビットリバース（2進数で表現して逆に読む、1011を1101にするみたいに）。
ここで使う数や除算は普通のものとは異なる。
数は多項式のようなもの、除算はモジュロ2で行う。
やり方はWikipediaのCRCの計算のようにする。
中学校で、多項式を筆算で割り算したあの感覚を思い出すとわかりやすい。
上のコードでは、まずコンストラクタで0x0*0x100000000から0xff*0x100000000の
256個について、余りを計算している。
ここでは、最下位ビットが「数」の最上位の桁としている（だからビットリバースした）。
x >>= 1;で「最上位の桁」が消えるが、それが1だったときだけ、xorをかけている。
（普通の筆算の割り算で、商に1が立てば除数を引くが、0ならそのまま下ろすのと同じ）
こうして得た32bitの「余り」を配列（テーブル）に保存しておく。
同じように1bitずつ計算していけばデータ全体のCRC値も求まるのだが、
テーブルを使って1byteずつ処理できるようにしている（バイト毎ならコーディングもしやすい）。
テーブルを作ったら、あとはひたすら上位（アドレス上では下位）8bitを消していく。
処理内容がビッグエンディアン的なので非常にわかりにくいが、特に変なことはしていない。
x & 0xffとして「上位」8bitを取り出し、残っている最上位1byteのc[i]と合成して余りを求める。
そうして処理した8bitをx >> 8として消し、xorして合成すれば、処理が1byteぶん進んだことになる。
ここではxの初期値が0xffffffffで、更に最後には0xffffffffとxorしている。
これは、データの上位4byteを反転し、更にデータの末尾へ0xffffffffを追加するということ。
出力データの挙動が本質的に変わるわけではないので、そういう仕様だと思っておけばいい。
x = (x >> 8) ^ table[(x & 0xff) ^ c[i]];という行がメインの処理となるが、
これを1命令でやってくれるのが、SSE4.2で追加されたCRC32だ。
CRC32 x, c[i] という感じに書ける（テーブルはいらないし、1〜8byteずつ処理できる）。
ただし、上のソースでの割る多項式は0x104c11db7だったが、CRC32命令では0x11edc6f41固定。
参考にしたURL
http://kone.vis.ne.jp/diary/diaryb07.html
http://ameblo.jp/cpp-prg/entry-10227924329.html
