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

[quxinna]

看了这个视频发现 CRC-8 可以通过查表法查，方法是查表得到的 CRC-8 值 XOR 输入的数据，得到的数值作为表的索引找到新的 CRC 值不断循环得到最终的 CRC-8 值，但是 CRC-32 查表法要不止 256 个索引吧，那 CRC-32 查表法不就不存在吗

[3dwelcome]

你可以看这个页面 http://www.zorc.breitbandkatze.de/crc.html

所谓 CRC-8 和 CRC-32 区别，也就是 order 不一样，查表是一样的。

[quxinna]

@3dwelcome 什么是 order ？查表为什么 CRC-32 和 CRC-8 都是 256 个？但是 CRC-32 是 32 位 CRC-8 是 8 位，一次只能计算 8 位啊

[3dwelcome]

order 是次方的意思，CRC 原理就是多项式校验和，CRC-8 是单次计算最大 8 次方，CRC-32 是单次计算最大 32 次方。

查找表的本意是把多项式累加这个预处理过程先算一遍，和处理最终值大小没什么关系。因为对于输入的校验数据，都是按照 bit-by-bit 处理的，就算查找表也一样。

[quxinna]

@3dwelcome 但是表不是有一个索引吗？这个索引从哪里来？

[3dwelcome]

@quxinna 你没懂我的意思，索引是 256 个，说明是对数据 8 个 bit 进行处理，也就是每次处理一个 byte 。
你也可以改成 4 个 bit 一次建表，那就是 lookuptable[16]。
和计算的 order 没关系。

[quxinna]

@3dwelcome 但是 CRC-32 的表里的元素是 32 位的，一次不可能只处理 8 个 bit 吧？

[3dwelcome]

@quxinna 说了数据是一个 bit 一个 bit 处理的，和元素有多少位没关系，表格仅仅只是为了加速运算，所以 256 个数组来加速一个字节，已经足够了。
元素是 32 位，说明最终的累加结果是 CRC-32 位的，你要把中间结果都加起来，肯定不能只用 8 位了。如果元素是 64 位，那就是 CRC-64 位算法。

[quxinna]

@3dwelcome 主题中 YouTube 视频为什么 Index=CRC XOR Input Data?

[3dwelcome]

@quxinna " 视频为什么 Index=CRC XOR Input Data?"正常来说，不用加速表，一个 byte 有 8bit, 每个 bit 都是有可能算一次异或的(视具体多项式而定)。
加速表把这个结果预计算后保存起来，那么现在处理一个 byte，仅需要算一次异或，大大降低了总体计算量。

[yolee599]

查表属于用空间换时间的算法，理论上所有 crc 都可以通过查表法计算

[tempdban]

我要不要给你贴代码…

[quxinna]

@tempdban 贴了解释一下吧，我看不太懂代码，只知道皮毛，例如这个 BSD 的 CRC32 代码我就没有看懂。http://web.mit.edu/freebsd/head/sys/libkern/crc32.c

[ZhaoHuiLiu]

所有的 CRC 算法都可以生成表来查询。。。。
从 CRC4 到 CRC64 都可以通过表，你可以到 Github 搜索算法就知道了。。。

[quxinna]

@ZhaoHuiLiu 我到 Github 搜到了这个
import copy

poly_crc32_normal=0x104c11db7

crc32_table_normal=[]
for byte in range(256):
operator=copy.copy(byte)
operator<<=24
for bit in range(8):
if (operator & 0x80000000) != 0:
operator <<= 1
operator ^= poly_crc32_normal
else:
operator <<= 1
crc32_table_normal.append(operator)
def crc32_normal(line):
var=0xffffffff
for ch in line:
operator=ord(ch)
operator=int('{:08b}'.format(operator)[::-1],2)
operator=operator^(var>>24)
var=(crc32_table_normal[operator])^(var<<8)&0xffffffff
var=int('{:032b}'.format(var)[::-1],2)
return var^0xffffffff

print(hex(crc32_normal('123456789')))

好像能够得到正确的结果，但是看不懂如何索引表的，哪位高手解释一下感激不尽

[quxinna]

@quxinna 这个表好像是 4294967296 个元素，不是 256 个元素

[quxinna]

@3dwelcome 能不能帮忙解释一下这段 python 代码是如何查表的？
https://github.com/221294583/crc32

[3dwelcome]

generate a look up table

poly_crc32_normal=0x104c11db7 (这个就是多项式，和 0xedb88320 为大小头互补，是一个值。可以自定义，crc32 算法并不是唯一多项式。）
crc32_table_normal=[]
for byte in range(256):
　　 operator=copy.copy(byte)
　　 operator<<=24
　　 for bit in range(8):
　　　 if (operator & 0x80000000) != 0:
　　　　 operator <<= 1 　　　（要异或时 operator 的最高位是 1，CRC 多项式最高位一直就是 1，异或后必为 0，所以一开始就偷懒把 CRC 多项式去掉最高位变成 0x4C11DB7, 所以相应的这时候要把 operator 左移一位，只要异或后边的 32 位）
　　　　 operator ^= poly_crc32_normal 　（余式 CRC 乘以 2 再求 CRC ）
　　　 else:
　　　　 operator <<= 1
　　 crc32_table_normal.append(operator)

[3dwelcome]

CRC32，严格来说是 33 位 bit 的多项式，但是最前面一直是 1(和计算机里的 IEEE 浮点格式一样，Fraction 部分永远是 1 开头，干脆去掉，这叫隐含位），去完后，刚好凑齐 32bit 一个整型来保存多项式。

所以 CRC32 上面建表算法里，才会有那个比较奇怪的 if (operator & 0x80000000) != 0 这行。

[quxinna]

@3dwelcome 0x80000000 是 32 位的 10000000000000000000000000000000，用于检查数据是否是 32 位，不够的话需要补位

[quxinna]

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

[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 帮助文档中