在Python中不使用库进行CRC32计算

Question

我一直在试图理解CRC32计算，但没有取得太大的进展，我似乎得到的值与应该得到的值不匹配。

我知道Python有能够生成这些校验和的库（即zlib和binascii），但我不能使用它们，因为MicroPython上不存在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的计算结果是一致的，但我的计算结果不同。我认为所计算的字节表是正确的，因为我已经与网上可用的示例进行了比较。因此问题必须在计算每个字节的程序中，有没有人能指点我正确的方向？

提前感谢！

- Cooper

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位。

- PM 2Ring

---

您真是个救星，非常感谢您的快速回复和解决方案！ - Cooper

@Cooper 没关系。我对我的调整不是 100％ 自信（由于将算术与位运算混合使用而导致）。它看起来似乎正常工作，但我有点担心它在某些边角情况下可能会给出错误的答案。另一方面，我刚刚检查了当传递 '\xff\xff\xff\xff' 时它返回 ffffffff，这是一个好兆头。 :) - PM 2Ring

@Cooper 在进行了这些额外的测试之后，我的信心增强了。 :) 如果它对任何输入返回错误的结果，我会非常惊讶的。 - PM 2Ring

看起来 'return (value ^ 0xffffffff)' 可以避免之后对结果进行与操作的需要。位运算不是我的强项，而且已经有一段时间了。再次感谢。 - Cooper

@Cooper 当然！ :) 另一个选项是 return ~value & 0xffffffff。这两个都比 return (-1 - value) & 0xffffffff 更简洁。你的版本可能是最好的，因为它使用了最少的操作。 - PM 2Ring

顺便提一下，我在这里有更多的CRC代码示例：https://stackoverflow.com/a/53360240/4014959 - PM 2Ring

Answer 2

如果使用二进制数据，并且 CRC 被链接在多个缓冲区上，我会使用以下方法（使用 OPs 表）：

def crc32(data, crc=0xffffffff):  
    for b in data:  
        crc = table[(b ^ crc) & 0xff] ^ (crc >> 8)  
    return crc

可以将最终结果与-1进行异或以与在线计算器一致。

crc = crc32(b'test')  
print('0x{:08x}'.format(crc))
  
crc = crc32(b'te')  
crc = crc32(b'st', crc)  
print('0x{:08x}'.format(crc))

print('xor: 0x{:08x}'.format(crc ^ 0xffffffff))

输出

0x278081f3
0x278081f3
xor: 0xd87f7e0c

- Rob Milne