Python CRC-32 горе - PullRequest
Новая
       44

Python CRC-32 горе

5 голосов
/ 19 февраля 2011

Я пишу программу на Python для извлечения данных из середины файла размером 6 ГБ bz2.Файл bzip2 состоит из независимо дешифруемых блоков данных, поэтому мне нужно только найти блок (они разделены магическими битами), затем создать временный одноблочный файл bzip2 из него в памяти и, наконец, передать егоФункция bz2.decompress.Легко, нет?

Формат bzip2 имеет контрольную сумму crc32 для файла в конце.Нет проблем, binascii.crc32 на помощь.Но ждать.Данные для контрольной суммы не обязательно заканчиваются границей байтов, а функция crc32 работает с целым числом байтов.

Мой план: используйте функцию binascii.crc32 для всех, кроме последнего байта, а затеммоя собственная функция для обновления вычисленного crc с последними 1–7 битами.Но часы кодирования и тестирования оставили меня в замешательстве, и моя загадка может быть сведена к следующему вопросу: почему crc32 ("\ x00") не равен 0x00000000?Разве это не должно быть, согласно статье в Википедии?

Вы начинаете с 0b00000000 и добавляете 32 0, затем выполняете полиномиальное деление с 0x04C11DB7 до тех пор, пока в первых 8 битах не останется ни одного, что сразу.Ваши последние 32 бита являются контрольной суммой, и как это может быть не всеми нулями?

Я искал в Google ответы и посмотрел код нескольких реализаций CRC-32, не найдя никакой подсказки, почему это так.

Ответы [ 2 ]

9 голосов
/ 13 июля 2011

почему crc32 ("\ x00") не равен 0x00000000?

Основной алгоритм CRC заключается в обработке входного сообщения как многочлена в GF (2), деленного нафиксированный полином CRC и использование остатка полинома в качестве результирующего хеша.

CRC-32 вносит ряд изменений в базовый алгоритм:

  1. Биты в каждом байте сообщенияперевернутыйНапример, байт 0x01 обрабатывается как многочлен x ^ 7, а не как многочлен x ^ 0.
  2. Сообщение дополняется 32 нулями с правой стороны.
  3. Первые 4байты этого перевернутого и дополненного сообщения XOR'd с 0xFFFFFFFF.
  4. Остальной полином обращен.
  5. Остальной полином XOR'd с 0xFFFFFFFF.
  6. И отзывчто полином CRC-32 в не обращенной форме равен 0x104C11DB7.

Давайте разберем CRC-32 однобайтовой строки 0x00:

  1. Сообщение: 0x00
  2. в обратном порядке: 0x00
  3. с добавлением: 0x00 00 00 00 00
  4. XOR'd: 0xFF FF FF FF 00
  5. Остаток при делении на 0x104C11DB7: 0x4E 08 BF B4
  6. XOR'd: 0xB1 F7 40 4B
  7. Реверс: 0xD2 02 EF 8D

И вот оно у вас: CRC-320x00 - это 0xD202EF8D.
(Вы должны проверить это.)

1 голос
/ 20 февраля 2011

В дополнение к однократной функции decompress модуль bz2 также содержит класс BZ2Decompressor, который распаковывает данные при их передаче в метод распаковки. Поэтому он не заботится о контрольной сумме конца файла и предоставляет необходимые данные, как только он достигает конца блока.

Для иллюстрации предположим, что я нашел блок, который я хочу извлечь из файла, и сохранил его в экземпляре bitarray.bitarray (другие модули битового тиддлинга, вероятно, также будут работать). Тогда эта функция расшифрует его: 

def bunzip2_block(block):
    from bz2 import BZ2Decompressor
    from bitarray import bitarray

    dummy_file = bitarray(endian="big")
    dummy_file.frombytes("BZh9")
    dummy_file += block

    decompressor = BZ2Decompressor()
    return decompressor.decompress(dummy_file.tobytes())

Обратите внимание, что методы bitarray frombytes и tobytes ранее назывались fromstring и tostring.

...