从现有的 crc 函数生成 crc16 查找 table

Question

我在一个项目中工作，其中有一个计算 CRC16 校验和的函数。

uint16_t x_crc(uint16_t CrcVal, uint8_t DataIn) {

    CrcVal = (unsigned char) (CrcVal >> 8) | (CrcVal << 8);
    CrcVal ^= DataIn;
    CrcVal ^= (unsigned char) (CrcVal & 0xff) >> 4;
    CrcVal ^= (CrcVal << 8) << 4;
    CrcVal ^= ((CrcVal & 0xff) << 4) << 1;

    return CrcVal &0xFFFF;
}

并且是这样使用的：

uint8_t x[]={1,2,3,4,5,6,7,8,9,0};
        
uint16_t CrcResult=0;
    
for (size_t i = 0; i<10; i++) {
    CrcResult = x_crc(CrcResult, *(x + i));
}    
    
printf("\n\n\nCRC1 = 0x%04X\n",CrcResult);

由于性能问题，我需要转换为查找 table。我该怎么做，使用上面的函数生成条目？

谢谢。

Answer 1

由于移位实现，不清楚这是一个多项式为0x11021的左移CRC。示例代码包括一个由 16 位 table 驱动的 256。我认为编译器优化将内联 z_crc，也就是 table。如果不是，则将函数更改为采用 3 个参数，crcvalue、缓冲区指针、字节数。

#include <stdio.h>

typedef unsigned short uint16_t;
typedef unsigned char  uint8_t;

uint16_t crctbl[256];

uint16_t x_crc(uint16_t CrcVal, uint8_t DataIn) {
    CrcVal = (unsigned char)(CrcVal>>8)|(CrcVal<<8);  /* rotate left 8 bits */
                                                /* crc ^=      (byte*0x10000)>>16 */
    CrcVal ^= DataIn;                           /* crc ^=       (byte*0x0001)     */
    CrcVal ^= (unsigned char)(CrcVal&0xff)>>4;  /* crc ^= ((crc&0xf0)*0x1000)>>16 */
    CrcVal ^= (CrcVal<<8)<<4;                   /* crc ^= ((crc&0x0f)*0x1000)     */
    CrcVal ^= ((CrcVal&0xff)<<4)<<1;            /* crc ^= ((crc&0xff)*0x0020)     */
    return CrcVal;                              /*                    0x1021      */
}

uint16_t y_crc(uint16_t CrcVal, uint8_t DataIn) {
    CrcVal ^= ((uint16_t)DataIn) << 8;
    for (uint16_t i = 0; i < 8; i++)
        CrcVal = (CrcVal&0x8000)?(CrcVal<<1)^0x1021:(CrcVal << 1);
    return CrcVal;
}

void inittbl()
{
    for (uint16_t j = 0; j < 256; j++)
        crctbl[j] = x_crc(0, (uint8_t)j);
}

uint16_t z_crc(uint16_t CrcVal, uint8_t DataIn) {
    CrcVal = crctbl[(CrcVal>>8)^DataIn]^(CrcVal<<8);
    return CrcVal;
}

int main()
{
uint16_t crcx = 0;
uint16_t crcy = 0;
uint16_t crcz = 0;
uint8_t x[]={1,2,3,4,5,6,7,8,9,0};
    inittbl();
    for(size_t i = 0; i<10; i++)
        crcx = x_crc(crcx, *(x + i));
    for(size_t i = 0; i<10; i++)
        crcy = y_crc(crcy, *(x + i));
    for(size_t i = 0; i<10; i++)
        crcz = z_crc(crcz, *(x + i));
    if (crcx == crcy && crcx == crcz)
        printf("match\n");
    return 0;
}

从现有的 crc 函数生成 crc16 查找 table

Generate crc16 lookup table from existing crc function

c

checksum

crc

crc16