假设一个多字节数据块由一些CRC处理两次,一次不变,一次有一个故障字节。故障字节是否可以仅基于两个代码定位?注意,这并不意味着必须仅识别错误的确切性质,而是将字节错误限制为可由任何CRC纠正的单个位翻转。
给定:良好数据的CRC和具有一个坏字节的数据的CRC。假设两个给定的CRC是好的,因此CRC本身内没有错误。 Xor与坏数据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);
}