CRC16 auf CRC32 erweitern (C)

[Tobias P. (genesis)]

Hallo zusammen,
ich beschäftige mich derzeit mit der CRC-Programmierung (in C) und 
möchte gerne einen CRC32-Code programmieren. Der CRC16-Code ist soweit 
fertig und funktioniert auch allerdings habe ich nun das Problem dass 
der CRC32-Code falsche Werte anzeigt.

Bei der Erweiterung des funktionierenden CRC16-Codes auf CRC32 wird 
eigentlich "nur" die Maske (für das MSB) und die Anzahl an Bits (die 
verschoben werden) geändert.

Das heißt ich habe für die Maske statt 0x8000 (CRC16) nun 0x80000000 
(CRC32).
Und statt einer Verschiebung um 8 Stellen, nun eine Verschiebung um 24 
Stellen.

Die "LUT-32" funktioniert auch (zumindest stimmen die Hex-Werte dieser 
Tabelle mit dem Online-Calculator überein daher vermute ich einen Fehler 
in der Compute_CRC32() nur sehe ich es leider nicht..


Vielleicht hat jemand eine Idee?





Programmiert wird mit C und Eclipse (MinGW).

Der CRC Code wurde anhand eines Besipiels von folgendem Link erstellt:
http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html

Die Ergebnisse werden geprüft mit:
http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

CRC16-Code

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>


static unsigned short CrcTable16[256] ;
static unsigned short crc = 0;

/*Look-Up Table erstellen */
void CalculateTable_CRC16()
{
  const unsigned short generator = 0x1021;

 /* iterate over all possible input byte values 0 - 255 */
      for (int divident=0 ; divident<256 ; divident++ ) {
          unsigned short curByte = divident << 8 ; 

          for (int bit=0 ; bit<8 ; bit++ ) {
              if ( (curByte & 0x8000)!=0 ) {
                  curByte <<= 1;
                  curByte ^= generator;   
              } else {
                  curByte <<= 1;
              }
          }
          CrcTable16[divident] = curByte;
      }
  }

unsigned short Compute_CRC16(unsigned char str[],int len)      
{

    unsigned int pos;
    crc =0;            
    for (int b=0 ; b<len ; b++ ) {
        pos = ( (crc >> 8) ^ str[b]);
        crc = (unsigned short)((crc << 8) ^ (unsigned short)(CrcTable16[pos]));
    }
    return crc;
}


void main(){
    unsigned char message[3] = {0xA1, 0xBD, 0xF0};

    CalculateTable_CRC16();
  Compute_CRC16(message,3);

  printf("CRC-Code ist:  %x\n",crc);
}

CRC32-Code:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <time.h>


static unsigned long CrcTable32[256] ;
static unsigned long crc = 0;

/*Look-Up Table erstellen */
void CalculateTable_CRC32(){

      for (unsigned long divident=0 ; divident < 256 ; divident++ ) { 
          unsigned long curByte = divident << 24 ; 

          for (int bit=0 ; bit<8 ; bit++ ) {
              if ( (curByte & 0x80000000)!=0 ) {
                  curByte <<= 1;
                  curByte ^= generator;   //XOR-Anweisung
              } else {
                  curByte <<= 1;
              }
          }
          CrcTable32[divident] = curByte;
      }
  }


//CRC-Code ausführen
unsigned long Compute_CRC32(unsigned char str[],int len)      
{
    unsigned int pos;
     crc = 0;                              
    for (int b=0 ; b<len ; b++ ) {
        pos = ( (crc >> 24) ^ str[b]);
        crc = (unsigned  long)((crc << 8) ^ (unsigned long)(CrcTable32[pos]));
    }
    return crc;
}

void main()
{
    
    unsigned char message[3] = {0x83, 0x01, 0x00};
    CalculateTable_CRC32();
    Compute_CRC32(message,3);
    printf("CRC_32-Code ist:  %lx\n",crc);

/* Look-up Table ausgeben*/
    /*
for (int i=0; i<256; i++){
  printf("%x\n",CrcTable32[i]);
}
*/
  }

[Yalu X. (yalu) (Moderator)]

Tobias P. schrieb:
> Der CRC Code wurde anhand eines Besipiels von folgendem Link erstellt:
> http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html

Weiter unten auf dieser Webseite gibt es auch ein Code-Beispiel für
CRC-32.

[Kaj G. (Firma: RUB) (bloody)]

Tobias P. schrieb:
> allerdings habe ich nun das Problem dass
> der CRC32-Code falsche Werte anzeigt.
Dann sag doch mal, um was fuer eine Architektur es sich handelt. Denn je 
nach Architektur kann long 32 oder 64 bit breit sein.

Mein Tipp, um Bugs auszuschliessen:
Nutze die Datentypen aus stdint.h, wenn du unsigned long als 32 bit 
breit erwartest, nimm uint32_t. Diese Datentypen haben den Vorteil, dass 
sie auf allen Platformen dieselbe Breite haben, d.h. du kannst den 
Code entspannt auf einem x-bliebigen PC testen (z.B. mit Unittests), 
damit die korrekte Funktion sicherstellen, und dann kannst du den Code 
auch genauso auf einem uC nutzen. Mit int/long ist das nicht oder nur 
umstaendlich moeglich.

Gerade bei Hash- und anderen kryptographischen Funktionen sollte man 
diese Datentypen verwenden.

Und bevor hier wieder jemand schreit, dass das ja performancetechnisch 
kacke ist:
Erstmal die korrekte Funktion sicherstellen! Danach kann man sich 
immernoch um Performance kuemmern.


--- EDIT ---
1. Dein Code fuer CRC32 compiliert nicht. Da fehlt 'generator'.
2. Als 32 bit Applikation compiliert laeuft es immerhin, ob der Wert 
richtig ist: keine Ahnung.
3. Als 64 bit Applikation gibt es einen Segfault.

Pass die Datentypen an und mach das Beispiel compilierfaehig!

[Tobias P. (genesis)]

Vielen Dank für die Antworten :-)

