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?
1
staticuint8_tcrc_poly=0x0B;// '1011' CRC-Polynom
2
frame=0x99b0;// Frame[15:0]
3
volatileuint8_ti=12;
4
uint8_tanhang=(frame>>i);// Anhang[3:0] aus Frame[15:12] nehmen
5
do// die CRC-Dividenden berechnen
6
{
7
i--;
8
if((anhang&0x08)==0x08)// CRC-Dividenden berechnen, wenn Bit 3 eine 1 ist
9
{
10
anhang=(crc_poly^anhang);
11
}
12
anhang=((anhang<<1)|((frame>>i)&0x01));// Anhang mit nächtem FrameBit rechts auffüllen
13
}while(i>0);// bis zum vorletzten Dividenden
14
if((anhang&0x08)==0x08)// letzten CRC-Dividenden berechnen, wenn Bit 3 eine 1 ist
15
{
16
anhang=(crc_poly^anhang);
17
}// bis hier dauerts ca 100µs ab 'do'
18
// in 'anhang' steht jetzt auf den letzten 3 Bit das gewünschte..
Besten Dank fürs lesen und eventuelle Antworten :-)
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.
..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 :-)
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:
1
volatileuint8_ti=12;
2
uint8_tanhang=(frame>>i);// i ist 12 -> schiebe frame um 12 Stellen nach rechts, fertig
3
...
4
do// die CRC-Dividenden berechnen
5
{
6
i--;// Durchlauf #1: i ist 11
7
[...]// CRC-Hilfsdividend berechnen (XOR)
8
anhang=((anhang<<1)|((frame>>i)&0x01));// frame um 11 nach rechts schieben und Bit übernehmen
9
10
}while(i>0);// i ist größer 0, also noch ne Runde
11
12
<--->
13
14
i--;// Durchlauf #2: i ist 10
15
[...]// CRC-Hilfsdividend berechnen (XOR)
16
anhang=((anhang<<1)|((frame>>i)&0x01));// frame um 10 nach rechts schieben und Bit übernehmen
17
18
}while(i>0);// i ist größer 0, also noch ne Runde
19
20
21
//usw usf..
22
23
24
i--;// Durchlauf #11: i ist 0
25
[...]// CRC-Hilfsdividend berechnen (XOR)
26
anhang=((anhang<<1)|((frame>>i)&0x01));// frame um 0 nach rechts schieben und Bit übernehmen
27
28
}while(i>0);// i ist nicht größer 0, fertig mit der Schleife.
29
30
//(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..
Geschwindigkeit ist (fast) immer ein Widerspruch zur Lesbarkeit und
Wartbarkeit. Du darfst also nicht erwarten dass das Ergebnis einer
Optimierung noch "interpretierbar" ist.
1
uint8_tanhang=(frame>>i);
Hier erzeugt der Compiler Code der zur Laufzeit ausgeführt werden muss.
Besser ist
1
uint8_tanhang=(0x99b0>>12);// oder einfach anhang = 9;
Das kann der Compiler schon zur Übersetzungszeit berechnen.
Als nächstes
1
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 ;-)
1
frame=0x0d9;// Bitreverse von 0x99b0 um 4 nach rechts verschoben
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.
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.
@ 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
Thread beobachten
Seitenaufteilung abschalten