Hallo, hat jemand eine einfach und schnelle Implementierung eines CRC16 ohne lookup table? Martin
Hier sind 3 Methoden beschrieben: http://pdfserv.maxim-ic.com/arpdf/AppNotes/app27.pdf Die beste Methode ist aber nur für CPUs mit Parity-Flag, z.B. 8051. Ist sogar schneller, als die Tabellenmethode. Für 8-Bit-CRC (DS18B20 und Konsorten) nehme ich das hier: char crc8 (char crc, char n) { n ^= crc; crc = 0; if( n & 0x01 ) crc = 0x5E; if( n & 0x02 ) crc ^= 0xBC; if( n & 0x04 ) crc ^= 0x61; if( n & 0x08 ) crc ^= 0xC2; if( n & 0x10 ) crc ^= 0x9D; if( n & 0x20 ) crc ^= 0x23; if( n & 0x40 ) crc ^= 0x46; if( n & 0x80 ) crc ^= 0x8C; return crc; } Peter
Nimm die:
/***********************************************************************
******
* Name: crcCCITT()
* Eingaben: - Laenge der Nachricht
* - Zeiger auf die Nachricht
* - CRC-Vorladewert, Startwert ist 0xFFFF
* Ausgaben: - CRC von der Nachricht
* Beschreibung: Die Funktion berechnet den CRC von der Nachricht nach
dem
* Generatorpolynom g(x) = x^16+ x^12 + x^5 + 1 (CCITT-Polynom).
************************************************************************
*****/
unsigned short crcCCITT(int size, unsigned char * mem, unsigned short
crc)
{
const unsigned short poly = 0x1021; // g(x) = (x^16+) x^12 + x^5 + 1
static int i,j;
static unsigned short b;
static unsigned char m;
// While (more message bits)
for (i=0; i < size; i++)
{
m = mem[i];
for (j=0; j < 8; j++)
{
b = (crc & 32768);
// Shift the register left by one bit,
crc <<= 1;
if ((m & 128) != 0) crc |= 1;
m <<= 1;
// If (a 1 bit popped out of the register during step 3)
// Register = Register XOR Poly.
if (b != 0) crc ^= poly;
}
}
return crc;
}
Grüße
Oliver
@Oliver,
ich hab da mal ein paar leichte Optimierungen vorgenommen.
Danach war der erzeugte Code erheblich kleiner.
/***********************************************************************
******
* Name: crcCCITT()
* Eingaben: - Laenge der Nachricht
* - Zeiger auf die Nachricht
* - CRC-Vorladewert, Startwert ist 0xFFFF
* Ausgaben: - CRC von der Nachricht
* Beschreibung: Die Funktion berechnet den CRC von der Nachricht nach
dem
* Generatorpolynom g(x) = x^16+ x^12 + x^5 + 1 (CCITT-Polynom).
************************************************************************
*****/
unsigned short crcCCITT(unsigned int size, unsigned char * mem, unsigned
short crc)
{
// const unsigned short poly = 0x1021; // g(x) = (x^16+) x^12 + x^5 + 1
#define poly 0x1021 // g(x) = (x^16+) x^12 + x^5 + 1
// static int i,j;
unsigned int i;
unsigned char j;
// static unsigned short b;
unsigned char b;
// static unsigned char m;
unsigned char m;
// While (more message bits)
for (i=0; i < size; i++)
{
m = mem[i];
// for (j=0; j < 8; j++)
for( j = 8; j; j-- )
{
// b = (crc & 0x8000);
b = 0;
if(crc & 0x8000)
b++;
// Shift the register left by one bit,
crc <<= 1;
if ((m & 0x80) != 0) crc |= 1;
m <<= 1;
// If (a 1 bit popped out of the register during step 3)
// Register = Register XOR Poly.
if (b != 0) crc ^= poly;
}
}
return crc;
}
Einige Grundregeln für effektives C-Programmieren:
Wenn möglich, folgendes vorziehen:
- #define statt constante Variablen
- unsigned statt signed
- char statt int
- Schleifen abwärts bis auf 0 zählen
- static Variablen nur dann, wenn deren alter Wert beim nächsten
Aufruf auch wirklich wieder benötigt wird.
Peter
Ich kann deine Tipps nicht ganz nachvollziehen, Peter.. - #define statt constante Variablen -> Klar - unsigned statt signed -> Ich würde mal eher sagen, das was man braucht.. - char statt int -> Dito - Schleifen abwärts bis auf 0 zählen -> Warum das denn bitte? - static Variablen nur dann, wenn deren alter Wert beim nächsten Aufruf auch wirklich wieder benötigt wird. -> Klar
@sasha Schleifen immer nach null zählen. Hier kann der Compiler optimaleren Code erzeugen, da er entsprechende Compare-Befehle durch einfache Flag-Auswertung ersetzen kann. Unsigned Integer erlaubt ebenso optimaleren und damit schnelleren Maschinencode.
Meine Variante:
in c:
unsigned short CalcCrc16(unsigned char* a_pArr, const unsigned int
a_nLen) {
unsigned short nCrc = 0, nIndex, nCount;
for (nCount = 0; nCount < a_nLen; nCount++) {
nCrc = nCrc ^ (a_pArr[nCount] << 8);
for (nIndex = 1; nIndex <= 8; nIndex++) {
if ((nCrc & 0x8000) != 0)
nCrc = ((nCrc << 1) ^ 0x1021);
else
nCrc = (nCrc << 1);
}
}
return (nCrc & 0xFFFF);
}
oder asm:
berechnet ob crc stimmt!! in CRCH und CRCL sollten am Ende 0'len stehen.
; beim avr -> high register
.DEF CRCH = .. ; Current CRC-value, 8 upper bits
.DEF CRCL = .. ; Current CRC-value, 8 lower bits
.DEF TMP0 = .. ; workregister
.DEF TMP1 = .. ; workregister
.DEF DATA = .. ; data-byte
tst CRCH
brne T_ERROR ; If CRC16 != 0, alles faul...
tst CRCL
breq T_ERROR ; if CRC16 != 0, alles faul...
CRC16:
eor CRCH, DATA
ldi TMP1, 0x08 ;
CRC16_LOOP:
lsl CRCL
rol CRCH
brcc CRC16_SKIP
ldi TMP0, 0x10
eor CRCH, TMP0
ldi TMP0, 0x21
eor CRCL, TMP0
CRC16_SKIP:
dec TMP1
brne CRC16_LOOP
ret
> Warum ist noch keiner auf #include <avr/crc16.h> gekommen?
in welcher Version des avrgcc gibt es das?
In keiner. Es ist Bestandteil der avr-libc. :-) Damit ist es zumindest in den aktuellen Versionen von WinAVR dabei. Die berühmt-berüchtigte ,,AVRfreaks distribution'' des avr-gcc ist leider (aus Sicht dessen, was danach alles noch passiert ist) hornalt und mittlerweile völlig veraltet. Es ist jammerschade, aber natürlich preist AVRfreaks die eigene Fassung nach wie vor als "long awaited" an, obwohl sie mittlerweile "long obsolete" ist. Die sollten dort ehrlicherweise hinschreiben: "For Windows, please get the latest version of WinAVR."
Hmm, also ich arbeite eigentlich recht gerne mit dieser "Uralt-Version". Ich habe sogar noch die 3.02, da ich mit dem was danach kam nicht mehr besonders zufrieden war. Dieser WinAVR soll doch noch total buggy sein, zumindest nach den Urteilen die man in diversen Foren lesen kann.
Hallo Peter, klar kann man die eine oder andere Routine bis zum geht nicht mehr optimieren. Den C-Code verwende ich 1. auf dem PC 2. auf einem C167 mit 20 MHz Habe auf beiden Seiten keine Zeitprobleme, daher ist mein Interesse an optimalem Code nicht sonderlich groß. Meine Projekte lassen mir zudem gar keine Zeit, alles perfekt zu machen. Wichtig ist in erster Linie, daß es läuft. Das Makeup kommt dann vielleicht später, wenn es notwendig werden sollte. Wichtig beim Algorithmenentwurf ist, nicht schon in der Entstehungsphase mit Optimierungen anzufangen. Aus leidvoller Erfahrung kann ich da nur sagen, daß man sich selbst Beine stellt und oft zu überhaupt keiner Lösung kommt. Wenn man dann aber noch Zeit hat und die Lust verspührt, spricht nichts gegen eine Optimierung des Codes. Grüße Oliver
@Notker: Wenn an WinAVR etwas buggy ist, dann vermelde es dem Autor. Was ich Dir allerdings versichern kann ist, daß in der aktuellen Version der Bibliothek (die in WinAVR enthalten ist) nicht nur zahllose Bugs beseitigt worden sind, sondern auch eine mittlerweile doch recht vernünftig gewordene Doku dabei ist. Was aber in der Tat völlig buggy ist, sind all diese Tools, die aus dem ELF-File ein AVR-COFF-File für das AVR-Studio machen. Aber da hat sich an der Situation nichts geändert gegenüber früher: ein Programm, das massig Bugs hatte und vom Autor aus Zeitmangel weiterentwickelt worden ist (elfcoff) ist durch ein weiteres Programm ersetzt worden (objtool), dessen Autor im Moment keine rechte Zeit für die Beseitigung der bekannten Bugs hat... Hmm, das beste für alle wäre natürlich, wenn AVRstudio gleich ELF lesen könnte ;-), aber das wird wohl nicht passieren. Es scheitert hier einfach an jemandem mit dem nötigen Know-How, der da weitermachen kann... Ich würde mir ja objtool selbst mal ansehen, aber ich bekomme unter Wine keins der AVRstudios installiert und ein Windows habe ich nicht. Aber wie geschrieben, all das betrifft nur die Bugs von objtool bzw. elfcoff. Die eigentliche Codegenerierung ist davon nicht betroffen, die compilierten Programme laufen völlig ordentlich auf der target MCU (auch wenn sie sich vielleicht gerade in AVRstudio nicht simulieren lassen).
@Oliver, das ist noch weit weg vom "bis zum geht nicht mehr optimieren". Es sind nur einige Dinge, die mir in Fleisch und Blut übergegangen sind. Das mit den static Variablen ist immer sehr wichtig. Es hilft dann auch beim Verständnis, was man geschrieben hat, wenn man es nach ein paar Jahren wieder betrachtet. Und das ich immer unsigned nehme, wenn negative Werte unsinnig sind, hat auch mehr Effekt auf das Verstehen und die Fehlerfreiheit bei späterer Nachnutzung. Z.B. ist es unsinnig eine CRC über negative Längen zu berechnen ebenso wie negative Anzahlen von Schleifendurchläufen. Wenn also bessere Lesbarkeit und bessere Fehlerfreiheit gepaart ist mit effizienteren Code ist es das allemal wert. Bei mir zählt eben nicht nur der Aufwand zum ersten Entwickeln des Kodes sondern auch der Aufwand zum Wiederbenutzen und Wiederverstehen bei den 100 nächsten Projekten. Damit spare ich nämlich viel mehr Zeit, als bei jedem Projekt wieder von vorn anzufangen oder alte potenzielle Fehlerquellen ausmerzen zu müssen. Alle wiederbenutzbaren Module, versuche ich so universell, effizient und fehlerfrei zu gestalten, wie ich kann. Peter
Hallo Peter,
1. Static Variable sind nichts schlimmes. Wenn man ausreichend Speicher
hat, ist diese Variante schneller, als zur Laufzeit erzeugte Variablen
auf dem Heap.
2. Signed integer ist in meinen Augen "fehlertoleranter" als unsigned
integer: Beispiel
unsigned int i;
for (i=10; i >0; i--){/*mach irgendwas*/}
Nach zwei Jahren fällt Dir ein, daß man bei /* mach mal was*/ auch noch
die 0 gebrauchen könnte. Also schreibst Du den Code um:
for (i=10; i >=0; i--){/*mach irgendwas*/}
Nach 2 Jahren und mindestens einem Tag, fragt man sich:" ..eiße, wo ist
bloß der bekloppte Fehler!"
3. Nicht optimierter Code ist besser zu lesen und zu verstehen.
Grüße
Oliver
@Oliver, komisch, bei mir brachte das Weglassen des static einen riesen Sprung bezüglich Kode und Zeit, da dann dafür erst gar kein Speicher alloziiert wurde sondern nur mit Registern gearbeitet wurde. Hängt aber wohl stark vom Compiler ab. Zu unsigned gibt es auch das Gegenbeispiel, wenn ich z.B. über alle 64kB Datenspeicher ein CRC machen will, und bei signed über 32kB immer nur Mist rauskommt. Die Verantwortung, eben bei jeder Variable auf den Wertebereich zu achten, kann einem kein Compiler abnehmen. Und immer ausschließlich double float zu nehmen, dürfte selbst auf dem C167 zu lahmen Kode führen. Abgesehen davon sind ja Vergleiche von float Zahlen mit Fallgruben gespickt (nie auf Gleichheit testen !). Peter
Man sollte aber auch nicht versuchen jede Erfahrung, die man auf einer uralten Version eines Keil Compilers gemacht hat, auf eine aktuelle Version des avrgcc zu übertragen. So allgemeingültig sind die nun auch wieder nicht.
@Notker, Du vermutest richtig, ich habs nicht mit dem AVRGCC probiert. Ich hatte nur angenommen, da der AVR ja eine Registerarchitektur hat, daß der AVRGCC aus dieser Tatsache reichlich Kapital schlägt, d.h. auch massiv Register als nicht statische lokale Variablen einsetzt und keine riesigen PUSH-POP-Orgien veranstaltet. Wenn dem aber nicht so ist, dann brauche ich mir den AVRGCC ja erst gar nicht näher ansehen. Ich hab mit dem AVR bisher nur Assembler gemacht und dabei sehr schnell gemerkt, daß man RAM nur mit der Kneifzange anfassen kann und nur häufige Registernutzung zu effektivem und schnellem Code führt. Meine Keil-Version ist von 1995. Und man muß nicht alles aus vor-AVR-Zeiten als uralt beschimpfen, nur weil man davon keine Ahnung hat. Getreu dem Motto "never change a winning team" tut er alles zu meiner vollsten Zufriedenheit. Und nur, um von einer rasend schnellen Kommandozeile auf träge "Klick und Sanduhr" Oberfläche umzusteigen, lohnt sich ein Update nicht. Peter
Selbstverständlich benutzt der avr-gcc ausgiebig die verfügbaren Register. Wenn Du Dein Urteil natürlich schon fällst, bevor Du Dir den vom Compiler generierten Code überhaupt erstmal ansiehst, dann ist Dir allerdings nicht zu helfen. Wer hat Dir den Unsinn erzählt, daß Du für den gcc auf die Kommandozeile verzichten müßtest? Er kommt ausschließlich in dieser Version daher. Nur wer ihn unbedingt in einem Klicki-Tool wie AVRstudio haben will, muß sich dann auch noch damit rumschlagen, ihn da einzubinden. (Nicht-so-sehr- Klicki-Tools wie Emacs sind da einfacher zu handhaben, da sie die Einbindung von make und Debugger schon von Haus aus beherrschen. ;-) Ich kenne zumindest einen (kommerziellen Anwender), der beim Umstieg von Keil MCS51 Compiler auf avr-gcc von einem Sprung um mehr als eine Größenordnung bezüglich der Qualität der Codegenerierung (Optimierung, Bugfreiheit) gesprochen hat... Ich kann es selbst nicht beurteilen, der letzte Keil-Compiler, den ich in den Händen hatte, war der für OS-9 (MC68k) vor mehr als 10 Jahren, und der war scheußlich. Der konnte nichtmal Variablen, die in einem lokalen Block innerhalb einer Funktion deklariert waren, anschließend wieder vom Stack räumen...
@Joerg, scheint, daß wir uns gründlich mißverstehen. Mein Posting bezog sich ausschließlich auf Notkers und dessen Posting habe ich so verstanden, daß das Weglassen des static eben nicht einen Quantensprung in Kodeeffizienz bewirkt. Der 2. Teil meines Postings bezog sich ausschließlich auf die Abqualifizierung, daß ich nicht die allerneueste Version eines Tools benutze und nicht mehr auf den AVRGCC. Ich weiß auch, daß eine wirklich uralte gecrackte Version des Keil im Web kursiert, aber die ist in keinster Weise mit den späteren ausgereiften Versionen zu vergleichen. Peter
@Joerg: kennst du eine dokumentation über den aufbau von elf und coff? würde mir das gerne mal anschauen und je nach aufwand mal das objtool weiter entwickeln wenn der author dieses tools nichts dagegen hat... MfG BAB
ELF sollte hinreichend gut dokumentiert sein, zumindest GNU binutils müssen ja tagaus, tagein damit umgehen können. AVR-COFF ist eine Atmel-Erfindung und daher dort irgendwo dokumentiert. Der Name und Aufbau scheinen an das unter Unix seit 10 Jahren als veraltet geltende COFF angelehnt. (Keine Ahnung, warum sie nicht gleich ELF genommen haben.) Für beides befindet sich Doku im Source von objtool. Da ich mittlerweile einen Weg gefunden habe, eine ausgewickelte Installation von AVRstudio so auf meine Kiste zu transferieren, daß sie hier auch unter Wine (Windows-Emulation) läuft, habe ich auch ein Interesse daran, objtool weiterzuentwickeln. Wir können uns da ggf. mal in einer privaten Mail verständigen. Ich möchte insbesondere: . ihm die Benutzung eines Mapfiles abgewöhnen; alle notwendigen Informationen stehen bereits im ElF . mal nach all den Symbolen (struct, static?, volatile?) gucken, die bislang noch nicht tun
ja können wir gerne tun...wie ich sehe hast du den code von objtool bereits...hast du den direkt vom author oder liegt der irgendwo auf einem gnu server public rum? struct und volatile gehen defintiv nicht.. mit static hatte ich bisher keine probleme... das objtool sich die daten aus dem mapfile holt, liegt wohl eher daran das man die daten dort besser rausfiltern kann. ob es sinnvoll ist weiss ich nicht kenne mich mit dem elf file noch zu wenig aus. aber wer lesen kann ist klar im vorteil..:) BAB
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.