Fast crc8

[kevinkk525]

I'm currently using a crc8 python implementation on the esp32 but it easily takes 1-4ms to calculate the crc. So I'm wondering if there is a better option in micropython for a simple crc/checksum for UART communications.

Current code:

Code: Select all

def crc8(*args, initial_value=0):
    crc = initial_value
    for datagram in args:
        # Iterate bytes in data
        for byte in datagram:
            # Iterate bits in byte
            for _ in range(0, 8):
                if (crc >> 7) ^ (byte & 0x01):
                    crc = ((crc << 1) ^ 0x07) & 0xFF
                else:
                    crc = (crc << 1) & 0xFF
                # Shift to next bit
                byte = byte >> 1
    return crc

[uCTRL]

Search on the net for example with lookup table, it is quicker than doing loop calculations.
crc8 is not very big.

[kevinkk525]

Thanks that was a good tip.

I found one with a lookup table and stripped it down for micropyhton:

Code: Select all

_table = b'\x00\x07\x0e\t\x1c\x1b\x12\x158?61$#*-pw~ylkbeHOFATSZ]\xe0\xe7\xee\xe9\xfc\xfb\xf2\xf5\xd8\xdf\xd6\xd1\xc4\xc3\xca\xcd\x90\x97\x9e\x99\x8c\x8b\x82\x85\xa8\xaf\xa6\xa1\xb4\xb3\xba\xbd\xc7\xc0\xc9\xce\xdb\xdc\xd5\xd2\xff\xf8\xf1\xf6\xe3\xe4\xed\xea\xb7\xb0\xb9\xbe\xab\xac\xa5\xa2\x8f\x88\x81\x86\x93\x94\x9d\x9a\' ).;<52\x1f\x18\x11\x16\x03\x04\r\nWPY^KLEBohafst}z\x89\x8e\x87\x80\x95\x92\x9b\x9c\xb1\xb6\xbf\xb8\xad\xaa\xa3\xa4\xf9\xfe\xf7\xf0\xe5\xe2\xeb\xec\xc1\xc6\xcf\xc8\xdd\xda\xd3\xd4ing`ur{|QV_XMJCD\x19\x1e\x17\x10\x05\x02\x0b\x0c!&/(=:34NI@GRU\\[vqx\x7fjmdc>907"%,+\x06\x01\x08\x0f\x1a\x1d\x14\x13\xae\xa9\xa0\xa7\xb2\xb5\xbc\xbb\x96\x91\x98\x9f\x8a\x8d\x84\x83\xde\xd9\xd0\xd7\xc2\xc5\xcc\xcb\xe6\xe1\xe8\xef\xfa\xfd\xf4\xf3'


@Profiler.measure
def crc82(*args):
    _sum = 0
    table = _table
    for arg in args:
        for byte in arg:
            _sum = table[_sum ^ byte]
    return _sum

I transformed the table from a list to a bytes object because bytes objects don't get loaded into RAM while a list would. This reduced the time required to calculate the crc from 2.5ms to 740us.
However, the result is different, but I guess that's to be expected (and no problem if both sides use the same function)? The old function returned a crc of 170 and this one 39.

[rcolistete]

What about this CRC8 ?
https://github.com/rcolistete/MicroPyth ... 615_driver
https://github.com/rcolistete/MicroPyth ... lx90615.py

Code: Select all

def _crc8(self, icrc, data):
    crc = icrc ^ data
    for _ in range(8):
        crc <<= 1
        if crc & 0x0100:
            crc ^= 0x07
        crc &= 0xFF
    return crc

[kevinkk525]

Thanks for the suggestion but for bytearrays of 40 bytes that code needed twice the time of the lookup table. (1ms vs 2ms)

[Roberthh]

I made a littl script which can create the crc tables for arbitrary polynomes and bit lengths. The code below is juts raw and contains two sections for a 6 bit and 4 bit polynome. But can easily be adapted.

Code: Select all

def bitreverse(v, bits):
    o = 0
    for i in range(bits):
        o = (o << 1) | (v & 1)
        v >>= 1
    return o

bits = 6
entries = 2 ** bits
uprmask  = 1 << (bits - 1)  # Masking the upper bit of the crc
crcmask = entries - 1
crctab = bytearray(entries)

polynome = 0b011001  # (x^6 +) x^4 + x^3 + 1  (1 is x^0 -> lowest bit set, x^6 is implicit set)

for i in range(entries):
    crc = i
    for _ in range(bits):
        crc = ((crc << 1) ^ (polynome if (crc & uprmask) else 0))
    crctab[i] = crc & crcmask

print("crc%d_tab = (" % bits, end="")
for i in range(entries):
    print("%d" % crctab[i], end="")
    if (i == (entries - 1)):
        print(")")
    elif ((i % 16) == 15):
        print(",\n            ", end="")        
    else:
        print(", ", end="")

# -----------------------------------------------------

bits = 4
uprmask  = 1 << (bits - 1)  # Masking the upper bit of the crc
entries = 2 ** bits
crcmask = entries - 1
crctab = bytearray(entries)

polynome = 0b1101  # (x^4 +) x^3 + x^2 + 1  (1 is x^0 -> lowest bit set, x^4 is implicit set)

for i in range(entries):
    crc = i
    for _ in range(bits):
        crc = ((crc << 1) ^ (polynome if (crc & uprmask) else 0))
    crctab[i] = crc & crcmask

print("crc%d_tab = (" % bits, end="")
for i in range(entries):
    print("%d" % crctab[i], end="")
    if (i == (entries - 1)):
        print(")")
    elif ((i % 16) == 15):
        print(",\n            ", end="")        
    else:
        print(", ", end="")

[kevinkk525]

That's nice but I'm not sure what exactly to do with it. Can it replace the table I'm using? It was created for crc8, does that code work with tables for 6 or 4 too? Sorry I'm not too familiar with how crc works, I just use it anyway

[Roberthh]

You can use the tables generated by my code snippets in your example crc code. Just set bits to 8 and specify the respective polynome, and it will produce a 256 sized table. If the crc is over 4 or 6 bit data, you may have to split the in-data up to feed it into your code.

The code you showed uses one specific polynome. But there are different one that can be used, which has to specified the datasheet of a device. And in addition there are variants on whether there is a pre- or post-calculation step. So it's always some trial & error.

[pythoncoder]

I was going to point you at a faster way to bit reverse until I noticed you don't actually use the function

[Roberthh]

Still useful. I mad es to whole script for preparing data. So speed was not an issue. The context was generating test messages for the SENT protocol.