Fast crc8

Discussion about programs, libraries and tools that work with MicroPython. Mostly these are provided by a third party.
Target audience: All users and developers of MicroPython.
kevinkk525
Posts: 875
Joined: Sat Feb 03, 2018 7:02 pm

Fast crc8

Post by kevinkk525 » Tue Feb 09, 2021 9:03 am

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
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode

uCTRL
Posts: 47
Joined: Fri Oct 12, 2018 11:50 pm

Re: Fast crc8

Post by uCTRL » Tue Feb 09, 2021 10:34 am

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

kevinkk525
Posts: 875
Joined: Sat Feb 03, 2018 7:02 pm

Re: Fast crc8

Post by kevinkk525 » Tue Feb 09, 2021 11:11 am

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.
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode

User avatar
rcolistete
Posts: 338
Joined: Thu Dec 31, 2015 3:12 pm
Location: Brazil
Contact:

Re: Fast crc8

Post by rcolistete » Tue Feb 09, 2021 3:37 pm

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
My "MicroPython Samples". My "MicroPython Firmwares" with many options (double precision, ulab, etc).

kevinkk525
Posts: 875
Joined: Sat Feb 03, 2018 7:02 pm

Re: Fast crc8

Post by kevinkk525 » Tue Feb 09, 2021 7:30 pm

Thanks for the suggestion but for bytearrays of 40 bytes that code needed twice the time of the lookup table. (1ms vs 2ms)
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode

User avatar
Roberthh
Posts: 2462
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: Fast crc8

Post by Roberthh » Wed Feb 10, 2021 9:34 am

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
Posts: 875
Joined: Sat Feb 03, 2018 7:02 pm

Re: Fast crc8

Post by kevinkk525 » Wed Feb 10, 2021 10:58 am

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 :D
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode

User avatar
Roberthh
Posts: 2462
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: Fast crc8

Post by Roberthh » Wed Feb 10, 2021 12:04 pm

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.

User avatar
pythoncoder
Posts: 4940
Joined: Fri Jul 18, 2014 8:01 am
Location: UK
Contact:

Re: Fast crc8

Post by pythoncoder » Wed Feb 10, 2021 1:27 pm

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

User avatar
Roberthh
Posts: 2462
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: Fast crc8

Post by Roberthh » Wed Feb 10, 2021 1:52 pm

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.

Post Reply