tek1 :: OSASK計画

tek1の技術的情報

• (by K, 2004.05.31)
• 以下ほとんど現状とマッチしていません。そのうち対処します。

• そのうち書くと思うドキュメントの下書き
• フォーマットに関する情報以外は、このページではなくimpressionsなどにお願いします。
• ここでは展開手順をベースに書きます。圧縮のほうは、この展開手順で展開できるようなファイルを作ればいいだけですので。

• bim2bin4hで一部ビットの意味が反転したので訂正。

tek1圧縮

• tek1は、次の1バイトから始まります。
  • 註：OSACMP形式はこの1バイトに先立って16バイトのシグネチャとnバイトの展開後のサイズに関する情報が付属する。これについては後述。
  • bit0：1です。もしここが0ならそれは拡張情報をもつ先行バイトで、以下の意味を持つのはbit0が1になっているバイトです。
    • 実はこの先頭バイト自身がs7s符号になっている。
  • bit1：1です。tek2ではここが0になる場合もありますが、tek1では常に1です。
  • bit2-5：ブロックサイズです。0001ならブロックサイズ512バイト、0010なら1KB、・・・0111ならブロックサイズ32KB、・・・1111ならブロックサイズ8MBです。
  • bit6：通常は0です。1だとブロックごとに圧縮形式が変えられるモードです。
  • bit7：通常は0です。1だと以下の「tek1s x ブロック数」が始まる直前に、これをスキップするためのs7s符号が先行します（ECCなどがある場合はtek1sのかたまりのあとにまとめておかれるので、そこへアクセスするために存在する）。
• tek1では展開後のサイズに関する情報はフォーマットの中には含まれません。これは展開時に既知であるとします。OSACMP形式の場合はOSACMPヘッダの中に展開後のサイズが記録されているので問題ありません。
• その展開後のサイズを上記のブロックサイズで割って、いくつのブロックがアーカイブに含まれるか計算します。このブロック数によって、これ以降のフォーマットが決まります。
  • レベル0フォーマット：1ブロック
  • レベル1フォーマット：2～256ブロック
  • レベル2フォーマット：257～65536ブロック
  • レベル3フォーマット：63357～16777216ブロック
  • 以下略
• 一般的に言って、レベル0フォーマットが一番単純で圧縮率も高いですが、部分解凍ができないのでランダムアクセス性能は劣ります。またブロックサイズは最大でも8MBなので8MBを超えるファイルはレベル0を選べないことになります。
  • ブロックサイズのところで0000をリザーブしてあるので、これをブロックサイズ無限大にしようかとは思っていますが、とりあえず今は未定です。これがあるとどんな大きいファイルもレベル0でかけることにはなります。でもあちこちで最大ブロック長8MBを前提にしたフォーマットになっているのでその辺も直さないといけなさそうですが。
• このレベルに関してですが、デコーダ、エンコーダともこれらの全てのレベルに対応しなければいけないというわけではありません。サブセットであってもいいのです。これが複雑だといって別の形式を考えたり、さらにはそれがtek1のサブセットよりもへぼい圧縮率になってしまうくらいなら、たとえば、tek1でレベルは常に1でブロックサイズは常に4KBにしたもの、みたいな感じで使えばいいでしょう。
• これはレベルだけではなく、以降の他のことについても同様です。

• レベル0の場合、次のバイトからtek1sフォーマットになります。
• レベル1の場合、次のバイトからは以下のようになります。
  • (1)s7s符号で書いた(2)の長さ
  • (2)tek1h
  • (3)tek1s x ブロック数
• レベル2の場合、次のバイトからは以下のようになります。
  • (1)s7s符号で書いた(2)の長さ
  • (2)tek1h
  • (3)s7s符号で書いた(4)の長さ
  • (4)tek1h x (2～256個)
  • (5)tek1s x ブロック数
• レベル3の場合、次のバイトからは以下のようになります。
  • (1)s7s符号で書いた(2)の長さ
  • (2)tek1h
  • (3)s7s符号で書いた(4)の長さ
  • (4)tek1h x (2～256個)
  • (5)s7s符号で書いた(6)の長さ
  • (6)tek1h x (257～65536個)
  • (7)tek1s x ブロック数
• tek1hの役割は、ランダムアクセスの際にブロックがどこから始まっているかを手早く見つけるためのもので、256個以上の場合は階層を成します。
• 最初のバイトでbit7が1だった場合、tek1sが始まる直前にs7s符号がおかれますが、その値は、「tek1s群の総サイズ（バイト単位）-1」です。
• また上記で示されるtek1h群の長さは実際のバイト数から2を減じて記載されています。

tek1s

• これが圧縮の核となる部分です。その他はヘッダのようなもので、圧縮としては本質的な部分ではありません。
• tek1sの最初はs7符号になっていて、まずはこれを取得します。これはビットストリーム部分が何バイトであるかという情報で、これに2を加えたバイト数がビットストリーム部分の長さです。その直後がバイトストリームになっているので、バイトストリームが必要になったらここから1バイトずつ読んでいきます。
• s7符号の直後がビットストリームです。バイトストリーム以外はここからビット単位で読みます。

tek1s圧縮の基礎

• 基本はtek0とまったく同じです。単に符号化の方法がUC0符号に統一されただけです。それと符号寿命という概念があるので、それが付け加えられてはいますが。

