这是一个创建于 1346 天前的主题，其中的信息可能已经有所发展或是发生改变。
看了这个视频发现 CRC-8 可以通过查表法查，方法是查表得到的 CRC-8 值 XOR 输入的数据，得到的数值作为表的索引找到新的 CRC 值不断循环得到最终的 CRC-8 值，但是 CRC-32 查表法要不止 256 个索引吧，那 CRC-32 查表法不就不存在吗
 |
1
3dwelcome 2021-04-23 13:46:04 +08:00
|
 |
2
quxinna OP @3dwelcome 什么是 order ？查表为什么 CRC-32 和 CRC-8 都是 256 个？但是 CRC-32 是 32 位 CRC-8 是 8 位，一次只能计算 8 位啊
|
|
3
3dwelcome 2021-04-23 15:06:06 +08:00
order 是次方的意思，CRC 原理就是多项式校验和，CRC-8 是单次计算最大 8 次方，CRC-32 是单次计算最大 32 次方。
查找表的本意是把多项式累加这个预处理过程先算一遍，和处理最终值大小没什么关系。因为对于输入的校验数据，都是按照 bit-by-bit 处理的，就算查找表也一样。 |
|
5
3dwelcome 2021-04-23 16:59:04 +08:00
@quxinna 你没懂我的意思，索引是 256 个，说明是对数据 8 个 bit 进行处理，也就是每次处理一个 byte 。
你也可以改成 4 个 bit 一次建表，那就是 lookuptable[16]。 和计算的 order 没关系。 |
|
7
3dwelcome 2021-04-23 18:53:21 +08:00
@quxinna 说了数据是一个 bit 一个 bit 处理的，和元素有多少位没关系，表格仅仅只是为了加速运算，所以 256 个数组来加速一个字节，已经足够了。
元素是 32 位，说明最终的累加结果是 CRC-32 位的，你要把中间结果都加起来，肯定不能只用 8 位了。如果元素是 64 位，那就是 CRC-64 位算法。 |
|
9
3dwelcome 2021-04-24 02:22:31 +08:00
@quxinna " 视频为什么 Index=CRC XOR Input Data?"正常来说，不用加速表，一个 byte 有 8bit, 每个 bit 都是有可能算一次异或的(视具体多项式而定)。
加速表把这个结果预计算后保存起来，那么现在处理一个 byte，仅需要算一次异或，大大降低了总体计算量。 |
 |
10
yolee599 2021-04-24 11:11:48 +08:00 via Android
查表属于用空间换时间的算法，理论上所有 crc 都可以通过查表法计算
|
 |
11
tempdban 2021-04-24 12:21:47 +08:00 via Android
我要不要给你贴代码…
|
|
12
quxinna OP @tempdban 贴了解释一下吧，我看不太懂代码，只知道皮毛，例如这个 BSD 的 CRC32 代码我就没有看懂。http://web.mit.edu/freebsd/head/sys/libkern/crc32.c
|
 |
