c语⾔tcp校验和算法,IP、ICMP、UDP、TCP校验和算法分享以前看计算机⽹络相关的书,每次看到IP或者UDP报头校验和时,都⼀瞥⽽过,以为相当简单,不就是16bit数据的相加吗。最近在研究《TCP/IP详解 卷1:协议》这本书,看到校验和是16bit字的⼆进制反码和(晕,以前都没注意原来是反码和,看来以前看书不仔细啊!罪过,罪过~~),觉得很奇怪,为什么会⽤反码和,⽽不是直接求和呢?(因为我认为TCP/IP协议⾥⾯的算法和思想⼀般都是⾮常经典的,⼈家这么做⼀定有原因的)下⾯就来探索⼀下这个校验和算法具体怎么实现的。
⾸先,IP、ICMP、UDP和TCP报⽂头部都有校验和字段,⼤⼩都是16bit,算法也基本⼀样:
在发送数据时,为了计算数据包的校验和。应该按如下步骤:
(1)把校验和字段置为0;
(2)把需校验的数据看成以16位为单位的数字组成,依次进⾏⼆进制反码求和;
(3)把得到的结果存⼊校验和字段中。
在接收数据时,计算数据包的校验和相对简单,按如下步骤:
(1)把⾸部看成以16位为单位的数字组成,依次进⾏⼆进制反码求和,包括校验和字段;
(2)检查计算出的校验和的结果是否为0;
(3)如果等于0,说明被整除,校验是和正确。否则,校验和就是错误的,协议栈要抛弃这个数据包。
虽然上⾯四种报⽂的校验和算法⼀样,但在作⽤范围存在不同:IP校验和只校验20字节的IP报头;⽽ICMP校验和覆盖整个报⽂(ICMP报头+ICMP数据);UDP和TCP校验和不仅覆盖整个报⽂,⽽且还有12字节的IP伪⾸部,包括源IP地址(4字节)、⽬的IP地址(4字节)、协议(2字节,第⼀字节补0)和TCP/UDP包长(2字节)。另外UDP、TCP数据报的长度可以为奇数字节,所以在计算校验和时需要在最后增加填充字节0(注意,填充字节只是为了计算校验和,可以不被传送)。
这⾥还要提⼀点,UDP的校验和是可选的,当校验和字段为0时,表明该UDP报⽂未使⽤校验和,接收⽅就不需要校验和检查了!那如果UDP校验和的计算结果是0时怎么办呢?书上有这么⼀句话:“如果校验和的计算结果为0,则存⼊的值为全1(65535),这在⼆进制反码计算中是等效的。”
讲了这么多,那这个校验和到底是怎么算的呢?
1. 什么是⼆进制反码求和
对⼀个⽆符号的数,先求其反码,然后从低位到⾼位,按位相加,有溢出则向⾼位进1(跟⼀般的⼆进制加法规则⼀样),若最⾼位有进位,则向最低位进1。
⾸先这⾥的反码好像跟我们以前学的有符号数的反码不⼀样(即正数的反码是其本⾝,负数的反码是在其原码的基础上,符号位不变,其余各位取反),这⾥不分正负数,直接每个位都取反!
上⾯加粗的那句是跟我们⼀般的加法规则不太⼀样的地⽅:最⾼位有进位,则向最低位进1。确实有些疑惑,为什么要这样做呢?仔细分析⼀下(为了⽅便说明,以 4bit⼆进制反码求和举例),上⾯的这种操作,使得在发⽣加法进位溢出时,溢出的值并不是10000,⽽是1111。也即是当相加结果满1111时溢出,这样也可以说明为什么0000和1111都表⽰0了(你同样可以发现,任何数与这两个数做⼆进制反码求和运算结果都是原数,这恰好符合数0的加法意义)。
下⾯再举例两种⼆进制反码求和的运算:
原码加法运算 反码加法运算
3(0011)+ 5(0101)= 8(1000) 3(1100)+ 5(1010)= 8(0111)
8(1000)+ 9(1001)= 1(0001) 8(0111)+ 9(0110)= 2(1101)
从上⾯两个例⼦可以看出,当加法未发⽣溢出时,原码与反码加法运算结果⼀样;当有溢出时,结果就不⼀样了,原码是满10000溢出,⽽反码是满1111溢出,所以相差正好是1。举例只是为了形象地观察⼆进制反码求和的运算规则,⾄于为什么要定义这样的规则以及该运算规则还存在其它什么特性,
可能就需要涉及代数理论的东西的了(呜呜~~数学理论没学好啊,只能从表⾯上分析分析)。
另外关于⼆进制反码求和运算需要说明的⼀点是,先取反后相加与先相加后取反,得到的结果是⼀样的!(事实上我们的编程算法⾥,⼏乎都是先相加后取反。)
2. 校验和算法的实现
讲了什么是⼆进制反码求和,那么校验和的算法实现就简单多了。废话少说,直接上代码:
复制代码代码如下:
[cpp] view plaincopy
tcpip协议pdf//计算校验和
USHORT checksum(USHORT *buffer,int size)
{
unsigned long cksum=0;
while(size>1)
{
cksum+=*buffer++;
size-=sizeof(USHORT);
}
if(size)
{
cksum+=*(UCHAR *)buffer;
}
//将32位数转换成16
while (cksum>>16)
cksum=(cksum>>16)+(cksum & 0xffff);
return (USHORT) (~cksum);
}
buffer是指向需校验数据缓存区的指针,size是需校验数据的总长度(字节为单位)
4~13⾏代码对数据按16bit累加求和,由于最⾼位的进位需要加在最低位上,所以cksum必须是32bit的unsigned long型,⾼16bit⽤于保存累加过程中的进位;另外代码10~13⾏是对size为奇数情况的处理!
14~16⾏代码的作⽤是将cksum⾼16bit的值加到低16bit上,即把累加中最⾼位的进位加到最低位上。这⾥使⽤了while循环,判断cksum⾼16bit是否⾮零,因为第16⾏代码执⾏的时候,仍可能向cksum的⾼16bit进位。有些地⽅是通过下⾯两条代码实现的:cksum = (cksum >> 16) + (cksum & 0xffff);
cksum += (cksum >>16);这⾥只进⾏了两次相加,即可保证相加后cksum的⾼16位为0,两种⽅式的效果⼀样。事实上,上⾯的循环也最多执⾏两次!
17⾏代码即对16bit数据累加的结果取反,得到⼆进制反码求和的结果,然后函数返回该值。
3. 为什么使⽤⼆进制反码求和呢?
好了,最后⼀个问题,为什么要使⽤⼆进制反码来计算校验和呢,⽽不是直接使⽤原码或者补码?
这个问题我想了很久,由于⽔平有限实在弄不明⽩,于是在百度上⼀阵狂搜,什么都没有(不知道是百度不给⼒,还是⼤家都不关注这个问题呢?)。果断换google,敲了3个关键词:why checksum tcp,嘿嘿 结果第⼆篇就是我想要的⽂章了
先把链接给⼤家吧:wwwfor2/checksum.html
这篇⽂章主要介绍⼆进制反码求和(the 1's complement sum)与补码求和(the 2's complement sum)的区别,另外还说明了在TCP/IP校验和中使⽤反码求和的优点。
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校验和中使⽤反码求和的⼀些优点:
a. 不依赖系统是⼤端还是⼩端。 即⽆论你是发送⽅计算或者接收⽅检查校验和时,都不需要调⽤htons 或者 ntohs,直接通过上⾯第2节的算法就可以得到正确的结果。这个问题你可以⾃⼰举个例⼦,⽤反码求和时,交换16位数的字节顺序,得到的结果相同,只是字节顺序相应地也交换了;⽽如果使⽤原码或者补码求和,得到的结果可能就不相同!
b. 计算和验证校验和⽐较简单,快速。说实话,这个没怎么看明⽩,感觉在校验和计算⽅⾯,原码或者补码求和反⽽更简单⼀些(从C语⾔⾓度),在校验和验证上⾯,通过⼀样的算法判断结果是否为全 0,确实要⽅便⼀些,所以可能从综合考虑确实反码求和要简便⼀些。另外,IP报⽂在传输过程中,路由器经常只修改TTL字段(减1),此时路由器转发该报⽂时可以直接增加它的校验和,⽽不需要对IP整个⾸部进⾏重新计算。当然,可能从汇编语⾔的⾓度看,反码求和还有很多⾼效的地⽅,这⾥就不在深⼊追究了~~~
结语:本来⼀个不怎么注意的地⽅,深⼊探究⼀下竟然发现这么多东西。学习算法其实没有必要抱着《算法导论》⼀页⼀页地啃(嘿嘿,哥也有⼀本哦),我更喜欢从 TCP/IP协议或LInux内核原理中去探究算法以及实现思想,这样反倒更有趣,⽽且这⾥⾯的⼀些算法和思想相当经典,慢慢体会,必然受益
匪浅!
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论