日記帳だ! with Tux on Libserver

二度目の大改造!! 日記帳…か?を継承し、より柔軟でパワフルなBlogに変身しました。

RSSに対応しています。リンク・コメント・トラックバックは自由にしていただいてほぼ問題ありません。
RSS購読方法、僕のリンク・コメント・トラックバックについての考えを読むことをおすすめします。

思っていたCRC32とは少し違う

最近、CRCの計算とかやることがあって……

というかこれからCRCを導入しようとしているところがあって、そのための調査をしてたんだよね。

導入するならCRC32だろうと思ったのだが、詳しく調べてみると、これまで思ってたより複雑だった。


というのも、これまで職場で使ってたCRC32と、僕が想像していたCRC32と、世間的によく使われているCRC32は、それぞれ少しずつ違ったのよね。

これまで、職場で使われているCRC32の計算プログラムを他のシステムに移植したりすることはあったんだが、

その意味について詳しく考えたことはなかったし、世間のCRC32の計算がどうなってるかはあまり気にしてなかった。

だから、いろいろ勘違いがあったというわけ。


そもそもCRCというのは、2進数のわり算の余りのこと。

CRC32の場合、一般的には0x104C11DB7 という33ビットの値でわり算をして、その余りの32ビットの値を使う。

そういう理解はしていたし、職場で主に使われているCRC32も、世間的によく使われているCRC32もこの考えは一緒。

だけど、単純に上に書いた考えで計算した値と、職場で使われているツールで計算したCRC32の値が食い違うんだよね。

ソースコードの途中経過を追うと、かなり最初の方で食い違いがあるらしい。

そこでいろいろ調べてみたのだが、根本的なところに差があった。それは、よく使われるCRC32は右送りだということだ。


CRCの計算では左送りと右送りという考えがある。

普通、コンピュータの計算というのは一番左のビットがMSB、右のビットがLSBと考えて計算する。

CRCの計算もそうだと思ったのだが、この考えは主流ではないらしい。

ちなみにこの方法でのCRC計算はデータを左ビットシフトしながら計算するので、左送りという。

CRCの計算で一般的なのは、右のビットをMSB、左のビットをLSBと考えて計算する方法。

CRCの計算に限っては1バイト単位でMSBとLSBを反転させて計算するのが一般的な方法らしい。

除数(0x104C11DB7)のMSB・LSBを反転させた値を使いながら、データを右ビットシフトしながら計算するので、右送りと呼ばれる。

なぜ右送りが主流なのかというと、シリアル通信ではLSB→MSBの順序でデータを送ることが多いから。

到着したデータから順番に後ろに足して、わり算してというのを繰り返すとすれば、こちらの方が好都合なんだと。


そういう前提が分かれば、逆回しで計算するように書けばよいだけのことである。

これまでのソースコードも見返しながら、右送りで計算するように書くと、職場で使っていたツールの計算結果と一致するようになった。

ただ、その一方で世間でよく使われているらしいCRC32の計算ツールの結果とは食い違うことに気づいた。

なぜ食い違うのかというと、それは世間で使われているCRC32は前と後に追加の処理が入っているからである。

確かに世の中に転がっているサンプルプログラムと、職場でよく使われているCRC32の計算プログラム、

似てるが、前後に差があることに気づいた。


どうも、世間ではCRC32の初期値は0xFFFFFFFFとして計算して、最後にビット反転させるのが一般的らしい。

職場では初期値0x00000000のものしか見たこと無いし、最後のビット反転もしない。

なぜ、初期値を0xFFFFFFFFとするのが一般的なのかというと、

0を初期値にすると0x00が連続するデータに対するCRCがオール0になってしまうからだそう。

そういえば、以前このBlogにも「オール0のデータに対するCRCはオール0になる」ことに由来する事件について書いたな。

一見正しいCRCだけど

これを避けるために初期値を0xFFFFFFFFとすることが一般的になったそう。

最後にビット反転を行う意味はよくわからないが、なんとなく最後も反転させておくかと考えたんだろうか。

ただし、前処理・後処理は誤り検出の能力に本質的な差はないとされている。

オール0のデータに対するCRCがオール0になったとしても、それは運の悪いケースの1つという話だ。


このあたりの事情を調べているときに発見したことがある。

どうもデータの後ろにCRCを付加したデータを作って、それのCRCを計算すると一定のCRCになるという性質があるらしい。

16進数で 01 02 03 04 05 06 07 08 というデータ列があったとする。

これを初期値0xFFFFFFFF、右送りでCRC32を計算し、最後にビット反転すると0x3FCA88C5 という値が得られる。

このCRCはわり算の余りのMSB・LSBを反転して後処理した値なので、全体のMSB・LSBを反転して、

さらにデータ列の順序を踏まえて、計算バイト単位でMSB・LSBを反転すると C5 88 CA 3F というデータ列になる。

すなわち右送りの場合は、計算して得られたCRCをリトルエンディアンで並べ替えて付加すればいいってこと。

こうしてCRCを付加したデータ列のCRC32を同様に計算すると 0x2144DF1C になる。

一見すると意味不明な値だが、これは 00 00 00 00 というデータ列に対して計算したCRC32と一致し、

同様の方法で生成したデータ列に対しては必ず0x2144DF1C というCRCが求まる。


ちなみに最後のビット反転の後処理がない(再反転した)場合、最初のデータ列のCRCは 0xC035773A になる。

これをリトルエンディアンで並べ替えて 3A 77 35 C0 というデータ列を最初のデータ列に付加する。

このデータ列にビット反転の後処理なしのCRC32を計算すると 0x00000000 になる。

そうなんですね。後処理がなければ、綺麗にオール0になるんですね。

原理は上とまったく一緒なんだけど、後処理なしだとオール0になるということの方が本質に近い。

わり算の余りを後ろに付けるってそういうことだから。

CRCを最後に付ける場合にしか適用できないのだけど、当てはまる場合は実装上、シンプルでよい方法かも。


同じ方法で計算するだけならなんとなくで使ってればいいんだけど、

マイコンとデジタル回路とか、複数の方法で計算する場合はその間で整合性がとれる必要がある。

あと、今回は取り上げなかったけど、Intel CPUに内蔵されているCRC32計算命令では、一般的に使われているものと除数が異なるそう。

というわけで、よく理解して使わないと痛い目を見ることもあるって話。

原理が思いのほか複雑だから、ハマってしまうとなかなか手間取ると思うので要注意だなと思った。


Author : hidemaro
Date : 2017/07/20(Thu) 22:31
コンピュータ・インターネット | Comment | trackback (0)

Tools