CRC校验

作者: starmier | 来源:发表于2019-11-26 11:35 被阅读0次

1. 基本概念

1.1 模2运算

模2运算是一种二进制算法，CRC校验技术中的核心部分，因此，我们在分析CRC算法之前，必须掌握模2运算的规则。与四则运算相同，模2运算也包括模2加、模2减、模2乘、模2除四种二进制运算。而且，模2运算也使用与四则运算相同的运算符，即“＋”表示模2加，“－”表示模2减，“×”或“·”表示模2乘，“÷”或“/”表示模2除。但与四则运算不同的是模2运算不考虑进位和借位，即模2加法是不带进位的二进制加法运算，模2减法是不带借位的二进制减法运算。这样，两个二进制位相运算时，这两个位的值就能确定运算结果，不受前一次运算的影响，也不对下一次造成影响。

1.1.1模2加法运算

这是一种二进制的运算，等同于“异或”运算。通常用于计算机和电子领域。
规则是:

两个序列模二相加，即两个序列中对应位，相加，不进位，相同为0，不同为1。
1+1=0+0=0
1+0=0+1=1
0＋0＝0
0＋1＝1
1＋0＝1
1＋1＝0

例如0101＋0011＝0110，列竖式计算：
0 1 01
＋ 0 0 1 1
──────
0 1 1 0

1.1.2 模2减法运算

0－0＝0
0－1＝1
1－0＝1
1－1＝0

例如0110－0011＝0101，列竖式计算：
01 1 0
－ 0 0 1 1
──────
0 1 0 1

1.1.3 模2乘法运算：

多位二进制模2乘法类似于普通意义上的多位二进制乘法，不同之处在于后者累加中间结果（或称部分积）时采用带进位的加法，而模2乘法对中间结果的处理方式采用的是模2加法。

0×0＝0
0×1＝0
1×0＝0
1×1＝1

例如1011×101＝100111，列竖式计算：
1 0 1 1
× 1 0 1
──────────
1 0 1 1
0 0 0 0
＋ 1 0 1 1
──────────
1 0 0 1 1 1

1.1.4 模2除法运算

多位二进制模2除法也类似于普通意义上的多位二进制除法，但是在如何确定商的问题上两者采用不同的规则。后者按带借位的二进制减法，根据余数减除数够减与否确定商1还是商0，若够减则商1，否则商0。多位模2除法采用模2减法，不带借位的二进制减法，因此考虑余数够减除数与否是没有意义的。实际上，在CRC运算中，总能保证除数的首位为1，则模2除法运算的商是由余数首位与除数首位的模2除法运算结果确定。因为除数首位总是1，按照模2除法运算法则，那么余数首位是1就商1，是0就商0。

0÷1＝0
1÷1＝1

例如1100100÷1011＝1110……110，列竖式计算：
1 1 10
────────
1 0 1 1 ) 1 1 0 0 1 0 0
－ 1 0 1 1
───────
1 1 1 1
－ 1 0 1 1
─────────
1 0 0 0
－ 1 0 1 1
─────────
0 1 1 0
－ 0 0 0 0
──────
1 1 0

1.2 生成多项式

1.2.1 定义

若一个循环码的所有码字多项式都是一个次数最低的非零首一多项式 g(x)的倍式，则称g(x)生成该码，并称g(x)为该码的生成元或生成多项式。

生成多项式位数 (又成为位宽) = CRC校验码位数 +1。

注意有些生成多项式的简记式中将生成多项式的最高位1省略了。

生成多项式是接受方和发送方的一个约定，也就是一个二进制数，在整个传输过程中，这个数始终保持不变。在发送方，利用生成多项式对信息多项式做模2除生成校验码。在接收方利用生成多项式对收到的编码多项式做模2除检测和确定错误位置。
应满足以下条件：

A、生成多项式的最高位和最低位必须为1。
B、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做除后应该使余数不为0。
C、不同位发生错误时，应该使余数不同。
D、对余数继续做除，应使余数循环。

1.2.2 生成原则

若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得

V(x)=A(x)g(x)=xRm(x)+r(x);

