Fletchers16 校验和适合小数据吗？

使用直接实施维基百科弗莱彻的校验和 https://en.wikipedia.org/wiki/Fletcher's_checksum对于“BCA”和“CAB”以及“BAC”和“ACB”等数据，我们得到相同的校验和。

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

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

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

...我们得到相同的校验和...这是预期的吗？

是的，因为这是可能的。校验和是 16 位（并且永远不会出现 511 种组合：0x..FF, 0xFF..）所以3个24位的字符串肯定会发生冲突。鸽巢原理 https://en.wikipedia.org/wiki/Pigeonhole_principle

Fletcher16 校验和不应该考虑块的顺序吗？

确实如此。只是该算法很容易与选择的相似输入发生冲突。另请参阅汉明距离 https://en.wikipedia.org/wiki/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，但有潜在的改进。

[Edit]

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

详细信息：如果我们抛开%255, sum1 is data[0] + ... + data[count-1]) and sum2 is 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;