bzip2を読む ブロックソート9

こんにちは、junkawaです。

本記事では、前回に続きブロックソートアルゴリズムの「巡回行列のソート」についてソースコードを交えて紹介します。

これまでの記事

https://note.mu/junkawashima/m/m3adbdc56f010

前回までのおさらい

ブロックソートでは巡回行列のソートが必要です。

前回までは、ソートを行うmainSort()の紹介を行いました。

本記事では、mainSort()の呼び出し元のBZ2_blockSort() を紹介します。

BZ2_bockSort()では、mainSort()の呼び出し前の準備や、ブロックソート逆変換に必要な情報の準備などを行います。

ソースコード紹介

BZ2_blockSort()@blocksort.c
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/blocksort.c#L1031
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/blocksort.c#L1018
〜
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/blocksort.c#L1090

 1018: /*---------------------------------------------*/
 1019: /* Pre:
 1020:       nblock > 0
 1021:       arr2 exists for [0 .. nblock-1 +N_OVERSHOOT]
 1022:       ((UChar*)arr2)  [0 .. nblock-1] holds block
 1023:       arr1 exists for [0 .. nblock-1]
 1024: 

図の青い部分に、意味にある情報が入っています。

領域の確保は、BZ2_bzCompressInit() @ bzlib.c で行います。
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/bzlib.c#L177

 1025:    Post:
 1026:       ((UChar*)arr2) [0 .. nblock-1] holds block
 1027:       All other areas of block destroyed
 1028:       ftab [ 0 .. 65536 ] destroyed
 1029:       arr1 [0 .. nblock-1] holds sorted order
 1030: */

図のオレンジの部分が、書き換わった部分です。

ただし、quadrantの領域については、mainSort()が実行された時だけ書き換わります。fallbackSort()が実行された時は書き換わりません。

 1031: void BZ2_blockSort ( EState* s )
 1032: {
 1033:    UInt32* ptr    = s->ptr; 
 1034:    UChar*  block  = s->block;
 1035:    UInt32* ftab   = s->ftab;
 1036:    Int32   nblock = s->nblock;
 1037:    Int32   verb   = s->verbosity;
 1038:    Int32   wfact  = s->workFactor;
 1039:    UInt16* quadrant;
 1040:    Int32   budget;
 1041:    Int32   budgetInit;
 1042:    Int32   i;
 1043: 

下記で紹介します。

 1044:    if (nblock < 10000) {
 1045:       fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );

入力データブロックサイズが10000未満の場合、fallbackSort()を行います。

 1046:    } else {
 1047:       /* Calculate the location for quadrant, remembering to get
 1048:          the alignment right.  Assumes that &(block[0]) is at least
 1049:          2-byte aligned -- this should be ok since block is really
 1050:          the first section of arr2.
 1051:       */
 1052:       i = nblock+BZ_N_OVERSHOOT;
 1053:       if (i & 1) i++;
 1054:       quadrant = (UInt16*)(&(block[i]));
 1055: 

quadrantのメモリ領域は、入力ブロックデータの終端(block[nblock-1])からOVERSHOOT領域を挟んで、2バイトアライメントされた場所から始まります。

BZ2_blockSort()のコメント部分の図を参照ください。
arr2から始まる領域で、blockはarr2の先頭を参照しています。quadrantはarr2のnblock+BZ_N_OVERSHOOTを参照しています。

このようにblockとquadrantのメモリ領域を隣接させている理由は、データキャッシュに載せやすくし、交互に行うblockの比較とquadrantの比較を高速化するためだと思われます。

 1056:       /* (wfact-1) / 3 puts the default-factor-30
 1057:          transition point at very roughly the same place as 
 1058:          with v0.1 and v0.9.0.  
 1059:          Not that it particularly matters any more, since the
 1060:          resulting compressed stream is now the same regardless
 1061:          of whether or not we use the main sort or fallback sort.
 1062:       */

（wfact-1）/ 3は、default-factor-30の遷移点をv0.1およびv0.9.0とほぼ同じ場所に置きます。
遷移とはmainSort()からfallbackSort()への切り替えのことです。

mainSort()やfallbackSort()を使用するかどうかにかかわらず、結果として得られる圧縮ストリームが同じになるため、現在では特に重要ではありません。

 1063:       if (wfact < 1  ) wfact = 1;
 1064:       if (wfact > 100) wfact = 100;
 1065:       budgetInit = nblock * ((wfact-1) / 3);
 1066:       budget = budgetInit;
 1067: 

wfactの初期値は30です。main() bzip2.c L1802
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/bzip2.c#L1802

bzip2の隠しオプション --exponential をつけて実行すると fwact=1となります。main() bzip2.c L1921
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/bzip2.c#L1921

wfactの値によってbudgetが決定します。wfactが小さいほどbudgetが小さくなり、fallbackSort()への切り替えが発生しやすくなります。

 1068:       mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );

