论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2007-12-08 15:00 |只看该作者 |倒序浏览

关于 ip 校验和的一个注记

这是我 blog 上一个文章，原文见这里 http://blog.chinaunix.net/u/20/showart_438512.html

前两个星期有网友问群有什么用，这里给出了一个环在计算机科学中的应用例子。

读这个文章需要对反码的数学表示有一定了解，可以产考这个帖子 http://bbs.chinaunix.net/viewthread.php?tid=1026362&page=1&extra=page%3D1#pid7692611

================================================================================================================

校验和的计算和检验

首先我们来描述一下 ip 校验和的计算方法

检验和算法在发送分组之前计算出要放在 ip 首部检验和字段的值。为了计算这个值，现把首部的检验和字段设为 0, 然后计算整个首部（包括选项）的二进制反码的和。把首部作为一个 16 bit 整数数组来处理。让我们把这个计算结果称为 a。因为检验和字段被明确设为 0，所以 a 是除了检验和字段外所有 ip 首部字段的和。a 的二进制反码，用 -a 表示，被放在检验和字段中，发送该分组。

这段话来自 Stevens TCP/IP 详解卷 2，中译本第 186 页

红色一段我认为是错的，不清楚是原文的问题还是翻译的问题。因为在计算校验和的时候，是按 16 位无符号反码计算的，a 本身已经是反码表示，然后说 a 的反码为 -a 是根本不对的。因为是无符号的数，不应该取 -a，而且即使有有符号的数也要判断一下其正负。

我认为正确的说法是把 -a 的 16 bit 反码表示放在检验和字段中。

校验方计算首部，包括检验和位的校验和，如果没有出错，结果应该为 a + (-a) = 16 bit 全 1。.

=======================================================================================================

代码

书本上给出了一个实现，尽管不是 Net/3 中的实现，但用来计算一个正确的校验和是没有问题的。

