CRC 算法，从原理到实施

最编程 2024-03-11 12:20:50

...

CRC，一种基于有限域GF(2)的多项式环的Hash算法。在GF(2)中，多项式系数只有0、1，加减运算等同于异或(XOR)运算，乘除运算与一般多项式运算一致（合并同类项时需要注意为XOR运算）

abstract.jpg

概述

在GF(2)中，多项式系数只有0、1，加减运算等同于异或(XOR)运算，乘除运算与一般多项式运算一致（合并同类项时需要注意为XOR运算）。在CRC-n算法中，有M(x)·xⁿ=Q(x)·G(x)+R(x)，M(x)为m位的数据，G(x)为一个GF(2)的n+1项的生成多项式(Poly)，M(x)·xⁿ 则是通过在数据M(x)后添加n个0形成的对应的m+n位多项式，而R(x)即为M(x)·xⁿ 除以G(x)的n位余数——即CRC校验码，Q(x)为商，直接丢弃。通过比较两次计算产生的Signature是否一致判断故障的发生

基本原理

假定M(x)=11100110，G(x)=x³ + x + 1，其中n=3，则M(x)·xⁿ=11100110000，将G(x)多项式中的各项系数取出，按降幂排列所对应的数据Poly=1011，然后对其进行除法运算：

Fig1.png

所得n位余数即为CRC——100

根据定义可以建立一个简单的CRC实现算法，模型如下图所示：
1)建立一个长度为r的CRC Register，并初始化为0
2)在M(x)后添加r个0形成M(x)·xⁿ
3)将CRC Register左移一位，将M(x)·xⁿ的MSB移入CRC Register的Bit 0
4)第3步中的从CRC Register移出的数，如果是1，则计算，CRC Register=Poly XOR CRC Register
5)重复第3步，直到M(x)·xⁿ全部移入CRC Register
6)CRC Register即为CRC校验值

Fig2.png

算法实现

Table Driven Algorithm

根据定义所建立的算法模型存在明显缺陷，按位移动处理效率低下，为此我们探索如何实现更大处理单元的算法。这次我们以CRC-32为例，按照前面的算法思路构建的模型如下图所示：

Fig3.png

设CRC Register中的Byte 3依次为：t7 t6 t5 t4 t3 t2 t1 t0，Poly中的Bit31-Bit24依次为：g7 g6 g5 g4 g3 g2 g1 g0，根据1.3.2可知，在第1次迭代中，CRC Register的MSB:t7将会决定Poly与CRC Register的异或，如果t7=1，这就会发生，反之就不会发生;在第2次迭代中，CRC Register的MSB:t6 XOR (t7*g7) 将会决定本次Poly与CRC Register的异或是否发生，即t7、t6控制第2XOR操作；同理，在第3次迭代中，CRC Register的MSB也是通过t7、t6、t5决定，即t7、t6、t5控制第3次XOR操作。故我们可以得出下述结论：k次以后的迭代的最高位的值，可以由寄存器的前k位计算得到。根据这个结论，我们可以一次性取出CRC Register的Byte 3，提前计算出8次迭代后的寄存器余式，因为高位终将会在迭代中被移出，我们只需要关心余式即可。同时XOR运算满足结合律：A XOR B XOR C = A XOR (B XOR C)

Fig4.png

上图即为Byte 3全部迭代移出的示意图，根据结合律可以看出，我们可以依据Byte 3直接确定8次异或的与否及Poly的偏移量，从而提前计算出不同偏移量的Poly间XOR的值，令其为A，易知A的高8位和Byte 3一定相等，Reg向左移出btye3，从M(x)·xⁿ读取一个byte放在byte 0，最后将A的低32位与Reg完成XOR操作。为避免与字节边界发生冲突，我们采用字节的整数倍——字节（1 byte）、字（2 byte）、双字（4 byte），故一般不采用4bit作为处理单元。由于一个字节的取值是有限的——256种，我们只要提前计算一个字节全部的A值保存到表中。运行时以byte值为索引，直接从表里取出即可

至此我们完成基于1 byte为处理单元的Table Driven，算法模型如下图所示：
1)建立一个长度为r的CRC Register，并初始化为0
2)在M(x)后添加r个0形成M(x)·xⁿ
3)将CRC Register左移一个byte，从M(x)·xⁿ读入一个byte至CRC Register的byte 0中
4)以第3步中的从CRC Register移出的byte为index，从表中取出对应的n位宽的值，将该值与CRC Register进行XOR
5)重复第3步，直到M(x)·xⁿ全部移入CRC Register6) CRC Register即为CRC校验值

Fig5.png

Direct Table Algorithm

