在Python中無需使用庫的CRC32計算

Question

我一直試圖讓我的頭繞過CRC32計算沒有太多成功，我似乎得到的值與我應該得到的值不匹配。

我知道Python具有能夠生成這些校驗和的庫（即zlib和binascii），但由於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 

的binascii和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位。