mainSort()を実行します。

 1069:       if (verb >= 3) 
 1070:          VPrintf3 ( "      %d work, %d block, ratio %5.2f\n",
 1071:                     budgetInit - budget,
 1072:                     nblock, 
 1073:                     (float)(budgetInit - budget) /
 1074:                     (float)(nblock==0 ? 1 : nblock) ); 

budgetInit-budgetは、mainSort() で消費されたbudget。
nblockは入力ブロック数。

 1075:       if (budget < 0) {

mainSort()から呼び出されるmainGtU()で比較中に同じパターンが連続する同士行を比較した場合に budgetはデクリメントされます。

ここでは、budgetが負数になった場合にmainSort()を中断し、 fallbackSort()に切り替えます。mainSort()で途中までソートした結果はptrに保存されているので、そのまま利用されます。

 1076:          if (verb >= 2) 
 1077:             VPrintf0 ( "    too repetitive; using fallback"
 1078:                        " sorting algorithm\n" );

繰り返しが多発したために fallback ソートアルゴリズムに切り替えたことを表示します。

 1079:          fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
 1080:       }

fallbackSort() を実行します。
s->arr1は ptr、s->arr2は blockです。

 1081:    }
 1082: 

下記は、mainSort()かfallbackSort()が完了した後の処理です。

 1083:    s->origPtr = -1;
 1084:    for (i = 0; i < s->nblock; i++)
 1085:       if (ptr[i] == 0)
 1086:          { s->origPtr = i; break; };

巡回行列のソート後、オリジナルの入力データの行(block[0]、行番号0から始まる行)が、何番目にソートされたかを調べ、結果を s->origPtr に保存します。

s->origPtr は出力ファイルに書き込みます。

圧縮ファイルの伸長時、bunzip2 のブロックソート逆変換では、この値が必要になります。

ブロックソートでは行のソート後、最後の列が出力するデータとなります。

bzip2では、この最後の列に対して、MTF変換を行います。

図は、入力データブロックが block[11] = [a,b,r,a,c,a,d,a,b,r,a] の例です。

図のように、ptr にはソートした順番に行番号が入っています。

図の例では、s->origPtr は 2 となります。

ptrを使って、ブロックソート変換後の出力(最後の列) lastRow を得る方法は下記のとおりです。

for (i=0; i<nblock; i++) {
   int j = ptr[i] -1 ; if (j < 0) j+=nblock;
   lastRow[i] = block[j];
}

ptr[i] には、ソート順でi番目の行番号が入っています。block[ ptr[i]-1 ] によって、この行の最後のシンボルを参照できます(巡回行列なので)。

図の例では、行番号10の行では、block[9] が行の最後のシンボルとなります。

ブロックソート BZ2_bockSort() の結果は、ptr と origPtr となります。

 1087: 
 1088:    AssertH( s->origPtr != -1, 1003 );

オリジナルのデータの行番号が見つからなかった場合アサートします。

 1089: }
 1090: 

まとめ

本記事では、ブロックソートを行う関数 BZ2_blockSort() について紹介しました。

次回は、fallbackSort()について紹介する予定です。

お楽しみに。