www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik CRC- Funktion


Autor: Faller (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ich habe folgenden Bespielcode für die CRC- Berechnung gefunden. Kann 
mir jemand von euch sagen was die übergabe Paramter der Funktion (size, 
mem, crc) im einzelnen bedeuten? Vielen Dank!

Faller

unsigned char crc(unsigned char size, unsigned int * mem, unsigned char
crc)
{
   #define poly 0x1021 // g(x) = x^16+ x^12 + x^5 + 1
   unsigned int i;
   unsigned char j, b, m;

   // While (more message bits)
   for (i=0; i < size; i++)
   {
      m = mem[i];
      for( j = 8; j; j-- )
      {
         b = 0;
         if(crc & 0x80)//00)
            b++;
         crc <<= 1;           // Shift the register left by one bit,
         if ((m & 0x80) != 0)
           crc |= 1;
         m <<= 1;
         if (b != 0)  // If (a 1 bit popped out during step 3)
           crc ^= poly;          // Register = Register XOR Poly.
       }
   }
   return crc;
}

Autor: Obelix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was denkst du denn? Schau mal ins Deutsch-Englisch Wörterbuch.
Du hast doch schon den Quellcode dabei, da kannst du dir doch alles raus 
suchen.


Size - Größe (Wird dann wohl die Größe des Speicherbereichs sein.)
Mem wie Memory - Speicher (Ein Zeiger auf den Speicherbereich)
crc - Ist der Startwert (üblicherweise warscheinlich 0)

Autor: Obelix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Aber deine Routine sieht irgenswie fehlerhaft aus.
1. Das Polynom past nicht zur beschreibung dahinter.
2. Es ist ein 16Bit Polynom aber die Funktion gibt nur ein unsugned char 
zurück.

Autor: Faller (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja das Polynom sieht fehlerhaft aus und die Funktion sollte kein 
unsigned zurückgeben. Ich bin mir auch nicht sicher ob der Quellcode 
sonst passt. Hat jemand von euch zufällig ein Bespiel zu Hand, mitdem 
man aus 32Bit Daten mit einem x^16+x^15+x^2+1 die Cecksumme berechnen 
kann.

Ich kenne mich damit leider überhaupt nicht aus.

Autor: Obelix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Unsigned ist schon OK, aber "char" nicht, das sind nur 8Bit.
Gugg mal ins Wikipedia.de.

Dein Datenblock ist nur 32Bit Groß?

Autor: Daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

bei Wikipedia sind zwei Beispiele in C fuer die CRC32 Berechnung.
http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung
Es ist nur Schieben und XOR (^) oder nur Schieben.
und je nachdem was man fuer einen startwert hat, alles null oder alles 
eins verwendet wird nach links (<<) oder nach Rechts (>>) geschoben
(in Klammern die C-Syntax aus dem Code Beispiel).

Die 32 Bit Checksum ist ein 32 Bitwert, welcher am Ende des Algorithmus 
im 32 Bit Register, mit welchen der Algorihtums ausgefuehrt wird, steht.

Bei Wikipedia ist es verstaendlicher erklaert, als das was ich hier 
geschrieben habe.

Ich habe aber selbst noch eine Frage.
Ich fuege die Checksum an das Ende eine berechneten Datenblockes und 
wenn ich nun den Datenblock wieder einlese und wiederum in den 
Algoritmus schieben, dann muesste das verwendete Generatorpolynom 
uebrigbleiben. Macht es aber nicht. :(
Beispiel: Generatorpolynom 0xEDB88320
 liest Bit 0 zuerst bis Bit 7
Der verwendete Algorithmus ist:
   #define CRC32POLYREV 0xEDB88320 /* CRC-32 Polynom, umgekehrte 
Bitfolge */
   crc32_rev=0xffffffff; /* Startwert (111...) */

   uint32_t crc32_rev; /* Shiftregister */
   void calc_crc32_rev(int bit)
   {    int lbit;
        lbit=crc32_rev & 1;
        if (lbit != bit)
                crc32_rev=(crc32_rev>>1) ^ CRC32POLYREV;
        else
                crc32_rev=crc32_rev>>1;
   }

der Algorithmus liest jeweils die einzelnen Bytebloecke in der 
Reihenfolge von links nach rechts, so werden sie in den Algorithmus 
geschoben:
09,08,07,06,05,04,03,02,01,00-> 6035A035 (CHECKSUM ist korrekt)
sie werden dann so an den Code angehaengt, so das der Algorithmus das 
Bit 31 der Checksum als erstes liest.
60,35,A0,35,09,08,07,06,05,04,03,02,01,00
nun muesste doch eigentlich das Generatorpolynom uebrigbleiben und ich 
wuerde es auf gleichheit pruefen. Statt dessen erhalte ich E54433D7
Vielleicht darf bei der Ueberpruefung, der Startwert nicht wieder 
0xFFFFFFFF sein?!

Vielen Dank fuer Hinweise

daniel

Autor: Peter (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Warum benutzt du nicht einfach mal die Suchfunktion. Ich hab hier schon 
2 mal Code gepostet, einmal Berechnung, einmal mit Lookup Table

Autor: Daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,
ich habe genuegend Code gefunden.
Aber ich habe eine Frage zum Prinzip.
ich lese 10 Bytes ein, berechne die CRC32 und alles in Ordnung.
Haenge diese CRC32 an die Datei im Little Endian Format.
Nun werden die 14 Bytes wieder eingelesen und im selben Alghoritmus 
verarbeitet. Zuerst wird das LowByte des CRC32 eingelesen und dann die 
10 Byte Daten. Nach dieser Berechnung der 14 Bytes, muesste doch das 
Generator polynom als CRC32 rauskommen ? Kommt es aber nicht.
Hab es auch schon mit Big Endian variante probiert.

Wie kann man simpel die Daten mit CRC pruefen?

Danke
Daniel

Autor: Obelix (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Zuerst wird das LowByte des CRC32 eingelesen und dann die 10 Byte Daten
Du schmeist da irgendetwas durcheinander.

Ich habe es so verstanden, wenn man bei CRC32 an die Nutzdaten alle 
32Bit anhängt (in der richtigen Reihenfolge natürlich) dann muss 0 bei 
bei einer weiteren CRC32 raus kommen.

Autor: Daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,
Was ist denn die richtige Reihenfolge fuer das Einlesen?
Wenn ich ein Datenblock habe und ihn von hinten nach vorn durchlese und 
berechne.Dann diesen CRC32 an den Datenblock so haenge, dass das lsb 
zuerst an den daten haengt. Sieht dann so aus: [ Datenblock ][LSB CRC32 
MSB] und diesen Block wieder von hinten nach vorn durchlese, bedeutet 
das das MSB des CRC32 als erstes gelesen wird und dann bis zum ende des 
Datenblocks.

Oder muss man den Datenblock von vorn nach hinten lesen und dann denn 
CRC anhaengen mit dem LSB an den Datenblock. Beim Ueberpfruefen wieder 
alles von vorn nach hinten durchlesen. Also erst denn Datenblock dann 
vom LSB des CRC32 bis zum MSB berechnen und dieses Ergebnis sollte dann 
null sein.

Welche von den beiden Varianten ist nun die richtige? Ist es 
entscheidend, dass der CRC32 zuerst oder zuletzt eingelesen wird, oder 
anders gesagt ist es entscheidend, ob der CRC32 vor dem Datenblock oder 
hinter dem Datenblock sich befindet? Wie ist es richtig?

Danke
Daniel

Autor: Faller (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du aus den Nutzdaten und der berechneten CRC-Cecksumme 
(CRC-Checksumme an die Nutzdaten anhängen) praktisch erneut die 
CRC-Cecksumme berechnest. Muss in der letzten division eine Null 
heraukommmen -also kein Rest übrigbleiben. Dann sind deine Daten 
richtig!


Autor: Daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

noch eine Anmerkung, ich verwende den Ethernet Standard, das bedeutet 
mein Startwert ist 0xFFFFFFFF und das Ergebnis wird invertiert. Es 
werden Bytes verarbeitet,wobei mit dem LSB begonnen wird.

Bei der Ueberpruefung muessen die ersten 32 Bits invertiert werden und 
dann wird das Bit 31 des CRC32 zuerst verarbeitet.
Fuer die Ueberpfruefung verwende ich denselben Algorithmus und ebenso 
wieder den Startwert 0xFFFFFFFF. Wenn ich aber all das beachte 
funktioniert es aber dann wiederrum nicht. :(

Es ist doch in Ordnung dieser Startwert, wenn ich die ersten 32 Bits mit 
dem Startwert 0xFFFFFFFF XOR verknuepfe, dann ist das diese 
Invertierung. Ist das richtig so ? oder habe ich da etwas falsch 
verstanden.

Danke
Daniel

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.