wxleasyland@139.com
2022.7
以前写过《我学习CRC32、CRC16、CRC原理和算法的总结（与WINRAR结果一致）》长篇。经过十几年又忘记了。
这次碰到DS18B20进行CRC校验（以前都没校的），重新温了一下，补充了一下。
DS18B20是反着算的，有点难理解，所以花了点时间。
为什么反着算，如何做正算等效，这是重点。
DS18B20的CRC有很多人已经写过了，就不列举了。
这里把正算、反算CRC原理详细说明一下，算是原来文章的补充。精华都在这里了。
=========================================
【
】
【通用简单的 按比特位 传统直接计算程序：
“计算一串字节流的8位CRC”，POLY是单片机中常见的X8+X5+X4+1（比如HTU31D湿度传感器）：
再次强调一下，不要把扩展的0和数据中的0搞混：
输入数据流68 3A，则扩展00后是68 3A 00，算出CRC是7C。
输入数据流68 3A，则扩展CRC后是68 3A 7A，算出CRC是00，即校验成功。
输入数据流68 3A 00，则扩展00后是68 3A 00 00，算出CRC是85H ！
即数据流68 3A和68 3A 00，CRC值是不一样的！
unsigned char CRC1_add0(unsigned char *addr, unsigned char len)
//计算8位CRC，输入是一串字节流数据。 按原始计算方式，数据需要扩展CRC位的0（或CRC值）。
//注意：这里的addr[]中已经放好了扩展的一字节0，len长度包含了扩展的0！！ 即原始数据是n字节，则len=n+1！！ 重要！！
//扩展的0也可以是CRC值，这样计算出来CRC值就是0
{
unsigned char crc = 0, inbyte, i;
while (len--)
{
// inbyte 存储当前参与计算的新字节
inbyte = *addr++;
for (i = 8; i; i--)
{
if(crc & 0x80) //如果要移出的高位是1，则要XOR
{
crc<<=1; //移出高位
crc+=( (inbyte & 0x80)>0 ); //移入数据位到CRC寄存器，看移入的数据位是1还是0
crc^=0x31; //POLY生成项
}
else
{
crc<<=1;
crc+=( (inbyte & 0x80)>0 );
}
inbyte<<=1;
}
}
return crc;
}
前面几次移位其实只是把数据移入CRC寄存器，所以可以简化一下：
unsigned char CRC2_add0(unsigned char *addr, unsigned char len)
//计算8位CRC，输入是一串字节流数据。 按原始计算方式，数据需要扩展CRC位的0（或CRC值）。
//注意：这里的addr[]中已经放好了扩展的一字节0，len长度包含了扩展的0！！ 即原始数据是n字节，则len=n+1！！ 重要！！
//扩展的0也可以是CRC值，这样计算出来CRC值就是0
{
unsigned char crc = 0, inbyte, i;
crc = *addr++;
len--;
while (len--)
{
// inbyte 存储当前参与计算的新字节
inbyte = *addr++;
for (i = 8; i; i--)
{
if(crc & 0x80) //如果要移出的高位是1，则要XOR
{
crc<<=1; //移出高位
crc+=( (inbyte & 0x80)>0 ); //移入数据位到CRC寄存器，看移入的数据位是1还是0
crc^=0x31; //POLY生成项
}
else
{
crc<<=1;
crc+=( (inbyte & 0x80)>0 );
}
inbyte<<=1;
}
}
return crc;
}
】
【这里插一个“不扩0直接计算法”：
原始数据后面需要扩展0，太麻烦了，需要有一个不用扩展0的计算法，即变种计算。因为传统的扩0计算方法，前面几次的循环只是把数据移入CRC寄存器中，没有进行真正的计算，又麻烦又浪费。
不扩0 变种直接计算：传统方式变种后快速计算，按位计算，一次计算1位，待测数据不需要加0扩展，数据不移入寄存器，寄存器可直接先放INIT预置值。
方法是：从CRC寄存器移出的MSB“最高位”，与待测数据移出的MSB“最高位”，进行XOR，结果如果为1，则把POLY值XOR到CRC寄存器中；如果为0，则不进行XOR。
算法原理：为什么是这样的原理，想不明白，直接用就好了。
好处：待测数据不需要加0扩展了！比较方便。直接一下就可以出来CRC值！收发电路在硬件上好实现，大家都是这么干的！
硬件CRC电路只有二种：
一种是MSB优先，数据先发送高比特位，即数据从高位移出，则CRC寄存器也一样从高位移出（我叫它“正算”）。 前几章节的程序都是这种类型的。
另一种是LSB优先，数据先发送低比特位，即数据从低位移出，则CRC寄存器也一样从低位移出（我叫它“反着算”）。这个后面再说。
比如 MSB优先的硬件CRC电路（“正算”），很简单：
这里是寄存器bit4移到bit5，移动中做XOR，相当于移完后的bit5做XOR。同理，bit4、bit0做XOR。
所以POLY=X8+X5+X4+X1 （X8是默认有的），即0011 0001，即0x31
比如HTU31D湿度传感器，就是这样子算的。
前面已经有“计算一串字节流的8位CRC”的传统需要扩0的计算程序，这里采用变种算法不扩0直接计算：
unsigned char CRC_noadd0(unsigned char *addr, unsigned char len)
//计算8位CRC，输入是一串字节流数据。 按变种计算方式，数据不需要扩展CRC位的0，可以扩展CRC值。
//注意：这里的addr[]中是原始数据，不需要扩展的一字节0，len长度为原始数据长度！！ 重要！！
//注意：这里的addr[]中可以扩展一字节CRC值，len长度为原始数据长度+1，这样计算出来CRC值就是0。
{
unsigned char crc = 0, inbyte, i;
while (len--)
{
// inbyte 存储当前参与计算的新字节
inbyte = *addr++;
for (i = 8; i; i--)
{
//CRC寄存器移出的高位与待测数据移出的高位相XOR，是1则要把CRC寄存器XOR
if( (crc & 0x80) ^ (inbyte & 0x80) )
{
crc<<=1;
crc^=0x31;
}
else
crc<<=1;
inbyte<<=1;
}
}
return crc;
}
可以看出，算出来结果是完全一样的，比如：
printf("%x %x %x \n", CRC1_add0(test,3), CRC2_add0(test,3) , CRC_noadd0(test,2) );
变种直接计算一次只能计算1位。对应变种直接计算的，就是变种查表了，一次可以计算1字节。
】
【这里插一个“颠倒的变种直接计算法”（反着算）：
用于很多硬件在发送时先发送最低位LSB的情况。等同于CRC参数模型要求REFIN=TRUE并且REFOUT=TRUE。
很多硬件是先发送每字节数据的最低位LSB，那怎么计算CRC？
我们做XOR时，肯定是最高位和最高位、最低位和最低位做XOR。如果最高位和最低位做XOR，那就傻X了，无论程序还是硬件电路，都麻烦。
所以如果数据是LSB最低位先移出，那肯定是和CRC寄存器的最低位做XOR，做完就移走了。
和前面正算的MSB最高位移出是正好相反的。
其它就一样了，如果XOR出来是1，那就拿POLY去XOR，是0则不做XOR。最后寄存器里就是CRC值。
这就是“反着算”（“颠倒的变种直接计算法”）。
可以看出来，“反着算”的结果肯定和正算不一样。那二者能否等效呢？
可以！CRC参数模型是针对正算的，在REFIN=TRUE并且REFOUT=TRUE时，二者等效。
同时，POLY要做颠倒镜像才行，即此POLY非彼POLY。
这就是“REFIN=TRUE并且REFOUT=TRUE”的由来！正是因为硬件是反着干的，所以就有了这个CRC参数模型！
比如在DS18B20温度传感器里，有说明“等效POLY”是X8+X5+X4+X1，实现电路却是：
这张图是不是就像前面那张图的照镜子的镜像版？
等效POLY=X8+X5+X4+X1，即0011 0001，即0x31
本图上是bit3、bit2、bit7进行XOR，所以：POLY=X8+X7+X3+X2，即1000 1100，即0x8C
实际POLY 0x8C就是“等效POLY 0x31”颠倒后的反过来值！
方法是：原始数据每字节从最低位LSB移出，CRC寄存器从LSB最低位移出，等效POLY值做个颠倒。从CRC寄存器移出的“位”，与待测数据移出的“位”，进行XOR，结果如果为1，则把POLY值XOR到CRC寄存器中；如果为0，则不进行XOR。
实现程序是：
unsigned char DS18B20_CRC1(unsigned char *addr, unsigned char len)
//计算8位CRC，输入是一串字节流数据。 数据不需要扩展CRC位的0。
//注意：这里的addr[]中是原始数据，不需要扩展的一字节0，len长度为原始数据长度！！ 重要！！
{
unsigned char crc = 0, inbyte, i, mix;
while (len--)
{
// inbyte 存储当前参与计算的新字节
inbyte = *addr++;
for (i = 8; i; i--)
{
mix = (crc ^ inbyte) & 0x01; // CRC寄存器最低位 与 数据的最低位 进行XOR（高位都是忽略的），看结果是1还是0，如果是1，则需要用POLY对CRC寄存器进行XOR
crc >>= 1; //高位移入的是0
if (mix)
{
crc ^= 0x8C; //颠倒后的POLY
}
inbyte >>= 1;
}
}
return crc;
}
这样算出来的CRC是正确的。
但是，如果采用以前的程序CRC_noadd0()、“POLY 0x31”来正着算，得到的结果是不一样的！
为什么？因为等效的条件是：REFIN=TRUE并且REFOUT=TRUE。
也就是说，如果你想要正着算，就需要进行REFIN=TRUE并且REFOUT=TRUE的操作，即：输入数据做镜像，最终CRC寄存器值做镜像。
我们做个颠倒每字节内部比特位的程序：
unsigned char Reflect(unsigned char ref)
{
unsigned char value=0,i;
for( i = 1; i < 9; i++)
{
if(ref & 1) value |= 1 << (8 - i);
ref >>= 1;
}
return value;
}
将输入数据的各个字节Reflect()、CRC_noadd0()采用“POLY 0x31”来正着算、最后将最后的CRC值Reflect()，OK，成功了，得到的结果和DS18B20_CRC1()反着算是一样的。实现了等效！
也就是说：CRC硬件电路都是越简单越好，只有正着算、或者反着算，二种电路。
硬件上MSB优先（比如HTU31D） 就是用 常规正算，REFIN=FALSE、REFOUT=FALSE
硬件上LSB优先（比如DS18B20） 就是用 反着算， 等同于 常规正算、REFIN=TRUE、REFOUT=TRUE[注意POLY的镜像]
INIT值看硬件要求[反着算应也是要镜像的]。
对于反着算的电路，我们电脑上或单片机上可以正着算，也可以反着算。
以上算法的原理：想不明白，直接用。
关于DS18B20网上还引申了查表CRC算法，基本原理应是一样的。
我们电脑上一般还是正着算的，对于REFIN=TRUE并且REFOUT=TRUE的反着算的电路，我们电脑上要先对每字节做颠倒太麻烦了，于是针对这种CRC参数模型引出来后面的“颠倒的直驱表法”，做快速查表计算。
】
