CRC-15 giving wrong values

Question

I am trying to create a CRC-15 check in c and the output is never correct for each line of the file. I am trying to output the CRC for each line cumulatively next to each line. I use: #define POLYNOMIAL 0xA053 for the divisor and text for the dividend. I need to represent numbers as 32-bit unsigned integers. I have tried printing out the hex values to keep track and flipping different shifts around. However, I just can't seem to figure it out! I have a feeling it has something to do with the way I am padding things. Is there a flaw to my logic?

The CRC is to be represented in four hexadecimal numbers, that sequence will have four leading 0's. For example, it will look like 0000xxxx where the x's are the hexadecimal digits. The polynomial I use is 0xA053.

I thought about using a temp variable and do 4 16 bit chunks of code per line every XOR, however, I'm not quite sure how I could use shifts to accomplish this so I settled for a checksum of the letters on the line and then XORing that to try to calculate the CRC code.

I am testing my code using the following input and padding with . until the string is of length 504 because that is what the pad character needs to be via the requirements given: "This is the lesson: never give in, never give in, never, never, never, never - in nothing, great or small, large or petty - never give in except to convictions of honor and good sense. Never yield to force; never yield to the apparently overwhelming might of the enemy."

The CRC of the first 64 char line ("This is the lesson: never give in, never give in, never, never,) is supposed to be 000015fa and I am getting bfe6ec00.

My logic:

• In CRCCalculation I add each character to a 32-bit unsigned integer and after 64 (the length of one line) I send it into the XOR function.

• If it the top bit is not 1, I shift the number to the left one causing 0s to pad the right and loop around again.

• If the top bit is 1, I XOR the dividend with the divisor and then shift the dividend to the left one.

• After all calculations are done, I return the dividend shifted to the left four ( to add four zeros to the front) to the calculation function

• Add result to the running total of the result

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <ctype.h>
#define POLYNOMIAL 0xA053
void crcCalculation(char *text, int length)
{
    int i;
    uint32_t dividend = atoi(text);
    uint32_t  result;
    uint32_t sumText = 0;

    // Calculate CRC
    printf("\nCRC 15 calculation progress:\n");

    i = length;

    // padding
    if(i < 504)
        {
            for(; i!=504; i++)
                {
                    //  printf("i is %d\n", i);
                    text[i] = '.';
                }
        }
    // Try calculating by first line of crc by summing the values then calcuating, then add in the next line
    for (i = 0; i < 504; i++)
        {
            if(i%64 == 0 && i != 0)
                {
                    result = XOR(POLYNOMIAL, sumText);
                    printf(" - %x\n",result);


                }
            sumText +=(uint32_t)text[i];
            printf("%c", text[i]);
        }

    printf("\n\nCRC15 result : %x\n", result);
}

uint32_t XOR(uint32_t divisor, uint32_t dividend)
{
    uint32_t divRemainder = dividend;
    uint32_t currentBit;
    // Note: 4 16 bit chunks

    for(currentBit = 32; currentBit > 0; --currentBit)
        {
            // if topbit is 1
            if(divRemainder & 0x80)
                {
                    //divRemainder = (divRemainder << 1) ^ divisor;
                    divRemainder ^= divisor;
                    printf("%x %x\n", divRemainder, divisor);
                }
            //  else
            //  divisor = divisor >> 1;
            divRemainder = (divRemainder << 1);
        }
    //return divRemainder;  , have tried shifting to right and left, want to add 4 zeros to front so >>
    //return divRemainder >> 4;
    return divRemainder >> 4;
}

Answer 1

here is a typical CRC16, extracted from: <www8.cs.umu.se/~isak/snippets/crc-16.c>

#define POLY 0x8408
/*
//                                      16   12   5
// this is the CCITT CRC 16 polynomial X  + X  + X  + 1.
// This works out to be 0x1021, but the way the algorithm works
// lets us use 0x8408 (the reverse of the bit pattern).  The high
// bit is always assumed to be set, thus we only use 16 bits to
// represent the 17 bit value.
*/

unsigned short crc16(char *data_p, unsigned short 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);
}

Since you want to calculate a CRC15 rather than a CRC16, the logic will be more complex as cannot work with whole bytes, so there will be a lot of bit shifting and ANDing to extract the desire 15 bits.

Note: the OP did not mention if the initial value of the CRC is 0x0000 or 0x7FFF, nor if the result is to be complemented, nor certain other criteria, so this posted code can only be a guide.

Answer 2

The first issue I see is the top bit check, it should be:

        if(divRemainder & 0x8000)

The question doesn't state if the CRC is bit reflected (xor data into low order bits of CRC, right shift for cycle) or not (xor data into high order bits of CRC, left shift for cycle), so I can't offer help for the rest of the code.

The question doesn't state the initial value of CRC (0x0000 or 0x7fff), or if the CRC is post complemented.

The logic for a conventional CRC is:

• xor a byte of data into the CRC (upper or lower bits)
• cycle the CRC 8 times (or do a table lookup)

After generating the CRC for an entire message, the CRC can be appended to the message. If a CRC is generated for a message with the appended CRC and there are no errors, the CRC will be zero (or a constant value if the CRC is post complemented).