程序员实用算法笔记----2.CRC校验

1.最常用的几种生成多项式如下：
CRC8=X8+X5+X4+X0
CRC-CCITT=X16+X12+X5+X0
CRC16=X16+X15+X2+X0
CRC12=X12+X11+X3+X2+X0
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X0
2. 《程序员实用算法》10.3.1 CRC-CCITT
2.1 直接计算出crc

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)

unsigned short getCCITT(unsigned short crc, unsigned short ch)
{
     static unsigned int i;
     ch <<= 8;
     for(i=8; i>0; i--)
     {
         if( (ch^crc) & 0x8000)
             crc = (crc<<1)^0x1021;
         else
             crc <<= 1;
         ch <<= 1;
     }
     return (crc);
}

int main ( int argc, char *argv[] )
{
    int i;
    int len;
    //7E 00 05 60 31 32 33 计算CRC16校验结果是：5B3E
    char buf[16]= {0x7E, 0x00, 0x05, 0x60, 0x31, 0x32, 0x33};
    unsigned short crc;
    len = 7;
    crc = 0;
    for(i=0; i<len; i++)
    {
        crc = getCCITT(crc, buf[i]);
        dbmsg("crc=0x%x", crc);
    }
    printf("crc=0x%x\n", crc);
    return EXIT_SUCCESS;
}

2.2 查表法之一生成CRC的table

#include 
#include 
#include 
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
unsigned short table[256];

unsigned short initCCITT()
{
    unsigned int i;
    unsigned int j;
    unsigned int index;
    unsigned short crc = 0;
    for(i=0; i<256; i++)
    {
        crc  = 0;
        index = i<<8;
        for(j=8; j>0; j--)
        {
            if( (index^crc)&0x8000 )
                crc = (crc<<1)^0x1021;
            else 
                crc <<= 1;
            index <<= 1;
        }
        table[i] = crc;
        dbmsg("%d=0x%04X", i, table[i]);
    }
    return 0; 
}

int main ( int argc, char *argv[] )
{
    initCCITT();             //生成crc16表
    return EXIT_SUCCESS;
}

2.3 查表法之二利用查表法得到crc

#include 
#include 
#include 
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
unsigned short table[256];

unsigned short initCCITT()
{
    unsigned int i;
    unsigned int j;
    unsigned int index;
    unsigned short crc = 0;
    for(i=0; i<256; i++)
    {
        crc  = 0;
        index = i<<8;
        for(j=8; j>0; j--)
        {
            if( (index^crc)&0x8000 )
                crc = (crc<<1)^0x1021;
            else 
                crc <<= 1;
            index <<= 1;
        }
        table[i] = crc;
        dbmsg("%d=0x%04X", i, table[i]);
    }
    return 0; 
}


int main ( int argc, char *argv[] )
{
    int i;
    int len;
    //7E 00 05 60 31 32 33 计算CRC16校验结果是：5B3E
    char buf[16]= {0x7E, 0x00, 0x05, 0x60, 0x31, 0x32, 0x33};
    unsigned short crc;
    len = 7;
    crc = 0;
    initCCITT();
    for(i=0; i
    {
        crc = (crc<<8)^table[crc>>8^buf[i]];
        dbmsg("crc=0x%x", crc);
    }
    printf("crc=0x%x\n", crc);
    return EXIT_SUCCESS;
}