一、
校驗和算法
之前一直只知道IP校驗和算法反碼求和相關(guān)的,但具體細(xì)節(jié)不清楚,今天了解了下。
IP校驗和主要是用來保證數(shù)據(jù)(IP包頭)的完整性的.它用的算法非常簡單,就是反碼求和校驗.需要注意的是反碼求和又叫1的補碼(one's
complement),而2的補碼就是我們通常說的補碼求和了.校驗算法具體如下.
1、發(fā)送方
i)將校驗和字段置為0,然后將IP包頭按16比特分成多個單元,如包頭長度不是16比特的倍數(shù),則用0比特填充到16比特的倍數(shù);
ii)對各個單元采用反碼加法運算(即高位溢出位會加到低位,通常的補碼運算是直接丟掉溢出的高位),將得到的和的反碼填入校驗和字段;
iii)發(fā)送數(shù)據(jù)包;
2、接收方
i)將IP包頭按16比特分成多個單元,如包頭長度不是16比特的倍數(shù),則用0比特填充到16比特的倍數(shù);
ii)對各個單元采用反碼加法運算,檢查得到的和是否符合是全1(有的實現(xiàn)可能對得到的和會取反碼,然后判斷最終值是不是全0);
iii)如果是全1則進(jìn)行下步處理,否則意味著包已變化從而丟棄之.
需要強調(diào)的是反碼和是采用高位溢出加到低位的,如3比特的反碼和運算:100b+101b=010b(因為100b+101b=1001b,高位溢出1,其應(yīng)該加到低位,即001b+1b(高位溢出位)=010b),具體細(xì)節(jié)請參考文章:http://blog.chinaunix.net/u/20/showart_438418.html
二、
校驗和源碼
網(wǎng)上流傳多組實現(xiàn),常見的有如下兩種(如追求效率可改寫為匯編代碼):
1、RFC1071源碼
|
unsigned short csum(unsigned char *addr, int count)
{
/* Compute Internet Checksum for "count" bytes
* beginning at location "addr".
*/
register long sum = 0;
while( count > 1 )
{
/* This is the inner loop */
sum += * (unsigned short) addr++;
count -= 2;
}
/* Add left-over byte, if any */
if( count > 0 )
sum += * (unsigned char *) addr;
/* Fold 32-bit sum to 16 bits */
while (sum>>16)
sum = (sum & 0xffff) + (sum >> 16);
return ~sum;
}
|
第一個while循環(huán)是做普通加法(2進(jìn)制補碼加法),因為IP包頭和TCP整個報文段比較短(沒達(dá)到2^17數(shù)量級),所以不可能導(dǎo)致4字節(jié)的sum溢出(unsigned long 一般至少為4字節(jié))).
緊接著的一個判斷語句是為了能處理輸入數(shù)據(jù)是奇數(shù)個字節(jié)的這種情況.
再接著的數(shù)據(jù)循環(huán)是實現(xiàn)反碼算法(在前面的普通加法得到的數(shù)據(jù)的基礎(chǔ)上),由反碼和的高位溢出加到低位的性質(zhì),可得到"32位的數(shù)據(jù)的高位比特移位16比特,再加上原來的低16比特,不影響最終結(jié)果"這個等價運算,因為sum的最初值(剛開始循環(huán)時)可能很大,所以這個等價運算需循環(huán)進(jìn)行,直到sum的高比特(16比特以上)全為0.對于32位的sum,事實上這個運算循環(huán)至多只有兩輪,所以也有程序直接用兩條"sum = (sum & 0xffff) + (sum >> 16);"代替了整個循環(huán).
最后,對和取反返回.
2、對數(shù)據(jù)長度沒限制的實現(xiàn)
|
unsigned short cksum (struct ip *ip, int len)
{
long sum = 0; /* assume 32 bit long, 16 bit short */
while ( len >1 )
{
sum += *((unsigned short *) ip)++;
if (sum & 8x00000000) /* if high-order bit set, fold */
sum = (sum & 0xFFFF) + (sum>> 16) ;
len -= 2;
}
if ( len ) /* take care of left over byte */
sum += ( unsigned short ) * (unsignedl char *) ip;
while ( sum >> 16)
sum =(sum & 0xFFFF) + (sum>> 16);
return ~sum;
}
|
這個實現(xiàn)與前面的一個的最大的不同是對數(shù)據(jù)的長度沒什么限制了,因為它在第一個循環(huán)的加法運算中實時檢測sum的高位的值,一旦發(fā)現(xiàn)其有溢出的危險,就及時運用等價運算關(guān)系消除了這個危險.
三、
幾個細(xì)節(jié)問題
1、數(shù)據(jù)部分改變時的重校驗
考慮這樣的應(yīng)用場景:路由器轉(zhuǎn)發(fā)IP報文時,有可能只更改了IP數(shù)據(jù)包頭的部分內(nèi)容(如更改了TTL,分片了或SNAT更改了源IP等~~~),卻需要重校驗的問題.為提高轉(zhuǎn)發(fā)效率,要求重校驗算法盡可能快,故出現(xiàn)了如下的重校驗算法:
|
UpdateTTL(struct ip_hdr *ipptr, unsigned char n)
{
unsigned long sum;
unsigned short old;
old = ntohs(*(unsigned short *)&ipptr->ttl);
ipptr->ttl -= n;
sum = old + (~ntohs(*(unsigned short *)&ipptr->ttl) & 0xffff);
sum += ntohs(ipptr->Checksum);
sum = (sum & 0xffff) + (sum>>16);
ipptr->Checksum = htons(sum + (sum>>16));
}
|
算法的實現(xiàn)依據(jù)是這樣的.假設(shè)包頭原校驗和為~C,改變的字段的原始值是m,更改后的值是m',設(shè)~C'為重校驗和,則有 ~C' = ~(C+(-m)+m') = ~C+(m-m') = ~C+m+~m'
等價關(guān)系的成立基于反碼的運算性質(zhì):取反運算滿足結(jié)合律,按位取反運算與符號取反(及相反數(shù))是等價的(即~C=-C).
2、為什么采用反碼和運算
IP數(shù)據(jù)包校驗要求速度快,所以只采用了簡單的和校驗,為什么采用反碼和而不是補碼和呢?
i)反碼和的溢出有后效性(蔓延性)
反碼和將高位溢出加到低位,導(dǎo)致這個溢出會對后面操作有永久影響,有后效性;而補碼和直接將高位和溢出,導(dǎo)致這個溢出對后面的操作再無影響,因此無后效性
ii)反碼校驗無需考慮字節(jié)序
正因為反碼和的溢出有后效性,導(dǎo)致大端字節(jié)序(big-endian)和小端字節(jié)序(little-endian)對同一數(shù)據(jù)序列(如兩個16比特的序列)產(chǎn)生的校驗和也只是字節(jié)序相反，而補碼和因為將溢出丟掉了,不同字節(jié)序之間的校驗大不相同且沒什么聯(lián)系。
基于以上的理由，校驗和運算既可選擇在數(shù)據(jù)被轉(zhuǎn)換成網(wǎng)絡(luò)字節(jié)序前，也可選擇在之后。（這其實可以看作是負(fù)負(fù)得正，計算校驗和與字節(jié)序有關(guān)，然后寫校驗和字段與字節(jié)序有關(guān)，然后直接計算校驗和再寫校驗和字段則與字節(jié)序無關(guān)了~~）
四、
參考文章
http://blog.chinaunix.net/u/20/showart_438512.html，關(guān)于IP校驗和的
http://blog.chinaunix.net/u/12313/showart_176114.html，關(guān)于網(wǎng)絡(luò)校驗和的
http://www.wesoho.com/article/Delphi/2143.htm，關(guān)于IP校驗和的
http://blog.chinaunix.net/u/20/showart_438418.html，關(guān)于補碼和反碼的
posted on 2009-07-12 23:42
iConnect 閱讀(210)
評論(0) 編輯 收藏 所屬分類:
C/C++