Crc32 C or C++ Implementation

CRC32 C or C++ implementation

Use the Boost C++ libraries. There is a CRC included there and the license is good.

C# Crc32 implementation

The following parameters produce the desired result 280ACDA5:

Initializer = 0xFFFFFFFF,
TruncatedPolynomial = 0x04C11DB7,
FinalXorValue = 0x00000000,
ReverseResultBeforeFinalXor = true,
ReverseDataBytes = true

---

This is identical (except for the order of the bytes) to the online tools:

https://crccalc.com/

http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

---

The complete C# code is:

using System;
using static Nito.HashAlgorithms.CRC32;
                    
public class Program
{
    public static void Main()
    {
        var definition = new Definition
        {
            Initializer = 0xFFFFFFFF,
            TruncatedPolynomial = 0x04C11DB7,
            FinalXorValue = 0x00000000,
            ReverseResultBeforeFinalXor = true,
            ReverseDataBytes = true
        };

        var inputHex = "3D020000000F0000112233445566778899AABBCCDDEEFF";
        var input = Convert.FromHexString(inputHex);
        var whow = new Nito.HashAlgorithms.CRC32(definition);
        
        var crc32 = whow.ComputeHash(input);
        var crc32Hex = Convert.ToHexString(crc32);
        Console.WriteLine(crc32Hex); // 280ACDA5
    }
}

Crc32 C implementation - doesn't work

//typedef struct {
//    unsigned short xor;
//} xor_context;//--> Not sure what part this plays in the code!

void crc32_init(crc32_context *context) {
    context->crc = 0xFFFFFFFF;
}

void crc32_update(crc32_context *context, unsigned char byte) {
    uint32_t crc, mask;

    crc = context->crc;
    crc = crc ^ byte;
    for (int j = 7; j >= 0; j--) {    // Do eight times.
        mask = -(crc & 1);
        crc = (crc >> 1) ^ (0xEDB88320 & mask);
    }
    //context->crc = ~crc; //<-- Don't perform for every byte.
    context->crc = crc; //EDIT: Forgot this!
}

//Completes the check.
uint32_t crc32_complete(crc32_context *context){
    return ~context->crc;
}

Fast CRC algorithm?

CRC implementations use tables for speed. They are not required.

Here is a short CRC32 using either the Castagnoli polynomial (same one as used by the Intel crc32 instruction), or the Ethernet polynomial (same one as used in zip, gzip, etc.).

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

/* CRC-32C (iSCSI) polynomial in reversed bit order. */
#define POLY 0x82f63b78

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

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 initial crc value should be zero. The routine can be called successively with chunks of the data to update the CRC. You can unroll the inner loop for speed, though your compiler might do that for you anyway.

Same crc32 for Python and C

I'm using right now zlib.crc32, but for C there is no such library

Um, yes, there is. It's called zlib. zlib is written in C, and it's what Python is using! Hence the name of the class.

You can use the crc32() function in zlib. That implementation is a fair bit faster than others you might find. Read zlib.h for the interface information.

You can compile zlib yourself, or it may already be installed on your system.

Update:

I now see your comment (which should be edited into the question since it is critical to getting the right answer) that you have extremely limited memory. Then you can use this:

static uint32_t crc32(uint32_t crc, 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) ^ 0xedb88320 : crc >> 1;
    }
    return ~crc;
}

The crc is initially set to zero.

The use of ~ will give the correct result, since the uint32_t type in stdint.h is assured to be 32 bits.

If you can afford a little more code space, then unrolling the loop will likely speed it up (if the compiler doesn't already do this):

static uint32_t crc32(uint32_t crc, unsigned char *buf, size_t len)
{
    crc = ~crc;
    while (len--) {
        crc ^= *buf++;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
        crc = crc & 1 ? (crc >> 1) ^ 0xedb88320 : crc >> 1;
    }
    return ~crc;
}

You said that you only have 4 KBytes of "memory". Is that just working memory for the program, or does the program have to live there as well? If you have more space in flash for example for the code, then the table can be precomputed and stored with the code. A table-driven CRC will be much faster. The zlib code provides table-driven CRCs that do one byte at a time and four-bytes at a time, requiring respectively a 1Kbyte or 4Kbyte table.

Update 2:

Since you answered in a comment that the 4KBytes are just working memory, then you should use a table-driven CRC. You can simply use the crc32() function in zlib's crc32.c and the table in crc32.h with BYFOUR undefined.

definitive CRC for C

No. There is no "definitive CRC" as CRC represents a set of algorithms based upon polynomials. Various [ambiguous] common names are usually given based on size (e.g. CRC-8, CRC-32). Unfortunately, there are several different versions for most sizes.

Wikipedia's Cyclic Redundancy Check entry lists some common variants, but the correct checksum for the given domain must be used or else there will be incompatibilities. (See my comment to Mike's answer for just how confusing this can be!)

Anyway, pick a suitable implementation and use it - there is no shortage of examples that can be found online. If there happens to be a library that provides a suitable implementation then, by all means, use that. However, there is no "standard" C library for this.

Here are a few resources:

• A "CRC16" (CRC-16-CCITT) implementation on AutomationWiki.
• Implementing The CCITT Cyclical Redundancy Check on Dr Dobbs.
• The IEEE 802.3 Cyclic Redundancy Check article by Chris Borrelli discusses an obsolete Xilinx tool to generate Verilog (i.e. "to hardware") implementations.
• See associated question CRC32 C or C++ implementation - note that some answers relate to "CRC32" (IEEE 802.3) and others to Adler-32.
• The librock library, boost, source for cksum from GNU core utils ..

Difference between crc32() implementations of linux/crc32.h and zlib.h in C

It appears that someone was disturbed by the fact that the standard Ethernet (PKZIP, ITU V.42 etc. etc.) CRC-32 does a pre- and post-exclusive-or with 0xffffffff. So the version in the Linux kernel leaves that out, and expects the application to do that. Go figure.

Anyway, you can get the same result as the (correct) zlib crc32(), using the (non-standard) Linux crc32() instead, thusly:

crc_final = crc32(crc_initial ^ 0xffffffff, buf, len) ^ 0xffffffff;

In fact, that exact same code would allow you to duplicate the Linux crc32() using the zlib crc32() as well.

---

Related Topics