快速CRC32算法实现逆序位

约翰尼·埃格兰

我正在使用一个微控制器,该控制器可实时计算上传到闪存中的数据的CRC32校验和。反过来,通过在所有数据上传后验证结果校验和,可以将其用于验证上传正确。

唯一的问题是,微控制器在通过其他标准的crc32计算运行时会反转输入字节的位顺序。这又意味着我需要反转编程主机上数据中的每个字节,以便计算要验证的CRC32和。由于编程主机有些受限制,所以这相当慢。

我认为,如果可以修改CRC32查找表,而无需反转位顺序就可以执行查找,则验证算法的运行速度将提高许多倍。但我似乎无法找到一种方法来做到这一点。

为了阐明字节反转,我需要按以下方式更改输入字节:

01 02 03 04-> 80 40 C0 20

当然,以二进制表示形式查看反转要容易得多:

00000001 00000010 00000011 00000100-> 10000000 01000000 11000000 00100000

编辑这是我用来验证CRC32计算正确性的PoC Python代码,但是这会使每个字节反转(即慢速方式)。

EDIT2我还尝试了使用标准LUT CRC32算法生成排列查找表的失败尝试。

代码首先输出正确的参考CRC值,然后输出错误的LUT计算出的CRC。

import binascii

CRC32_POLY = 0xEDB88320

def reverse_byte_bits(x):
    '''
    Reverses the bit order of the giveb byte 'x' and returns the result
    '''
    x = ((x<<4) & 0xF0)|((x>>4) & 0x0F)
    x = ((x<<2) & 0xCC)|((x>>2) & 0x33)
    x = ((x<<1) & 0xAA)|((x>>1) & 0x55)
    return x

def reverse_bits(ba, blen):
    '''
    Reverses all bytes in the given array of bytes
    '''
    bar = bytearray()
    for i in range(0, blen):
        bar.append(reverse_byte_bits(ba[i]))
    return bar

def crc32_reverse(ba):
    # Reverse all bits in the
    bar = reverse_bits(ba, len(ba))

    # Calculate the CRC value
    return binascii.crc32(bar)

def gen_crc_table_msb():
    crctable = [0] * 256

    for i in range(0, 256):
        remainder = i
        for bit in range(0, 8):
            if remainder & 0x1:
                remainder = (remainder >> 1) ^ CRC32_POLY
            else:
                remainder = (remainder >> 1)

        # The correct index for the calculated value is the reverse of the index
        ix = reverse_byte_bits(i)
        crctable[ix] = remainder

    return crctable

def crc32_revlut(ba, lut):
    crc = 0xFFFFFFFF
    for x in ba:
        crc = lut[x ^ (crc & 0xFF)] ^ (crc >> 8)
    return ~crc

# Reference test which gives the correct CRC
test = bytearray([1, 2, 3, 4, 5, 6, 7, 8])
crcrev = crc32_reverse(test)
print("0x%08X" % (crcrev & 0xFFFFFFFF))

# Test using permutated lookup table, but standard CRC32 LUT algorithm
lut = gen_crc_table_msb()
crctst = crc32_revlut(test, lut)
print("0x%08X" % (crctst & 0xFFFFFFFF))

有没有人暗示如何做到这一点?

哈罗德

通过逆转crc“流动”的逻辑,可以避免主计算中的逆转。因此,crc >> 8我们将crc << 8查找LUT索引的crc的低字节而不是与Xc的低字节进行异或。像这样:

def reverse_dword_bits(x):
    '''
    Reverses the bit order of the given dword 'x' and returns the result
    '''
    x = ((x<<16) & 0xFFFF0000)|((x>>16) & 0x0000FFFF)
    x = ((x<<8) & 0xFF00FF00)|((x>>8) & 0x00FF00FF)
    x = ((x<<4) & 0xF0F0F0F0)|((x>>4) & 0x0F0F0F0F)
    x = ((x<<2) & 0xCCCCCCCC)|((x>>2) & 0x33333333)
    x = ((x<<1) & 0xAAAAAAAA)|((x>>1) & 0x55555555)
    return x

def gen_crc_table_msb():
    crctable = [0] * 256

    for i in range(0, 256):
        remainder = i
        for bit in range(0, 8):
            if remainder & 0x1:
                remainder = (remainder >> 1) ^ CRC32_POLY
            else:
                remainder = (remainder >> 1)

        # The correct index for the calculated value is the reverse of the index
        ix = reverse_byte_bits(i)
        crctable[ix] = reverse_dword_bits(remainder)

    return crctable

def crc32_revlut(ba, lut):
    crc = 0xFFFFFFFF
    for x in ba:
        crc = lut[x ^ (crc >> 24)] ^ ((crc << 8) & 0xFFFFFFFF)
    return reverse_dword_bits(~crc)

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章