在物联网(IoT)设备的开发过程中,数据的完整性校验是一个至关重要的环节。数据在传输过程中可能会因为各种原因出现错误,如信号干扰、硬件故障等。因此,确保数据在传输过程中的完整性,是保证通信可靠性的关键。本文将探讨几种常见的数据完整性校验方法,并提供一个基于CRC(循环冗余校验)的实现示例。
数据完整性校验是通信协议中的一个重要组成部分。当向另一台机器发送一系列字节数据时,接收方需要能够确认这些数据在传输过程中没有发生错误。例如,IP协议已经内置了良好的完整性校验机制。然而,TCP套接字基本上是一个流,这意味着无法确切知道缓冲区的开始和结束位置。通过使用完整性校验,可以验证正在查看的是完整的缓冲区。
为了确保数据的完整性,需要在数据的开始和结束之间建立某种关联。例如,如果前两个字节是缓冲区的长度,而最后两个字节是0x0102,那么就可以持续扫描缓冲区,直到前两个字节指向0x0102。然而,选择的任何数字都可能出现在缓冲区中作为数据的一部分。例如,如果有10,000字节的0x0102,会找到0x0102,假设它是长度,然后向前跳转并找到0x0102。显然,使用“魔术数字”可能是最糟糕的方法之一。长度是缓冲区的一个特征,需要在缓冲区的末尾也有另一个特征。首选的方法是使用缓冲区中的所有数据来生成一个完整性校验值。常见的方法有校验和(Checksum)、异或(XOR)、循环冗余校验(CRC)和哈希函数(Hush)。问题在于CPU和RAM的使用量与错误检测的质量之间的权衡。
校验和最初是通过对所有字节进行简单加法运算得到的(求和...)。问题是0x80+0x10与0x10+0x80的结果相同。这意味着,替换一个字节可能会被检测到,但是有很高的概率,一个字节或多个字节可能会补偿以得到相同的结果。这里有一个例子:0x10+0x20+0x30的校验和与0x60+0x00+0x00的校验和相同。显然,这是一个不同的缓冲区。
使用XOR非常简单,对CPU的开销很小。问题是0x80^0x80与0x81^0x81的结果相同。这意味着,缓冲区中的一个错误可能会被检测到,但是有很高的概率,第二个错误会掩盖第一个错误。只要每个字节的所有位(或任何奇数个错误)中只有一个错误,XOR就是安全的。
循环冗余校验可能是最佳选择。有一个不错的算法,将在下面详细说明。它在CPU和RAM上的开销更大,但更加可靠。任何错误都会不断产生完全不同的数字。用另一个错误来补偿一个错误是非常困难的。例如,如果有0x12而不是0x10,那么不仅仅是一个数字需要改变到一个特定位置来补偿。CRC16意味着16位数字,CRC32意味着32位数字。这意味着CRC16有1/64K的概率缓冲区是正确的。如果一个字节改变了,导致产生了不同的CRC16,那么需要几个不同的字节来补偿,因为一个字节无法修复16位的值。
高级哈希函数通常消耗太多的RAM和CPU,但最终输出的数字是最重要的。如果有一个16位的完整性值,那么即使是最好的算法也无法让摆脱1:64K的比例。
在寻找一种可以在Arduino设备上使用的方法,既不会浪费CPU,也不会占用大量设备的内存。以下是得到的实现(从C#翻译而来,未编译,将解释原因):
C++
myCrc ^= *buffer++;
myCrc = (myCrc) ^ (myCrc << 5) ^ (myCrc << 8);
怎么可能不知道这样的实现,而且它没有出现在谷歌搜索的第一条结果中。错过了什么?
使用C#的原因是为了测试(因为这是想要测试这个解决方案时打开的项目)。
C#
private static ushort CRC16(byte[] buffer, out ushort crc, out ushort myCrc)
{
myCrc = 0;
crc = 0;
int pos = 0;
while (pos < buffer.Length)
{
crc ^= (ushort)(buffer[pos] << 8);
for (int i = 0; i < 8; ++i)
{
if ((crc & 0x8000) != 0) crc = (ushort)((crc << 1) ^ 0x1021);
else crc = (ushort)(crc << 1);
}
myCrc ^= (ushort)(buffer[pos]);
myCrc = (ushort)((myCrc) ^ (myCrc << 5) ^ (myCrc << 8));
pos++;
}
return (crc);
}
测试代码:
C#
private static void BenchmarkCRC16()
{
ushort[] crcTable = new ushort[0x10000];
ushort[] myCrcTable = new ushort[0x10000];
for (int a = 0; a < 0x17000; a += 13)
{
if (0 == (a % 256)) Console.WriteLine("a = 0x" + a.ToString("X"));
ushort ua = (ushort)a;
for (int i = 0; i < 0x10000; i++)
{
ushort u = (ushort)i;
ushort crc16 = 0;
ushort myCrc = 0;
CRC16(new byte[] { (byte)(u & 0xFF), (byte)((u >> 8) & 0xFF), (byte)(ua & 0xFF), (byte)((ua >> 8) & 0xFF) }, out crc16, out myCrc);
crcTable[crc16]++;
myCrcTable[myCrc]++;
}
}
List crcUtilization = new List();
List myCrcUtilization = new List();
for (int i = 0; i < 0x10000; i++)
{
bool ok = false;
for (int t = 0; t < crcUtilization.Count; t++)
{
if (crcUtilization[t] == crcTable[i]) { ok = true; break; }
}
if (!ok) crcUtilization.Add(crcTable[i]);
ok = false;
for (int t = 0; t < myCrcUtilization.Count; t++)
{
if (myCrcUtilization[t] == myCrcTable[i]) { ok = true; break; }
}
if (!ok) myCrcUtilization.Add(myCrcTable[i]);
}
}