title: Calculate/validate bz2 (bzip2) CRC32 in Python
body: <p>I'm trying to calculate/validate the CRC32 checksums for compressed bzip2 archives.</p>
  
  <pre><code>.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
  </code></pre>
  
  <p><a href="http://en.wikipedia.org/wiki/Bzip2" rel="noreferrer">http://en.wikipedia.org/wiki/Bzip2</a></p>
  
  <p>So I know where the CRC checksums are in a bz2 file, but how would I go about validating them. What chunks should I <code>binascii.crc32()</code> to get both CRCs? I've tried calculating the CRC of various chunks, byte-by-byte, but have not managed to get a match.</p>
  
  <p>Thank you. I'll be looking into the bzip2 sources and <code>bz2</code> Python library code, to maybe find something, especially in the <code>decompress()</code> method.</p>
  
  <p><strong>Update 1:</strong></p>
  
  <p>The block headers are identified by the following tags as far as I can see. <em>But tiny bz2 files do not contain the ENDMARK ones.</em> (Thanks to <strong>adw</strong>, we've found out that one should look for bit shifted values of the ENDMARK, since the compressed data is not padded to bytes.)</p>
  
  <pre><code>#define BLOCK_HEADER_HI  0x00003141UL
  #define BLOCK_HEADER_LO  0x59265359UL
  
  #define BLOCK_ENDMARK_HI 0x00001772UL
  #define BLOCK_ENDMARK_LO 0x45385090UL
  </code></pre>
  
  <p>This is from the <code>bzlib2recover.c</code> 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).</p>
  
  <pre><code>searching for block boundaries ...
  block 1 runs from 80 to 1182
  </code></pre>
  
  <p>Looking into the code that calculates this.</p>
  
  <p><strong>Update 2:</strong></p>
  
  <p><code>bzlib2recover.c</code> 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 <code>bz2</code> compressed file. Back on track, I have found that <code>compress.c</code> refers to some of the definitions in <code>bzlib_private.h</code>.</p>
  
  <pre><code>#define BZ_INITIALISE_CRC(crcVar) crcVar = 0xffffffffL;
  #define BZ_FINALISE_CRC(crcVar) crcVar = ~(crcVar);
  #define BZ_UPDATE_CRC(crcVar,cha)              \
  {                                              \
     crcVar = (crcVar &lt;&lt; 8) ^                    \
              BZ2_crc32Table[(crcVar &gt;&gt; 24) ^    \
                             ((UChar)cha)];      \
  }
  </code></pre>
  
  <p>These definitions are accessed by <code>bzlib.c</code> as well, <code>s-&gt;blockCRC</code> is initialized and updated in <code>bzlib.c</code> and finalized in <code>compress.c</code>. 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 <code>C</code> tag to the question as well.</p>
  
  <p>By the way, here are the C sources for bzip2 <a href="http://www.bzip.org/1.0.6/bzip2-1.0.6.tar.gz" rel="noreferrer">http://www.bzip.org/1.0.6/bzip2-1.0.6.tar.gz</a></p>
  
  <p><strong>Update 3:</strong></p>
  
  <p>Turns out <code>bzlib2</code> block CRC32 is calculated using the following algorithm:</p>
  
  <p><code>dataIn</code> is the data to be encoded.</p>
  
  <pre><code>crcVar = 0xffffffff # Init
      for cha in list(dataIn):
          crcVar = crcVar &amp; 0xffffffff # Unsigned
          crcVar = ((crcVar &lt;&lt; 8) ^ (BZ2_crc32Table[(crcVar &gt;&gt; 24) ^ (ord(cha))]))
  
      return hex(~crcVar &amp; 0xffffffff)[2:-1].upper()
  </code></pre>
  
  <p>Where BZ2_crc32Table is defined in <code>crctable.c</code></p>
  
  <p>For <code>dataIn = "justatest"</code> the CRC returned is <code>7948C8CB</code>, having compressed a textfile with that data, the crc:32 checksum inside the bz2 file is <code>79 48 c8 cb</code> which is a match.</p>
  
  <p><strong>Conclusion:</strong></p>
  
  <p>bzlib2 CRC32 is (quoting <code>crctable.c</code>)</p>
  
  <blockquote>
    <p>Vaguely derived from code by Rob
    Warnock, in Section 51 of the
    comp.compression FAQ...</p>
  </blockquote>
  
  <p>...thus, as far as I understand, cannot be precalculated/validated using standard CRC32 checksum calculators, but rather require the <code>bz2lib</code> implementation (lines 155-172 in <code>bzlib_private.h</code>).</p>