C/C++知识点之CRC校验的C语言实现-职坐标

C/C++知识点之CRC校验的C语言实现

小标 2018-09-19 来源：阅读 2056 评论 0

摘要：本文主要向大家介绍了C/C++知识点之CRC校验的C语言实现，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

本文主要向大家介绍了C/C++知识点之CRC校验的C语言实现，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

一、原理部分
CRC 算法的基本思想是将传输的数据当做一个位数很长的数，将这个数除以另一个数，得到的余数作为校验数据附加到原数据后面。除法采用正常的多项式乘除法，而加减法都采用模2运算。模2运算就是结果除以2后取余数，如3 mod 2 = 1，在计算机中就是异或运算：
例如：

要传输的数据为：1101011011
除数设为：10011
在计算前先将原始数据后面填上4个0：11010110110000，之所以要补0，补0的个数就是得到的余数位数。

采用了模2的加减法后，不需要考虑借位的问题。最后得到的余数就是CRC 校验字。为了进行CRC运算，也就是这种特殊的除法运算，必须要指定个被除数，在CRC算法中，这个被除数有一个专有名称叫做“生成多项式”。文献中提到的生成多项式经常会说到多项式的位宽（Width，简记为W），这个位宽不是多项式对应的二进制数的位数，而是位数减1。比如CRC8中用到的位宽为8的生成多项式，其实对应得二进制数有九位：100110001。
二、编程实现

假设我们的生成多项式为：100110001（简记为0x31），也就是CRC-8
则计算步骤如下：
（1）      将CRC寄存器（8-bits，比生成多项式少1bit）赋初值0
（2）      在待传输信息流后面加入8个0
（3）      While (数据未处理完)
（4）      Begin
（5）          If (CRC寄存器首位是1)
（6）              reg = reg XOR 0x31
（7）          CRC寄存器左移一位，读入一个新的数据于CRC寄存器的0 bit的位置。
（8）      End
（9）      CRC寄存器就是我们所要求的余数。
实际上，真正的CRC 计算通常与上面描述的还有些出入。这是因为这种最基本的CRC除法有个很明显的缺陷，就是数据流的开头添加一些0并不影响最后校验字的结果。因此真正应用的CRC 算法基本都在原始的CRC算法的基础上做了些小的改动。
所谓的改动，也就是增加了两个概念，第一个是“余数初始值”，第二个是“结果异或值”。
所谓的“余数初始值”就是在计算CRC值的开始，给CRC寄存器一个初始值。“结果异或值”是在其余计算完成后将CRC寄存器的值在与这个值进行一下异或操作作为最后的校验值。

加入这些变形后，常见的算法描述形式就成了这个样子了：
（1）      设置CRC寄存器，并给其赋值为“余数初始值”。
               while(数据未处理完)
               begin(8_bit)
（2）      将数据的第一个8-bit字符与CRC寄存器进行异或，并把结果存入CRC寄存器。
（3）      CRC寄存器向右移一位，MSB补零，移出并检查LSB。
（4）      如果LSB为0，重复第三步；若LSB为1，CRC寄存器与0x31相异或。
（5）      重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。
               end(8-bit)
（6）      重复第2至第5步直到所有数据全部处理完成。
（7）      最终CRC寄存器的内容与“结果异或值”进行或非操作后即为CRC值。
示例性的C代码如下所示，因为效率很低，项目中如对计算时间有要求应该避免采用这样的代码。这个代码有一个crc的参数，可以将上次计算的crc结果传入函数中作为这次计算的初始值，这对大数据块的CRC计算是很有用的，不需要一次将所有数据读入内存，而是读一部分算一次，全读完后就计算完了。这对内存受限系统还是很有用的。

#define POLY        0x1021
/**
* Calculating CRC-16 in ‘C‘
* @para addr, start of data
* @para num, length of data
* @para crc, incoming CRC
*/
uint16_t crc16(unsigned char *addr, int num, uint16_t crc)
{
    int i;
    for (; num > 0; num--)              /* Step through bytes in memory */
    {
        crc = crc ^ (*addr++ << 8);     /* Fetch byte from memory, XOR into CRC top byte*/
        for (i = 0; i < 8; i++)             /* Prepare to rotate 8 bits */
        {
            if (crc & 0x8000)            /* b15 is set... */
                crc = (crc << 1) ^ POLY;    /* rotate and XOR with polynomic */
            else                          /* b15 is clear... */
                crc <<= 1;                  /* just rotate */
        }                             /* Loop for 8 bits */
        crc &= 0xFFFF;                  /* Ensure CRC remains 16-bit value */
    }                               /* Loop until num=0 */
    return(crc);                    /* Return updated CRC */
}

