Implementation and Optimization of CRC16 Checksum Calculation Function

Introduction

In serial communication protocols such as RS232 or RS485, data integrity verification is crucial for reliable communication. Cyclic Redundancy Check (CRC), as an efficient error detection mechanism, is widely used in various communication systems. Based on a specific CRC16 implementation issue, this article delves into the detailed differences in algorithm implementation and their correction methods.

Fundamentals of CRC16 Algorithm

The CRC16 algorithm uses a generator polynomial to compute a data stream, producing a 16-bit checksum. Different implementations may vary in initial values, bit processing order, and output handling, leading to different results for the same input. For example, the CRC16 implementation with polynomial 0x8005 requires special attention to the direction of data bit processing.

Analysis of Original Code

The original code processes data bits starting from the most significant bit of each byte, which may cause mismatches with some standard implementations. The core logic of the original code is as follows:

#include <stdint.h>

#define CRC16 0x8005

uint16_t gen_crc16(const uint8_t *data, uint16_t size)
{
    uint16_t out = 0;
    int bits_read = 0, bit_flag;

    if(data == NULL)
        return 0;

    while(size > 0)
    {
        bit_flag = out >> 15;
        out <<= 1;
        out |= (*data >> (7 - bits_read)) & 1;
        bits_read++;
        if(bits_read > 7)
        {
            bits_read = 0;
            data++;
            size--;
        }
        if(bit_flag)
            out ^= CRC16;
    }
    return out;
}

This code processes data from the high bit and lacks subsequent CRC register handling and bit reversal steps, resulting in outputs that do not match standard calculators.

Detailed Correction Solution

To align the code with online CRC calculators (e.g., lammertbies.nl), three key modifications are necessary:

a) Process Data from Least Significant Bit

Change the data bit processing order to start from the least significant bit of each byte, modifying the code as follows:

out |= (*data >> bits_read) & 1;

This ensures that data bits enter the CRC calculation in the order commonly used in hardware implementations.

b) Push Out the Last 16 Bits of CRC Register

After data processing, perform 16 additional shift and XOR operations to ensure all bits are fully processed by the polynomial:

int i;
for (i = 0; i < 16; ++i) {
    bit_flag = out >> 15;
    out <<= 1;
    if(bit_flag)
        out ^= CRC16;
}

c) Reverse CRC Output Bits

Finally, reverse the bits of the generated CRC value to match the output format of some hardware implementations:

uint16_t crc = 0;
i = 0x8000;
int j = 0x0001;
for (; i != 0; i >>=1, j <<= 1) {
    if (i & out) crc |= j;
}

Complete Corrected Code

The full function integrating the above modifications is as follows:

#define CRC16 0x8005

uint16_t gen_crc16(const uint8_t *data, uint16_t size)
{
    uint16_t out = 0;
    int bits_read = 0, bit_flag;

    if(data == NULL)
        return 0;

    while(size > 0)
    {
        bit_flag = out >> 15;
        out <<= 1;
        out |= (*data >> bits_read) & 1;
        bits_read++;
        if(bits_read > 7)
        {
            bits_read = 0;
            data++;
            size--;
        }
        if(bit_flag)
            out ^= CRC16;
    }

    int i;
    for (i = 0; i < 16; ++i) {
        bit_flag = out >> 15;
        out <<= 1;
        if(bit_flag)
            out ^= CRC16;
    }

    uint16_t crc = 0;
    i = 0x8000;
    int j = 0x0001;
    for (; i != 0; i >>=1, j <<= 1) {
        if (i & out) crc |= j;
    }

    return crc;
}

Testing with input data "123456789", this function returns 0xbb3d, consistent with online calculator results.

Other Implementation References

Another common CRC16 CCITT implementation uses lookup tables or different polynomial handling methods, for example:

unsigned short crc16(const unsigned char* data_p, unsigned char length){
    unsigned char x;
    unsigned short crc = 0xFFFF;

    while (length--){
        x = crc >> 8 ^ *data_p++;
        x ^= x>>4;
        crc = (crc << 8) ^ ((unsigned short)(x << 12)) ^ ((unsigned short)(x <<5)) ^ ((unsigned short)x);
    }
    return crc;
}

This method improves efficiency through precomputation and combined operations but requires ensuring that the polynomial, initial value, and output processing match the target standard.

Conclusion

Correct implementation of the CRC16 algorithm requires careful alignment with the specific polynomial specifications, including bit processing order, initial value setting, and output handling. Through the detailed analysis and code examples in this article, readers can better understand these key details and implement reliable CRC verification functions in practical projects.