Расчет CRC32 в Python без использования библиотек

Question

Я старался не упускать из виду вычисления 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 расчеты согласны, где, как мой один не делает. Я считаю, что вычисленная таблица байтов верна, поскольку я сравнил ее с примерами, доступными в сети. Таким образом, проблема должна быть обычной, когда вычисляется каждый байт, может ли кто-нибудь указать мне правильное направление?

Заранее благодарен!

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-битные разряды младшего разряда.