在上述的两种算法中，我们每次都需要在M(x)后添加n个0，其并不参与运算，目的只是为了将M(x)的全部推入CRC Register而已，并且在有些情境下在M(x)后添0操作并不总是能够实现的，故通过改进计算步骤有了直接表法，避免了对原始数据的添0操作
算法流程，算法模型如下图所示：
1)建立一个长度为r的CRC Register，按照Init值对其初始化
2)将CRC Register左移一个byte，从M(x)左移一个byte，两者进行XOR
3)第2步中XOR后的值作为index，从表中取出对应的n位宽的值，将该值与CRC Register进行XOR
4)重复第2步，直到M(x)全部取出
5)CRC Register即为CRC校验值

Fig6.png

Reflected Direct Table Algorithm

在Direct Table算法中，当RefIn、RefOut为True，每次都需要对数据做颠倒操作，很麻烦。为此产生了Reflected Direct Table算法，该算法改变了CRC Register的移动方向，而不需要对M(x)做任何处理，按字节顺序读取即可，算法模型如下图所示

算法流程如下：
1)建立一个长度为r的CRC Register，按照Init值对其初始化
2)将CRC Register右移一个byte，从M(x)左移一个byte，两者进行XOR
3)第2步中XOR后的值作为index，从表中取出对应的n位宽的值，将该值与CRC Register进行XOR
4)重复第2步，直到M(x)全部取出
5)CRC Register即为CRC校验值

Fig7.png

CRC模型

Name: CRC标准

Width: 生成的CRC的位宽

Poly: 生成多项式，一般采用十六进制简记，长度为width+1，由于其最高位恒为1，故记法中不体现出来（例如：x¹⁶+x¹²+x⁵+1记为0x1021）

Init: 初始值，如果数据前添加了若干个前导零，在前述算法中，一般是检测不到的，故通过改变CRC Register中的预设值，以实现对该类型错误的检测。在Direct Table算法中用Init初始化CRC Register即可，在Table Driven算法中，不可以直接用Init初始化CRC Register，因为其等同于在原始数据前插入了Init，必须要先把CRC Register设为0，等M(x)·xⁿ移动n/8次后，即CRC Register的预设值0全部移出时，再将Init值异或进CRC Register。完成Init操作

Xorout: 结果异或值，所有计算完成后将CRC Register与Xorout进行异或作，作为最后的校验值

RefIn: 输入反转，这是一个布尔值，如果为False，则每个字节内的位顺序保持不变，即Bit 7为MSB，Bit0为LSB。如果为True，则将需要每个字节内的位顺序颠倒，即Bit 7为LSB，Bit0为MSB。这个约定在硬件CRC中是合理的，因为在串口通讯中硬件一般默认先发送字节的Bit 0，最后发送Bit 7

RefOut: 输出反转，这是一个布尔值，如果为False，则在计算结束后，直接进入Xorout环节，如果为True，则在计算结束后，将CRC Register进行颠倒后，再进入Xorout环节。注意，和RefIn颠倒字节内的位顺序不同的是，这个是将CRC Register的值作为一个整体颠倒，即Bit n到Bit0进行颠倒

实现

针对常见常用的下述CRC给出了实现方法，以供参考

#include <stdio.h>

typedef unsigned char   uint8_t;
typedef signed char     int8_t;
typedef unsigned short int  uint16_t;
typedef signed short int    int16_t;
typedef unsigned int    uint32_t;
typedef signed int      int32_t;
typedef unsigned long long int  uint64_t;
typedef signed long long int    int64_t;

uint16_t Table16[256];
uint32_t Table32[256];
uint32_t Table32Ref[256];

/********************      CRC-16/CITI False Model      ********************/
/*
Name   : "CRC-16/CITT FALSE"
Width  : 16
Poly   : 1021
Init   : FFFF
RefIn  : False
RefOut : False
XorOut : 0000
*/
/***************************************************************************/       
uint16_t CRC16_CITIFalse(uint8_t *ptr, uint32_t len);
uint8_t GenerateT16(void);


/********************      CRC-32 Model      *******************************/
/*
Name   : "CRC-32"
Width  : 32
Poly   : 04C11DB7
Init   : FFFFFFFF
RefIn  : True
RefOut : True
XorOut : FFFFFFFF
*/
/***************************************************************************/
uint32_t CRC32(const uint8_t* ptr, uint32_t len);
uint8_t GenerateT32(void);   
uint32_t CRC32Ref(const uint8_t* ptr, uint32_t len);
uint8_t GenerateT32Ref(void);
uint32_t ExchBitOrder(uint32_t data, uint8_t bitnum);

