c++ - How to configure calculation of CRC table

Question

There are a lot of CRC calculation examples out there. Simple implementations with bit shifting and more efficient with a pre-calculated table. But there are also a lot of Parameters of a CRC beside the polynomial that affect the calculation. You can evaluate these parameters here: http://zorc.breitbandkatze.de/crc.html

These parameters are

• initial value of CRC
• reflection of input data
• reflection of output data
• final XOR value for CRC

For some "standard" CRC algorithm these parameters are well defined, like CRC-16 (CCITT). But there are some implementations that use different parameters.

My implementation has to be compatible with a CRC16 with a CCITT polynomial (x¹⁶ + x¹² + x⁵ + 1). But the data bytes and the final CRC must be reflected. I have implemented these reflection in the calculation method. But that is time consuming. For best performance it must be removed from the calculation.

How can the reflection parameters of the CRC be calculated in the initialization method?

Edit: How should I do to control each of the parameters individually? I would like to understand how the Init function actually works and how all the parameters are implemented.

typedef unsigned char uint8_t;
typedef unsigned short crc;

crc  crcTable[256];
#define WIDTH  (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH - 1))
#define POLYNOMIAL 0x1021

template<typename t>
t reflect(t v)
{
    t r = 0;

    for (int i = 0; i < (8 * sizeof v); ++i)
    {
        r <<= 1;
        r |= v&1;
        v >>= 1;
    }

    return r;
}

void Init()
{
    crc  remainder;

    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend << (WIDTH - 8);

        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & TOPBIT)
                remainder = (remainder << 1) ^ POLYNOMIAL;
            else
                remainder = (remainder << 1);
        }

        crcTable[dividend] = remainder;
    }
}

crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;

    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = reflect(message[byte]) ^ (remainder >> (WIDTH - 8));
        remainder = crcTable[data] ^ (remainder << 8);
    }

    return reflect(remainder);
}

int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";

    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);

    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04x
", result, expected);
    }
}

Answer 1

Instead of reflecting the data coming in, and the CRC coming in, and the CRC going out, you simply reflect the polynomial and the operations. You only need to do that once, when you're writing the code. The reflected polynomial is 0x8408.

typedef unsigned char uint8_t;
typedef unsigned short crc;

crc  crcTable[256];
#define POLYNOMIAL 0x8408

void Init()
{
    crc  remainder;

    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend;

        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ POLYNOMIAL;
            else
                remainder = (remainder >> 1);
        }

        crcTable[dividend] = remainder;
    }
}

crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;

    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = message[byte] ^ remainder;
        remainder = crcTable[data] ^ (remainder >> 8);
    }

    return remainder;
}

int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";

    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);

    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04x
", result, expected);
    }
}

For the general case, if the input data is reflected, then you reflect the polynomial as shown in this answer, feed the byte at the bottom, check the low bit for exclusive-oring the polynomial, and shift up. If the input data is not reflected, then you do it as in the code in your question, leaving the polynomial as is, feeding the byte at the top, check the high bit, and shift down.

In nearly all cases, the reflection of the output is the same as the reflection of the input. For all of those, there is no need for a bit reverse function. You leave the result from the shift register as is if both input and output are not reflected, or if both input and output are reflected. In only one of the 72 CRCs catalogued at the RevEng site is the reflect out different from the reflect in (CRC-12/3GPP). In that one case, you need to bit reverse the output since the input is not reflected, but the output is.

The initial CRC is simply the initial contents of the shift register. You set that once when starting the CRC. The final exclusive-or is applied to the shift register contents at the end. If you have a function that computes a CRC a piece at a time, you need to apply the final exclusive-or when entering the function as well, and also apply that final exclusive-or to the initial value that the user sees, so that the actual initial value is what ends up in the shift register.