c - Fletcher 16 校验和适合小数据吗？

Question

在 wikipedia Fletcher's checksum 上使用直接实现对于“BCA”和“CAB”以及“BAC”和“ACB”等数据，我们得到相同的校验和。

这是预期的吗？
Fletcher16 校验和不应该考虑 block 的顺序吗？

通过将索引与数据进行“或”操作可以轻松修复该缺陷，如下面的代码所示......

uint16_t fletcher16( uint8_t *data, int count )
{
   uint16_t sum1 = 0;
   uint16_t sum2 = 0;
   int index;

   for( index = 0; index < count; ++index )
   {
      //sum1 = (sum1 + data[index]) % 255; // Original
      sum1 = (sum1 + index | data[index]) % 255; // The "fix"
      sum2 = (sum2 + sum1) % 255;
   }

   return (sum2 << 8) | sum1;
}

Answer 1

... we get the same checksum... Is this expected?

是的，因为这是可能的。校验和是 16 位(并且永远不会出现 511 种组合: 0x..FF 、 0xFF.. )，因此 3 个 24 位字符串肯定会发生冲突。 Pigeonhole principle

Should not the Fletcher16 checksum account for the order of the blocks?

确实如此。只是该算法很容易与选择的相似输入发生冲突。另请参阅Hamming distance

顺便说一句，如果使用字符串的长度或大小(还要检查空字符)，原始算法会给出不同的结果。此外，4 个输入字符串给出了一对不同的结果。

  printf("%x\n", fletcher16("BCA",3)); // 8ec6
  printf("%x\n", fletcher16("CAB",3)); // 8ec6 same
  printf("%x\n", fletcher16("BAC",3)); // 8cc6 
  printf("%x\n", fletcher16("ACB",3)); // 8cc6 same

  printf("%x\n", fletcher16("BCA",4)); // 55c6
  printf("%x\n", fletcher16("CAB",4)); // 55c6 same
  printf("%x\n", fletcher16("BAC",4)); // 53c6
  printf("%x\n", fletcher16("ACB",4)); // 53c6 same

<小时/>

OP 建议的改进还通过在索引中进行“或”运算来削弱校验和，这会忽略每个阶段的选择位。建议进行异或或添加。

<小时/>

轻微尼特:

// return (sum2 << 8) | sum1;
return (1u*sum2 << 8) | sum1;

此更改不会对所有人产生不利影响 int/unsigned大小但避免实现定义的行为时 int/unsigned是 16 位的。最好确保代码不会左移到符号位。

some_int % 255执行有符号余数。在设备上，例如简单的嵌入式设备，无符号余数肯定同样快或更快。 % 255u 不会丢失任何东西，但有潜在的改进。

[编辑]

尽管 OP 对于短字符串有“固定”代码，但它违反了 fletcher16() 的设计参数。 ，即执行速度。

<小时/>

详细信息:如果我们搁置%255 , sum1是 data[0] + ... + data[count-1] )和sum2是 data[0]*(count) + data[0]*(count-1) + ... + data[count-1]*(1) ，很容易创建 1,2,3 等长字符串，其值较低，几乎不会产生 %255操作。

请注意sum2是根据顺序有效创建不同校验和的部分。如果数组元素的总和永远不会达到 255(这发生在 OP 的 4 个测试用例中)，sum1对于任何 2 个仅顺序不同的字符串来说都是相同的。

为了有效地“混合/散列”具有低值的短字符串，需要不同的算法。

也许仅在 count < 8 时使用变体:

sum1 = (sum1 + index + data[index]) % 255;