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

如果a、b和c的长度相同，那么CRC(a)异或CRC(b)再异或CRC(c)的结果等于CRC(a异或b异或c)。回到你最开始的说法，这意味着CRC(a异或b)等于CRC(a)异或CRC(b)再异或CRC(z)，其中z是一串和其他两个序列长度相同的零。

Answer 2

CRC-32算法是基于多项式除法的，并且添加了一些额外的步骤。简单来说，纯多项式的余数是可以相加的。

我的意思是：mod(poly1 + poly2, poly3) = mod(mod(poly1, poly3) + mod(poly2, poly3), poly3)

CRC-32算法在这个基础上进行了扩展，并且是不可加的。要计算一个字节数组m的CRC-32值，可以按照以下步骤进行：

1. 把前4个字节和0xFFFFFFFF进行异或运算。
2. 把之前的字节看作高次多项式，把低位的比特看作高次多项式。例如，字节0x01和0x04可以表示为多项式x^15 + x^3。
3. 把这个多项式乘以x^32。
4. 将这个多项式除以CRC-32多项式0x104C11DB7，得到的余数多项式的次数小于32。
5. 把低次项看作高位的整数。例如，多项式x^2可以表示为32位整数0x40000000。
6. 把结果再和0xFFFFFFFF进行异或运算。

纯多项式余数操作在第4步。而第1步和第6步的操作使得CRC-32算法变得不可加。如果你去掉第1步和第6步的影响，就可以把CRC-32算法改造成可加的。

(另见：Python CRC-32问题)

Answer 3

CRC（循环冗余校验）在数学上是可加的，因为CRC哈希值其实就是把所有数据（看作一个大整数）用一个多项式常数进行无进位除法后得到的余数。用你的例子来说，可以这样理解：

7 除以 5 的余数是 2

6 除以 5 的余数是 1

把这两个余数加起来：2 + 1 = 3

而把 7 和 6 加起来再除以 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值设为0，而是设为-1。原因是，初始CRC为0时，数据中任何数量的前导0都不会影响当前的CRC值，它仍然是0。所以，把CRC初始化为0在数学上是合理的，但在实际计算哈希时，这并不是你想要的做法。