CRC (Cyclic Redundancy Check, 巡回冗長検査)は、いろいろなデータフォーマットでデータの整合性を確認するために使われる誤り検出符号のひとつであるが、ひとくちにCRCといってもいろいろ実装にバリエーションがあるようなので、備忘録として残す。
・CRCの基本
CRCは、巡回冗長検査などと大仰な名前がついているが、端的にいうと割り算の「あまり」である。ただし、単なる割り算のあまりではなく、多項式の割り算で、しかも係数は\(\mod 2\) したものを考える(つまり0か1しかない)。数学的にはなんか位数が2のベキの有限体\(GF(2^n)\)が云々みたいな感じなのだが、そういう厳密な話は数学が専門の人にお任せする。
多項式の四則演算が普通の四則演算と何が違うのかというと、繰り上りと繰り下がりがないということである。例えば多項式 \(x\) をどんだけ足しても引いても、次数が違う \(1\) とか \( x^2, x^3,\dots\)になることはないということである。そして各々の次数の係数は2で割ったあまりなので、結局、多項式の足し算・引き算はどちらも、各々の次数の係数を各ビットで表したときのビット毎の排他的論理和(XOR)になることがわかる。ビット毎のXORでは自分自身とのXOR \(X\oplus X\) は必ず\(0\)で、 自分自身が反対元 \(X=-X\) になるからである。
zlibとかpngとかで使われているCRC-32は生成多項式( "割る数" )が32次の多項式で
$$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 00000100 11000001 00011101 10110111で、16進数にすると0x104c11db7になる。一番上の桁が1なのは当たり前なのでこれを省略して0x04c11db7と書くことが多い。
・じゃあ割り算してみる
要は普通の引き算のかわりにXORを使って割り算の筆算をすればその余りがCRCになりますよ、ということなので、愚直に割り算してみる。
適当なデータ列、たとえばabcdef = 0x61 0x62 0x63 0x64 0x65 0x66を先に示した生成多項式で割ってみる。ちょっと長いが、
) 01100001 01100010 01100011 01100100 01100101 01100110
1000001 00110000 01000111 01101101 11 . .
------------------------------------ . .
100000 01010010 00100100 00001001 10 . .
100000 10011000 00100011 10110110 111 . .
------------------------------------ . .
11001010 00000111 10111111 010 . .
10000010 01100000 10001110 11011011 1 .
------------------------------------- .
1001000 01100111 00110001 10011110 1 .
1000001 00110000 01000111 01101101 11 .
------------------------------------- .
1001 01010111 01110110 11110011 00 .
1000 00100110 00001000 11101101 10111 .
------------------------------------- .
1 01110001 01111110 00011110 10011 .
1 00000100 11000001 00011101 10110111
-------------------------------------
01110101 10111111 00000011 00101001となって、CRCの値は0x75bf0329になった。
では既存のライブラリで合ってるか確かめてみよう。例えばPythonならbinascii.crc32関数が使える。
>>> import binascii
>>> "0x%x" % binascii.crc32(b"abcdef")
'0x4b8e39ef'？？？
違う値が出てきた。なぜだろう？
・罠① 末尾のゼロパディング
まず1つ目の罠は、往々にしてほとんどの実装では、計算される対象のデータ列の末尾に4バイトのゼロパディングが行われることである。つまり入力データが 0x61 0x62 0x63 0x64 0x65 0x66だとすると、割られる数は実際には0x61 0x62 0x63 0x64 0x65 0x66 0x00 0x00 0x00 0x00になっているということである。
これをやる理由は2つくらい考えられる。
1つ目は、入力自体が4バイト未満だと入力が生成多項式より小さいので、余りが入力そのものになってしまうということだが、そのくらい入力が短いとチェックサムもクソもないのでは？と思わないでもない。
2つ目は、ゼロパディングした部分にCRCの計算結果を放り込めば、そのCRCがくっついたデータ列に対するCRCは必ずゼロになるという検証時の利便性があることである。普通の割り算では \(a\) を \(b\) で割った余りが \(r\) のとき \(a-r\) は \(b\) で割り切れるが、前述の通りXORでは和と差は同じものなので、\(a\oplus r\) が \(b\) で割り切れることになる (\(a\) = ゼロパディングした入力、\(b\) = 生成多項式、\(r\) = CRCの計算結果)。ただ逆に検証時にはパディングしてはいけないので、CRC側の実装としてパディングを含めるのはいかがなものかと思ってしまう。実際、ほとんどのライブラリではパディングの有無を選択できないので、この利便性を享受することはできない。
・罠② ビット順序 (reflect)
これはハードウェア的な都合なのか実装上の利便性なのかわからないが、各バイトの最上位ビットではなく最下位ビットから割っていく実装があるようである。つまり例えば入力データ0x61 0x62 0x63 0x64 0x65 0x66に対するCRCを求めるときに、各バイトのビット順序が逆転(reflected)した0x86 0x46 0xc6 0x26 0xa6 0x66を割った余りを返すということである。あるいは入力のビット順はそのままでバイト順を逆にして「右から」割っても同じことである。
01100110 01100101 01100100 01100011 01100010 01100001 (
. . 1 11011011 01110001 00000110 01000001
. . -------------------------------------
. . 0 10111111 00010010 01100100 001
. . 111011 01101110 00100000 11001000 001
. . -------------------------------------
. . 011111 11010001 00110010 101011
. 111 01101101 11000100 00011001 000001
. -------------------------------------
. 001 00110010 00010101 00101011 10101
. 1110 11011011 10001000 00110010 00001
. -------------------------------------
. 111111 10100110 01110100 01100110 101
. 111011 01101110 00100000 11001000 001
. -------------------------------------
. 010100 10000111 10111101 11010001 1
11101101 10111000 10000011 00100000 1
-------------------------------------
10111001 00111111 00111110 11110001 この場合は生成多項式も左右逆転した0xedb88320と表すことが多いようである。さらに余りも逆転して出力するかどうかで分かれる。「右から」割る実装だと出力はすでに逆転したものが出てくる。
・罠③ ビットマスク
入力を係数列としてみる都合上、先頭にゼロが連続するようなケースだとゼロの個数が変化しても結果のCRCが変わらない。これを防ぐためか、入力の先頭4バイトにビットマスクをかける実装があるようである。0xffffffffをXORして先頭4バイトを全部反転させるものがほとんどである。例えば入力データ0x61 0x62 0x63 0x64 0x65 0x66に対するCRCを求めるとすると、先頭4バイトが反転した0x9e 0x9d 0x9c 0x9b 0x65 0x66を割った余りを返す。また、そのような実装では余りに対してもビットマスクをかけることが多い(必要性はわからない)。
・罠④ そもそも生成多項式が違う
CRC-32では0x04c11db7を使うことが多いが、0x1edc6f41 (CRC-32C)とか 0x741b8cd7 (CRC-32K)とか、そもそも生成多項式が違う変種が存在するので、よく確認する必要がある。
・改めて計算しなおしてみる
「一般的なCRC-32」は罠①～③をすべて備えたものを指すことが多い。つまり、入力の末尾に4バイトのゼロパディングを行い、先頭4バイトに0xffffffffをXORして反転させ、ビット順序を逆転させてから割り算をし、余りのビット順序も逆転させ、最後に0xffffffffをXORしたものを出力するということである。なんで？
長すぎてはみ出るので載せなかったが、ともかくこの条件で割り算をすると、確かに既存のライブラリと同じ 0x4b8e39efが得られることが分かった。
もうちょっと呼び分けを考えてほしいところではある。