CRC：定位错误字节

Question

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

Answer 1

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

为了能够检测到坏字节的位置，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);
}

CRC：定位错误字节

CRC: Locate Erroneous Byte

embedded

redundancy

crc

error-detection

error-correction