V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
quxinna
V2EX  ›  程序员

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

  •  
  •   quxinna ·
    quxinna · 2021-04-23 13:39:12 +08:00 · 3800 次点击
    这是一个创建于 1061 天前的主题,其中的信息可能已经有所发展或是发生改变。
    看了这个视频发现 CRC-8 可以通过查表法查,方法是查表得到的 CRC-8 值 XOR 输入的数据,得到的数值作为表的索引找到新的 CRC 值不断循环得到最终的 CRC-8 值,但是 CRC-32 查表法要不止 256 个索引吧,那 CRC-32 查表法不就不存在吗
    37 条回复    2022-02-27 06:58:44 +08:00
    3dwelcome
        1
    3dwelcome  
       2021-04-23 13:46:04 +08:00
    你可以看这个页面 http://www.zorc.breitbandkatze.de/crc.html

    所谓 CRC-8 和 CRC-32 区别,也就是 order 不一样,查表是一样的。
    quxinna
        2
    quxinna  
    OP
       2021-04-23 14:42:36 +08:00
    @3dwelcome 什么是 order ?查表为什么 CRC-32 和 CRC-8 都是 256 个?但是 CRC-32 是 32 位 CRC-8 是 8 位,一次只能计算 8 位啊
    3dwelcome
        3
    3dwelcome  
       2021-04-23 15:06:06 +08:00
    order 是次方的意思,CRC 原理就是多项式校验和,CRC-8 是单次计算最大 8 次方,CRC-32 是单次计算最大 32 次方。

    查找表的本意是把多项式累加这个预处理过程先算一遍,和处理最终值大小没什么关系。因为对于输入的校验数据,都是按照 bit-by-bit 处理的,就算查找表也一样。
    quxinna
        4
    quxinna  
    OP
       2021-04-23 16:27:18 +08:00
    @3dwelcome 但是表不是有一个索引吗?这个索引从哪里来?
    3dwelcome
        5
    3dwelcome  
       2021-04-23 16:59:04 +08:00
    @quxinna 你没懂我的意思,索引是 256 个,说明是对数据 8 个 bit 进行处理,也就是每次处理一个 byte 。
    你也可以改成 4 个 bit 一次建表,那就是 lookuptable[16]。
    和计算的 order 没关系。
    quxinna
        6
    quxinna  
    OP
       2021-04-23 17:35:13 +08:00
    @3dwelcome 但是 CRC-32 的表里的元素是 32 位的,一次不可能只处理 8 个 bit 吧?
    3dwelcome
        7
    3dwelcome  
       2021-04-23 18:53:21 +08:00
    @quxinna 说了数据是一个 bit 一个 bit 处理的,和元素有多少位没关系,表格仅仅只是为了加速运算,所以 256 个数组来加速一个字节,已经足够了。
    元素是 32 位,说明最终的累加结果是 CRC-32 位的,你要把中间结果都加起来,肯定不能只用 8 位了。如果元素是 64 位,那就是 CRC-64 位算法。
    quxinna
        8
    quxinna  
    OP
       2021-04-23 23:43:18 +08:00
    @3dwelcome 主题中 YouTube 视频为什么 Index=CRC XOR Input Data?
    3dwelcome
        9
    3dwelcome  
       2021-04-24 02:22:31 +08:00
    @quxinna " 视频为什么 Index=CRC XOR Input Data?"正常来说,不用加速表,一个 byte 有 8bit, 每个 bit 都是有可能算一次异或的(视具体多项式而定)。
    加速表把这个结果预计算后保存起来,那么现在处理一个 byte,仅需要算一次异或,大大降低了总体计算量。
    yolee599
        10
    yolee599  
       2021-04-24 11:11:48 +08:00 via Android
    查表属于用空间换时间的算法,理论上所有 crc 都可以通过查表法计算
    tempdban
        11
    tempdban  
       2021-04-24 12:21:47 +08:00 via Android
    我要不要给你贴代码…
    quxinna
        12
    quxinna  
    OP
       2021-04-24 12:23:29 +08:00
    @tempdban 贴了解释一下吧,我看不太懂代码,只知道皮毛,例如这个 BSD 的 CRC32 代码我就没有看懂。http://web.mit.edu/freebsd/head/sys/libkern/crc32.c
    ZhaoHuiLiu
        13
    ZhaoHuiLiu  
       2021-04-24 17:51:48 +08:00
    所有的 CRC 算法都可以生成表来查询。。。。
    从 CRC4 到 CRC64 都可以通过表,你可以到 Github 搜索算法就知道了。。。
    quxinna
        14
    quxinna  
    OP
       2021-04-24 17:57:10 +08:00
    @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
        15
    quxinna  
    OP
       2021-04-24 18:00:59 +08:00
    @quxinna 这个表好像是 4294967296 个元素,不是 256 个元素
    quxinna
        16
    quxinna  
    OP
       2021-04-24 23:53:45 +08:00
    @3dwelcome 能不能帮忙解释一下这段 python 代码是如何查表的?
    https://github.com/221294583/crc32
    3dwelcome
        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)
    3dwelcome
        18
    3dwelcome  
       2021-04-25 00:30:35 +08:00   ❤️ 1
    CRC32,严格来说是 33 位 bit 的多项式,但是最前面一直是 1(和计算机里的 IEEE 浮点格式一样,Fraction 部分永远是 1 开头,干脆去掉,这叫隐含位),去完后,刚好凑齐 32bit 一个整型来保存多项式。

    所以 CRC32 上面建表算法里,才会有那个比较奇怪的 if (operator & 0x80000000) != 0 这行。
    quxinna
        19
    quxinna  
    OP
       2021-04-25 11:59:35 +08:00
    @3dwelcome 0x80000000 是 32 位的 10000000000000000000000000000000,用于检查数据是否是 32 位,不够的话需要补位
    quxinna
        20
    quxinna  
    OP
       2021-04-25 12:39:21 +08:00
    @3dwelcome var=(crc32_table_normal[operator])^(var<<8)&0xffffffff 这句代码是什么意思?
    quxinna
        21
    quxinna  
    OP
       2021-04-25 12:40:49 +08:00
    @3dwelcome for bit in range(8) 和 operator <<= 1 等于补足 8 位,并不仅仅是去掉最高位
    ZhaoHuiLiu
        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 大小的数组
    quxinna
        23
    quxinna  
    OP
       2021-04-25 14:50:02 +08:00
    @ZhaoHuiLiu var=(crc32_table_normal[operator])^(var<<8)&0xffffffff 这句代码是什么意思?
    ZhaoHuiLiu
        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 数值。
    quxinna
        25
    quxinna  
    OP
       2021-04-25 17:05:16 +08:00
    @ZhaoHuiLiu 可是这样查表法就和手算法有矛盾,手算法是先查表计算出第 1byte 的 crc32 的值,然后把剩下的 3byte 和这个 crc32 进行 xor,结果再进行查表,可是查表法是查表得到一个 crc32 的值,提取出最开始 1byte,把剩下的 1byte 和这个 1byte crc32 进行 xor,结果进行查表,然后 xor 上次的 CRC32 值去掉开头 1byte,可是结果是一样的,真的好奇怪
    ZhaoHuiLiu
        26
    ZhaoHuiLiu  
       2021-04-25 17:23:03 +08:00
    @quxinna

    crc32 默认值就是 0xffffffff 这个值。。。你传递进行去的数据和这个值做运算
    quxinna
        27
    quxinna  
    OP
       2021-04-25 19:08:27 +08:00
    @ZhaoHuiLiu 我把初始值 INIT 和结果异或值 XOROUT 都设为了 0,不影响结果的正确性,我只是搞不懂

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

    是什么意思
    ZhaoHuiLiu
        28
    ZhaoHuiLiu  
       2021-04-25 19:11:30 +08:00
    我建议你看 C 语言,这个 python 语言资料还没 C 语言多,python 也只是个玩具。
    quxinna
        29
    quxinna  
    OP
       2021-04-25 20:41:50 +08:00
    @ZhaoHuiLiu 计算 0x010x02 的 crc32 值
    1 的 crc32 值 0x4c11db7 提取最高位 1byte 4,和 2 进行 xor 结果 6 查表 crc32 值 0x1a864db2,1 的 crc32 值去掉最高位 1byte,低位补 0 0xc11db700,和 2 的 crc32 值 0x1A864DB2 xor 得到 0xdb9bfab2
    结果是正确的,但是暂时不知道和手算法如何等同
    quxinna
        30
    quxinna  
    OP
       2021-04-25 21:44:56 +08:00
    @quxinna
    100000010
    0x104c11db7

    10000001000000000000000000000000000000000
    100000100110000010001110110110111

    11011000001000111011011011100000000
    100000100110000010001110110110111

    1011010010000110011100000111011100
    100000100110000010001110110110111

    11011011100110111111101010110010

    结果是一样的,但是不知道怎么会是一样
    jhdsgfww
        31
    jhdsgfww  
       2021-04-26 09:23:34 +08:00
    好久之前写过一篇博文说过 CRC 的计算,里面有 CRC32 的查表计算。https://blog.zmyme.com/posts.html?id=crc-principles-and-algorithms
    (但是现在再看已经头大了.....)
    quxinna
        32
    quxinna  
    OP
       2021-04-27 22:31:18 +08:00
    @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
        33
    quxinna  
    OP
       2021-05-08 17:48:25 +08:00
    @3dwelcome var=(crc32_table_normal[operator])^(var<<8) 中当 var=0xffffffff,第一次计算的时候会异或 0xffffff00 吗? operator^=(var>>24),operator^ff,那么并不是输入数据反转啊?
    quxinna
        34
    quxinna  
    OP
       2021-05-08 18:06:18 +08:00
    @quxinna var 的 0xffffffff 值,提取最高位 1byte 0xff,和 01 进行 xor 结果,查表 crc32 值,var 的 0xffffffff 值去掉最高位 1byte,低位补 0 0xffffff00,和查表 crc32 值 xor 得到结果,原来是输入数据反转
    quxinna
        35
    quxinna  
    OP
       2021-07-12 19:30:01 +08:00
    quxinna
        36
    quxinna  
    OP
       2021-07-22 13:51:54 +08:00
    我发现这个问题和引体向上有关
    quxinna
        37
    quxinna  
    OP
       2022-02-27 06:58:44 +08:00
    crc32 表存在于 gmail 帮助文档中
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5417 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 08:15 · PVG 16:15 · LAX 01:15 · JFK 04:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.