bzip2を読む MTF2

こんにちは、junkawaです。

本記事では、Move To Front (MTF) 変換についてソースコードを交えて紹介します。

目次

makeMaps_e()
generateMTFValues() 変数初期化部分

makeMaps_e()

makeMaps_e()では、MTF変換で使用する変数 s->unseqToSeq の用意を行います。
後述のgenerateMTFValues()から呼び出されます。

s->unseqToSeq は、非連続(unsequence)なシンボルを、連続(sequence)なシンボル’ へ変換するために使用します。

本連載では、連続値へ変換したシンボルを、シンボル’ と表記します。

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

https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L100
〜
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L117

  100: /*---------------------------------------------------*/
  101: /*--- The back end proper                         ---*/
  102: /*---------------------------------------------------*/
  103: 

  104: /*---------------------------------------------------*/
  105: static
  106: void makeMaps_e ( EState* s )
  107: {
  108:    Int32 i;
  109:    s->nInUse = 0;
  110:    for (i = 0; i < 256; i++)
  111:       if (s->inUse[i]) {
  112:          s->unseqToSeq[i] = s->nInUse;
  113:          s->nInUse++;
  114:       }
  115: }
  116: 
  117: 

入力データブロックにシンボルiが含まれている時、s->inUse[i]は1。含まれていない時、s->inUse[i]は0となります。

s->inUse は、ADD_CHAR_TO_BLOCK()、add_pair_to_block()@ bzlib.c でセットされます。
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/bzlib.c#L260
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/bzlib.c#L216

あるシンボル(0〜255のいずれか)が入力データブロックに含まれない場合、シンボルの集合は非連続の値の集合となります。

シンボルiを s->unseqToSeq[i] で変換したシンボル’ では、0〜s->nInUse-1の連続したシンボル’ の集合となります。

図では、説明のためにあまり現実的ではない例を載せています。

s->inUse[1]、s->inUse[5]、s->inUse[6]、s->inUse[7] のみが 1 となっています。
これは、入力データ中にシンボル1、5、6、7 のみが含まれている場合です。

s->unseqToSeq[1]が0、s->unseqToSeq[5]が1、s->unseqToSeq[6]が2、s->unseqToSeq[7]が3、s->nInUse が 4 となります。

s->unseqToSeq を使うことで、シンボル1、5、6、7 を、シンボル’ 0、1、2、3 に変換できます。

入力データに含まれないシンボルは、符号化されることがない情報のため、無駄です。
無駄なシンボルの情報を取り除いたシンボル’を使用することで、MTF変換とハフマン符号化での処理の高速化と圧縮率の向上が図れます。

圧縮データを元のデータに戻す伸長時のために、圧縮データにs->inUseを含めます。

generateMTFValues() 変数初期化部分

generateMTFValues() では、MTF変換を行います。

本記事では、MTF変換に必要な変数の初期化部分を紹介します。

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

