代码之家 › 专栏 › 技术社区 › Waxhead

Fletchers16校验和是否适用于小数据?

checksum c

Waxhead · 技术社区 · 7 年前

这是预期的吗?
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;
}

1 回复 | 直到 7 年前

chux 7 年前

是的,这是可能的。校验和为16位(511个组合从未出现: 0x..FF , 0xFF.. Pigeonhole principle

Fletcher16校验和不应该说明块的顺序吗?

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建议的改进也通过索引中的或ing来削弱校验和,这忽略了每个阶段的选择位。建议使用xor ing或添加。

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

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) %255 操作。

sum2 sum1 对于仅在顺序上不同的任何2个字符串都是相同的。

可能仅在以下情况下使用变体: count < 8

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

推荐文章

Alex · 配置文件校验和猜测(CRC)

7 年前