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.
User avatar
Roberthh
Posts: 2462
Joined: Sat May 09, 2015 4:13 pm
Location: Rhineland, Europe

Re: Fast crc8

Post by Roberthh » Sat Feb 13, 2021 3:22 pm

I tested it for my own interest. I replaced the byte. The numbers of bits changed depend on the way, the new byte was chosen and the previous content. All in all, it was between 1 and 8 bits changed.
Still, Peter is right in that pure transmission errors will be very rare. More likely are message frame errors: messages too short or too long.

P.S.: On RP2040, the calculation times I see are not that different, 3 vs. 4 ms for a 400 byte data block. But the hash uses way less data. Still the 3k for the CRC table seems large. The net size should be 512 bytes.

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

Re: Fast crc8

Post by Roberthh » Sat Feb 13, 2021 3:48 pm

A slight modification of the hash code made it better in detecting errors, albeit a little bit slower. Still not at the CRC level in both aspects

Code: Select all

@micropython.native
def hash(str):
    result = 0xceed

    for v in str:
        result = ((result * 227  + 1) ^ v) & 0xffff
    return result

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

Re: Fast crc8

Post by Roberthh » Sat Feb 13, 2021 4:09 pm

And another one makes it even faster on rp2040, replacing the multiplication by shift and subtraction. On RP2040 from 3.3ms to 1.9 ms.

Code: Select all

@micropython.native
def hash(str):
    result = 0xceed

    for v in str:
        result = ((result << 7) - result + v) & 0xffff
    return result
The problem is here the missing support for hardware multiplication in the firmware. That was already addressed.
On ESP32 you can write:
result = (result *127 + v) & 0xffff
The code looks now pretty similar to the table based CRC16. Only it uses less RAM and is somewhat faster,

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

Re: Fast crc8

Post by Roberthh » Sat Feb 13, 2021 5:07 pm

One note about CRC usage. The CRC is usually appended to the message, low order byte first. That makes checking easy, because when you then compute the CRC again over the whole message, including the CRC, the result will be 0 for a matching CRC. That may compensate for a slightly longer computation time.

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

Re: Fast crc8

Post by kevinkk525 » Sat Feb 13, 2021 7:42 pm

Roberthh wrote:
Sat Feb 13, 2021 3:22 pm
Still, Peter is right in that pure transmission errors will be very rare. More likely are message frame errors: messages too short or too long.
Yeah I might be wasting time for a situation that is very unlikely to happen.. Guess I'll make it configurable so people can decide if they want to use a crc/hash or prefer some higher speed.
Roberthh wrote:
Sat Feb 13, 2021 3:22 pm
P.S.: On RP2040, the calculation times I see are not that different, 3 vs. 4 ms for a 400 byte data block. But the hash uses way less data. Still the 3k for the CRC table seems large. The net size should be 512 bytes.
About the net size: You're of course right, the array shouldn't take more than 512 Bytes. I was just testing with gc.collect();gc.mem_free() which might have been a bit inaccurate.
About the speed:
Roberthh wrote:
Sat Feb 13, 2021 4:09 pm
And another one makes it even faster on rp2040, replacing the multiplication by shift and subtraction. On RP2040 from 3.3ms to 1.9 ms.
Now I'm a bit confused, I thought the RP2040 already needed only 1.7ms for the hash:
Roberthh wrote:
Fri Feb 12, 2021 8:34 pm
In my test, the numbers on a rp2040 for 400 bytes are
4.6 ms for the non.table CRC
4.0 ms for the table based crc, table locally linked
1.7 ms for the hash without table
2.2 ms for the hash with table
But great optimization. 1.9ms is a good time.


Roberthh wrote:
Sat Feb 13, 2021 5:07 pm
One note about CRC usage. The CRC is usually appended to the message, low order byte first. That makes checking easy, because when you then compute the CRC again over the whole message, including the CRC, the result will be 0 for a matching CRC. That may compensate for a slightly longer computation time.
Didn't even think about that.. I always reset the crc/hash bytes to 0 before checking the crc :lol: But that operation is rather short so I don't think that makes more than 300us of a difference.
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 » Sat Feb 13, 2021 8:13 pm

Now I'm a bit confused, I thought the RP2040 already needed only 1.7ms for the hash:
That was the surprise of the day. I hope it's not related to updating my RP2040 with new firmware. The CRC times stayed as they were.

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

Re: Fast crc8

Post by Roberthh » Sun Feb 14, 2021 7:11 am

Another remark: There is a built-in hash function in micropython, which is obviously much faster (<200µs vs. ~2000µs fro 400 bytes). Two obstacles:

- it works on strings and bytes objects only
- for some strange reasons the length is set to 1 byte for rp2040 and to 2 bytes on ESP32. The underlying code is the same.

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

Re: Fast crc8

Post by kevinkk525 » Sun Feb 14, 2021 8:26 am

It has? I only found uhashlib which offers sha1 and sha256 which are both considerably longer.

But apart from that weird inconsistency of the amount of returned bytes, I actually don't deal with strings or byte objects. Especially the receiving end of a transmission only does checksums over the received bytearray which is preallocated as a buffer. So if that hash function doesn't work on bytearrays/memoryviews, it's of not much use to me.
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 » Sun Feb 14, 2021 8:38 am

It has?
Yes. That's a standard Python method of the builtins class. Just try:
hash("abcdef")

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

Re: Fast crc8

Post by kevinkk525 » Sun Feb 14, 2021 11:09 am

Sorry, I was of course not questioning your knowledge, just wondering about something I couldn't find :D
Oh built-in, of course, that makes sense.. those don't show up in dir() either..

But could only be useful if it supported bytearrays.
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode

Post Reply