Adler32滚动校验和计算的差异 - Python

StackOverflow https://stackoverflow.com//questions/9699315

  •  13-12-2019
  •  | 
  •  

题

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

假设我有这样的数据。

data = 'helloworld'
.

假设块显示为5，我需要计算运行校验和。

>>> zlib.adler32('hello')
103547413
>>> zlib.adler32('ellow')
105316900
.

根据Python文档（Python版本2.7.2）

zlib.adler32(data[, value])
.

“计算数据的Adler-32校验和。（Adler-32校验和几乎 作为CRC32可靠，但可以更快地计算。）如果 值存在，它用作校验和的起始值; 否则，使用固定的默认值。这允许计算a 运行校验和对几个输入的串联。“

但是当我提供这样的东西时，

>>> 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功能的滚动属性正确吗？

有帮助吗？

解决方案

adler32()功能不提供“滚动”。该文档正确使用“运行”（不是“滚动”）的单词，这意味着它只需将Adler32计算在块中就像一次性相反。您需要编写自己的代码来进行“滚动”Adler32值，这将是数据上的滑动窗口的Adler32。

其他提示

在你的方法“滚动”中，

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

应该是

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

根据 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)
.

顺便说一下，您的def rolling（）是正确的，至少对于Python，其中Modulo结果的符号具有除法表的标志。它可能无法用其他语言工作，例如在c中的符号％的符号是股息的符号或已定义的实现。

您可以通过考虑从Modulo 65521获取每个步骤的程度来更有效地使您的算法更有效，并且替换为65521的添加或减法的百分比，或使用足够大的数据类型来放置它虽然并弄清楚了多常，你可以逃避百分比，以避免溢出。再次，小心占负股的％。

这是工作功能。请注意，在计算mod的步骤。

def myadler32(data):
  a = 1
  b = 0
  for c in data:
      a += c
      b += a
  a %= MOD_ADLER
  b %= MOD_ADLER
  return b<<16 | a
.

我相信您在测试中错误计算了Adler32值：

>>> import zlib
>>> zlib.adler32("helloworld")
389415997
>>> zlib.adler32("world",zlib.adler32("hello"))
389415997
.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top