以前看計(jì)算機(jī)網(wǎng)絡(luò)相關(guān)的書，每次看到IP或者UDP報(bào)頭校驗(yàn)和時(shí)，都一瞥而過，以為相當(dāng)簡單，不就是16bit數(shù)據(jù)的相加嗎。最近在研究《TCP/IP詳解 卷1：協(xié)議》這本書，看到校驗(yàn)和是16bit字的二進(jìn)制反碼和（暈，以前都沒注意原來是反碼和，看來以前看書不仔細(xì)??！罪過，罪過~~），覺得很奇怪，為什么會(huì)用反碼和，而不是直接求和呢？（因?yàn)槲艺J(rèn)為TCP/IP協(xié)議里面的算法和思想一般都是非常經(jīng)典的，人家這么做一定有原因的）下面就來探索一下這個(gè)校驗(yàn)和算法具體怎么實(shí)現(xiàn)的。

 首先，IP、ICMP、UDP和TCP報(bào)文頭部都有校驗(yàn)和字段，大小都是16bit，算法也基本一樣：

 在發(fā)送數(shù)據(jù)時(shí)，為了計(jì)算數(shù)據(jù)包的校驗(yàn)和。應(yīng)該按如下步驟：

（1）把校驗(yàn)和字段置為0； 　　
（2）把需校驗(yàn)的數(shù)據(jù)看成以16位為單位的數(shù)字組成，依次進(jìn)行二進(jìn)制反碼求和； 　　
（3）把得到的結(jié)果存入校驗(yàn)和字段中。 　　

在接收數(shù)據(jù)時(shí)，計(jì)算數(shù)據(jù)包的校驗(yàn)和相對簡單，按如下步驟： 　　
（1）把首部看成以16位為單位的數(shù)字組成，依次進(jìn)行二進(jìn)制反碼求和，包括校驗(yàn)和字段； 　　
（2）檢查計(jì)算出的校驗(yàn)和的結(jié)果是否為0； 　　
（3）如果等于0，說明被整除，校驗(yàn)是和正確。否則，校驗(yàn)和就是錯(cuò)誤的，協(xié)議棧要拋棄這個(gè)數(shù)據(jù)包。

 雖然上面四種報(bào)文的校驗(yàn)和算法一樣，但在作用范圍存在不同：IP校驗(yàn)和只校驗(yàn)20字節(jié)的IP報(bào)頭；而ICMP校驗(yàn)和覆蓋整個(gè)報(bào)文（ICMP報(bào)頭+ICMP數(shù)據(jù)）；UDP和TCP校驗(yàn)和不僅覆蓋整個(gè)報(bào)文，而且還有12字節(jié)的IP偽首部，包括源IP地址(4字節(jié))、目的IP地址(4字節(jié))、協(xié)議(2字節(jié)，第一字節(jié)補(bǔ)0)和TCP/UDP包長(2字節(jié))。另外UDP、TCP數(shù)據(jù)報(bào)的長度可以為奇數(shù)字節(jié)，所以在計(jì)算校驗(yàn)和時(shí)需要在最后增加填充字節(jié)0（注意，填充字節(jié)只是為了計(jì)算校驗(yàn)和，可以不被傳送）。

這里還要提一點(diǎn)，UDP的校驗(yàn)和是可選的，當(dāng)校驗(yàn)和字段為0時(shí)，表明該UDP報(bào)文未使用校驗(yàn)和，接收方就不需要校驗(yàn)和檢查了！那如果UDP校驗(yàn)和的計(jì)算結(jié)果是0時(shí)怎么辦呢？書上有這么一句話：“如果校驗(yàn)和的計(jì)算結(jié)果為0，則存入的值為全1（65535），這在二進(jìn)制反碼計(jì)算中是等效的。”

講了這么多，那這個(gè)校驗(yàn)和到底是怎么算的呢？

1. 什么是二進(jìn)制反碼求和

