在不使用库的情况下 Python 中的 CRC32 计算

CRC32 calculation in Python without using libraries

我一直在努力了解 CRC32 计算,但没有成功,我似乎得到的值与我应该得到的值不匹配。

我知道 Python 有能够生成这些校验和的库(即 zlib 和 binascii),但我无法使用它们,因为 CRC 功能不存在微型蟒蛇。

到目前为止我有以下代码:

import binascii
import zlib
from array import array

poly = 0xEDB88320

table = array('L')
for byte in range(256):
    crc = 0
    for bit in range(8):
        if (byte ^ crc) & 1:
            crc = (crc >> 1) ^ poly
        else:
            crc >>= 1
        byte >>= 1
    table.append(crc)

def crc32(string):
    value = 0xffffffffL

    for ch in string:
        value = table[(ord(ch) ^ value) & 0x000000ffL] ^ (value >> 8)

    return value

teststring = "test"

print "binascii calc:  0x%08x" % (binascii.crc32(teststring) & 0xffffffff)
print "zlib calc:      0x%08x" % (zlib.crc32(teststring) & 0xffffffff)
print "my calc:        0x%08x" % (crc32(teststring))

然后我得到以下输出:

binascii calc:  0xd87f7e0c
zlib calc:      0xd87f7e0c
my calc:        0x2780810c

binascii 和 zlib 的计算一致,而我的不一致。我相信计算出的 table 字节是正确的,因为我已经将它与网上的示例进行了比较。所以问题一定是计算每个字节的例程,谁能指出我正确的方向?

提前致谢!

我没有仔细查看您的代码,因此无法确定错误的确切来源,但您可以轻松调整它以获得所需的输出:

import binascii
from array import array

poly = 0xEDB88320

table = array('L')
for byte in range(256):
    crc = 0
    for bit in range(8):
        if (byte ^ crc) & 1:
            crc = (crc >> 1) ^ poly
        else:
            crc >>= 1
        byte >>= 1
    table.append(crc)

def crc32(string):
    value = 0xffffffffL
    for ch in string:
        value = table[(ord(ch) ^ value) & 0xff] ^ (value >> 8)

    return -1 - value

# test

data = (
    '',
    'test',
    'hello world',
    '1234',
    'A long string to test CRC32 functions',
)

for s in data:
    print repr(s)
    a = binascii.crc32(s)
    print '%08x' % (a & 0xffffffffL)
    b = crc32(s)
    print '%08x' % (b & 0xffffffffL)
    print

输出

''
00000000
00000000

'test'
d87f7e0c
d87f7e0c

'hello world'
0d4a1185
0d4a1185

'1234'
9be3e0a3
9be3e0a3

'A long string to test CRC32 functions'
d2d10e28
d2d10e28

这里还有几个测试可以验证调整后的 crc32 给出与 binascii.crc32 相同的结果。

from random import seed, randrange

print 'Single byte tests...',
for i in range(256):
        s = chr(i)
        a = binascii.crc32(s) & 0xffffffffL
        b = crc32(s) & 0xffffffffL
        assert a == b, (repr(s), a, b)

print('ok')

seed(42)

print 'Multi-byte tests...'
for width in range(2, 20):
    print 'Width', width
    r = range(width)
    for n in range(1000):
        s = ''.join([chr(randrange(256)) for i in r])
        a = binascii.crc32(s) & 0xffffffffL
        b = crc32(s) & 0xffffffffL
        assert a == b, (repr(s), a, b)
print('ok')

输出

Single byte tests... ok
Multi-byte tests...
Width 2
Width 3
Width 4
Width 5
Width 6
Width 7
Width 8
Width 9
Width 10
Width 11
Width 12
Width 13
Width 14
Width 15
Width 16
Width 17
Width 18
Width 19
ok

如评论中所述,原始代码中的错误来源是此 CRC-32 算法反转初始 crc 缓冲区,然后反转最终缓冲区内容。所以 value 被初始化为 0xffffffff 而不是零,我们需要 return value ^ 0xffffffff,也可以写成 ~value & 0xffffffff,即反转 value 然后 select 结果的低 32 位。