uint8_t main(void)
{
    uint8_t Table16Flag = 0;
    uint8_t Table32Flag = 0;
    uint8_t Table32RefFlag = 0;

    if (0 == Table16Flag)
    {
        printf("Calc Table16 Start...\r\n");
        GenerateT16();
        printf("Calc Table16 Over!\r\n");
        Table16Flag = 1;
    }
    if (0 == Table32Flag)
    {
        printf("\r\nCalc Table32 Start...\r\n");
        GenerateT32();
        printf("Calc Table32 Over!\r\n");
        Table32Flag = 1;
    }
    if (0 == Table32RefFlag)
    {
        printf("\r\nCalc Table32Ref Start...\r\n");
        GenerateT32Ref();
        printf("Calc Table32Ref Over!\r\n");
        Table32Flag = 1;
    }

    uint8_t test1[4] = { 0,0,0,0};
    uint8_t test2[3] = { 0xF2,0x01,0x83};
    uint8_t test3[9] = { 0x33,0x22,0x55,0xAA,0xBB,0xCC,0xDD,0xEE,0xFF};
    uint8_t test4[4] = { 0xFF,0xFF,0xFF,0xFF};
    uint8_t test5[4] = { 0x31,0x32,0x33,0x34 };

    printf("\r\n       CRC-16/CITT-FALSE Test\r\n");
    printf("____________________________________________________\r\n");
    printf(" TestData               Expecte     Actual\r\n");
    printf("____________________________________________________\r\n");
    printf("0x00000000              0x84C0      0x%X\r\n", CRC16_CITIFalse(test1,4));     
    printf("0xF20183                0xD374      0x%X\r\n", CRC16_CITIFalse(test2,3));
    printf("0x332255AABBCCDDEEFF    0xF53F      0x%X\r\n", CRC16_CITIFalse(test3,9));
    printf("0xFFFFFFFF              0x1D0F      0x%X\r\n", CRC16_CITIFalse(test4,4));
    printf("0x31323334              0x5349      0x%X\r\n", CRC16_CITIFalse(test5,4));
    printf("____________________________________________________\r\n");


    printf("\r\n       CRC-32 Test\r\n");
    printf("Algorithm : Direct Table\r\n");
    printf("__________________________________________________________\r\n");
    printf(" TestData                Expecte             Actual\r\n");
    printf("__________________________________________________________\r\n");
    printf("0x00000000              0x2144DF1C          0x%X\r\n", CRC32(test1, 4));
    printf("0xF20183                0x24AB9D77          0x%X\r\n", CRC32(test2, 3));
    printf("0x332255AABBCCDDEEFF    0xB0AE863D          0x%X\r\n", CRC32(test3, 9));
    printf("0xFFFFFFFF              0xFFFFFFFF          0x%X\r\n", CRC32(test4, 4));
    printf("0x31323334              0x9BE3E0A3          0x%X\r\n", CRC32(test5, 4));
    printf("__________________________________________________________\r\n");
    
    printf("\r\n       CRC-32 Test\r\n");
    printf("Algorithm : Reflected Direct Table\r\n");
    printf("__________________________________________________________\r\n");
    printf(" TestData        Expecte       Actual\r\n");
    printf("__________________________________________________________\r\n");
    printf("0x00000000              0x2144DF1C          0x%X\r\n", CRC32Ref(test1, 4));
    printf("0xF20183                0x24AB9D77          0x%X\r\n", CRC32Ref(test2, 3));
    printf("0x332255AABBCCDDEEFF    0xB0AE863D          0x%X\r\n", CRC32Ref(test3, 9));
    printf("0xFFFFFFFF              0xFFFFFFFF          0x%X\r\n", CRC32Ref(test4, 4));
    printf("0x31323334              0x9BE3E0A3          0x%X\r\n", CRC32Ref(test5, 4));
    printf("__________________________________________________________\r\n");

    return 0;
}

uint16_t CRC16_CITIFalse(const uint8_t *ptr,uint32_t len)       //   Algorithm:Direct Table
{
    uint16_t CrcReg = 0xFFFF;   
    uint8_t TopByte = 0;
    uint8_t index = 0;
    while (0!=len)
    {
        TopByte = (uint8_t)((CrcReg & 0xFF00) >> 8);
        CrcReg = (uint16_t)((uint32_t)CrcReg << 8);
        index = (uint8_t)(*ptr) ^ TopByte;
        CrcReg = CrcReg^Table16[index];
        ptr++;
        len--;
    }                       
    return CrcReg;
}                             