對一個(gè)無符號的數(shù)，先求其反碼，然后從低位到高位，按位相加，有溢出則向高位進(jìn)1（跟一般的二進(jìn)制加法規(guī)則一樣），若最高位有進(jìn)位，則向最低位進(jìn)1。

首先這里的反碼好像跟我們以前學(xué)的有符號數(shù)的反碼不一樣（即正數(shù)的反碼是其本身，負(fù)數(shù)的反碼是在其原碼的基礎(chǔ)上，符號位不變，其余各位取反），這里不分正負(fù)數(shù)，直接每個(gè)位都取反！

上面加粗的那句是跟我們一般的加法規(guī)則不太一樣的地方：最高位有進(jìn)位，則向最低位進(jìn)1。確實(shí)有些疑惑，為什么要這樣做呢？仔細(xì)分析一下（為了方便說明，以 4bit二進(jìn)制反碼求和舉例），上面的這種操作，使得在發(fā)生加法進(jìn)位溢出時(shí)，溢出的值并不是10000，而是1111。也即是當(dāng)相加結(jié)果滿1111時(shí)溢出，這樣也可以說明為什么0000和1111都表示0了（你同樣可以發(fā)現(xiàn)，任何數(shù)與這兩個(gè)數(shù)做二進(jìn)制反碼求和運(yùn)算結(jié)果都是原數(shù)，這恰好符合數(shù)0的加法意義）。

下面再舉例兩種二進(jìn)制反碼求和的運(yùn)算：

原碼加法運(yùn)算                                               反碼加法運(yùn)算
3（0011）+ 5（0101）= 8（1000）      3（1100）+ 5（1010）=  8（0111）
8（1000）+ 9（1001）= 1（0001）      8（0111）+ 9（0110）=  2（1101）

從上面兩個(gè)例子可以看出，當(dāng)加法未發(fā)生溢出時(shí)，原碼與反碼加法運(yùn)算結(jié)果一樣；當(dāng)有溢出時(shí)，結(jié)果就不一樣了，原碼是滿10000溢出，而反碼是滿1111溢出，所以相差正好是1。舉例只是為了形象地觀察二進(jìn)制反碼求和的運(yùn)算規(guī)則，至于為什么要定義這樣的規(guī)則以及該運(yùn)算規(guī)則還存在其它什么特性，可能就需要涉及代數(shù)理論的東西的了（嗚嗚~~數(shù)學(xué)理論沒學(xué)好啊，只能從表面上分析分析）。

另外關(guān)于二進(jìn)制反碼求和運(yùn)算需要說明的一點(diǎn)是，先取反后相加與先相加后取反，得到的結(jié)果是一樣的！（事實(shí)上我們的編程算法里，幾乎都是先相加后取反。）

2. 校驗(yàn)和算法的實(shí)現(xiàn)

講了什么是二進(jìn)制反碼求和，那么校驗(yàn)和的算法實(shí)現(xiàn)就簡單多了。廢話少說，直接上代碼：

buffer是指向需校驗(yàn)數(shù)據(jù)緩存區(qū)的指針，size是需校驗(yàn)數(shù)據(jù)的總長度（字節(jié)為單位）
4~13行代碼對數(shù)據(jù)按16bit累加求和，由于最高位的進(jìn)位需要加在最低位上，所以cksum必須是32bit的unsigned long型，高16bit用于保存累加過程中的進(jìn)位；另外代碼10~13行是對size為奇數(shù)情況的處理！
14~16行代碼的作用是將cksum高16bit的值加到低16bit上，即把累加中最高位的進(jìn)位加到最低位上。這里使用了while循環(huán)，判斷cksum高16bit是否非零，因?yàn)榈?6行代碼執(zhí)行的時(shí)候，仍可能向cksum的高16bit進(jìn)位。有些地方是通過下面兩條代碼實(shí)現(xiàn)的：cksum = (cksum >> 16) + (cksum & 0xffff);
cksum += (cksum >>16);這里只進(jìn)行了兩次相加，即可保證相加后cksum的高16位為0，兩種方式的效果一樣。事實(shí)上，上面的循環(huán)也最多執(zhí)行兩次！
17行代碼即對16bit數(shù)據(jù)累加的結(jié)果取反，得到二進(jìn)制反碼求和的結(jié)果，然后函數(shù)返回該值。

