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

回答

相關問題