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

vlurs2pr 于 5个月前发布在 Go

关注(0)|答案(2)|浏览(45)

我在go中实现了adler32 checksum的rolling版本。
这个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
}

字符串
它在各种输入上进行了测试，它工作得很好，直到我决定在随机数据上运行它。
令我困惑的是，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整数上的模运算的特殊性是造成这一点的原因。
发生了什么以及如何修复我的代码？

来源：https://stackoverflow.com/questions/40985080/why-does-my-rolling-adler32-checksum-not-work-in-go-modulo-arithmetic

2条答案

按热度按时间

goucqfw61#

Python中的整数是有符号的。你在golang版本中声明了所有的整数都是无符号的。这就是区别。
当一个无符号数从一个较小的无符号数中减去时，你会得到一个巨大的无符号数，它在除法时给出的余数与小的负差不同。当你换行时，你实际上是加上232。232 mod 65521是225，或0xe1，这就是为什么你会在b中看到这种差异，它更有可能在b计算中出现，但如果a在这一步非常小，那么a也会出现这种情况。
根据@samgak的评论，你还必须担心不同语言中有符号值的%运算符的定义。因此，适用于不同约定的解决方案是在执行% MOD之前，通过添加尽可能多的MOD s来使值为正。对于a，只需添加MOD。对于b，添加(1 + n * leave / MOD) * MOD。
注意确保中间值不会溢出。如果n*leave大到足以 Package 所使用的整数类型，go中的代码可能会给出给予错误的结果。

赞(0）回复(0）举报 5个月前

xggvc2p62#

我不知道去，但这里有一些可能性：

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?

字符串

赞(0）回复(0）举报 5个月前

我来回答

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

2条答案

相关问题

热门标签

最新问答