Forum: Mikrocontroller und Digitale Elektronik CRC16 - schnellere Implementierung möglich?


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Adam P. (adamap)


Angehängte Dateien:

Bewertung
-1 lesenswert
nicht lesenswert
Hallo zusammen,

ich verwende für meine CRC16 Berechnung eine Lockup-Tabelle (siehe 
Anhang).
Mein µC läuft mit 64MHz und benötigt für ein 64Byte Datenpaket 60µs,
verschiebe ich die Tabelle aus dem Flash in den RAM, spare ich mir 5µs 
ein.

Frage: Gibt es schnellere Berchnungen einer CRC16 oder vllt. ein ganz 
anderes Verfahren?

Gruß

von Guest (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Für privat oder kommerziell?
Falls letzteres kann ich das hier empfehlen:
https://www.segger.com/products/security-iot/emlib/variations/crc/

Und falls privat kannst du da ja vielleicht ein bisschen abschauen ;-).

von dummschwaetzer (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
Nimm halt einen µC der CRC in Hardware machen kann.

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Guest schrieb:
> Für privat oder kommerziell?

Kommerziell - jedoch nicht für 500/800€.

dummschwaetzer schrieb:
> Nimm halt einen µC der CRC in Hardware machen kann.

Das ist nicht möglich.


Dachte es gäbe vllt. eine andere Herangehensweise, die etwas schneller 
wäre.
Ich muss jetz auch nicht auf 5µs für 64Byte kommen, aber schneller wäre 
schon nett.

Zur Not ist es halt so :-) Bereitet im mom. auch keine Probleme, ist mir 
nur aufgefallen und da kam mir die Idee mit der Optimierung.

: Bearbeitet durch User
von Peter II (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Adam P. schrieb:
> Dachte es gäbe vllt. eine andere Herangehensweise, die etwas schneller
> wäre.

das kommt auf das Programm an. Wenn du z.b. die Byte am ende eh in einer 
schleife versendest, könnte man auch dort die CRC berechnen. Genauso bei 
empfangen, einfach wenn ein Byte reinkommt, gleich die CRC mitführen.

Das ist zwar dann immer noch nicht "schneller" aber die Zeit fällt nicht 
auf einmal an.

von Pandur S. (jetztnicht)


Bewertung
0 lesenswert
nicht lesenswert
>  .. oder vllt. ein ganz anderes Verfahren?

Ja, gibt es. Der Tabellen CRC mit den 256 Eintraegen ist der Schnellste.

Aber, .. man kann den CRC, welcher ueblicherweise am Ende der Nachricht 
angehaengt wird, auch waehrend des Rausschiebens durch das UART 
berechnen. Also einfach im UART Sende-Interrupt den CRC mitrechnen.

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Ja das wäre zwar eine Idee, jdeoch werden die 64Byte Pakete per DMA(PDC) 
versendet/empfangen.

von dummschwaetzer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Dann berechne doch den CRC erst beim Senden der einzelnen Zeichen und 
nicht am Stück voe oder nach dem senden:
alt:
berechne_crc(string)
sende(string)

neu:
for(position=0;position<sizeof(string);position++)
{
  crc=berechne_crc(zeichen an positon)
  sende(zeichen an positon)
}

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Hat sich grad wohl alles überschnitten!

Adam P. schrieb:
> Ja das wäre zwar eine Idee, jdeoch werden die 64Byte Pakete per DMA(PDC)
> versendet/empfangen.

von Dergute W. (derguteweka)


Bewertung
0 lesenswert
nicht lesenswert
Moin,

Haste schonmal ins Assemblerlisting geguckt, was der Compiler aus deinem 
Code macht? Je nach Prozessor oder Compiler kann man da vielleicht noch 
bissl drehen. Aber ich hab' wenig Hoffnung.

Gruss
WK

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Dergute W. schrieb:
> Haste schonmal ins Assemblerlisting geguckt

Nein habe ich noch nicht, denn der erste Gedanke war:
Der Compiler bekommt das mit Assembler bestimmt besser hin wie ich :)

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Aber dann wird es erstmal so bleiben.

