C语言 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;
}

这两种实现产生相同的结果，例如字符串abcdef对应0x56502d2a。为了验证这确实是正确的，我试图找到该算法的其他实现:

一个在线校验和/哈希生成器
srecord项目中的c++实现
还有一个JavaScript实现

所有这些似乎都同意abcdef的校验和是0x8180255，而不是维基百科上实现给出的值。我已经将其缩小到实现如何操作数据缓冲区。上述所有非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。

我现在的问题是:哪个是正确的?

根据标准，正确的方法是Wikipedia提供的方法-除了名称:

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

在HideFromKGB回答中引用的标准中，算法是微不足道的:8位版本只使用8位累加器("ints")，产生8位结果A和B, 16位版本使用16位"ints"，产生16位结果A和B。

值得注意的是，维基百科所称的"32位fletcher";实际上是"16位fletcher"。名称中的位数在标准中指的是每个D[i]和每个A和B中的位数，但在维基百科上它指的是"堆叠结果"中的位数，即在A<<16 | B中为32位结果。

我没有实现这个，但也许这可以解释差异。我倾向于认为你的解释(实现)是正确的。

的被害者。还要注意，有必要将data用零填充到适当的字节数。

这些是测试向量，它们在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)

TCP替代校验和选项描述了TCP: RFC 1146日期为1990年3月使用的Fletcher校验和算法。

讨论了给出16位校验和的8位Fletcher算法和给出32位校验和的16位算法。

8位弗莱彻校验和算法是在一个序列上计算的的数据字节(称它们为D[1]到D[N])无符号1补位8位累加器A和B，其内容为初始值为0，并在I的范围内执行以下循环1到N:

       A := A + D[i]
       B := B + A

16位弗莱彻校验和算法以完全相同的方式进行方式为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; //  '' 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 nn",  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

我的回答是关注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。正好是2乘以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

相关内容

最新更新

热门标签：