0

コード (C で記述):

unsigned long chksum_crc32 (unsigned char *block, unsigned int length)
{
   register unsigned long crc;
   unsigned long i;

   crc = 0xFFFFFFFF;
   for (i = 0; i < length; i++)
   {
      crc = ((crc >> 8) & 0x00FFFFFF) ^ crc_tab[(crc ^ *block++) & 0xFF];
   }
   return (crc ^ 0xFFFFFFFF);
}


/* chksum_crc32gentab() --      to a global crc_tab[256], this one will
 *              calculate the crcTable for crc32-checksums.
 *              it is generated to the polynom [..]
 */

void chksum_crc32gentab ()
{
   unsigned long crc, poly;
   int i, j;

   poly = 0xEDB88320L;
   for (i = 0; i < 256; i++)
   {
      crc = i;
      for (j = 8; j > 0; j--)
      {
         if (crc & 1)
         {
            crc = (crc >> 1) ^ poly;
         }
         else
         {
            crc >>= 1;
         }
      }
      crc_tab[i] = crc;
   }
}

手始めに; 私はCRCがどのように機能するかを知っています。最初に除数が指定された多項式で計算され、次にこのFCS（フレームチェックシーケンス）がデータセットに追加され、エンドユーザーシステムに送信されます。転送が完了すると、FCS の計算に使用されたのと同じ多項式で FCS がチェックされ、その除数によるデータの剰余がゼロの場合、データが正しいことがわかります。

これら 2 つの関数の実装がわかりません。私が学んだことから、関数 chksum_crc32gentab() は、チェックサムが 32 ビット CRC 多項式で取ることができるすべての可能な 16 進数値を生成します。私が得られないことの1つは、poly = 0xEDB88320L; の方法です。は多項式と同等です。この関数の一番下のロジックもわかりません。たとえば、条件付きのif (crc & 1)は、crc のすべてのビットが 1 の場合は計算し、それ以外の場合は 1 ビット右にシフトすることを意味しますか?

chksum_crc32(unsigned char *block, unsigned int length); もわかりません。. この関数はバイト文字列を取り込んで、テーブルで計算された適切な crc 値に変換するだけですか?. forループ内で使用するロジックについて混乱していると思います。

誰かがこのコードを理解しているなら、説明は素晴らしいでしょう。これは、.net クラスからの crc32 変換で機能します。データが変換され、これらの関数で使用される方法の例は次のようになります: (C# ソース)

      MemoryStream ms = new MemoryStream(System.Text.Encoding.Default.GetBytes(input));

            foreach (byte b in crc32.ComputeHash(ms))
                hash += b.ToString("x2").ToLower();

C コードが取得された元のサイトとプロジェクトは次のとおりです。http://www.codeproject.com/Articles/35134/How-to-calculate-CRC-in-C

どんな説明でも役に立ちます

4

2 に答える 2

3

または、グーグルで検索してください... 2番目のヒットは次のとおりです。

C# からバックポートするのは難しい方法ですが、これらのアルゴリズムのほとんどは既にC に組み込まれています。

于 2012-07-30T15:49:10.870 に答える
2

CRC 計算では、0 または 1 の係数の合計であるバイナリ多項式はx^n、0 または 1 の位置がそのx係数の累乗を示すバイナリ ワードとして単純に表されます。

0xEDB88320LCRC32 多項式の係数を、項がある場合は 1 として表しますx^n(省略されている項を除くx^32)。CRC32 多項式 (なぜ、なぜスタックオーバーフローには math.stackexchange のような TeX 方程式がないのか - ここにまともな方程式を書くことはできません! ため息、暴言を吐いて申し訳ありません ... ) は次のとおりです。

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

この CRC がビット順序に関してどのように定義されているかにより、最低の係数が最高のビットにあります。したがって、E上記の 16 進定数の最初の部分は1110(ビットの左から右の順に) を表しています1 + x + x^2。

構造はzlibcrc32.cのソース ファイルで確認できます。ここにスニペットを示します。

static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

    /* make exclusive-or pattern from polynomial (0xedb88320UL) */
    poly = 0;
    for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
        poly |= (z_crc_t)1 << (31 - p[n]);

    /* generate a crc for every 8-bit value */
    for (n = 0; n < 256; n++) {
        c = (z_crc_t)n;
        for (k = 0; k < 8; k++)
            c = c & 1 ? poly ^ (c >> 1) : c >> 1;
        crc_table[0][n] = c;
    }

以上はif (crc & 1)、c & 1 ?シフトされる前に各ステップで CRC の下位ビットを調べます。これは実質的に多項式減算演算のキャリー ビットであるため、それが 1 の場合、多項式は CRC のシフト ダウンされた多項式 ( を乗算) から減算 (排他的論理和) されxます。下位ビットが 1 であるかどうかにかかわらず、CRC は下にシフトされます。

あなたchksum_crc32()が実際に示す関数は、提供されたデータブロックのCRCを計算します。これは、データ バイトと CRC の下位バイトの排他的論理和によってテーブルにインデックスを付ける、バイト文字列に対する CRC 計算の標準的なテーブル ベースのアプローチです。これは、一度にビットをシフトして 1 ビットの多項式を適用するのと同じことを行いますが、8 ではなく 1 ステップで行います。CRC は効果的にx^8(the >> 8) で乗算され、インデックス値に応じてさまざまなシフト位置で 0 ～ 8 回、多項式との排他的論理和の効果で排他的論理和が計算されます。これは、事前に計算されたテーブルを使用した単純なスピード トリックです。

crc32.cより大きなテーブルを使用し、一度により多くのデータを処理するzlib で使用される、さらに極端な速度のトリックを見つけることができます。

于 2012-07-30T19:12:59.120 に答える