掲載すると言っておきながら載せなかった、
CRC32を算出できる完全なコード。
テーブルでの処理が理解しにくい場合は次の手順で1ビットづつ処理するように変更するとよいかも。
CalcCrc()内でコメントされているCalcCrc1byte()を有効にしてCalcCrc1byteTbl()を削除する。
見通しが悪いならCalcCrc1byteTbl()とMakeCrcTbl()、DispTable()を削ってもよい。
CRC16、IBM PC-DOS版CRCのコードは後日掲載予定。。
[fcrc32.c]
/*
CRC32(ANSI)(右送り)を計算する。
ファイルのCRC32を求めるときはこれを使う。
CRC:Cyclic Redundancy Check (巡回冗長検査)
CRC32生成多項式 (ただし^は次数。XORではない。)
x = 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+1
x^0(x[0])をMSB、x^31(x[31])をLSBとして32ビットの生成多項式を表現すると、
(x^32(x[32])はLSBの下になり、押し出されるビットなのでこの値には現れない。入力ビットとのxorで使う。)
11101101101110001000001100100000(1) = 0xEDB88320
^x[0]   → CRCシフト方向     →  ^x[32]
これを除数としてCRCシフト時のビットあふれごとにCRCを除する。
(シフトは入力データとあふれビットのXORをとったもので回転シフトする)
処理はバイナリファイルの先頭から1バイトづつ、LSBを先頭としたビット列とし、
各ビットごとにCRCを右シフトし、
x^32(シフト前のCRCのLSB)の値とデータビットをXORした結果、
1ならCRC全体を生成多項式で除した後、1をMSB側から右シフトで挿入。
0なら0をMSB側から右シフトで挿入。
すべてのデータが終わったらCRCの値を反転させる。
*/
#include <stdio.h>
#define READBUF 10240   // ファイル読取バッファサイズ
#define DATABUF 1024    // CRC処理データ用バッファサイズ
unsigned long CalcCrc(unsigned long* Crc, unsigned char* pBuf, int nBytes);
unsigned long CalcCrc1byte(unsigned long* Crc, unsigned int nSample);
unsigned long CalcCrc1byteTbl(unsigned long* Crc, unsigned int nSample);
unsigned long CalcCrclong(unsigned long* Crc, unsigned long Data);
void MakeCrcTbl(void);
void DispTable(void);
// 生成多項式(除数)
unsigned long Poly = 0xEDB88320;
unsigned long CrcTbl[256];
// メインルーチン
// 指定のファイル全体をメモリ上に
int main(int argc, char* argv[])
{
        // CRCの初期値 CRC32では全ビット1
        unsigned long Crc;
       
        int nRead;                      // 読出し数
        int buf[DATABUF+1];     // データバッファ
        int num;
        FILE *fd;
       
        if(argc == 2 && (fd = fopen(argv[1], “rb”)) != NULL) {
               
                // 大容量バッファに変更。失敗しても問題ないのでエラー処理無し。
                setvbuf(fd, NULL, READBUF, _IOFBF);
               
                // CRCテーブル初期化
                MakeCrcTbl();
                //DispTable();
               
                // CRC初期値
                Crc  = 0xffffffffL;
               
                // ファイルを先頭から1バイトずつ読み出してCRCを計算する。
                // ワード長は関係無く先頭バイトから、ビット並びはデータのLSBから処理。
                do {
                        nRead = fread(&buf, 1, DATABUF, fd);
                        CalcCrc(&Crc, (unsigned char*)&buf, nRead);
                } while(nRead != 0);
                fclose(fd);
                // データの末尾にCRCがある場合のシミュレーション
                // これを実行すると常にCRCが0となる。
                //CalcCrclong(&Crc, Crc);
               
                // CRC32では最後に値を反転させる。CRC32特有の処理。
                Crc = ~Crc;
               
                // CRCを表示
                printf(“%08X\n”, Crc);
        }
        else {
                printf(“using>%s <file>\n”, argv[0]);
        }
        return(0);
}
// バッファに詰められたデータを先頭から1バイトずつnBytesまで更
unsigned long CalcCrc(unsigned long* Crc, unsigned char* pBuf, int nBytes)
{
        while(nBytes– != 0) {
                // 1バイトあたりのCRCを計算する
                CalcCrc1byteTbl(Crc, *pBuf++);   // テーブルを使って8ビットごとバージョン
                //CalcCrc1byte(Crc, *pBuf++);    // 1ビットづつ素朴にバージョン
        }
       
        return(*Crc);
}
// テーブルを使って1バイトのCRCを更新処理
unsigned long CalcCrc1byteTbl(unsigned long* Crc, unsigned int Data)
{
        Data = Data & 0xff;             // Dataにゴミがある場合の保険
       
        *Crc = (*Crc >> 8) ^ CrcTbl[(unsigned char)(*Crc ^ Data)];
        return(*Crc);
}
// ビット単位の処理で1バイトのCRCを更新処理
unsigned long CalcCrc1byte(unsigned long* Crc, unsigned int Data)
{
        unsigned int DataBit;   // 処理対象ビットの値
        unsigned int CrcTopBit; // CRCからシフト時あふれるビットの値
        int Bits;                               // ビット処理のカウンタ
        Data = Data & 0xff;             // Dataにゴミがある場合の保険
        // 入力データはバイト単位、LSBから処理
        for(Bits=0; Bits<=7; Bits++) {
                DataBit   = (Data >> Bits) & 0x1;       // データの中から対象とするビットを取得
                CrcTopBit = *Crc & 0x00000001;          // CRCからあふれるビットを取得
                // CRCは右シフトで詰める
                *Crc = *Crc >> 1;
                // CRCのあふれ(x^32の部分) xor 対象入力データ が1なら生成多項式で剰余を求める
                if(CrcTopBit ^ DataBit) {
                        *Crc = *Crc ^ Poly;     // 右シフト時にMSBに0が詰められるので、MSBには暗黙に生成多項式の値から1が入る
                }
        }
       
        return *Crc;
}
// 32ビット/ワードのCRC更新処理
// データ末尾にCRCを付けることの検証用 CalcCrclong(&Crc, Crc) で Crcが0になる。
//
// 最後のCRCが 85FAFF4F (10000101111110101111111101001111)なら
// 反転前のCRCが7A0500B0 (01111010000001010000000010110000)、
// 挿入はCRCのx^31(LSB側)から行なうのでファイル上の並びでは B0 00 05 7A となる。(データはLSBから)
unsigned long CalcCrclong(unsigned long* Crc, unsigned long Data)
{
        unsigned int DataBit;   // 処理対象ビットの値
        unsigned int CrcTopBit; // CRCからシフト時あふれるビットの値
        int Bits;               // ビット処理のカウンタ
        // 入力データはバイト単位、LSBから処理
        for(Bits=0; Bits<=31; Bits++) {
                DataBit   = (Data >> Bits) & 0x1;       // データの中から対象とするビットを取得
                CrcTopBit = *Crc & 0x00000001;          // CRCからあふれるビットを取得
                printf(“%d\n”, DataBit);
               
                // CRCは右シフトで詰める
                *Crc = *Crc >> 1;
                // CRCのあふれ(x^32の部分) xor 対象入力データ が1なら生成多項式で剰余を求める
                if(CrcTopBit ^ DataBit) {
                        *Crc = *Crc ^ Poly;     // 右シフト時にMSBに0が詰められるので、MSBには暗黙に生成多項式の値から1が入る
                }
        }
       
        return *Crc;
}
// 8ビット処理用に256エントリのCRCテーブルを作成
void MakeCrcTbl()
{
        unsigned int Data;              // ダミーのデータ
        unsigned long Crc;              // ここで使うCRCレジスタ
        for(Data=0; Data<256; Data++) {
                Crc = 0x00000000;       // CRCは0としておく
                CrcTbl[Data] = CalcCrc1byte(&Crc, Data);        // 値の作成にはビット単位のCRC処理を使う
        }
}
// CRCテーブル内容の表示
void DispTable()
{
        int i;
        for(i=0; i<256; i++) {
                printf(“%08x “, CrcTbl[i]);
                if((i+1) % 8 == 0) {
                        printf(“\n”);
                }
        }
}
CRC演算テーブルを作成するのに1ビット単位のCRC計算ロジックを流用してるのってあんまり無いんですよね。
ハードコーディング(固定値)されてるのは割とあるんだけど、それだと生成多項式を変更したいとか、
そもそもどうやってテーブルができきてるかとか、理解できないじゃないですか。
広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中