mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Ideen um CRC-Routine zu beschleunigen? (AVR, gcc)


Autor: Joan P. (joan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

ich berechne gerade mit nem AVR die CRC (Polynom 4. Grades: '1011') von 
einer Nachricht, die immer 13Bit lang ist (mit dem CRC-Ergebnis dran 
sind es dann genau 2 byte).

Da ich Timingmässig an die Schmerzgrenze komme wollte ich mal fragen, 
ob mir vielleicht jemand Tipps zur Optimierung geben könnte.. ich hatte 
irgendwo was von Tabellen und einer Verbesserung um den Faktor 8 
gelesen.. gilt das auch für ein Polynom 4ten Grades oder wär da nur 
der Faktor 4 drin (wobei das schon spitze wär!)?
Bei den Tabellen weiß ich nur nicht wo anfangen.. :-(

Oder kann man meinen bisherigen Code noch optimieren?
static uint8_t crc_poly=0x0B; // '1011' CRC-Polynom
frame = 0x99b0; // Frame[15:0]
volatile uint8_t i=12;
uint8_t anhang = (frame>>i); // Anhang[3:0] aus Frame[15:12] nehmen
do // die CRC-Dividenden berechnen
{
    i--;
    if ((anhang & 0x08)==0x08) // CRC-Dividenden berechnen, wenn Bit 3 eine 1 ist
    {
        anhang = (crc_poly ^ anhang);
    }
    anhang = ((anhang<<1) | ((frame>>i) & 0x01)); // Anhang mit nächtem FrameBit rechts auffüllen
} while (i>0); // bis zum vorletzten Dividenden
if ((anhang & 0x08)==0x08) // letzten CRC-Dividenden berechnen, wenn Bit 3 eine 1 ist
{
    anhang = (crc_poly ^ anhang);
} // bis hier dauerts ca 100µs ab 'do'
// in 'anhang' steht jetzt auf den letzten 3 Bit das gewünschte..

Besten Dank fürs lesen und eventuelle Antworten :-)

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ohne den Rest angesehen zu haben:
volatile uint8_t i=12;

Brauchts das volatile wirklich? wird i in ner ISR geändert?
allein das weglassen von volatile hier könnt schon ne Menge Zeit 
einsparen.

Autor: 3351 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Anstelle von bitweisem Schieben und XORen, kann man's auch mit ner 
Tabelle machen, Das gibt dann noch einen Zugriff pro Byte.

Autor: Joan P. (joan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wow!

Super, das hat 20µs ausgemacht. staun

Ich sollte wohl nochmal die Basics lesen :-(
'Volatile' klingt für mich wie: ändert sich viel, in der Nähe behalten.. 
aber wird wohl genau das Gegenteil sein, so wie sich das auswirkt.

Danke!!!

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nochn Tipp: Wenn du sauschnell werden musst, schreib die Routine mal von 
Hand in Assembler und optimier die nach bestem Wissen und Gewissen. Dann 
vergleich mal, was der GCC ausspuckt -- evtl. gibt dir das noch ein paar 
Anregungen. Wird dann natürlich als Inline-ASM verbaut.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Joan P. wrote:

>
>     anhang = ((anhang<<1) | ((frame>>i) & 0x01));
> 

Sowas mag der AVR nicht, er hat nämlich kein n-mal Shift.

Besser:

anhang <<= 1;
if( frame & 1<<11 )
  anhang++; 
frame <<= 1;



Peter

Autor: Joan P. (joan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Peter

ich hab deinen Vorschlag mal so umgesetzt:
anhang <<= 1;
if (frame & (1<<i))
{
  anhang++; 
}
..ist dann aber 5,6µs langsamer als die nicht so optimale, die es 
ersetzen sollte..

Die 'frame'-Variable kann ich nicht anfassen (also 'frame <<=1;') weil 
ich die hinterher ja noch verschicken will. Oder versteh ich da was 
falsch? Die wird doch bei der Anweisung nach links verschoben..


@Sven

Jau, das hätt ich gemacht, wenn ich die Schmerzgrenze erreicht hätte. 
Aber durch den Hinweis, die Variablen nicht mit 'volatile' zu 
deklarieren hab ich mittlerweile rund 60µs Sicherheitsabstand.. :-D


@all
vielen Dank nochmal, mein Problem ist damit vorerst vom Tisch - wenns 
nicht noch Einwände wegen der Form gibt oder so :-)

Autor: Andreas Watterott (andreasw) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> if (frame & (1<<i))
Genau das wollte Peter vermeiden. Wenn du 'frame' noch benötigst, dann 
sichere sie einfach vorher.

Autor: Joan P. (joan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas Watterott wrote:
>> if (frame & (1<<i))
> Genau das wollte Peter vermeiden. Wenn du 'frame' noch benötigst, dann
> sichere sie einfach vorher.

Hm.. wie soll dann 'frame' durchgeschoben werden, wenn nicht per 
wachsender Verschiebung?
Man muss doch das CRC-Polynom immer eins weiterschieben und dann per XOR 
auf das 'frame' bzw, den 'anhang' anwenden.. wie soll das ohne 
Laufvariable gehen?

Ich dachte Peters Code hätte den Vorteil, dass ich die variable 'frame' 
nicht mehr tlw. an 'anhang' übergebe (via Masken und Bitoperationen), 
sondern, dass die in 'anhang' eingehenden 0-en und 1-en per Vergleich 
mit 'frame' und direkter Erzeugung in 'anhang' selber entstehen.. 
'frame' also intern anders behandelt würde... ?!

verwirrte Grüsse

Autor: MC (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nur mal so nebenbei:
warum benutzen die meisten Protokolle fehlererkennende Verfahren (wie 
CRC) und keine fehlerkorrigierenden Verfahren (wie z.B. Haming-Code)?

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das "weniger Optimale", was Peter vermeiden wollte, ist dieser Teil: 
1<<i
Der AVR hat nämlich keinen Befehl für ein n-shift. Der Compiler macht 
daraus also eine Schleife, die i-mal um ein Bit shiftet.

Autor: Andreas Watterott (andreasw) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Der Gedanke ist, dass frame bei jedem Durchlauf nur einmal geschoben 
wird und nicht i mal. Denn es gibt bei den AVRs keinen Shift-Befehl 
für x mal schieben.

Autor: Joan P. (joan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas Watterott wrote:
> Der Gedanke ist, dass frame bei jedem Durchlauf nur einmal geschoben
> wird und nicht i mal. Denn es gibt bei den AVRs keinen Shift-Befehl
> für x mal schieben.

Hm.. im Moment glaube ich, dass ich euch zwar verstehe, aber ich seh 
meinen Fehler nicht.. ich schiebe doch nur 1mal pro Durchlauf?!
Oder wo ist der Unterschied zwischen (1<<i) mit 'i=11' und (1<<11), wo 
ich dann haufenweise Code aufschreiben muss, damit ich alle Schiebungen 
hinbekomme?
Ich muss doch eh alle Nummern durchgehen (wegen der einzelnen XOR's), 
bis ich 'theoretisch' (1<<0) da stehen habe.. warum also nicht mit 
Schleifenvariable?

Nochmal anhand des ersten Codes:
volatile uint8_t i=12;
uint8_t anhang = (frame>>i); // i ist 12 -> schiebe frame um 12 Stellen nach rechts, fertig
...
do // die CRC-Dividenden berechnen
{
    i--; // Durchlauf #1: i ist 11
    [...] // CRC-Hilfsdividend berechnen (XOR)
    anhang = ((anhang<<1) | ((frame>>i) & 0x01)); // frame um 11 nach rechts schieben und Bit übernehmen

} while (i>0); // i ist größer 0, also noch ne Runde

<--->

    i--; // Durchlauf #2: i ist 10
    [...] // CRC-Hilfsdividend berechnen (XOR)
    anhang = ((anhang<<1) | ((frame>>i) & 0x01)); // frame um 10 nach rechts schieben und Bit übernehmen

} while (i>0); // i ist größer 0, also noch ne Runde


//usw usf..


    i--; // Durchlauf #11: i ist 0
    [...] // CRC-Hilfsdividend berechnen (XOR)
    anhang = ((anhang<<1) | ((frame>>i) & 0x01)); // frame um 0 nach rechts schieben und Bit übernehmen

} while (i>0); // i ist nicht größer 0, fertig mit der Schleife.

//(in Wirklichkeit fehlt jetzt noch einmal XOR, deswegen hab ichs noch einmal drunter stehen in dem Code im OP ganz oben)

Da wird das frame doch nur 1 mal pro Runde geschoben?!? Denk ich..

Sorry, dass ich mich so blöd anstelle :-(

CRC-Rechnung zu Fuss (Quelle: 
http://www.informatik.uni-frankfurt.de/~haase/crc.html)
Das Ergebnis, was rechts steht, braucht man gar nicht.. für CRC 
interessiert ja nur der Rest, der unten an dem Schwanz dran hängt, weil 
der ja anstelle der 0-Bits an das Frame gehängt wird. Und genau so 
rechne ich das mit dem Code..
Frame:          1 1 0 1 0 1 1 0 1 1
Generator:      1 0 0 1 1
Frame 0-Bits:   1 1 0 1 0 1 1 0 1 1 0 0 0 0

Division:

    1 1 0 1 0 1 1 0 1 1 0 0 0 0  /  1 0 0 1 1  =  1 1 0 0 0 0 1 0 1 0
    1 0 0 1 1 ------------------------------------+ | |             |
    ---------                                       | |             |
      1 0 0 1 1                                     | |             |
      1 0 0 1 1 ------------------------------------+ |             |
      ---------                                       |             |
        0 0 0 0 1                                     |             |
        0 0 0 0 0 ------------------------------------+    . . .    |
        ---------                                                   |
          0 0 0 1 0                                                 |
          0 0 0 0 0                                                 |
          ---------                                                 |
            0 0 1 0 1                                               |
            0 0 0 0 0                                               |
            ---------                                               |
              0 1 0 1 1                                             |
              0 0 0 0 0                                             |
              ---------                                             |
                1 0 1 1 0                                           |
                1 0 0 1 1                                           |
                ---------                                           |
                  0 1 0 1 0                                         |
                  0 0 0 0 0                                         |
                  ---------                                         |
                    1 0 1 0 0                                       |
                    1 0 0 1 1                                       |
                    ---------                                       |
                      0 1 1 1 0                                     |
                      0 0 0 0 0 ------------------------------------+
                      ---------
                        1 1 1 0  =  Rest

Daraus ergibt sich der Frame mit Pruefsumme: 1 1 0 1 0 1 1 0 1 1 1 1 1 0

Autor: Werner B. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Geschwindigkeit ist (fast) immer ein Widerspruch zur Lesbarkeit und 
Wartbarkeit. Du darfst also nicht erwarten dass das Ergebnis einer
Optimierung noch "interpretierbar" ist.
uint8_t anhang = (frame>>i);
Hier erzeugt der Compiler Code der zur Laufzeit ausgeführt werden muss.
Besser ist
uint8_t anhang = (0x99b0>>12); // oder einfach anhang = 9;
Das kann der Compiler schon zur Übersetzungszeit berechnen.


Als nächstes
    anhang = ((anhang<<1) | ((frame>>i) & 0x01));
frame wird in jedem Durchlauf um i Stellen nach Rechts geschoben.
Das passiert in einer Schleife.

Das andere Problem ist, dass durch das abnehmende i die üblichen
Tricks zur  Maskenberechnung nicht so leicht anwendbar sind.
Aber man kann dem AVR einige der Berechnungen die er bei deinem
Code zur Laufzeit machen muss schon vorab manuell 
vorbereiten/erleichtern.

Komplett ungetestete "Idee" wie es laufen könnte
(bei der ersten Tasse Kaffee des Tages aus dem Ärmel geschüttelt ;-)
frame = 0x0d9; // Bitreverse von 0x99b0 um 4 nach rechts verschoben
uint8_t i=12;
uint8_t anhang = 9;
...
do // die CRC-Dividenden berechnen
{
    i--; // Durchlauf #1:
    [...] // CRC-Hilfsdividend berechnen (XOR)
    anhang = ((anhang<<1) | ((frame) & 0x01));
    frame >>= 1;
} while (i>0); // i ist größer 0, also noch ne Runde

Autor: 3351 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie kurz erwaehnt, kann man das Schieben fuer jeder Bit durch einen 
Tabellenzugriff fuer jedes Byte ersetzen. Das ergibt eine 
Verschnellerung um den Faktor 8  fuer den Preis einer Tabelle.

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Oder wo ist der Unterschied zwischen (1<<i) mit 'i=11' und (1<<11)

"1<<11" ist eine Konstante. Da wird in Wirklichkeit gar nichts 
geschoben, denn schon beim Übersetzen des Programms wird das durch 2048 
ersetzt. Bei "1<<i" mit veränderlichem i geht das natürlich nicht, da 
muss das zur Laufzeit berechnet werden.

> Da wird das frame doch nur 1 mal pro Runde geschoben?!? Denk ich..

Aber es wird um mehrere Bit geschoben.
Nochmal:
X<<1 ist schnell, weil der AVR einen Assemblerbefehl für "1 Bit 
schieben" hat.
X<<n ist langsam, weil der AVR keinen Befehl für "n Bit schieben" hat, 
und daher eine Schleife erzeugt werden muss.

Autor: Joan P. (joan)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, so weit versteh ich das.. aber ich komme glaube um das partielle 
Schieben während der Laufzeit nicht herum, weil das Frame sich jedes mal 
ändert, also nicht statisch ist.
Der Code im OP mit dem festen 'frame' war nur als Beispiel fürs 
Verständnis gedacht. Das Programm was ich hier vor mir hab ändert das 
Frame vor jeder CRC-Berechnung (ca 300µs von Frame zu Frame).

Wäre es 'hilfreich' bzw. 'optimaler' wenn man diese einzelnen 
Verschiebungen per switch-Anweisung machen würde? Weil ich brauch ja von 
'1<<11' bis '1<<0' alle Verschiebungen nacheinander, für jedes Frame.
Der Code wird dann halt 'unüberichtlicher' und größer.

Aber wie gesagt, der Hinweis mit den Variablen hat mir für meine Zwecke 
genug Sicherheitspolster verschafft, schneller brauch ich vorerst 
nicht..

Autor: Tobias Frost (coldtobi)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wie bereits schon mal erwähnt, aber bis jetzt gekonnt ignoriert:

Tabellen.

Es gibt eine CRC Implementiertung, die ist sau-schnell, braucht aber 
eine Lookup-Table. AFAIR 256 byte gross..
Ich habe irgendwo auch eine Half-Table implementierung gesehen, aber bei 
google jetzt nichts auf die schnelle gefunden (Die Implementierung die 
ich kenne ist leider closed source...)

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mach mal ne for-schleife draus und schalt die Optimierung ein, i = 12 
würde ich als konstante definieren. dann kann der Compiler da eventuell 
was besseres draus bauen.

Autor: kommutator (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier das Howto mit Quellen und Tabellengenerator als Quelltext:

http://www.ross.net/crc/download/crc_v3.txt

(Einfach TABLE DRIVEN CRC googlen)

Und: Tabellen-CRC ist wirklich schnell!

Autor: Til (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und wenn das alles nicht genug ist, echt mal das ganze in Assembler 
machen, muss man ja nicht alles selber machen, einfach List File 
erzeugen lassen, daraus den Assembler Code nehmen und diesen per Hand 
optimieren.

Autor: A. F. (artur-f) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier ist ein wissenswertes Dokument, was die Bildung von CRC Summen 
angeht:
http://www.google.de/url?sa=t&ct=res&cd=6&url=http...

Unten ist ein Beispiel, wie du für deinen CRC Check eine Tabelle 
erzeugen kannst.

Autor: eProfi (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
In der Kürze liegt die Würze:
1.
  do{
  cy=crc&1;crc>>=1;
  if(byte&mask){if(!cy){crc^=0xa001;}}else{if (cy){crc^=0xa001;}}}
  while(mask<<=1);
2.
  do{cy=crc&1;crc>>=1;if((byte&1)!=cy){crc^=0xa001;}byte>>=1;}while(--i);
  }
3.
  do{cy=crc;crc>>=1;if((byte^cy)&1){crc^=0xa001;}byte>>=1;}while(--i);
  }
4.
  do{cy=(crc^byte)&1;crc>>=1;byte>>=1;if(cy)crc^=0xa001;}while(--i);
5.
  i=8;do{b=(c&1)-(d&1);c/=2;d/=2;if(b)c^=40961;}while(--i);
6.
  i=8;do{b=(c^d)&1;c/=2;d/=2;if(b)c^=40961;}while(--i);


Hier nochmal ein komplettes Testprogramm, ich liebe cryptischen 
high-density-code  ;-)

#define p 0xa001 //polynom=40961 siehe Beispiel für Dallas 1-wire 
buttons
void main(void){ //              1w-standard.pdf S.145/158:
unsigned int b,  //boolean
c=0x90f1, //crc
d=0x75,   //data   with this data  result (variable c) must be 0x6390
i=7;

//i=8;do{if((c^d)&1)c=c/2^p; else c/=2;d/=2;}while(--i);
//i=8;do{b=(c&1)-(d&1);c/=2;d/=2;if(b)c^=p;}while(--i);
//i=8;do{b=(c^d)&1;c/=2;d/=2;if(b)c^=p;}while(--i);
  i=8;do{c=(c^d)&1?c/2^p:c/2;d/=2;}while(--i);
//i=8;do{c=c/2^((c^d)&1?p:0);d/=2;}while(--i);
}


Noch schneller geht's nur mit einer Tabelle:
siehe Anhang für eine CRC16 in Pascal

Autor: gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn das Sende/Empfangstelegramm nur variabel in den Daten- und 
CRC-Bytes ist und das Telegramm u.a. auch fixe Bytes besitzt. So 
könntest Du diese festen Bytes vorab berechnen und als Konstante im 
Programm ablegen. So braucht dein Programm nur noch die variablen Werte 
berechnen.

Autor: eProfi (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
mit for kann man es noch kürzer schreiben, hihi:
for(i=8;i--;c=c/2^((c^d)&1?p:0),d/=2);

Turbo-C übersetzt c/2 tatsächlich in einen div , deshalb c>>1:

register unsigned i;
i=8;do{c=(c^d)&1?c>>1^p:c>>1;d>>=1;}while(--i);

Turbo-C macht folgenden (nahezu optimalen) 80x86-Code daraus:

BE0800        MOV     SI,0008  ;i=8
8BC7          MOV     AX,DI    ;c
33C2          XOR     AX,DX    ;^d
A90100        TEST    AX,0001  ;&1
7409          JZ      0BB3     ;?
8BC7          MOV     AX,DI    ;c
D1E8          SHR     AX,1     ;>>1
3501A0        XOR     AX,A001  ;^p
EB04          JMP     0BB7     ;:
8BC7          MOV     AX,DI    ;c
D1E8          SHR     AX,1     ;>>1
8BF8          MOV     DI,AX    ;c=
D1EA          SHR     DX,1     ;d>>=1
4E            DEC     SI       ;--i
8BC6          MOV     AX,SI    ;test auf 0 könnte er sich sparen, da
0BC0          OR      AX,AX    ;  Z-Flag schon durch DEC SI gesetzt
75DF          JNZ     0BA1     ;while


Wenn Codegröße keine Rolle spielt, kann man weitere Zeit mit 
Loop-Unrolling einsparen, einfach die Zeile 8 mal hinschreiben:
c=(c^d)&1?c>>1^p:c>>1;d>>=1;
c=(c^d)&1?c>>1^p:c>>1;d>>=1;
c=(c^d)&1?c>>1^p:c>>1;d>>=1;
c=(c^d)&1?c>>1^p:c>>1;d>>=1;
c=(c^d)&1?c>>1^p:c>>1;d>>=1;
c=(c^d)&1?c>>1^p:c>>1;d>>=1;
c=(c^d)&1?c>>1^p:c>>1;d>>=1;
c=(c^d)&1?c>>1^p:c>>1;d>>=1;

Manche Compiler realisieren das Konstrukt ? : sehr umständlich, deshalb 
kann es günstiger sein, mit if .. else zu arbeiten.


Im Anhang noch eine crc32-Implementierung mit Lookup-Table von Charles 
Bloom.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@  Joan P.

Mal was Grundsätzliches:
Zitat:
..."ich berechne gerade mit nem AVR die CRC (Polynom 4. Grades: 
'1011')"...

1011 ist ein Polynom 3ten Grades:
1*x^3 + 0*x^2 + 1*x^1 + 1*x^0 = x^3 + x + 1

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]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [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.