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

[mfareed]

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?

    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

[weaknessforcats]

1) You are using non-ANS C++:

void Aal2CpsCrc::byteUpdate(unsigned char data)
{
  shftRgstr = byteCrc[shftRgstr ^ data];     //non-ANS C++
}
 

2) I assume you have stepped though this code exactly using your debugger. Yes?

[mfareed]

1) You are using non-ANS C++:

void Aal2CpsCrc::byteUpdate(unsigned char data)
{
  shftRgstr = byteCrc[shftRgstr ^ data];     //non-ANS C++
}
 

2) I assume you have stepped though this code exactly using your debugger. Yes?

Could you please explain me, what is the impact of non-ANS C++ code in the implementation of the given algorithm?

[Banfa]

shftRgstr = byteCrc[shftRgstr ^ data]; //non-ANS C++
[/code]

What is non-ANSI about this?

Taking the xor of 2 unsigned chars and using the result as an index into an array of unsigned chars and then assigning it to an unsigned char looks OK to me.

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

This is a mistake in your logic. In your original text you state that the message is 19 bits with a 5 bit CRC so it should be

Original message : 0000 1101 0000 1011 010

After appending W zeros you get

Original message : 0000 1101 0000 1011 0100 0000

You have put in too many zeros.