[FIXED] Recreating a C CRC32 algorithm in Python with crcmod

Issue

I'm attempting to decode a Novatel GPS stream in Python, and I have all of the components for the sync, header, and payload sorted, but I cannot replicate the CRC32 used as part of the messages. The algorithm used to generate the CRC appended on the message is written in c as follows:

#include <iostream>
#include <string>

using namespace std;

#define CRC32_POLYNOMIAL 0xEDB88320L
//#define CRC32_POLYNOMIAL 0x04C11DB7L

unsigned long CRC32Value(int i)
{
    int j;
    unsigned long ulCRC;
    ulCRC = i;
    for (j = 8; j > 0; j--)
    {
        if (ulCRC & 1)
            ulCRC = (ulCRC >> 1) ^ CRC32_POLYNOMIAL;
        else
            ulCRC >>= 1;
    }
    return ulCRC;
}
unsigned long CalculateBlockCRC32(
    unsigned long ulCount,
    unsigned char *ucBuffer)
{
    unsigned long ulTemp1;
    unsigned long ulTemp2;
    unsigned long ulCRC = 0;
    while (ulCount-- != 0)
    {
        ulTemp1 = (ulCRC >> 8) & 0x00FFFFFFL;
        ulTemp2 = CRC32Value(((int)ulCRC ^ *ucBuffer++ ) & 0xff );
        ulCRC = ulTemp1 ^ ulTemp2;
    }
    return(ulCRC);
}

int main()
{
    unsigned char buffer[] = {0xaa, 0x44, 0x12, 0x1c, 0x2a, 0x00, 0x02, 0x20, 0x48, 0x00, 0x00, 0x00, 0x90, 0xb4, 0x93, 0x05, 0xb0, 0xab, 0xb9, 0x12, 0x00, 0x00, 0x00, 0x00, 0x45, 0x61, 0xbc, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x1b, 0x04, 0x50, 0xb3, 0xf2, 0x8e, 0x49, 0x40, 0x16, 0xfa, 0x6b, 0xbe, 0x7c, 0x82, 0x5c, 0xc0, 0x00, 0x60, 0x76, 0x9f, 0x44, 0x9f, 0x90, 0x40, 0xa6, 0x2a, 0x82, 0xc1, 0x3d, 0x00, 0x00, 0x00, 0x12, 0x5a, 0xcb, 0x3f, 0xcd, 0x9e, 0x98, 0x3f, 0xdb, 0x66, 0x40, 0x40, 0x00, 0x30, 0x30, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0b, 0x0b, 0x00, 0x00, 0x00, 0x06, 0x00, 0x03};

    unsigned long crc = CalculateBlockCRC32(sizeof(buffer), buffer);
    cout << hex << crc << endl;
}

The result of this is 0x42, 0xdc, 0x4c, 0x48 - which matches the example given in the manual, so that's a nice start.

Whilst I could potentially use this algorithm in the code I am writing I would prefer to remain in Python where possible, so at this point I feel I have two options. I can either translate this into Python myself or hope that there is a built-in Python function or module capable of doing this for me, which is what I have been looking at doing. So far I have found three functions/modules:

• binascii.crc32
• zlib.crc32
• crcmod module

Of these the top two give the same incorrect result and I cannot tell any way of changing settings or specifying arguments which might influence this positively.

crcmod on the other hand has a plethora of settings and predefined functions which I think should be able to do what I am looking for. The format to create the CRC function is as follows:

crcmod.mkCrcFun(poly[, initCrc, rev, xorOut])

Of of the crucial things I found was there are predefined CRC functions, and the CRC32 version of this matches the results from binascii and zlib:

Name    Polynomial  Reversed?   Init-value  XOR-out Check
crc-32  0x104C11DB7 True    0x00000000  0xFFFFFFFF  0xCBF43926

So at least that helps me understand where the zlib and binascii variants are coming from in terms of the polynomial used.

I'm convinced that I should therefore be able to generate the same result as the C algorithm using this function, but not being well-versed in C I'm not sure how I do this. The polynomial used in the C algorithm is a reversed representation of the polynomial, so this implies that the settings above should work, but they don't generate the answer above as per the C code.

What am I looking for to determine these settings, is there a module/function which will do this that I haven't seen, or is this not going to work and I should instead just start translating that C into Python myself?

Solution

For crcmod, you need to add 1 in the front of the polynomial, as the 33rd bit needs to be 1, otherwise you get an exception saying that the degree must be 8, 16, 24 or 32. This seems to produce your expected output:

import crcmod
crc = crcmod.mkCrcFun(0x104C11DB7, 0, True, 0)

And then this following example should work properly on both Python 2 and 3:

value = bytes(bytearray(
    [0xaa, 0x44, 0x12, 0x1c, 0x2a, 0x00, 0x02, 0x20,
     0x48, 0x00, 0x00, 0x00, 0x90, 0xb4, 0x93, 0x05,
     0xb0, 0xab, 0xb9, 0x12, 0x00, 0x00, 0x00, 0x00, 
     0x45, 0x61, 0xbc, 0x0a, 0x00, 0x00, 0x00, 0x00,
     0x10, 0x00, 0x00, 0x00, 0x1b, 0x04, 0x50, 0xb3,
     0xf2, 0x8e, 0x49, 0x40, 0x16, 0xfa, 0x6b, 0xbe,
     0x7c, 0x82, 0x5c, 0xc0, 0x00, 0x60, 0x76, 0x9f, 
     0x44, 0x9f, 0x90, 0x40, 0xa6, 0x2a, 0x82, 0xc1, 
     0x3d, 0x00, 0x00, 0x00, 0x12, 0x5a, 0xcb, 0x3f, 
     0xcd, 0x9e, 0x98, 0x3f, 0xdb, 0x66, 0x40, 0x40,
     0x00, 0x30, 0x30, 0x30, 0x00, 0x00, 0x00, 0x00, 
     0x00, 0x00, 0x00, 0x00, 0x0b, 0x0b, 0x00, 0x00,
     0x00, 0x06, 0x00, 0x03]))

print(hex(crc(value))))

prints

0x484cdc42

Which is the little-endian ordered value of octets 0x42, 0xdc, 0x4c, 0x48.

Answered By - Antti Haapala