我用3种风格写了同样的算法:
- 普通Python
- 使用Numba优化Python
- 使用Viper优化的Micropython
我确信普通Python和Micropython中的例程是正确的:几兆字节随机数据的校验和等于zlib.adler32计算的校验和
下面是为Numba编写的例程:
@numba.jit(nopython = True)
def adler_32(data: bytes, length: np.int32, init: np.uint32) -> np.uint32 :
# note: on the first call, init should be 1
ADLER = np.uint16(65521)
NMAX = np.int32(5552) # max iterations to keep s1, s2 as uint16
s1 = np.uint16(init & 0xffff)
s2 = np.uint16(init >> 16)
i = 0
while length > 0 :
k = min(length, NMAX)
length -= k
while k :
s1 += np.uint8(data[i])
k -= 1
s2 += s1
i += 1
if s1 >= ADLER :
s1 -= ADLER
if s2 >= ADLER :
s2 -= ADLER
return (np.uint32(s2) << 16) | s1
问题:s1和s2假设值大于0xffff,因此结果不正确。
为什么s1和s2,声明为uint16,得到更大的值?是否有我没有看到的警告或副作用?
Errata Corrige普拉亚戴尔雷安格莱斯
这显然是错误的,我匆忙地从微控制器例程中复制并粘贴它,其中数据很小,s1,s2留在uint16中。
if s1 >= ADLER :
s1 -= ADLER
if s2 >= ADLER :
s2 -= ADLER
正确的通用算法是
s1 %= ADLER
s2 %= ADLER
2条答案
按热度按时间0dxa2lsx1#
你需要理解这个神奇的数字:5552。如果
s2
是一个 *32位 * 无符号整数,则在最坏情况下将溢出s2
的迭代次数为5553。s1
和s2
都需要声明为32位。不是16位。最坏的情况是
s1
和s2
从它们的最高值65520开始,所有字节都是255。然后s2
变成(1 + n)(65520 + 255 n / 2),其中 n 是字节数,所有字节的值都是255。将其设为232,然后求解 n,得到5552.19。另一个错误是
if sx > ADLER: sx -= ADLER
福尔斯不能保证sx
小于ADLER
,而ADLER
需要在循环中的那个点。第552章有什么意义两者都必须是sx %= ADLER
。2vuwiymt2#
(我写这篇文章是为了给Mark post写评论,但SO拒绝它太长了。
我发现了这个问题。
今天,我测试了高达8 GB的有效负载,用我的例程对zlib.adler32的部分校验和进行了每256 Mb的测试。一个有效载荷是随机数据,另一个有效载荷全是0xff。
两个例程返回相同的校验和,直到结束。我的例程仍然使用np.uint16来处理s1和s2!
在我看来,numpy变量类型只是JIT的一个“提示”,它们不是真实的的类型(像C声明)。在某个点上,变量不会溢出,可能有一个隐藏的“拆箱”从16位到32位。
检查:如果在模数之前,我强制使用“sx &= 0xffff”的16位,则结果不正确,就像@Mark Adler写的那样。我被这个“拆箱”转移了注意力,也因为我在三个不同的Python实现上处理同一个例程。
我讨厌Python:在C中,我在5分钟内发现了问题。我是个老程序员,习惯了编译和类型化语言 ;-)