2

adler32 checksumのローリングバージョンを実装しています。

この回答は、私の数学を再確認するのに役立ちました。ただし、golang で正しく実装するのに苦労しています。

次のコードを書きました。

func roll(adler, n, leave, enter uint32) uint32 {
    a := adler & 0xffff
    b := adler >> 16

    a = (a + enter - leave) % MOD
    b = (b - n*leave - 1 + a) % MOD
    return b<<16 | a
}

ランダムなデータで実行することを決定するまで、さまざまな入力でテストし、正常に機能しました。これが機能しないサンプルです（いくつか見つけました）。

私を困惑させているのは、Pythonの同じコードがこれらの入力で完全に機能することです:

def roll(adler, n, leave, enter):
    a = adler & 0xffff
    b = adler >> 16

    a = (a + enter - leave) % MOD
    b = (b - n*leave - 1 + a) % MOD
    return b<<16 | a

念のため、これが Python で機能することの証明を含めます。Python チェックサムは、go チェックサムの非ローリング バージョンと一致することに注意してください (その部分は、go コア ライブラリから直接取得されます)。

問題のある他のすべてのサンプルで結果を調べたところ、チェックサムの最下位ビット (「a」ビット) を決して間違えていないことがわかりました。また、エラーは一貫して同じで、 に等しくなり0xe10000ます。go が uint32 整数の剰余演算を処理する方法の特殊性が、この原因であると思われます。

何が起こっているのか、コードを修正するにはどうすればよいですか?

4

2 に答える 2

4

Python の整数は符号付きです。golang バージョンのすべての整数を符号なしとして宣言しました。それが違いです。

小さい符号なしの数値から符号なしの数値を引くと、小さな負の差とは異なる除算の剰余を与える巨大な符号なしの数値が得られます。ラップすると、効果的に 2 32が追加されます。2 32 mod 65521 は 225、つまり0xe1ですb。b計算をラップする可能性がはるかに高くなりますが、そのステップでたまたま非常に小さいa場合は、同様に発生する可能性があります。a

@samgak のコメントによると、異なる言語での符号付き値に対する % 演算子の定義についても心配する必要があります。したがって、さまざまな規則で機能する解決策はMOD、% MOD. についてaは、 を追加するだけMODです。についてbは、 を追加し(1 + n * leave / MOD) * MODます。

中間値がオーバーフローしないように注意してください。n*leaveが使用されている整数型をラップするのに十分な大きさである場合、go のコードは誤った結果をもたらす可能性があります。

于 2016-12-06T02:35:07.287 に答える
0

行くかどうかはわかりませんが、いくつかの可能性があります：

b := adler >> 16 change to b := (adler >> 16) & 0xffff

b = (b - n*leave - 1 + a) % MOD ... what happens if expression in () is negative?

return b<<16 | a ... check operator precedence; (b<<16)|a or b<<(16|a) ?

32-bit machine or 64-bit?
于 2016-12-06T00:28:15.243 に答える