CRC32: C Implemtierung OHNE Lookup-Table

[Guest (Gast)]

Hallo,
ich bin seit Ewigkeiten auf der Suche nach einer Funktion zur Berechnung 
einer CRC32. (grundlegendes Polynom: 0xEDB88320)

Das ganze sollte ohne LookUp-Table gemacht werden, da ich keine 
(riesige) Tabelle in dem verwendeten PIC vorhalten kann. (langsamer, 
weniger Speicherplatz notwendig)

Zudem sollte die Bildung der Prüfsumme byteweise geschehen.
Für einige sachdienliche Hinweise wäre ich mehr als dankbar.

Vielen Dank.

[Peter D. (peda)]

Guest schrieb:
> ich bin seit Ewigkeiten auf der Suche nach einer Funktion zur Berechnung
> einer CRC32. (grundlegendes Polynom: 0xEDB88320)


Ja, man muß da schon einige Sekunden googlen:

http://de.wikipedia.org/wiki/Zyklische_Redundanzpr%C3%BCfung


Peter

[Guest (Gast)]

Das Beispiel hatte ich mir bereits angesehen...
Was mich daran gestört hat: Es ist immer die Rede von Datenbits?!

int datastream[]={1,0,0,0,1,1,0,0}

bei mir wäre es aber ein char-Array, also ausschließlich Bytewerte

z.B.

int testdata[]={0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08}

Wenn ich über diese 8Byte (!) jetzt mit zwei unterschiedlichen 
Checksum-Tools eine CRC32 mache, komme ich auf die Prüfsumme 0x3fca88c5. 
Und die ist auch vollkommen korrekt meiner Ansicht nach.

Mit der Wikipedia-Routine ist mir das aber nicht gelungen.

Kann das jemand vielleicht überprüfen mit dem oben genannten Datenstrom 
und dem Polynom 0xEDB88320? (sonst werde ich hier noch wahnsinnig)

Danke sehr. Einen schönen Tag weiterhin.

[Peter D. (peda)]

Guest schrieb:
> Das Beispiel hatte ich mir bereits angesehen...
> Was mich daran gestört hat: Es ist immer die Rede von Datenbits?!
>
> int datastream[]={1,0,0,0,1,1,0,0}

Die 8 Bits sind hier verschwenderisch als int gespeichert, soll ja nur 
das Prinzip verdeutlichen.

Dein Problem ist also, wie Du die CRC über 8 Bits eines Bytes macht?
Dazu schiebt man sie einfach der Reihe nach durch:

#include <inttypes.h>

#define CRC32POLY 0x04C11DB7 /* CRC-32 Polynom */

uint32_t crc_32( uint32_t crc32, uint8_t val )
{
  uint8_t i;
    for(i = 8; i; i--){                               // 8 bits per byte
      if(((crc32 & 0x80000000) ? 1 : 0) != (val & 1)) // test LSB
        crc32=(crc32<<1) ^CRC32POLY;
      else
        crc32<<=1;
      val >>= 1;                                      // shift data bits
    }
  return crc32;
}

Ich hab jetzt mal LSBit first vermutet (Linksschieben).


Peter

[Guest (Gast)]

Ich möchte schlicht und ergreifend eine CRC32 über 8 BYTE bilden.
Derzeit benutze ich folgenden Code (von der Wikipedia-Seite):

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define CRC32POLYREV 0xEDB88320 /* CRC-32 Polynom, umgekehrte Bitfolge */
 
int datastream[]={1,0,0,0,1,1,0,0}; /* ASCII-"1", LSB zuerst */
int databits=8;
uint32_t crc32_rev=0xffffffff; /* Schieberegister, Startwert (111...) */
 
int main(void)
{ int i;
    for (i=0; i<databits; ++i)
        if ((crc32_rev & 1) != datastream[i])
             crc32_rev=(crc32_rev>>1) ^ CRC32POLYREV; 
        else 
             crc32_rev=crc32_rev>>1;
    printf("0x%08X\n",crc32_rev ^ 0xffffffff); /* inverses Ergebnis, MSB zuerst */
    return EXIT_SUCCESS;
}

