互联网校验和位移

这几乎肯定是一个非常愚蠢的问题，但由于某种原因，我在互联网校验和计算中遇到了麻烦。所有的算法基本上是这个样子：互联网校验和位移

WORD chksm(WORD *startpos, WORD checklen){ 
ulong sum = 0; 
WORD answer = 0; 

while (checklen > 1) 
{ 
    sum += *startpos++; 
    checklen -= 2; 
} 

if (checklen == 1) 
{ 
    *(BYTE *)(&answer) = *(BYTE *)startpos; 
    sum += answer; 
} 

sum = (sum >> 16) + (sum & 0xffff); 
sum += (sum >> 16); 
answer = ~sum; 

return answer;}

我的一切除了线清晰：

sum += (sum >> 16);

它看起来像之前它增加了前16位的行底部16位，在顶部16位保留全零。如果是这样，那么现在不会总和>> 16现在等于零？如果是这样，为什么那条线呢？

或者我（有可能）今天刚刚完全失智吗？

来源

2009-10-20 Rob Lachlan

太棒了。感谢大家。 – 2009-10-20 22:20:16

你几乎是正确的。

由于进位，高16位可能是1。例如，FFFF + FFFF => 1FFFE，或者FFFF + 1 => 10000。

来源

2009-10-20 22:13:13 DigitalRoss

我认为一个ULONG为32个比特宽，这意味着：

sum = (sum >> 16) + (sum & 0xffff) 
sum += (sum >> 16);

添加顶端sicteen比特和底部sisteen位在一起。然后下一行将前16位的结果相加;由于进位操作，其中可能有一个。

来源

2009-10-20 22:14:18

这是一个补码和定义的一部分。您可以获取任何溢出位并将它们添加回较低的16位。将它们加回来可能会导致进一步的溢出，所以你重复这个操作直到高位全部为零。因此，在概念上它是这样的：

while (sum >> 16 != 0) { 
    sum = (sum >> 16) + (sum & 0xffff); 
}

然而这个循环将只执行最多两次，所以外在的循环是没有必要的。第一次加法后，可能会或可能不会发生溢出，并且进位位以高16位结束。在这种情况下，高16位将为0x0001，并且您将不得不再次添加该位进位。

想象一下在最初的while循环之后总和结尾为0xffffffff的最坏情况。然后添加将按如下步骤进行：

sum = (0xffffffff >> 16) + (0xffffffff & 0xffff) 
    = 0xffff + 0xffff 
    = 0x1fffe 

sum = (0x1fffe >> 16) + (0x1fffe & 0xffff) 
    = 0x1 + 0xfffe 
    = 0xffff

而且有两个补充，我们完成了高16位现在清除。这是最糟糕的情况，因此循环可以展开为两个补充。

（和然后毕竟你拿了最后一笔的补充，导致一个高度混淆的名字：这是补码总和的补码，花了我很长时间来包裹我的头围绕这个，我第一次实现它—特别是一个补数和不涉及~补码操作符。）

来源

2009-10-20 22:17:40

互联网校验和位移

回答

相关问题