13
ZhaoHuiLiu 2021-04-24 17:51:48 +08:00
所有的 CRC 算法都可以生成表来查询。。。。
从 CRC4 到 CRC64 都可以通过表，你可以到 Github 搜索算法就知道了。。。 |
|
14
quxinna OP @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'))) 好像能够得到正确的结果，但是看不懂如何索引表的，哪位高手解释一下感激不尽 |
|
16
quxinna OP |
|
17
3dwelcome 2021-04-25 00:22:52 +08:00
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) |
|
18
3dwelcome 2021-04-25 00:30:35 +08:00  1
CRC32，严格来说是 33 位 bit 的多项式，但是最前面一直是 1(和计算机里的 IEEE 浮点格式一样，Fraction 部分永远是 1 开头，干脆去掉，这叫隐含位），去完后，刚好凑齐 32bit 一个整型来保存多项式。
所以 CRC32 上面建表算法里，才会有那个比较奇怪的 if (operator & 0x80000000) != 0 这行。 |
|
19
quxinna OP @3dwelcome 0x80000000 是 32 位的 10000000000000000000000000000000，用于检查数据是否是 32 位，不够的话需要补位
|
|
20
quxinna OP @3dwelcome var=(crc32_table_normal[operator])^(var<<8)&0xffffffff 这句代码是什么意思？
|
|
21
quxinna OP @3dwelcome for bit in range(8) 和 operator <<= 1 等于补足 8 位，并不仅仅是去掉最高位
|
|
22
ZhaoHuiLiu 2021-04-25 14:08:38 +08:00
@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 大小的数组 |
|
23
quxinna OP @ZhaoHuiLiu var=(crc32_table_normal[operator])^(var<<8)&0xffffffff 这句代码是什么意思？
|
|
24
ZhaoHuiLiu 2021-04-25 15:13:35 +08:00
@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 数值。 |
|
25
quxinna OP @ZhaoHuiLiu 可是这样查表法就和手算法有矛盾，手算法是先查表计算出第 1byte 的 crc32 的值，然后把剩下的 3byte 和这个 crc32 进行 xor，结果再进行查表，可是查表法是查表得到一个 crc32 的值，提取出最开始 1byte，把剩下的 1byte 和这个 1byte crc32 进行 xor，结果进行查表，然后 xor 上次的 CRC32 值去掉开头 1byte，可是结果是一样的，真的好奇怪
|
|
26
ZhaoHuiLiu 2021-04-25 17:23:03 +08:00
|
|
27
quxinna OP @ZhaoHuiLiu 我把初始值 INIT 和结果异或值 XOROUT 都设为了 0，不影响结果的正确性，我只是搞不懂
operator^=(var>>24) var=(crc32_table_normal[operator])^(var<<8)&0xffffffff 是什么意思 |
|
28
ZhaoHuiLiu 2021-04-25 19:11:30 +08:00
我建议你看 C 语言，这个 python 语言资料还没 C 语言多，python 也只是个玩具。
|
|
29
quxinna OP @ZhaoHuiLiu 计算 0x010x02 的 crc32 值
1 的 crc32 值 0x4c11db7 提取最高位 1byte 4，和 2 进行 xor 结果 6 查表 crc32 值 0x1a864db2，1 的 crc32 值去掉最高位 1byte，低位补 0 0xc11db700，和 2 的 crc32 值 0x1A864DB2 xor 得到 0xdb9bfab2 结果是正确的，但是暂时不知道和手算法如何等同 |
|
30
quxinna OP @quxinna
100000010 0x104c11db7 10000001000000000000000000000000000000000 100000100110000010001110110110111 11011000001000111011011011100000000 100000100110000010001110110110111 1011010010000110011100000111011100 100000100110000010001110110110111 11011011100110111111101010110010 结果是一样的，但是不知道怎么会是一样 |
 |
31
jhdsgfww 2021-04-26 09:23:34 +08:00
好久之前写过一篇博文说过 CRC 的计算，里面有 CRC32 的查表计算。https://blog.zmyme.com/posts.html?id=crc-principles-and-algorithms
（但是现在再看已经头大了.....) |
|
32
quxinna OP @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 种可能性，请教高手对吗？ |
|
33
quxinna OP @3dwelcome var=(crc32_table_normal[operator])^(var<<8) 中当 var=0xffffffff，第一次计算的时候会异或 0xffffff00 吗？ operator^=(var>>24)，operator^ff，那么并不是输入数据反转啊？
|
|
34
quxinna OP @quxinna var 的 0xffffffff 值，提取最高位 1byte 0xff，和 01 进行 xor 结果，查表 crc32 值，var 的 0xffffffff 值去掉最高位 1byte，低位补 0 0xffffff00，和查表 crc32 值 xor 得到结果，原来是输入数据反转
|
|
35
quxinna OP |
|
36
quxinna OP 我发现这个问题和引体向上有关
|
|
37
quxinna OP crc32 表存在于 gmail 帮助文档中
|
Select Language