关于 ip 校验和的一个注记
校验和的计算和检验
首先我们来描述一下 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^n-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.
在实际的代码中，计算校验和检查校验调用的是同一个函数，所以检查校验时除了累加，最后还有一个取反。因此实际的校验结果是 16 个 0 而不是 16 个 1。 但这个会增加讨论的复杂性，因此在上面我们假设校验时只累加，不取反。