unsigned short
cksum (struct ip *ip, int len)
{
long sum = 0; /* assume 32 bit long, 16 bit short */
while ( len >1 ) {
sum += *((unsigned short *) ip)++;
if (sum & 8x00000000) /* if high-order bit set, fold */
sum = (sum & 0xFFFF) + (sum>> 16) ;
len -= 2;
}
if ( len ) /* take care of left over byte */
sum += ( unsigned short ) * (unsignedl char *) ip;
while ( sum >> 16)
sum =(sum & 0xFFFF) + (sum>> 16);
return ~sum;

复制代码

书本上说：

这里唯一提高性能之处再在于累积 sum 高 16 位的进位。当循环结束是，累积的进位被加在低 16 bit 上，直到没有其它进位发生。RFC 1071 称此为延迟进位。在没有进位加法指令或检测进位代价很到的机器上，这个技术非常有效。

我们来分析一下，这个"延迟进位"的本质是什么。

16 比特反码就是模 2^16-1 后的结果。如果校验和在 2n 个字节 x_1y_1, x_2,y_2,,,,,x_n,y_n 上进行，
则结果为

(x_1+y_1 2^8 ) + ... + (x_n + y_n 2^8 ） (mod 2^16-1).

如果把双字节 x_iy_i 记为 Z_i,则校验和为:

Z_1 + Z_2 + ... + Z_n  (mod 2^16-1).

一步一步计算，Z_1+Z_2 如果大于等于 2^16，则

Z_1+Z_2 = 2^16 + r (mod 2^16-1).

由于 2^16 = 1 (mod 2^16-1)，所以 Z_1+Z_2 = r+1, 由于 Z_1, 和 Z_2 都小于 2^16，所以这里不会发生第二次进位了。如是重复，直到算出最后结果。但这样每计算一个双字节，就要检查一下是否有进位，如果有，就要执行一个增 1 的运算，消耗比较大。

如果我们允许在充分大的比特位上进行计算，则可以先计算出 Z_1+Z_2+...+Z_n 的和，最后再模 2^16-1。由于取模是同态，现模后加和现加后模是不影响结果的。假定

S=Z_1+Z_2+...+Z_n = Q2^16 + r (mod 2^16-1)

由于 2^16 = 1  (mod 2^16-1) 所以 S= Q+r，但 Q+r 很可能比 2^16-1 大，所以上述过程应该反复进行，知道比 2^16 小为止. 这样可以减少检测和移位加的次数。但在现实中，什么才是充分大呢？

在上面的代码中，采用 32 位的无符号整数进行累加，但如果数据量很大，可能 32 位也放不下，所以在计算时检查最高位，一但最高位为 1，则马上模 2^16-1.

=======================================================================================================

字节序

校验和算法里最有趣的一个问题要数字节序了。比如要校验的字节流为 x_1y_1, x_2y_2, ..., x_ny_n

在小端的机器上，计算的是

S1 = (x_1+ y_1 2^8) + (x_2 + y_2 2^8) + ... + (x_n + y_n 2^8)  (mod 2^16 -1) （mod 2^16-1)

但是在大端机器上计算的却是

S2 = (x_1 2^8 + y_1) + (x_2 2^8 + y_2) + ... + (x_n 2^8 +y_n) (mod 2^16-1). (mod 2^16-1)

S1 和 S2 看上去不大可能一样，这不禁令人生疑，小端发送的数据是如何通过大端校验的？

答案是，S1 和 S2 的确是不同的，但却不影响校验结果！

这是因为如果小端机器计算出来的校验和为 X + Y 2^8，则大端计算出来的校验和为 X 2^8 + Y，放到 16 位里都是双字节 XY.

事实上

S1 = (x_1+...+x_n) + (y_1+...+y_n) 2^8  (mod 2^16-1)
S2 = (x_1+...+x_n)2^8 + (y_1+...+y_n) (mod 2^16-1)

令 x_1 + ... + x_n  (mod 2^16-1) 的结果为 X
y_1 + ... + y_n  (mod 2^16-1) 的结果为 Y

则  S1= X+Y2^8, 而 S2=Y+X*2^8。

很可惜，X, Y 可以是 16 位的，所以这里不是最后结果，要把 X, Y 分别劈开成两个字节，然后进行讨论。这就有点罗嗦了。

如果采用同构的方法，就能很容易说明这个问题，一个双字节 x_1y_1 在小端看来，是

x_1 + y_1 2^8

在大端看来，是
x_1 2^8 + y_1

我们在小端解释与大端解释之间建立一个映射

f(x_1 + y_1 2^8) = x_1 2^8 +y

能看出 f 的一个表达式吗？它是

f(X) = X 2^8  (mod 2^16-1)

我把它称为换位映射，容易验证：

f(x_1+y_1 2^8)= (x_1 + y_1 2^8) 2^8 (mod 2^16 -1)
            = x_1 2^8 + y_1 2^16  (mod 2^16 -1)
            = x_1 2^8 + y_1

由于 (2^8, 2^16-1) = 1, 所以 f 是模 2^16-1 剩余类环上的自同构。

这样，若字节流为 x_1y_1, x_2y_2, ..., x_ny_n

则小端的校验和为

S1 = x_1y_1 + x_2y_2 +...+ x_ny_n  (mod 2^16-1)
= x_1+y_1 2^8 + ... + x_n y_n 2^8

而大端的校验和为

S2 = x_1y_1 + x_2y_2 +...+x_ny_n (mod 2^16-1)
= x_1 2^8 + y_1 + ... + x_n 2^8 + y_n  (mod 2^16-1)
= f(x_1+ 2^8 y_1) + ... + f(x_n + 2^8 y_n) (mod 2^16-1)
= f(x_1+2^8y +...+ x_n 2^8 + y_n)
= f(S1)

所以，若 S1 = X + 2^8 Y, 则 S2 = f(S1) = X 2^8 + Y, 写成双字节都是 XY.

在实际进行校验的时候，并不直接计算 S1 或 S2，而是检查最后结果是否为 16 个 1。比如小端发送

x_1y_1,..., x_ny_n |  -S1,

x_1y_1,..., x_ny_n 是数据，而 S1 是校验

大端检查时计算

f(x_1y_1+...+ x_ny_n + (-S_1) ) = f(x_1y_1+...+ x_ny_n) + (-f(S1)) = S2+(-S2) = 16 个 1.

[ 本帖最后由 win_hate 于 2007-12-8 15:16 编辑 ]