不使用库的Python中的CRC32计算

Question

我一直在试图了解CRC32的计算结果，但没有成功，我得到的值似乎与我应该得到的值不匹配。

我知道Python有能够生成这些校验和的库（即zlib和binasci），但由于CRC功能在micropython上不存在，因此我没有足够的资源来使用它们。

到目前为止，我有以下代码：

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

binasci和zlib的计算与我的不一致。我相信计算的字节表是正确的，因为我已经将它与网络上可用的示例进行了比较。所以问题必须是计算每个字节的例程，有人能告诉我正确的方向吗？

提前谢谢！

Answer 1

我没有仔细查看您的代码，因此无法确定错误的确切来源，但您可以轻松地对其进行调整以获得所需的输出：

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，而不是零，我们需要返回value ^ 0xffffffff，它也可以写为~value & 0xffffffff，即反转value，然后选择结果的低阶32位。