DaniWeb Forum Index > Software Development > C++

Question on implementation on CRC (Cyclic Redundancy Code) algorithm.

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Aug 2008

Posts: 1

Reputation: mfareed is an unknown quantity at this point

Solved Threads: 0

mfareed

Offline

Newbie Poster

Question on implementation on CRC (Cyclic Redundancy Code) algorithm.

Aug 21st, 2008

Can somebody help me with the CRC (Cyclic Redundancy Code) algorithm implementation given below:

There is a three byte packet header.

<--------1st byte-----><--------2nd byte-----><--------3rd byte------------->
---------------------------------------------------------------------------------------------
| 8bits | 8bits | 3 bits| 5 bits (CRC ) |
---------------------------------------------------------------------------------------------

for example: 0D 0B 40 ---> Input Data stream ( 19 bits)
04 ---> CRC ( 5bits)
Now combining 0D 0B 44 ----> Data stream after CRC (24 bits)

The function addCrc() generates a 5 bit CRC checksum, which is the part of the header. I am not getting how this checksum is implemented?

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
 
    inline void byteUpdate(unsigned char data);
    void addCrc(unsigned char* start);
    unsigned char byteCrc[256];
    unsigned char shftRgstr;
    unsigned char k;
    unsigned short i;
    unsigned short j;
 
 
 // CRC generator polynomial x^5+x^2+1 represented in a byte, starting
// from the most significant bit, excluding the first bit
 
const unsigned char Aal2CpsPoly = 0x28; 
 
// Below table generated is used in calculating the CRC 
{
  for (i=0; i<256; i++)
  {
    byteCrc[255-i] = 0;
 
    for (j = 0xff80 - i*0x0100; j != 0x8000; j <<= 1)
    {
      if ((byteCrc[255-i] & 0x80) ^ ((j & 0x8000) >> 8))
      {
        byteCrc[255-i] <<= 1;
        byteCrc[255-i] ^= Aal2CpsPoly;
      } else
      {
        byteCrc[255-i] <<= 1;
      }
    }
  }
}
 
 
void Aal2CpsCrc::byteUpdate(unsigned char data)
{
  shftRgstr = byteCrc[shftRgstr ^ data];
}
 
 
// Function used in calculating the CRC
void Aal2CpsCrc::addCrc(unsigned char* start)
{
  shftRgstr = 0;
  byteUpdate(*start++);
  byteUpdate(*start++);
 
  for (k = (*start & 0xe0) | (0x10); k != 0x80; k <<= 1)
  {
    if ((shftRgstr & 0x80) ^ (k & 0x80))
    {
      shftRgstr <<= 1;
      shftRgstr ^= Aal2CpsPoly;  
    } else
    {
      shftRgstr <<= 1;
    }
  }
 
  *start = (*start & 0xe0) | (shftRgstr >> 3);
}
 
    inline void byteUpdate(unsigned char data);
    void addCrc(unsigned char* start);
    unsigned char byteCrc[256];
    unsigned char shftRgstr;
    unsigned char k;
    unsigned short i;
    unsigned short j;

 
 // CRC generator polynomial x^5+x^2+1 represented in a byte, starting
// from the most significant bit, excluding the first bit
 
const unsigned char Aal2CpsPoly = 0x28; 
 
// Below table generated is used in calculating the CRC 
{
  for (i=0; i<256; i++)
  {
    byteCrc[255-i] = 0;
 
    for (j = 0xff80 - i*0x0100; j != 0x8000; j <<= 1)
    {
      if ((byteCrc[255-i] & 0x80) ^ ((j & 0x8000) >> 8))
      {
        byteCrc[255-i] <<= 1;
        byteCrc[255-i] ^= Aal2CpsPoly;
      } else
      {
        byteCrc[255-i] <<= 1;
      }
    }
  }
}

 
void Aal2CpsCrc::byteUpdate(unsigned char data)
{
  shftRgstr = byteCrc[shftRgstr ^ data];
}
 
 
// Function used in calculating the CRC
void Aal2CpsCrc::addCrc(unsigned char* start)
{
  shftRgstr = 0;
  byteUpdate(*start++);
  byteUpdate(*start++);
 
  for (k = (*start & 0xe0) | (0x10); k != 0x80; k <<= 1)
  {
    if ((shftRgstr & 0x80) ^ (k & 0x80))
    {
      shftRgstr <<= 1;
      shftRgstr ^= Aal2CpsPoly;  
    } else
    {
      shftRgstr <<= 1;
    }
  }
 
  *start = (*start & 0xe0) | (shftRgstr >> 3);
}

As per my understanding the CRC has been calculated by division method. The divisor ("generator polynomial") is x^5+x^2+1 (100101). Dividend (Input Data stream) is 0D 0B 40 ( 0000 1101 0000 1011 0100 0000)

The width(W) of a poly is the actual bit position of the
highest bit. For example, the width of 10011 is 4, not 5. For the
Having chosen a poly, we can proceed with the calculation. This is
simply a division (in CRC arithmetic) of the message by the poly. The
only trick is that W zero bits are appended to the message before the
CRC is calculated. Thus we have:

Original message : 0000 1101 0000 1011 0100 0000
Poly :100101
Message after appending W zeros : 0000 1101 0000 1011 0100 0000 0000 0

Now we simply divide the augmented message by the poly using CRC

____ 00101111111011110_______________________
100101) 1101 0000 1011 0100 0000 0000 0 Augmented message (0000 1101 0000 1011 0100 0000 + 00000)
1001 01
-----------
001010
000000
----------
.
.
.
.
and so on
.
.
001100
000000
-----------
01100 = Remainder = CRC
Note: The sum uses CRC addition(Binary Arithmetic with No Carries, that is XOR operation)

The manually calculated CRC(01100) is not matching with the calculated CRC (04 - 00100) from the above algorithm. So can somebody help me in resolving this discrepancies?

Regards,
Mohammed Fareed
----------------------------------------------------------------------------------------------------------------------------------------------------

Last edited by Ancient Dragon; Aug 22nd, 2008 at 12:44 am. Reason: add code tags