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

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

Заранее спасибо!


python checksum crc32 micropython
person Cooper    schedule 10.01.2017    source источник

Ответы (1)


arrow_upward
8
arrow_downward

Я не смотрел внимательно на ваш код, поэтому я не могу точно определить источник ошибки, но вы можете легко настроить его, чтобы получить желаемый результат:

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 бита результата.

person PM 2Ring    schedule 10.01.2017
comment
Вы, сэр, находка, большое спасибо за ваш быстрый ответ и решение! - person Cooper; 10.01.2017
comment
@Купер Не беспокойся. Я не уверен на 100% в своей настройке (из-за смешивания арифметики с побитовыми операциями). Похоже, он выполняет работу правильно, но я немного обеспокоен тем, что он может дать неправильный ответ в некоторых крайних случаях. OTOH, я только что проверил, что он возвращает ffffffff при передаче '\xff\xff\xff\xff', так что это хороший знак. :) - person PM 2Ring; 10.01.2017
comment
@Cooper После этих дополнительных тестов моя уверенность возросла. :) Я был бы очень удивлен, если бы он вернул неправильный результат для любого ввода. - person PM 2Ring; 10.01.2017
comment
похоже, что «возврат (значение ^ 0xffffffff)» устранит необходимость впоследствии выполнять операцию and над результатом. Побитовая арифметика не была моей сильной стороной, и с тех пор прошло некоторое время. Спасибо еще раз. - person Cooper; 10.01.2017
comment
@Купер А, конечно! :) Еще вариант return ~value & 0xffffffff. Оба они чище, чем return (-1 - value) & 0xffffffff. Ваша версия, вероятно, лучшая, так как она использует наименьшее количество операций. - person PM 2Ring; 10.01.2017