CCITT CRC 16 Bit Start Value 0xffff

Question

I need to calculate a CCITT 16 bit checksum value for data passed as a parameter together with the length. If I fill my array TempStr with the test data "123456789", use the polynomial 0x8408 with the length excluding the null termination character, I get the result string 6E90(Hex). Together with the null termination char I get 907A. When I swap out the polynomial to 0x1201 then I get results 29E2(Hex) and EFE8(Hex) with and without termination character.

My questions are: Do I need to calculate the CRC with or without the null termination character to obtain the correct value? Do I use the polynomial 0x1201 or the reverse polynomial 0x8408 in the algorithm? Is the correct CRC of the given data 0x29B1? I need the correct value to determine if the function works correctly.. Is the algorithm to calculate this specific CRC type correct? wData=(unsigned int)0xff & *pData++?? If someone can explain to me what is wrong and how to fix my problem I would much appreciate it. Thank you

This is the code that uses and displays the calculate_CRC16 function:

CHAR_t TestStr[] = {"123456789"};
unsigned short CrcTest = calculate_CRC16(TestStr,sizeof(TestStr)-1);
QString CrcDisplay = QString("CrcTest : %1").arg(CrcTest);
ui->txtDebug->setText(CrcDisplay);

This is the calculate_CRC16 function:

UINT16_t MainWindow::calculate_CRC16(CHAR_t* pData, UINT16_t wLength)
{

  UCHAR_t i;
  UINT16_t wData;
  UINT16_t wCrc = 0xffff;

  if (wLength == 0)
    return (~wCrc);

  do
  {
    for (i=0, wData=(unsigned int)0xff & *pData++; i < 8; i++, wData >>= 1)
    {
        if ((wCrc & 0x0001) ^ (wData & 0x0001))
            wCrc = (wCrc >> 1) ^ CRC_POLY;
        else  wCrc >>= 1;
    }
  } while (--wLength);

  wCrc = ~wCrc;
  wData = wCrc;
  wCrc = (wCrc << 8) | (wData >> 8 & 0xff);

  return (wCrc);
}

Solution 1

The result of 0x29b1 is for the "false" CCITT CRC-16 (link to CRC catalog). Which is apparently the one you need. From the catalog:

width=16 poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1 name="CRC-16/CCITT-FALSE"

So there is no bit reversal (refin, refout false). The CRC is initialized with 0xffff and is not post-processed.

To fix your code with the least changes:

if (wLength == 0)
    return wCrc;

do
{
    for (i=0, wData=((unsigned int)0xff & *pData++) << 8; i < 8; i++, wData <<= 1)
    {

        if ((wCrc & 0x8000) ^ (wData & 0x8000))
            wCrc = (wCrc << 1) ^ 0x1021;
        else  wCrc <<= 1;
    }
} while (--wLength);

return wCrc & 0xffff;

or to do it more reasonably:

while (wLength--) {
    wCrc ^= *(unsigned char *)pData++ << 8;
    for (i=0; i < 8; i++)
        wCrc = wCrc & 0x8000 ? (wCrc << 1) ^ 0x1021 : wCrc << 1;
}
return wCrc & 0xffff;

Solution 2

If you have a look at, it will calculate the CRC for different strings (or hex sequences, for checking with or without NUL) http://www.lammertbies.nl/comm/info/crc-calculation.html

According to that, you should NOT calculate including the terminating zero to get the value of 0x29B1 for your calculation.

Since you are starting with the low bit, you should be using the "non-reverse" polynomial.

I think the problem is that you are shifting the wrong way when you are shifting the "wCrc" in your calculation.

In other words:

wCrc = (wCrc >> 1) ^ CRC_POLY;

should be:

wCrc = (wCrc << 1) ^ CRC_POLY;

and likewise:

wCrc >>= 1;

should be:

wCrc <<= 1;

However, I'm not 100% certain.

Solution 3

There are a number of different variants of CRC algorithms.

• Bit-by-bit calculation versus lookup-table
• Reflected bytes versus non-reflected bytes (MSbit or LSbit first).
• Appending of augmented bits at the end of the message, or not.

That last point is a matter of confusion. Going back to CRC theory, CRC can be seen as long division in GF(2), where the result is the remainder of long division. To do a correct calculation according to base theory, n zero bits must be appended to the end of the message in order to get the right answer. There are CRC algorithms which do the calculation this way.

However, more commonly CRC algorithms are done a different way, so that the message doesn't need zero bits appended to the end of the message. This calculation is often called the "direct algorithm". It is more convenient to use, and functionally equivalent, except that any "initial value" of the algorithm needs to be modified to account for this variant algorithm.

In the case of CRC-16/CCITT, this results in confusion as to the correct initial value: should it be 0xFFFF or 0x1D0F? Arguably, 0xFFFF is the correct initial value for the algorithm that appends augmented bits to the message. If using the "direct algorithm", the initial value must be set to 0x1D0F to get the same result.

So you need to be aware of this difference, and use whichever one is needed to inter-work with the program/system you're interfacing with.

Further reading:

• CRC-CCITT -- 16-bit (other source)
• Chapter 10, "A Slightly Mangled Table-Driven Implementation", of A Painless Guide to CRC Error Detection Algorithms by Ross Williams
• CRC-16/AUG-CCITT versus CRC-16/CCITT-FALSE in the Catalogue of parametrised CRC algorithms
• Online CRC calculator which allows calculating with "nondirect" and "direct" algorithms, and converting the initial values between these two algorithms.