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