Primitive Technology という YouTube チャンネルに触発されて、プログラミングの世界でゼロから何かを実装したくなった。実装をできる限り単純化して、何も見なくても書けるようなコード片を作ることが目標である。
今回は CRC32 (Section 8 of RFC 1952) を実装する。完成品は以下である。Go 言語で 10 行で書けた。
func crc32(b []byte) uint32 {
u := uint32(0xffff_ffff)
for _, b := range b {
u ^= uint32(b)
for i := 0; i < 8; i++ {
u = u>>1 ^ 0xedb8_8320*(u&1)
}
}
return u ^ 0xffff_ffff
}
fmt.Printf("%08x\n", crc32([]byte{0x0a})) が 32d70693 を出力するので、この実装は正しい。
$ crc32 <(echo)
32d70693
解説の余地もないと思うが一応。元のコードでは大きさ 256 のテーブルを作っているが、これは高速化のためだけのものであり実質的には rev(b[0]) || rev(b[1]) || ... というビット列を GF(2) の多項式とみなして 1 << 32 | rev(0xedb8_8320) を多項式とみなしたもので割った余りをとっているだけである。(0xffff_ffff で xor をとるパートは非本質だが、なぜか含まれているので実装しないわけにはいかない。) それを素直に実装するとこうなる。実行速度は相当遅いはず。
(rev はビット列を反転させる関数である。ビット長は文脈で判断していただきたい。)
コードは https://go.dev/play/p/IieRIVzVIVK にある。