时间戳

首页 > 解决方案 > CRC：定位错误字节

embedded - CRC：定位错误字节

问题描述

假设一个多字节数据块被某个 CRC 处理了两次，一次是不变的，一次是一个错误的字节。能否仅根据这两个代码定位故障字节？请注意，这并不意味着错误的确切性质必须仅识别其位置，字节错误也不限于可由任何 CRC 纠正的单个位翻转。

标签： embeddedcrcredundancyerror-correctionerror-detection

解决方案

给定：正确数据的 CRC 和带有一个坏字节的数据的 CRC。假定两个给定的 CRC 是好的，因此 CRC 本身没有错误。将好数据 CRC 与坏数据 CRC 异或。将此视为将好数据 + 好 CRC 与坏数据 + 坏 CRC 进行异或运算，结果是除了一个坏字节和相应的 CRC 之外全为零的数据。xor 还会抵消任何初始 CRC 值或 CRC 值的后补。

为了能够检测坏字节的位置，对于字节位置和字节值的每个可能组合，CRC 需要是唯一的。

我发现 CRC32C 多项式 0x1edc6f41 为 1 到 190235 字节的数据生成唯一的 CRC。它在 190236 字节的数据处失败，因为除了 bfr[0] = 0xfb 或 bfr[190235] = 0x32 之外的全零缓冲区都产生相同的（非唯一）CRC = 0x364b1c30 。

给定一个好的 crc 和一个坏的 crc（一个坏字节）来确定位置的示例代码：

static uint32_t crcrtbl[256];

void genrtbl(void)
{
uint32_t crc;
uint32_t b;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c;
        for(i = 0; i < 8; i++){
            b = crc&1;
            crc >>= 1;
            crc ^= (0 - b) & (0x11edc6f41>>1);
        }
        crcrtbl[c] = crc;
    }
}

size_t crc32r(uint32_t crc, size_t size)
{
    while(size--){
        crc = (crc >> 8) ^ crcrtbl[crc & 0xff];
        if(0 == (crc & 0xffffff))
            break;
    }
    return(size);
}
// ...
genrtbl();  // generate table
// given good_crc and bad_crc, return location
location = crc32r(good_crc ^ bad_crc, size);

生成crc的代码

uint32_t crctbl[256];

void gentbl(void)
{
uint32_t crc;
uint32_t b;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++){
            b = crc>>31;
            crc <<= 1;
            crc ^= (0 - b) & 0x1edc6f41;   // 32 bit crc
        }
        crctbl[c] = crc;
    }
}

uint32_t crc32(uint32_t crc32, uint8_t * bfr, size_t size)
{
uint32_t crc = crc32;
    while(size--)
        crc = (crc << 8) ^ crctbl[(crc >> 24)^*bfr++];
    return(crc);
}

推荐阅读