转载

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 矢量化。

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

原文 https://software.intel.com/zh-cn/blogs/2015/09/02/whats-wrong-with-my-crc

正文到此结束