こんばんは、川合です。
先日までせっせとtek4の最終仕上げをしていましたが、どうも満足で
きる圧縮率になりませんでした。どうもUC0やUC1を一度捨てることも視
野に入れて、やり直す必要がありそうです。これはかなり長期戦になり
そうな気がしてきました（半年とか）。半年もメインの開発を中断しつ
づけるわけには行きませんので、tek4の開発は後回しにするべきだとい
う結論に達しました。
またtek3はtek4に近いアルゴリズムにすることが僕の希望なので、
tek4が決まらなければtek3も決められないということになります。とい
うことで、tek3とtek4は当面白紙です。tek2は結構いいのですが、ちょ
っとだけ引っかかっているところがあるので、まだ保留です。
一方、tek1は我ながらバランスに優れたいい出来で問題はなさそうな
ので、これはフォーマット確定ということにします。いや、厳密に言う
と、フォーマット確定はtek1ではなくstk1ですが。フルセット仕様であ
るtek1のほうは、まだいろいろテストしたいことが残っているので、確
定しないでおきます。とにかくtek1もstk1の範囲で使う分には全く問題
ないわけです。
OSASKやKHBIOSでも、とりあえずはstk1をサポートします。たぶんあ
る時点でstk1のサポートからtek1のサポートに繰り上げると思いますが
その場合は上位互換になりますので、問題はないわけです。
それで、結局新規に確定したフォーマットがstk1だけということにな
ってしまうと、圧縮率でtek0の代用になるものがないということになっ
てしまい、これでは相変わらずtek0が使いつづけられてしまいます。展
開の遅いtek0を使われるくらいなら、速度は同じくらいだけど圧縮率の
高いLZMAのほうがマシです。
それで、そういえばいつかLZMAライクな圧縮形式をtek5として作ろう
と思っていたことを思い出し（つまり、「スライド辞書法＋レンジコー
ダもしくは算術圧縮」）、いっそのこと、それを今作ってしまおうと思
いました。もちろんゼロから作るのは途方もない時間がかかりますが、
幸いLZMAのソースがLGPLで公開されていますので、これをちょっと手直
しすれば良さそうです。
ASKA版のデコーダを途中まで書いてみて、これはデコードするときの
ことをあまり考えていないなと思いました。よっぽどへんな仕様のCPU
でないかぎり（繰り下がり時にキャリーフラグが0になるなんていう仕
様でない限り・・・というかそんなCPUは存在するのか？）、今のLZMA
の仕様は展開しにくいです。どうしてもビット反転命令を追加しなけれ
ばいけなくなります。
ということで、デコードしやすい形式に改造しました。これで1%くら
いは展開が速く出来るでしょう（最適化が優秀ではないCコンパイラで
は、むしろ遅くなるかもしれないですが、そんなことはもちろんコンパ
イラのせいであってフォーマット仕様のせいではない）。
またスライド辞書での一致長が273バイトまでしかエンコードできな
いというさみしい制限があり（ちなみにこの手の制限はよくある制限で
LHAなどもそうです）、そのせいで圧縮率で損をしているようでした。
ということでフォーマットをいじって一致長の制限をなくしました。こ
れで、bim2binc以外のすべてで圧縮率が改善しました。そんなわけで、
今回紹介するstk5はベータ版ながら多くのケースでLZMAと同じかそれを
上回る圧縮率を発揮し、しかも展開速度がLZMAよりも速いという特徴を
もちます。もっとも展開速度についてはチューンした展開ルーチンがで
きているわけではないので、確証はありませんが。
LZMA stk5
bim2binc 110.2 110.2
kdun00b 101.7 100.0
osaskgo 104.8 104.8
osask.bmp 110.0 100.4
詳しいデータはこちら：
http://wiki.osask.jp/?tek1/comp
もはやstk5に対しては、bzip2はライバルではありません（というか
LZMAがbzip2を既に打ち負かしていた）。ライバルは王者のrkだけです
。
stk5はその名のとおりtek5のサブセットですが、フルセットのtek5で
は、さらにLZMAの弱点らしきところを改良しようと予定しています。
LZMAでは僕が今までtek1〜tek4の開発を通して発見した有効なテクニッ
クの多くが使われていないのです。それは、このテクニックがレンジコ
ーダに対してはもはや足手まといになるからかもしれませんが、でもた
とえば先の273バイト制限のように、ただ試していないだけというもの
もあるわけです。そんなわけで、tek5になれば、さらに圧縮率が改善し
rkにさらに迫れるようになる可能性があります。その上、tek5になって
も展開速度はほとんど増えません（というか僕は展開速度に影響するよ
うなテクニックは知らないだけですが）。
さて現状をまとめるとこうです。
stk1 : フォーマット確定
stk2 : フォーマット検討中（変更の可能性:3%）
stk3 : フォーマット開発そのものを当面中断
stk4 : フォーマット開発そのものを当面中断
stk5 : フォーマット検討中（変更の可能性:5%）
結局tek形式は、1個増えて2個減った、という感じですね。
stk2に関しては、今のところ何も変わっていないので、今回のリリー
スは特にありません。stk5に関するリリースはこれです。
http://k.hideyosi.com/bim2bi4m.lzh (161KB)
この中には3つの実行ファイルと1つのバッチファイルがあります。い
ずれも今の暫定版のstk5を生成したり、展開させたりするためのもので
す。今回は時間がなくてbim2bin内には組み込めませんでした。
それぞれのファイルについてのライセンスは、memo.txtを読んでくだ
さい。LZMAのライブラリを使っている上に、その中で救えるものはでき
るだけKL-01にしてやろうとしているので、ライセンスがちょっとやや
こしいです。
まあ結局はこれもベータ版なのですが、まあ次バージョンではOSASK
でstk5がサポートされて、そのときになったら、今のstk5とのフォーマ
ットの互換性はないかもしれませんが、とにかくこのくらいのサイズに
圧縮して使えるようになりそうだ、ということです。その目安を知って
暇つぶしが出来る、というだけのことです。
圧縮するには、
prompt>enctk5 osask.bmp osask.tk
などとしてください。これで圧縮されます。細かいパラメータはなしで
す。とりあえずパラメータがデフォルトでも十分に圧縮されますから。
圧縮速度は、今までのbim2bin4よりもずっと速いです。これはひとえに
LZMAライブラリのおかげです。
展開するには、
prompt>tstdstk5 osask.tk osask.bmp
です。
最後に今後の予定です。まずはstk5のデコードルーチンを完成させま
す。stk5のデコードルーチンを書いているうちに、stk5フォーマットの
どこに手を加えるべきかも自然に分かると思うので、デコードルーチン
が完成すればstk5もフォーマットが確定します。
そしてstk1とstk5がOSASKに組み込まれて、やっと本来の目的の
KHBIOSの開発がはじまるわけです。
stk2については、それまでに確定すればOSASKに入れますが、確定し
ないかもしれません。確定しなければ、確定しないままにしておくつも
りです。圧縮形式の開発が主目的ではない以上、こればかりに時間をか
けてもしょうがないでしょうから。バランスの悪いtek0を引退させて、
KHBIOSでバランスのよい形式だけをサポートすることだけが重要なので
す。
それでは。
--
川合 秀実(KAWAI Hidemi)
OSASK計画代表 / システム設計開発担当
E-mail:kawai !Atmark! osask.jp
Homepage http://osask.jp/