@Yalu: Genau. Und nach dem gegebenen Beispiel hatte ich die 
CRC32-Berechnung umgesetzt. Dort steht ja ziemlich genau drin was 
abgeändert werden muss, allerdings wird bei mir ein falscher Wert 
erzeugt.

Wenn ich meinen Code ausführe mit folgenden Parametern:
Generatorpolynom: 0x4C11DB7
Message: 0xA1, 0xDE, 0x2B

Dann erzeugt mein Programm: d9f6d155
Richtig wäre (laut Online CRC32-Calculator): 94FCFF94


@bloody
Der Code wird auf Win7 64-bit ausgeführt.
Danke dir für den Tipp mit dem Datentyp. Tatsächlich möchte ich später 
den Code auf einem Mikrocontroller übertragen (mit entsprechender 
Anpassung) und da hatte ich mir zunächst um den Datentyp keine Gedanken 
zu gemacht.

Beim "Copy/Paste" habe ich scheinbar den "generator ausgelassen.
Hier nochmal der angepasste (und ausführbare) Code.



----EDIT----
Ach verdammt..Jetzt hab ich den Fehler entdeckt.
Ich habe den Fehler an der falschen Stelle gesucht.

Tatsächlich habe ich beim überprüfen des CRC  (per Online 
CRC-Calculator) nicht darauf geachtet, dass oftmals die Einstellungen 
"Input reflected / Result reflected" automatisch aktiviert sind und 
somit natürlich ein anderes Ergebnis angezeigt wird. :-(

Ziemlicher Anfängerfehler aber dennoch danke für eure Mühen.
Den CRC32 Code hänge ich einfach nochmal an für die die es möglcherweise 
mal benötigen.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <time.h>


uint32_t CrcTable32[256] ;
uint32_t crc = 0;
uint32_t generator = 0x4C11DB7;   //Generator-Polynom


/*********************CRC32 Look-Up Tabelle erstellen ************************/
void CalculateTable_CRC32(){


      for (uint32_t divident=0 ; divident < 256 ; divident++ ) {
        uint32_t curByte = divident << 24 ;

          for (int bit=0 ; bit<8 ; bit++ ) {
              if ( (curByte & 0x80000000)!=0 ) {
                  curByte <<= 1;
                  curByte ^= generator;   //XOR-Anweisung
              } else {
                  curByte <<= 1;
              }
          }
          CrcTable32[divident] = curByte;
      }
  }





/******************CRC32-Code ausführen**********************/

uint32_t Compute_CRC32(unsigned char str[],int len)
{
  uint32_t pos;
    crc = 0;
    for (int b=0 ; b<len ; b++ ) {
        pos = ( (crc >> 24) ^ str[b]);
        crc = (uint32_t)((crc << 8) ^ (uint32_t)(CrcTable32[pos]));
    }
   return crc;
}






int main()
{
    unsigned char message[3] = {0xA1, 0xDE, 0x2B};

    CalculateTable_CRC32();
    Compute_CRC32(message,3);
    printf("CRC_32-Code ist:  %x\n",crc);

 //Look-Up Tabelle ausgeben

    /*
    for (int i=0; i<256; i++){
    printf("%x\n",CrcTable32[i]);
    }
     */
  return 0;
}

[Kaj G. (Firma: RUB) (bloody)]

Hey Tobias,

noch ein kleiner Verbesserungsvorschlag:
Gewoehen dir bitte an Funktionsprototypen hinzuschreiben.

Ich hab deinen Code mal so bearbeitet, wie ich es machen wuerde. Ueber 
das const, usw. kann man streiten. Ist nur ein Vorschlag. Wenigstens 
Funktionsprototypen solltest du dir aber angewoehnen :)

