CRC 出现什么问题?

检查以下(非) CRC 实施。 它有什么问题?

我正在处理面向物联网设备的连接库。 各通信协议的重要部分是数据完整性检查。 您向其他机器发送字节,该机器需要了解这些字节在传输过程中是否完好无损。 例如,IP 就是一次很好的完整性检查。 问题是,TCP 插槽基本上就是一个数据流。 这意味着,您不知道缓冲何时开始,何时结束。 通过完整性检查,我们可以验证,是否能看到全部缓冲区。

基本的概念是在第一个字节和最后一个字节之间进行一些纠正。 例如,如果前 2 个字节是缓冲区的长度,最后 2 个字节是 0x0102,那么我们可以一直扫描该缓冲区,直到前两个字节指向 0x0102。 问题是,我们选择的每个数都可能作为数据的一部分出现在缓冲区中。 例如,如果 0x0102 的字节数为 10,000,我们该怎么办? 我们将要查找 0x0102,假设这是它的长度,跳到前面并找到 0x0102。 幻数可能是最糟糕的方法之一。 长度是缓冲区的一个特征。 我们需要末端也有缓冲区的另一个特征。 首选方法是使用缓冲区的全部数据生成完整性校验值。 常用的有校验和、XOR、CRC 和 Hush。 问题是,CPU 和 RAM 的占用量对比错误检测质量。

校验和最初是全部字节的总和(和...)。 问题是,0x80+0x10 与 0x10+0x80 的校验和完全相同。 这意味着,替换一个字节可能会检测到,但还很有可能存在一个或多个字节加以弥补,以获得相同结果的情况。 再举一个例子: 0x10+0x20+0x30 与 0x60+0x00+0x00 的校验和相同。 显然是一个完全不同的缓冲区。

使用 XOR 不仅简单,而且 CPU 成本低。 问题是,0x80^0x80 与 0x81^0x81 完全相同。 这意味着,也许能检测到缓冲区的一个错误,但第一个错误之后很可能还隐藏第二个错误。 只要全部字节的每一位中只有一个错误(或任意位中的错误为奇数位),XOR 就是安全的。

CRC - 循环冗余校验也许是最好的方法。 其中包含一种非常好用的算法,下面来详细了解一下。 尽管它占用大量 CPU 和 RAM,但非常可靠。 每个错误都会传播,以持续生成完全不同的数字。 因此其他错误难以弥补某一个错误。 如果您的是 0x12(而非 0x10),需要更改至特定位置以进行弥补的数不止一个。 CRC16 表示 16 位数,CRC 32 表示 32 位数。 这意味着,CRC16 表示缓冲区正确的几率为 1/64,000。 如果字节更改,生成了不同的 CRC16,将需要数个不同的字节来弥补,因为一个字节无法修复 16 位值。

高级 hush 函数通常占用大量 RAM 和 CPU,但最终的输出值至关重要。如果您有一个 16 位整数值,即使是最佳的算法,也无法帮您摆脱 1 : 64,000 的困境。

我在谷歌上搜索 "crc16 algorithm c",找到了几个结果。 下列网址第一个介绍这一概念: http://www.nongnu.org/avr-libc/user-manual/group__util__crc.html

uint16_t crc16_update(uint16_t crc, uint8_t a)
{
   int i;
   crc ^= a;
   for (i = 0; i < 8; ++i)
   {
      if (crc & 1) crc = (crc >> 1) ^ 0xA001;
      else crc = (crc >> 1);
   }
   return crc;
}

该示例很好,因为它展示了一些循环。 针对每一个位移的位,我们根据指定的位值选择是否通过幻数进行 xor。 该循环消耗 CPU,因此我们实际上为查询表中的每个特定字节准备了结果: http://stackoverflow.com/questions/22432066/how-to-use-table-based-crc-16-code

unsigned int crctable[256] =
{
   0x0000, 0x1189 ........
};

while (len--)
{
   crc = (crc << 8) ^ crctable[((crc >> 8) ^ *c++)];
}

我试着寻找可以在不浪费 CPU 资源也不占用大量内存的情况下,用于 Arduino 设备的东西。 以下就是我的收获(未经编译,从 C# 转换而来,下面我会介绍原因)

myCrc ^= *buffer++;
myCrc = (myCrc) ^ (myCrc << 5) ^ (myCrc << 8);

我怎么不知道这种实施,谷歌搜索结果一开始也没有出现这种实施。 这里我错过了什么?

我之所以使用 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));
            //myCrc ^= *buffer++;
            //myCrc = (myCrc) ^ (myCrc << 5) ^ (myCrc << 8);

            pos++;
         }
         return (crc);
      }

测试员代码如下:

      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<int>   crcUtilization = new List<int>();
         List<int> myCrcUtilization = new List<int>();
         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]);
         }
// BREAKPOINT HERE and check out crcUtilization and myCrcUtilization (or print)
      }

      private static void CRCTest(byte[] buffer)
      {
         ushort crc16 = 0;
         ushort myCrc = 0;
         CRC16(buffer, out crc16, out myCrc);
      }

测试显示,myCrc 和 crc16 拥有相等的散列值,所以原始缓冲区中的字节的每次合并在 65,000 范围内都有一个独特的数。 例如,如果取消行 "myCrc = (ushort)((myCrc) ^ (myCrc << 5) ^ (myCrc << 8))" 的注释,测试函数 (only XOR) 中间显示少量重复覆盖的结果,以及大量根本没有用过的值(零)。

与使用循环或查询表不同,如果这种实施有用,那么显然也适用于 AVX 矢量化。

随时欢迎大家提出任何建议和想法。

有关编译器优化的更完整信息,请参阅优化通知