增量校验和

我正在寻找校验和算法，其中对于大块数据，校验和等于来自所有较小组件块的校验和的总和。我发现的大部分内容都来自提供此功能的RFC 1624/1141。有没有人有这些校验和技术或类似的经验？增量校验和

2009-07-23 Steve Severance

是否需要专门等于较小块的校验，算术和或者你只是更普遍希望能够从计算大块的校验小块的校验和？ – 2009-07-23 18:08:41

在我看来，校验和问题今天被认为是“基本解决”，常常被解释为“IO约束”，因此从算法性能角度来看并不令人感兴趣。但是，好吧，“IO界”是，我们可以做什么IO？那么，如果我们可以在缓存中IO仍然很热的时候计算散列值，那就很好。 – 2010-09-15 15:21:56

我只使用Adler/Fletcher校验和，其工作方式与您所描述的一样。

加密哈希/校验和实现here有很好的比较。

来源

2009-07-23 18:23:02

要回答Amigable Clark Kent的赏金问题，对于文件识别目的，您可能需要一个加密散列函数，该函数试图保证任何两个给定文件产生相同值的概率极低，而不是校验和通常仅用于错误检测，并可能为两个非常不同的文件提供相同的值。

许多加密散列函数，如MD5和SHA-1，使用Merkle–Damgård construction，在其中有一个计算以数据块压缩成固定大小，然后结合起来，与一个固定的大小的值从以前的块（或第一个块的初始化向量）。因此，他们能够以流模式工作，随着时间的推移逐渐计算。

来源

2010-09-22 14:55:08

如果只是快速组合小块的校验和以获得较大消息的校验和（不一定是通过简单求和），则可以使用CRC类型（或类似）算法来实现。

的CRC-32算法是如此简单：

uint32_t update(uint32_t state, unsigned bit) 
{ 
    if (((state >> 31)^bit) & 1) state = (state << 1)^0x04C11DB7; 
    else       state = (state << 1); 
    return state; 
}

在数学上，状态表示在字段GF2是始终降低模生成多项式的多项式。给定一个新的位b老态转化为新的状态这样

state --> (state * x^1 + b * x^32) mod G

其中G是生成多项式和另外在GF2（XOR）来完成。该校验和是在这个意义上线性可以编写消息M如消息A，B，C，的总和（XOR）...这样

10110010 00000000 00000000 = A = a  00000000 00000000 
    00000000 10010001 00000000 = B = 00000000 b  00000000 
    00000000 00000000 11000101 = C = 00000000 00000000 c 
------------------------------------------------------------- 
= 10110010 10010001 11000101 = M = a  b  c

具有以下属性

  M =   A +   B +   C 
checksum(M) = checksum(A) + checksum(B) + checksum(C)

同样，我的意思是GF2中的+，您可以使用二进制异或实现。

最后，有可能基于checksum(b)和相对B子块b的位置来计算checksum(B)。简单的部分是前导零。前导零不会影响校验和。因此checksum(0000xxxx)与checksum(xxxx)相同。如果你想计算一个零填充（向右 - >尾随零）消息的校验和，给定非填充消息的校验和，这有点复杂。但并不是很复杂：

zero_pad(old_check_sum, number_of_zeros) 
    := (old_check_sum * x^{number_of_zeros}  ) mod G 
    = (old_check_sum * (x^{number_of_zeros} mod G)) mod G

所以，得到一个零填充消息的校验和仅仅是一个与其他一些多项式（x^{number_of_zeros} mod G）乘以“校验多项式”非填充消息的事情，只有依赖关于你想添加的零的数量。您可以在表中预先计算此值，或使用平方和乘法算法快速计算此功率。

来源

2010-09-22 15:03:48 sellibitze

回答

相关问题