用于反转位顺序的快速 CRC32 算法

Question

我正在使用微控制器计算我上传到闪存的数据的 CRC32 校验和。通过在所有数据上传后验证生成的校验和，这又可以用于验证上传是否正确。

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

我认为如果可以修改 CRC32 查找table，这样我就可以在不颠倒位顺序的情况下进行查找，验证算法会快运行很多倍。但我似乎想不出办法。

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

01 02 03 04 -> 80 40 C0 20

当然二进制表示更容易看到反转：

00000001 00000010 00000011 00000100 -> 10000000 01000000 11000000 00100000

编辑这是我用来验证 CRC32 计算正确性的 PoC Python 代码，但是这会反转每个字节（a.e 慢速方式）。

EDIT2 我还包括了我尝试生成排列查找 table 并使用标准 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))

有没有人知道如何做到这一点？

Answer 1

把crc哪路的逻辑反过来"streams"，就可以避免主计算反了。因此，crc >> 8 将是 crc << 8，而不是与 LUT 索引的 crc 的底部字节进行异或，我们取顶部。像这样：

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)

用于反转位顺序的快速 CRC32 算法

Fast CRC32 algorithm for reversed bit order

algorithm

crc32