tek1​/adv0 のバックアップソース(No.2) :: OSASK計画

• 差分^[1] を表示
• 現在との差分^[2] を表示
• tek1/adv0^[3] へ行く。

* [[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で表現できる（0010101110111100001）。
--30→19ではたいした事はないと思うかもしれないが、 [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] も19bitになるので（0000000000000100001）、ここの複雑さに失望しないでほしい（まあtek1の中で一番複雑だというだけで、本質的にはそんなに複雑ではないのだが。Cのソースで50行ほど）。これは70→19に匹敵する。
*** モードヘッダ
-最初はモードヘッダである。上記の例だと最初の0001の4bitがこれに相当。
--（ここでも下位を右側に書くために、ストリームを右から左へ記述していることに注意）
--モード0とモード1
      000 : パラメータの最大値は 4以下、モード0
      100 : パラメータの最大値は 4以下、モード1
      010 : パラメータの最大値は 8以下、モード0
      110 : パラメータの最大値は 8以下、モード1
     0001 : パラメータの最大値は12以下、モード0
     1001 : パラメータの最大値は12以下、モード1
     0101 : パラメータの最大値は16以下、モード0
     1101 : パラメータの最大値は16以下、モード1
    00011 : パラメータの最大値は20以下、モード0
    10011 : パラメータの最大値は20以下、モード1
    01011 : パラメータの最大値は24以下、モード0
    11011 : パラメータの最大値は24以下、モード1
--ここまでのまとめ：
---最後のビット（一番左のビット）がモードに対応している
---また最後から2番目のビット（左から2番目のビット）が1だとパラメータの最大値は8の倍数、0だと8の倍数+4
---残りの部分（最初の部分）については、1の数を数えて0がきたら終わりで、パラメータの最大値が8づつ増えている。
--モード2
    00111 : パラメータの最大値は 4以下、モード2
    10111 : パラメータの最大値は 8以下、モード2
   001111 : パラメータの最大値は12以下、モード2
   101111 : パラメータの最大値は16以下、モード2
  0011111 : パラメータの最大値は20以下、モード2
  1011111 : パラメータの最大値は24以下、モード2
--ここまでのまとめ：
---最初の3bitはすべて111
---モードは2しかない
---ちょうど上記でモードビットを外して最初に111をつけた形式になっている
*** 本体

*** フッタ

*** デフォルトパラメータ



* tek1h



* こめんと欄
-0 : 直前の寿命と同じ寿命,1じゃないの？ -- 別の名無しさん SIZE(10){2004-06-02 (水) 15:23:36}
-あちゃあ、ほんとだ間違えてた・・・。いやその0はあっているんですが、他が全部間違っている・・・。ご指摘ありがとうございます。 -- [[K]] SIZE(10){2004-06-02 (水) 15:29:08}

#comment

• tek1/adv0 のバックアップ一覧^[6]
• tek1/adv0 のバックアップソース(No. All)
  • 1: 2004-06-01 (火) 17:25:31^[7]
  • 2: 2004-06-02 (水) 18:36:21
  • 3: 2004-06-03 (木) 00:10:36^[8]
  • 4: 2004-06-03 (木) 14:41:04^[9]
  • 5: 2004-06-03 (木) 14:41:04^[10]
  • 6: 2004-06-07 (月) 23:14:33^[11]
  • 7: 2004-06-08 (火) 06:30:28^[12]
  • 8: 2009-11-17 (火) 12:07:37^[13]
  • 現: 2024-01-08 (月) 12:59:03^[14] ゲスト