tek1​/adv0

tek1の続き

• ここでは全体像に影響しない、より些末なことを書く

符号寿命

• まず最初は以下の符号寿命が初期値として設定されている。
  • 符号寿命A：2048
  • 符号寿命B：512
• また圧縮コード内では寿命が次のようにエンコードされている。
  • （ここでは下位を右側に書くために、ストリームを右から左へ記述していることに注意）

           0 : 直前の寿命と同じ寿命
         001 : 直前の寿命の2倍
         011 : 直前の寿命の半分
        1111 : 寿命は無限大
        0111 : リザーブ
     0000101 : リザーブ
     0001101 : 直前の寿命に4bitの符号付き整数を加算したものが今回の寿命（4bitが後続）
     0010101 : 上記の8bit版
     0011101 : 上記の12bit版
     0100101 : 上記の16bit版
     0101101 : 上記の20bit版
     0110101 : 上記の24bit版
     0111101 : 上記の28bit版
     1000101 : 直前の寿命の4倍
     1001101 : 直前の寿命の8倍
     1010101 : 直前の寿命の16倍
     1011101 : 直前の寿命の32倍
     1100101 : 直前の寿命の1/4倍（端数切捨て）
     1101101 : 直前の寿命の1/8倍（端数切捨て）
     1110101 : 直前の寿命の1/16倍（端数切捨て）
     1111101 : 直前の寿命の1/32倍（端数切捨て）

UC0符号パラメータの動的補正

概念

• UC0は0以上の整数をエンコードできる符号で、そのためにパラメータテーブルがある。このテーブルがたとえば [ 0, 4, 8, 10, 12 ] の場合、符号長は当然次のようになる。
  • 0：1bit (1+0)
  • 1-16:6bit (2+4)
  • 17-272:11bit (3+8)
  • 273-1296:14bit (4+10)
  • 1297-5392:16bit (4+12)
• しかしたとえばあるブロックの展開中でdsを読み込むとき、現在のブロック内のポインタが60バイト目であれば、当然dは-60より小さくなることはありえない。つまりdsの値は0-59の値しかありえないことになる。
• そうであれば、このテーブルを一時的にちょっと細工して、 [ 0, 4, 8 ] にしてしまおう、というのが動的補正である。これだと17-272で1bitの得がある。
• そしてさらに、59までしかないのなら、ここに8bitを割り当てるのも合理的ではないだろう。ということで、さらに補正して [ 0, 4, 6 ] にしてしまう。17-80で2bit得する（さっきのを含めると3bitの得）。

実装

• 当然実装に際しては、エンコード側とデコード側とで同じ最大値を予測していないと、食い違いが生じてデコードできなくなる。ということでそれを説明する。
  • byの値のときは、残りデコードバイト長-1が最大値（-1するのは、そもそもbyがUC0の値を+1して利用しているため）
  • lzの値のときも、残りデコードバイト長-1が最大値（-1するのは、そもそもlzがUC0の値を+1して利用しているため）
    • 実はlzの最大値はこれよりも小さくなる場合もありうるが（コピー長の最小が1ではない場合があり、2だったり3だったりするから）、そのために除算をすると展開速度が落ちるし、そこまでしても得られる圧縮率改善はあまりに些細なので、上記のようになっている。
  • dsの値のときは、概念のところで紹介した59を算出する方法でおこなう。つまり結果的にはコピーを開始するバイトポインタ値-1（60-1=59）。
  • cpの値は(残りデコードバイト長)-(コピー長の最小)が最大値
• 次にデコードの高速化のテクニックについて説明する。
  • 毎回UC0のデコードパラメータを再構築していたら圧倒的に時間の無駄であり、展開速度に影響する。
  • by、lz、cpでは、ブロックのデコードとともに最大値が小さくなっていくという性質がある。したがって、デコードの際は、最大値がいくつよりも小さくなったら再構築が必要かを変数に入れておき、その値に達するまでは再構築ルーチンをスキップすればよい。これで展開速度低下は事実上なくなる。
  • dsでは、これとは逆にブロックのデコードとともに最大値が大きくなっていくという性質がある。したがって現在の修正UC0パラメータで表現可能な最大値を控えておき、これよりも予測最大値が大きくなったら再構成を行えばよい。

UC0符号パラメータのフォーマット

基本

