python3和numba,adler32校验和计算错误

avwztpqn  于 2023-07-01  发布在  Python
关注(0)|答案(2)|浏览(164)

我用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
0dxa2lsx

0dxa2lsx1#

你需要理解这个神奇的数字:5552。如果s2是一个 *32位 * 无符号整数,则在最坏情况下将溢出s2的迭代次数为5553。s1s2都需要声明为32位。不是16位。
最坏的情况是s1s2从它们的最高值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

2vuwiymt

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分钟内发现了问题。我是个老程序员,习惯了编译和类型化语言 ;-)

相关问题