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 查表法不就不存在吗

[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 这句代码是什么意思？