Fast crc8
Re: Fast crc8
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.
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.
Re: Fast crc8
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
Re: Fast crc8
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.
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,
Code: Select all
@micropython.native
def hash(str):
result = 0xceed
for v in str:
result = ((result << 7) - result + v) & 0xffff
return result
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,
Re: Fast crc8
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.
-
- Posts: 969
- Joined: Sat Feb 03, 2018 7:02 pm
Re: Fast crc8
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.
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:
Now I'm a bit confused, I thought the RP2040 already needed only 1.7ms for the hash:
But great optimization. 1.9ms is a good time.
Didn't even think about that.. I always reset the crc/hash bytes to 0 before checking the crc But that operation is rather short so I don't think that makes more than 300us of a difference.Roberthh wrote: ↑Sat Feb 13, 2021 5:07 pmOne 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.
Kevin Köck
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode
Re: Fast crc8
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.Now I'm a bit confused, I thought the RP2040 already needed only 1.7ms for the hash:
Re: Fast crc8
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.
- 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.
-
- Posts: 969
- Joined: Sat Feb 03, 2018 7:02 pm
Re: Fast crc8
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.
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
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode
Re: Fast crc8
Yes. That's a standard Python method of the builtins class. Just try:It has?
hash("abcdef")
-
- Posts: 969
- Joined: Sat Feb 03, 2018 7:02 pm
Re: Fast crc8
Sorry, I was of course not questioning your knowledge, just wondering about something I couldn't find
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.
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
Micropython Smarthome Firmware (with Home-Assistant integration): https://github.com/kevinkk525/pysmartnode