Fletcher32校验和算法的正确性
我很难弄清楚Fletcher校验和算法 32位变体的实现是正确的。Wikipedia提供了以下优化实现：
uint32_t fletcher32( uint16_t const *data, size_t words ) {
uint32_t sum1 = 0xffff, sum2 = 0xffff;
size_t tlen;
while (words) {
tlen = words >= 359 ? 359 : words;
words -= tlen;
do {
sum2 += sum1 += *data++;
} while (--tlen);
sum1 = (sum1 & 0xffff) + (sum1 >> 16);
sum2 = (sum2 & 0xffff) + (sum2 >> 16);
}
/* Second reduction step to reduce sums to 16 bits */
sum1 = (sum1 & 0xffff) + (sum1 >> 16);
sum2 = (sum2 & 0xffff) + (sum2 >> 16);
return sum2 << 16 | sum1;
}此外，我还修改了维基百科文章中的非优化16位示例，以计算32位校验和：
uint32_t naive_fletcher32(uint16_t *data, int words) {
uint32_t sum1 = 0;
uint32_t sum2 = 0;
int index;
for( index = 0; index < words; ++index ) {
sum1 = (sum1 + data[index]) % 0xffff;
sum2 = (sum2 + sum1) % 0xffff;
}
return (sum2 << 16) | sum1;
}这两种实现产生相同的结果，例如用于字符串0x56502d2a的abcdef。为了验证这确实是正确的，我试图找到该算法的其他实现：
- 在线校验和/散列生成器
- srecord项目中的C++实现
- 还有一个JavaScript实现
所有这些似乎都同意abcdef的校验和是0x8180255，而不是维基百科上的实现所提供的值。我已经将范围缩小到实现的数据缓冲区是如何操作的。所有上述非Wikipedia实现一次操作一个字节，而Wikipedia实现使用16位字计算校验和。如果我修改上面的“朴素”维基百科实现来代替每字节操作，它的内容如下：
uint32_t naive_fletcher32_per_byte(uint8_t *data, int words) {
uint32_t sum1 = 0;
uint32_t sum2 = 0;
int index;
for( index = 0; index < words; ++index ) {
sum1 = (sum1 + data[index]) % 0xffff;
sum2 = (sum2 + sum1) % 0xffff;
}
return (sum2 << 16) | sum1;
}唯一能改变的就是签名，真的。因此，修改后的朴素实现和上面提到的实现(维基百科除外)一致认为，abcdef的校验和确实是0x8180255。
我现在的问题是:哪一个是正确的？
回答 5
Stack Overflow用户
发布于 2016-10-26 19:44:27
根据标准的说法，正确的方法是维基百科提供的方法--除了名称：
注意，8位弗莱彻算法给出了16位校验和，16位算法给出了32位校验和。
Stack Overflow用户
发布于 2017-10-03 16:58:54
这些是测试向量，它们与16位和32位校验和的两种不同实现交叉检查：
8-bit implementation (16-bit checksum)
"abcde" -> 51440 (0xC8F0)
"abcdef" -> 8279 (0x2057)
"abcdefgh" -> 1575 (0x0627)
16-bit implementation (32-bit checksum)
"abcde" -> 4031760169 (0xF04FC729)
"abcdef" -> 1448095018 (0x56502D2A)
"abcdefgh" -> 3957429649 (0xEBE19591)Stack Overflow用户
发布于 2018-02-17 02:35:40
TCP替代校验和选项描述了1990年3月与TCP：RFC 1146一起使用的弗莱彻校验和算法。
讨论了给出16位校验和的8位Fletcher算法和给出32位校验和的16位算法。
8位弗莱彻校验和算法是在一组数据八进制(通过DN调用它们为D1 )上计算的，方法是维护两个内容最初为零的无符号1 s-补8位累加器A和B，并执行以下循环(i范围从1到N)：
A := A + D[i]
B := B + A16位弗莱彻校验和算法与8位校验和算法进行的方式完全相同，但A、B和Di是16位量。有必要(与标准的TCP校验和算法一样)在包含奇数八进制的数据报上加上一个零八位数。
这与维基百科算法是一致的。简单的测试程序证实了引用的结果：
#include <stdio.h>
#include <string.h>
#include <stdint.h> // for uint32_t
uint32_t fletcher32_1(const uint16_t *data, size_t len)
{
uint32_t c0, c1;
unsigned int i;
for (c0 = c1 = 0; len >= 360; len -= 360) {
for (i = 0; i < 360; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 65535;
c1 = c1 % 65535;
}
for (i = 0; i < len; ++i) {
c0 = c0 + *data++;
c1 = c1 + c0;
}
c0 = c0 % 65535;
c1 = c1 % 65535;
return (c1 << 16 | c0);
}
uint32_t fletcher32_2(const uint16_t *data, size_t l)
{
uint32_t sum1 = 0xffff, sum2 = 0xffff;
while (l) {
unsigned tlen = l > 359 ? 359 : l;
l -= tlen;
do {
sum2 += sum1 += *data++;
} while (--tlen);
sum1 = (sum1 & 0xffff) + (sum1 >> 16);
sum2 = (sum2 & 0xffff) + (sum2 >> 16);
}
/* Second reduction step to reduce sums to 16 bits */
sum1 = (sum1 & 0xffff) + (sum1 >> 16);
sum2 = (sum2 & 0xffff) + (sum2 >> 16);
return (sum2 << 16) | sum1;
}
int main()
{
char *str1 = "abcde";
char *str2 = "abcdef";
size_t len1 = (strlen(str1)+1) / 2; // '\0' will be used for padding
size_t len2 = (strlen(str2)+1) / 2; //
uint32_t f1 = fletcher32_1(str1, len1);
uint32_t f2 = fletcher32_2(str1, len1);
printf("%u %X \n", f1,f1);
printf("%u %X \n\n", f2,f2);
f1 = fletcher32_1(str2, len2);
f2 = fletcher32_2(str2, len2);
printf("%u %X \n",f1,f1);
printf("%u %X \n",f2,f2);
return 0;
}输出：
4031760169 F04FC729
4031760169 F04FC729
1448095018 56502D2A
1448095018 56502D2A https://stackoverflow.com/questions/40270450
复制相似问题
腾讯云开发者
