V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  程序员

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

  •  
  •   amiwrong123 · 186 天前 · 1992 次点击
    这是一个创建于 186 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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

    15 条回复    2021-11-22 00:32:45 +08:00
    nuk
        1
    nuk  
       186 天前
    啥叠加啊,不是求和么,求和就不会是全 1 了啊,2 是考虑到高 16 和低 16 相加溢出的情况
    crab
        2
    crab  
       186 天前
    00001000 (数据 1 )
    00000100 (数据 2 )
    00001100 (相加)
    11110011(取反 检验和)
    ------------------

    00001000 (数据 1 )
    00000100 (数据 2 )
    11110011(上面的检验和)
    11111111 (相加)
    2i2Re2PLMaDnghL
        3
    2i2Re2PLMaDnghL  
       186 天前
    sum = ~X + ~Y + 1111
    check = ~X + ~Y + ~sum
    check = ?
    这简单的数学不是很清晰的吗?
    至于高 4b 加到低 4b 上去,其实是在模 15 空间内做计算
    qbqbqbqb
        4
    qbqbqbqb  
       186 天前
    所谓的“反码”(英文名是 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
        5
    qbqbqbqb  
       186 天前
    @qbqbqbqb 知道了上面这些之后,不难发现为什么先取反和后取反都是正确的:
    如果已知其它数字要求校验和,假设其它数字为 x1,x2,...xn ,校验和为 c ,则根据规则应该满足:
    x1+x2+...+xn+c=0 (注意这里加号"+"表示反码加法,不是普通加法!)
    计算校验和 c 就有两种方式:
    c=-x1-x2-...-xn (相当于每个数先取反) 或者 c=-(x1+x2+...+xn) (相当于最后取反)
    这里关键点就是:“反码运算” 中 “取反”相当于“加负号”

    同时也可以发现,接收端其实是没必要取反的。
    qbqbqbqb
        6
    qbqbqbqb  
       186 天前
    @qbqbqbqb 这里唯一一个有问题的地方就是,当校验和为 0 的时候不同的算法可能算出 0 或者 0xffff 两种不同的结果。这两个数字在反码运算里是等价的,但是网络协议上可能有特殊的规定。网络协议里 TCP 没有特别的要求,而 UDP 要求校验和字段算出 0 的时候必须填入 0xffff (全 0 校验和在 UDP 里表示发送端没有计算校验和)。
    amiwrong123
        7
    amiwrong123  
    OP
       185 天前
    @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
        8
    amiwrong123  
    OP
       185 天前
    @amiwrong123 #7
    好像理解了。。

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

    剩下的我接着理解
    😂
    amiwrong123
        9
    amiwrong123  
    OP
       185 天前
    @qbqbqbqb #4
    普通的数 的加法里,溢出后,溢出的那一位 刚好就代表 2^w ,所以普通的数 加起来 不用特殊操作。

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

    总之,两个反码相加,可能会得到 0001 xyza ,而“溢出高位叠加到低位”就是把这个 0001 ,给加进来。
    amiwrong123
        10
    amiwrong123  
    OP
       185 天前
    @qbqbqbqb #4
    ![]( https://s3.bmp.ovh/imgs/2021/11/a1701aa01a429c66.jpg)
    我好像通过这个懂了,为什么 要“溢出高位叠加到低位”。但我好像还是没通过你的这句话,来 get 到为什么“溢出高位叠加到低位”。
    哎,我太笨了
    总之,不管是再加 1 ,还是“溢出高位叠加到低位”,都是为了 保证 反码 a+反码 b = 反码 c (因为 a+b=c )
    amiwrong123
        11
    amiwrong123  
    OP
       185 天前
    @qbqbqbqb #5
    > x1+x2+...+xn+c=0

    本贴中第一个图中,发送方的数据是 1000 0100 ,最后算出来的校验和为 0011 ,
    1000 + 0100 + 0011 = 1111. 为啥我这算出来是 全 1 呢😂,是我哪里理解错了
    😂
    qbqbqbqb
        12
    qbqbqbqb  
       185 天前
    @amiwrong123 反码里全 0 表示“+0”,全 1 表示“-0”,数学上可以认为是等价的,是 0 这个数的不同的表示方法。
    qbqbqbqb
        13
    qbqbqbqb  
       185 天前
    @amiwrong123 实际计算中确实是全 1 ,因为计算的过程中不会故意对 2^w-1 取模。
    amiwrong123
        14
    amiwrong123  
    OP
       182 天前
    @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
        15
    amiwrong123  
    OP
       182 天前
    @qbqbqbqb
    又或者根本不该加 sum += (sum>>16);
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2868 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 12:15 · PVG 20:15 · LAX 05:15 · JFK 08:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.