Fast crc8

[Roberthh]

The mentioned limits ensure, that all 1 and 2 bit error are detected. Exceeding it means, that this is not guaranteed. Still many errors will detected. I assume that you have other checks too, like a length check. You could also split your message in shorter blocks with a CCRC byte each.
CRC16 is more time or space consuming, or both. Although there are fast implementations. Some working with two 8bit tables, and somewhere deep in my old projects I found a CRCITT implementation w/o tables. Porting that to Python is straightforward. Note: 010201 is an octal number. You could try to put that into native or viper code, which should run faster.

Code: Select all

INITFCS = 0x0000  # Initial FCS value, to be chosen 

crc = INITFCS;
data = b"The quick red fox jumps over the lazy dog"

for v in data:
    crc = (crc >> 4) ^ (((crc ^ v) & 0x0f) * 0o10201)
    crc = (crc >> 4) ^ ((((crc ^ (v >> 4))) & 0x0f) * 0o10201)

print(hex(crc))

[kevinkk525]

Thank you! I'm a bit wary of adding more overhead with an even bigger/more crc since the communication is already slow enough due to processing time.

I have a few checks in place:
First a START_BYTE is read, then a 6 byte header including the crc8 is being read, which also contains the length of the message. Then the remaining packet is being read. If the length doesn't match -> discard. If the crc of the whole packet doesn't match -> discard. Then I read an END_BYTE and if that doesn't match -> discard.

Since a UART is a rather stable connection and typically doesn't corrupt just a single byte (or is my assumption wrong?) but rather returns complete gibberish if the connection breaks, should these checks be enough to ensure the integrity of the message?

[Roberthh]

UART can corrupt single bytes, a sequence of bytes or produce total gibberish. That depends on the relative timing of sender and receiver. What I have seen is, that if the receiver starts in the middle of a transmission, or drops in between, you will have a few gibberish bytes until is synchronizes again. Single byte or bit error are caused by distortion on the wires, which are not to be expected here. The CRC8 will detect gibberish errors with a probability of 1/256.
In your set-up, the length check is a good means, also the check for magic numbers. Although, the CRC itself is a magic number too. So if message size counts, increasing the CRC is more effective than adding constant magic numbers. Drops in between are unlikely at the ESP32 side due to it's large two level buffering (128 byte UART FIFO + ring buffer) . The RP2040 is a little bit worse. It just has a 64 byte FIFO in the UART (AFAIK). Anyhow drops will be visible as shortened messages.

Anhow: Here is another crc16 which I found on the net. It pre-calculates a table once and then uses table accesses.

Code: Select all

POLYNOMIAL = 0x1021
PRESET = 0

def _initial(c):
    crc = 0
    c = c << 8
    for j in range(8):
        if (crc ^ c) & 0x8000:
            crc = (crc << 1) ^ POLYNOMIAL
        else:
            crc = crc << 1
        c = c << 1
    return crc & 0xffff

_tab = [ _initial(i) for i in range(256) ]

def crc16(str):
    crc = PRESET
    for c in str:
        crc = ((crc & 0xff) << 8) ^ _tab[((crc >> 8) ^ c) & 0xff]
    return crc

print(hex(crc16(data)))

[pythoncoder]

I think it's worth considering the actual use case here. The communication link is between a MicrPython host and an ESP32 over a short distance. In normal use I would expect zero errors.

The need for CRC is to cater for the case where the ESP32 fails: typically this is a spontaneous reboot. This is something which Kevin and myself have found occurs from time to time. There is also the possibility that the ESP might crash, with the code running wild. We haven't encountered this, but I think it should be acknowledged as a possibility.

If failure occurs while a transmission from the ESP32 to the host is in progress, the following may occur - in order of decreasing likelihood.

• The host UART times out waiting on a start bit (highly probable if it reboots).
• The last byte in the message is corrupt with a single or multi bit error. Depending on the receiving UART design this might throw a framing error, or it might just accept the rubbish.
• Total garbage is received (code running wild). This might or might not cause UART exceptions, depending on exactly what the code is doing.

My view is that just about any CRC will pick up these conditions. I would prioritise speed over ability to detect subtle faults.

[Roberthh]

I agree that single bit errors due to distortion on the line are unlikely. Besides the sender seding rubbish for whatever reason or the receiver could drop bytes. That would result either a) in a too short message received (dropped bytes), covered by the length check, or
b) a message long enough or too long, but with unexpected data, which has to be covered by other means.
CRC's are the appropriate method to cater for that. Whether a CRC8 is sufficient in this case, has to be determined. But what I've learned over time is, that one effective measure is better than many small ones.

The error check should include the header, especially the length byte.

[kevinkk525]

Good arguments. Now I'm a bit unsure. Maybe I'll make it configureable Let the user decide.. recipe for disaster?
I guess it could make sense to secure the whole package with a proper crc even if it slows the code down by 4-8ms.

Thanks for the crc16 code!
When I use that code at 400Bytes it takes ~4ms, crc8 takes ~2.7ms. So kind of acceptable. With only 100Bytes the difference is only ~400us. Guess I could live with that. For 1KB the difference is up to 2ms but that's fine too, sending 1kb doesn't happen often.

Only problem is the use of a list because it will reside in RAM and it's a considerably long list, it taks 10kb of RAM! On an esp32 no problem, if I plan on using an esp8266 it will be a problem.
I tried transforming it into a bytes object so it can stay in flash when the module gets frozen (which the client side will likely not, but at least might be an .mpy).
However, to use it I have to change the crc16 code to correctly read the 2 bytes from the bytes object (since I can't just read 16 bits like from the table can I?), which obviously makes the code even slower and is now 2-4ms slower than the original crc16 code.. So a 400Byte message will take 6.5-9ms with this code.. that is just too long.

So crc16 original has a RAM demand of 10kb and crc16 with table as bytes is very slow..

[Roberthh]

Only problem is the use of a list

The crc16 code with precalculated table has a table of 256 shorts. You could put that into an array of shorts as well. Then the line crating _tab would be:

Code: Select all

import array
_tab = array.array("H", [_initial(i) for i in range(256)])

But that may still create an intemediate list.

[Roberthh]

Using the @micropython.native decorator, both variants are equally fast on my ESP32. About 3.8ms for a 410 byte message.

[kevinkk525]

The crc16 code with precalculated table has a table of 256 shorts. You could put that into an array of shorts as well.
But that may still create an intemediate list.

Thanks a lot, didn't think about that solution. It reduced the RAM need to <3kB which is very acceptable.
The speed of crc16 even with @native is 50% slower than crc8 @native but acceptable. For most message the dfiference will be <500us as they are short anyway.
After improving the rest of my code I can now send and receive 400Bytes in 80ms, 100Bytes in 60ms. This seems acceptable.

[Roberthh]

In my tests on ESP32 and rp2040, the nibble wise code w/o table was slightly faster. To recall:

Code: Select all

INITFCS = 0x0000  # Initial FCS value, to be chosen 

crc = INITFCS;
data = b"The quick red fox jumps over the lazy dog"

for v in data:
    crc = (crc >> 4) ^ (((crc ^ v) & 0x0f) * 0o10201)
    crc = (crc >> 4) ^ ((((crc ^ (v >> 4))) & 0x0f) * 0o10201)

print(hex(crc))

Whatever it means, these two codes do not get the same result.