Mit 3Mbit läufts ohne Probleme, bei 6Mbit hab ich halt zwischen den 
Paketen kleine Pausen, da die Paketgenerierung nicht hinterherkommt.

Aber wenn Segger was hat, dann weiß ich ja worauf man zurückgreifen 
könnte.

...falls jmnd noch etwas einfällt, gern bescheid sagen.
Danke!

: Bearbeitet durch User
von Dergute W. (derguteweka)


Bewertung
0 lesenswert
nicht lesenswert
Moin,

Adam P. schrieb:
> Der Compiler bekommt das mit Assembler bestimmt besser hin wie ich :)

Ja, stimmt auch meistens. Aber: Vertrauen ist gut - Kontrolle ist besser 
:-)
Manchmal kriegen Compiler irgendwas in den falschen Hals, oder muessen 
mit sanfter Gewalt ueberzeugt werden, was anders zu machen.

Gruss
WK

von Der Siebenschläfer (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Malzeit,

was für einen uC hast du? 8/16/32 bit?

im code sind ggf ein paar unschönheiten drin, die ggf rechenleistung 
kosten könnten. ggf gibt es je nach platform schnellere 
implementierungen.


was sagen deine Compiler flags? schon auf speed gestellt?
Hast du caches? sind die aktiv?
Was sagen die flash configuration (wait states) geht da noch was?
Wie sieht das aligment aus? 8  16  32 bit? bzw an welcher adresse 
startet die lookup tabelle. passt das zu deiner architektur?

Wenn ram 5us schneller ist bei den 64 lookup zugriffen, ...
ggf die ganze routine in den RAM copieren und von dort ausführen.

von Adam P. (adamap)


Bewertung
1 lesenswert
nicht lesenswert
µC: Atmel SAM4E Cortex-M4

Aber:
SCHANDE über mein Haupt :-D


Ja es waren die Projekt-Konfigs.

Nun hab ich beides probiert (Flash & RAM), macht nun kein unterschied.

Fazit: 64Byte = max. 25µs

Bei diesem Ergebnis braucht man keine Lib. kaufen :)

DANKE.

(manchmal sieht man die einfachsten "Fehler/Gründe" nicht) - aber dass 
kennt wohl jeder.

: Bearbeitet durch User
von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
@ Adam P. (adamap)

>µC: Atmel SAM4E Cortex-M4

Also 32 Bit.

>Ja es waren die Projekt-Konfigs.

Keine Optimierung eingestellt?

>Fazit: 64Byte = max. 25µs

Geht so.

Ich würde da möglichst große, natrliche Datenbreiten nutzen, mal sehen 
wie sich das auswirkt. Außerdem sieht der Algorithmus komisch aus.

http://www.ross.net/crc/download/crc_v3.txt
1
   r=0;
2
   while (len--)
3
     {
4
      byte t = (r >> 24) & 0xFF;
5
      r = (r << 8) | *p++;
6
      r^=table[t];
7
     }

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Ja, Optimierung war bei der einen Konfig aus.

Komisch?
Also ich hatte mehrere Tests durchgeführt und die CRC stimmte mit 
fertigen CRC-Tools überein.

Ist das "CRC-16 (Modbus)".

Aber werde mir deinen Link mal durchlesen und dein Code-Schnippsel mal 
laufen lassen.

von Dergute W. (derguteweka)


Bewertung
0 lesenswert
nicht lesenswert
Moin,

Bei einem 32bit Prozessor ist's nicht turbo-performant, 16bit Variablen 
zu nehmen. Koennt' sein, dass das langsamer wird (weil der Compiler dann 
ggf. noch extra 16 bit ausmaskieren/setzen muss) als mit 32bit.

