AVR in CRC

[gumby]

A mi lahko kdo razloži, zakaj izračun 8-bitnega CRC potrebuje približno 2,3x več ciklov, kot izračun 16-bitnega? Nekako logično bi bilo, da je ravno obratno...
Tole so cikli pri različnih dolžinah blokov:

Koda: Izberi vse

dolžina   8  16   24   32   48
crc8    485 941 1397 1853 2765
crc16   221 413  605  797 1181

[mujo]

Saj poglej kodo implementacije.
CRC8 uporablja zanko, s katero se sprehaja po bitkih.
CRC16 pa nima zanke in uporabla drugi način uporabe CRC.

Pri CRC imaš tipičen trade off. Lahko imaš majhno porabo RAMa in imaš več ciklov, ali pa imaš večjo porabo RAMa in manj ciklov. Lahko pa imaš srečo in imaš hitro implementacijo z malo rama. Odvisno je nameč tudi od samega polinoma.

Potrebuješ kakšno konketno rešitev?

[gumby]

Namesto ccitt sem probal še crc16 (ta ima tudi zanko) in je še vedno za 1,8x hitrejši od ibutton. Koliko vem nobena od teh funkcij ne uporablja tabele, zato mi tudi ni jasno, zakaj take cifre.

[Kroko]

Pomeri še tole. Je z tabelo in brez.

[mujo]

Na pa smo prišli še do vejitev. 8bit verzija ima vejitve - ki lahko trajajo 1 oz 2 cikla (odvisno od izida). Vejitve so pa še v zanki. Ostale aritmetične/bitne operacije so večinoma vse en cikel.

[gumby]

crc16 ima tudi vejitev, funkcija je praktično identična tisti za ibutton. Drugačen je samo polinom in začetna vrednost... se pa vseeno izvede 2x hitreje.
Za hec sem dal zraven še xmodem, ki je tudi precej hitrešji od ibutton.

Kroko: sprobal sem obe funkciji, rezultati so čisto po pričakovanjih. Verzija s tabelo je najhitrejša, tista brez pa daleč najpočasnejša, ker uporablja 32-bit aritmetiko. Na ARM bi bilo drugače, tule se pa pozna
Še cifre:

Koda: Izberi vse

dolžina    8   32   128
crc16    257  977  3857
ccitt16  209  785  3089
xmodem   274 1042  4114
ibutton  472 1840  7312
kroko    128  464  1808
kroko NT 951 3647 14627