原创 使用半字节查表法之CRC16的code sample(二)

3.2 字节查表法

unsigned char code crc_ta[256] = {  
#else   
const unsigned short crc_ta[256] = {                    /* 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[da^*ptr];                               /* 高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[16]={ 
 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^(*ptr/16)];                  
        da = ((unsigned char)(crc/256))/16;         
        crc<<=4;                                    
        crc^=crc_ta[da^(*ptr&0x0f)];                
        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(二)