Author Topic: Faster alternatives to CRC?  (Read 3510 times)

0 Members and 1 Guest are viewing this topic.

Online DiTBho

  • Super Contributor
  • ***
  • Posts: 3995
  • Country: gb
Re: Faster alternatives to CRC?
« Reply #25 on: January 08, 2024, 09:18:07 am »
The one used by Modbus
The opposite of courage is not cowardice, it is conformity. Even a dead fish can go with the flow
 

Offline m k

  • Super Contributor
  • ***
  • Posts: 2167
  • Country: fi
Re: Faster alternatives to CRC?
« Reply #26 on: January 09, 2024, 08:28:06 am »
There is no advantage of doing the same in inline assembly (which you apparently suggest?)

Yes.
Advance-Aneng-Appa-AVO-Beckman-Danbridge-Data Tech-Fluke-General Radio-H. W. Sullivan-Heathkit-HP-Kaise-Kyoritsu-Leeds & Northrup-Mastech-REO-Simpson-Sinclair-Tektronix-Tokyo Rikosha-Topward-Triplett-YFE
(plus lesser brands from the work shop of the world)
 

Online Jeroen3

  • Super Contributor
  • ***
  • Posts: 4087
  • Country: nl
  • Embedded Engineer
    • jeroen3.nl
Re: Faster alternatives to CRC?
« Reply #27 on: January 09, 2024, 02:39:59 pm »
One possible advantage of using inline assembler is that it will always be that assembler regardless of compiler version or settings.
 

Offline InfravioletTopic starter

  • Super Contributor
  • ***
  • Posts: 1061
  • Country: gb
Re: Faster alternatives to CRC?
« Reply #28 on: January 09, 2024, 07:52:18 pm »
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
« Last Edit: January 09, 2024, 08:13:54 pm by Infraviolet »
 

Online brucehoult

  • Super Contributor
  • ***
  • Posts: 4118
  • Country: nz
Re: Faster alternatives to CRC?
« Reply #29 on: January 09, 2024, 10:34:12 pm »
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
 

Online Siwastaja

  • Super Contributor
  • ***
  • Posts: 8253
  • Country: fi
Re: Faster alternatives to CRC?
« Reply #30 on: January 10, 2024, 08:10:15 am »
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.
 

Online Jeroen3

  • Super Contributor
  • ***
  • Posts: 4087
  • Country: nl
  • Embedded Engineer
    • jeroen3.nl
Re: Faster alternatives to CRC?
« Reply #31 on: January 10, 2024, 08:30:00 am »
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;                   \
}))
 

Offline m k

  • Super Contributor
  • ***
  • Posts: 2167
  • Country: fi
Re: Faster alternatives to CRC?
« Reply #32 on: January 10, 2024, 04:40:21 pm »
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
Advance-Aneng-Appa-AVO-Beckman-Danbridge-Data Tech-Fluke-General Radio-H. W. Sullivan-Heathkit-HP-Kaise-Kyoritsu-Leeds & Northrup-Mastech-REO-Simpson-Sinclair-Tektronix-Tokyo Rikosha-Topward-Triplett-YFE
(plus lesser brands from the work shop of the world)
 

Online brucehoult

  • Super Contributor
  • ***
  • Posts: 4118
  • Country: nz
Re: Faster alternatives to CRC?
« Reply #33 on: January 11, 2024, 12:23:01 am »
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.
 

Offline Perkele

  • Regular Contributor
  • *
  • Posts: 56
  • Country: ie
Re: Faster alternatives to CRC?
« Reply #34 on: January 11, 2024, 09:10:03 pm »
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.
 

Offline InfravioletTopic starter

  • Super Contributor
  • ***
  • Posts: 1061
  • Country: gb
Re: Faster alternatives to CRC?
« Reply #35 on: January 17, 2024, 01:59:52 am »
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?
 

Offline Perkele

  • Regular Contributor
  • *
  • Posts: 56
  • Country: ie
Re: Faster alternatives to CRC?
« Reply #36 on: January 22, 2024, 02:23:56 pm »
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.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf