好贷网好贷款

PCQQ2013 0828涉及到的CRC校验算法[.net

发布时间:2016-12-4 10:00:58 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"PCQQ2013 0828涉及到的CRC校验算法[.net",主要涉及到PCQQ2013 0828涉及到的CRC校验算法[.net方面的内容,对于PCQQ2013 0828涉及到的CRC校验算法[.net感兴趣的同学可以参考一下。

 http://www.10qf.com/thread-4-1-1.html 发表于 2013-9-7 12:23:00 | 只看该作者 |只看大图 |倒序浏览 |阅读模式 PCQQ协议自从2012版本开始较之前有了较大改动,包括接下来我们要用到的crc32算法。如果对算法原理不甚明白,可以参考百度百科里对crc校验的解释。 CRC校验码的编码方法是用待发送的二进制数据t(x)除以生成多项式g(x),将最后的余数作为CRC校验码。其实现步骤如下: 设待发送的数据块是m位的二进制多项式t(x),生成多项式为r阶的g(x)。在数据块的末尾添加r个0,数据块的长度增加到m+r位,对应的二进制多项式为 。 用生成多项式g(x)去除 ,求得余数为阶数为r-1的二进制多项式y(x)。此二进制多项式y(x)就是t(x)经过生成多项式g(x)编码的CRC校验码。 用 以模2的方式减去y(x),得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。 从CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式t(x)转换成了可以被g(x)除尽的m+r位二进制多项式,所以解码时可以用接受到的数据去除g(x),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时可以看做是由t(x)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。 为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。 设待发送的数据t(x)为12位的二进制数据100100011100;CRC-4的生成多项式为g(x)= ,阶数r为4,即10011。首先在t(x)的末尾添加4个0构成 ,数据块就成了1001000111000000。然后用g(x)去除,不用管商是多少,只需要求得余数y(x)。下表为给出了除法过程。 除数次数 被除数/ g(x)/结果 余数 0 1 001000111000000 100111000000 1 0011 0 000100111000000 1 1 00111000000 1000000 1 0011 0 00001000000 2 1 000000 1100 1 0011 0 001100 从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述: //reg是一个5 bits的寄存器 把reg中的值置0. 把原始的数据后添加r个0. While (数据未处理完) Begin If (reg首位是1) reg = reg XOR 0011. 把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。 End reg的后四位就是我们所要求的余数。 这种算法简单,容易实现,对任意长度生成多项式的G(x)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合了。它一次只能处理一位数据,效率太低。为了提高处理效率,可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理,所以一次处理8位比较合适。 为了对优化后的算法有一种直观的了解,先将上面的算法换个角度理解一下。在上面例子中,可以将编码过程看作如下过程: 由于最后只需要余数,所以我们只看后四位。构造一个四位的寄存器reg,初值为0,数据依次移入reg0(reg的0位),同时reg3的数据移出 reg。有上面的算法可以知道,只有当移出的数据为1时,reg才和g(x)进行XOR运算;移出的数据为0时,reg不与g(x)进行XOR运算,相当与和0000进行XOR运算。就是说,reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit,所以有 种选择。上述算法可以描述如下, //reg是一个4 bits的寄存器 初始化t[]={0011,0000} 把reg中的值置0. 把原始的数据后添加r个0. While (数据未处理完) Begin 把reg中的值左移一位,读入一个新的数据并置于register的0 bit的位置。 reg = reg XOR t[移出的位] End 上面算法是以bit为单位进行处理的,可以将上述算法扩展到8位,即以Byte为单位进行处理,即CRC-32。构造一个四个Byte的寄存器reg,初值为0x00000000,数据依次移入reg0(reg的0字节,以下类似),同时reg3的数据移出reg。用上面的算法类推可知,移出的数据字节决定reg和什么样的数据进行XOR。由于有8个bit,所以有 种选择。上述算法可以描述如下: //reg是一个4 Byte的寄存器 初始化t[]={…}//共有 =256项 把reg中的值置0. 把原始的数据后添加r/8个0字节. While (数据未处理完) Begin 把reg中的值左移一个字节,读入一个新的字节并置于reg的第0个byte的位置。 reg = reg XOR t[移出的字节] End 算法的依据和多项式除法性质有关。如果一个m位的多项式t(x)除以一个r阶的生成多项式g(x), ,将每一位(0=<K<M)提出来,在后面不足R个0后,单独去除G(X),得到的余式位 quote] 以下是c#实现的crc32算法: 本帖隐藏的内容 点击下载完整源码: /// /// 计算或验证各种通信帧校验的工具类 /// public class FrameCheckHelper { private ulong[] Crc32Table; //生成CRC32码表 private void GetCRC32Table() { ulong Crc; Crc32Table = new ulong[256]; int i, j; for (i = 0; i < 256; i++) { Crc = (ulong)i; for (j = 8; j > 0; j--) { if ((Crc & 1) == 1) Crc = (Crc >> 1) ^ 0xEDB88320; else Crc >>= 1; } Crc32Table[i] = Crc; } } //获取字符串的CRC32校验值 public ulong GetCrc32Long(/*string sInputString*/byte[] buffer) { //生成码表 GetCRC32Table(); // byte[] buffer = System.Text.ASCIIEncoding.ASCII.GetBytes(sInputString); ulong value = 0xffffffff; int len = buffer.Length; for (int i = 0; i < len; i++) { value = (value >> 8) ^ Crc32Table[(value & 0xFF) ^ buffer[i]]; } return value ^ 0xffffffff; } public byte[] GetCRCByteArray(byte[] buffer) { byte[] c = Util.LongToByteArray((long)GetCrc32Long(buffer)); System.Array.Reverse(c); return c; } } 复制代码

上一篇:创新工场笔试题----有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,求有多少种组合可以组合成n分钱?
下一篇:亚马逊面试题2(二叉树)

相关文章

相关评论