adler32滚动校验和python计算的差异

Question

在计算运行校验和时需要澄清。在

假设我有这样的数据。在

data = 'helloworld'

假设块大小为5，我需要计算运行校验和。在

^{pr2}$

根据Python文档（Python版本2.7.2）

zlib.adler32(data[, value])

"Computes a Adler-32 checksum of data. (An Adler-32 checksum is almost as reliable as a CRC32 but can be computed much more quickly.) If value is present, it is used as the starting value of the checksum; otherwise, a fixed default value is used. This allows computing a running checksum over the concatenation of several inputs."

但当我提供这样的东西时

>>> zlib.adler32('ellow', zlib.adler32('hello'))
383190072

结果完全不同。在

我尝试创建一个自定义函数来生成rsync算法中定义的滚动校验和。在

def weakchecksum(data):
    a = 1
    b = 0

    for char in data:
        a += (ord(char)) % MOD_VALUE
        b += a % MOD_VALUE



    return (b << 16) | a



def rolling(checksum, removed, added, block_size):
    a = checksum
    b = (a >> 16) & 0xffff
    a &= 0xffff

    a = (a - ord(removed) + ord(added)) % MOD_VALUE
    b = (b - (block_size * ord(removed)) + a) % MOD_VALUE

    return (b << 16) | a

下面是我从运行这些函数得到的值

Weak for hello: 103547413
Rolling for ellow: 105382436
Weak for ellow: 105316900

如您所见，我的滚动校验和实现与python的实现在价值上有很大的不同。在

我在计算滚动校验和时哪里出错了？ 我是否正确地使用了python adler32函数的rolling属性？在

Answer 1

在你的“滚动”方法中

b = (b - (block_size * ord(removed)) + a) % MOD_VALUE

应该是

^{pr2}$

根据维基百科对adler32算法的解释，我们可以看到：

A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
  = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521)

Adler-32(D) = B × 65536 + A

当我们滚动校验和时，我们将得到以下等式：

A1 = (1 + D2 + D3 + … + Dn + Dn+1)(mod 65521)
= (1 + D1 + D2 + D3 + … + Dn) – D1 + Dn+1(mod 65521)
= A – D1 + Dn+1(mod 65521)
B1 = (1 + D2) + (1 + D2 + D3) + … + (1 + D2 + D3 + … + Dn + Dn+1)(mod 65521)
= (1 + D1) – D1 – 1 + (1 + D1 + D2) – D1 + ... +(1 + D1 + D2 + … + Dn) – D1 + (1 + D1 + D2 +      … + Dn + Dn+1) – D1(mod 65521)
= B – nD1 – 1 + A1 + D1 – D1(mod 65521)
= B – nD1 + A1 – 1(mod 65521)

Answer 2

adler32()函数不提供“滚动”。文档正确地使用了单词“running”（而不是“rolling”），这意味着它可以分块计算adler32，而不是一次全部计算。您需要编写自己的代码来计算一个“滚动”adler32值，这将是数据上滑动窗口的adler32。在

Answer 3

顺便说一句，def rolling（）是正确的，至少对于Python来说，模结果的符号有除数的符号。它在其他语言中可能不起作用，例如在C语言中，%结果的符号要么是被除数的符号，要么是由实现定义的。在

您可以通过考虑每一步离模65521的距离有多远，或者用if和65521的加减来替换%或者使用足够大的数据类型让它暂时消失，并计算出在总和上使用%以避免溢出的频率是多么的少。再次，小心负股息的百分比。在