logo标签列表

Fletcher32校验算法的正确性

calgorithmchecksumcorrectness
8

我很难确定32位变量的Fletcher校验算法的正确实现。维基百科提供了以下优化的实现：

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

这两种实现都会产生相同的结果，例如对于字符串abcdef，结果为0x56502d2a。为了验证这一点，我尝试找到算法的其他实现： 所有这些实现似乎都同意abcdef的校验和是0x8180255，而不是Wikipedia上给出的值。我将这归结于实现所操作的数据缓冲区。以上所有非Wikipedia的实现每次都只处理一个字节，而Wikipedia的实现使用16位字来计算校验和。如果我修改上面“朴素”的Wikipedia实现以按字节操作，则代码如下：
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。
我的问题是：哪一个是正确的？
在 naive_fletcher 中，循环中的 % 0xffff 不是必需的。你可以在循环之后执行。 - Paul Ogilvie
@PaulOgilvie：只要没有溢出，循环中的％0xffff就不是必需的。 - greybeard
@老程序员，如果发生溢出会怎么样？那些永远不会被使用的位将从寄存器中掉落。 - Paul Ogilvie
@老程序员，我不明白你的意思。在溢出时，低位上不会添加任何内容。16位的高位不会被使用。 - Paul Ogilvie
2
@PaulOgilvie：0x10000％0xffff是1，而不是0：必须考虑进位。 - greybeard
显示剩余2条评论
5个回答
2

根据标准，正确的方法是维基百科提供的方法——除了名称:

请注意，8位Fletcher算法给出16位校验和，16位算法给出32位校验和。

1
在HideFromKGB的回答中引用的标准中，算法很简单：8位版本仅使用8位累加器（“int”），生成8位结果A和B，而16位版本使用16位“int”，生成16位结果A和B。
应该注意的是，维基百科所谓的“32位Fletcher”实际上是“16位Fletcher”。名称中的位数指的是标准中每个D[i]和每个A和B中的位数，但在维基百科中，它指的是“堆叠结果”中的位数，即32位结果的A<<16 | B。
我没有实现这个，但也许这可以解释差异。我倾向于说你的解释（实现）是正确的。
请注意：还需要用零填充data到适当的字节数。
谢谢回答！对我来说，这仍然让我想到为什么我找到的所有其他实现都不符合这个标准。也就是说，一个没有人实现的标准有点毫无意义，但是再说一遍，我也没有在TCP中看到实现，也许我应该去检查一下。 - fresskoma
1
我在您提供的第一个参考资料中留下了澄清请求。第二个和第三个似乎相当非官方，并且没有提供澄清请求选项。在您提供的第三个参考资料中，我没有找到Fletcher或其RFC的参考。 - Paul Ogilvie
1
TCP备用校验和选项介绍了用于TCP的Fletcher校验和算法: RFC 1146，日期为1990年3月。
讨论了给出16位校验和的8位Fletcher算法和给出32位校验和的16位算法。
8位Fletcher校验和算法通过维护两个初始值为零的无符号一补数8位累加器A和B来计算数据八位组（称之为D[1]到D[N]）的序列。执行以下循环，其中i从1到N：
       A := A + D[i]
       B := B + A

16位Fletcher校验算法的过程与8位校验算法完全相同，除了A、B和D[i]都是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
1
然而，fletcher32_1和fletcher32_2并不总是生成相同的结果（请参见Sven的分析）。例如，fletcher32_1（0,0）给出0x0，而fletcher32_2（0,0）= 0xffffffffffffffff。通常，与参考资料相比已经被修改的维基百科上发现的任何代码都应视为非常可疑的。 - Hans Olsson
1
这些是测试向量，用于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)
1
我的答案关注于 s = (s & 0xffff) + (s >> 16) 的正确性。 显然，这是用来替换模运算的。现在模运算的主要问题是需要执行除法运算。技巧在于不要执行除法并估计 floor(s / 65535)。因此，我们不是计算 s - floor(s/65535)*65535（与模运算相同），而是计算 s - floor(s/65536)*65535。这显然不等同于执行模运算。但它足以快速减小 s 的大小。

现在我们有：

  s - floor(s / 65536) * 65535
= s - (s >> 16) * 65535
= s - (s >> 16) * (65536 - 1)
= s - (s >> 16) * 65536 + (s >> 16)
= (s & 0xffff) + (s >> 16)

由于(s & 0xffff) + (s >> 16)并不等同于取模运算，因此仅使用此公式是不够的。如果s == 65535，那么s % 65535将产生零。然而，前面的公式会得到65535。因此，这里发布的经过优化的维基百科实现显然是错误的！需要更改最后3行为

        /* Second reduction step to reduce sums to 16 bits */
        sum1 = (sum1 & 0xffff) + (sum1 >> 16);
        sum2 = (sum2 & 0xffff) + (sum2 >> 16);
        if (sum1 >= 65535) { sum1 -= 65535; }
        if (sum2 >= 65535) { sum2 -= 65535; }
        return (sum2 << 16) | sum1;

值得注意的是，我再也找不到维基百科页面上优化的实现了（2020年2月）。
补充说明：假设s等于最大的32位无符号值，即0xFFFF_FFFF。那么公式(s & 0xffff) + (s >> 16)将产生0x1FFFE。这恰好是65535的两倍。因此，校正步骤if (s >= 65535) { s -= 65535; }将无法工作，因为它最多只会减去65535。因此，我们希望在循环中严格保持sum1和sum2小于0xFFFF_FFFF。然后，该公式最多产生2*65535-1，并且校正步骤将起作用。下面这个简单的Python程序确定，在360次迭代后，sum2将变得太大。因此，一次处理最多359个16位字是完全正确的。
s1 = 0x1FFFD
s2 = 0x1FFFD
for i in range(1,1000):
    s1 += 0xFFFF
    s2 += s1
    if s2 >= 0xFFFFFFFF:
        print(i)
        break
在进行更正之后，优化版本是否更快似乎不太清楚。（这可能取决于硬件。）请注意，此更改仅涉及循环外的优化，对吗？ - Hans Olsson
1
我没有计算过359是否是正确的边界。除此之外，循环是正确的。我的更正不需要在循环内部进行，只需要在最后一次进行即可。 - Sven
我添加了对数字359的说明。 - Sven
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接