datastream[] ist in meinem Fall wohl mein Char-Buffer also (0x01 bis 
0x08) nehme ich stark an.
Für databits habe ich die Anzahl der Elemente meines Buffers angenommen, 
also 8. (sozusagen die buffer_length)

Das Ergebnis ist halt nicht richtig. Ich frage mich jetzt, was ICH 
falsch mache...

[Thomas P. (tpircher)]

Bist du dir sicher, dass

int datastream[]={1,0,0,0,1,1,0,0}; /* ASCII-"1", LSB zuerst */

wirkilch ist was du beabsichtigst? Du berechnest den CRC ueber 8 Bytes, 
aber die Werte schauen verdaechtig danach aus, dass du den CRC 
eigentlich ueber 8 Bits berechnen wolltest...

Habe mir den CRC code nicht genauer angeschaut, aber auf den ersten 
Blick sieht er gut aus.

Mit pycrc (http://www.tty1.net/pycrc/) laesst sich gut mit verschiedenen 
Parametern und Eingabedaten experimentieren. Und btw, pycrc kann dir 
auch C-Code generieren.

Thomas

[Thomas P. (tpircher)]

Ich habe jetzt verstanden was obiger Code macht: er nimmt nur EIN bit 
von jedem Byte in deinem datastream. Der Code aus dem Wikipedia Artikel 
ist nur fuer didaktische Zwecke geeignet, in einem wirklichen Programm 
wirst du die CRC Berechnung so nicht finden.

[Sumynona (Gast)]

Hallo


Der Code von Peter Dannegger ist schon sehr gut! Besser geht es kaum 
noch
Falls du nicht mit irgendwas kompatibel sein musst, ist ein invertierter 
CRC, bei dem du nicht auf  & 0x80000000 prüfen musst sondern auf & 0x01 
besser, da es vorher einen Cast auf (uint8_t) ermöglicht -> spart 
Rechenschritte.

hier mal etwas ungetesteter code (hab grad keinen C Compiler da)

#include <inttypes.h>

#define CRC32POLYREV 0xEDB88320 /* CRC-32 Polynom, umgekehrte Bitfolge */

void crc_32( uint32_t* crc32, uint8_t* buffer, uint8_t length )
{
  uint8_t i;
  while(length--)
  {
    for(i = 0x80; i; i >> 1)
    {
      if(  ((*(uint8_t*)crc32 * i) & i) != (*buffer & i)  )
        *crc32 = (*crc32 >> 1) ^ CRC32POLYREV;
      else
        *crc32 >>= 1;
    }
    buffer++;
  }
}

Ich habe den CRC32 in einen Pointer geändert, so kann er bei späteren 
Aufrufen wiederverwendet werden. Außerdem funktioniert (sollte) es über 
mehrere Bytes.

Nicht vergessen: *crc32 mit 0xFFFFFFFF initialisieren und ganz zum 
schluss ein xor mit 0xFFFFFFFF

[Guest (Gast)]

Okay, danke für die Bemühungen. Probiere den Code morgen aus.
Noch eine klitzekleine Frgae hätte ich da:
Was´n das für eine For-Schleife?

for(i = 0x80; i; i >> 1)

Die ist etwas tricky bzw. nicht alltäglich oder? Vor allem die 
Abbruchbedingung kann ich derzeit nicht deuten...

Vielen Dank.

[?? (Gast)]

Die ueblichen C Toelpel...
Die Abbruchbedingung ? i; bedeutet als Boolean <>0, solange I ungleich 
Null.

[H.j.Seifert (Gast)]

hm, die Schleife wird 8 mal durchlaufen, mit i=0x80,0x40,..0x01.

[Sumynona (Gast)]

Genau, für jedes Bit im Byte einmal
Der Trick ist, dass der Wert dann gleich als Bitmaske verwendet werden 
kann

[Sumynona (Gast)]

Edit: Fehler gefunden: in der For schleife muss es
for(i = 0x80; i; i >>= 1)

heißen (es fehlt ein = )

[Wiesel (Gast)]

Es wäre didaktisch besser gewesen, wenn Du geschrieben hättest was genau 
Du an der For-Schleife nicht verstehst.
Ich nehme aber an, das Du die Abbruchbedingung meinst die hier lediglich 
aus:

...;i ;...

besteht.

Schau Dir mal die Beschreibung der For-Schleife in einem guten C-Buch 
an.

Der Witz ist das zwischen "Wahr" und "Falsch" und Zahlenwerten eine 
Beziehung besteht. Wahr ist jeder Wert ungleich 0. Falsch hingegen eben 
die verbleibende Null.

Wenn also das oberste Bit immer weiter nach rechts schiebst, wird es 
irgendwann rechts aus dem Byte fallen, auf den Tisch fallen und Bing 
machen.
Dann ist i = Null, also Falsch. Die Schleife wird beendet.

[Guest (Gast)]

@Sumynona:
Vielen Dank, jetzt macht die Schleife mehr Sinn. Hab´s verstanden...

@Wiesel:
"Es wäre didaktisch besser gewesen, wenn Du geschrieben hättest was 
genau
Du an der For-Schleife nicht verstehst. Ich nehme aber an, das Du die 
Abbruchbedingung meinst die hier lediglich aus..."

Die Aussage war der Oberhammer an diesem heutigen Nachmittag. Wenn du 
mal höher scrollst dann stand/steht da in etwa folgendes:

"Vor allem die Abbruchbedingung kann ich derzeit nicht deuten..."

Habe in diesem Thread wirklich viel Gutes, nur leider auch ziemlich viel 
Blödes lesen müssen.

[Jannik (Gast)]

Hi,

kann mir einer helfen, das Bsp zum laufen zu bekommen?

Ich übergebe val = 0x50;
crc32 = 0xffffffff;

Ergebnis der Funktion ist: 0x61826962

Sämtlich onlinekalkulatoren geben mit diesem Input als Ergebnis 
0xB969BE79.

Warum?

Peter D. schrieb:
>
> #define CRC32POLY 0x04C11DB7 /* CRC-32 Polynom */
>
> uint32_t crc_32( uint32_t crc32, uint8_t val )
> {
>   uint8_t i;
>     for(i = 8; i; i--){                               // 8 bits per byte
>       if(((crc32 & 0x80000000) ? 1 : 0) != (val & 1)) // test LSB
>         crc32=(crc32<<1) ^CRC32POLY;
>       else
>         crc32<<=1;
>       val >>= 1;                                      // shift data bits
>     }
>   return crc32;
> }
>
> Ich hab jetzt mal LSBit first vermutet (Linksschieben).
>
> Peter

Viele Grüße
Jannik

[A. S. (Gast)]

Es gibt 4 verschiedene Problemstellen:
1) der Startwert (0 oder alles ff?)
2) lsb zuerst oder msb zuerst?
3) Dementsprechend das Polynom mal gespiegelt, mal nicht
4) nochmal Invertierung des Endwertes (ja/nein)

