CRC4 在 C 中的实现

Question

我修改了发现的实现 here ，为 CRC4 构建表生成函数，如下所示:

#define bufferSize 16
crc crcTable[bufferSize];
#define POLYNOMIAL 0x13

void Init()
{
    crc remainder;

     for(int dividend = 0; dividend < bufferSize; ++dividend)
     {
          remainder = dividend;
          for(uint8_t bit = 8; bit > 0; --bit)
          {
              if(remainder & 1)
                  remainder = (remainder >> 1) ^ POLYNOMIAL;
              else
                  remainder = (remainder >> 1);
          }

          crcTable[dividend] = remainder;
          printf("%hu\n", remainder);
    }
}

然后计算 CRC，如下所示:

uint8_t calc_crc4(uint8_t start_crc, uint8_t byte)
{
    byte ^= start_crc;
    start_crc = crcTable[byte] ^ (start_crc >> 8);

    return start_crc;
}

生成的 crcTable 为:

/*
* Table based on Polynomial 0x13
*/
uint8_t crcTable[tableSize] = {
    0x00, 0x0E, 0x1C, 0x12,
    0x1F, 0x11, 0x03, 0x0D,
    0x19, 0x17, 0x05, 0x0B,
    0x06, 0x08, 0x1A, 0x14
};

问题是，当我针对 ERF 文件运行它时，生成的 CRC 值都不等于附加到 ERF 帧末尾的值。当我打印值时，看起来 calc_crc4 函数中对 crcTable[byte] 的调用几乎总是返回值 0x00，但我没有很好地理解这个概念足以知道这是否是正确的值。我唯一能想到的是它在字节的索引位置没有找到任何东西，所以它返回0x00。我假设 CRC4 只能有 16 个值，因此该位置必须有一些东西。

Answer 1

您没有所需 CRC 的完整定义，并且您尝试将实现推断为四位有很多错误。

首先，您需要了解的不仅仅是多项式。您需要知道 CRC 是否被反射(reflect)，输出是否也被反射(reflect)，初始寄存器值是多少，以及输出是否与某个值进行异或。

其次，如果一次处理一个字节，则无论 CRC 的长度如何，该表都需要有 256 个条目。此外，每个条目必须是 CRC 的长度，在本例中为 4 位，而条目的长度为 5 位。此外，您还需要将 CRC 放在字节的正确末尾，以便在表查找之前进行初始异或操作，或者移动表。如前所述，向下移动八位的八位值为零，因此与之进行异或运算不会产生任何效果。

四位 CRC 的表驱动实现类似于其中之一，具体取决于反射。

static unsigned char const table_byte[256] = {
    0x90, 0xa0, 0xf0, 0xc0, 0x50, 0x60, 0x30, 0x00, 0x20, 0x10, 0x40, 0x70, 0xe0,
    0xd0, 0x80, 0xb0, 0xc0, 0xf0, 0xa0, 0x90, 0x00, 0x30, 0x60, 0x50, 0x70, 0x40,
    0x10, 0x20, 0xb0, 0x80, 0xd0, 0xe0, 0x30, 0x00, 0x50, 0x60, 0xf0, 0xc0, 0x90,
    0xa0, 0x80, 0xb0, 0xe0, 0xd0, 0x40, 0x70, 0x20, 0x10, 0x60, 0x50, 0x00, 0x30,
    0xa0, 0x90, 0xc0, 0xf0, 0xd0, 0xe0, 0xb0, 0x80, 0x10, 0x20, 0x70, 0x40, 0xe0,
    0xd0, 0x80, 0xb0, 0x20, 0x10, 0x40, 0x70, 0x50, 0x60, 0x30, 0x00, 0x90, 0xa0,
    0xf0, 0xc0, 0xb0, 0x80, 0xd0, 0xe0, 0x70, 0x40, 0x10, 0x20, 0x00, 0x30, 0x60,
    0x50, 0xc0, 0xf0, 0xa0, 0x90, 0x40, 0x70, 0x20, 0x10, 0x80, 0xb0, 0xe0, 0xd0,
    0xf0, 0xc0, 0x90, 0xa0, 0x30, 0x00, 0x50, 0x60, 0x10, 0x20, 0x70, 0x40, 0xd0,
    0xe0, 0xb0, 0x80, 0xa0, 0x90, 0xc0, 0xf0, 0x60, 0x50, 0x00, 0x30, 0x70, 0x40,
    0x10, 0x20, 0xb0, 0x80, 0xd0, 0xe0, 0xc0, 0xf0, 0xa0, 0x90, 0x00, 0x30, 0x60,
    0x50, 0x20, 0x10, 0x40, 0x70, 0xe0, 0xd0, 0x80, 0xb0, 0x90, 0xa0, 0xf0, 0xc0,
    0x50, 0x60, 0x30, 0x00, 0xd0, 0xe0, 0xb0, 0x80, 0x10, 0x20, 0x70, 0x40, 0x60,
    0x50, 0x00, 0x30, 0xa0, 0x90, 0xc0, 0xf0, 0x80, 0xb0, 0xe0, 0xd0, 0x40, 0x70,
    0x20, 0x10, 0x30, 0x00, 0x50, 0x60, 0xf0, 0xc0, 0x90, 0xa0, 0x00, 0x30, 0x60,
    0x50, 0xc0, 0xf0, 0xa0, 0x90, 0xb0, 0x80, 0xd0, 0xe0, 0x70, 0x40, 0x10, 0x20,
    0x50, 0x60, 0x30, 0x00, 0x90, 0xa0, 0xf0, 0xc0, 0xe0, 0xd0, 0x80, 0xb0, 0x20,
    0x10, 0x40, 0x70, 0xa0, 0x90, 0xc0, 0xf0, 0x60, 0x50, 0x00, 0x30, 0x10, 0x20,
    0x70, 0x40, 0xd0, 0xe0, 0xb0, 0x80, 0xf0, 0xc0, 0x90, 0xa0, 0x30, 0x00, 0x50,
    0x60, 0x40, 0x70, 0x20, 0x10, 0x80, 0xb0, 0xe0, 0xd0};

