mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik CRC-16 Implementierung unverständlich


Autor: Stephan W. (stephan-w)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

Ich habe in dem Beitrag (Beitrag "CRC16 Prüfsumme vs. Hyper Terminal")
folgenden Codeauszug gefunden:

unsigned int calc_crc (unsigned char *ptr, unsigned int count)
{
  int crc=0,i;
  while (count>0)
  {
    crc=crc^(int)*ptr++<<8;
    for(i=0;i<8;i++)
    {
      if(crc&0x8000) crc=crc<<1^0x1021;
      else crc=crc<<1;
    }
    count--;
  };
  return(crc&0xffff);
}

Prinzipiell ist mir klar, wie CRC funktioniert, aber ich raffe die 
Implementierung nicht so recht.

Hier ist mir nicht klar, was diese Funktion eigentlich zurückliefert. Im 
genannten Beitrag steht dazu "Rückgabe: unsigned int crc" Aber 
eigentlich wollte möchte ich doch wissen, ob die Division lediglich den 
Rest 0 hat, oder nicht...

Kann mir bitte jemand erläutern was diese Funktion genau macht? Es 
scheint ja ein gängige Weg zu sein, die CRC-Prüfung so durchzuführen.


Ich würde mich über Eure Unterstützung und aufklärende Worte freuen.

vG Stephan

Autor: Stephan W. (stephan-w)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ach ja, um die angehängte Datei zu erklären: ich möchte den 
XNUT-Bootloader so umbauen, dass er eben CRC-16 statt die normale 
X-Modem-Prüfsumme zur Überprüfung der übertragenen Daten heranzieht.

vG Stephan

Autor: Stephan W. (stephan-w)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich habe nun schon etwas weitergesucht, verstehe aber immernoch nicht 
die Implementierung der CRC-Logik in C:

(1) Das steht doch für ("Solange der Datenstrom Bytes enthält), oder?
(2) Ist es richtig, diese Konstruktion so aufzulösen:

temp=(int)*ptr<<8;
crc=crc^temp;
ptr++;

Ich bin mir da unsicher, in welcher Reihenfolge die Operationen 
abgearbeitet werden...

(3) Hier schaue ich mir ein Datenbyte nach dem Anderen an, oder?

(4),(5) Diese Selektion verstehe ich nicht. Warum interessiert mich das 
MSB   und sein test auf 1???


Klar ist mir, dass die zugrundeliegende Polynomdivision mit XOR 
durchgeführt werden muss, aber das Geschiebe ist mir ein Rätsel...


unsigned int calc_crc (unsigned char *ptr, unsigned int count)
{
  int crc=0,i;
  while (count>0)               //(1)
  {
    crc=crc^(int)*ptr++<<8;     //(2)
    for(i=0;i<8;i++)            // (3)
    {
      if(crc&0x8000) crc=crc<<1^0x1021; //(4)
      else crc=crc<<1;                  //(5)
    }
    count--;
  };
  return(crc&0xffff);
}


Ich bitte dringend um Aufklärung!!!

vG Stephan

Autor: Stephan W. (stephan-w)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stephan W. schrieb:
> if(crc&0x8000) crc=crc<<1^0x1021; //(4)

wie löst man das eigentlich auf?

wird zuerst crc um 1 Bit nach links verschoben und danach das ganze mit 
0x1021 verXORt oder wird erst das XOR gemacht und dann der Links-Shift?

vG Stephan

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stephan W. schrieb:
> Stephan W. schrieb:
>> if(crc&0x8000) crc=crc<<1^0x1021; //(4)
>
> wie löst man das eigentlich auf?
>
> wird zuerst crc um 1 Bit nach links verschoben und danach das ganze mit
> 0x1021 verXORt oder wird erst das XOR gemacht und dann der Links-Shift?
>

Es wird Zeit, dass du diese Tabelle studierst

http://www.difranco.net/cop2220/op-prec.htm

Der Begriff nach dem du googeln musst lautet: "Operator Precedence"

Autor: Zwölf Mal Acht (hacky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es ist aber klar, dass der CRC-16 nur fuer 2^16 bit (8kbytes) taugt ? 
Bei mehr sollte man den CRC-32 verwenden.

Autor: Stephan W. (stephan-w)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Es wird Zeit, dass du diese Tabelle studierst
> http://www.difranco.net/cop2220/op-prec.htm
> Der Begriff nach dem du googeln musst lautet: "Operator Precedence"

Hallo Karl-Heinz,

danke für Deinen Tipp. Eine ähnliche Tabelle hatte ich schon die ganze 
Zeit vor mir liegen und bin der Meinung, dass zuerst der Shift gemacht 
wird, da er eine höhere Prio hat. Das Problem ist nur, dass ich eben das 
geshifte da nicht verstehe und deswegen stutzig geworden bin.

Kannst du mir in einfachen Worten erklären, was die Funktion macht?


Verschneiter Tag schrieb:
> Es ist aber klar, dass der CRC-16 nur fuer 2^16 bit (8kbytes) taugt ?
> Bei mehr sollte man den CRC-32 verwenden.

Hallo Hacky,

auch danke für Deinen Tipp. Nein, klar ist mir diese Aussage nicht, aber 
in meinem Fall sollen ja auch nur 128 Byte geprüft werden....

Autor: Thomas Pircher (tpircher) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Verschneiter Tag schrieb:
> Es ist aber klar, dass der CRC-16 nur fuer 2^16 bit (8kbytes) taugt ?

Wie bitte? Was hat die Menge der verarbeiteten Bits mit der Tauglichkeit 
des CRCs zu tun? Ob ein CRC 'taugt' oder nicht, haengt doch eher von der 
Breite und der Qualitaet des Polinoms ab. Bei einem 16 Bit-CRC ist die 
Wahrscheinlichkeit von Kollisionen natuerlich hoeher als bei 32 Bit. Und 
das unabhaengig, ob du nun 1, 2 oder 2^64 Bytes damit verwurstest [1].

Ein CRC (vollkommen egal, welcher Breite) erfuellt keine 
kryptographischen Anforderungen, und wurde auch nicht dafuer konzipiert. 
Aber zur Ueberpruefung von Uebertragungsfehlern ist ein CRC immer noch 
gut geeignet.

Thomas

[1] Zugegeben, diese Aussage stimmt nicht zu 100%, wie Koopman in 
"Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded 
Networks" beschreibt, aber in erster Naeherung duerfte sie doch 
zutreffen.

Autor: Thomas Pircher (tpircher) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stephan W. schrieb:
> (1) Das steht doch für ("Solange der Datenstrom Bytes enthält), oder?

Ja

> (2) Ist es richtig, diese Konstruktion so aufzulösen:

Ja.

> (3) Hier schaue ich mir ein Datenbyte nach dem Anderen an, oder?

Nein. Hier schaust du dir alle 8 Bits in einem Byte an.

> (4),(5) Diese Selektion verstehe ich nicht. Warum interessiert mich das
> MSB   und sein test auf 1???

Das ist die Polynom-Division von einem CRC. Wenn du das verstehen 
willst, lies dich einmal in http://www.ross.net/crc/download/crc_v3.txt 
ein.
Dort wirst du auch diesen Code-Schnipsel analysiert finden.

Thomas

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.