二進制反碼求和

從低到高位逐列進行計算。0和0加得0,0和1加得1,1和1加得0但要產生一個進位1，加到下一列。若最高位產生了進位，則最後得到的結果要加1。

（0）反 + （0）反 = 1 + 1 = 10

（1）反 +（0）反=0+ 1 =1

（1）反 + （1）反 = 0 + 0 = 0

IP/ICMP/IGMP/TCP/UDP等協議的 ^[1]  校驗和算法都是相同的，算法如下：

（1）把IP數據包的校驗和字段置為0。

（2）把首部看成以16位為單位的數字組成，依次進行二進制反碼求和。

（3）把得到的結果存入校驗和字段中。

（1）把首部看成以16位為單位的數字組成，依次進行二進制反碼求和，包括校驗和字段。

（2）檢查計算出的校驗和的結果是否等於零（反碼應為16個0）。

（3）如果等於零，説明被整除，校驗和正確。否則，校驗和就是錯誤的，協議棧要拋棄這個數據包。

所謂的二進制反碼求和，即為先進行二進制數取反，然後求和，如果最高位進一，則保存到最低位即可。

（1）把IP數據包的校驗和字段置為0。

（2）把首部看成以16位為單位的數字組成，依次進行二進制求和（注意：求和時應將最高位的進位保存，所以加法應採用32位加法）。

（3）將上述加法過程中產生的進位（最高位的進位）加到低16位（採用32位加法時，即為將高16位與低16位相加，之後還要把該次加法最高位產生的進位加到低16位）。

（4）將上述的和取反，即得到校驗和。

二進制反碼求和的計算方法

首先，我們計算所示的部分和。我們把每一列相加，如果有進位，就加到下一列，注意以下幾點：

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 校驗和

二進制記法的部分和

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.1.2校驗和

在計算出和以後，我們把每一個位求反碼，得出檢驗和。圖B-2也給出了檢驗和。二進制計算方法其實可以轉換為十進制計算，原理相同。

首先，查看了Linux 2.6內核中的校驗算法，使用 ^[2]  彙編語言編寫的，顯然效率要高些。代碼如下：

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語言編寫的。我看了許多實現網絡 ^[3]  協議棧的代碼，這個算法是最常用的了，即使變化，也無非是先取反後取和之類的。考慮其原因，估計還是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);

}

return ~sum;

}