unsigned crc4interlaken_byte(unsigned crc, void const *mem, size_t len) {
    unsigned char const *data = mem;
    if (data == NULL)
        return 0;
    crc &= 0xf;
    crc <<= 4;
    while (len--)
        crc = table_byte[crc ^ *data++];
    crc >>= 4;
    return crc;
}

或

static unsigned char const table_byte[256] = {
    0x0, 0x7, 0xe, 0x9, 0x5, 0x2, 0xb, 0xc, 0xa, 0xd, 0x4, 0x3, 0xf, 0x8, 0x1, 0x6,
    0xd, 0xa, 0x3, 0x4, 0x8, 0xf, 0x6, 0x1, 0x7, 0x0, 0x9, 0xe, 0x2, 0x5, 0xc, 0xb,
    0x3, 0x4, 0xd, 0xa, 0x6, 0x1, 0x8, 0xf, 0x9, 0xe, 0x7, 0x0, 0xc, 0xb, 0x2, 0x5,
    0xe, 0x9, 0x0, 0x7, 0xb, 0xc, 0x5, 0x2, 0x4, 0x3, 0xa, 0xd, 0x1, 0x6, 0xf, 0x8,
    0x6, 0x1, 0x8, 0xf, 0x3, 0x4, 0xd, 0xa, 0xc, 0xb, 0x2, 0x5, 0x9, 0xe, 0x7, 0x0,
    0xb, 0xc, 0x5, 0x2, 0xe, 0x9, 0x0, 0x7, 0x1, 0x6, 0xf, 0x8, 0x4, 0x3, 0xa, 0xd,
    0x5, 0x2, 0xb, 0xc, 0x0, 0x7, 0xe, 0x9, 0xf, 0x8, 0x1, 0x6, 0xa, 0xd, 0x4, 0x3,
    0x8, 0xf, 0x6, 0x1, 0xd, 0xa, 0x3, 0x4, 0x2, 0x5, 0xc, 0xb, 0x7, 0x0, 0x9, 0xe,
    0xc, 0xb, 0x2, 0x5, 0x9, 0xe, 0x7, 0x0, 0x6, 0x1, 0x8, 0xf, 0x3, 0x4, 0xd, 0xa,
    0x1, 0x6, 0xf, 0x8, 0x4, 0x3, 0xa, 0xd, 0xb, 0xc, 0x5, 0x2, 0xe, 0x9, 0x0, 0x7,
    0xf, 0x8, 0x1, 0x6, 0xa, 0xd, 0x4, 0x3, 0x5, 0x2, 0xb, 0xc, 0x0, 0x7, 0xe, 0x9,
    0x2, 0x5, 0xc, 0xb, 0x7, 0x0, 0x9, 0xe, 0x8, 0xf, 0x6, 0x1, 0xd, 0xa, 0x3, 0x4,
    0xa, 0xd, 0x4, 0x3, 0xf, 0x8, 0x1, 0x6, 0x0, 0x7, 0xe, 0x9, 0x5, 0x2, 0xb, 0xc,
    0x7, 0x0, 0x9, 0xe, 0x2, 0x5, 0xc, 0xb, 0xd, 0xa, 0x3, 0x4, 0x8, 0xf, 0x6, 0x1,
    0x9, 0xe, 0x7, 0x0, 0xc, 0xb, 0x2, 0x5, 0x3, 0x4, 0xd, 0xa, 0x6, 0x1, 0x8, 0xf,
    0x4, 0x3, 0xa, 0xd, 0x1, 0x6, 0xf, 0x8, 0xe, 0x9, 0x0, 0x7, 0xb, 0xc, 0x5, 0x2};

unsigned crc4g_704_byte(unsigned crc, void const *mem, size_t len) {
    unsigned char const *data = mem;
    if (data == NULL)
        return 0;
    crc &= 0xf;
    while (len--)
        crc = table_byte[crc ^ *data++];
    return crc;
}

此代码和表格由 my crcany code 生成。这些函数使用 data 处的 len 字节推进 CRC。当data等于NULL调用时，返回初始CRC(即零字节的CRC)。 CRC 位于返回值的最低有效位中。

这两个 CRC 在 Greg Cook's catalog 中定义。 ，其中两个 4 位 CRC 定义为:

width=4 poly=0x3 init=0xf refin=false refout=false xorout=0xf check=0xb residue=0x2 name="CRC-4/INTERLAKEN"
width=4 poly=0x3 init=0x0 refin=true refout=true xorout=0x0 check=0x7 residue=0x0 name="CRC-4/G-704"