CRC-32 查表法真的存在吗？

[quxinna]

<amp-youtube data-videoid="6qAZAX6ymXY" layout="responsive" width="480" height="270"></amp-youtube>看了这个视频发现 CRC-8 可以通过查表法查，方法是查表得到的 CRC-8 值 XOR 输入的数据，得到的数值作为表的索引找到新的 CRC 值不断循环得到最终的 CRC-8 值，但是 CRC-32 查表法要不止 256 个索引吧，那 CRC-32 查表法不就不存在吗

[quxinna]

@3dwelcome for bit in range(8) 和 operator <<= 1 等于补足 8 位，并不仅仅是去掉最高位

[ZhaoHuiLiu]

@quxinna

var=0xffffffff 这里最大值是 UINT32_MAX
operator=int('{:08b}'.format(operator)[::-1],2) 这里的 {:08b} 是指 8 位二进制，也就是 256 个数
operator=operator^(var>>24) 这里的 var 是 32 位，向右移动 24 位，就剩下 8 位，8 位再和 operator 位进行位运算
crc32_table_normal[operator] 此时的 crc32_table_normal 必然为 256 大小的数组

[quxinna]

@ZhaoHuiLiu var=(crc32_table_normal[operator])^(var<<8)&0xffffffff 这句代码是什么意思？

[ZhaoHuiLiu]

@quxinna
var=(crc32_table_normal[operator])^(var<<8)&0xffffffff
crc32_table_normal 数组 operator 变量，var<<8 左边移动 8 位，如果 var 是 32 位，此时左边移动 8 位就是 40 位, (var<<8) & 0xffffffff 这里的 (var<<8) 是 40 位，& 0xffffffff 表示我只要 32 位数据，crc32_table_normal[operator] 查表得到一个 32 位数据，32 位数据进行 ^ 操作得到 32 位数据，此时 var 还是 32 位数据。
crc32_table_normal[operator] 这里的 operator 根据上面的处理，确定为 8 位，也就是 256 最大大小。索引是从 0 开始，所以 operator 最大值为 255 数值。

[quxinna]

@ZhaoHuiLiu 可是这样查表法就和手算法有矛盾，手算法是先查表计算出第 1byte 的 crc32 的值，然后把剩下的 3byte 和这个 crc32 进行 xor，结果再进行查表，可是查表法是查表得到一个 crc32 的值，提取出最开始 1byte，把剩下的 1byte 和这个 1byte crc32 进行 xor，结果进行查表，然后 xor 上次的 CRC32 值去掉开头 1byte，可是结果是一样的，真的好奇怪

[ZhaoHuiLiu]

@quxinna

crc32 默认值就是 0xffffffff 这个值。。。你传递进行去的数据和这个值做运算

[quxinna]

@ZhaoHuiLiu 我把初始值 INIT 和结果异或值 XOROUT 都设为了 0，不影响结果的正确性，我只是搞不懂

operator^=(var>>24)
var=(crc32_table_normal[operator])^(var<<8)&0xffffffff

是什么意思

[ZhaoHuiLiu]

我建议你看 C 语言，这个 python 语言资料还没 C 语言多，python 也只是个玩具。

[quxinna]

@ZhaoHuiLiu 计算 0x010x02 的 crc32 值
1 的 crc32 值 0x4c11db7 提取最高位 1byte 4，和 2 进行 xor 结果 6 查表 crc32 值 0x1a864db2，1 的 crc32 值去掉最高位 1byte，低位补 0 0xc11db700，和 2 的 crc32 值 0x1A864DB2 xor 得到 0xdb9bfab2
结果是正确的，但是暂时不知道和手算法如何等同

[quxinna]

@quxinna
100000010
0x104c11db7

10000001000000000000000000000000000000000
100000100110000010001110110110111

11011000001000111011011011100000000
100000100110000010001110110110111

1011010010000110011100000111011100
100000100110000010001110110110111

11011011100110111111101010110010

结果是一样的，但是不知道怎么会是一样

[jhdsgfww]

好久之前写过一篇博文说过 CRC 的计算，里面有 CRC32 的查表计算。https://blog.zmyme.com/posts.html?id=crc-principles-and-algorithms
（但是现在再看已经头大了.....)

[quxinna]

@quxinna 好像可以通过结合律： ( A ^ B ) ^ C = A ^ ( B ^ C )推导出查表法等于手算法
但是由于自反性：A ^ B ^ B = A （由结合律可推：A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A ）查表法等于 255 个 crc32 值每隔 1byte 进行 xor，算出有 4129476120/24=172061505 种可能性，请教高手对吗？

[quxinna]

@3dwelcome var=(crc32_table_normal[operator])^(var<<8) 中当 var=0xffffffff，第一次计算的时候会异或 0xffffff00 吗？ operator^=(var>>24)，operator^ff，那么并不是输入数据反转啊？

[quxinna]

@quxinna var 的 0xffffffff 值，提取最高位 1byte 0xff，和 01 进行 xor 结果，查表 crc32 值，var 的 0xffffffff 值去掉最高位 1byte，低位补 0 0xffffff00，和查表 crc32 值 xor 得到结果，原来是输入数据反转

[quxinna]

存在
https://v2ex.com/t/780186#reply4

[quxinna]

我发现这个问题和引体向上有关

[quxinna]

crc32 表存在于 gmail 帮助文档中