https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L118
〜
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L162

  118: /*---------------------------------------------------*/
  119: static
  120: void generateMTFValues ( EState* s )
  121: {
  122:    UChar   yy[256];

yyはMTF変換で使用するリストです。

  123:    Int32   i, j;
  124:    Int32   zPend;
  125:    Int32   wr;
  126:    Int32   EOB;
  127: 

  128:    /* 
  129:       After sorting (eg, here),
  130:          s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
  131:          and
  132:          ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] 
  133:          holds the original block data.
  134: 

ブロックソートの後

s->arr1 は、s->ptr のことです。

入力データブロックを巡回行列化して、各行を辞書順にソートした結果が s->ptr に入っています。s->ptr には、各行の先頭ブロック番号が入ります。

s->arr2 は、(UChar*)s->block [ 0.. s->nblock-1 ]です。
入力データブロックが s->block に入っています。

  135:       The first thing to do is generate the MTF values,
  136:       and put them in
  137:          ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
  138:       Because there are strictly fewer or equal MTF values
  139:       than block values, ptr values in this area are overwritten
  140:       with MTF values only when they are no longer needed.
  141: 

MTF変換では、変換後の出力を s->ptr に保存します。

しかし、s->ptr にはBWT変換でソートした後の出力が入っているので、適切な順番で s->ptr から値を取り出して、MTF値を生成して、s->ptr へ保存する必要があります。

BZ2_bzCompressInit() @ bzlib.c

  199:    s->mtfv              = (UInt16*)s->arr1;

MTF変換後の出力は s->mtfv に保存します。これはs->arr1 (=s->ptr)と同じ領域です。

mtfvをptrと同じ領域にする理由は、メモリ使用量を減らすため以外に、TLBミス、キャッシュミスを減らして処理を高速化するためだと思われます。

  142:       The final compressed bitstream is generated into the
  143:       area starting at
  144:          (UChar*) (&((UChar*)s->arr2)[s->nblock])
  145: 

MTF変換後、ハフマン符号化で圧縮したビットデータは、入力データブロックの後ろに出力します。

BZ2_compressBlock() @ compress.c

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

入力データブロックの終端はs->block[s->nblock-1]で、その次のバイトs->block[s->nblock]から後ろにデータを出力します。

  146:       These storage aliases are set up in bzCompressInit(),
  147:       except for the last one, which is arranged in 
  148:       compressBlock().
  149:    */

s->mtfv、s->ptr、s->block などは、BZ2_bzCompressInit() でセットします。

s->zbits は、BZ2_compressBlock() でセットします。

  150:    UInt32* ptr   = s->ptr;

BWT変換後のソート済みのブロック番号の配列です。

  151:    UChar* block  = s->block;

入力ブロックデータです。

  152:    UInt16* mtfv  = s->mtfv;
  153: 

MTF変換後の出力を保存する配列です。

  154:    makeMaps_e ( s );

非連続シンボルを連続シンボル’ に変換するための s->unseqToSeq を用意します。

  155:    EOB = s->nInUse+1;
  156: 

MTFでは、連続シンボル’ 0〜s->nInUse を使って変換を行います。

シンボル’ 0〜s->nInUse-1 を、0〜s->nInUse-1のリスト位置に変換します。

MTFと同時に行うランレングス符号化(ゼロランレングス)により、リスト位置0が連続する場合に0、1の2進値に変換します。

2進値1と、リスト位置1を区別するために、1〜s->nInUse-1のリスト位置に+1して、2〜s->nInUse として出力されます。

伸長時に、シンボル’ の終端を見つけるためのシンボルとして EOB を用意します。
EOBは、0〜s->nInUseとは異なる値にする必要があるので、s->nInUse+1 としています。

EOBの取りうる最大値は、257となります。これは入力データに全シンボルが含まれている場合です。この時、s->nInUseは256となり、EOBは257となります。
(英語版WikipediaではEOBが258だとありますが、これは誤りだと思われます)
https://en.wikipedia.org/wiki/Bzip2

MTF変換後の値が0〜257となるので、UChar型では収まりません。したがって、MTF変換後の値を格納する mtfv配列は、UInt16型となっています。

  157:    for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
  158: 

後でハフマン符号化に使用するために、シンボル’ (0〜s->nInUse,EOB)の出現頻度をs->mtfFreqに保存します。
ここではs->mtfFreqを0で初期化します。

  159:    wr = 0;

wr は、MTF変換後の出力データ数です。
MTF変換後のデータは、mtfv[wr] に書き込みます。

  160:    zPend = 0;

zPend はリスト位置 0 が連続した時にインクリメントします。
ランレングス符号化で使用します。

  161:    for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
  162: 

リストyyを初期化します。

まとめ

makeMaps_e()とgenerateMTFValues() 変数初期化部分を紹介しました。

次回は、MTF変換の実装を紹介します。