tek1​/adv1 のソース :: OSASK計画

• 差分^[1] を表示
• tek1/adv1^[2] へ行く。

TITLE:x
* [[tek1]]の続き [#n6cd3da5]
-ここではtek0からのアイデアの連続性やその他の読み物的なことについて書く

* UC0のアイデア [#rb30220d]
-UC0符号は、tek0でのdfの発展型である。
--ここで少しおさらいしておくと、dfはd3の発展型であった。つまりd3→df→UC0ということになる。
-dfはその名のとおりd3などよりもずっとフレキシブルであり、ファイルごとに適切なパラメータを選択できるところがとてもよかった。これをぜひ他の3つのパラメータ（by、lz、cp）にも応用したいと考えたわけである。
-そこでよりいっそうフレキシブルにして、パラメータ次第でL1aやL1bにもなれるような、そんなものに拡張して、それで名前を汎用符号（ユニバーサルコード）のバージョン0ということで、UC0としたわけである。

-また展開速度の高速化にも配慮した。符号中に分散したストップビット・継続ビットは、デコードの際に取り除いて結合しなければならず、これは大きな負担である。そこでこれらの制御用ビットをざざーと先頭に集めて以下のようにした。
    1dd0dd0ddd → ddddddd100        （ビットストリームは右から左へ書いている）
//-以下はbim2bin4hで直ったので削除
//-なお、ほんの気まぐれで継続・ストップの意味が反転してしまったので、
//    ddddddd011
//-となっているが、これはもし継続ビット個数を数えるのにASKAのBSFを使うのであれば少々不便であるなと今は少し後悔している。
//--まあBSFは遅いので使うべきではないし、どうしても使いたければNOTしてからBSFすれば済むことではあるが。
//--いや、やっぱりフォーマットを変えよう。今しかフォーマットはいじれないわけだし（2004.06.03）。
-これはまさにUC0である。そして先頭にまとめることで100が先行したときのdの数と1000が先行したときのdの数との大小関係を、あえて逆転することもできるようになった（今まではもっぱらdの個数は増やしていくしかなかった）。この先行形式にしたとたんにベース値という考えも思いつけるようになった。
-思えばl2d3からtek0へ進化したときも同じような発想だった。つまり、無圧縮ヘッダ"1"と圧縮ヘッダ"0"のbitを全部前に集めてしまおうと考えて、それをL0a符号に置き換えたのである。L0aにしたことで無圧縮領域が長くなるときに"1"を並べるのではなくもっと短くすることができるようになり、tek0の圧縮率はl2d3よりもほぼ全てのケースでよくなったわけである。

-ちなみに符号寿命という考え方は、LHAがたまに静的ハフマン符号を作り直しているらしいという話を聞き、なるほど効果がありそうだと思って入れた。実験したらいろいろ分かったので、全部を一気に切り替えるのではなく、複数の寿命を扱えるようにした。

* UC0 vs ハフマン [#mf41a126]
-まず、たとえば0～255などといったある程度狭い数値しか扱わないと確実にわかっている場合、ハフマン符号のほうが圧縮率の観点では有利である。しかし、任意の32bitの数値をエンコードするなどの用途になると、もはや4G個のハフマンテーブルを並べるわけには行かず、かといって動的ハフマンでもこの数は扱いにくいし速度が出ないので、UC0が有利である。
-LHAで使われているらしい方法として、32bit数値をそのままハフマンにかけるのではなく、総ビット数（0～31）をハフマン符号で表して、後続のbitをそのままビットストリームに並べるという方法があるらしい。この場合後続は先頭の1bitは必ず"1"なのでこれを省略するようだ。この方法のほうが圧縮率がUC0よりもいいかもしれない。
-なんと言ってもハフマン符号の強みは、小さい数字ほど出現頻度が高いだろうというtek1での仮定を前提にしないところである。
-一方弱みとしては、静的ハフマンではどうしてもパラメータが多くなり（符号長リスト）、動的では展開速度が遅くなるということである。パラメータが多くなれば当然符号寿命は長くしないと割が合わない。そうなると状況に合わせてきめ細かくハフマン表を切り替えられないので、結局圧縮率はそれほど有利にはならず、結果的にtek1が善戦しているのだろう。
-ハフマンもUC0も展開速度を上げることはそんなに難しくはないが、速度を上げる方法を使うとプログラムは長くなる。速度を上げる方法を積極的に使わなくてもUC0は十分に速いが、ハフマンではtek0なみに遅くなる。

* スケーラビリティ [#c0f7596e]
-l2d3やtek0では、圧縮対象のファイルは4GBまでしか考えていなかったし、将来拡張したくなったときのための拡張フラグなどをまったく残していなかった。
-tek1では（ちなみにtek2も）、いずれは大きなディスクイメージを扱うことにも配慮し、OSACMPヘッダ部分のファイルサイズゾーンにs7s符号を使って4GB以上を表現できるようにしたし、拡張フラグ類も準備した。
-tek1は圧縮率比較表でのMD:2mに象徴されるように（註：実はファイルフォーマット的にはMDも8MBまでとれる。現在制限されているのは、圧縮ルーチン側の都合に過ぎない）、大きなバッファメモリをふんだんに使うような、そんな形式に見えるかもしれないが、それは大いなる誤解である。
--MDはmaxdisのこと。maxdisを省略して書けるようになっている。
-tek1はしょせんl2d3やtek0の子孫であり、今までどおりMD:32kやそれ未満で使うこともでき（というか、今でもデフォルトはMD:32kであるし）、この場合バッファメモリは32KBしか要しない。UC0のパラメータテーブルも4つあわせて1KB程度であり、16bit環境でも容易に展開できる。l2d3やtek0と比べて消費メモリが増えたとすれば、せいぜいこのUC0パラメータテーブル1KBであろうが、しかしこれもLHAのハフマンデコード用テーブルに比較すれば、取るに足らない大きさである。
--上記は展開時の話である。圧縮時の消費メモリ量もMDに比例する部分があるので、MD:32kなら圧縮時の消費メモリも結構少なくなる。
--さらにいえばl2d3とtek0にあってはMDに何の制限もなく、100MBでも200MBでも許していたので、こっちのほうがよっぽどリッチではある（圧縮速度の問題があるので、今まで誰もやっていなかったとは思うが）。なお、tek1の8MBという上限はBS（ブロックサイズ）の8MBに起因する。ランダムアクセスを考えると8MB以上のブロックサイズは考えにくいので、問題はないだろう。もし問題があれば、有り余る拡張bitで16MB以上のブロックサイズをサポートすれば済む。
-tek1はこのように、小規模システムから大規模システムまでを単一のアルゴリズムと単一のフォーマットのみで連続的にサポートできるところがよいのであって、実際にこのフォーマットを活用する段階で、MDはいくつ以下でなければいけないとか、BS（ブロックサイズ）はいくつ以下である必要があるなどの制限を課したり課さなかったりすればよいのである。
-LHAは16bit時代に考えられた形式だからあれでよかったとか、あれで仕方がないなどという弁護を見かけたが、それはtek0に4GB制限があるのと同レベルであって、たいした理由にはならない。いかなる時代のいかなる環境であっても、汎用フォーマットとしてスケーラブルなフォーマットを制定することはできたのであるから。
--要するにパラメータ（ファイルサイズやバッファサイズ）のフォーマットに起因する上限がなければよいだけのことである。展開のことを考えれば、もちろん何らかの上限があるほうが好ましいが、それがいつか自らの可能性を縛る壁になるので、展開ルーチン側でチェックして対応できないものはできないといわせるほうが前向きであろう。

* こめんと欄 [#edcfc8ef]

#comment

• tek1/adv1 のバックアップ一覧^[4]
• tek1/adv1 のバックアップソース(No. All)
  • 1: 2004-06-03 (木) 02:13:51^[5]
  • 2: 2004-06-07 (月) 23:41:04^[6]
  • 3: 2004-06-08 (火) 06:49:47^[7]
  • 4: 2009-11-17 (火) 12:07:37^[8]
  • 現: 2024-01-08 (月) 12:59:03 ゲスト