Gruss
WK

von ABC (Gast)


Bewertung
0 lesenswert
nicht lesenswert
I-cash ist eingeschaltet? Der flash Schaft nur 24mhz.

Die mcu hat noch etwas Luft nach oben 120 MHz wenn ich's richtig gesehen 
hab.

Ggf Mal die Takte für die Busse und RAM kontrollieren.

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
ABC schrieb:
> I-cash ist eingeschaltet?

Nein ist es nicht, hab die Lockup aber auch im RAM getestet, macht kein 
unterschied.

Ja ich takte mit 64MHz (geringere Stromaufnahme).

Aber ich werde das mal mit den 32bit Variablen testen (bzw. bin bei, 
jedoch stimmt die CRC nun nicht mehr)

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Falk B. schrieb:
> r=0;
>    while (len--)
>      {
>       byte t = (r >> 24) & 0xFF;
>       r = (r << 8) | *p++;
>       r^=table[t];
>      }

Welche CRC soll das sein?
Sieht bei der evtl. die lockup anders aus?

Ich vergleich immer mit:
https://www.lammertbies.nl/comm/info/crc-calculation.html

Bin zwar nun bei 20µs, aber stimmt mit keiner dort aufgelisteten überein 
:-/
(Habe auch nicht so die Ahnung von CRC, Polynomen usw.)

: Bearbeitet durch User
von Guest (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Lass dir doch von SEGGER einfach mal emLib CRC geben und teste, ob deren 
Implementierung schneller ist. Falls ja, könnten sich die Lizenzkosten 
ja schnell rechnen, wenn man sie gegen deine Arbeitszeit rechnet.

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Guest schrieb:
> Lass dir doch von SEGGER einfach mal emLib CRC geben und teste

Ja ich belasse es nun auch bei meinem Stand, erfüllt nun erstmal die 
Anforderung.

War auch eher für mich gedacht, dazu lernen ist nie verkehrt.

: Bearbeitet durch User
von Johannes S. (jojos)


Bewertung
0 lesenswert
nicht lesenswert
Wenn der µC mit angezogener Handbremse läuft (64 statt 120 MHz) könnte 
es sein man mit den wait states für das flash heruntergehen kann. 
'Könnte' weil ich den Sam nicht kenne.

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Johannes S. schrieb:
> mit den wait states für das flash heruntergehen

Waren auf 4, mit 3 läufts auch noch & den Zugriff hab ich mal von 64 auf 
128bit geändert.

Jetz sinds 17-19µs. Das ist vollkommen ok (würde ich sagen).

von Dr. Sommer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Kennst du das hier schon? Da gibt es so eine Technik für 
"Multi-Level-LUT's" welche das nochmal beschleunigen können:
http://create.stephan-brumme.com/crc32/
Ist u.U. etwas Hirnverknoten nötig um das an den eigenen Anwendungsfall 
anzupassen.

von Adam P. (adamap)


Bewertung
0 lesenswert
nicht lesenswert
Dr. Sommer schrieb:
> Da gibt es so eine Technik für
> "Multi-Level-LUT's"

Ah OK, vielen dank!
Hab schon mal sowas gesehen, wo in einem Zyklus direkt mehrere Werte 
berechnet werden.

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Sliceing-by-8 bringts...btdt

https://de.wikipedia.org/wiki/Slicing_by_Eight (oder eben auch im link 
oben...)

73