• 展開アルゴリズム：
  • (1)まず符号寿命Aと符号寿命Bを寿命切れにセット（これらはただの整数カウンタです）。
  • (2)もし符号寿命Aが寿命切れだったら、byとlzのUC0符号パラメータとこれらの寿命を読み込む。
    • フォーマット的には、寿命、by、lzの順番
  • (3)符号寿命Aを1カウント進めて年をとらせる。
  • (4)byの値を整数で取得。その値に1を足す。
  • (5)(4)で求めたバイト数だけ、バイトストリームから持ってきて展開（これが無圧縮部分）。
  • (6)もしこの時点で展開バイト数に達していたら展開終了。
  • (7)lzの値を整数で取得。その値に1を足す。この回数だけ(8)～(12)を繰り返す。
  • (8)もし符号寿命Bが寿命切れだったら、dsとcpのUC0符号パラメータとこれらの寿命を読み込む。
    • フォーマット的には、寿命、ds、cp、cpの最低値(2bit)の順番
  • (9)符号寿命Bを1カウント進めて年をとらせる。
  • (10)dsの値を整数で取得。これに-1をXOR。そうすると、-1以下の整数になる。これをdとしよう。
  • (11)cpの値を整数で取得。
  • (12)(11)の回数だけ *p = *(p + d); p++; をやる。スライド辞書展開部分。
  • (13)もしこの時点で展開バイト数に達していたら展開終了。
  • (14)(2)へ戻る。

s7s符号

• これはtek0で出てきたs8符号の7bit版だと思えば理解が早いでしょう。
  • (1)1バイト読む。
  • (2)最下位のbitを捨てる（全体を右シフト）。
  • (3)捨てたビットが1ならおしまい。
  • (4)また1バイト読むために256倍しておいて、(1)に戻ったときにはこの下位8bitに読み込ませる。
  • (1)に戻る。
• 雰囲気としては、こうです。

      aaaaaaa0 bbbbbbb0 cccccccc1  → aaaaaaabbbbbbbccccccc

• 結果的に上位下位の関係がインテル風じゃないところだけに注意。

s7符号

• s7s符号にちょっと細工します。
  • s7sで読み取った際に1バイトで終わったのなら0を加える。
  • s7sで読み取った際に2バイトで終わったのなら0x80を加える。
  • s7sで読み取った際に3バイトで終わったのなら0x4080を加える。
  • s7sで読み取った際に4バイトで終わったのなら0x204080を加える。
  • s7sで読み取った際に5バイトで終わったのなら0x10204080を加える。
  • 以下略。

UC0符号

• 0以上の整数を符号化するものです。多くのパラメータを持っているので、そのパラメータによっていろいろな状況にマッチします。
• デコード方式は基本的に次のとおりです（実際は1bitずつ読まずに数ビットずつ処理して高速化しますが）。
  • 最初に1bitずつ読み込んで、"0"のbitがいくつ続くかを数えます。"1"を読み込んだらそこでストップです。たとえばこれが3個だとしましょう。
  • 次にパラメータテーブルを見て、3番目のパラメータがなんであるかを調べます。ここではこれが8だったとしましょう。
  • そしたらビットストリームから8bitを読み込みます。これは0～255ですね。それに3番目のベース値を足します。おしまいです。
• ベース値は、次のようにパラメータテーブルから自動で決まります。
  • まず0番目のベースは必ず0です。
  • そして0番目のパラメータと0番目のベース値とで、最大いくつまで表現できるかを計算し、それより1大きい数を1番目のベース値にします。
  • 今度は1番目のパラメータと1番目のベース値とで、最大いくつまで表現できるかを計算し、それより1大きい数を2番目のベース値にします。
  • 以下同じように3番目、4番目、・・・のベース値が求められます。これらは符号パラメータを読み込んだときに計算しておけばいいでしょう。
• なおn番目のパラメータが0の場合もあります。この場合、1bitも読みません。だから0にベース値を足します。

• たとえばパラメータテーブルが10個しかないときは、最大でも9番目までしかありえないので、最初の"0"を数えるループで"0"の数が9個になったら、次の"1"は省略されているものとみなします。これで1ビット節約しています。
  • 同様にもしパラメータテーブルが2個しかないときは、最大が1番目なので、"0"が1個きたらもうそれでおしまいですし、最初が"1"ならそれは0番目なので、それでもおしまいです。だから、最初の"0"数え部分では結局1bitしか読まないことになります。
  • さらにもしパラメータテーブルが1個しかないときは、もはや"0"の数を数えるまでもなく"1"がくるはずなので、この"1"は省略されたものとみなし、1bitも読むことなく、いきなり0番目のテーブルを参照します。

• 圧縮の際には、たとえば0をたくさん符号化したいと思えば、パラメータテーブルの0番目を0にすればいいわけです。そうすれば整数0は1+0=1bitで符号化できます。
• また小さい数はあまり出てこないけど、100くらいの数字がたくさん出てくる場合は、パラメータテーブル0を7とかにしておくわけです。そうすると0-127は1+7=8bitで符号化できます。

OSACMP形式

• 16バイトのシグネチャ：

   83 FF FF FF 01 00 00 00 4F 53 41 53 4B 43 4D 50

• そしてこのあとに展開後のファイルサイズがs7sでかかれている。それだけ。

この他の細かいことは以下で

• tek1​/adv0 ： 残りのフォーマット
• tek1​/adv1 ： tek0からの進歩の流れ
• tek1​/adv2 ： 補助バッファ利用について
• tek1​/comp ： 他のフォーマットとの比較表

こめんと欄

• tek1 -- 名無しさん 2009-07-10 (金) 10:25:25