其中: m(x)为K次原始的信息多项式， r(x)为R-1次校验多项式（即CRC校验和），

g(x)称为生成多项式：

g(x)=g0+g1x1+ g2x2+...+g(R-1)x(R-1)+gRxR

发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。

结合系统的具体特点及要求，提出一种生成多项式的选取方法，其主要设计思想有以下两个方面：

（1）首先，为了确保选取的生成多项式校验性能是最优的，考察在具体嵌入式网络系统中传输数据帧最大长度的情况下，码重最大，漏检率最低的生成多项式。

（2）其次，为了确保选取的生成多项式有较广的使用范围和良好的可移植性，分别考察小于和大于最大数据帧长度的情况，生成多项式的码重及漏检率的情况。

在这里要注意的是严格按照这两个方面的优先次序考虑，在保证自身应用环境中最优检错性能的前提下考察其扩展性和可移植性。

对于最小距离相同的生成多项式，要首先选取可检测数据长度最大的生成多项式；对于较短的数据帧，如果要提高生成多项式的最小距离，必须以不影响该生成多项式对于长数据帧的校验性能为前提；对于一些现行的协议，随着网络的不断发展，也会对协议进行修正，同时也会要求增加传输数据帧的长度，因此在选择生成多项式时要考虑将来的可扩展性，使生成多项式传输较长数据帧时也能有较好的校验性能。

比如说我们有两个二进制数，分别为：1101 和1011。

1101 与如下的多项式相联系：1x3+1x2+0x1+1x0=x3+x2+x0

1011与如下的多项式相联系：1x3+0x2+1x1+1x0=x3+x1+x0

两个多项式的乘法：(x3+x2+x0)(x3+x1+x0)=x6+x5+x4+x3+x3+x3+x2+x1+x0

得到结果后，合并同类项时采用模2运算。也就是说乘除法采用正常的多项式乘除法，而加减法都采用模2运算。所谓模2运算就是结果除以2后取余数。比如3 mod 2 = 1。因此，上面最终得到的多项式为：x6+x5+x4+x3+x2+x1+x0，对应的二进制数:111111

1.2.3 最常用的几种生成多项式

CRC8=X8+X5+X4+X0

CRC-CCITT=X16+X12+X5+X0

CRC16=X16+X15+X2+X0

CRC12=X12+X11+X3+X2+X0

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X0

有一点要特别注意，文献中提到的生成多项式经常会说到多项式的位宽（Width，简记为W），这个位宽不是多项式对应的二进制数的位数，而是位数减1。比如CRC8中用到的位宽为8的生成多项式，其实对应得二进制数有九位：100110001。另外一点，多项式表示和二进制表示都很繁琐，交流起来不方便，因此，文献中多用16进制简写法来表示，因为生成多项式的最高位肯定为1，最高位的位置由位宽可知，故在简记式中，将最高的1统一去掉了，如CRC32的生成多项式简记为04C11DB7实际上表示的是104C11DB7。当然，这样简记除了方便外，在编程计算时也有它的用处。

对于上面的例子，位宽为4（W=4），按照CRC算法的要求，计算前要在原始数据后填上W个0，也就是4个0。

位宽W=1的生成多项式(CRC1)有两种，分别是X1和X1+X0，读者可以自己证明10 对应的就是奇偶校验中的奇校验，而11对应则是偶校验。因此，写到这里我们知道了奇偶校验其实就是CRC校验的一种特例，这也是我要以奇偶校验作为开篇介绍的原因了。

2. CRC 介绍

2.1 从奇偶校验说起

所谓通讯过程的校验是指在通讯数据后加上一些附加信息，通过这些附加信息来判断接收到的数据是否和发送出的数据相同。比如说RS232串行通讯可以设置奇偶校验位，所谓奇偶校验就是在发送的每一个字节后都加上一位，使得每个字节中1的个数为奇数个或偶数个。比如我们要发送的字节是0x1a，二进制表示为0001 1010。

采用奇校验，则在数据后补上个0，数据变为0001 1010 0，数据中1的个数为奇数个（3个）

