CODEWITHSUNDEEP
csemanticscrc32
Kaonashi
Kaonashi

Reputation: 11

CRC-32 with LFSR Byte by Byte in C

I implemented a CRC32 algorithm in C but after hours of looking around and trying to fix it, it still doesn't work. It compiles but the checksum is not the same as in several online CRC calculators. I suspect the error to be in the line "if (0 != (character & j))" but don't understand it, since it is even mainly the same as the code on wikipedia.

wikipedia 

int CRC32_C(char *message){
    int length, i, j;
    unsigned long p,g;
    char character;
    p = 0x00000000;
    g = 0x04C11DB7;
    length = strlen(message);

    for (i = 0; i < length; i++){
        character=*message;
        //iterieren durch die bits jedes zeichens
        for (j= 0x80; j != 0; j >>= 1){ 
            //(p & 0x80000000)? 1 : 0)
            if (0 != (character & j))
                p = (p << 1) ^ g;
            else
                p <<=1;
        }
        message++;
    }
    return p;
}
//sample main
int main(char ** argv, int argc){
    char *msg;
    int p;
    msg = "HALLO";
    p = CRC32_C(msg);
    printf("p ist 0x%x \n", p);
    return 0;
}

Sample input: "HALLO"

Expected result: 0x4E26F361 (according to this page, which uses the same generator polynomial, as seen at the bottom of the page)

Actual result: 0xc25a747d

@chux: I tried removing the "0 !=" in the if clause, but it didn't change the result.

CRC32_C simply stands for "Implemented in C". As the Generator polynomial suggests, it is standard Ethernet.

Thanks for your help

Upvotes: 1

Views: 1721

Answers (2)

Mark Adler
Mark Adler

Reputation: 112404

This will generate the CRC 0x4E26F361 from HALLO:

#include <stddef.h>
#include <stdint.h>

/* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */
#define POLY 0xedb88320


/* Compute CRC of buf[0..len-1] with initial CRC of crc.  Start
   with crc == 0. */
uint32_t crc32c(uint32_t crc, const unsigned char *buf, size_t len)
{
    int k;

    crc = ~crc;
    while (len--) {
        crc ^= *buf++;
        for (k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    }
    return ~crc;
}

The above computes the CRC bit-by-bit, where there are faster approaches. That happens to be CRC in common use, so you can find a fast implementation in zlib, called crc32(), which is already available as an installed library in most systems.

Upvotes: 0

rcgldr
rcgldr

Reputation: 28826

The CRC may be msb to lsb or lsb to msb, and the generator polynomial may be different in the online examples. CRC32_F is msb to lsb, CRC32_R is lsb to msb (with the polynomial reversed). If you can find an online CRC calculator that takes hex, try using hex 01 to test for msb to lsb, or hex 80 to test for lsb to msb. Other variations initialize the crc to 0xffffffff and/or invert (not) the crc after calculating the crc. Looking at a description of ethernet crc, try using CRC32_R, but change the initialization of crc to crc = 0xfffffffful; .

unsigned long CRC32_F(unsigned char *message, size_t length){
    size_t i, j;
    unsigned long crc,gnp;
    crc = 0x00000000ul;
    gnp = 0x04C11DB7ul;
    for (i = 0; i < length; i++){
        crc ^= ((unsigned long)*message)<<24;
        for (j = 0; j < 8; j++){ 
            if (crc & 0x80000000ul)
                crc = (crc << 1) ^ gnp;
            else
                crc = (crc << 1);
        }
        message++;
    }
    return crc;
}

unsigned long CRC32_R(unsigned char *message, size_t length){
    size_t i, j;
    unsigned long crc,gnp;
    crc = 0x00000000ul;
    gnp = 0xEDB88320ul;
    for (i = 0; i < length; i++){
        crc ^= ((unsigned long)*message)<<0;
        for (j = 0; j < 8; j++){ 
            if (crc & 0x00000001ul)
                crc = (crc >> 1) ^ gnp;
            else
                crc = (crc >> 1);
        }
        message++;
    }
    return crc;
}

Upvotes: 3

Related Questions