3. 為什么使用二進(jìn)制反碼求和呢？

好了，最后一個(gè)問題，為什么要使用二進(jìn)制反碼來計(jì)算校驗(yàn)和呢，而不是直接使用原碼或者補(bǔ)碼？
這個(gè)問題我想了很久，由于水平有限實(shí)在弄不明白，于是在百度上一陣狂搜，什么都沒有（不知道是百度不給力，還是大家都不關(guān)注這個(gè)問題呢？）。果斷換google，敲了3個(gè)關(guān)鍵詞：why checksum tcp，嘿嘿 結(jié)果第二篇就是我想要的文章了?。?！
先把鏈接給大家吧：http://www.netfor2.com/checksum.html
這篇文章主要介紹二進(jìn)制反碼求和（the 1's complement sum）與補(bǔ)碼求和（the 2's complement sum）的區(qū)別，另外還說明了在TCP/IP校驗(yàn)和中使用反碼求和的優(yōu)點(diǎn)。

It may look awkword to use a 1's complement addition on 2's complement machines. This method however has its own benefits.
Probably the most important is that it is endian independent. Little Endian computers store hex numbers with the LSB last (Intel processors for example). Big Endian computers put the LSB first (IBM mainframes for example). When carry is added to the LSB to form the 1's complement sum (see the example) it doesn't matter if we add 03 + 01 or 01 + 03. The result is the same.
Other benefits include the easiness of checking the transmission and the checksum calculation plus a variety of ways to speed up the calculation by updating only IP fields that have changed.

上面是原文的一部分，說明在TCP/IP校驗(yàn)和中使用反碼求和的一些優(yōu)點(diǎn)：

a. 不依賴系統(tǒng)是大端還是小端。 即無論你是發(fā)送方計(jì)算或者接收方檢查校驗(yàn)和時(shí)，都不需要調(diào)用htons 或者 ntohs，直接通過上面第2節(jié)的算法就可以得到正確的結(jié)果。這個(gè)問題你可以自己舉個(gè)例子，用反碼求和時(shí)，交換16位數(shù)的字節(jié)順序，得到的結(jié)果相同，只是字節(jié)順序相應(yīng)地也交換了；而如果使用原碼或者補(bǔ)碼求和，得到的結(jié)果可能就不相同！
b. 計(jì)算和驗(yàn)證校驗(yàn)和比較簡單，快速。說實(shí)話，這個(gè)沒怎么看明白，感覺在校驗(yàn)和計(jì)算方面，原碼或者補(bǔ)碼求和反而更簡單一些（從C語言角度），在校驗(yàn)和驗(yàn)證上面，通過一樣的算法判斷結(jié)果是否為全 0，確實(shí)要方便一些，所以可能從綜合考慮確實(shí)反碼求和要簡便一些。另外，IP報(bào)文在傳輸過程中，路由器經(jīng)常只修改TTL字段（減1），此時(shí)路由器轉(zhuǎn)發(fā)該報(bào)文時(shí)可以直接增加它的校驗(yàn)和，而不需要對IP整個(gè)首部進(jìn)行重新計(jì)算。當(dāng)然，可能從匯編語言的角度看，反碼求和還有很多高效的地方，這里就不在深入追究了~~~
結(jié)語：本來一個(gè)不怎么注意的地方，深入探究一下竟然發(fā)現(xiàn)這么多東西。學(xué)習(xí)算法其實(shí)沒有必要抱著《算法導(dǎo)論》一頁一頁地啃（嘿嘿，哥也有一本哦），我更喜歡從 TCP/IP協(xié)議或LInux內(nèi)核原理中去探究算法以及實(shí)現(xiàn)思想，這樣反倒更有趣，而且這里面的一些算法和思想相當(dāng)經(jīng)典，慢慢體會(huì)，必然受益匪淺！