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

Re: Fast crc8

Post by kevinkk525 » Thu Feb 11, 2021 6:17 am

I don't really know how to choose another polynome for 8 bits :roll:
I thought this could be it: x^8+ x^6 + x^4 + x^3 + 1

But I don't see how I get to the polynome byte from that :?:
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 » Thu Feb 11, 2021 7:53 am

x^8+ x^6 + x^4 + x^3 + 1 = (2^8) + 2^6 + 2^4 + 2^3 + 2^0 = 0b01011001

The x^8 = 2^8 bit is ignored.

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

Re: Fast crc8

Post by kevinkk525 » Thu Feb 11, 2021 8:36 am

Thanks, generated a new table with this! looks good.
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode

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

Re: Fast crc8

Post by kevinkk525 » Thu Feb 11, 2021 7:24 pm

How do I get to crc4 from this:

Code: Select all

def crc8(*args, initial_value=0):
    _sum = initial_value
    table = _table
    for arg in args:
        for byte in arg:
            _sum = table[_sum ^ byte]
    return _sum
Since you created a script for the tables, you probably have an example code too?
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 » Thu Feb 11, 2021 7:43 pm

Nibble-wise, like here:

Code: Select all

    for v in msg:
        nibble = (v >> 4) & 0xf
        crc = crc4_tab[crc] ^ nibble

        nibble = v & 0xf
        crc = crc4_tab[crc] ^ nibble
    crc = crc4_tab[crc]  # padding nibble
Obviously there is not need for the interim store to the variable nibble. it's just for clarity. This has a post-processing step, which is sometimes requested, sometimes not. Some use cases have also a specific start value for the crc. To know that, you need a description and a handful of test data pairs (data + crc).

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

Re: Fast crc8

Post by kevinkk525 » Thu Feb 11, 2021 7:57 pm

Thanks a lot! Interestingly this crc4 algorithm needs twice the time of my crc8 lookup table algorithm :?
On a 400Byte bytearray crc8 takes 2.5ms, this crc4 takes 6ms.
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 » Thu Feb 11, 2021 8:00 pm

That's because it has two CRC steps per byte, and the nibble extraction. But usually the messages are shorter.

Edit: As per general use:
4 bit CRC is good for up to four nibbles = 2 bytes
6 bit CRC is good for up to eleven 6 bit data chunks
8 bit CRC is good for up to 64 bytes

n bit CRC is good for messages up to (2^(n + 1) - 1) bits.

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

Re: Fast crc8

Post by kevinkk525 » Thu Feb 11, 2021 8:02 pm

yeah the message is 4bit vs 8bit but if it takes longer, it won't help the transmission speed. Sending an additional byte takes 80us so it's faster to just send more.
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 » Thu Feb 11, 2021 8:12 pm

See my edit in the previous post about suitable message sizes vs. CRC type.

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

Re: Fast crc8

Post by kevinkk525 » Thu Feb 11, 2021 10:04 pm

oh well.. then I would need a crc16 for up to 500Bytes? ... I just want some fast way to recognize garbae on my uart. Shouldn't crc8 be enough for that? Or is it recommended to use crc16?
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode

Post Reply