CODEWITHSUNDEEP
ccrc16
abhiarora
abhiarora

Reputation: 10430

CRC16-CCITT Incorrect result?

I am making a program which will communicate with a bootloader to update the firmware of a microcontroller. Everything is ready except the CRC calculation.

I have used CRC calculation function from here to calculate CRC16 for polynomial x16 + x12 + x5 + 1 (0b10001000000100001).

But the result for input 0x3304000012345678 is coming out to be wrong. I have checked over this website. Also, i have double checked with a python script which i am replicating in C. The python script calculates the CRC correctly.

Here is the code from the website:

uint16_t crc16(uint8_t *data_p, unsigned length)
{
  unsigned char i;
  unsigned int data;
  unsigned int crc = 0xffff;

  if (length == 0)
        return (~crc);

  do
  {
        for (i=0, data=(unsigned int)0xff & *data_p++;
             i < 8; 
             i++, data >>= 1)
        {
              if ((crc & 0x0001) ^ (data & 0x0001))
                    crc = (crc >> 1) ^ POLY;
              else  crc >>= 1;
        }
  } while (--length);

  crc = ~crc;
  data = crc;
  crc = (crc << 8) | (data >> 8 & 0xff);

  return (crc);
}

Upvotes: 1

Views: 1809

Answers (2)

Jonathan Gilbert
Jonathan Gilbert

Reputation: 3840

I've compared the C code you posted with the algorithm at the web site you linked, and I've found two main differences:

1) The C code you posted processes the bits in the reverse order of the web site. This is true for both the CRC calculation itself (shifts right, where the web site shifts left), and for the processing of each byte of input (processes the least significant bit first, where the web site processes the most significant bit first).

2) The C code inverts all the bits in the CRC value before returning it, and also swaps the low and high bytes. The web site's algorithm includes no such post-processing.

I've updated the C code you pasted to match the web site:

uint16_t crc16(const uint8_t *data_p, unsigned length)
{
  unsigned char i;
  uint8_t data;
  unsigned int crc = 0; // 0xffff;

  while (length-- > 0)
  {
    for (i = 0, data = *data_p++; 
         i < 8;
         i++, data <<= 1)
    {
      if ((crc >> 15) ^ (data >> 7))
        crc = (crc << 1) ^ POLY;
      else
        crc <<= 1;

      crc &= 0xffff;
    }
  }

  return crc;
}

The differences:

1) The data local variable is now of type uint8_t.

2) The crc variable is initialized to 0 instead of 0xFFFF, as suggested by @AShelly. The web site specifically mentions that it initializes all the registers to 0 before beginning the calculation.

3) Rather than separately testing for length 0, I've restructured the loop from a 'do' loop to a 'while' loop, so that it simply doesn't enter the loop in the first place if 'length' is 0.

4) In the for loop, data is shifted left instead of right. This is because we want to process its high bit first, then the bit to the right of that, and so on -- the left shift moves each subsequent bit into the high bit position.

5) The if statement that combines the carry with the new bit of input is now comparing the high bit of the CRC (crc >> 15) with the high bit of the data (data >> 7), instead of the low bit of each. The rest of the code ensures that crc won't have a bit in the 16th position, and data won't have a bit in the 8th position, so these shifts are guaranteed to yield a single bit only.

6) The actual crc calculation shifts to the left instead of the right.

7) After shifting crc to the left, I mask off any bits from position 16 on. This is the part of the code mentioned in point 4 that makes sure that crc >> 15 yields only a single bit. (This could also be done by making crc be of type uint16_t.)

8) The post-processing code is removed. The final crc value is returned as it is when the loop completes.

With these changes, the CRCs produced by the C function match the web site.

Upvotes: 3

AShelly
AShelly

Reputation: 35540

CRC-16 is not a unique spec, it depends on initializer and polynomial. I'd suspect the 0xFFFF The website you are using uses 0x0000 as the initializer.

In a past job we used this website to verify implementations, after first verifying the website results for several known inputs.

Upvotes: 1

Related Questions