/** @file crc.h
 *
 * @brief Compact CRC library for embedded systems for CRC-CCITT, CRC-16, CRC-32.
 *
 * @par
 * COPYRIGHT NOTICE: (c) 2000, 2018 Michael Barr. This software is placed in the
 * public domain and may be used for any purpose. However, this notice must not
 * be changed or removed. No warranty is expressed or implied by the publication
 * or distribution of this source code.
 */

#ifndef CRC_H
#define CRC_H

// Compile-time selection of the desired CRC algorithm.
//
#if defined(CRC_CCITT)

#define CRC_NAME   "CRC-CCITT"
typedef uint16_t   crc_t;

#elif defined(CRC_16)

#define CRC_NAME   "CRC-16" 
typedef uint16_t   crc_t;

#elif defined(CRC_32)

#define CRC_NAME   "CRC-32" 
typedef uint32_t   crc_t;

#else

#error "One of CRC_CCITT, CRC_16, or CRC_32 must be #define'd."

#endif

// Public API functions provided by the Compact CRC library.
//
void    crc_init(void);
crc_t   crc_slow(uint8_t const * const p_message, int n_bytes);
crc_t   crc_fast(uint8_t const * const p_message, int n_bytes);

#endif /* CRC_H */

/*** end of file ***/

/** @file crc.c
 *
 * @brief Compact CRC generator for embedded systems, with brute force and table-
 * driven algorithm options. Supports CRC-CCITT, CRC-16, and CRC-32 standards.
 *
 * @par
 * COPYRIGHT NOTICE: (c) 2000, 2018 Michael Barr. This software is placed in the
 * public domain and may be used for any purpose. However, this notice must not
 * be changed or removed. No warranty is expressed or implied by the publication
 * or distribution of this source code.
 */

#include <stdint.h> 

#include "crc.h"

// Algorithmic parameters based on CRC elections made in crc.h.
//
#define BITS_PER_BYTE       8
#define WIDTH               (BITS_PER_BYTE * sizeof(crc_t))
#define TOPBIT              (1 << (WIDTH - 1))

// Allocate storage for the byte-wide CRC lookup table.
//
#define CRC_TABLE_SIZE      256
static crc_t                g_crc_table[CRC_TABLE_SIZE];

// Further algorithmic configuration to support the selected CRC standard.
//
#if defined(CRC_CCITT)

#define POLYNOMIAL	       ((crc_t) 0x1021)
#define INITIAL_REMAINDER      ((crc_t) 0xFFFF)
#define FINAL_XOR_VALUE	       ((crc_t) 0x0000)
#define REFLECT_DATA(X)	       (X)
#define REFLECT_REMAINDER(X)   (X)

#elif defined(CRC_16)

#define POLYNOMIAL             ((crc_t) 0x8005)
#define INITIAL_REMAINDER      ((crc_t) 0x0000)
#define FINAL_XOR_VALUE	       ((crc_t) 0x0000)
#define REFLECT_DATA(X)	       ((uint8_t) reflect((X), BITS_PER_BYTE))
#define REFLECT_REMAINDER(X)   ((crc_t) reflect((X), WIDTH))

#elif defined(CRC_32)

#define POLYNOMIAL             ((crc_t) 0x04C11DB7)
#define INITIAL_REMAINDER      ((crc_t) 0xFFFFFFFF)
#define FINAL_XOR_VALUE        ((crc_t) 0xFFFFFFFF)
#define REFLECT_DATA(X)	       ((uint8_t) reflect((X), BITS_PER_BYTE))
#define REFLECT_REMAINDER(X)   ((crc_t) reflect((X), WIDTH))

#endif

/*!
 * @brief Compute the reflection of a set of data bits around its center.
 * @param[in] data The data bits to be reflected.
 * @param[in] num2 The number of bits.
 * @return The reflected data.
 * /
static uint32_t
reflect (uint32_t data, uint8_t n_bits)
{
   uint32_t   reflection = 0x00000000;

   // NOTE: For efficiency sake, n_bits is not verified to be <= 32.

   // Reflect the data about the center bit.
   //
   for (uint8_t bit = 0; bit < n_bits; ++bit)
   {
       // If the LSB bit is set, set the reflection of it.
       //
       if (data & 0x01)
       {
           reflection |= (1 << ((n_bits - 1) - bit));
       }

       data = (data >> 1);
   }

   return (reflection);

}  /* reflect() */

/*!
 * @brief Initialize the lookup table for byte-by-byte CRC acceleration.
 *
 * @par
 * This function must be run before crc_fast() or the table stored in ROM.
 */
void
crc_init (void)
{
   // Compute the remainder of each possible dividend.
   //
   for (crc_t dividend = 0; dividend < CRC_TABLE_SIZE; ++dividend)
   {
       // Start with the dividend followed by zeros.
       //
       crc_t remainder = dividend << (WIDTH - BITS_PER_BYTE);

       // Perform modulo-2 division, a bit at a time.
       //
       for (int bit = BITS_PER_BYTE; bit > 0; --bit)
       {
           // Try to divide the current data bit.
           //
           if (remainder & TOPBIT)
           {
               remainder = (remainder << 1) ^ POLYNOMIAL;

           }
           else
           {
               remainder = (remainder << 1);
           }
   }

   // Store the result into the table.
   //
   g_crc_table[dividend] = remainder;
  }
}  /* crc_init() */

/*!
 * @brief Compute the CRC of an array of bytes, bit-by-bit.
 * @param[in] p_message	A pointer to the array of data bytes to be CRC'd.
 * @param[in] n_bytes	The number of bytes in the array of data.
 * @return The CRC of the array of data.
 */
crc_t
crc_slow   (uint8_t const * const p_message, int n_bytes)
{
   crc_t   remainder = INITIAL_REMAINDER;

   // Perform modulo-2 division, one byte at a time.
   //
   for (int byte = 0; byte < n_bytes; ++byte)
   {
       // Bring the next byte into the remainder.
       //
       remainder ^= (REFLECT_DATA(p_message[byte]) << (WIDTH - BITS_PER_BYTE));

       // Perform modulo-2 division, one bit at a time.
       //
       for (int bit = BITS_PER_BYTE; bit > 0; --bit)
       {
           // Try to divide the current data bit.
           //
           if (remainder & TOPBIT)
           {
               remainder = (remainder << 1) ^ POLYNOMIAL;
           }
           else
           {
               remainder = (remainder << 1);
           }
       }
   }

   // The final remainder is the CRC result.
   //
   return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);

}  /* crc_slow() */

/*!
 * @brief Compute the CRC of an array of bytes, byte-by-byte.
 * @param[in] p_message	A pointer to the array of data bytes to be CRC'd.
 * @param[in] n_bytes	The number of bytes in the array of data.
 * @return The CRC of the array of data.
 */ 
crc_t
crc_fast (uint8_t const * const p_message, int n_bytes)
{
   crc_t remainder = INITIAL_REMAINDER;

   // Divide the message by the polynomial, a byte at a time.
   //
   for (int byte = 0; byte < n_bytes; ++byte)
   {
       uint8_t data = REFLECT_DATA(p_message[byte]) ^
                          (remainder >> (WIDTH - BITS_PER_BYTE)); 
       remainder = g_crc_table[data] ^ (remainder << BITS_PER_BYTE);
   }

   // The final remainder is the CRC.
   //
   return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);
}  /* crc_fast() */

/*** end of file ***/