4

そこには多くのCRC計算の例があります。ビットシフトによるシンプルな実装と、事前に計算されたテーブルによるより効率的な実装。しかし、計算に影響を与える多項式以外にも、CRC の多くのパラメーターがあります。これらのパラメータは、http: //zorc.breitbandkatze.de/crc.htmlで評価できます。

これらのパラメータは

  • CRCの初期値
  • 入力データの反映
  • 出力データの反映
  • CRC の最終 XOR 値

一部の「標準」CRC アルゴリズムでは、CRC-16 (CCITT) のように、これらのパラメーターが明確に定義されています。ただし、異なるパラメーターを使用する実装がいくつかあります。

私の実装は、CCITT 多項式 (x 16 + x 12 + x 5 + 1)を持つ CRC16 と互換性がある必要があります。ただし、データ バイトと最終的な CRC を反映する必要があります。これらの反映を計算方法に実装しました。しかし、それには時間がかかります。最高のパフォーマンスを得るには、計算から除外する必要があります。

CRC の反射パラメータは、初期化メソッドでどのように計算できますか?

編集:各パラメーターを個別に制御するにはどうすればよいですか? 関数が実際にどのようにInit機能し、すべてのパラメーターがどのように実装されているかを理解したいと思います。

typedef unsigned char uint8_t;
typedef unsigned short crc;

crc  crcTable[256];
#define WIDTH  (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH - 1))
#define POLYNOMIAL 0x1021

template<typename t>
t reflect(t v)
{
    t r = 0;

    for (int i = 0; i < (8 * sizeof v); ++i)
    {
        r <<= 1;
        r |= v&1;
        v >>= 1;
    }

    return r;
}

void Init()
{
    crc  remainder;

    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend << (WIDTH - 8);

        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & TOPBIT)
                remainder = (remainder << 1) ^ POLYNOMIAL;
            else
                remainder = (remainder << 1);
        }

        crcTable[dividend] = remainder;
    }
}

crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;

    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = reflect(message[byte]) ^ (remainder >> (WIDTH - 8));
        remainder = crcTable[data] ^ (remainder << 8);
    }

    return reflect(remainder);
}

int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";

    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);

    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04x\n", result, expected);
    }
}
4

1 に答える 1

4

入ってくるデータ、入ってくる CRC、そして出ていく CRC を反映する代わりに、単に多項式と演算を反映します。コードを書いているときに一度だけ行う必要があります。反映された多項式は0x8408です。

typedef unsigned char uint8_t;
typedef unsigned short crc;

crc  crcTable[256];
#define POLYNOMIAL 0x8408

void Init()
{
    crc  remainder;

    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend;

        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ POLYNOMIAL;
            else
                remainder = (remainder >> 1);
        }

        crcTable[dividend] = remainder;
    }
}

crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;

    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = message[byte] ^ remainder;
        remainder = crcTable[data] ^ (remainder >> 8);
    }

    return remainder;
}

int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";

    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);

    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04x\n", result, expected);
    }
}

一般的なケースでは、入力データが反映されている場合、この回答に示されているように多項式を反映し、下部のバイトをフィードし、多項式の排他的論理和の下位ビットをチェックし、上にシフトします。入力データが反映されない場合は、質問のコードのように、多項式をそのままにして、先頭のバイトをフィードし、上位ビットを確認して、シフトダウンします。

ほとんどの場合、出力の反射は入力の反射と同じです。これらすべてについて、ビットリバース機能は必要ありません。入力と出力の両方が反映されない場合、または入力と出力の両方が反映される場合は、シフト レジスタからの結果をそのままにします。RevEng サイトでカタログ化された 72 個の CRC のうち 1 つだけが、リフレクト インと異なるリフレクト アウトです (CRC-12/3GPP)。その場合、入力は反映されませんが、出力は反映されるため、出力をビット反転する必要があります。

初期 CRC は、単純にシフト レジスタの初期内容です。CRC を開始するときに一度設定します。最後の排他的論理和は、最後にシフト レジスタの内容に適用されます。一度に CRC を計算する関数がある場合は、関数に入るときに最終排他的論理和を適用する必要があり、その最終排他的論理和をユーザーに表示される初期値にも適用する必要があります。実際の初期値は、シフト レジスタに格納される値です。

于 2015-02-22T17:45:08.117 に答える