luni, 4 august 2014

Calcularea CRC-ului pentru standardul SAE-J1850 CRC8

CRC (Cyclic redundancy check ) este o metoda matematica bazata pe polinoame care verifica integritatea datelor.
Polinomul pentru standardul SAE-J1850 este P(x) = x^4+x^3+x^2+x^0 => 11101 = 0x1D Algoritmul cel mai rapid de calcul se bazeaza pe folosirea unui lookup table. Acest vector este calculat in prealabil si valorile se folosesc direct in formula de calcul. Algoritmul este bazat pe aritmetica polinomială de tipul modulo 2
Descriere algoritm:
Algoritmul acționează repetitiv la nivelul biților executându-se operatia XOR cu numarul divizor. Bitii rezultat sunt copiați apoi direct pentru pasul urmator. Divizorul este apoi mutat un bit mai la dreapta, iar procesul se repetă până când împărțitor-ul ajunge la capătul din dreapta al rândului de intrare.
Exemplu:

11010011101100 000 - input right padded by 3 bits
1011               - divisor
01100011101100 000 - result see note *
 1011              - divisor
00111011101100 000
  1011
00010111101100 000
   1011
00000001101100 000 - note **
       1011             
00000000110100 000
        1011
00000000011000 000
         1011
00000000001110 000
          1011
00000000000101 000 
           101 1
-----------------
00000000000000 100 <--- remainder (3 bits).  Division algorithm stops here as quotient is equal to zero.