von Der Siebenschläfer (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Nabend.

Schau dir das mit den wait states noch mal im datenblatt an. Falsche 
wert machen das system ggf instabil oder langsam. Das gilt nicht nur für 
die CRC berechnung sondern für die ganze FW.

Beschäftige dich mit dem Cash. mit angezogener handbremse bringen dir 
die 64mhz auch nichts. kanst gleich mit 24 Mhz takten (mit 
entsprechenden Wait States) macht vermutlich keinen grossen unterschied. 
der Flash schaft ja nur 24Mhz. nur mit dem I cash reizt man die 64mhz 
und mehr auch wirklich aus. Der I Cash läuft mit voller Core frequenz 
anstelle der 24Mhz

Beim D-Cash und DMA aufpassen! Was vom Core schreibt und liest, muss 
nicht gleich dem im RAM sein. der DMA läuft ja paralell, und erwischt 
alte daten, ... gilt natürlich auch umgekehrt.

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
@ Adam P. (adamap)

>> r=0;
>>    while (len--)
>>      {
>>       byte t = (r >> 24) & 0xFF;
>>       r = (r << 8) | *p++;
>>       r^=table[t];
>>      }

>Welche CRC soll das sein?

Die aus dem Link.

>Sieht bei der evtl. die lockup anders aus?

Kann sein, denn da gibt es mehrer Versionen. Einmal mit links und einmal 
mit rechts schieben. Darauf muss die Tabelle angepaßt sein. Logo.

Deine CRC schiebt die Daten nach rechts, der Schnipsel oben nach links!

>Bin zwar nun bei 20µs, aber stimmt mit keiner dort aufgelisteten überein
>:-/

Ist doch super! Also nur noch die CRC-Tabelle neu berechnen.

>(Habe auch nicht so die Ahnung von CRC, Polynomen usw.)

Ich auch nicht, aber mit ein wenig experimentieren kommt man da hin. Die 
Tabelle kann man selber berechnen. Das schafft man, indem man die Werte 
0-255 durch den bitweisen CRC jagt. Dort kann man je nach CRC-Typ das 
Links/Recht schieben und den Startwert variieren. Steht alles in meinem 
Link.

Probier das mal. Das rausgeschobene Byte wird vor dem Schieben zum Index 
der Tabelle.
1
uint16_t crc16_calc(const uint8_t *data, size_t length)
2
{
3
  uint16_t temp;
4
  uint16_t crc_word = CRC16_PRELOAD;
5
  
6
  while(length--)
7
  {
8
    temp      = crc_word & 0xFF;
9
    crc_word  = (crc_word >> 8) | ((uint16_t)*data++ << 8);
10
    crc_word ^= crc_table[temp];
11
  }
12
13
  return crc_word;
14
}

von Martin (Gast)


Bewertung
0 lesenswert
nicht lesenswert

von Thomas O. (kosmos)


Bewertung
1 lesenswert
nicht lesenswert
ich hatte vor Jahren das ganze mal versucht und einen Wiki Beitrag dazu 
erstellt.

https://www.mikrocontroller.net/wikisoftware/index.php?title=CAN_CRC_Berechnung&redirect=no

Hier sind jetzt nur die XOR Verknüpfungen dabei, mann müsste mal die 
Schiebebefehle mit dazuzählen.

Das sollte schon etwas schneller als 60 µSek gehen. Denke das es nicht 
mehr wie 200 Takte sind bei einem AVR mit 16 MHz sollte das in 13µSek 
erledigt sein.

: Bearbeitet durch User
von Georg (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Martin schrieb:
> Beitrag "CRC16 Berechnung mit Tabelle"

Was man so findet beruht i.A. auf byteweiser Berechnung. Rein 
theoretisch könnte man auch 16bit-weise rechnen, aber dann braucht man 
statt 256 Tabelleneinträgen 65536 und hätte etwa die doppelte 
Geschwindigkeit - ganz ausgeschlossen ist das ja nicht.

Hardware wie in USARTs funktioniert dagegen bitweise.

Georg

von Falk B. (falk)


Bewertung
0 lesenswert
nicht lesenswert
Ich hab das mal spaßenshalber auf dem TMS320F28027 probiert, der läuft 
mit 60 MHz. Braucht ca. 1300 Takte für 64 Bytes, macht ~22us. Viel 
schneller wird das glaub ich nicht.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.