-
I'm trying to implement a CRC checksumming check on an AVR microcontroller.
I'm making a 16 bit checksum from up to 35 bytes of data.
I use a 16 item table of uint16_t values to a table driven CRC algorithm.
The algorithm calls:
uint16_t crc_of_byte(uint16_t crc, uint8_t data_byte){
uint8_t i;
i = (crc >> 12) ^ (data_byte >> 4);
crc = pgm_read_dword_near(table + (i & 0x0f)) ^ (crc <<4);
i = (crc >> 12) ^ (data_byte >> 0);
crc = pgm_read_dword_near(table + (i & 0x0f)) ^ (crc <<4);
return crc;
}
for each byte of the up to 35, with the result of the function being fed back in as crc when it run for the next byte of the array it is calculating the CRC of.
But it seems rather slow, quite a lot of clock cycles per byte to the extent that with a 16MHz clock rate my AVR chips are taking about 6.5us per byte to calculate checksums.
I cannot switch to a 256 element table as that would take too much PROGMEM space.
I'm aware of something called a sliced CRC table, which is apparently faster than normal CRC tables, mentioned at https://pycrc.org/pycrc.html . But I tried generating a CRC table by that method using the very useful python script provided, and it wouldn't do it unless I used a 256 element table anyway.
I am not tied to using a particular CRC polynomial, nor even to using a CRC at all, I could try anything which can detect errors and produce a 2 byte "checksum" for an array up to 35 bytes.
What else could I try for error detection? I'd like methods which would do a good job of catching burst errors, and "sliding" errors*, as well as having the largest easily feasible hamming distance (max number of bit flip errors somewhere throughout a message before you can potentially get a bit flip which makes a corrupted message which still passes the check as if it were valid).
Thank You
*By sliding, I mean, imagine the effect on data if a single bit is missed, and everything following shifts earlier by one bit, or if a phantom bit is added and everything afterwards shifts later by one bit.
121,82,96,3
(
01111001,
01010010,
01100000,
00000011
)
could "slide" to, if an error happened that missed the last bit of 121:
120,164,192,6
(
01111000,
10100100,
11000000,
00000110
)
-
https://en.wikipedia.org/wiki/Fletcher%27s_checksum is pretty good for detecting bit errors in short messages. It has a few weaknesses, but those are usually not an issues for real applications.
-
I cannot switch to a 256 element table as that would take too much PROGMEM space.
That seems rather strange as that's only 512 bytes and even the ATTiny25/45/85 series is available with 8K of program space. It will be much faster!
You could switch to a simple xor checksum (multiple CRC-1 streams in parallel), but that won't meet your burst etc requirements.
I don't think you're going to find any algorithm with as good or better protection properties than CRC with lower memory or clock cycles requirements. There's a reason the CRC algorithm is still used after sixty years, though better polynomials are known today than were initially used (e.g. CRC-32C (Castagnoli)).
And of course a 32 bit CRC will give much better protection than a 16 bit CRC.
-
I also like using the fletcher checksum.
It is very fast on MCUs because it is just 2 sum operations. Sure CRC is more efficient in hardware, but that doesn't help unless the MCU has such hardware built in.
-
https://en.wikipedia.org/wiki/Fletcher%27s_checksum is pretty good for detecting bit errors in short messages. It has a few weaknesses, but those are usually not an issues for real applications.
Fletcher and Adler are certainly a lot cheaper to compute than CRC, for slightly worse but maybe adequate protection.
You could also look into the much more recent murmurhash, cityhash, farmhash series developed primarily for very fast hashing of relatively short keys for hash tables. There's no reason they can't also be used for data transmission. I guess one thing to watch out for is that they pretty much assume shifts by arbitrary amounts are fast, which is not the case on AVR, unlike on typical ARM/RISC-V implementations.
-
Good alternatives above. But don't forget the ultra-simple approaches if all else is still too expensive: the simple checksum, just one addition. It's not ultra-robust for sure, but has proven adequate in myriads of applications as long as a *very occasional* (in practice) false "ok" is not overly critical.
But I otherwise second the Fletcher checksum as a better alternative while still cheap. And of course as Berni mentioned, that's a lot more efficient in software but for direct hardware implementation, the story is different.
-
"That seems rather strange as that's only 512 bytes and even the ATTiny25/45/85 series is available with 8K of program space. It will be much faster!"
Thanks, I'll double check how much flash space is in use for everything else the program does, things are tight on an ATTiny85, but there might be 512 bytes offlash to spare. I might have been mentally equating those bytes with the SRAM, which is ofcourse much smaller than the flash in which a PROGMEM array can sit.
-
Good alternatives above. But don't forget the ultra-simple approaches if all else is still too expensive: the simple checksum, just one addition.
I mentioned XOR, which has essentially the same cost and properties as ADD. I wrote XOR/ADD at first, but simplified before posting.
An N-bit XOR checksum is exactly N 1-bit CRCs interleaved. And ADD checksum is similar but with harder to analyse properties due to the internal carries (it's not better!)
It's not ultra-robust for sure, but has proven adequate in myriads of applications as long as a *very occasional* (in practice) false "ok" is not overly critical.
Any N-bit checksum, no matter what algorithm (as long as all input bits contribute to the checksum!) will detect all but 1 in 2^N of all possible random transmission errors i.e. any 16 bit checksum will detect 65535/65536 of random errors. ADD/XOR does not differ from CRC in this.
The difference is in matching the kind of checksum to the expected non-random distribution of transmission errors.
In practice, with many transmission technologies, most errors occur in bursts, with most bits transmitted correctly (usually no errors at all) but with at most one contiguous burst of incorrect bits. N-bit CRCs are precisely the mathematical algorithm that guarantees that not only all bursts of N bits or fewer will be detected but also a very high proportion of bursts of a small multiple of N.
All other checksums are inferior in their protection against a single burst of errors. An XOR/ADD of size N, for example, is easily fooled by a burst of length N+1. Fletcher is actually worse, in that an N-bit Fletcher checksum (two N/2 bit checksums) can also be fooled by bursts of N/2+1 bits i.e. a 16 bit Fletcher checksum is only guaranteed to detect bursts up to 8 bits long.
If bursts are the likely problem, then a 16 bit XOR (two 8-bit XORs with interleaved streams) is much better than 16 bit Fletcher.
On the other hand, if data arriving out of order is a likely problem then XOR is completely useless. That's maybe a problem if you're checksumming an entire file, but shouldn't be if you're checksumming each indivisible data packet.
-
This is the method I use for small code size with good performance. It is essentially an optimized explicitly unrolled loop.
uint16_t crc;
void update_crc(uint8_t x)
{
x ^= (crc >> 8);
crc <<= 8;
if(x & 0x01) crc ^= 0x1021;
if(x & 0x02) crc ^= 0x2042;
if(x & 0x04) crc ^= 0x4084;
if(x & 0x08) crc ^= 0x8108;
if(x & 0x10) crc ^= 0x1231;
if(x & 0x20) crc ^= 0x2462;
if(x & 0x40) crc ^= 0x48C4;
if(x & 0x80) crc ^= 0x9188;
}
-
Come to think of it, an N+1 bit error burst is 100% GUARANTEED to fool XOR checksums, because a burst (from the point of view of the receiver) is defined as the first and last bits both being flipped. If one of them wasn't flipped then it would only be an N bit (or less) error burst.
-
To be fair no error detection method is 100% reliable.
As long as there is a considerable amount of data to be hashed down into a error detection word, you have a lot of combinations that can result in the same checksum output. So if the error detection word is 8 bit you always have a 1 in 256 chance that a completely random sequence of input bytes will appear to be correct.
It is more about picking a method that is most robust against the type of data corruption that might happen in the particular operation. A radio link might have a burst of complete garbage in the middle. A really long RS232 cable might suffer from an occasional flipped bit or lost byte. Some other transfer link might suffer from chunks of data getting swapped around into the wrong order. Some might guarantee the length and byte order to always be correct but commonly only 1 byte is garbage.
For some of these a dead simple 8bit sum might be enough. Heck for some even 1 bit parity might be enough. For other cases you might want 32bit of proper CRC, or for some cases you might want actual ECC codes so you can patch up errors in your data. But further you go the more processing power a MCU would have to dedicate to the task.
-
Have you tried the CRC16 implementation of avr-libc (https://www.nongnu.org/avr-libc/user-manual/group__util__crc.html)? It is a well optimised implementation written in assembly. Looks like it is branchless too, so should be pretty fast. Although probably still not as fast as a table-based algorithm.
Beware that it's inlined, so if you're calling it in multiple places in your code, you'll end up with multiple copies of it in the binary, which may not be helpful if you're tight on space.
-
But it seems rather slow, quite a lot of clock cycles per byte to the extent that with a 16MHz clock rate my AVR chips are taking about 6.5us per byte to calculate checksums.
No idea where time is consumed but anyway.
i = SLR((crc_high_byte ^ data_byte), 4);
i = SLR((crc_high_byte ^ (data_byte << 4)), 4);
You can also add table pointer directly and avoid pgm_read call.
-
You can also add table pointer directly and avoid pgm_read call.
What do you mean? AVR is a weird architecture with separate address spaces for RAM and FLASH. You either access flash with these special instructions, or you copy the tables to RAM. Latter would be faster (and doesn't require special access code), but the amount of RAM in these small controllers is so little that I guess OP has to read the tables from FLASH.
-
What do you mean? AVR is a weird architecture with separate address spaces for RAM and FLASH.
Pretty much standard for 8 bit microcontrollers. AVR is probably the *least* weird of them. At least the flash is byte-oriented (not 12 or 14 or whatever bits wide, varying from model to model, like in PIC). And PIC doesn't give you instructions to read data from flash, but only computed GOTO into a table of load immediate instructions.
-
And PIC doesn't give you instructions to read data from flash, but only computed GOTO into a table of load immediate instructions.
Yes, at least the PIC16F and similar, that was a real pain. I think the PIC18 made it better though. Still a separate instruction for reading from flash, but at least there was one.
-
And PIC doesn't give you instructions to read data from flash, but only computed GOTO into a table of load immediate instructions.
PIC can read from Flash using indirect addressing.
-
But it seems rather slow, quite a lot of clock cycles per byte to the extent that with a 16MHz clock rate my AVR chips are taking about 6.5us per byte to calculate checksums....
It has been a few years, but I bet you could do better with a 16-bit CRC. I guided avr-gcc 3.4.6 to take less than 2µs per byte checking the flash of an ATMega88.
-
And PIC doesn't give you instructions to read data from flash, but only computed GOTO into a table of load immediate instructions.
PIC can read from Flash using indirect addressing.
Yea. About 10 or so years ago the 8 bit PIC architecture was updated to allow the index registers (FSR/INDF) to directly access flash memory and have linear access to the register file (RAM). This allow much cleaner and faster pointers in C.
-
I mentioned XOR
it's used by SONY in the { Playstation1, Playstation2 } for checksuming both the memory card and pad { joypad, mouse } :D
-
I was thinking of combining some operation like add with rotate and it ends up the old BSD checksum (https://en.wikipedia.org/wiki/BSD_checksum) does exactly that. It only requires two operations per byte or word and requires no extra storage or tables.
I wonder about the properties if exclusive-or replaced the add.
-
Remember that there is nothing magically wonderful about a CRC. They started out from people trying to protect, scramble or whiten serial bit streams in hardware, with as few gates as possible. There are many alternatives which are better when the data exists in parallel form, or a mix of serial and parallel, in the path being protected. There are certainly things which are a lot simpler in software.
-
You can also add table pointer directly and avoid pgm_read call.
What do you mean?
Do "internally" what "external" thing is doing and avoid a call.
-
You can also add table pointer directly and avoid pgm_read call.
What do you mean?
Do "internally" what "external" thing is doing and avoid a call.
https://manpages.debian.org/jessie/avr-libc/pgm_read_dword_near.3avr.en.html
pgm_read_dword_near is not a function, there is no call. It makes the compiler emit the correct instructions to access the flash address space, inlined where it's "called". There is no advantage of doing the same in inline assembly (which you apparently suggest?)
-
It's always a balance between code size and speed.
The people squeezing an 8bit avr to the limit still managed to fit an 512 byte table.
https://github.com/prusa3d/Prusa-Firmware/blob/d6250592b20f2475bbd3e8d967e5026fda016489/Firmware/Sd2Card.cpp#L478
They also have a table-less variant of CRC8.
https://github.com/prusa3d/Prusa-Firmware/blob/MK3/Firmware/mmu2_crc.h
-
The one used by Modbus
-
There is no advantage of doing the same in inline assembly (which you apparently suggest?)
Yes.
-
One possible advantage of using inline assembler is that it will always be that assembler regardless of compiler version or settings.
-
I switched from that 16 element table with 4 bits "width" for addressing it, to a 256 element table. This avoids those >>12 and >>4 operations. I've improved the speed 3.3 fold without even changing the polynomial. Now it only has to do this for each byte of data:
i = (crc >> 8 ) ^ data_byte;
crc = pgm_read_dword_near(table + i) ^ (crc << 8 );
I also got rid of the crc_of_byte function and put those two lines directly inside the loop over all the bytes of data
uint16_t crc = 0;
for (uint8_t j=0; j<Length; j++){
uint8_t i = (crc >> 8 ) ^ data_array[j];
crc = pgm_read_dword_near(table + i) ^ (crc << 8 );
}
so these was no need to enter and exit the function each time the for loop ran.
Together switching the table type and unfunctioning the function seem to have got me enough of a speed boost.
And it's still compatible with checksums calculated via the 16 element table version.
Thanks
-
Good job.
>>4 of a 16 bit int is pretty painful on AVR because it only has single-bit shifts, and only on 8 bits at a time, so >>4 takes 8 instructions. Ironically >>12 is better because it only has to choose the hi byte and shift it 4 times. >>8 is simply choosing the register containing the hi byte, so very cheap or even free. If you want bits 4..7 of a 16 bit int then it's better to do (char)x >> 4
-
One possible advantage of using inline assembler is that it will always be that assembler regardless of compiler version or settings.
You realize pgm_read we are discussing is just a #define which emits __LPM, which makes the compiler emit the correct instructions directly. There is no function call regardless of compiler version or settings.
-
Yes,
https://github.com/avrdudes/avr-libc/blob/55e8cac69935657bcd3e4d938750960c757844c3/include/avr/pgmspace.h#L427C1-L438C4
#define __LPM_enhanced__(addr) \
(__extension__({ \
uint16_t __addr16 = (uint16_t)(addr); \
uint8_t __result; \
__asm__ __volatile__ \
( \
"lpm %0, Z" "\n\t" \
: "=r" (__result) \
: "z" (__addr16) \
); \
__result; \
}))
-
i = (crc >> 8 ) ^ data_byte;
crc = pgm_read_dword_near(table + i) ^ (crc << 8 );
You can still access crc parts directly.
Reserve dword but use it part by part.
One side being crc and other side being zero.
Then 'i' would use high part of crc, no shifts.
Other part of crc would shift its address.
1234 memory locations
nn00
x- 1st part
xx 2nd part
or little endian
00nn
-x 1st part
xx 2nd part
-
i = (crc >> 8 ) ^ data_byte;
crc = pgm_read_dword_near(table + i) ^ (crc << 8 );
You can still access crc parts directly.
Reserve dword but use it part by part.
One side being crc and other side being zero.
Then 'i' would use high part of crc, no shifts.
Other part of crc would shift its address.
1234 memory locations
nn00
x- 1st part
xx 2nd part
or little endian
00nn
-x 1st part
xx 2nd part
There are no shifts in the above code. The upper 8 bits are stored in one 8 bit AVR register and the lower 8 bits in another register. The shifts written in C are compiled to simply using the appropriate AVR register.
-
Hate to be that guy, but is it possible to switch to some other AVR MCU?
Newer Attiny 2-series devices have more resources, faster GPIO (no read-modify-write) and cost less.
-
Switching isn't necessary with what I've now got, but out of interest:
1.Are the 2 series devices pin compatible with older ones like the ATTiny84(a)?
2.Can they be programmed using the same ICSP method, using an AVR as ISP programmer device?
-
Hi,
1. No. But they made them compatible between ATtiny 0-1-2 core families. Vcc, GND, RST are now at the same positions for the same footprints.
On a project where we used it, we're now able to move vertically between 8/16/32 KB versions for the same footprint. But we're using between several hundreds or several thousands per year, so the move made sense on that project.
2. Depends on your RST pin implementation. New devices use UPDI. If you've used the standard Atmel's ISP pinout, then it should work (you'll need only Vcc, RST and GND), as long as you don't have any capacitors on that line.
And you'll need a series resistors of about 470 ohm connecting it to the programmer.
On low-cost AVR programmers (like Adafruit) they're usually using UART on the "programmer" to load the firmware onto a target.
-
Here is an efficient C code for a fast 16-bit CRC, which is appropriate for microcontrollers (it has low complexity and requires no lookup table):
uint16_t fast_crc16(uint8_t *data, size_t length)
{
uint16_t A, crc=0;
for(size_t i=0; i<length; i++)
{
A = (crc>>8)^data[i];
crc = (A<<2)^(A<<1)^A^(crc<<8);
}
return crc;
}
This CRC, generated by x^16 + x^2 + x + 1, has HD=4 and length up to 32767 bits, which are the same as those of CRC-16-ANSI (x^16 + x^15 + x^2 + 1) and CRC-16-CCITT (x^16 + x^12 + x^5 + 1).
For more details about this CRC and other fast CRCs, see G.D. Nguyen, “Fast CRCs,” IEEE Transactions on Computers, vol. 58, no. 10, pp. 1321-1331, Oct. 2009. See also arXiv:1009.5949 [cs.IT].
-
And PIC doesn't give you instructions to read data from flash, but only computed GOTO into a table of load immediate instructions.
Yes, at least the PIC16F and similar, that was a real pain. I think the PIC18 made it better though. Still a separate instruction for reading from flash, but at least there was one.
Not true. PIC16F ( like PIC16F1947 and the like) has two index registers and one can use either to read from the FLASH directly by adding offset 0x8000 to it IIRC.
But that way, one can only see low bytes in each 14-bit word. Which is in practice good enough for many applications as top byte has only 6 bits anyway.
But even if you need all 14 bits, reading is simple as it has basically register pair that works just as pointer for these sort of jobs.
-
This is the method I use for small code size with good performance. It is essentially an optimized explicitly unrolled loop.
uint16_t crc;
void update_crc(uint8_t x)
{
x ^= (crc >> 8);
crc <<= 8;
if(x & 0x01) crc ^= 0x1021;
if(x & 0x02) crc ^= 0x2042;
if(x & 0x04) crc ^= 0x4084;
if(x & 0x08) crc ^= 0x8108;
if(x & 0x10) crc ^= 0x1231;
if(x & 0x20) crc ^= 0x2462;
if(x & 0x40) crc ^= 0x48C4;
if(x & 0x80) crc ^= 0x9188;
}
it can be optimized:
uint16_t crc;
uint16_t table[256];
void update_crc(uint8_t x)
{
crc = (crc << 8) ^ table[((crc >> 8) ^ x) & 0xff];
}
A further optimization can be achieved by processing data in blocks rather than individual bytes, leveraging vectorization for parallel computation
-
Note that if the application is not ultra-critical, a simple sum may be adequate. Just mentioning.
-
Note that if the application is not ultra-critical, a simple sum may be adequate. Just mentioning.
Programmers are often perfectionists in irrelevant aspects and still miss much bigger problems.
Like, we regularly have to trust completely non-checksummed data from e.g. I2C/SPI sensors and then we worry against the strength of the checksum when relaying the same data forward using similar signal integrity. And in reality downtime and customer dissatisfaction is caused by some glaring bug we missed.
Simple sum is like 99.9% strong against usual corruption mechanisms*. Maybe CRC16 is then 99.99%. Both are susceptible to malicious modifications, and have some very specific "weak points" of their own against certain types of corruption. Whether that matters at all is a question of how often corruption does happen in the first place, and how large are the consequences.
*) it misses stuff like same bit index corrupting from 0->1 and from 1->0 in different bytes
Modulo sum of bytes is super easy to implement and performance so much better it's very rarely a limiting factor.
-
Simple sum is like 99.9% strong against usual corruption mechanisms*. Maybe CRC16 is then 99.99%. Both are susceptible to malicious modifications, and have some very specific "weak points" of their own against certain types of corruption. Whether that matters at all is a question of how often corruption does happen in the first place, and how large are the consequences.
All checksums with the same number of bits detect exactly the same proportion of errors, the differences lie in which ones detect the errors that are likely to occur.
CRCs are particularly good at detecting error bursts of up to the length of the CRC, in a single place in the data packet being checked. This is the most common kind of error in electrical wiring, especially as signalling speeds increase, not a random bit here and another random bit there. If most transmissions are error-free then CRC is probably what you want for communications channels. But not for things such as bit-flips in RAM or registers.
That x^16 + x^2 + x + 1 CRC is very cheap to compute as it's just two adds and three xors -- no large displacement shifts are required.
Sure, a simple add or xor of the bytes is faster, but computing the above CRC is probably faster than your communications channel.
If most transmissions are not error-free then you need to use something waaay more complicated -- very highly redundant FEC with the number of bits transmitted possibly several times more than the number of actual data bits.
-
>>4 of a 16 bit int is pretty painful on AVR because it only has single-bit shifts, and only on 8 bits at a time, so >>4 takes 8 instructions.
Are there any CRCs (or similar) that can use the nybble swap present in many 8bit chips (including the AVR)?
(this can apparently reduce the 4bit shift to "only" 6 instructions.)