crc.c

/**
 * @file crc.c
 * @version 0.1
 * @date 2023-04-15
 * 
 * @note The parameters for each supported CRC standard are
 *       defined in the header file crc.h.  The implementations
 *       here should stand up to further additions to that list.
 * 
 */


#include "crc.h"

crc crcTable[256]; // Lookup table array.


// Derive parameters from the standard-specific parameters in crc.h.
#define WIDTH  (8 * sizeof(crc))     
#define TOPBIT (1 << (WIDTH - 1))

#if (REFLECT_DATA == TRUE)
#undef REFLECT_DATA
#define REFLECT_DATA(X) ((unsigned char)reflect((X), 8))
#else
#undef REFLECT_DATA
#define REFLECT_DATA(X) (X)
#endif

#if (REFLECT_REMAINDER == TRUE)
#undef REFLECT_REMAINDER
#define REFLECT_REMAINDER(X) ((crc)reflect((X), WIDTH))
#else
#undef REFLECT_REMAINDER
#define REFLECT_REMAINDER(X) (X)
#endif


/// @brief Reorder the bits of a binary sequence, by reflecting them about the middle position.
/// @param data The data to reflect.
/// @param nBits The number of bits in the data.
/// @return The reflection of the original data.
/// @note No checking is done that nBits <= 32.
static unsigned long reflect(unsigned long data, unsigned char nBits)
{
	unsigned long  reflection = 0x00000000;
	unsigned char  bt;

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

		data = (data >> 1);
	}

	return (reflection);

}	/* reflect() */


/// @brief Compute the CRC
/// @param message The data to compute the CRC of.
/// @param nBytes The length of the data.
/// @return The CRC of the data.
crc crcSlow(unsigned char const message[], int nBytes)
{
    crc remainder = INITIAL_REMAINDER;
    int byte;
    unsigned char bt;

    // Divide the message by the polynomial, a byte at a time.
    for (byte = 0; byte < nBytes; ++byte)
    {
        // Bring the next byte into the remainder.
        remainder ^= (message[byte] << (WIDTH - 8)); 

        // Perform modulo-2 division, a bit at a time.
        for (bt = 8; bt > 0; --bt)
        {
            // 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 (remainder ^ FINAL_XOR_VALUE); 

} /* crcSlow() */

/// @brief Populate the partial CRC lookup table.
/// @note  This function must be rerun any time the CRC standard is changed. 
///        If desired, it can be run "offline" and the table results stored 
///        in a loopup table.
void crcInit(void)
{
    crc remainder;
    int dividend;
    unsigned char bt;

    // Perform binary long division, a bit at a time.
    for (dividend = 0; dividend < 256; ++dividend)
    {
        // Start with the dividend followed by zeros.
        remainder = dividend << (WIDTH - 8);

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

        // Store the result into the table.
        crcTable[dividend] = remainder;
    }

} /* crcInit() */


/// @brief Compute the CRC of a given message.
/// @param message The data to compute the CRC of.
/// @param nBytes The length of the data.
/// @return The CRC of the data.
/// @note crcInit() must be called first.
crc crcFast(const unsigned char *message, int nBytes)
{
    crc remainder = INITIAL_REMAINDER;
    unsigned char data;
    int byte;

    // Divide the message by the polynomial, a byte at a time.
    for (byte = 0; byte < nBytes; ++byte)
    {
        data = REFLECT_DATA(message[byte]) ^ (remainder >> (WIDTH - 8));
    	remainder = crcTable[data] ^ (remainder << 8);
    }

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

} /* crcFast() */

crc.h

/**
 * @file crc.h
 * @version 0.1
 * @date 2023-04-15
 *
 */

#ifndef _crc_h
#define _crc_h

#define FALSE 0
#define TRUE  !FALSE

/*
 * Select the CRC standard from the list that follows.
 */
#define CRC8

#if defined(CRC_CCITT)

typedef unsigned short crc;

#define CRC_NAME          "CRC-CCITT"
#define POLYNOMIAL        0x1021
#define INITIAL_REMAINDER 0xFFFF
#define FINAL_XOR_VALUE   0x0000
#define REFLECT_DATA      FALSE
#define REFLECT_REMAINDER FALSE
#define CHECK_VALUE       0x29B1

#elif defined(CRC8)

typedef unsigned char  crc;

#define CRC_NAME			"CRC-8"
#define POLYNOMIAL			0x07
#define INITIAL_REMAINDER	0x00
#define FINAL_XOR_VALUE		0x00
#define REFLECT_DATA		0
#define REFLECT_REMAINDER	0
#define CHECK_VALUE			0xF4

#elif defined(CRC16)

typedef unsigned short crc;

#define CRC_NAME          "CRC-16"
#define POLYNOMIAL        0x8005
#define INITIAL_REMAINDER 0x0000
#define FINAL_XOR_VALUE   0x0000
#define REFLECT_DATA      TRUE
#define REFLECT_REMAINDER TRUE
#define CHECK_VALUE       0xBB3D

#elif defined(CRC32)

typedef unsigned long crc;

#define CRC_NAME          "CRC-32"
#define POLYNOMIAL        0x04C11DB7
#define INITIAL_REMAINDER 0xFFFFFFFF
#define FINAL_XOR_VALUE   0xFFFFFFFF
#define REFLECT_DATA      TRUE
#define REFLECT_REMAINDER TRUE
#define CHECK_VALUE       0xCBF43926

#else
#error "One of CRC_CCITT, CRC16, or CRC32 must be #define'd."
#endif

void crcInit(void);
crc  crcSlow(unsigned char const message[], int nBytes);
crc  crcFast(unsigned char const message[], int nBytes);

#endif /* _crc_h */