CODEWITHSUNDEEP
pythoncrc32bzip2
Lauritz V. Thaulow
Lauritz V. Thaulow

Reputation: 50995

Python CRC-32 woes

I'm writing a Python program to extract data from the middle of a 6 GB bz2 file. A bzip2 file is made up of independently decryptable blocks of data, so I only need to find a block (they are delimited by magic bits), then create a temporary one-block bzip2 file from it in memory, and finally pass that to the bz2.decompress function. Easy, no?

The bzip2 format has a crc32 checksum for the file at the end. No problem, binascii.crc32 to the rescue. But wait. The data to be checksummed does not necessarily end on a byte boundary, and the crc32 function operates on a whole number of bytes.

My plan: Use the binascii.crc32 function on all but the last byte, and then a function of my own to update the computed crc with the last 1–7 bits. But hours of coding and testing has left me bewildered, and my puzzlement can be boiled down to this question: How come crc32("\x00") is not 0x00000000? Shouldn't it be, according to the Wikipedia article?

You start with 0b00000000 and pad with 32 0's, then do polynomial division with 0x04C11DB7 until there are no ones left in the first 8 bits, which is immediately. Your last 32 bits is the checksum, and how can that not be all zeroes?

I've searched Google for answers and looked at the code of several CRC-32 implementations without finding any clue to why this is so.

Upvotes: 7

Views: 10027

Answers (2)

Lauritz V. Thaulow
Lauritz V. Thaulow

Reputation: 50995

In addition to the one-shot decompress function, the bz2 module also contains a class BZ2Decompressor that decompresses data as it is fed to the decompress method. It therefore does not care about the end-of-file checksum and provides the data needed once it reaches the end of the block.

To illustrate, assume I have located the block I wish to extract from the file and stored it in a bitarray.bitarray instance (other bit-twiddling modules will probably work as well). Then this function will decode it:

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())

Note that the frombytes and tobytes methods of bitarray were previously called fromstring and tostring.

Upvotes: 3

Nayuki
Nayuki

Reputation: 18532

how come crc32("\x00") is not 0x00000000?

The basic CRC algorithm is to treat the input message as a polynomial in GF(2), divide by the fixed CRC polynomial, and use the polynomial remainder as the resulting hash.

CRC-32 makes a number of modifications on the basic algorithm:

  1. The bits in each byte of the message is reversed. For example, the byte 0x01 is treated as the polynomial x^7, not as the polynomial x^0.
  2. The message is padded with 32 zeros on the right side.
  3. The first 4 bytes of this reversed and padded message is XOR'd with 0xFFFFFFFF.
  4. The remainder polynomial is reversed.
  5. The remainder polynomial is XOR'd with 0xFFFFFFFF.
  6. And recall that the CRC-32 polynomial, in non-reversed form, is 0x104C11DB7.

Let's work out the CRC-32 of the one-byte string 0x00:

  1. Message: 0x00
  2. Reversed: 0x00
  3. Padded: 0x00 00 00 00 00
  4. XOR'd: 0xFF FF FF FF 00
  5. Remainder when divided by 0x104C11DB7: 0x4E 08 BF B4
  6. XOR'd: 0xB1 F7 40 4B
  7. Reversed: 0xD2 02 EF 8D

And there you have it: The CRC-32 of 0x00 is 0xD202EF8D.
(You should verify this.)

Upvotes: 11

Related Questions