* note the first four bits are the XOR with the divisor beneath, the rest of the bits are unchanged
** that the divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero)
   (in other words, it doesn't necessarily move one bit per iteration)

Codul sursa:

#define CRC_8_POLYNOMIAL            (0x1DU)
#define CRC_8_RESULT_WIDTH          (8U)

static const uint8 crcTable[CRC_TABLE_SIZE] = {
    (0x00U), (0x1dU), (0x3aU), (0x27U), (0x74U),
    (0x69U), (0x4eU), (0x53U), (0xe8U), (0xf5U),
    (0xd2U), (0xcfU), (0x9cU), (0x81U), (0xa6U),
    (0xbbU), (0xcdU), (0xd0U), (0xf7U), (0xeaU),
    (0xb9U), (0xa4U), (0x83U), (0x9eU), (0x25U),
    (0x38U), (0x1fU), (0x02U), (0x51U), (0x4cU),
    (0x6bU), (0x76U), (0x87U), (0x9aU), (0xbdU),
    (0xa0U), (0xf3U), (0xeeU), (0xc9U), (0xd4U),
    (0x6fU), (0x72U), (0x55U), (0x48U), (0x1bU),
    (0x06U), (0x21U), (0x3cU), (0x4aU), (0x57U),
    (0x70U), (0x6dU), (0x3eU), (0x23U), (0x04U),
    (0x19U), (0xa2U), (0xbfU), (0x98U), (0x85U),
    (0xd6U), (0xcbU), (0xecU), (0xf1U), (0x13U),
    (0x0eU), (0x29U), (0x34U), (0x67U), (0x7aU),
    (0x5dU), (0x40U), (0xfbU), (0xe6U), (0xc1U),
    (0xdcU), (0x8fU), (0x92U), (0xb5U), (0xa8U),
    (0xdeU), (0xc3U), (0xe4U), (0xf9U), (0xaaU),
    (0xb7U), (0x90U), (0x8dU), (0x36U), (0x2bU),
    (0x0cU), (0x11U), (0x42U), (0x5fU), (0x78U),
    (0x65U), (0x94U), (0x89U), (0xaeU), (0xb3U),
    (0xe0U), (0xfdU), (0xdaU), (0xc7U), (0x7cU),
    (0x61U), (0x46U), (0x5bU), (0x08U), (0x15U),
    (0x32U), (0x2fU), (0x59U), (0x44U), (0x63U),
    (0x7eU), (0x2dU), (0x30U), (0x17U), (0x0aU),
    (0xb1U), (0xacU), (0x8bU), (0x96U), (0xc5U),
    (0xd8U), (0xffU), (0xe2U), (0x26U), (0x3bU),
    (0x1cU), (0x01U), (0x52U), (0x4fU), (0x68U),
    (0x75U), (0xceU), (0xd3U), (0xf4U), (0xe9U),
    (0xbaU), (0xa7U), (0x80U), (0x9dU), (0xebU),
    (0xf6U), (0xd1U), (0xccU), (0x9fU), (0x82U),
    (0xa5U), (0xb8U), (0x03U), (0x1eU), (0x39U),
    (0x24U), (0x77U), (0x6aU), (0x4dU), (0x50U),
    (0xa1U), (0xbcU), (0x9bU), (0x86U), (0xd5U),
    (0xc8U), (0xefU), (0xf2U), (0x49U), (0x54U),
    (0x73U), (0x6eU), (0x3dU), (0x20U), (0x07U),
    (0x1aU), (0x6cU), (0x71U), (0x56U), (0x4bU),
    (0x18U), (0x05U), (0x22U), (0x3fU), (0x84U),
    (0x99U), (0xbeU), (0xa3U), (0xf0U), (0xedU),
    (0xcaU), (0xd7U), (0x35U), (0x28U), (0x0fU),
    (0x12U), (0x41U), (0x5cU), (0x7bU), (0x66U),
    (0xddU), (0xc0U), (0xe7U), (0xfaU), (0xa9U),
    (0xb4U), (0x93U), (0x8eU), (0xf8U), (0xe5U),
    (0xc2U), (0xdfU), (0x8cU), (0x91U), (0xb6U),
    (0xabU), (0x10U), (0x0dU), (0x2aU), (0x37U),
    (0x64U), (0x79U), (0x5eU), (0x43U), (0xb2U),
    (0xafU), (0x88U), (0x95U), (0xc6U), (0xdbU),
    (0xfcU), (0xe1U), (0x5aU), (0x47U), (0x60U),
    (0x7dU), (0x2eU), (0x33U), (0x14U), (0x09U),
    (0x7fU), (0x62U), (0x45U), (0x58U), (0x0bU),
    (0x16U), (0x31U), (0x2cU), (0x97U), (0x8aU),
    (0xadU), (0xb0U), (0xe3U), (0xfeU), (0xd9U),
    (0xc4U)
};

/**
 * @brief : Calculation of SAE-J1850 CRC8
 * P(x) =  x^4 + x^3 + x^2 + 1 -> 0x1D
 * */
uint8 Crc( uint8 const DataPtr[],
           uint8 nBytes, 
           uint8 Crc_Polynomial, 
           uint8 InitValue )
{
  uint8 byte;
  uint8 Idx;
  uint32 crcValue = InitValue;

  /*
   * Divide the message by the polynomial, a byte at a time.
   */
  for (byte = 0; byte < nBytes; ++byte)
  {
      Idx = (DataPtr[byte] ^ crcValue) & (uint32)0x00FFU;
      crcValue = crcTable[Idx] ^ (crcValue << CRC_8_RESULT_WIDTH);
  }
  /*
   * The final remainder is the CRC.
   */
  return ~(crcValue);
}  

/**
 * @brief : AUTOSAR interface for CRC Calculation of SAE-J1850 CRC8
 * */
uint8 Crc_CalculateCRC8( const uint8* Crc_DataPtr,
                         uint32 Crc_Length,
                         uint8 Crc_StartValue8,
                         boolean Crc_IsFirstCall
                       )
{
  uint8 crc_local = E_NOT_OK;

  if(Crc_DataPtr != NULL_PTR)
  {
    if(Crc_IsFirstCall == TRUE)
    {
      crc_local = CRC_8_INITIAL_VALUE;
    }
    else
    {
      crc_local = Crc_StartValue8;
    }
    crc_local = Crc(Crc_DataPtr, Crc_Length, CRC_8_POLYNOMIAL, crc_local);
  }

  return (crc_local);
}