IP数据包的校验和算法

IP数据包的校验和算法

在发送数据时，为了计算数IP据报的校验和。应该按如下步骤：
(1) 把IP数据报的校验和字段置为0。
(2) 把首部看成以16位为单位的数字组成，依次进行二进制反码求和
(3) 把得到的结果存入校验和字段中。

在接收数据时，计算数据报的校验和相对简单，按如下步骤：
（1）把首部看成以16位为单位的数字组成，依次进行二进制反码求和，包括校验和字段。
（2）检查计算出的校验和的结果是否等于零。
（3）如果等于零，说明被整除，校验是和正确。否则，校验和就是错误的，协议栈要抛弃这个数据包。


Linux 2.6内核中的校验算法，使用汇编语言编写的，显然效率要高些
/usr/src/linux-2.6.23/include/asm-i386/checksum.h

static inline __sum16 ip_fast_csum(const void *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"
    : "=r" (sum), "=r" (iph), "=r" (ihl)
    : "1" (iph), "2" (ihl)
    : "memory");
    return (__force __sum16)sum;
}

(1) 将IP头部(包括可选项)以32位为单位进行进位加法运算
(2) 将sum的低16位和高16位相加
(3) 取反

1b -- 1 before

在这个函数中，第一个参数显然就是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;
}



让我们假设一个IP头数据，来解cksum的惑

IP头数据:

01000101                             /*ver_hlen*/
00000000                             /*tos*/
00000000 00000010                    /*len*/
00000000 00000000                    /*id*/
00000000 00000000                    /*offset*/
00000100                             /*ttl*/
00010001                             /*type*/
00000000 00000000                    /*cksum(0)*/
01111111 00000000 00000000 00000001 -/*sip*/
01111111 00000000 00000000 00000001 -/*dip*/

运算过程(注意是大端格式加):
for(sum = 0; nword > 0; nword--)
    sum += *buf++;

-01000101 00000000
-00000000 00000010
---------------------
-01000101 00000010
-00000000 00000000
---------------------
-01000101 00000010
-00000000 00000000
---------------------
-01000101 00000010
-00000100 00010001
---------------------
-01001001 00010011
-00000000 00000000
---------------------
-01001001 00010011
-01111111 00000000
---------------------
-11001000 00010011
-00000000 00000001
---------------------
-11001000 00010100
-01111111 00000000
---------------------
101000111 00010100
-00000000 00000001
---------------------
101000111 00010101            sum

                
sum = (sum>>16) + (sum&0xffff);
00000000 00000001            (sum>>16)
01000111 00010101            (sum&0xffff)
---------------------
01000111 00010110

sum += (sum>>16);
01000111 00010110
00000000 00000000            (sum>>16)
---------------------
01000111 00010110            sum

~sum
10111000 11101001            cksum  
      
说白了就是循环加，然后在取反!



对方机器调用checksum()计算校验和，如果校验和为0表明IP包传输正确
-----------------------------------------------------------
01000101                             /*ver_hlen*/
00000000                             /*tos*/
00000000 00000010                    /*len*/
00000000 00000000                    /*id*/
00000000 00000000                    /*offset*/
00000100                             /*ttl*/
00010001                             /*type*/
10111000 11101001                    /*cksum(0)*/
01111111 00000000 00000000 00000001 /*sip*/
01111111 00000000 00000000 00000001 /*dip*/

-01000101 00000000
-00000000 00000010
---------------------
-01000101 00000010
-00000000 00000000
---------------------
-01000101 00000010
-00000000 00000000
---------------------
-01000101 00000010
-00000100 00010001
---------------------
-01001001 00010011
-10111000 11101001
---------------------
100000001 11111100
-01111111 00000000
---------------------
110000000 11111100
-00000000 00000001
---------------------
110000000 11111101
-01111111 00000000
---------------------
111111111 11111101
-00000000 00000001
---------------------
111111111 11111110            sum

sum = (sum>>16) + (sum&0xffff);
00000000 00000001            (sum>>16)
11111111 11111110            (sum&0xffff)
----------------------
11111111 11111111

sum += (sum>>16);
11111111 11111111
00000000 00000000            (sum>>16)
----------------------
11111111 11111111

~sum
00000000 00000000