CRC32 のテーブルを利用した最適化のメモ
解決したこと
CRC32 を計算するプログラムをテーブルを利用して最適化する場合の個人的な引っ掛かりポイントについて再確認しました。
- 元々の手順とテーブル利用の関連付け
- データテーブルの計算方法
環境
- Windows 10
- Visual Studio 2019
解決方法?
CRC32 そのものについての説明はこちらのスライド を参考にしました。
まずはスライドの説明に沿って実際にビット演算を手計算しました。
例えば入力データが文字'a' の場合
- 'a' = 0x61 = 01100001 =[ビット順序反転]=> 10000110
- 後ろに0 を32 bit 付加して1000011000000000000000000000000000000000
- 先頭32 bit を反転して0111100111111111111111111111111100000000
- 多項式は100000100110000010001110110110111
- シフトとxor の繰り返し
input :0111100111111111111111111111111100000000
polynomial: 100000100110000010001110110110111
xor result:0011100011001111101110001001001011000000
polynomial: 100000100110000010001110110110111
xor result:0001100001010111100110110010010000100000
polynomial: 100000100110000010001110110110111
xor result:0000100000011011100010101111111101010000
polynomial: 100000100110000010001110110110111
xor result:0000000000111101100000100001001011101000
入力データのMSB が32 bit より下位になったので終了しビットを反転
xor result:--------00111101100000100001001011101000
=>:--------11000010011111011110110100010111
- 結果のビット順序を反転した値の16 進数は0xe8b7be43
- python のcrc32 と同じ結果になることを確認する
ひっかかりポイント
CRC32 の説明などでしばしば「ビット順序の反転」が出てきますが、ここがよく理解できていなかったのがポイントでした。
C++ で任意の長さのデータを取り扱う場合は主に1 byte の基本型であるchar やuint8_t の配列として取り扱います。例えば入力データが"abcd" という長さ4 の文字列の場合、これをC++ 的に素直に表現すると
'a', 'b', 'c', 'd' = 0x61, 0x62, 0x63, 0x64 => 0110 0001 0110 0010 0110 0011 0110 0100
となります。これは、1 byte ごとに2 進数にして並べたものです。
ここで1 byte 中のビットの順序について考えてみます。'a' でいうと上位←0110 0001→下位 ですが、上位ビットと下位ビットはどちらが先なのか？ というとリトルエンディアンでは下位ビットが先、ビッグエンディアンでは上位ビットが先、となります。これについては構造体のビットフィールドで確認することができます。
struct Data { union { uint8_t bit : 1; uint8_t value; }; }; Data d; std::memset(&d, 0, sizeof(Data)); d.bit = 1;
とした場合、d.value の値はリトルエンディアンだと0x01, ビッグエンディアンだと0x80 となります。
これを踏まえて改めて入力データ"abcd" をビットの入力順に2 進数表現する場合、リトルエンディアンであれば各1 byte については下位ビットから並べることになります。
'a', 'b', 'c', 'd' = 0x61, 0x62, 0x63, 0x64 => 1000 0110 0100 0110 1100 0110 0010 0110
C++ プログラム中で入力データのbyte 配列に手を加えなくても、modulo 2 の計算に対する入力としてビット列の先頭を最上位ビットとして扱うことで、ビット順序が反転したように見えます。実際にはプログラム・メモリ上の上位ビット方向とmodulo 2 計算上の上位ビット方向が逆であるということです。
プログラム実装時に使用する最上位ビットを省略した多項式は00000100110000010001110110110111 ですが、このときの上位ビット方向はmodulo 2 計算上のものであり、C++ プログラム上でのバイト列としての表現は0010 0000 1000 0011 1011 1000 1110 1101 => 0x20, 0x83, 0xb8, 0xed となります。リトルエンディアンでの32 bit 値とする場合には先に来るバイトが下位になるので0xedb88320 です。
以上の、プログラム・メモリ上のビット順序とmodulo 2 計算時のビット順序の対応 について理解することで計算処理の各操作が何をしているのかもよくわかるようになりました。
データテーブルの計算方法
CRC32 計算の最適化用に作成するデータテーブルの内容は、8 bit のパターンごとに後続の32 bit に適用される多項式のxor を先に計算しておいたものです。modulo 2 で上位から下位に向けて1 のビットを見つけてxor を行う操作で、プログラム上では逆に下位ビットから処理することになります。
uint32_t table[256]; // x^32 を省略した多項式 const uint32_t polynomial = 0xedb88320; // テーブル各要素を計算 for (uint32_t i = 0; i < 256; ++i) { // xor 初期値 uint32_t xor = 0; // 入力データ uint32_t input = i; // 8 bit を処理 for (uint32_t j = 0; j < 8; ++j) { // ビットがたっていたら if (input & (1 << j)) { // 入力データにxor 適用 // ビットがたっているのは多項式のx^32 に対応する位置 // xor をとるのはその次からなのでi + 1 でシフトする input ^= (polynomial << (i + 1)); // 後続データに対してのxor // i = 0 の時には後続32 bit の先頭から見て // polynomial はmodulo 2 の計算上で7 bit 上位になる // プログラム上では下位に7 bit はみ出していることになる xor ^= (polynomial >> (7 - i)); } } // 結果をテーブルに収める table[i] = xor; }
その他
github にコードをコミットしました。
