Calculate/validate bz2 (bzip2) CRC32 in Python

Question

I'm trying to calculate/validate the CRC32 checksums for compressed bzip2 archives.

.magic:16                       = 'BZ' signature/magic number
.version:8                      = 'h' for Bzip2 ('H'uffman coding)
.hundred_k_blocksize:8          = '1'..'9' block-size 100 kB-900 kB

.compressed_magic:48            = 0x314159265359 (BCD (pi))
.crc:32                         = checksum for this block
...
... 
.eos_magic:48                   = 0x177245385090 (BCD sqrt(pi))
.crc:32                         = checksum for whole stream
.padding:0..7                   = align to whole byte

http://en.wikipedia.org/wiki/Bzip2

So I know where the CRC checksums are in a bz2 file, but how would I go about validating them. What chunks should I binascii.crc32() to get both CRCs? I've tried calculating the CRC of various chunks, byte-by-byte, but have not managed to get a match.

Thank you. I'll be looking into the bzip2 sources and bz2 Python library code, to maybe find something, especially in the decompress() method.

Update 1:

The block headers are identified by the following tags as far as I can see. But tiny bz2 files do not contain the ENDMARK ones. (Thanks to adw, we've found out that one should look for bit shifted values of the ENDMARK, since the compressed data is not padded to bytes.)

#define BLOCK_HEADER_HI  0x00003141UL
#define BLOCK_HEADER_LO  0x59265359UL

#define BLOCK_ENDMARK_HI 0x00001772UL
#define BLOCK_ENDMARK_LO 0x45385090UL

This is from the bzlib2recover.c source, blocks seem to start always at bit 80, right before the CRC checksum, which should be omitted from the CRC calculation, as one can't CRC its own CRC to be the same CRC (you get my point).

searching for block boundaries ...
block 1 runs from 80 to 1182

Looking into the code that calculates this.

Update 2:

bzlib2recover.c does not have the CRC calculating functions, it just copies the CRC from the damaged files. However, I did manage to replicate the block calculator functionality in Python, to mark out the starting and ending bits of each block in a bz2 compressed file. Back on track, I have found that compress.c refers to some of the definitions in bzlib_private.h.

#define BZ_INITIALISE_CRC(crcVar) crcVar = 0xffffffffL;
#define BZ_FINALISE_CRC(crcVar) crcVar = ~(crcVar);
#define BZ_UPDATE_CRC(crcVar,cha)              \
{                                              \
   crcVar = (crcVar << 8) ^                    \
            BZ2_crc32Table[(crcVar >> 24) ^    \
                           ((UChar)cha)];      \
}

These definitions are accessed by bzlib.c as well, s->blockCRC is initialized and updated in bzlib.c and finalized in compress.c. There's more than 2000 lines of C code, which will take some time to look through and figure out what goes in and what does not. I'm adding the C tag to the question as well.

By the way, here are the C sources for bzip2 http://www.bzip.org/1.0.6/bzip2-1.0.6.tar.gz

Update 3:

Turns out bzlib2 block CRC32 is calculated using the following algorithm:

dataIn is the data to be encoded.

crcVar = 0xffffffff # Init
    for cha in list(dataIn):
        crcVar = crcVar & 0xffffffff # Unsigned
        crcVar = ((crcVar << 8) ^ (BZ2_crc32Table[(crcVar >> 24) ^ (ord(cha))]))

    return hex(~crcVar & 0xffffffff)[2:-1].upper()

Where BZ2_crc32Table is defined in crctable.c

For dataIn = "justatest" the CRC returned is 7948C8CB, having compressed a textfile with that data, the crc:32 checksum inside the bz2 file is 79 48 c8 cb which is a match.

Conclusion:

bzlib2 CRC32 is (quoting crctable.c)

Vaguely derived from code by Rob Warnock, in Section 51 of the comp.compression FAQ...

...thus, as far as I understand, cannot be precalculated/validated using standard CRC32 checksum calculators, but rather require the bz2lib implementation (lines 155-172 in bzlib_private.h).

Answer 1

The following is the CRC algorithm used by bzip2, written in Python:

crcVar = 0xffffffff # Init
    for cha in list(dataIn):
        crcVar = crcVar & 0xffffffff # Unsigned
        crcVar = ((crcVar << 8) ^ (BZ2_crc32Table[(crcVar >> 24) ^ (ord(cha))]))

    return hex(~crcVar & 0xffffffff)[2:-1].upper()

(C code definitions can be found on lines 155-172 in bzlib_private.h)

BZ2_crc32Table array/list can be found in crctable.c from the bzip2 source code. This CRC checksum algorithm is, quoting: "..vaguely derived from code by Rob Warnock, in Section 51 of the comp.compression FAQ..." (crctable.c)

The checksums are calculated over the uncompressed data.

Sources can be downloaded here: http://www.bzip.org/1.0.6/bzip2-1.0.6.tar.gz