CRCの作成について
あつし
どこのニュースグループに投稿してよいか分からなかったので、とりあえず
こちらに投稿させていただきました。適切なグループがありましたら、ご指摘くださ
い。
よく、HDLC手順等で採用されているメッセージの正常性チェックに、CRCという方式
が存在しますが、この生成方法は、具体的にはどうすればよいのでしょうか?
ものの本を読んでも、高次の生成多項式を云々・・・・と書いてあって、どうやって
実装
してよいのかわかりません。
通常はHWで自動的に計算して電文につけるものだと思うのですが、ある事情で、
電文のCRCを自前で作らなければならない状況になってしまいました。
あるホームページ(学生さんの研究発表のようなものでしたが・・)では、1文字のCRC
生成例(Cのソースでした)はあったのですが、それを、電文長分だけ単順に足してい
けば良いのか、わかりません。
そもそもCRCのチェック方法が理解できてない(^^;文系プログラマな私ですが、何と
ぞ
ヒントをお教えください。
ちなみに、ビットシフト、ビット演算等は理解できますが、多項式を云々、という数
学的
な内容になるとからきしダメです。
小島 淳志 oj...@a1.mbn.or.jp
oomoto ryuuji
あつし wrote:
> よく、HDLC手順等で採用されているメッセージの正常性チェックに、CRCという方式
> が存在しますが、この生成方法は、具体的にはどうすればよいのでしょうか?
> ものの本を読んでも、高次の生成多項式を云々・・・・と書いてあって、どうやって
> 実装
> してよいのかわかりません。
> 小島 淳志 oj...@a1.mbn.or.jp
多項式とは 0xedb88320L のことです。演算はビットシフト＋排他的論理和で
す。
後は１バイトづつ読みながらＣＲＣを更新していってデータの最後に書いてある
オリジナルのＣＲＣと比較するだけです。
#include <stdio.h>
#define FAST_CRC
FILE *fi;
main(argc,argv)
int argc;
char *argv[];
{
int size;
if((fi = fopen(argv[1],"rb")) == NULL) {
printf("can not open file1 for input\n");
exit();
}
size = fgetc(fi);
size |= fgetc(fi)<<8;
crc_check(size);
}
crc_check(size)
int size;
{
unsigned long c,crc,pol,table[256];
int i,j,k,d;
pol = 0xedb88320L;
for(i=0;i<256;i++) {
c=i;
for(k=0;k<8;k++) {if(c & 1) c=(c>>1)^pol; else c >>= 1;}
table[i]=c;
}
c = 0xffffffffL;
while(size) {
d=getc(fi);
if(d == EOF) {printf("EOF\n");exit();}
#ifdef FAST_CRC
/* fast CRC(use table) */
c = table[((int)c ^ d) & 0xff] ^ (c >> 8);
#else
/* original CRC */
for(j=0;j<8;j++) {
if(((d >> j)^c) & 1) c=(c>>1)^pol; else c >>= 1;
}
#endif
size--;
}
c ^= 0xffffffffL;
crc=0;
for(i=0;i<4;i++) crc=(crc<<8) | fgetc(fi);
if(c != crc) {printf(":error\n");exit();}
printf(":ok\n");
}
------------
大本隆二
------------
NAKAMURA Takahiro
あつし <oj...@a1.mbn.or.jp> wrote:
>
> 通常はHWで自動的に計算して電文につけるものだと思うのですが、ある事情で、
> 電文のCRCを自前で作らなければならない状況になってしまいました。
>
使用したい生成多項式はどんなのでしょう？
生成多項式がCRC-CCITT方式であればCソースがITU-TのホワイトブックG3/G4ファ
クシミリ関連勧告集(勧告T.0-T.563)に載ってたはずです。
確かテーブル参照と多少の演算で求められるんじゃなかったかな。
一般の書店では売ってないと思うので新日本ITU協会に問い合わせするといい
と思います。
他の生成多項式の場合は分かりません（1ビットずつまじめに計算する方法な
らば思いつきますが）。
--
NAKAMURA Takahiro
NAKAMURA Takahiro
At Thu, 09 Sep 1999 20:53:06 +0900,
NAKAMURA Takahiro <nakam...@tch.sharp.co.jp> wrote:
>
> 生成多項式がCRC-CCITT方式であればCソースがITU-TのホワイトブックG3/G4ファ
> クシミリ関連勧告集(勧告T.0-T.563)に載ってたはずです。
>
嘘ついた。今見直してみたら載ってなさそう。違うホワイトブックだったか
もしんない。
--
NAKAMURA Takahiro
あつし
news:14295.41848....@siva.video.yaita.sharp.co.jp...
> 嘘ついた。今見直してみたら載ってなさそう。違うホワイトブックだったか
> もしんない。
>
> --
> NAKAMURA Takahiro
ホワイトブックに載ってたといいう情報だけでも貴重です。
ありがとうございました。調べてみます。
小島 淳志
あつし
oomoto ryuuji <oom...@tpp.epson.co.jp> wrote in message
news:37D70111...@tpp.epson.co.jp...
> 多項式とは 0xedb88320L のことです。演算はビットシフト＋排他的論理和で
> す。
> 後は１バイトづつ読みながらＣＲＣを更新していってデータの最後に書いてある
> オリジナルのＣＲＣと比較するだけです。
ありがとうございます。
明日、会社の方で試してみます。
0xedb88320L とは、long の 16進で、EDB88320ということですよね・・・。
なぜ生成多項式が0xedb88320L なのか、イマイチピンと来ないのですが・・
プログラムを頑張って読んでみます。
小島 淳志
Yasushi Kurokawa
あつし <oj...@a1.mbn.or.jp>
wrote in message news:7r61v3$dmf$1...@news.mbn.or.jp...
> よく、HDLC手順等で採用されているメッセージの正常性チェックに、CRCという
> 方式が存在しますが、この生成方法は、具体的にはどうすればよいのでしょう
> か?ものの本を読んでも、高次の生成多項式を云々・・・・と書いてあって、ど
> うやって実装してよいのかわかりません。
次の本はいかがでしょう。
奥村晴彦著、技術評論社、「C 言語による最新アルゴリズム事典」
背景となる理論もそうですが、C 言語での実装例がすぐ使える物が多く、使い
方や応用方法も載っていて、便利かと思います。一生物の本だと思います。
> 通常はHWで自動的に計算して電文につけるものだと思うのですが、ある事情で、
> 電文のCRCを自前で作らなければならない状況になってしまいました。
まあ、ソフトでも良く使います。(^o^)
--------------------------------------------------------------------------
Yasushi Kurokawa, Faculty of engineering, Takushoku university
If you have any e-mail to me...
y...@rose.yyy.or.jp
oomoto ryuuji
> なぜ生成多項式が0xedb88320L なのか、イマイチピンと来ないのですが・・
X^4 +X^1 +1 というのは実は 2^4+2^1+1 の事なのです。
おまけによくＣＲＣの計算の説明文に書いてある２進数の筆算（割り算）と
実際のプログラムでは MSB と LSB が逆になっているので余計分かりにくので
す。
--
------------
大本隆二
------------
NAKAMURA Takahiro
これは通信の世界では一般的にLSB Firstでデータが流れていて、そのビット列
を順次処理するため、8bitデータとして取り扱う場合に逆になってしまうんです。
--
NAKAMURA Takahiro
Kazuo Fox Dohzono
私が昔コーディングの勉強用に参考にしたのは UNIX 用の x/y/zmodem パッケー
ジに付いてくる crc.c です (実はこのパッケージの正式名称を知らないので
すけど, 古くからあって有名なものです).
現在上記 x/y/zmodem のソフトウェア群 (rx, ry, rz, sx, sy, sz) は
shareware ということになっているようですが, それらと独立したソフトウェ
アである crc.c には
/*
* Copyright (C) 1986 Gary S. Brown. You may use this program, or
* code or tables extracted from it, as desired without restriction.
*/
とありますし, その他の部分には
In article <14296.53191....@siva.video.yaita.sharp.co.jp>
NAKAMURA Takahiro <nakam...@tch.sharp.co.jp> writes:
> これは通信の世界では一般的にLSB Firstでデータが流れていて、そのビット列
> を順次処理するため、8bitデータとして取り扱う場合に逆になってしまうんです。
この辺りの技術的な話も含めて詳しく書かれています.
あと“何故生成多項式が 0xedb88320L なのか”ですけど (この場合生成多項
式というのは
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+X^0
ですよね), 答は“ITU-T でそう定められている (それが選択されている) か
ら”です. 誤り検出に使える生成多項式は多数 (長さを問わなければ無限に)
存在し, 検出可能な誤りビット長などの兼ね合いから選択されています.
--
Kazuo Fox Dohzono / doh...@hf.rim.or.jp
[12],(6,9),0,0,2
(190/8035/14779)
Masaaki Ohnaka
> あと“何故生成多項式が 0xedb88320L なのか”ですけど (この場合生成多項
> 式というのは
>
> 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+X^0
この場合、X^32が反映されていないようですが、これはどうしてなのでしょう。
単に３２ビット区切りがちょうど良いので無視しているのでしょうか。
Masaaki Ohnaka
Kazuo Fox Dohzono
In article <7rfrhg$luu$1...@newsgw7.odn.ne.jp>
"Masaaki Ohnaka" <ohn...@pop02.odn.ne.jp> writes:
> > 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+X^0
>
> この場合、X^32が反映されていないようですが、これはどうしてなのでしょう。
> 単に３２ビット区切りがちょうど良いので無視しているのでしょうか。
n 次多項式による剰余は高々 n-1 次ですから, 先に多項式を減ずる必要があ
るかどうかを最上位桁について調べれば演算結果は (この場合) 32bit に収ま
ることになります.
In article <37D70111...@tpp.epson.co.jp>
oomoto ryuuji <oom...@tpp.epson.co.jp> writes:
| if(((d >> j)^c) & 1) c=(c>>1)^pol; else c >>= 1;
ここで減算 (排他的論理和) する前に最下位ビットを見ているのが元の生成多
項式での最上位桁と比較 (論理積) している部分です.
…というような説明でよろしいでしょうか (わかりにくい?).
--
Kazuo Fox Dohzono / doh...@hf.rim.or.jp
[12],(6,9),0,0,2
(198/8699/15798)
Masaaki Ohnaka
>
> ここで減算 (排他的論理和) する前に最下位ビットを見ているのが元の生成多
> 項式での最上位桁と比較 (論理積) している部分です.
あ、プログラムをちゃんと見ていませんでした。
X^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+X^0
がITU-T で定められているというのは32ビット環境での、今回の例のような
コーディングを見据えてのことの様な気がします。
例えば64ビット環境なんかでは、
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+X^0
を馬鹿正直にそのまま全部使って計算、なんてコーディングもありなんで
しょうね。
って、こんな理解で良いのかな・・・？
Masaaki Ohnaka
MIYASAKA Masaru
news:7rgmjk$n06$1...@newsgw7.odn.ne.jp...
>
> 例えば64ビット環境なんかでは、
> 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+X^0
> を馬鹿正直にそのまま全部使って計算、なんてコーディングもありなんで
> しょうね。
>
> って、こんな理解で良いのかな・・・？
>
多項式の最上位ビットは、扱いが他のビットとは異なるので、それは
ないと思います。多項式の最上位ビットに対応する計算相手のビットが
0ならXORしない/1ならXORする、と場合分けするので最上位ビットの
計算結果は必ず 0 になりますし。
CRC の計算は、小学校で習った筆算のわり算を思い浮かべると、わりと
簡単に理解できますね。ただ、２進数であることと、途中の引き算の
代わりに XOR を使うところが違いますが。
---------------------------------
宮坂 賢 (Miyasaka, Masaru)
Asahikawa-City, Hokkaido, Japan
e-mail : alk...@coral.ocn.ne.jp
oomoto ryuuji
ｃとｐｏｌの大小比較はＭＳＢのみで行われています。
ｐｏｌが割る数。
本当の割られる数は c^d32 ですが以前のプログラムでは c と d に分離した
状態で保持されています。
そのため msb==1 の判定が c のビット０と d のビット０の xor が１かどうか
という形になっていたのです。
#include <stdio.h>
FILE *fi;
main(argc,argv)
int argc;
char *argv[];
{
long size;
if(argc<2) {
printf("cr2 input\n");
exit();
}
if((fi = fopen(argv[1],"rb")) == NULL) {
printf("can not open file1 for input\n");
exit();
}
size=0;
while(1) {
if(fgetc(fi) == EOF) break;
size++;
}
rewind(fi);
printf("size=%ld\n",size);
crc_check(size);
}
crc_check(size)
long size;
{
unsigned long c,c_org,crc,pol,table[256],d32;
int i,j,k,d,msb,pr;
pr=1;
pol = 0xedb88320L;
for(i=0;i<256;i++) {
c=i;
for(k=0;k<8;k++) {if(c & 1) c=(c>>1)^pol; else c >>= 1;}
table[i]=c;
}
c = 0xffffffffL;
/* pre read 4 byte */
d32 = (unsigned long)fgetc(fi);
d32 |= (unsigned long)fgetc(fi) << 8;
d32 |= (unsigned long)fgetc(fi) << 16;
d32 |= (unsigned long)fgetc(fi) << 24;
while(size) {
if(size > 4) {
d=getc(fi);
if(d == EOF) {printf("EOF\n");exit();}
} else {
d=0;
}
for(j=0;j<8;j++) {
c_org = (c^d32); /* original c = (c^d32) */
msb = (c_org & 1);
c >>= 1;
d32 = (d32 >> 1) | ((unsigned long)(d & 1) << 31);
d >>= 1;
c_org = (c^d32);
if(pr) {
printf(" %d.",msb);
for(i=0;i<32;i++) {
if(c_org & (1L << i)) printf("1"); else printf("0");
}
printf(" (=c)\n");
}
if(msb == 1) {
c_org ^= pol;
c ^= pol;
if(pr) {
printf(" - 1.",msb);
for(i=0;i<32;i++) {
if(pol & (1L << i)) printf("1"); else
printf("0");
}
printf(" (=pol)\n");
printf("---------------------------------------\n");
printf(" 0.");
for(i=0;i<32;i++) {
if(c_org & (1L << i)) printf("1"); else
printf("0");
}
printf("\n");
}
}
if(pr) printf("\n");
}
size--;
}
c ^= 0xffffffffL;
printf("crc = %08lx\n",c);
}
------------
大本隆二
------------
Masaaki Ohnaka
> ないと思います。多項式の最上位ビットに対応する計算相手のビットが
そうなんですか。
私は、ビット演算ではなく多項式そのものでザクザク割っていくような
のもあるのかなと思ったんです。
ビット演算に比べると非効率的ですが、見た目わかりやすいかなと。
いずれにしても、今の段階では私の理解度が低いので、せっかくしてくださった
アドバイスが徒労に終わってしまいそうで申し訳ないです。
アルゴリズムの本を片手に、紙と鉛筆で人間デバッガ(トレーサー)をやってみます。
もっと理解が深まれば、みなさんのおっしゃることも理解できるのでは、と思って
います。
いつかはやらねばと思いつつ手を出せなかったことに、道が開けました。
このスレッドの投稿者の方々に感謝します。
Masaaki Ohnaka
あつし
> アルゴリズムの本を片手に、紙と鉛筆で人間デバッガ(トレーサー)をやってみま
す。
> もっと理解が深まれば、みなさんのおっしゃることも理解できるのでは、と思って
> います。
>
> いつかはやらねばと思いつつ手を出せなかったことに、道が開けました。
> このスレッドの投稿者の方々に感謝します。
このスレッドの発端をつくりました小島です。
ちょっと見ない間にこんなに内容が発展していて、コメントなしでもうしわけありま
せん。
私もみなさんの意見を参考に、解読してみたいと思います。
みなさま、ありがとうございました。
小島 淳志 oj...@a1.mbn.or.jp