为什么我的滚动adler32校验和在go中不起作用？（模算术）

Question

我在go中实现了adler32 checksum的rolling版本。在

这个answer有助于复查我的数学。然而，我正在努力在果朗正确地实施它。在

我写了以下代码：

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
}

它在各种输入上进行了测试，运行良好，直到我决定用随机数据运行它。这里有一个sample它不工作（我发现了几个）。在

让我困惑的是，python中的相同代码可以完美地处理这些输入：

^{pr2}$

为了更好地度量，我将proof包括在内，说明这在python中可以工作。请注意，python校验和与go校验和的非滚动版本相匹配（该部分直接来自go核心库）。在

我研究了所有其他有问题的样本的结果，发现我从来没有在校验和的最低有效位（“a”位）上出错。同样，错误是一致的，等于0xe10000。我怀疑go如何处理uint32整数上的模运算的一个特殊性是造成这种情况的原因。在

发生了什么？我如何修复代码？在

Answer 1

Python中的整数是有符号的。您声明golang版本中的所有整数都是无符号的。这就是区别。在

当一个无符号数从一个较小的无符号数中减去时，你会得到一个巨大的无符号数，它给出的除法余数与小的负差不同。包装时，实际上是在添加2³²。2³²mod65521是225，或者是0xe1，这就是为什么你看到{}之间的区别。它更可能是围绕b计算，但如果{}恰好在这一步非常小，a也可能发生。在

根据@samgak的评论，您还必须担心不同语言中对有符号值的%运算符的定义。因此，在执行% MOD操作之前，通过添加尽可能多的MOD使值为正。对于a，只需添加MOD。对于b，添加(1 + n * leave / MOD) * MOD。在

注意确保中间值不会溢出。如果n*leave大到足以包装所使用的整数类型，go中的代码可能会给出错误的结果。在

Answer 2

我不知道怎么走，但这里有一些可能性：

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?