神刀安全网

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

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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » CRC 出现什么问题?

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