标签: 半字节查表法

3.2 字节查表法 unsigned char code crc_ta = {   #else    const unsigned short crc_ta = {                    /* CRC余式表 */   #endif        0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,       0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,       0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,       0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,       0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,       0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,       0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,       0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,       0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,       0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,       0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,       0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,       0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,       0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,       0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,       0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,       0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,       0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,       0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,       0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,       0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,       0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,       0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,       0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,       0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,       0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,       0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,       0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,       0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,       0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,       0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,       0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0       };   unsigned short CalCRC16Quick(unsigned char *ptr,  unsigned char len)    {       unsigned short crc;       unsigned char da;          crc=0;       while(len--!=0) {       da=(unsigned char) (crc/256);                       /* 以8位二进制数的形式暂存CRC的高8位 */       crc=8;                                          /* 左移8位，相当于CRC的低8位乘以  */       crc^=crc_ta ;                               /* 高8位和当前字节相加后再查表求CRC ，再加上以前的CRC */       ptr++;       }       return(crc);   }   #endif   注: 未经我们验证. 3.3 半字节查表法 从网络资料中我们理解到这样的结论: 该方法速度强于基本运算法, 对code空间的要求, 低于字节查表法(512bytes array). unsigned short CalCRC16(unsigned char *ptr,  unsigned char len)   {       unsigned short crc;       unsigned char da;       unsigned short crc_ta ={   0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,    0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef       };     crc = 0;       while(len--!=0)        {           da = ((unsigned char)(crc/256))/16;                  crc=4;                                             crc^=crc_ta ;                           da = ((unsigned char)(crc/256))/16;                  crc=4;                                             crc^=crc_ta ;                         ptr++;       }       return(crc);   }  注: 该函数, 经过了我们对1字节(0x00, 0x01, 0x0f)的CRC结果的验证, 它们的结果分别是: 0x0000, 0x1021, 0xf1ef. 4. 结论: 当我们不得不引入 CRC 计算时, 半字节查表法在微处理器有限的资源下, 看起来是最适合的算法模式. 同时我们也对文中 16 bit 的 0x1021 CRC 码的半字节查表法的例程, 做了1字节的简单结果验证. Allen 通宵工作于 2010.8.5 深圳 使用半字节查表法之CRC16的code sample(一) 使用半字节查表法之CRC16的code sample(二)  

在进行通讯的过程中, 我们需要和CRC打交道. Allen觉得, 尽管在很多时候, CRC并不是那么重要. 但是出于通讯协议兼容, 我们往往被迫使用CRC计算. 在通宵的工作过程中, Allen 对网络资源进行了一番整理, 并自行加入理解, 便于同行们, 在相应工作时, 节省大量查阅资料的时间. 前提: 1. 运算法则的可靠性: 在反复检索资料后, Allen 意识到, 弄清运算法则需要至少1个工作日, 用大量实例和思考, 并配合相当的实例进行思考. 在极大的项目时间压力下, 我们放弃这个know-why 的行为. 我们接受现有算法, 作为"定理"的引用, 而非作为一个严谨算数逻辑推导的结果. CRC要素: 1. 多项式除法 在进行 CRC 计算之前, 我们不得不重温多项式除法. 检索:   http://certmaths.ilongman.com/chi/ppt/ch03/lecture03_02c.ppt 的 ppt 文档. 大致我们知道: 多项式除以单项式时, 我们可以使用分配率. 而多项式除以多项式时, 我们必须使用长除法. 2. CRC原理 简单描述: 把待传送的数据 M 的二进制码序列看成多项式 M, 事先选定一个 r+1 bit 的二进制数看成多项式 P, 把多项式 M 除以 P, 得到商Q 和余数 R(r bit), 把余数 R 附加在信息码 M 一起发送. 在接收端, 使用同样的 M/P 获取余数 R', 与 R 比较验证 M 是否正确. 引用讨论: http://topic.csdn.net/u/20090625/09/d3121402-443c-4d6d-be2d-6746f9434c72.html 举例说明: 信息位: 1011001 CRC码: 4位 r = 4 校验多项式(生成码): 11001 (x4+x3+1) 运算步骤: 1011001 - 左移4位 - 10110010000 - 除以 11001 - 遵守运算法则: 不借位除法, 即异或运算, 得到结果(余数) 1010, 即为 CRC 码. 3. 例程实现: CRC的算法包括: 基本算法, 字节查表法, 半字节查表法 我们主要讨论 16 bit 的 CRC 实现, 使用 CRC16-CCITT, 也即是 X16+X12+X5+1, 生成码为 0x1021. 本来实际值应该是 0x010121, 这里又引入了一个运算法则: "最高位一定为1故抛弃", 因此是 0x1021. 3.1 基本算法: http://read.pudn.com/downloads90/sourcecode/embed/341559/crc.c__.htm /****************************************************************   *函数性质：公共   *入口：要进行CRC校验的数据缓冲unsigned char *ptr，要进行CRC校验的数据长度   *出口：CRC计算结果   *功能：CRC16计算（计算速度慢，程序空间小）   *调用方式：unsigned short CalCRC16Slow(unsigned char *ptr, unsigned char len)  *****************************************************************/   #if CRC16 == CRC16SLOW    unsigned short CalCRC16Slow(unsigned char *ptr, unsigned char len)   {       unsigned char i;       unsigned short crc = 0;       while(len--!=0)        {           for(i = 0x80; i != 0; i/=2)            {               if((crc0x8000)!=0)                {                   crc*=2;                    crc^=0x1021;               }                                           /* 余式CRC乘以2再求CRC  */               else crc*=2;               if((*ptri)!=0) crc^=0x1021;                /* 再加上本位的CRC */           }           ptr++;       }       return(crc);   }   #endif    注: 我们未验证该例程. 并注意到这里又引入了一个运算法则: 使用模2的方式, 进行异或运算(应该指不借位除法). 使用半字节查表法之CRC16的code sample(一) 使用半字节查表法之CRC16的code sample(二)