CRC32添加剂？

Question

在几个地方我读过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

有人能提供一个证明这个理论的正确代码,还是指出我失败的地方？

Answer 1

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哈希作为第一个参数,将新数据作为第二个参数进行累积.返回值是新运行的CRC.

上面代码中初始运行的CRC值为0是至关重要的.使用任何其他初始值,CRC在实际意义上不是"加性的",因为您已经有效地丢弃了有关您要分割的整数的信息.这正是你的例子中发生的事情.CRC函数永远不会将初始运行的CRC值初始化为零,但通常为-1.原因是初始CRC为0允许数据中的任何数量的前导0简单地通过而不改变运行的CRC值,该值保持为0.因此,将CRC初始化为0在数学上是合理的,但是出于实际的计算目的哈希,这是你想要的最后一件事.

Answer 2

这意味着 CRC 结果的每个位位置仅由输入中的等效位位置驱动。考虑 B == 0 的示例。

对于某些原始异或或附加校验和算法，您描述的关系更有可能成立。