Fletcher32校验和算法的正确性

Question

我很难搞清楚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不是由维基百科上执行给定的值.我已经将其缩小到实现操作的数据缓冲区的方式.所有上述非维基百科实现一次操作一个字节,而维基百科实现使用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.

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

Answer 1

根据标准，正确的方法是维基百科提供的 \xe2\x80\x94 除了名称之外：

\n

\n

请注意，8 位 Fletcher 算法提供 16 位校验和，16 位算法提供 32 位校验和。

\n

\n