• ここは結構ややこしい。ブロックサイズが最大8MBなので、UC0でエンコードされる数字も最大で8M程度までありうるが、これはつまりパラメータテーブルの各要素を単純に並べて最後にターミネータをつけるような方法だと、1要素あたり5bitを要し、 [ 0, 4, 8, 10, 12 ] なら30bitも要してしまうことになる。これは4バイト近くであり、こんなものをそのまま使うわけにはいかない。
  • 短くエンコードできれば、パラメータ切り替えのオーバヘッドが減り、寿命を短く設定できるようになり、つまりそのときそのときでの最適なパラメータを使う機会が増え、結果的に圧縮率が上がるというわけである。
  • またここが少々ややこしかったとしても頻度は低いので展開速度に影響しにくい。だから遠慮なく（？）短く表現することを心がけた。
  • ここに示す方法では [ 0, 4, 8, 10, 12 ] を19bitで表現できる（1101010001000010010）。
  • 30→19ではたいした事はないと思うかもしれないが、 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] も19bitになるので（1111111111111010010）、ここの複雑さに失望しないでほしい（まあtek1の中で一番複雑だというだけで、本質的にはそんなに複雑ではないのだが。Cのソースで50行ほど）。これは70→19に匹敵する。

モードヘッダ

• 最初はモードヘッダである。上記の例だと最初の0010の4bitがこれに相当。
  • （ここでも下位を右側に書くために、ストリームを右から左へ記述していることに注意）
  • モード0とモード1

         001 : パラメータの最大値は 0- 4、モード0
         101 : パラメータの最大値は 0- 4、モード1
         011 : パラメータの最大値は 5- 8、モード0
         111 : パラメータの最大値は 5- 8、モード1
        0010 : パラメータの最大値は 9-12、モード0
        1010 : パラメータの最大値は 9-12、モード1
        0110 : パラメータの最大値は13-16、モード0
        1110 : パラメータの最大値は13-16、モード1
       00100 : パラメータの最大値は17-20、モード0
       10100 : パラメータの最大値は17-20、モード1
       01100 : パラメータの最大値は21-24、モード0
       11100 : パラメータの最大値は21-24、モード1

  • ここまでのまとめ：
    • 最後のビット（一番左のビット）がモードに対応している
    • また最後から2番目のビット（左から2番目のビット）が1だとパラメータの最大値の上限は8の倍数、0だと8の倍数+4
    • 残りの部分（最初の部分）については、1の数を数えて0がきたら終わりで、パラメータの最大値が8づつ増えている。
  • モード2

       01000 : パラメータの最大値は 0- 4、モード2
       11000 : パラメータの最大値は 5- 8、モード2
      010000 : パラメータの最大値は 9-12、モード2
      110000 : パラメータの最大値は13-16、モード2
     0100000 : パラメータの最大値は17-20、モード2
     1100000 : パラメータの最大値は21-24、モード2

  • ここまでのまとめ：
    • 最初の3bitはすべて000
    • モードは2しかない
    • ちょうど上記でモードビットを外して最初に000をつけた形式になっている

本体

• 基本的な考えとしては、パラメータ値そのものではなく、前の項から次の項を求めるための差分をエンコードしていく感じになる
  • 大雑把な傾向として、パラメータ列の値はその前後の値に近くなるため
• モード0では、この差分値を1以上の整数のみで表す（若干の例外はある）
• モード1では、この差分値を0以上の整数のみで表す
• モード2では、この差分値に符号ビットがあるため、正と零はもちろんのこと負の整数も使える
• 初項も統一的な方法で求めるために0番目の項より前にも仮想的な項が存在すると仮定する
  • この仮想的な項は0とする
• デコード方法0：
  • モード0で、さらに直前の項が0でない場合はこれになる
  • "1"がくるまでの"0"の数を数えて、それにさらに1を加えたものが差分値
• デコード方法1：
  • モード1か、もしくはモード0かつ直前の項が0の場合はこれになる
  • "1"がくるまでの"0"の数を数えたものが差分値
• デコード方法2：
  • モード2の場合はこれになる
  • まず最初は符号ビット、これが0なら0以上、これが1なら-1以下
  • "1"がくるまでの"0"の数を数えて、符号ビットが1だったらさらにそれに-1をXORしたものが差分値
• (註)モード0でも直前の項に限ってデコード方法1になるのは、パラメータの最初の項のほうに0をいくつか並べたいときがあるからである
• ターミネーション（終端処理）
  • パラメータの終わりを表すには、いくつかの方法があり、そのどれでもよい
  • モード0で、たとえばパラメータの最大値の範囲が9-12の場合、もし12という内容の項をデコードし終わったら、もう次の項はありえないのでターミネーションとなる
    • 13以上になるはずがないため
    • この終端方法はモード0でしか使えないし、しかも最後のパラメータが4の倍数のときにしか使えない
  • これはどのモードでも使える方法だが、たとえばパラメータの最大値の範囲が9-12の場合、次の項が13となるようなそんな差分を受け取ったとしよう、これはもちろんありえないのでターミネーションする
    • この場合13になるのに必要なだけの"0"を数えたら、もう"1"を待たずに打ち切る
    • 14などをエンコードする意味はないので、もはやターミネーションのための13しかありえず、最後の"1"が省略されているとみなすのである
  • モード2で、次の項が-1となるようなそんな差分を受け取ったとしよう、これもありえないのでターミネーションする
    • この場合も-1になるのに必要なだけの"0"を数えたら、もう"1"を待たずに打ち切る
    • 前の項が0だった場合、符号ビットが1だった時点でもう打ち切る

