bzip2を読む MTF3

こんにちは、junkawaです。

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

generateMTFValues() MTF変換部分

本記事では、generateMTFValues() 関数の 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#L163
〜
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/compress.c#L231

  163:    for (i = 0; i < s->nblock; i++) {
  164:       UChar ll_i;

  165:       AssertD ( wr <= i, "generateMTFValues(1)" );

ソート済みブロック番号 UInt32 ptr[i] を読み出して、MTF変換して UInt16 mtfv[wr] に書き出します。

アサートの意味としては、ptr と mtfv は同じメモリ領域を参照しているため、wr > i となると、ptr から読み出す前に mtfv へ書き込んでしまい、まだ読み出していない ptr の領域を破壊してしまう、ということだと思います。

しかし ptr[i] は UInt32型で、mtfv[wr]は UInt16型です。したがって、wr*2 <= i が正しいアサート条件ではないでしょうか。

bzip2-0.9.0でも同様の型で、同様のアサート条件になっていました。

備考

ランレングス符号化を考慮すると、連続するシンボル’はさらに短いバイト数に変換されます。したがって、実際の書き込み数 <= wr*2 <= i 、となります。

  166:       j = ptr[i]-1; if (j < 0) j += s->nblock;

ptr[i] はソートされた、i番目に小さい行の先頭ブロック番号です。

ここで、ブロックソート変換の出力は、巡回行列の行のソート後の、「最後の列」です。

各行は入力データブロックを1シンボルずつずらして生成され、末尾は入力データを巡回して埋められます。

したがって、各行の最後のシンボルは、block[ ptr[i] - 1 ] で得られます。

また、ptr[i]が0の場合、ptr[i]-1は-1となるので、巡回して s->nblock-1 としています。

図より、「巡回行列の行番号-1」が各行の末尾のシンボルを指すことが分かります。

一番上の行番号10では、末尾 r は、block[10-1] の block[9] となります。
ptrを使ってソート順に考えると、先頭は ptr[0] で、行番号10です。
したがって、ソート順で先頭の行の末尾は、block[ ptr[0] - 1 ] となります。

  167:       ll_i = s->unseqToSeq[block[j]];

block[j] は、ブロックソート変換後のi番目のシンボルです。これを連続シンボル’ ll_i に変換します。

  168:       AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
  169: 

シンボル’ は 0〜s->nInUse-1なので、ll_i < s->nInUse を確認しています。

  170:       if (yy[0] == ll_i) { 
  171:          zPend++;

yy[0] は1回前のループのll_iです。204行目でセットされます。また、初期値は0です。

前回と今回のll_iが同じ場合、つまり2回連続で同じシンボル’ が続いた場合、zPendをインクリメントします。ループ初回時は、ll_iが0の場合にzPendをインクリメントします。

zPendは、シンボル’の連続回数-1となります。

例) 2が、4回連続(2,2,2,2)の時、zPend = 3

  172:       } else {
  173: 

このブロックは、前回のシンボル’ と今回のシンボル’ ll_i が異なる場合に実行されます。

  174:          if (zPend > 0) {
  175:             zPend--;
  176:             while (True) {
  177:                if (zPend & 1) {
  178:                   mtfv[wr] = BZ_RUNB; wr++; 
  179:                   s->mtfFreq[BZ_RUNB]++; 
  180:                } else {
  181:                   mtfv[wr] = BZ_RUNA; wr++; 
  182:                   s->mtfFreq[BZ_RUNA]++; 
  183:                }
  184:                if (zPend < 2) break;
  185:                zPend = (zPend - 2) / 2;
  186:             };
  187:             zPend = 0;
  188:          }

zPendが1以上、つまり前回までに何回か連続で同じシンボル’が続いた場合、ここでランレングス符号化してmtfvに出力します。

本来のMTF符号化では、入力データが連続する場合、連続する0値に符号化します。bzip2では入力データが連続している場合、ランレングス符号化(Run Length Encoding, RLE) で符号化します。

入力データが値3で10回連続する(zPend=9)場合、下記となります。

入力データ [3,3,3,3,3,3,3,3,3,3]
bzip2のMTF+RLE [0,1,0] (下記参照)

BZ_RUNA、BZ_RUNB は、bzlib_private.hで定義されます。

bzlib_private.h

  118: #define BZ_RUNA 0
  119: #define BZ_RUNB 1

mtfv[]は出力データ、wrは書き出すデータ位置。s->mtfFreq[i]はデータiの出現回数(後でハフマン符号化時に使用)です。

上記処理のランレングス符号化の結果を記します。

RLE符号化後の列の表記 [x1,x2,x3] は、mtfv[wr++] = x1、mtfv[wr++] = x2、mtfv[wr++] = x3 となるような値の出力結果です。

ランレングス符号化は様々な実現方法がありますが、ここでの方法はゼロレングスエンコーディング(Zero Length Encoding, ZLE) です。

ZLEについては、下記サイトを参考にしました。
いつも勉強させていただいている、 広井 誠さんのホームページです。

正の整数を 2 進数で表す場合、最上位ビットは常に 1 なるので省略することが可能です。Zero Lenght Encoding では、個数 N に 1 を加えて最上位以外のビットを出力しています。
http://www.geocities.jp/m_hiroi/light/pyalgo29.html

引用文中の個数Nが、zPendとなります。

zPendに1を加えた数は、シンボルの連続回数です。

このシンボルの連続回数を2進表現にして、最上位ビット以外のビット(表中の下線のついた部分)を下位ビットから出力したものが、RLE符号化後の値となります。

  189:          {
  190:             register UChar  rtmp;
  191:             register UChar* ryy_j;
  192:             register UChar  rll_i;
  193:             rtmp  = yy[1];
  194:             yy[1] = yy[0];
  195:             ryy_j = &(yy[1]);
  196:             rll_i = ll_i;
  197:             while ( rll_i != rtmp ) {
  198:                register UChar rtmp2;
  199:                ryy_j++;
  200:                rtmp2  = rtmp;
  201:                rtmp   = *ryy_j;
  202:                *ryy_j = rtmp2;
  203:             };
  204:             yy[0] = rtmp;
  205:             j = ryy_j - &(yy[0]);
  206:             mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
  207:          }
  208: 
  209:       }

