CRC without knowing the data type or size

Question

I wrote a function to calculate an 8-bit CRC/checksum for unknown data types. The only restriction is the data type must be at most 4bytes/32bits.

uint8_t crc(void* _crc, ssize_t len, uint8_t _crc_seed) {
    void* _crc_cpy = malloc(len);
    memcpy(_crc_cpy, _crc, len);
    uint32_t* _crc_cpy_pointer = static_cast<uint32_t*>(_crc_cpy);
    uint8_t _crc_u[len];
    for(int i = len; i > 0; i--) {
        _crc_u[len-i] = ((*_crc_cpy_pointer)&(0xff << 8*(i-1))) >> (8*(i-1));
    }
    uint8_t crc_seed = _crc_seed;
    uint8_t crc_u;
    for(int i = 0; i < len; i++) {
        crc_u = _crc_u[i] ^= crc_seed;
        for(int i = 0; i < 8; i++) {
            crc_u = (crc_u & 0x80) ? 0x7 ^ (crc_u << 1) : (crc_u << 1);
        }
        crc_seed = crc_u;
    }
    return crc_u;
}

How can I do this better? What are things that I did incorrectly?

Answer 1

Its always informative to comment the specific crc polynomial. An 8 bit crcs is only marginally better than 8 bit checksum.

First, remove the malloc() and memcpy(). A crc is a calculation that does not affect the input data. There is no need to allocate and copy the input data. Also, your code has a memory leak because its not releasing the allocated memory.

Second, just read each byte and update the crc calculation. There is nothing to gain with an arbitrary restriction on the input data size.

Third, replace the bit by bit calculation loop with a byte wide calculation.

Answer 2

crc should be a pointer to const void, as we should not need to modify any of the input.

len ought to be std::size_t - it doesn't make sense for it to be signed.

Document the generator polynomial.

Prefer new[] to std::malloc(); prefer not allocating to either.

Variable-length arrays are not part of standard C++.

Reinterpreting as uint32_t* will give different results on platforms of different endianness.

Restricting to a maximum of 32 bits of input is very severe. And the code should check that this restriction is respected, rather than assuming correct usage. With such a small limit, we could just accept input as a std::uint_fast32_t, rather than as a pointer to memory data.

Answer 3

I see a number of things that may allow you to improve your program.

Show all required #includes

To get size_t, malloc and memcpy we need the following includes:

#include <cstdint> 
#include <cstdlib>
#include <cstring>

Because they are required by the crc routine, they are important to show.

Use const where practical

The crc function does not need to alter the passed message, so that parameter should be declared const.

Avoid using a leading underscore for items in global namespace

As you can read in this answer, global names that begin with an underscore are "reserved to the implementation;" that is, they are for your compiler rather than for you.

Don't leak memory

The code calls malloc but never calls free so it leaks memory. That's not good, but in this case it's easily fixed because the copy isn't needed anyway.

Use better names

The crc_seed is not a bad name because it suggests the meaning of the variable within the context of the function, but _crc as the input variable is a terrible name because that's not at all what it represents. I'd call it message or maybe msg instead.

Use appropriate data types

There's not much reason to have _crc passed in as a void *. It allows the user to pass in just about anything without an explicit cast, but I'd suggest that it would be better to have it be const uint8_t * instead and have the caller cast if necessary. To me, it makes the use of the variable more clear. Also, the use of ssize_t is incorrect in this instance. Read this question for details on size_t versus ssize_t. Also note that in C++, these are actually in the std namespace.

Document your code

A short comment in the code would be sufficient to make this code much more understandable to anyone reading it. In particular, the polynomial used and the fact that it processes memory from high to low (reverse from the usual) arre important points to note.

Don't introduce arbitrary restrictions

There is nothing in the signature of the crc routine that would suggest to the user that it's limited to a 32-bit message, and nothing in the code that checks for or enforces that. In this case, I'd recommend simply removing that restriction, since it's simpler than enforcing a limit.

Don't create lots of spurious variables

The _crc_cpy, crc_cpy_pointer and _crc_u variables are not necessary. What the code is attempting to do is to calculate an 8-bit CRC from high memory to low memory, so the logical way to do that is also the most straightforward:

/*
 * calculates 8-bit CRC using polynomial x^8 + x^2 + x^1 + 1
 * processing the bytes from the end of the message to the beginning
 */
std::uint8_t rev_crc(const std::uint8_t* msg, std::size_t msg_len, std::uint8_t crc_seed) {
    constexpr uint8_t poly{0x07};   // represents x^8 (implicit) + x^2 + x^1 + x^0
    for(msg += msg_len - 1; msg_len; --msg_len, --msg) {
        crc_seed ^= *msg;
        for(int i = 0; i < 8; i++) {
            crc_seed = (crc_seed & 0x80) ? poly ^ (crc_seed << 1) : (crc_seed << 1);
        }
    }
    return crc_seed;
}

Understand the engineering trade-off

This particular polynomial is not terrible, but it may be useful for you to consider alternatives. In particular, if the concern is in detecting 4-bit errors in a 32-bit message, there are other polynomials that perform better. See Koopman's CRC Zoo for more information about that, and how to interpret Hamming Distance and Hamming weights.