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.