上面的算法对数据流逐位进行计算，效率很低。实际上仔细分析CRC计算的数学性质后我们可以多位多位计算，最常用的是一种按字节查表的快速算法。该算法基于这样一个事实：计算本字节后的CRC码，等于上一字节余式CRC码的低8位左移8位，加上上一字节CRC右移 8位和本字节之和后所求得的CRC码。如果我们把8位二进制序列数的CRC(共256个)全部计算出来，放在一个表里，编码时只要从表中查找对应的值进行处理即可。
按照这个方法，可以有如下的代码（这个代码来自Micbael Barr的书“Programming Embedded Systems in C and C++” ）：

/*
crc.h
*/

#ifndef CRC_H_INCLUDED
#define CRC_H_INCLUDED

/*
* The CRC parameters. Currently configured for CCITT.
* Simply modify these to switch to another CRC Standard.
*/
/*
#define POLYNOMIAL          0x8005
#define INITIAL_REMAINDER   0x0000
#define FINAL_XOR_VALUE     0x0000
*/
#define POLYNOMIAL          0x1021
#define INITIAL_REMAINDER   0xFFFF
#define FINAL_XOR_VALUE     0x0000

/*
#define POLYNOMIAL          0x1021
#define POLYNOMIAL          0xA001
#define INITIAL_REMAINDER   0xFFFF
#define FINAL_XOR_VALUE     0x0000
*/

/*
* The width of the CRC calculation and result.
* Modify the typedef for an 8 or 32-bit CRC standard.
*/
typedef unsigned short width_t;
#define WIDTH (8 * sizeof(width_t))
#define TOPBIT (1 << (WIDTH - 1))

/**
* Initialize the CRC lookup table.
* This table is used by crcCompute() to make CRC computation faster.
*/
void crcInit(void);

/**
* Compute the CRC checksum of a binary message block.
* @para message, 用来计算的数据
* @para nBytes, 数据的长度
* @note This function expects that crcInit() has been called
*       first to initialize the CRC lookup table.
*/
width_t crcCompute(unsigned char * message, unsigned int nBytes);

#endif // CRC_H_INCLUDED

/*
*crc.c
*/

#include "crc.h"
/*
* An array containing the pre-computed intermediate result for each
* possible byte of input. This is used to speed up the computation.
*/
static width_t crcTable[256];

/**
* Initialize the CRC lookup table.
* This table is used by crcCompute() to make CRC computation faster.
*/
void crcInit(void)
{
    width_t remainder;
    width_t dividend;
    int bit;
    /* Perform binary long division, a bit at a time. */
    for(dividend = 0; dividend < 256; dividend++)
    {
        /* Initialize the remainder.  */
        remainder = dividend << (WIDTH - 8);
        /* Shift and XOR with the polynomial.   */
        for(bit = 0; bit < 8; bit++)
        {
            /* Try to divide the current data bit.  */
            if(remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = remainder << 1;
            }
        }
        /* Save the result in the table. */
        crcTable[dividend] = remainder;
    }
} /* crcInit() */

/**
* Compute the CRC checksum of a binary message block.
* @para message, 用来计算的数据
* @para nBytes, 数据的长度
* @note This function expects that crcInit() has been called
*       first to initialize the CRC lookup table.
*/
width_t crcCompute(unsigned char * message, unsigned int nBytes)
{
    unsigned int offset;
    unsigned char byte;
    width_t remainder = INITIAL_REMAINDER;
    /* Divide the message by the polynomial, a byte at a time. */
    for( offset = 0; offset < nBytes; offset++)
    {
        byte = (remainder >> (WIDTH - 8)) ^ message[offset];
        remainder = crcTable[byte] ^ (remainder << 8);
    }
    /* The final remainder is the CRC result. */
    return (remainder ^ FINAL_XOR_VALUE);
} /* crcCompute() */

上面代码中crcInit() 函数用来计算crcTable，因此在调用 crcCompute 前必须先调用 crcInit()。