こんばんは、川合です。
今夜はtek1を中心にあれこれ書きたいと思います。主に読み物です。
まず、tek1を使うにはどうすればいいかですが、bim2bin4のアルファ
版を使います。
http://k.hideyosi.com/bim2bi4a.lzh
prompt>bim2bin -osacmp -tek1 in:file.org out:file.tk1
などのようにすれば利用できます。復元は今までどおり-restoreででき
ます。restoreのときは-tek1などのオプションは要りません。ヘッダか
ら圧縮タイプを自動判別します。
なおOSASKがtek1に対応していないので、今のところtek1はあまり使
えません。そのうちOSASKやedimgにtek1サポートコードを追加します。
---
さて、ここからが本題です。
そもそも僕がl2d3やtek0を作った背景を、ここでざっと復習しておき
ますと、OSが展開をサポートすることは非常に意義があるという確信が
あって（それは実行ファイル内のstaticデータをパックするというのが
最初のきっかけでした）、どんな圧縮アルゴリズムをサポートするべき
か、と考えました。
もちろんメジャーで圧縮率の良いLHAやzipやbz2などを入れてしまう
というアイデアもありましたが、
・展開速度は速くなければいけない
・展開用コードは短くなくてはいけない
・展開時のワークエリアは少なくてもOKでなければいけない
の3つが非常に重要だと考え、lzhなどのメジャーな形式は展開用コード
の肥大と展開速度のバランスが悪いということで、OSに組み込まず、
DLLなどでサポートするほうがよい、と判断しました。
なにしろ圧縮は日進月歩の世界なので、たぶんたびたびサポートを切
り替える必要が出てくるでしょう。そしてOSASKとしては互換性を守る
ために古い展開形式もサポートしていくとすると（もちろんあまり使わ
れないものはAPIブリッジなどへ追い出されていくでしょうが）、基本
的に展開用ルーチンがコンパクトなほうがいいのです。
古い形式も使えるので切り替えるというよりは追加でしょうか。とに
かく新しい形式をサポートするようになると、たいてい新しいほうが圧
縮率が良いので、古い形式はお荷物になりやすいのです。
ということで手ごろな形式としてlzexpを見つけて、でも圧縮率の点
で改良の余地があったので改良してl2d3になり、さらに圧縮率を高くす
るためにtek0形式を作ってきたわけです。
さて今回tek1を作ったのですが、これは実はOSASKのための圧縮形式
ではなく、KHBIOSのための圧縮形式です。とはいうものの、もちろん
OSASKでもtek1はサポートされます。・・・いや実際のところ、OSASK
で遊んでいる分には今のtek0だけでもそんなに問題があるとは思いませ
ん（圧縮がノロマとかそういう圧縮形式に依存しない問題はありますが
）。
OSASKでの圧縮サポートはとてもうまくいっていると僕は思います。
ちいさなディスクにたくさんのファイルを詰め込めますし、遅いFDでも
アクセス時間が短縮されて高速化に貢献しています。これはOSASKだけ
のサポートに終わらせるのはもったいないので、DOSASKでもやりたいと
思いました。そしてOSASKにもDOSASKにも持たせるくらいなら、いっそ
のことKHBIOSのファンクションレベルで、圧縮展開をサポートしようと
考えたわけです。
KHBIOSというとメインはストレージデバイスの統一的なサポートです
が、これと圧縮を組み合わせると、圧縮されたディスクイメージにアク
セスする、とかができることになります。たいていどんなOSでもディス
クイメージはかさばります。だからきっと配布時には圧縮されているで
しょう。しかしこれを展開しないと使えないというのは、ちょっと不便
です。できれば解凍したイメージがなくても圧縮したイメージのままで
それぞれのOSが起動できたら便利そうではありませんか。これがきっか
けでした。
もちろんKHBIOS内の展開ファンクションはストレージアクセスとは切
り離して任意のデータの展開にも使えるので、ディスクイメージに対し
てしか利用できないわけではありません。
しかしこの目的のためにはtek0やl2d3は不便すぎました。これらの圧
縮符号は、先頭から終端までを一度に展開することだけを考えており、
まあ途中で展開を打ち切ることはできますが、途中から展開をはじめる
ことはできません。たとえば1MBの中の末尾の1KBを展開したければ、先
頭からせっせと解凍して目的のところまでやって、それでそれまでの不
要な1MB近くのコードを捨てなければいけないわけです（もちろんとっ
ておいてもいいですが）。
KHBIOSでの想定では、当然それぞれのOSがディスクを先頭のセクタか
ら順番に読んでくれる、なんていう都合の良いことを期待することはで
きません。ランダムアクセスでしょう。末尾のほうを読むたびにアクセ
スが遅くなっていたらまったく使い物になりません（いくら展開が早く
なるように設計されていても、1KBのために1MBを解凍するようなことを
していたらさすがに遅くなるのは目に見えています）。
とまあ、そんなわけで上記のほかにもKHBIOSでの利用状況を想定して
tek1は以下のような機能を持った圧縮符号にしようと思いました。
・どこからでも展開可能（セクタ単位）
・ランダムアクセスに対して展開開始位置がすぐに引けるように、
インデックスをつける
・セクタによっては圧縮・非圧縮が選べる
非圧縮セクタは書き込みも簡単にできる
・ECCやCRCを付加できるようにする
・ついでにtek0よりもさらに高速な展開を（約2倍）
・もしできたらtek0よりも高い圧縮率を
なんだかすごく欲張りな仕様ですが、なんとかできました（できたの
でこのメールを書いているわけです）。構想しはじめてから半年くらい
経っていますが、まあそれだけのものではあると思います。
どこからでも展開可能というのは、つまり圧縮前のファイルを一定の
サイズごとにブロックに分けて、それぞれをtek1s圧縮しているだけの
ことです。もちろん同一内容のブロックは同じものを何個もおいても無
駄なので、内部で共有化できます。このブロックサイズ（セクタサイズ
）は圧縮時に設定できます。IA-32の場合は4KBとかにするとページサイ
ズと同じで扱いやすくなるかもしれません（特にメモリマップトファイ
ル）。ただ当然のことながら、ブロックをこまかくすると圧縮率はそれ
なりに落ちます（圧縮というのは前後のデータの相関関係を利用してや
るものなので、相関が使いにくくなれば、あまり縮まなくなるわけです
）。
圧縮データはサイズが不ぞろいで（というかそれをそろえるためにパ
ディングしたりしたら圧縮率が落ちる！）、5780番目のブロックを解凍
したいというときに、その圧縮データ位置を手早く見つけることは、イ
ンデックスなしではできません。またインデックスは階層構造になって
いて短時間で引けるようになっています。インデックスをそのままつけ
るとバカらしいほどサイズが増えるので、tek1h圧縮してあります。
もちろんブロックサイズ以下のファイルを圧縮したときは、インデッ
クスはつきません。
ええと、無圧縮ブロック混在とかECCとかは説明しなくてもわかると
思うのでスキップ。
展開速度についてですが、これはosaskgoの展開がちょっと遅いと思
ったことがきっかけです。tek0やl2d3は圧縮データの全てをビットスト
リームとして扱っています。だから無圧縮の1バイトを持ってくるため
には8bitを処理しなければならず、まあ遅くなって当然ではあります。
tek1では、圧縮データ内の無圧縮部分を分けてバイトストリーム部分を
作りました。たいていtek0などのデータのうちの半分はこのバイトデー
タなので、面倒なbit処理が半分になり、結果的に速度が倍になるとい
うことです。
この構造のため、適当なファイルをtek1圧縮してバイナリエディタで
覗いてみると、中のバイトデータが結構読めます（ビットがずれないた
め）。hellok1.orgを圧縮したら中に"hellok"などの文字が見えます（
笑）。tek0ではたいてい読めません。また"hellok"の周辺をよく見ると
圧縮前のデータがたくさん入っています。ああこうやって圧縮されてい
るんだなってわかります。
最後の圧縮率ですが、ある程度大きなサイズならtek0に勝てます。小
さいサイズになるとtek0よりも圧縮率が悪いです。これは各種の拡張性
のために（さらにはバイトストリームとビットストリームの分離のため
に）、ヘッダがtek0よりも長くなっているせいです。ブロックサイズが
小さいと、個々のブロックの圧縮率が悪くなり、さらにはインデックス
がついたりもしてtek0に対してけっこうな差がつきます。
ということでtek1はtek0に代わるものではなく、向き不向きにあわせ
て使い分ける感じでいくのがいいと思います。
そのへんも踏まえて、いくつかのデータを挙げます。
・hellok1.orgでの比較
圧縮前: 272バイト
tek0: 128バイト
tek1: 130バイト
早速負けています。というかこのサイズで2バイト差はむしろ健闘し
ているといっていいです。ヘッダの構造を考えると、そこで5〜10バイ
トの差がついていますので。
・bball2.binでの比較
tek0: 295バイト
tek1: 303バイト
（tek1では一段目のデータ部のみの圧縮の際に
ブロックサイズ64kを指定）
staticなデータ部分は結果的に2重圧縮になりますが、そのせいで
tek1はヘッダのハンデを2度背負うことになり、惨敗。
・kdun00b.bin（アーカイブ）での比較
圧縮前: 640KB
tek0: 46246バイト
tek1: 46518バイト（ブロックサイズ32KB指定）
tek1: 45793バイト（ブロックサイズ1MB指定）
tek1もブロックサイズが十分大きくてインデックスのハンデもない状
況なら、tek0よりも圧縮率がよくなっているのがこれでわかります。な
お、このメールを書いている今わかったことですが、ブロックサイズ
32KBのほうは展開しようとするとエラーになるようです。まだまだデバ
ッグの必要ありですね。
とまあ現状はこんなところです。
それでは。
--
川合 秀実(KAWAI Hidemi)
OSASK計画代表 / システム設計開発担当
E-mail:kawai !Atmark! osask.jp
Homepage http://osask.jp/