c - 弗莱彻校验和 : Is a modulo-255 sum really the same as a one's complement sum

Question

我的问题的简短背景:我正在从事一个小型业余项目，该项目使用微 Controller 通过 UART 与 PC 进行通信。现在我正在使用 COBS 字节填充，其中包含 0x00 数据包定界符字节和一个简单的 1 字节校验和，它可以是二进制补码运行总和或一个补码总和。我的补码校验和实现与 Internet checksum 非常相似(第 7 页。有趣的部分如下所示)

//  Fold 32-bit sum to 16 bits //
while (sum>>16)
    sum = (sum & 0xffff) + (sum >> 16);

checksum = ~sum; 

几天前我发现了 Fletcher 校验和:
Fletcher article
Fletcher implementation
Fletcher Wikipedia

来自 Fletcher Wiki 页面的简短代码片段:

for( index = 0; index < count; ++index )
{
    sum1 = (sum1 + data[index]) % 255;
    sum2 = (sum2 + sum1) % 255;
}

return (sum2 << 8) | sum1;

我的问题:在上面的两篇文章中，他们都说 Fletcher 使用“one's complement [mod(255)] checksums”，就好像 mod-255 和 one's complement sum 是一样的。这是真的吗？

1. 对我来说有意义的是，与上面的补码加法器相比，使补码校验和更优的进位位在 mod-255 和中的工作方式几乎相同。但是对于 mod-255 和，您永远无法获得值 0xFF (-0)，只能获得 0x00 (+0)？
2. 我猜 mod-operator 比较慢(尽管它是线性的，所以您可以等待 mod- 计算直到求和结束)。
3. 一个很好的特性(当使用 COBS 时)是 mod-255 永远不会产生 0x00 校验字节，因为 mod-255 总和永远不会是 0xFF(尽管即使在上面的补码加法器中也很容易修复)。

非常感谢您的宝贵时间!

亲切的问候/亨里克

Answer 1

不，模 255 不等于一个补码。我认为这里的混淆是 Fletcher 的校验和同时利用模 255 加法 和 将一个的补码作为最后一步。此外，慢得多的模运算符可能只是模拟它可能在 asm 中使用的 ADC 运算符。

One's Complement 是位的反转(按位 NOT)，通常作为计算的最终操作完成，称为“取 one's complement”。这样做是为了优化验证过程并将正确的结果强制为 -0(或二进制的 1111 1111)。它仅在使用一个补码算法的低级硬件上真正有用。现在大多数其他人都使用二进制补码，因此要实现相同的效果，除了位反转之外还必须减一。

模 255 不同。意图可能是模拟“Add with Carry”指令。如果 Fletcher-16 是用 ADC 指令在汇编中实现的，我不会感到惊讶。

基本上，不仅仅是忽略溢出，它会在设置时添加进位。模 255 在这里达到相同的效果。通常这样做是为了以极低的成本提高校验和的错误检测质量。