二進制反碼求和

二進制反碼求和，二進制算法。

0和0相加是0，0和1相加是1，1和1相加是0但要產生一個進位1，加到下一列．若最高位相加後產生進位，則最後得到的結果要加1．
IP/ICMP/IGMP/TCP/UDP等協定的校驗和算法都是相同的，算法如下：
在傳送數據時，為了計算IP數據包的校驗和。應該按如下步驟：
（1）把IP數據包的校驗和欄位置為0；
（2）把首部看成以16位為單位的數字組成，依次進行二進制反碼求和；
（3）把得到的結果存入校驗和欄位中。
在接收數據時，計算數據包的校驗和相對簡單，按如下步驟：
（1）把首部看成以16位為單位的數字組成，依次進行二進制反碼求和，包括校驗和欄位；
（2）檢查計算出的校驗和的結果是否等於零（反碼應為16個0）；
（3）如果等於零，說明被整除，校驗是和正確。否則，校驗和就是錯誤的，協定棧要拋棄這個數據包。
所謂的二進制反碼求和，即為先進行二進制求和，然後對和取反。
計算對IP首部檢驗和的算法如下：
（1）把IP數據包的校驗和欄位置為0；
（2）把首部看成以16位為單位的數字組成，依次進行二進制求和（注意：求和時應將最高位的進位保存，所以加法應採用32位加法）；
（3）將上述加法過程中產生的進位（最高位的進位）加到低16位（採用32位加法時，即為將高16位與低16位相加，之後還要把該次加法最高位產生的進位加到低16位）
（4）將上述的和取反，即得到校驗和。
其中，二進制反碼求和的計算方法：
首先，我們計算如圖B-1所示的部分和。我們把每一列相加，如果有進位，就加到下一列。注意以下幾點：
1-->16
1 1-->15
* 1-->14
* 1-->13
* * 1 1-->12
* * * 1-->11
* * * * 1-->10
* * * * * 1 1-->9
* * * * * * * 1 1-->7
* * * * * * * * * 1-->6
* * * * * * * * * 1-->5
* * * * * * * * * 1-->4
* * * * * * * * * * 1-->3
* * * * * * * * * * * * 1 1-->2
* * * * * * * * * * * * 1-->第1的進位，以上同意（右起為第一列）
1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1
1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0
0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1
0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0
0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 1
0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0
__________________________________
1 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 部分和
1 -->第15列的進位
1 -->第16列的進位
__________________________________
1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 和
0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 校驗和
圖B-1 二進制記法的部分和
1，當我們加第1列(最右邊一列)的時候，我們得到8。在二進制中，數8是1000。我們保留最右邊的0，把其餘的位進到第2列，第3列和第4列。
2，當我們加第2列時，我們計入從第1列來的進位。結果是7，它是二進制的0111。我們保留第一個位(最右邊的)，把其餘011進位給第3列、第4列和第5列。
3，對每一列重複以上過程。
4，當我們加完最後一列時，我們有兩個1沒有列可以進行相加。這兩個1在下一個步驟中應與部分和(Partial sum)相加。
B.1.2和
如果最後一列沒有進位，那么部分和就是和。但是，如果還有額外的列(在本例中，有一個具有兩行的列)，那么就要把它加到部分和中，以便得出和。下圖給出了這樣的計算，現在我們得出了和。
1 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 部分和
1 0 -->第15，16列的進位
__________________________________
1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 和
0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 校驗和
圖B-2 二進制記法的和與校驗和
B.1.2校驗和
在計算出和以後，我們把每一個位求反碼，得出檢驗和。圖B-2也給出了檢驗和。二進制計算方法其實可以轉換為十進制計算，原理相同。
算法的實現：
首先，查看了Linux 2.6核心中的校驗算法，使用彙編語言編寫的，顯然效率要高些。代碼如下：
unsigned short ip_fast_csum(unsigned char * iph,
unsigned int IHL)
{
unsigned int sum;
__asm__ __volatile__(
"movl (%1), %0 ;\n"
"subl $4, %2 ;\n"
"jbe 2f ;\n"
"addl 4(%1), %0 ;\n"
"adcl 8(%1), %0 ;\n"
"adcl 12(%1), %0 ;\n"
"1: adcl 16(%1), %0 ;\n"
"lea 4(%1), %1 ;\n"
"decl %2 ;\n"
"jne 1b ;\n"
"adcl $0, %0 ;\n"
"movl %0, %2 ;\n"
"shrl $16, %0 ;\n"
"addw %w2, %w0 ;\n"
"adcl $0, %0 ;\n"
"notl %0 ;\n"
"2: ;\n"
/* Since the input registers which are loaded with iph and ihl
are modified, we must also specify them as outputs, or gcc
will assume they contain their original values. */
: "=r" (sum), "=r" (iph), "=r" (ihl)
: "1" (iph), "2" (ihl)
: "memory");
return(sum);
}
在這個函式中，第一個參數顯然就是IP數據報的首地址，所有算法幾乎一樣。需要注意的是第二個參數，它是直接使用IP數據報頭信息中的首部長度欄位，不需要進行轉換，因此，速度又快了（高手就是考慮的周到）。使用方法會在下面的例子代碼中給出。
第二種算法就非常普通了，是用C語言編寫的。我看了許多實現網路協定棧的代碼，這個算法是最常用的了，即使變化，也無非是先取反後取和之類的。考慮其原因，估計還是C語言的移植性更好吧。下面是該函式的實現：
unsigned short checksum(unsigned short *buf,int nword)
{
unsigned long sum;
for(sum=0;nword>0;nword--)
sum += *buf++;
sum = (sum>>16) + (sum&0xffff);
sum += (sum>>16);
return ~sum;
}