12

いくつかの場所で、crc32は加算的であると読んだので、CRC（A xor B）= CRC（A）xor CRC（B）です。

上記のステートメントは、私が書いた次のコードによって反証されました。

import zlib
def crc32(data):
        return zlib.crc32(data) & 0xffffffff

print crc32(chr(ord("A") ^ ord("B")))
print crc32("A") ^ crc32("B")

プログラム出力：

1259060791
2567524794

誰かがこの理論を証明する適切なコードを提供したり、私が失敗した場所を教えてもらえますか？

4

4 に答える 4

6

CRC ハッシュは、すべてのデータ (巨大な整数として扱われる) を多項式定数で除算したキャリーレス除算の剰余値であるため、CRC は数学的な意味で加算されます。あなたの例を使用すると、次のようなものに似ています。

7 mod 5 = 2

6 mod 5 = 1

(7 mod 5) + (6 mod 5) = 3

(7 + 6) mod 5 = 3

そのアナロジーでは、「5」は CRC 多項式です。

これは（gccベース）で遊ぶ例です：

#include <stdio.h>
#include <x86intrin.h>

int main(void)
{
        unsigned int crc_a = __builtin_ia32_crc32si( 0, 5);
        printf( "crc(5) = %08X\n", crc_a );
        unsigned int crc_b = __builtin_ia32_crc32si( 0, 7);
        printf( "crc(7) = %08X\n", crc_b );
        unsigned int crc_xor = crc_a ^ crc_b;
        printf( "crc(5) XOR crc(7) = %08X\n", crc_xor );
        unsigned int crc_xor2 = __builtin_ia32_crc32si( 0, 5 ^ 7);
        printf( "crc(5 XOR 7) = %08X\n", crc_xor2 );

        return 0;
}

出力は期待どおりです。

plxc15034> gcc -mcrc32 -Wall -O3 crctest.c
plxc15034> ./a.out
crc(5) = A6679B4B
crc(7) = 1900B8CA
crc(5) XOR crc(7) = BF672381
crc(5 XOR 7) = BF672381

このコードは x86 CRC32 命令を使用するため、Intel i7 以降でのみ実行されます。組み込み関数は、実行中の CRC ハッシュを最初のパラメーターとして受け取り、蓄積する新しいデータを 2 番目のパラメーターとして受け取ります。戻り値は、新しい実行中の CRC です。

上記のコードの最初の実行中の CRC 値 0 は重要です。他の初期値を使用すると、分割する整数に関する情報を効果的に破棄するため、CRC は実用的な意味で「加法的」ではありません。そして、これはまさにあなたの例で起こっていることです。CRC 関数は、実行中の CRC の初期値をゼロに初期化することはありませんが、通常は -1 に初期化します。その理由は、初期 CRC が 0 の場合、データ内の任意の数の先頭の 0 が、実行中の CRC 値を変更せずに単純にフォールスルーできるためです。CRC 値は 0 のままです。したがって、CRC を 0 に初期化することは数学的に適切ですが、計算の実用的な目的のためです。ハッシュ、それはあなたが望む最後のものです。

于 2011-08-09T04:47:01.097 に答える
3

CRC-32 アルゴリズムは多項式除算に基づいており、いくつかの追加ステップが追加されています。純粋な多項式の剰余は加法的です。

つまり、 mod(poly1 + poly2, poly3) = mod(mod(poly1, poly3) + mod(poly2, poly3), poly3)

CRC-32 アルゴリズムはこれに基づいて構築されており、加法的ではありません。バイト配列 m の CRC-32 を計算するには:

  1. 最初の 4 バイトを 0xFFFFFFFF で XOR します。
  2. 前のバイトをより高い多項式累乗として扱い、下位ビットをより高い多項式累乗として扱います。たとえば、バイト 0x01 0x04 は多項式 x^15 + x^3 になります。
  3. 多項式に x^32 を掛けます。
  4. この多項式の余りを CRC-32 多項式 0x104C11DB7 で割った値をとります。剰余多項式の次数は 32 未満です。
  5. 下位ビットを上位ビットとして扱います。たとえば、多項式 x^2 は 32 ビット整数 0x40000000 になります。
  6. 結果を 0xFFFFFFFF で XOR します。

純粋な多項式剰余演算はステップ 4 にあります。CRC-32 アルゴリズムを無加法にするのは、ステップ 1 と 6 です。したがって、ステップ 1 と 6 の効果を元に戻すと、CRC-32 アルゴリズムを加法的に変更できます。

(参照: Python CRC-32 woes )

于 2011-08-10T04:09:08.767 に答える
2

a、b、および c が同じ長さの場合、CRC(a) xor CRC(b) xor CRC(c) は CRC(a xor b xor c) に等しくなります。元の定式化に戻ると、CRC(a xor b) が CRC(a) xor CRC(b) xor CRC(z) に等しいことを意味します。ここで、z は他の 2 つのシーケンスと同じ長さのゼロのシーケンスです。

于 2012-02-23T23:59:58.050 に答える
1

これは、CRC 結果の各ビット位置が、入力の同等のビット位置によってのみ駆動されることを意味します。B == 0 の例を考えてみましょう。

あなたが説明している関係は、一部のプリミティブ xor または加法的チェックサム アルゴリズムに当てはまる可能性が高くなります。

于 2011-08-08T07:39:29.443 に答える