bzip2を読む ファイルフォーマット

こんにちは、junkawaです。

本記事では、bzip2の圧縮ファイルの形式について紹介します。

ストリームヘッダ

上段左端の‘BZ’、’h’、blocksizeがヘッダとなります。blocksizeは、’1’〜’9’となります。

‘BZ’ (16bit) は識別子です。compress.c 624、625行目で書き出します。

‘h’ (8bit)はバージョンです。bzip2は’h’、bzip1は’0’です。compress.c 626行目。

blocksize(8bit)は入力ブロックサイズです。’1’〜’9’となります。’9’の時、ブロックサイズは900,000バイトとなります。compress.c 627行目。

ストリームテイラ

上段右端の0x177245385090、CRCがテイラとなります。

0x177245385090(48bit)は、sqrt(π) (円周率πの平方根) の BCD(Binary-coded decimal)です。compress.c 659、660、661行目。

CRC(32bit)は、圧縮前の入力データに対応するCRC(Cyclic Redundancy Check)です。compress.c 662行目。

CRCの後ろに、1バイトアライメントになるようにパディング(1〜7bit)します。compress.c 665行目。

ブロックデータ

ヘッダの後には、入力ブロックデータに対応する出力ブロックデータが続きます。入力ブロックデータは一般に複数あるので、対応する出力ブロックデータも複数あります。図中の下段が、出力ブロックデータの中身です。

0x314159265359(48bit)は、円周率πのBCDです。compress.c 632、633、634行目。
CRC(32bit)は入力ブロックデータに対応するCRCです。compress.c 637行目。

0(1bit)はランダム化の使用不使用です。現在のbzip2ではランダム化は行わず、常に0です。compress.c 648行目。

origPtr(24bit)はブロックソート逆変換に使用する、オリジナルデータのソート後の行番号です。compress.c 650行目。

used_map(16bit)はused_bitmaps[0]〜[15]のpresence bit(存在ビット)です。used_mapが1となるビットに対応するused_bitmapsのみが出力データに含まれます。compress.c 505行目。

used_bitmaps(16〜256bit)は入力データ中に(ビット位置に対応する)シンボルが存在するかどうかを表します。compress.c 510行目。

huffman_groups(3bit)はマルチプルハフマン符号化で使用するハフマンテーブルの数です。compress.c 519行目。

selector_used(15bit)はハフマンテーブルを割り当てた(MTF変換後のデータを50シンボル毎に区切った)ブロックの数です。compress.c 520行目。

selector_list(1〜6 * selector_used bit)はブロックに割り当てたハフマンテーブルの番号です。厳密には、テーブル番号をMTF変換した後にデルタ符号化した値です。compress.c 521〜524行目。

huffman_trees (可変長ビット) はハフマンテーブルです。huffman_groups個のハフマンテーブル毎のシンボルと符号長の組です。compress.c 531〜539行目。

huffman_encoded_data(可変長ビット)はハフマン符号化された圧縮データ本体です。compress.c 548〜593行目

参考
https://github.com/dsnet/compress/blob/master/doc/bzip2-format.pdf
https://en.wikipedia.org/wiki/Bzip2#File_format

コードの紹介

