adler32ローリングチェックサムの計算の違い - Python

Question

実行中のチェックサムの計算を見ながら明確にする必要があります。

このようなデータがあるとします。

data = 'helloworld' 

ブロックサイズを5と仮定すると、実行中のチェックサムを計算する必要があります。

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

Pythonドキュメント（Pythonバージョン2.7.2）

zlib.adler32(data[, value]) 

によれば、「データのアドラー-32チェックサムを計算します。（アドラー-32チェックサムはほぼ ほど信頼性が高いですCRC32であるが、はるかに速く計算することができる）。 値が存在する場合、それはチェックサムの開始値として使用される; それ以外の場合、固定のデフォルト値が使用される。 実行中のチェックサムは、 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 

は、私はあなたがローリングチェックサムとPythonの私の実装では、いくつかの大きな違いは、価値の面で、そこにある見ることができるように、これらの機能

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

を実行しているから取得した値です。

ここで、ローリングチェックサムの計算に間違っていますか？ 私はpythonのadler32関数のローリングプロパティを正しく使用していますか？

Answer 1

をadler32()機能は「ローリング」を提供しません。ドキュメントでは「running」（「ローリング」ではなく）という単語が正しく使用されています。つまり、adler32を一度にすべてではなくチャンクで計算することができます。 「ローリング」のadler32値を計算するための独自のコードを記述する必要があります。この値は、データに対するスライディングウィンドウのadler32になります。

Answer 2

私はあなたのテストでAdler32チェック値の誤計算しまし信じる：

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

Answer 3

ところで、あなたのdef rolling（）は、少なくともモジュロ結果の符号が除数の符号を持つPythonでは正しいです。他の言語ではうまくいかないかもしれません。たとえば、Cの例では、％の結果の符号は被除数の符号か実装定義のどちらかです。

モジュロ65521から各ステップでどのくらい離れているかを考慮し、65521のifとwithまたはadditionsまたはsubtractionsを％で置き換えるか、または十分なデータ型を使用してアルゴリズムをより効率的にすることができますしばらくの間、オーバーフローを避けるために、合計で％を得ることができる頻度を調べます。再び、負の配当については％に注意してください。

Answer 4

ここに作業機能があります。 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 

Answer 5

"ローリング"、

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 

を

ローリングチーズ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)