CRC ist sehr effizient bei der Verarbeitung einer Bit-Folge. Dabei 
spielt es eine Rolle, ob das niederwertigste Byte zuerst kommt oder das 
höchstwertige. Dementsprechend kommt auch das niederwertigste Bit zuerst 
bzw. das höchwertigste.

Der Erste Link bei Wikipedia liefert Dir sowohl online-Rechner als auch 
C-Code.

Bitte angeben, wie genau Du berechnest, der Code zeigt es nicht, die 
Initialisierung  (und ggf. Finalisierung) fehlen.

Der Rechner kommt in keiner Variation auf keinen Deiner Wert. Womit hast 
Du getestet.

[Jannik (Gast)]

Hallo Achim,

danke für deine ausführliche Antwort.
Ich habe Bsp in dem Kalkulator: 
https://www.lammertbies.nl/comm/info/crc-calculation.html den Hexwert 
0x50 getestet. Dieser benutzt im Ergebnis CRC32 dasselbe Polynom 
(0x04C11DB7). Ergebnis hier: 0xB969BE79.

Ich initialisiere mit 0xffffffff, wie bereits oben geschrieben. Versucht 
habe ich beide Varianten LSB und MSB first (0x50 und 0x05).
Bei der Polynomspiegelung verlasse ich mich auf die fertige Funktion, 
dass es hier nicht not tut und mit LSB/MSB first funktionieren soll. Ein 
abschließendes XOR vom Ergebnis ergibt auch keinen gleichen Wert.

Der Code wurde direkt auf einem 32bit Mikrocontroller getestet.