Fast CRC32 algorithm for reversed bit order

Question

I am working with a micro controller which calculates the CRC32 checksum of data I upload to it's flash memory on the fly. This can in turn be used to verify that the upload was correct, by verifying the resulting checksum after all data is uploaded.

The only problem is that the Micro Controller reverses the bit order of the input bytes when it's run through the otherwise standard crc32 calculation. This in turn means I need to reverse every byte in the data on the programming host in order to calculate the CRC32 sum to verify. As the programming host is somewhat constrained, this is quite slow.

I figure that if it's possible to modify the CRC32 lookuptable so I can do the lookup without having to reverse the bit order, the verification algorithm would run many times faster. But I seem unable to figure out a way to do this.

To clarify the byte reversal, I need to change the input bytes following way:

01 02 03 04 -> 80 40 C0 20

It's a lot easier to see the reversal in binary representation of course:

00000001 00000010 00000011 00000100 -> 10000000 01000000 11000000 00100000

Edit Here is the PoC Python code I use to verify the correctness of the CRC32 calculation, however this reverses each byte (a.e the slow way).

EDIT2 I've also included my failed attempt to generate a permutated lookup table, and using a standard LUT CRC32 algorithm.

The code spits out the correct reference CRC value first, and then the wrong LUT calculated CRC afterwards.

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))

Does anyone have any hints to how this could be done?

Loop through the input bytes in reverse order, and use each byte as an index into a 256-element lookup table? — meowgoesthedog
The table indexed by "non-reversed" bytes is the same table but permuted according to the bit-reversal permutation — harold
post your code. that will document your problem and help us to understand it. — stefan
The bytes are sent in the correct order to the MCU, but the bits in each byte needs to be reversed when calculating CRC. I can append the "slow code" if that clarifies stuff some more. — Johnny Egeland
harold: That was my initial idea as well. Calculate the CRC32 lookup table as normal, but permutate the table using the bit-reversed index. However, the resulting checksum is then not correct. — Johnny Egeland

harold harold · Accepted Answer · 2018-08-15T13:00:50

By reversing the logic of which way the crc "streams", the reverse in the main calculation can be avoided. So instead of crc >> 8 there would be crc << 8 and instead of XORing with the bottom byte of the crc for the LUT index we take the top. Like this:

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)

Fast CRC32 algorithm for reversed bit order

1 Answers