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

在计算运行校验和时需要澄清。adler32滚动校验和的计算差异 - python

假设我有这样的数据。

data = 'helloworld'

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

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

根据Python文档（Python版本2.7.2）

zlib.adler32(data[, value])

“计算数据的一个阿德勒-32校验和。（一种阿德勒-32校验和几乎是作为可靠CRC32，但可以更快计算）如果存在值，则将其用作校验和的起始值;否则将使用固定的默认值，这允许计算一个在多个i nputs“。

但是当我提供了这样的事情，

>>> 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函数的滚动属性？

来源

2012-03-14 Liju Mathew

的adler32()功能不提供“滚动”。该文档正确地使用了“运行”（不是“滚动”）这个词，这意味着它可以一次性计算大块中的adler32。你需要编写自己的代码来计算一个“滚动”的adler32值，这个值就是数据滑动窗口的adler32值。

来源

2012-03-14 19:17:33

我相信你们已经错误地计算在测试的Adler32值：

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

来源

2012-03-14 09:45:03 sarnold

谢谢。但是，我想我正在寻找滚动校验和的差异。就你而言，我得到的是'world'的校验和，我感兴趣的是使用'hello'的校验和计算'ellow'的校验和。两者之间的区别是'h'被删除，'w'被添加。如果我不清楚，请告诉我。 – 2012-03-14 12:14:47

顺便说一下，您的def rolling（）是正确的，至少对于模数结果的符号具有除数符号的Python。它可能不适用于其他语言，例如在C中，％结果的符号是股息的标志或者是实现定义的。

通过考虑您可以在每一步获得的模65521的距离，以及用if和65521的加法或减法来替换％，或者使用足够大的数据类型来让它运行一段时间，并找出如何很少你可以摆脱总和的％，以避免溢出。再次，小心与负股息％。

来源

2012-03-15 18:32:45

感谢您的补充评论，马克。 – prabhu 2012-04-08 05:41:44

我尝试了prime 65521，并在我的滚动校验和过程实现（更改已检测或未检测到）中得到计算错误。如果我使用2^16，一切都很好。我希望在一段时间之后，我能够回到这个问题上，并排除编程错误的可能性，从而在同一时间内为这个主题带来一些有用的信息。 – 4pie0 2017-03-25 09:50:58

这是工作功能。请注意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

来源

2013-10-20 12:59:19

在你的方法 “滚动” 时，

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

当我们滚动che cksum，我们将得到方程：

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)

来源

2013-11-20 02:25:51 JasonDong

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

回答

相关问题