2

CRC-32 アルゴリズムについて調査した結果、次のことがわかりました。

/* Usage: Recursively call this with previous crc. Start with crc = 0. */
#define POLYNOMIAL 0x04C11DB7

unsigned int crc32( unsigned int crc, char* msg, unsigned int len ) {
  for ( unsigned int byteNum = 0; byteNum < len; byteNum++ ) {
    char msgByte = msg[ byteNum ];

    for ( unsigned int bitNum = 0; bitNum < 8; bitNum++ ) {
      char msgBit = ( msgByte >> ( 7 - bitNum ) ) & 0x1;

      if ( ( crc & 0x80000000 ) != 0 )
        crc = ( ( crc << 1 ) | msgBit ) ^ POLYNOMIAL;
      else
        crc = ( crc << 1 ) | msgBit;
    }
  }
  return crc;
}

ただし、私のコードの出力は、一般的に使用される CRC-32 関数 (テーブルで最適化) の出力とはまったく異なります。

ここで、テーブルによって最適化されていない CRC-32 アルゴリズムのサンプル ソース コードを誰かが提供してくれることを願っています。

ありがとう、
デニス

4

4 に答える 4

1

これは正しくありません:

if ( ( crc & 0x80000000 ) != 0 )
    crc ^= POLYNOMIAL;
crc = ( crc << 1 ) | msgBit;

シフトする前に上位ビットをテストする必要がありますが、メッセージビットをシフトして挿入した後crc、POLYNOMIAL の残りを xor します。

実際の多項式は0x104C11DB7であり、ビット 32 の 1 がキャンセルされることに注意してください0x80000000 << 1(これはテストで証明されています)。

于 2013-11-11T16:54:01.737 に答える