CRC32の雑多メモ

アルゴリズム的には、ビット幅と生成多項式でバリエーションがあり、バースト誤りを検出しやすい。ハッシュ的ではあるが、改ざんには弱いので、セキュリティ目的では使えない。

実用上は、バースト誤りを検出しやすいことから通信路やバスでの化け検出に使われる。ビット幅・生成多項式ともに、よく使われるものは限られている、特にCRC-32-IEEE 802.3のものが狭い意味でのCRC32と解釈されていて、EthernetとかMPEGとかZIPとかに広く使われている。

このCRC32はRFCによくサンプルプログラムが乗っていて(例えばRFC3309の末尾の方)、下記ヘッダとともにcrc32.cのまま広くコピペされて使われている。

/*************************************************************/
/* Note Definition for Ross Williams table generator would */
/* be: TB_WIDTH=4, TB_POLLY=0x1EDC6F41, TB_REVER=TRUE */
/* For Mr. Williams direct calculation code use the settings */
/* cm_width=32, cm_poly=0x1EDC6F41, cm_init=0xFFFFFFFF, */
/* cm_refin=TRUE, cm_refot=TRUE, cm_xorort=0x00000000 */
/*************************************************************/

ちなみに、仕様上のCRC32は最初と最後で0xFFFFFFFFでXORするが、サンプルプログラムではこれをしていない。Ubuntuにはcrc32の名前のプログラム(というかPerlサンプルスクリプトというか)が入ってるので、これの結果と比べてみるのがよい。

ただ、今時の32bitのCPU(ARM cortex-Aとか)だと実はこのままでは遅い。どうせコピペするならzlibのcrc32.cあたりから持っていったほうがよい。1byteでwhileループを回しているとこを、4byteのループアンローリング込みにしていて、手元計測でおおむね40-50%くらいの実行時間になった。zlibなので「zlibからコピペして使った」と書きつつzlibライセンス文のコピーを載せとけば著作権的にも問題ない。

x86系CPUでは、SSE4.2よりcrc32c命令が加わっている。上記の広く使われているCRC32ではなくてiSCSIとかに使われているものではあるものの、専用命令を使えばさらに高速に処理できる。c++ - Implementing SSE 4.2's CRC32C in software - Stack Overflow

AESも専用命令が作られたりと、汎用コンピューティング性能が上がらない今日では、ソフトの実装で最適化するにも限界があるので、どうせソフト対応入れるならこういう方向専用命令使ったasm化がトレンドなのかもしれない。

ちなみに、zlibやってるとよく見かける「Adler-32」は、zlib作者の1人のマーク・アドラーさんの名前らしい。カッシーニとかマーズ・エクスプレスとかに関わっているそっちの人ということらしい。

※ 2017/02/22(Wed)追記:
CRC32のベンチマークに特化したサイトがある。そこにある「git clone http://create.stephan-brumme.com/crc32/.git」はgitレポジトリがなかったのはご愛敬として、サンプルをベンチマークしてみた結果、
● x86_64だと、「16 bytes at once」は確かに早い(最速)。zlibやつは「16 bytes at once」よりは遅いが「8 bytes at once」よりは早い
● arm64だと、「16 bytes at once」も「8 bytes at once」とあまり変わらず。zlibやつの方が早い。
となった。zlibのは固定テーブルをconst参照するから最適化が効きやすいんだろうか。ちなみにzlibのはアルゴリズム的には「Slicing-by-4」でいいみたい。というわけで、zlibのをコピペするのが安心でオススメ。

このブログ記事について

このページは、らるるが2017年1月30日 00:01に書いたブログ記事です。

ひとつ前のブログ記事は「Googleで日本語以外を検索する方法」です。

次のブログ記事は「「天使に教わる勝ち残るプロマネ」読んだ」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ

ウェブページ

Powered by Movable Type 7.9.0