この処理でやりたいことは下記のとおりです。

　・リストyyから ll_i の位置を取得し、mtfv[wr] にセットする
　・ll_i をリストyyの先頭に移動する

190〜192行でローカル変数 rtmp、ryy_j、rll_i を定義しています。変数名の先頭にrがついているのは、変数が register 修飾子付きで宣言されているからだと思われます。

193,194行でリストyyの先頭(yy[0])の値を1番目(yy[1])に入れます。

195行目でポインタ ryy_j にリストの1番目のアドレス(&(yy[1]))を入れます。
このポインタ ryy_j を上手く使って、リスト中のll_iの位置を取得します。

196行目で ll_i を rll_i にセットしています。これは register 修飾子で宣言した変数 rll_i を使うことで高速化を狙ったものだと思われます。

197行目では、変換対象のシンボル’ rll_i が、リスト yy 中で見つかるまで(while (rll_i != rtmp))、リストを辿っています(ryy_j++)。rtmpは今見ている、リスト中の値です。

また、リストを辿るついでに、要素を後ろに一つずつずらし、セットしていきます。202行目で、今見ているrtmp2を、次に見るリストの位置ryy_jにセットします。

204行目でyy[0] に変換対象の値ll_i(whileループを抜けたときにはrtmpはll_iと同じ)をセットしています。

whileループを抜けた時点で、ryy_jは、値ll_iがあったyy中の場所を指しています。

MTFでは、対象の値(ll_i)を入力とし、リストyyの先頭からの位置を出力とします。
先頭からの位置は、値ll_iのあったリスト要素を指すアドレスryy_jから、リストの先頭アドレス&(yy[0])を引いた値となります。

205行目で、j = ryy_j - &(yy[0]) としてMTF変換後の値 j を求めています。

yy は Uchar型の配列であるため、アドレスの差分がそのまま要素の番号となります。

206行で出力データ(mtfv[wr])、出現回数(s->mtfFreq[j+1])をセットします。

mtfv[wr] = j+1; の +1 について説明します。

j = ryy_j - &(yy[0]); かつ、ryy_jの初期値は&(yy[1])なので、jは1以上の値となります。

mtfv[]には0以上の値が入りますが、0と1はゼロランレングスでのRUNAとRUNBに使用されているため(予約されているため)、0、1以外の値を使う必要があります。

本来のMTFにて0は、前回と同じ値が出た時。1は、今回の値がリストの先頭から1番目 (yy[1])に出た時となります。

ゼロランレングスにて前回と同じ値が出た時に0(RUNA)と1(RUNB)を使用しているので、bzip2では、リストの先頭からの距離に1を加えた値を出力するようにしています。

もちろん伸長ではこれを意識して処理する必要があります。具体的には、伸長処理のdecompress.c:427で対応しています。
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/decompress.c#L427

  210:    }
  211: 

  212:    if (zPend > 0) {
  213:       zPend--;
  214:       while (True) {
  215:          if (zPend & 1) {
  216:             mtfv[wr] = BZ_RUNB; wr++; 
  217:             s->mtfFreq[BZ_RUNB]++; 
  218:          } else {
  219:             mtfv[wr] = BZ_RUNA; wr++; 
  220:             s->mtfFreq[BZ_RUNA]++; 
  221:          }
  222:          if (zPend < 2) break;
  223:          zPend = (zPend - 2) / 2;
  224:       };
  225:       zPend = 0;
  226:    }
  227: 

ここの処理は174〜188行と全く同じです。

174〜188行は、連続した値の後で、異なる値があった場合に入る処理なので、連続した値の後で、異なる値を検出しない場合、ランレングス符号化されないまま163〜210行のforループを抜けてしまいます。

ここでは、入力データブロックの最後が連続していた場合に、それらをランレングス符号化します。

  228:    mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
  229: 

出力データの最後に、EOBをセットします。

EOBは、s->nInUse+1 です。

s->mtfFreq[EOB]++で、シンボルEOBの出現回数を記録しています。EOBもハフマン符号化の対象であるためです。

  230:    s->nMTF = wr;

出力データの長さ(wr)をs->nMTFに保存します。

これで、MTF符号化が完了します。

備考

伸長時のMTF逆変換に必要な情報は下記となります。

　・mtfv[0..wr-1]
　・s->inUse

s->inUseから、seqToUnseq(s->unseqToSeqの逆)、s->nInUse、EOBを導出できます。

伸長時のリストyyは、for(i=0; i<s->nInUse; i++) yy[i] = i; で生成できます。

データからEOBが見つかるまでMTF逆変換を行い、生成したデータ(シンボル’)をseqToUnseqによってシンボルに変換します。

伸長時のMTF逆変換については、別の記事で紹介します。
decompress.c の 423 でMTF逆変換を行っています。
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/decompress.c#L423

  231: }

まとめ

MTF変換の実装について紹介しました。

次回は、ハフマン符号について紹介します。