フッタ

• 特定の条件でのみフッタが存在する
  • モード0かモード1で、パラメータの数が2つ以上で、さらに最後のパラメータが0ではないとき
• フォーマットは例によって"1"がくるまで"0"の数を数えるというものである
• この値を、最後のパラメータから差し引く
  • モード0やモード1ではパラメータが増える一方で最後を小さい値にすることができないため
  • 最後だけ減少で、あとはパラメータを増加させたいという状況が結構あるのでこの仕組みがある
  • 差し引く前の最後のパラメータが10だとしたら、当然"0"の数は10より多いことはありえないので、"0"が10個続いたら"1"は省略されているとみなして1ビット節約する

デフォルトパラメータ

• これだけの圧縮をしてパラメータを短くまとめても、それでも対tek0では小さいファイルで負ける
  • なぜならtek0はパラメータが固定されており、圧縮ファイル内に書かなくていい分だけ有利だからである
  • ある程度の大きさ以上ではtek0に負けることはまったくないが
  • しかしtek0を破棄してtek1への移行を推進するにはやはりほぼ全てのケースでtek1のほうが高圧縮であるべきだろう
• ということで考え出されたのがデフォルトパラメータである
  • これは非常に短い形式で圧縮ファイル内に記述できる
  • デフォルトとしては平均的な内容のものを選んでいる
  • これにより小さいファイルでの圧縮率が改善したのはもちろんであるが、大きなファイルも必要に応じてこのパラメータを利用することでさらに圧縮率が改善した
• デフォルトパラメータも含めてUC0パラメータのエンコードフォーマットをストリーム順に説明すると次のようになる
• 更新ビット
  • このビットが0のとき、寿命にもかかわらず、パラメータを更新しないことを意味する
  • これはたまたま圧縮対象の統計的性質が変わらなかった場合などに、同じことを何度も書くのを回避するためである
  • このビットが0なら、以降のフィールドはすべてない
  • ブロックの一番最初では必ずパラメータを設定しなければいけないので、このビットはない
• 非デフォルトビット
  • このビットが1なら、直後から上記で説明したUC0パラメータの圧縮コードが始まる
  • このビットが0なら、デフォルトパラメータ利用ということで複数用意されたデフォルトのうちのどれなのかを記述するコードが続く
  • (1)byかlzのとき：
    • 3bitのパラメータがあり、仮にこれが0なら [ 1, 2, 3, 4, 5, 6, 7, 8, ... ] というのを指定したことになる。
    • これが3なら [ 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, ... ] を意味する
    • すなわち、最初に0が0～7個並び、そのあとは1から順に1づつ増えるようなパラメータである
  • (2)dsのとき：
    • デフォルトは一種類しかないので、追加のパラメータはない
    • デフォルトの内容は [ 0, 4, 8, 10, 12, 14, 16, 18, 20, 22, 24 ] である
  • (3)cpのとき：
    • 2bitのパラメータがあり、それぞれの意味は次の通り：
    • 00：[ 1, 2, 3, 4, 5, 6, 7, 8, 9, ... ]
    • 01：[ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, ... ]
    • 10：[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ... ]
    • 11：リザーブ
• cpの場合に限り、2bitのcp最低値フィールドがある
  • 非デフォルトビットの値にかかわらず、このフィールドはある
  • 更新ビットが0の場合は、このフィールドもない
  • ここの値に+1したものがcpの最低値となる
    • つまり1～4

最低保証値

• tek1は非常にスケーラブルな形式であり、展開ルーチン側の負担は小さくないと思うので、ここで一つ基準を設ける。
  • これは汎用の場合の最低値規定であって、対象データが限定される場合はこの限りではない。
• UC0のパラメータテーブルは最低でも32個（＝0番から31番）は利用可能でなければいけない。それ以上は環境によってサポートがあったりなかったりしてよい。
• スライド辞書のバッファサイズ（＝MD値）は最低で32KBである。32bit環境であれば（かつメモリの制約が厳しくないなら）、1MBくらいまではサポートしてほしいところである。
• 対応可能ファイルサイズについては最低でも2GB、符号寿命の値、およびby、lz、cpの値は最低でも24bitは利用できることを保証すること。
• tek1hについては、レベル0のみ（＝tek1hのノンサポート）であってもよいが、できればレベル2くらいまでのサポートがあるほうが好ましい。

tek1h

こめんと欄