もどる

CRCの計算方法

スクリプトに実装するためにCRCの計算が必要になったので色々と調べてみたんですがどこも小難しい理論ばかりで・・・　割り算を使うらしいとかの程度しか知識が無かったんですが、いろんなページを回って結局わかるんですが、どうやって実装する??　と考えるとかえって分からなくなる始末(;_;)　なんとか「やり方」がわかったので、ここに書き留めておきます。

CRCとは主に通信中の誤りを検出する手段として使われていて、なにやら凄い精度で検出できるそうです。（苦手なデータもありますが）
おまけに、これをハードウェアで実装するのがすごく簡単なのでまた広く使われるそうです。

その理論は専門のページをみてもらうとして、実際の実装を分かりやすく紹介してみたいと思います。逆に、リストだけ載ってるページもあるんですが、最初からチューンされたリストを見てもアルゴリズムがわかりにくいので・・・(^_^;

PerlやCの分かる人は以下の例を見ただけで自分で実装できると思います。

sub crc{
	local($crc)=shift;
	local($data)=shift;

	for ($count=8; $count>0; $count--){
		$crc=$crc<<1;
		$c=$crc & 0xffff;
		if ($crc & 0x10000){
			$crc=$c^0x18003;	# CRC-16
#			$crc=$c^0x11021;	# CRC-CCITT
		}
		$crc=$crc&0xffff;
		$data=$data<<1;
		if ($data & 0x100){
			$crc=$crc^1;
		}
	}
	return($crc);
}

CRCのことを調べていると「生成多項式」という数学用語(??)が出てきますが、それを固定的な定数にしてしまったのがリスト中に出てくる「0x18003」や「0x11021」とう数値です。

これは、以下の式により導き出されます。

アルゴリズム的にはこうです。

1. データを一つ（１バイト）とってきます
2. CRC値を左ビットシフトして、桁上がりがあればさらに生成多項式とXORを取ります
3. データを左ビットシフトして、桁上がりがあればCRC値と1のXORを取ります
4. あと7回（1バイト＝8ビットなので）2と3を繰り返します
5. 残りのデータがあれば1に戻ります

CRC値を16ビットで扱う場合は2¹⁶は桁あふれを起こしてしまうので元から計算せず、生成多項式は8003hや2021hを使用しても良いようです。

で、最適化したのが次。私の力量じゃここまでです(^_^; CRC-16を使用して、CRC値は16ビットです。

sub crc{
	local($crc)=shift;
	local($data)=shift;

	$count=8;
	while ($count--){
#		$crc=$crc^0x1021 if ($crc<<=1)&0x10000;	# CRC-CCITT
		$crc=$crc^0x8003 if ($crc<<=1)&0x10000;	# CRC-16
		$crc=$crc^1 if ($data<<=1)&0x100 ;
	}
	return($crc&0xffff);
}

文字列に特化させてみました

sub crcc{
	local($data)=shift;

	local($crc, $p, $d);
	local($len)=length($data);
	while ($len--){
		$d=ord(substr($data, $p++, 1));
		$count=8;
		while ($count--){
#			$crc=$crc^0x1021 if ($crc<<=1)&0x10000;	# CRC-CCITT
			$crc=$crc^0x8003 if ($crc<<=1)&0x10000;	# CRC-16
			$crc=$crc^1 if ($d<<=1)&0x100 ;
		}
	}
	return($crc&0xffff);
}

・・・どんな感じでしょか??(^_^;

2001.11.17 Misaki

</HTML>