TCP 检验和原理不太懂？求大佬指点

[amiwrong123]

1. 就是有点不明白，为啥这么弄了以后，接收方最后算出来就会全是 1 ？（当无比特差错时）（居然最后还有个叠加操作）

    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;
    }

1. 上面这个校验和算法，是先求和，最后取反码，好像也可以（因为算出来是一样的）？这是什么原理（因为上图是 先取反码，再求和，最后叠加。难道这三步 任意换顺序都可以吗）
2. sum += (sum>>16);这一步看起来是多余的吧？因为上一句就把 前 16 比特 和 后 16 比特 累加了啊？

参考文章：

https://www.cnblogs.com/zxiner/p/7203192.html

http://t.zoukankan.com/pengkunfan-p-3967461.html

[nuk]

啥叠加啊，不是求和么，求和就不会是全 1 了啊，2 是考虑到高 16 和低 16 相加溢出的情况

[crab]

00001000 （数据 1 ）
00000100 （数据 2 ）
00001100 （相加）
11110011(取反 检验和)
------------------

00001000 （数据 1 ）
00000100 （数据 2 ）
11110011(上面的检验和)
11111111 （相加）

[2i2Re2PLMaDnghL]

sum = ~X + ~Y + 1111
check = ~X + ~Y + ~sum
check = ?
这简单的数学不是很清晰的吗？
至于高 4b 加到低 4b 上去，其实是在模 15 空间内做计算

[qbqbqbqb]

所谓的“反码”（英文名是 ones' complement ）是一种负数的表示方式，定义上是这样的：
-x = [11..11]2-x = “x 取反”
其中[11..11]2 表示二进制数“w 个 1”

根据上面的定义，不难发现反码加法实际上就是关于 2^w-1 取模的加法。
这样就不难理解为什么计算反码加法要“溢出高位叠加到低位”了：因为平常编程里的普通整数加法溢出时是关于 2^w 取模的，而反码加法是关于 2^w-1 取模，普通加法里低位每向高位溢出一次两者的差值就增加 1 ，所以这样叠加一下算出来的数值恰好是正确的。
原则上应该每加一次就叠加一次，但是因为 IP 头和 TCP 头的字节数不是太长，溢出总数不可能达到 2^16 ，所以说无论先加再叠加还是每加一次就叠加一次，得到的结果没有什么差别。

理解了反码的原理以后，校验和算法就可以一句话描述：每 16 比特当成一个整数，全部相加（包括校验和本身），再除以 65535 （即 2^16-1 ）余数应该为 0.

[qbqbqbqb]

@qbqbqbqb 知道了上面这些之后，不难发现为什么先取反和后取反都是正确的：
如果已知其它数字要求校验和，假设其它数字为 x1,x2,...xn ，校验和为 c ，则根据规则应该满足：
x1+x2+...+xn+c=0 （注意这里加号"+"表示反码加法，不是普通加法！）
计算校验和 c 就有两种方式：
c=-x1-x2-...-xn （相当于每个数先取反） 或者 c=-(x1+x2+...+xn) （相当于最后取反）
这里关键点就是：“反码运算” 中 “取反”相当于“加负号”

同时也可以发现，接收端其实是没必要取反的。

[qbqbqbqb]

@qbqbqbqb 这里唯一一个有问题的地方就是，当校验和为 0 的时候不同的算法可能算出 0 或者 0xffff 两种不同的结果。这两个数字在反码运算里是等价的，但是网络协议上可能有特殊的规定。网络协议里 TCP 没有特别的要求，而 UDP 要求校验和字段算出 0 的时候必须填入 0xffff （全 0 校验和在 UDP 里表示发送端没有计算校验和）。

[amiwrong123]

@qbqbqbqb #4
正数的话，原码和反码相同。
负数的话，反码是 把负数绝对值的原码，按位取反，再把符号位置为 1 。这样，负数的反码 和 负数绝对值的反码（负数绝对值就是正数，正数的话，原码和反码相同）恰好各个位都是 相反的。

从上可以得知（假设为 4 位 bit 的数）(|负数|是这个负数的绝对值)：
负数的反码 + |负数|的反码 = 1111

所以就得出了 ~x = [11..11]2-x = “x 取反”
因为 负数的反码 = 1111 - |负数|的反码

然后你说的“反码加法”就是指两个反码相加是吧。
但我还是没懂“反码加法实际上就是关于 2^w-1 取模的加法”这句话。

比如
负数 a 的反码 = 1111 - |负数 a|的反码
负数 b 的反码 = 1111 - |负数 b|的反码

那么
负数 a 的反码 + 负数 b 的反码 = 1111 + 1111 - |负数 a|的反码 - |负数 b|的反码

但是怎么理解成“关于 2^w-1 取模”啊

有点笨，求指点迷津啦

[amiwrong123]

@amiwrong123 #7
好像理解了。。

0b10000 - 6 = 2 那就是对 8 取模
0b1111 - 6 = 1 那就是对 7 取模

剩下的我接着理解
😂

[amiwrong123]

@qbqbqbqb #4
普通的数 的加法里，溢出后，溢出的那一位 刚好就代表 2^w ，所以普通的数 加起来 不用特殊操作。

反码 的加法里，溢出后，溢出的那一位也是就代表 2^w 的，但反码的范围是 [0000-0111 ，1000-1110] （前者 正数，后者负数，-0 么有算在里面），所以就 应该再把溢出那一位 1 加到后面（但这里我 无法正确表述这个道理，希望大佬解释下）

总之，两个反码相加，可能会得到 0001 xyza ，而“溢出高位叠加到低位”就是把这个 0001 ，给加进来。

[amiwrong123]

@qbqbqbqb #4
我好像通过这个懂了，为什么 要“溢出高位叠加到低位”。但我好像还是没通过你的这句话，来 get 到为什么“溢出高位叠加到低位”。
哎，我太笨了
总之，不管是再加 1 ，还是“溢出高位叠加到低位”，都是为了 保证 反码 a+反码 b = 反码 c （因为 a+b=c ）

[amiwrong123]

@qbqbqbqb #5
> x1+x2+...+xn+c=0

本贴中第一个图中，发送方的数据是 1000 0100 ，最后算出来的校验和为 0011 ，
1000 + 0100 + 0011 = 1111. 为啥我这算出来是 全 1 呢😂，是我哪里理解错了
😂

[qbqbqbqb]

@amiwrong123 反码里全 0 表示“+0”，全 1 表示“-0”，数学上可以认为是等价的，是 0 这个数的不同的表示方法。

[qbqbqbqb]

@amiwrong123 实际计算中确实是全 1 ，因为计算的过程中不会故意对 2^w-1 取模。

[amiwrong123]

@qbqbqbqb
大佬，再问一下这个算法：
sum = (sum>>16) + (sum&0xffff);
sum += (sum>>16);

1. 这两句，我理解后面这句话 sum += (sum>>16);是有必要的，因为前面这句 sum = (sum>>16) + (sum&0xffff);可能又发生了溢出，所以针对这种可能出现的情况，我们需要再做一次 sum += (sum>>16);？是这样理解的吗

2. 但为什么第二句不是 sum = (sum>>16) + (sum&0xffff)呢？

[amiwrong123]

@qbqbqbqb
又或者根本不该加 sum += (sum>>16);