www.mikrocontroller.net

Forum: Compiler & IDEs Suche CRC16


Autor: MdeWendt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

hat jemand eine einfach und schnelle Implementierung eines CRC16 ohne 
lookup table?


Martin

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Oliver K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Sascha Weitkunat (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: mikki merten (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: mcic (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Joerg Wunsch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Warum ist noch keiner auf #include <avr/crc16.h> gekommen?

Autor: Notker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Warum ist noch keiner auf #include <avr/crc16.h> gekommen?

in welcher Version des avrgcc gibt es das?

Autor: Joerg Wunsch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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."

Autor: Notker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Oliver K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Joerg Wunsch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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).

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Oliver K. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Notker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Joerg Wunsch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: BAB (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Joerg Wunsch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: BAB (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

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.