Faster alternatives to CRC?

[DiTBho]

The one used by Modbus

[m k]

There is no advantage of doing the same in inline assembly (which you apparently suggest?)

Yes.

[Jeroen3]

One possible advantage of using inline assembler is that it will always be that assembler regardless of compiler version or settings.

[Infraviolet]

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

[brucehoult]

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

[Siwastaja]

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.

[Jeroen3]

Yes,
https://github.com/avrdudes/avr-libc/blob/55e8cac69935657bcd3e4d938750960c757844c3/include/avr/pgmspace.h#L427C1-L438C4

Code: [Select]

#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;                   \
}))


[m k]

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

[brucehoult]

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.

[Perkele]

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.

[Infraviolet]

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?

[Perkele]

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.

[ptext]

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):

Code: [Select]

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].

[Hella_Wini22]

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.

[radiolistener]

This is the method I use for small code size with good performance. It is essentially an optimized explicitly unrolled loop.

Code: [Select]

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:

Code: [Select]

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

[SiliconWizard]

Note that if the application is not ultra-critical, a simple sum may be adequate. Just mentioning.

[Siwastaja]

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.

[brucehoult]

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.

[westfw]

>>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.)