CRC-16 Implementierung unverständlich

[Stephan W. (stephan-w)]

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

[Stephan W. (stephan-w)]

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

[Stephan W. (stephan-w)]

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

[Stephan W. (stephan-w)]

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

[Karl H. (kbuchegg)]

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"

[Purzel H. (hacky)]

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

[Stephan W. (stephan-w)]

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

[Thomas P. (tpircher)]

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.

[Thomas P. (tpircher)]

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