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 :-)

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.

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

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!!!

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.

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

@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 :-)

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

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

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

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.

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.

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

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

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.

> 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.

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..

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...)

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.

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!

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.

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

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

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

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.

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.