uint8_t GenerateT16(void)
{
    uint16_t i=0;
    uint16_t pxp = 0;
    for (i = 0; i < 256; i++)
    {
        pxp = 0;
        for (int8_t nbit = 7; nbit > -1; nbit--)
        {
            if (((i >> nbit) ^ (pxp >> 15)) & 0x0001)     
            {
                //待测数据位和pxp高位相异，poly进行XOR
                pxp = (uint16_t)((uint32_t)pxp << 1) ^ 0X1021;
            }
            else                                          
            {
                //待测数据位和pxp高位相同，poly不进行XOR
                pxp = (uint16_t)((uint32_t)pxp << 1);
            }
        }
        Table16[i] = pxp;
    }
    return 0;
}   

uint32_t CRC32(const uint8_t* ptr,uint32_t len)     //  Algorithm : Direct Table    
{
    uint32_t CrcReg = 0xFFFFFFFF;   
    uint8_t TopByte = 0;
    uint8_t index = 0;
    uint8_t tmp = 0;
    while (0!=len)
    {
        tmp = ExchBitOrder((uint8_t)(*ptr),8);                  //  RefIn  : True
        TopByte = (uint8_t)((CrcReg & 0xFF000000) >> 24);
        CrcReg = (uint32_t)(CrcReg << 8);
        index = (uint8_t)tmp ^ TopByte;
        CrcReg = CrcReg^Table32[index];
        ptr++;
        len--;
    }           
    CrcReg = ExchBitOrder(CrcReg,32);               //  RefOut : True
    CrcReg = CrcReg ^ 0xFFFFFFFF;                   //  XorOut : FFFFFFFF   
    return CrcReg;
}

uint8_t GenerateT32(void)
{
    uint16_t i = 0;
    uint32_t pxp = 0;
    for (i = 0; i < 256; i++)
    {
        pxp = 0;
        for (int8_t nbit = 7; nbit > -1; nbit--)
        {
            if (((i >> nbit) ^ (pxp >> 31)) & 0x00000001)     
            {
                pxp = (pxp << 1) ^ 0x04C11DB7;  //待测数据位和pxp高位相异，poly进行XOR
            }
            else                                          
            {
                pxp = pxp << 1;  //待测数据位和pxp高位相同，poly不进行XOR
            }
        }
        Table32[i] = pxp;
    }
    return 0;
}

//  Algorithm : Reflected Direct Table  
uint32_t CRC32Ref(const uint8_t* ptr, uint32_t len)     
{
    uint32_t CrcReg = 0xFFFFFFFF;
    uint8_t TopByte = 0;
    uint8_t index = 0;
    uint8_t tmp = 0;
    while (0 != len)
    {
        tmp = *ptr;                 //  RefIn  : True    X
        TopByte = (uint8_t)(CrcReg & 0x000000FF);
        CrcReg = (uint32_t)(CrcReg >> 8);
        index = (uint8_t)tmp ^ TopByte;
        CrcReg = CrcReg^Table32Ref[index];
        ptr++;
        len--;
    }
//  CrcReg = ExchBitOrder(CrcReg, 32);              //  RefOut : True    X
    CrcReg = CrcReg ^ 0xFFFFFFFF;                   //  XorOut : FFFFFFFF   
    return CrcReg;
}

uint8_t GenerateT32Ref(void)
{
    uint16_t i = 0;
    uint32_t pxp = 0;
    uint8_t iRef = 0;
    for (i = 0; i < 256; i++)
    {
        pxp = 0;
        for (int8_t nbit = 7; nbit > -1; nbit--)
        {
            if (((i >> nbit) ^ (pxp >> 31)) & 0x0001)
            {
                pxp = (pxp << 1) ^ 0x04C11DB7;  //待测数据位和pxp高位相异，poly进行XOR
            }
            else   
            {
                pxp = pxp << 1;  //待测数据位和pxp高位相同，poly不进行XOR
            }
        }
        iRef = (uint8_t)ExchBitOrder(i, 8);
        pxp = ExchBitOrder(pxp, 32);
        Table32Ref[iRef] = pxp;
    }
    return 0;
}

uint32_t ExchBitOrder(uint32_t data, uint8_t bitnum)
{
    uint32_t bar = 0;
    for (uint8_t j = 0; j < bitnum; j++)
    {
        if ((data >> j) & 0x01)
        {
            bar = (1 << (bitnum - 1 - j)) | bar;
        }
    }
    return bar;
}

Fig8.png

上一篇：在一篇文章中了解以太网和 CANoe 的配置情况

下一篇： CSS：实现颜色选择器透明度栏的两种方法（使用在线图像转换为 base64 网站）

CRC 算法，从原理到实施

概述

基本原理

算法实现

Table Driven Algorithm

Direct Table Algorithm

Reflected Direct Table Algorithm

CRC模型

实现

推荐系统从原理到策略从算法到架构产品[翻译]

从理解到深入虚拟 DOM 并实施差异算法

CRC 算法，从原理到实施

从《暗杀者》到《原神》的抽卡程序算法