CRCの検定コードがどの文字でも同じになった!?

質問

C言語の初級者が質問します。
講義の課題で、「伝送誤り検出方式として巡回符号方式（CRC:Cyclic Redundancy Check)を使用した場合、送り側でアルファベット6文字の適当な単語を1文字ずつ入力した場合の検定コードを算出しなさい。生成多項式はCRC-16-CCITT（Xの16乗)＋（Xの12乗）＋（Xの5乗）＋1を使用し、検定コードは2byteとする。
この課題に対し、一文字ずつ、検定コードを求めて合計6個の和を出して16進数で表現しようと考え、以下のプログラムを作りました。#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main ()
{
int t,s,i,m;
int l;
int flag;
int crcReg[10]; // crcRegは一文字ごとのCRCの計算途中過程　res[]は一文字ごとのCRCの最終結果
char inData[6]; //文字列入力
int jyuroku[6];
int crcmax;

printf("文字入力(6文字まで）:");

gets(inData); //
l=strlen(inData);

for(i = 0;i < l; i++) {
printf("%d番目は16進数で%X\n",i+1,inData[i]); //
}
printf("各文字の16進asciiは(0x必要か？）");
for(m = 0;m <l;m++) {
printf("%d番目のascii:",m+1);
scanf("%X", &jyuroku[m]); //
}

//**********************************(後半）**********************************************
for(s=0;s < l; s++) {//文字の数だけ繰り返し
crcReg[s]=0xFFFF; //CRCの初期値はどの文字の場合でも同じ
printf("%d 番目の16進ascii:%X\n",s+1,jyuroku[s]); //
for (t = 0;t < 8; t++) { //入力する16進数は8ビット=1バイト ゆえ8回繰り返し
flag = (crcReg[s] ^ jyuroku[s] & 0x01); // 生成多項式をかけるかどうかの判定の前段階

crcReg[s] = crcReg[s] >> 1; //CRCの計算過程を1ビット右にシフト
if (flag == 0x01) { //最下位ビットflagが1の時の処理
crcReg[s] = (crcReg[s] ^ 0x8408); //生成多項式は10進数で
}
else if (flag == 0x00) {

}
jyuroku[s] = jyuroku[s] >> 1; // asciiコードも1 ビットシフト
}

printf("CRCの結果は%X\n",crcReg[s]); //
}
crcmax = crcReg[0]+crcReg[1]+crcReg[2]+crcReg[3]+crcReg[4]+crcReg[5];

printf("\n kekka:%d",crcmax); //
return 0; //
}
しかし、こうするとcrcReg[s]（検定コード）がどの文字の場合でも同じ255（16進数ではFF）になって、6文字の単語は常に和が1530になってしまいます。255＝16の2乗－1であることが問題解決の鍵だと思うのですが、何か問題点わかりますか？

回答No.2

麻野 なぎ（@AsanoNagi） · ベストアンサー

うまくいきません。だけではなく、
必ず同じ結果になるということに
着目したのは、まず、ＯＫとしま
しょう。

「結果」というのは、直接的には、
crcReg[] の値です。
まず、crcReg[] の値を変化させて
いる（または設定している）箇所を
全て抜き出します。

1) crcReg[s]=0xFFFF;
2) crcReg[s] = crcReg[s] >> 1;
3) crcReg[s] = (crcReg[s] ^ 0x8408);

よく見ると、1) は、初期設定。
2) は、for(t = 0; t < 8; t++) の
ループで毎回実行されますから、
トータルで、８ビット右シフトが発生し
ここで、crcReg[] は、0x00ff に
なっていることがわかります。

そうすると、3) は、「一度も実行
されていない」ことが推定できます。

ここまでが第一段階。

次に行きます。

3) が一度も実行されていないというこ
とは、これを実行するための条件が
決して満足されないということです。
つまり、

if (flag == 0x01) が成立しない。
つまり、
flag = (crcReg[s] ^ jyuroku[s] & 0x01);
が 0x01 にならない。
ということがわかります。

結論から言えば、ここが今回問題点です。

& と ^ は演算子の優先順位が異なります。
（& の優先順位が高い）

従って、この式は、意図しない順序で計算
されます。
この結果、flag の上位桁には、crcReg[] の
（そもそも、0xffff で初期化された）値
がそのまま反映されてしまいます。

この結果、flga が 0x01 になることはない
というのが今回の結果になります。

そうすれば、

flag = ((crcReg[s] ^ jyuroku[s]) & 0x01);

とすれば少なくとも、「同じ結果」にはなら
ないことがわかると思います。

回答No.1

gau_puzzler

参考にしてください

static Word crctable[256];
void MakeCrc(void)
{
　　Word i;
　　Word j;
　　Word r;

　　for (i = 0; i < 256; i++) {
　　　　r = i;
　　　　for (j = 0; j < 8; j++)
　　　　　　if (r & 1)
　　　　　　　　r = (r >> 1) ^ 0x8408u;
　　　　　　else
　　　　　　　　r >>= 1;
　　　　crctable[i] = r;
　　}
}

Word GetCrcN(Byte *s, int len)
{
　　Word r;

　　r = 0xFFFFu;
　　while (len--) {
　　　　r = (r >> 8) ^ crctable[(Byte)r ^ *s++];
　　}
　　return (r ^ 0xFFFFu);
}

お礼

とりあえずありがとうございます