#include <stdio.h>
#include <stdint.h>


void create_crc32_table(uint32_t *const table, const uint32_t len);
uint32_t Compute_CRC32(const uint8_t *const msg, const int32_t len, const uint32_t *const table);


int main(void)
{
    uint32_t Crc32Table[256] = {0};
    uint8_t message[3] = {0xA1, 0xDE, 0x2B};

    create_crc32_table(Crc32Table, sizeof(Crc32Table)/sizeof(uint32_t));
    uint32_t crc = Compute_CRC32(message, sizeof(message), Crc32Table);

    printf("CRC_32-Code ist:  %x\n", crc);

    return 0;
}


/*********************CRC32 Look-Up Tabelle erstellen ************************/
void create_crc32_table(uint32_t *const table, const uint32_t len)
{
    static const uint32_t generator = 0x4C11DB7;
    static const uint32_t mask = 0x80000000;

    for (uint32_t divident = 0; divident < len; divident++) {
        uint32_t curByte = divident << 24 ;

        for (int32_t bit = 0; bit < 8; bit++) {
            if ((curByte & mask) != 0) {
                curByte <<= 1;
                curByte ^= generator;
            } else {
                curByte <<= 1;
            }
        }

        table[divident] = curByte;
    }
}


/******************CRC32-Code ausführen**********************/
uint32_t Compute_CRC32(const uint8_t *const msg, const int32_t len, const uint32_t *const table)
{
    uint32_t crc = 0;

    for (int32_t b = 0; b < len; b++) {
        uint32_t pos = (crc >> 24) ^ msg[b];
        crc = (crc << 8) ^ table[pos];
    }

    return crc;
}

Ob len und pos 32 bit sein muessen, oder ob 8 bzw. 16 bit reichen, musst 
du nachher anhand deines uC und deinen Anforderungen entscheiden.

[Peter D. (peda)]

Kaj G. schrieb:
> Gewoehen dir bitte an Funktionsprototypen hinzuschreiben.

Bei lokalen (static) Funktionen ist es üblich, die Definition vor den 
Aufruf zu schreiben. Dann spart man sich die Deklaration.
Bei globalen Funktionen erfolgt die Deklaration im .h-File.