python - 为什么我的滚动 adler32 校验和在 go 中不起作用？ (模运算)

Question

我正在执行一个 rolling adler32 checksum 的版本.

这answer有助于仔细检查我的数学。但是，我正在努力在 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
}

它在各种输入上对其进行了测试并且运行良好，直到我决定在随机数据上运行它。这是一个sample它不起作用的地方(我发现了其中的几个)。

让我感到困惑的是，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

为了更好的衡量，我包括了proof这在 python 中有效。请注意，python 校验和与 go 校验和的非滚动版本相匹配(并且该部分直接来自 go 核心库)。

我研究了所有其他有问题样本的结果，发现我在校验和的最低有效位(“a”位)上从未犯错。此外，错误始终相同，等于 0xe10000。我怀疑 go 处理 uint32 整数模运算的特殊性是造成这种情况的原因。

发生了什么，我该如何修复我的代码？

Answer 1

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

当一个无符号数从一个较小的无符号数中减去时，你会得到一个巨大的无符号数，它给出的除法余数与小的负差不同。换行时，实际上是在添加 2³²。 2³² mod 65521 是 225，或 0xe1，这就是您在 b 中看到差异的原因。它更有可能包裹在 b 计算中，但它也可能发生在 a 上，如果 a 恰好在那个时候非常小步骤。

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

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