Fletcher32校验和算法的正确性

Question

我很难弄清楚 Fletcher checksum algorithm 的 32 位变体的哪个实现。是正确的。维基百科提供了以下优化实现:

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。为了验证这确实是正确的，我试图找到该算法的其他实现:

• An online checksum/hash generator
• C++ implementation in the srecord project
• There's also a JavaScript implementation

所有这些似乎都同意 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

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

Note that the 8-bit Fletcher algorithm gives a 16-bit checksum and the 16-bit algorithm gives a 32-bit checksum.