采用偶校验，则在数据后补上个1，数据变为0001 1010 1，数据中1的个数为偶数个（4个）

接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。

奇偶校验的缺点也很明显，首先，它对错误的检测概率大约只有50%。也就是只有一半的错误它能够检测出来。另外，每传输一个字节都要附加一位校验位，对传输效率的影响很大。因此，在高速数据通讯中很少采用奇偶校验。奇偶校验优点也很明显，它很简单，因此可以用硬件来实现，这样可以减少软件的负担。因此，奇偶校验也被广泛的应用着。

奇偶校验就先介绍到这来，之所以从奇偶校验说起，是因为这种校验方式最简单，而且后面将会知道奇偶校验其实就是CRC 校验的一种(CRC-1)。

2.2 累加和校验

另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种，最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子：

我们要传输的信息为： 6、23、4

加上校验和后的数据包：6、23、4、33

这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算，如果累加和与最后一个字节相同的话就认为传输的数据没有错误。

累加和校验由于实现起来非常简单，也被广泛的采用。但是这种校验方式的检错能力也比较一般，对于单字节的校验和大概有1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验，是因为CRC校验在传输数据的形式上与累加和校验是相同的，都可以表示为：通讯数据校验字节（也可能是多个字节）

2.3 初识 CRC 算法

CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。还以上面例子中的数据为例：

6、23、4 可以看做一个2进制数： 0000011000010111 00000010

假如被除数选9，二进制表示为：1001

则除法运算可以表示为：

可以看到，最后的余数为1。如果我们将这个余数作为校验和的话，传输的数据则是：6、23、4、1

2.4 CRC算法的编程实现

说了这么多总算到了核心部分了。从前面的介绍我们知道CRC校验核心就是实现无借位的除法运算。下面还是通过一个例子来说明如何实现CRC校验。

假设我们的生成多项式为：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寄存器的值在与这个值进行一下异或操作作为最后的校验值。

常见的三种CRC 标准用到个各个参数如下表。

CCITT

CRC16

CRC32

校验和位宽W

生成多项式

x16+x12+x5+1

x16+x15+x2+1

x32+x26+x23+x22+x16+

x12+x11+x10+x8+x7+x5+

x4+x2+x1+1

除数（多项式）

0x1021

0x8005

0x04C11DB7

余数初始值

0xFFFF

0x0000

0xFFFFFFFF

结果异或值

0x0000

0xFFFFFFFF

加入这些变形后，常见的算法描述形式就成了这个样子了：

（1）设置CRC寄存器，并给其赋值为“余数初始值”。

（2）将数据的第一个8-bit字符与CRC寄存器进行异或，并把结果存入CRC寄存器。

（3） CRC寄存器向右移一位，MSB补零，移出并检查LSB。

（4）如果LSB为0，重复第三步；若LSB为1，CRC寄存器与0x31相异或。

（5）重复第3与第4步直到8次移位全部完成。此时一个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 */
}

上面的代码是我从http://mdfs.net/Info/Comp/Comms/CRC16.htm找到的，不过原始代码有错误，我做了些小的修改。

