bzip2を読む ハフマン符号8

こんにちは、junkawaです。

本記事では、ハフマン符号後のデータを出力バッファに書き出す処理について紹介します。

コードの紹介

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

  544:    /*--- And finally, the block data proper ---*/

MTF変換後のデータをハフマン符号化して書き出します。

  545:    nBytes = s->numZ;

現在の出力バッファのサイズs->numZをnBytesに保存します。

  546:    selCtr = 0;
  547:    gs = 0;

selCtrは(MTF変換後のデータを50シンボル毎に分割した)ブロック番号です。0で初期化します。

gsはブロックの開始シンボル番号です。0で初期化します。

  548:    while (True) {

全ブロックのハフマン符号化したシンボルを書き出すまでループを回します。

  549:       if (gs >= s->nMTF) break;

gsがMTF後データのシンボル数(s->nMTF)を超えた場合、書き出しが完了したとして、ループを抜けます。

  550:       ge = gs + BZ_G_SIZE - 1;
  551:       if (ge >= s->nMTF) ge = s->nMTF-1;

今回のループでは、s->mtfv[gs]〜s->mtfv[ge]のシンボルを書き出します。

551行目で、geがMTF後のシンボル数を超えた場合、最後のデータとなるs->nMTF-1としています。

  552:       AssertH ( s->selector[selCtr] < nGroups, 3006 );
  553:

ブロックselCtrに割り当てたハフマンテーブルs->selector[selCtr](0〜nGroups-1)がnGroups未満であることを確認します。

  554:       if (nGroups == 6 && 50 == ge-gs+1) {
  555:             /*--- fast track the common case ---*/

nGroupsが6で、ブロックのシンボル数が50の時、処理を高速化できます。
ループを展開することで処理を高速化しています。

  556:             UInt16 mtfv_i;
  557:             UChar* s_len_sel_selCtr
  558:                = &(s->len[s->selector[selCtr]][0]);
  559:             Int32* s_code_sel_selCtr
  560:                = &(s->code[s->selector[selCtr]][0]);
  561:

s_len_sel_selCtrは、ハフマンテーブルselCtrの符号長配列の先頭ポインタです。

s_code_sel_selCtrは、ハフマンテーブルselCtrの符号配列の先頭ポインタです。

  562: #           define BZ_ITAH(nn)                      \
  563:                mtfv_i = mtfv[gs+(nn)];              \
  564:                bsW ( s,                             \
  565:                      s_len_sel_selCtr[mtfv_i],      \
  566:                      s_code_sel_selCtr[mtfv_i] )
  567:

BZ_ITAH(nn)では、シンボルmtfv[gs+nn]をハフマンテーブルsetCtrで符号化した符号s_code_sel_selCtr[mtfv_i] を、出力バッファに書き出します。

シンボルmtfv[gs+nn]は、符号長 s_len_sel_selCtr[mtfv_i]、符号s_code_sel_selCtr[mtfv_i] で書き出されます。

  568:             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
  569:             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
  570:             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
  571:             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
  572:             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
  573:             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
  574:             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
  575:             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
  576:             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
  577:             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
  578:

mtfv[gs]〜mtfv[ge](mtfv[gs+49])のシンボルを、ハフマンテーブルsetCtrで符号化し、出力バッファに書き出します。

  579: #           undef BZ_ITAH
  580:

BZ_ITAHをundefします。

  581:       } else {
  582: 	 /*--- slow version which correctly handles all situations ---*/

nGroupsが6ではないか、ブロックのシンボル数が50ではない時、このブロックを実行します。

  583:          for (i = gs; i <= ge; i++) {
  584:             bsW ( s,
  585:                   s->len  [s->selector[selCtr]] [mtfv[i]],
  586:                   s->code [s->selector[selCtr]] [mtfv[i]] );
  587:          }

s->selector[selCtr]は、このブロックに割り当てたハフマンテーブルの番号です。
mtfv[i]はブロック中のシンボルです。

bsW()で、符号長s->len [s->selector[selCtr]] [mtfv[i]]ビットで、符号s->code [s->selector[selCtr]] [mtfv[i]] を出力バッファに書き出します。

  588:       }
  589:
  590:

  591:       gs = ge+1;
  592:       selCtr++;

次回ループのために、ブロックの開始シンボル番号gsを、今回のブロックの終端geの次のシンボルge+1にします。

ブロック数setCtrをインクリメントします。

  593:    }

  594:    AssertH( selCtr == nSelectors, 3007 );
  595:

ブロック数selCtrが、以前に計算したブロック数nSelectorsと一致するか確認します。

  596:    if (s->verbosity >= 3)
  597:       VPrintf1( "codes %d\n", s->numZ-nBytes );
  598: }
  599:
  600:

書き出したハフマン符号化データのサイズを表示します。

まとめ

本記事では、ハフマン符号後のデータを出力バッファに書き出す処理について紹介しました。

ここまでの連載で、ブロックソート、MTF変換、ハフマン符号化の処理を全て紹介しました。

次回は、ブロックソートの呼び出し元に戻って、圧縮ファイルのデータ構造という点で紹介したいと思います。