梦依稀

IP数据报首部校验和算法 [转]

IP/ICMP/IGMP/TCP/UDP 报文头都有检验和字节, 大小都是2个字节(16bit), 算法相同

对于发送方计算检验和：
（1）把IP数据报的首部都置为0，包括校验和字节。
（2）把首部看成以16bit为单位的数字组成，依次进行二进制反码求和。
（3）把得到的结果存入校验和字段中。

对于接收者校验：
（1）对于接收的IP报文头部以16bit为单位逐个求和；
（2）若结果全为1，则校验正确，否则出错丢弃；

        0x0000:  4500 00e5 0000 4000 4011 7592 0ace 22cf  E.....@[email protected]...".
        0x0010:  0af6 8be3

发送方

4500 + 00e5 + 0000 + 4000 + 4011 + 0000 + 0ace + 22cf  + 0af6 + 8be3 = 1 8a6c
0001 + 8a6c = 8a6d
8a6d 反码 7592

接收方

4500 + 00e5 + 0000 + 4000 + 4011 + 7592 + 0ace + 22cf  + 0af6 + 8be3 = 1 fffe
0001 + fffe = ffff

虽然上面报文的校验和算法一样，但是作用范围却不同：IP校验和只校验20字节的IP报头; 而ICMP校验和覆盖整个报文(ICMP报头+ICMP数据); UDP和TCP校验和不仅覆盖整个报文, 而且还有12个字节的IP伪首部, 包括源IP地址(4字节)、目的IP地址(4字节)、协议(2字节)、TCP/UDP包长(2字节)。另外UDP、TCP数据报的长度可以为奇数字节, 所以在计算校验和时需要在最后增加填充字节0(填充字节只是为了计算校验和, 可以不被传送)。

为什么使用二进制反码循环移位加法呢？

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.

a. 不依赖系统是大端还是小端。 即无论你是发送方计算或者接收方检查校验和时，都不需要调用htons 或者 ntohs，直接通过上面第2节的算法就可以得到正确的结果。这个问题你可以自己举个例子，用反码求和时，交换16位数的字节顺序，得到的结果相同，只是字节顺序相应地也交换了；而如果使用原码或者补码求和，得到的结果可能就不相同！
b.计算和验证校验和比较简单，快速。

校验和计算方法：
对一个无符号的数，先求其反码，然后从低位到高位，按位相加，有溢出则向高位进1(和一般的二进制法则一样),若最高位有进位，则向最低位进1.

特点：关于二进制反码循环移位求和运算，先取反后相加与先相加后取反，得到的结果是一样的。

可结合性和可交换性
用A，B，C，D，E，F分别表示一个8位的二进制数（一个字节），用[A, B]这样的形式表示A << 8 + B，那么16位校验和可以用个如下形式给出 sum = [A，B]+’[C，D]+’[E，F]； 其中， +’被表示二进制循环移位加法 可结合性：[A，B]+’[C，D]+’[E，F] = [A，B]+’（[C，D]+’[E，F]） 可交换性：[A，B]+’[C，D]+’[E，F] = [C，D]+’[A，B]+’[E，F] 字节自主性 [A，B]+’[C，D]+’[E，F] = [B，A]+’（[D，C]+’[F，E]） 由于若最高位有进位，则向最低位进1 这样的特性，第15位到0位进位，第7位向第8位进位，所以，整个求和结果是一样的。 并行计算 有些机器的字处理长度是16的倍数，这样可以提高他的计算速度，由于可结合行，那么32位机器可以[A，B，C，D]+’…进行32校验和

Reference
[1] http://www.netfor2.com/checksum.html

whisper