BZ2_compressBlock() @ compress.c
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L602

  602: void BZ2_compressBlock ( EState* s, Bool is_last_block )
  603: {

入力データ900,000バイト毎にBZ2_compressBlock () が呼び出されます。
(900,000は、コマンドラインオプションで変更できます)

  604:    if (s->nblock > 0) {
  605:

s->nblockが0の時に呼び出されることはある？ブロックにデータが1つでもある時。lastblockの時、テイラだけ書き出すことがある?

入力データブロックが存在する時、このブロックを実行します。

  606:       BZ_FINALISE_CRC ( s->blockCRC );

s->blockCRCは、(ランレングス符号化前の)入力データブロックのCRCです。
bzip2では、AutoDIN II多項式で生成したCRCを利用します。

bzlib_private.h
  162: #define BZ_FINALISE_CRC(crcVar)                \
  163: {                                              \
  164:    crcVar = ~(crcVar);                         \
  165: }

  607:       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
  608:       s->combinedCRC ^= s->blockCRC;

s->combinedCRCは入力データのCRCです。

  609:       if (s->blockNo > 1) s->numZ = 0;
  610:

s->numZは、出力バッファに書き出したデータサイズです。0で初期化します。
ここで、s->blockNo > 1 としている理由は不明です。
s->blockNoが1の時はprepare_new_block()@bzlib.cで初期化しているためでしょうか。

  611:       if (s->verbosity >= 2)
  612:          VPrintf4( "    block %d: crc = 0x%08x, "
  613:                    "combined CRC = 0x%08x, size = %d\n",
  614:                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
  615:

s->blockNoは入力データブロックの番号です。入力データブロックのCRC s->blockCRCとこれまでの入力データのCRC s->combinedCRC、入力データブロックのシンボル数(バイト数)s->nblock を表示します。

  616:       BZ2_blockSort ( s );

入力データブロックをブロックソートします。
s->origPtrに、オリジナルデータのソート後の巡回行列の行番号が入ります。

  617:    }
  618:
  619:    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
  620:

入力データブロック配列s->arr2 の後尾を、出力バッファs->zbitsとします。

  621:    /*-- If this is the first block, create the stream header. --*/
  622:    if (s->blockNo == 1) {

入力データブロック番号が1、つまり初めてBZ2_compressBlock()が呼ばれた時、出力バッファの先頭にヘッダ情報を書き出します。

  623:       BZ2_bsInitWrite ( s );

出力バッファを初期化します。

  624:       bsPutUChar ( s, BZ_HDR_B );
  625:       bsPutUChar ( s, BZ_HDR_Z );
  626:       bsPutUChar ( s, BZ_HDR_h );
  627:       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );

ヘッダ情報(“BZ”、”h”、’1’〜’9’)を書き出します。

628:    }
629:
630:    if (s->nblock > 0) {
631:

入力データブロックが存在する時、このブロックを実行します。TODO 補足必要

  632:       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
  633:       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
  634:       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
  635:

ブロックヘッダのマジックナンバー(0x314159265359)を書き出します。

  636:       /*-- Now the block's CRC, so it is in a known place. --*/
  637:       bsPutUInt32 ( s, s->blockCRC );
  638:

入力データブロックに対応するCRCを書き出します。

  639:       /*--
  640:          Now a single bit indicating (non-)randomisation.
  641:          As of version 0.9.5, we use a better sorting algorithm
  642:          which makes randomisation unnecessary.  So always set
  643:          the randomised bit to 'no'.  Of course, the decoder
  644:          still needs to be able to handle randomised blocks
  645:          so as to maintain backwards compatibility with
  646:          older versions of bzip2.
  647:       --*/
  648:       bsW(s,1,0);
  649:

ランダム化ビットに0(不使用)をセットします。1.0.6ではランダム化を使用しません。

  650:       bsW ( s, 24, s->origPtr );

ブロックソート逆変換で必要となるs->origPtrを書き出します。これは、ブロックソート後のオリジナルデータの(巡回行列の)行番号です。

  651:       generateMTFValues ( s );

MTF変換を行います。

  652:       sendMTFValues ( s );

ハフマン符号化を行い、伸長に必要な情報と符号化したデータを出力バッファに書き出します。

  653:    }
  654:
  655:
  656:    /*-- If this is the last block, add the stream trailer. --*/
  657:    if (is_last_block) {
  658:

最後の入力データブロックの場合、テイラ情報を書き出します。

  659:       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
  660:       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
  661:       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );

テイラのマジックナンバー(0x177245385090)を書き出します。

  662:       bsPutUInt32 ( s, s->combinedCRC );

入力データ全体に対応するCRCを書き出します。

  663:       if (s->verbosity >= 2)
  664:          VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );

入力データ全体に対応するCRCを表示します。

  665:       bsFinishWrite ( s );

書き出しバッファをバイトアライメントにパディングします。

  666:    }
  667: }

まとめ

bzip2の圧縮ファイルの形式について紹介しました。