我的 CRC 出了什么问题？

获取新的 Intel® 物联网开发者套件，这是一个完整的硬件和软件解决方案，使开发者能够使用 Intel® Galileo 和 Intel® Edison 开发板创建激动人心的新解决方案。请访问 Intel® 物联网开发者中心。

看看下面的（非）CRC 实现。它有什么问题？

我正在为物联网设备开发一个连接库。数据完整性检查是每个通信协议中非常重要的一部分。您将一连串字节发送到另一台机器，然后该机器必须知道在传输过程中没有发生错误。例如，IP 已经有一个很好的完整性检查。问题在于 TCP 套接字本质上是一个流。这意味着您并不真正知道缓冲区何时开始和结束。通过使用完整性检查，我们可以验证我们正在查看的是完整的缓冲区。

基本概念是让第一个字节和最后一个字节之间存在某种关联。例如，如果前两个字节是缓冲区的长度，而最后两个字节是 0x0102，那么我们可以继续扫描缓冲区，直到前两个字节指向 0x0102。问题在于，我们选择的任何数字都可能出现在缓冲区内作为数据的一部分。例如，如果我们有 10,000 个 0x0102 字节怎么办？我们会找到 0x0102，假设它是长度，向前跳，然后找到 0x0102。魔术数字可能是最糟糕的方法之一。长度是缓冲区的特征。我们还需要在末尾有一个缓冲区的其他特征。首选方法是使用缓冲区中的所有数据来生成完整性检查值。为此，通常有 Checksum、XOR、CRC 和 Hush。问题是 CPU 和 RAM 的使用量与错误检测的质量相比如何。

Checksum 最初只是所有字节的简单加法（和...）。问题在于 0x80+0x10 和 0x10+0x80 是相同的。这意味着替换一个字节可能会被检测到，但很有可能一个或多个字节会补偿以获得相同的结果。这里有另一个例子：0x10+0x20+0x30 的 checksum 和 0x60+0x00+0x00 一样。这显然是不同的缓冲区。

使用 XOR 非常简单且对 CPU 成本低。问题在于 0x80^0x80 和 0x81^0x81 是相同的。这意味着一个字节的错误可能被检测到，但很可能第二个错误会掩盖第一个错误。只要每个字节的每个位只有一个错误（或者任何位有奇数个错误），XOR 就是安全的。

CRC - 循环冗余校验可能是最佳选择。有一个很好的算法，我将在下面详细介绍。它在 CPU 和 RAM 上的开销更大，但可靠性要高得多。任何错误都会传播以持续产生完全不同的数字。一个错误很难被另一个错误补偿。如果您将 0x10 替换为 0x12，那么不仅仅是一个数字需要改变到特定位置才能进行补偿。CRC16 表示 16 位数字，CRC 32 表示 32 位数字。这意味着 CRC16 有 1/64K 的概率缓冲区是正确的。如果一个字节发生变化导致生成了不同的 CRC16，那么需要几个不同的字节来补偿它，因为一个字节无法修复一个 16 位值。

高级 Hush 函数通常会消耗过多的 RAM 和 CPU，但最终输出的数字才是最重要的。如果您有一个 16 位的完整性值，那么即使是最好的算法也无法将您从 1:64K 的比例中拯救出来。

我搜索了“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++)];
}

我试图找到一个可以在 Arduino 设备上使用的东西，既不浪费 CPU 也不占用设备大量内存。这是我找到的（从 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 都具有均匀的分布值，因此原始缓冲区中的每种字节组合在 64K 的限制内都有一个唯一的数字。例如，如果您在我的测试函数中注释掉“myCrc = (ushort)((myCrc) ^ (myCrc << 5) ^ (myCrc << 8));”这一行（仅使用 XOR），您会看到一些结果被重复覆盖，而许多值根本没有被使用（为零）。

如果这样的实现是好的，那么它显然适合 AVX 向量化，而不是使用 for 循环或查找表。

我愿意接受任何建议或想法。