一、引言
因为最近需要用到CRC循环冗余校验码，所以上网查了一些资料，但是找了一圈没有说得比较明白的，不少文章都只说了一部分，看了让人摸不着头脑，在经过一番纸上列式计算后，yellowko算是搞清楚了这里面的道道，所以记录分享一下。
二、基础概念
CRC码是一种校验码，具有一定的纠错能力，但是一般不用来纠错，想了解其纠错的可参考《一种改进的循环冗余校验纠错技术》这篇文章，本文仅讨论CRC的检错。操作就是对数据做模二除法，得到的余数就是CRC校验码，更详细的原理上的内容可以参考这篇文章，或者Wiki的相关页面。
在CRC中有几个参数或者是操作这里得说明一下：
初始值（initial value）：设定的CRC初值，在计算数据流第一个值时预先设定的CRC值，会在最初一次计算中与数据做异或。
位宽（width）:CRC的长度，例如8、16、32，比较特殊的1位其实也就是奇偶校验码
生成多项式（generator polynomial）：用于产生CRC校验码的多项式，需要满足一定的特征，以达到一定的检错性能，即使是相同位宽也有性能不分上下的多种，根据需要挑选现成的即可。例如X16+ X15+X2+1。生成多项式通常使用简化的记法，由于最高位都固定为1，所以省略掉，因此前面这个式子就可以用十六进制记为0x8005。
输入输出数据反转（refin、refout）：这个反转是倒序的意思，有一些协议要求对数据逆序计算，也就是0x01变为0x80来算，算出CRC值后再倒过来进行校验。为什么会有这种奇怪的要求呢，或许是为了编程方便，详细的后面会讲解。
异或输出（xorout）：计算完成后再与其进行异或得出最终的结果，大多数情况下为0x00。
三、过程分析
举个例子如果位宽为8，初始值为0x00，生成多项式为0x9B（那么除数为0x19B），不进行输入输出的反转，也不进行异或输出，输入值（被除数）为0x80，那么计算过程如下
正向计算和反向计算的示例
绿色是补的0，数量为位宽，这里是8个，蓝色的是被除数相对除数在左移，遇到1时需要做异或运算，本来应该是9位一起运算，但是由于最高位运算一定为0，所以实际上除数的最高位可以不参与运算，在编程时就可以忽略掉，遇到1也左移。所以最后红色的结果就是0x0B(00001011)。如果要做反转的操作呢，上面的式子就相当于0x01做了输入反转的计算，一般输入输出反转都是同时的，如果输出也需要反转，那结果就是0x0B的反转即0xD0(11010000)，就像上面右图演示的。如果要有初始值怎么样，前面的式子就等效于输入时0x7F(01111111),初始值是0xFF(11111111)，其余不变。这两个变式都可以在这个在线计算CRC的网站计算出来，选择hex输入输出，计算CRC-8就可以在下面的结果中找到。
四、编程实现
要实现CRC的计算，大方向有两种，一种是计算法，一种是查表法。计算CRC时一般一次计算一个字节，计算得到的结果作为下一次计算的初始值。
1.计算法求CRC值的实现
下面是分别列举了正常计算和输入输出反向的计算方法，两种方法的原理在前面都有。程序是用用Javascript写的，大家可以直接在浏览器里按F12粘贴到控制台里验证，要移植成其他的语言也很简单。
//正向计算
var inputData = [0x80];
function crc_8(data, len) {
var crc = 0x00;
var poly = 0x9B;
var i, j;
for (i = 0; i < len; i++) {
crc ^= data[i];
console.log(crc.toString(2).padStart(8, '0') + ('0').repeat(8));
for (j = 0; j < 8; j++) {
if ((crc & 0x80) != 0) {
crc <<= 1;
crc &= 0xFF; //限制住数据长度为8bit
console.log((' ').repeat(j + 1) + crc.toString(2).padStart(8, '0'));
console.log((' ').repeat(j + 1) + poly.toString(2).padStart(8, '0'));
crc ^= poly;
console.log('---------------');
console.log((' ').repeat(j + 1) + crc.toString(2).padStart(8, '0'));
}
else {
crc <<= 1;
crc &= 0xFF; //限制住数据长度为8bit
}
}
console.log((' ').repeat(8) + crc.toString(2).padStart(8, '0'));
}
return crc & 0xFF; //限制住数据长度为8bit
}
crc_8(inputData, inputData.length).toString(16).padStart(2, '0');
//反向计算
var inputData = [0x01];
function crc_8(data, len) {
var crc = 0x00;
var poly = 0xD9;
var i, j;
for (i = 0; i < len; i++) {
crc ^= data[i];
console.log(('0').repeat(8) + crc.toString(2).padStart(8, '0'));
for (j = 0; j < 8; j++) {
if ((crc & 0x01) != 0) {
crc >>= 1;
console.log((' ').repeat(7 - j) + crc.toString(2).padStart(8, '0'));
console.log((' ').repeat(7 - j) + poly.toString(2).padStart(8, '0'));
crc ^= poly;
console.log('---------------');
console.log((' ').repeat(7 - j) + crc.toString(2).padStart(8, '0'));
}
else {
crc >>= 1;
}
}
console.log(crc.toString(2).padStart(8, '0'));
}
return crc;
}
crc_8(inputData, inputData.length).toString(16).padStart(2, '0');
可以看出，正向计算直接得出了前面举例的其实长除法式子，而输入输出的反转就是把式子做镜像翻转，但是反转计算直接右移即可，不用考虑移出去的数据还会有影响，而像Javascript这类语言，并没有办法卡死数据长度为8bit，在正向计算左移时高位不会被移出去，在最终输出时高位会有一定影响，需要丢弃掉。所以例如Modbus协议就会要求倒序输入倒序输出，也就是后一种方法。这在很多文章里都没说清楚，都是说一个正序的原理就开始贴倒序的代码，让人看不明白。
2.查表法求CRC值的实现
查表法就是把一个字节一共256种情况所对应的256种CRC码对应起来，要用时直接查询即可。
//查表法计算CRC
var inputData = [0x80];
var crcTable = [
0x00, 0x9b, 0xad, 0x36, 0xc1, 0x5a, 0x6c, 0xf7, 0x19, 0x82, 0xb4, 0x2f, 0xd8, 0x43, 0x75, 0xee,
0x32, 0xa9, 0x9f, 0x04, 0xf3, 0x68, 0x5e, 0xc5, 0x2b, 0xb0, 0x86, 0x1d, 0xea, 0x71, 0x47, 0xdc,
0x64, 0xff, 0xc9, 0x52, 0xa5, 0x3e, 0x08, 0x93, 0x7d, 0xe6, 0xd0, 0x4b, 0xbc, 0x27, 0x11, 0x8a,
0x56, 0xcd, 0xfb, 0x60, 0x97, 0x0c, 0x3a, 0xa1, 0x4f, 0xd4, 0xe2, 0x79, 0x8e, 0x15, 0x23, 0xb8,
0xc8, 0x53, 0x65, 0xfe, 0x09, 0x92, 0xa4, 0x3f, 0xd1, 0x4a, 0x7c, 0xe7, 0x10, 0x8b, 0xbd, 0x26,
0xfa, 0x61, 0x57, 0xcc, 0x3b, 0xa0, 0x96, 0x0d, 0xe3, 0x78, 0x4e, 0xd5, 0x22, 0xb9, 0x8f, 0x14,
0xac, 0x37, 0x01, 0x9a, 0x6d, 0xf6, 0xc0, 0x5b, 0xb5, 0x2e, 0x18, 0x83, 0x74, 0xef, 0xd9, 0x42,
0x9e, 0x05, 0x33, 0xa8, 0x5f, 0xc4, 0xf2, 0x69, 0x87, 0x1c, 0x2a, 0xb1, 0x46, 0xdd, 0xeb, 0x70,
0x0b, 0x90, 0xa6, 0x3d, 0xca, 0x51, 0x67, 0xfc, 0x12, 0x89, 0xbf, 0x24, 0xd3, 0x48, 0x7e, 0xe5,
0x39, 0xa2, 0x94, 0x0f, 0xf8, 0x63, 0x55, 0xce, 0x20, 0xbb, 0x8d, 0x16, 0xe1, 0x7a, 0x4c, 0xd7,
0x6f, 0xf4, 0xc2, 0x59, 0xae, 0x35, 0x03, 0x98, 0x76, 0xed, 0xdb, 0x40, 0xb7, 0x2c, 0x1a, 0x81,
0x5d, 0xc6, 0xf0, 0x6b, 0x9c, 0x07, 0x31, 0xaa, 0x44, 0xdf, 0xe9, 0x72, 0x85, 0x1e, 0x28, 0xb3,
0xc3, 0x58, 0x6e, 0xf5, 0x02, 0x99, 0xaf, 0x34, 0xda, 0x41, 0x77, 0xec, 0x1b, 0x80, 0xb6, 0x2d,
0xf1, 0x6a, 0x5c, 0xc7, 0x30, 0xab, 0x9d, 0x06, 0xe8, 0x73, 0x45, 0xde, 0x29, 0xb2, 0x84, 0x1f,
0xa7, 0x3c, 0x0a, 0x91, 0x66, 0xfd, 0xcb, 0x50, 0xbe, 0x25, 0x13, 0x88, 0x7f, 0xe4, 0xd2, 0x49,
0x95, 0x0e, 0x38, 0xa3, 0x54, 0xcf, 0xf9, 0x62, 0x8c, 0x17, 0x21, 0xba, 0x4d, 0xd6, 0xe0, 0x7b
];
function crc_8(data, len) {
var crc = 0x00; //crc初值
for (var i = 0; i < len; i++) {
crc = crcTable[crc ^ data[i]];
}
return crc;
}
crc_8(inputData, inputData.length).toString(16).padStart(2, '0');
这个表的生成也不麻烦，稍微修改一下前面计算法的程序即可
//crc表的生成
function crcTableGen_8(data) {
var crc = data; //注意这里的crc寄存器是没有初值的
var poly = 0x9B;
var i, j;
for (j = 0; j < 8; j++) {
if ((crc & 0x80) != 0) {
crc <<= 1;
crc &= 0xFF; //限制住数据长度为8bit
crc ^= poly;
}
else {
crc <<= 1;
crc &= 0xFF; //限制住数据长度为8bit
}
}
return crc & 0xFF; //限制住数据长度为8bit
}
var str = '';
for (var i = 0; i < 16; i++) {
for (var j = 0; j < 16; j++) {
str += '0x' + crcTableGen_8(i * 16 + j).toString(16).padStart(2, '0') + ',';
}
str += '\n';
}
console.log(str);
五、其余的参考链接
CRC（循环冗余校验）在线计算(这个比较卡，经常点了没反应，虽然定制选项很强，但是不如文中链接那个稳定)
本作品由yellowko采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