下面对这个函数给出个例子片段代码：

    unsigned char data1[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
    unsigned char data2[] = {'5', '6', '7', '8', '9'};
    unsigned short c1, c2;
    c1 = crc16(data1, 9, 0xffff);
    c2 = crc16(data1, 4, 0xffff);
    c2 = crc16(data2, 5, c2);
    printf("%04x\n", c1);
    printf("%04x\n", c2);

读者可以验算，c1、c2 的结果都为 29b1。上面代码中crc 的初始值之所以为0xffff，是因为CCITT标准要求的除数初始值就是0xffff。

上面的算法对数据流逐位进行计算，效率很低。实际上仔细分析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()。不过，对于嵌入式系统，RAM是很紧张的，最好将 crcTable 提前算好，作为常量数据存到程序存储区而不占用RAM空间。CRC 计算实际上还有很多内容可以介绍，不过对于一般的程序员来说，知道这些也就差不多了。余下的部分以后有时间了我再写篇文章来介绍吧。

最后，给出个 C++ 代码，实现了 CRC8、CRC16 和 CRC32 的计算。收集了常见的各种 CRC 系数。代码可以从这里下载：https://code.csdn.net/liyuanbhu/crc_compute/tree/master

#ifndef CRCCOMPUTE_H
#define CRCCOMPUTE_H
 
#include <stdint.h>
 
template <typename TYPE> class CRC
{
public:
    CRC();
    CRC(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value);
    void build(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value);
    /**
     * Compute the CRC checksum of a binary message block.
     * @para message, 用来计算的数据
     * @para nBytes, 数据的长度
     */
    TYPE crcCompute(char * message, unsigned int nBytes);
    TYPE crcCompute(char * message, unsigned int nBytes, bool reinit);
protected:
    TYPE m_polynomial;
    TYPE m_initial_remainder;
    TYPE m_final_xor_value;
    TYPE m_remainder;
    TYPE crcTable[256];
    int m_width;
    int m_topbit;
    /**
     * Initialize the CRC lookup table.
     * This table is used by crcCompute() to make CRC computation faster.
     */
    void crcInit(void);
};
 
template <typename TYPE>
CRC<TYPE>::CRC()
{
    m_width = 8 * sizeof(TYPE);
    m_topbit = 1 << (m_width - 1);
}
 
template <typename TYPE>
CRC<TYPE>::CRC(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value)
{
    m_width = 8 * sizeof(TYPE);
    m_topbit = 1 << (m_width - 1);
    m_polynomial = polynomial;
    m_initial_remainder = init_remainder;
    m_final_xor_value = final_xor_value;
 
    crcInit();
}
 
template <typename TYPE>
void CRC<TYPE>::build(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value)
{
    m_polynomial = polynomial;
    m_initial_remainder = init_remainder;
    m_final_xor_value = final_xor_value;
 
    crcInit();
}
 
template <typename TYPE>
TYPE CRC<TYPE>::crcCompute(char * message, unsigned int nBytes)
{
    unsigned int offset;
    unsigned char byte;
    TYPE remainder = m_initial_remainder;
    /* Divide the message by the polynomial, a byte at a time. */
    for( offset = 0; offset < nBytes; offset++)
    {
        byte = (remainder >> (m_width - 8)) ^ message[offset];
        remainder = crcTable[byte] ^ (remainder << 8);
    }
    /* The final remainder is the CRC result. */
    return (remainder ^ m_final_xor_value);
}
 
template <typename TYPE>
TYPE CRC<TYPE>::crcCompute(char * message, unsigned int nBytes, bool reinit)
{
    unsigned int offset;
    unsigned char byte;
    if(reinit)
    {
        m_remainder = m_initial_remainder;
    }
    /* Divide the message by the polynomial, a byte at a time. */
    for( offset = 0; offset < nBytes; offset++)
    {
        byte = (m_remainder >> (m_width - 8)) ^ message[offset];
        m_remainder = crcTable[byte] ^ (m_remainder << 8);
    }
    /* The final remainder is the CRC result. */
    return (m_remainder ^ m_final_xor_value);
}
 
class CRC8 : public CRC<uint8_t>
{
public:
    enum CRC8_TYPE {eCRC8, eAUTOSAR, eCDMA2000, eDARC, eDVB_S2, eEBU, eAES, eGSM_A, eGSM_B, eI_CODE,
                    eITU, eLTE, eMAXIM, eOPENSAFETY, eROHC, eSAE_J1850, eWCDMA};
    CRC8(CRC8_TYPE type);
    CRC8(uint8_t polynomial, uint8_t init_remainder, uint8_t final_xor_value)
        :CRC<uint8_t>(polynomial, init_remainder, final_xor_value){}
};
 
class CRC16 : public CRC<uint16_t>
{
public:
    enum CRC16_TYPE {eCCITT, eKERMIT, eCCITT_FALSE, eIBM, eARC, eLHA, eSPI_FUJITSU,
                     eBUYPASS, eVERIFONE, eUMTS, eCDMA2000, eCMS, eDDS_110, eDECT_R,
                     eDECT_X, eDNP, eEN_13757, eGENIBUS, eEPC, eDARC, eI_CODE, eGSM,
                     eLJ1200, eMAXIM, eMCRF4XX, eOPENSAFETY_A, eOPENSAFETY_B, ePROFIBUS,
                     eIEC_61158_2, eRIELLO, eT10_DIF, eTELEDISK, eTMS37157, eUSB,
                     eCRC_A, eMODBUS, eX_25, eCRC_B, eISO_HDLC, eIBM_SDLC, eXMODEM,
                     eZMODEM, eACORN, eLTE};
    CRC16(CRC16_TYPE type);
    CRC16(uint16_t polynomial, uint16_t init_remainder, uint16_t final_xor_value)
        :CRC<uint16_t>(polynomial, init_remainder, final_xor_value){}
};
 
class CRC32 : public CRC<uint32_t>
{
public:
    enum CRC32_TYPE {eADCCP, ePKZIP, eCRC32, eAAL5, eDECT_B, eB_CRC32, eBZIP2, eAUTOSAR,
                     eCRC32C, eCRC32D, eMPEG2, ePOSIX, eCKSUM, eCRC32Q, eJAMCRC, eXFER};
    CRC32(CRC32_TYPE type);
};
 
 
#endif // CRCCOMPUTE_H

#include "crcCompute.h"
 
template <typename TYPE>
void CRC<TYPE>::crcInit(void)
{
    TYPE remainder;
    TYPE dividend;
    int bit;
    /* Perform binary long division, a bit at a time. */
    for(dividend = 0; dividend < 256; dividend++)
    {
        /* Initialize the remainder.  */
        remainder = dividend << (m_width - 8);
        /* Shift and XOR with the polynomial.   */
        for(bit = 0; bit < 8; bit++)
        {
            /* Try to divide the current data bit.  */
            if(remainder & m_topbit)
            {
                remainder = (remainder << 1) ^ m_polynomial;
            }
            else
            {
                remainder = remainder << 1;
            }
        }
        /* Save the result in the table. */
        crcTable[dividend] = remainder;
    }
}
 
CRC8::CRC8(CRC8_TYPE type)
{
    switch (type)
    {
    case eCRC8:
        m_polynomial = 0x07; //http://reveng.sourceforge.net/crc-catalogue/all.htm
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eAUTOSAR:
        m_polynomial = 0x2f;
        m_initial_remainder = 0xff;
        m_final_xor_value = 0xff;
        break;
    case eCDMA2000:
        m_polynomial = 0x9b;
        m_initial_remainder = 0xFF;
        m_final_xor_value = 0x00;
        break;
    case eDARC:
        m_polynomial = 0x39;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eDVB_S2:
        m_polynomial = 0xd5;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eEBU:
    case eAES:
        m_polynomial = 0x1d;
        m_initial_remainder = 0xFF;
        m_final_xor_value = 0x00;
        break;
    case eGSM_A:
        m_polynomial = 0x1d;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eGSM_B:
        m_polynomial = 0x49;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0xFF;
        break;
    case eI_CODE:
        m_polynomial = 0x1d;
        m_initial_remainder = 0xFD;
        m_final_xor_value = 0x00;
        break;
    case eITU:
        m_polynomial = 0x07;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x55;
        break;
    case eLTE:
        m_polynomial = 0x9b;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eMAXIM:
        m_polynomial = 0x31;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eOPENSAFETY:
        m_polynomial = 0x2f;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eROHC:
        m_polynomial = 0x07;
        m_initial_remainder = 0xff;
        m_final_xor_value = 0x00;
        break;
    case eSAE_J1850:
        m_polynomial = 0x1d;
        m_initial_remainder = 0xff;
        m_final_xor_value = 0xff;
        break;
    case eWCDMA:
        m_polynomial = 0x9b;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    default:
        m_polynomial = 0x07;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    }
    crcInit();
 
}
 
CRC16::CRC16(CRC16_TYPE type)
{
    switch (type)
    {
    case eCCITT_FALSE:
    case eMCRF4XX:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xFFFF;
        m_final_xor_value = 0x0000;
        break;
    case eIBM:
    case eARC:
    case eLHA:
    case eBUYPASS:
    case eVERIFONE:
    case eUMTS:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eSPI_FUJITSU:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x1d0f;
        m_final_xor_value = 0x0000;
        break;
    case eCCITT:
    case eKERMIT:
    case eXMODEM:
    case eZMODEM:
    case eACORN:
    case eLTE:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eCDMA2000:
        m_polynomial = 0xc867;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0x0000;
        break;
    case eCMS:
    case eMODBUS:
        m_polynomial = 0x8005;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0x0000;
        break;
    case eDDS_110:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x800d;
        m_final_xor_value = 0x0000;
        break;
    case eDECT_R:
        m_polynomial = 0x0589;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0001;
        break;
    case eDECT_X:
        m_polynomial = 0x0589;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eDNP:
    case eEN_13757:
        m_polynomial = 0x3d65;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0xffff;
        break;
    case eGENIBUS:
    case eEPC:
    case eDARC:
    case eI_CODE:
    case eX_25:
    case eCRC_B:
    case eISO_HDLC:
    case eIBM_SDLC:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0xffff;
        break;
    case eGSM:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0xffff;
        break;
    case eLJ1200:
        m_polynomial = 0x6f63;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eMAXIM:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0xffff;
        break;
    case eOPENSAFETY_A:
        m_polynomial = 0x5935;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eOPENSAFETY_B:
        m_polynomial = 0x755b;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case ePROFIBUS:
    case eIEC_61158_2:
        m_polynomial = 0x1dcf;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0xffff;
        break;
    case eRIELLO:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xb2aa;
        m_final_xor_value = 0x0000;
        break;
    case eT10_DIF:
        m_polynomial = 0x8bb7;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eTELEDISK:
        m_polynomial = 0xa097;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eTMS37157:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x89ec;
        m_final_xor_value = 0x0000;
        break;
    case eUSB:
        m_polynomial = 0x8005;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0xffff;
        break;
    case eCRC_A:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xc6c6;
        m_final_xor_value = 0x0000;
        break;
    default:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    }
    crcInit();
}
 
 
CRC32::CRC32(CRC32_TYPE type)
{
    switch (type)
    {
    case eADCCP:
    case ePKZIP:
    case eCRC32:
    case eBZIP2:
    case eAAL5:
    case eDECT_B:
    case eB_CRC32:
        m_polynomial = 0x04c11db7;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eAUTOSAR:
        m_polynomial = 0xf4acfb13;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eCRC32C:
        m_polynomial = 0x1edc6f41;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eCRC32D:
        m_polynomial = 0xa833982b;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eMPEG2:
    case eJAMCRC:
        m_polynomial = 0x04c11db7;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0x00000000;
        break;
    case ePOSIX:
    case eCKSUM:
        m_polynomial = 0x04c11db7;
        m_initial_remainder = 0x00000000;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eCRC32Q:
        m_polynomial = 0x814141ab;
        m_initial_remainder = 0x00000000;
        m_final_xor_value = 0x00000000;
        break;
    case eXFER:
        m_polynomial = 0x000000af;
        m_initial_remainder = 0x00000000;
        m_final_xor_value = 0x00000000;
        break;
    default:
        m_polynomial = 0x04C11DB7;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    }
    crcInit();
}

#include <iostream>
#include <stdio.h>
#include "crcCompute.h"
 
using namespace std;
 
int main(int argc, char *argv[])
{
 
    CRC16 crc16(CRC16::eCCITT_FALSE);
    char data1[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
    char data2[] = {'5', '6', '7', '8', '9'};
    unsigned short c1, c2;
    c1 = crc16.crcCompute(data1, 9);
    c2 = crc16.crcCompute(data1, 4, true);
    c2 = crc16.crcCompute(data2, 5, false);
 
 
    printf("%04x\n", c1);
    printf("%04x\n", c2);
 
    return 0;
}