電子發燒友App
這兩天做項目，需要用到 CRC 校驗。以前沒搞過這東東，以為挺簡單的。結果看看別人提供的匯編源程序，居然看不懂。花了兩天時間研究了一下 CRC 校驗，希望我寫的這點東西能夠幫助和我有同樣困惑的朋友節省點時間。
先是在網上下了一堆亂七八遭的資料下來，感覺都是一個模樣，全都是從 CRC 的數學原理開始，一長串的表達式看的我頭暈。第一次接觸還真難以理解。這些東西不想在這里講，隨便找一下都是一大把。我想根據源代碼來分析會比較好懂一些。
費了老大功夫，才搞清楚 CRC 根據”權”(即多項表達式)的不同而相應的源代碼也有稍許不同。以下是各種常用的權。
CRC8=X8+X5+X4+1
CRC-CCITT=X16+X12+X5+1
CRC16=X16+X15+X5+1
CRC12=X12+X11+X3+X2+1
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1
以下的源程序全部以 CCITT 為例。其實本質都是一樣，搞明白一種，其他的都是小菜。
圖 1，圖 2 說明了 CRC 校驗中 CRC 值是如何計算出來的，體現的多項式正是 X16+X12+X5+1。 Serial Data 即是需要校驗的數據。從把數據移位開始計算，將數據位(從最低的數據位開始)逐位移入反向耦合移位寄存器(這個名詞我也不懂，覺得蠻酷的，就這樣寫了，嘿)。當所有數據位都這樣操作后，計算結束。此時，16 位移位寄存器中的內容就是 CRC 碼。
圖中進行 XOR 運算的位與多項式的表達相對應。
X5 代表 Bit5，X12 代表 Bit12，1 自然是代表 Bit0，X16 比較特別，是指移位寄存器移出的數據，即圖中的DATA OUT。可以這樣理解，與數據位做XOR運算的是上次 CRC值的 Bit15。
根據以上說明，可以依葫蘆畫瓢的寫出以下程序。(程序都是在 keil C 7.10 下調試的)
typedef unsigned char uchar;
typedef unsigned int uint;
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
uint crc; // CRC 碼
void main(void)
{
uchar *ptr;
crc = 0; // CRC 初值
ptr = crcbuff; // 指向第一個 Byte 數據
crc = crc16l(ptr,8);
while(1);
}
uint crc16l(uchar *ptr,uchar len) // ptr 為數據指針，len 為數據長度
{
uchar i;
while(len--)
{
for(i=0x80; i!=0; i>>=1)
{
if((crc&0x8000)!=0) {crc<<=1; crc^=0x1021;} 1-1
else crc<<=1; 1-2
if((*ptr&i)!=0) crc^=0x1021; 1-3
}
ptr++;
}
return(crc);
}
執行結果 crc = 0xdbc0;
程序 1-1,1-2,1-3 可以理解成移位前 crc 的 Bit15 與數據對應的 Bit(*ptr&i)做 XOR運算，根據此結果來決定是否執行 crc^=0x1021。只要明白兩次異或運算與原值相同，就不難理解這個程序。
很多資料上都寫了查表法來計算，當時是怎么也沒想通。其實蠻簡單的。假設通過移位處理了 8 個 bit 的數據，相當于把之前的 CRC 碼的高字節(8bit)全部移出，與一個 byte 的數據做XOR 運算，根據運算結果來選擇一個值(稱為余式)，與原來的 CRC 碼再做一次 XOR 運算，就可以得到新的 CRC 碼。
不難看出，余式有 256 種可能的值，實際上就是 0~255 以 X16+X12+X5+1 為權得到的 CRC碼，可以通過函數 crc16l來計算。以1 為例。
code test[]={0x01};
crc = 0;
ptr = test;
crc = crc16l(ptr,1);
執行結果 crc = 1021，這就是1 對應的余式。
進一步修改函數，我這里就懶得寫了，可得到 X16+X12+X5+1 的余式表。
code uint crc_ta[256]={ // X16+X12+X5+1 余式表
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
};
根據這個思路，可以寫出以下程序：
uint table_crc(uchar *ptr,uchar len) // 字節查表法求 CRC
{
uchar da;
while(len--!=0)
{
da=(uchar) (crc/256); // 以 8 位二進制數暫存 CRC 的高 8 位
crc<<=8; // 左移 8 位
crc^=crc_ta[da^*ptr]; // 高字節和當前數據 XOR 再查表
ptr++;
}
return(crc);
}
本質上 CRC 計算的就是移位和異或。所以一次處理移動幾位都沒有關系，只要做相應的處理就好了。
下面給出半字節查表的處理程序。其實和全字節是一回事。
code uint crc_ba[16]={
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
};
uint ban_crc(uchar *ptr,uchar len)
{
uchar da;
while(len--!=0)
{
da = ((uchar)(crc/256))/16;
crc <<= 4;
crc ^=crc_ba[da^(*ptr/16)];
da = ((uchar)(crc/256)/16);
crc <<= 4;
crc ^=crc_ba[da^(*ptr&0x0f)];
ptr++;
}
return(crc);
}
crc_ba[16]和crc_ta[256]的前 16 個余式是一樣的。
其實講到這里，就已經差不多了。反正當時我以為自己是懂了。結果去看別人的源代碼的時候，也是說采用 CCITT，但是是反相的。如圖 3
反過來，一切都那么陌生，faint.吐血，吐血。
仔細分析一下，也可以很容易寫出按位異或的程序。只不過由左移變成右移。
uint crc16r(unsigned char *ptr, unsigned char len)
{
unsigned char i;
while(len--!=0)
{
for(i=0x01;i!=0;i <<= 1)
{
if((crc&0x0001)!=0) {crc >>= 1; crc ^= 0x8408;}
else crc >>= 1;
if((*ptr&i)!=0) crc ^= 0x8408;
}
ptr++;
}
return(crc);
}
0x8408 就是 CCITT 的反轉多項式。
套用別人資料上的話
“反轉多項式是指在數據通訊時，信息字節先傳送或接收低位字節，如重新排位影響 CRC計算速度，故設反轉多項式。”
如
code uchar crcbuff [] = { 0x00,0x00,0x00,0x00,0x06,0x0d,0xd2,0xe3};
反過來就是
code uchar crcbuff_fan[] = {0xe3,0xd2,0x0d,0x06,0x00,0x00,0x00,0x00};
crc = 0;
ptr = crcbuff_fan;
crc = crc16r(ptr,8);
執行結果 crc = 0x5f1d;
如想驗證是否正確，可改
code uchar crcbuff_fan_result[] = {0xe3,0xd2,0x0d,0x06,0x00,0x00,0x00,0x00,0x1d,0x5f};
ptr = crcbuff_fan_result;
crc = crc16r(ptr,10);
執行結果 crc = 0; 符合 CRC 校驗的原理。
請注意 0x5f1d 在數組中的排列中低位在前，正是反相運算的特點。不過當時是把我搞的暈頭轉向。
在用半字節查表法進行反相運算要特別注意一點，因為是右移，所以 CRC 移出的 4Bit與數據 XOR 的操作是在 CRC 的高位端。因此余式表的產生是要以下列數組通過修改函數crc16r 產生。
code uchar ban_fan[]=
{0,0x10,0x20,0x30,0x40,0x50,0x60,0x70,0x80,0x90,
0xa0,0xb0,0xc0,0xd0,0xe0,0xf0};
得出余式表
code uint fan_yushi[16]={
0x0000, 0x1081, 0x2102, 0x3183,
0x4204, 0x5285, 0x6306, 0x7387,
0x8408, 0x9489, 0xa50a, 0xb58b,
0xc60c, 0xd68d, 0xe70e, 0xf78f
};
uint ban_fan_crc(uchar *ptr,uchar len)
{
uchar da;
while(len--!=0)
{
da = (uchar)(crc&0x000f);
crc >>= 4;
crc ^= fan_yushi [da^(*ptr&0x0f)];
da = (uchar)(crc&0x000f);
crc >>= 4;
crc ^= fan_yushi [da^(*ptr/16)];
ptr++;
}
return(crc);
}
主程序中
crc = 0;
ptr = crcbuff_fan;
crc = ban_fan_crc(ptr,8);
執行結果 crc = 0x5f1d;
工商網監
評論