SPECjvm98 _201_compress ソース解説

仕事と趣味の関連で Java のベンチマークである compress のソースを読んだので自分用メモ。compress のソースが手元に無いと全く意味不明だろう。単に compress のアルゴリズムを知るだけなら http://www.dogma.net/markn/articles/lzw/lzw.htm が非常にわかりやすい。

Main#main()

runBenchmark() に引数をそのまま渡して呼ぶだけ。引数の形式は、 files ...

Main#runBenchmark()

Harness#inst_main() を引数をそのまま渡して呼ぶだけだが、引数が無い場合はデフォルト引数の設定をする。spec.harness.Context.getSpeed() の値によってデータセットのサイズが変わる。デフォルトは100。サイズ100の場合、5つのファイル圧縮伸張を5回繰り返す。

Harness#inst_main()

run_compress() を引数をそのまま渡して呼ぶだけだが、その前後を System.currentTimeMillis() で挟んで実行時間を計測する。返り値は実行時間。

Harness#run_compress()

外側で指定された回数だけループを回る。その内側のループで指定されたファイルを順番に圧縮伸張する。最内ループでは fill_text_buffer() を呼んでファイルをbyte バッファに読み込み、Compress#spec_select_action() を引数 COMPRESS で呼んで もう一つの byte バッファに圧縮して格納する。バッファの順序を入れ替えてもう一度 spec_select_action() を引数 UNCOMPRESS で呼んで伸張する。伸張したバイトサイズが元のファイルのサイズと違っていたらエラー。

Compress

基本的にhttp://www.dogma.net/markn/articles/lzw/lzw.htmのまんま。最初は9ビットで始めて、最大16ビットまで可変長。ブロック圧縮も行う。すなわち、16ビットに達した後に圧縮率が低下したらテーブルをクリアして9ビットから始める。コード256はクリアに使うので、普通のコードは257から始まる。

Compress#spec_select_action()

Input_Buffer と Output_Buffer のインスタンスを割り当ててから、引数によって Compressor#compress() か Decompressor#decompress() を呼ぶ。結果のバイト数を返す。

Input_Buffer, Output_Buffer

byte バッファへのバイトの読み書きを支援するだけ。

Compressor#

Hash_Table と Code_Table を割り当て、3バイトのヘッダを出力する。

Hash_Table

コード＋1文字の検索を行うためのクローズドハッシュ表。16ビットぶんを格納するのに十分なサイズのエントリ（69001個）を始めから割り当てておく。

Code_Table

圧縮時：この表のi番目のエントリはハッシュ表のi番目のエントリに対応するコードを格納する。伸張時：コードに対応する文字列を出力する際にコード → prefixコード ＋ suffix1文字 の表を用いるが、prefixコードを格納するのに用いる。

Compressor#compress()

全体のほとんどはハッシュ表を検索するための処理である。コード＋新たに読んだ1文字がハッシュ表にある限りは文字を読んで連結する。ハッシュ表に無かったらその時点のコードを output() で出力し、その時の1文字を新たなコードとする。また、16ビットで満杯になるまでは Hash_Table と Code_Table に新たなエントリを追加し続ける。満杯になった後は CHECK_GAP = 10000 文字ごとに cl_block() を読んで、圧縮率をチェックしてテーブルをクリアするかどうか判断する。ハッシュのアルゴリズムの勘所はよくわからないが、最初は1文字を8ビット左シフトしてコードと XOR を取っている。それで見つからない場合は disp ごとにマイナス方向へエントリを検索する。この部分が compress() の最内ループ。

Compressor#output()

n_bits ビット（9ビット〜16ビット）のコードを byte 型のバッファであるbuf にパックしてから出力するメソッド。buf の長さは 16*8=128 ビットだが、n_bits*8 ビット貯まったら出力する。つまり、1バイトの倍数になったら出力する。インスタンス変数 offset が buf 内に何ビット書き込んだかを覚えておく。buf への書き込みはコードの LSB から。buf の中のバイトも LSB 側から用いられる。最後のコードはバイト単位に切り上げて出力する。また、コードのビット幅を増やしたりテーブルをクリアするのもoutput() の中で行われるが、その際には buf の中身はフラッシュされる。書き出すのは n_bits*8 ビットなので、後ろの方にはゴミデータが出力されると思われる。

Compressor#cl_block()

出力バイト数に対する入力バイト数の比率を求め、それが前回のチェックポイントより下がったらハッシュ表をクリアする。コードは9ビットに戻り、クリアコードである 256 が出力される。比率を求める際に浮動小数点命令を使わないために少し苦労している。

Decompressor#

3バイトのヘッダをチェックする。tab_prefix, tab_suffix, de_stack を初期化する。

Suffix_Table

この表のi番目のエントリはコード i に対応する文字列の最後の1文字を保持する。0〜255番目のエントリは0〜255で初期化される。

De_Stack

伸張時にはあるコードに対応する文字列を出力する必要がある。tab_suffix と tab_prefix を用いるとあるコードに対応する最後の1文字と残りの部分（prefix）のコードがわかる。つまり最後の文字から順に判明していくため、それをスタックに入れて最後に pop して実際に出力する。

Decompressor#decompress()

getcode() でコードを一つ読み込み、tab_prefix と tab_suffix を引いてde_stack に文字を push() していく。最後の文字まで見つかったら pop() しつつ出力バッファに書き込む。また、テーブルが16ビットで満杯になるまでは tab_prefix と tab_suffix に新しいエントリを追加していく。クリアコードが来た場合は tab_prefix をクリアして（これは必要ない気が）、getcode() でもう一つコードを読み込む。KwKwK パターンの場合、Kw が一つ前のコード、KwK が新しく来たコードである。新しく来たコードに対応する文字列を後ろから順に同定していくのだから、まず K を push() しておいてからコードを Kw とする。あとは普通の場合と同じ処理をすればよい。

Decompressor#getcode()

Compressor#output() と逆のビット処理をする。クリアコードが来た場合とバッファ中のコードを全部処理した場合とビット幅が足りなくなった場合は新たに n_bits*8 ビット読み込む。