tek1​/adv0 をテンプレートにして作成 :: OSASK計画

開始行:
TITLE:x * [[tek1]]の続き -ここでは全体像に影響しない、より些末なことを書く * 符号寿命 -まず最初は以下の符号寿命が初期値として設定されている。 --符号寿命A：2048 --符号寿命B：512 -また圧縮コード内では寿命が次のようにエンコードされている。 --（ここでは下位を右側に書くために、ストリームを右から左... 0 : 直前の寿命と同じ寿命 001 : 直前の寿命の2倍 011 : 直前の寿命の半分 1111 : 寿命は無限大 0111 : リザーブ 0000101 : リザーブ 0001101 : 直前の寿命に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：1bit (1+0) --1-16:6bit (2+4) --17-272:11bit (3+8) --273-1296:14bit (4+10) --1297-5392:16bit (4+12) -しかしたとえばあるブロックの展開中でdsを読み込むとき、現... -そうであれば、このテーブルを一時的にちょっと細工して、 [... -そしてさらに、59までしかないのなら、ここに8bitを割り当て... *** 実装 -当然実装に際しては、エンコード側とデコード側とで同じ最大... --byの値のときは、残りデコードバイト長-1が最大値（-1する... --lzの値のときも、残りデコードバイト長-1が最大値（-1する... ---実はlzの最大値はこれよりも小さくなる場合もありうるが（... --dsの値のときは、概念のところで紹介した59を算出する方法... --cpの値は(残りデコードバイト長)-(コピー長の最小)が最大値 -次にデコードの高速化のテクニックについて説明する。 --毎回UC0のデコードパラメータを再構築していたら圧倒的に時... --by、lz、cpでは、ブロックのデコードとともに最大値が小さ... --dsでは、これとは逆にブロックのデコードとともに最大値が... * UC0符号パラメータのフォーマット *** 基本 -ここは結構ややこしい。ブロックサイズが最大8MBなので、UC0... --短くエンコードできれば、パラメータ切り替えのオーバヘッ... --またここが少々ややこしかったとしても頻度は低いので展開... --ここに示す方法では [ 0, 4, 8, 10, 12 ] を19bitで表現で... --30→19ではたいした事はないと思うかもしれないが、 [ 0, 1,... *** モードヘッダ -最初はモードヘッダである。上記の例だと最初の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だ... ---残りの部分（最初の部分）については、1の数を数えて0がき... --モード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だったらさ... -(註)モード0でも直前の項に限ってデコード方法1になるのは、... -ターミネーション（終端処理） --パラメータの終わりを表すには、いくつかの方法があり、そ... --モード0で、たとえばパラメータの最大値の範囲が9-12の場合... ---13以上になるはずがないため ---この終端方法はモード0でしか使えないし、しかも最後のパ... --これはどのモードでも使える方法だが、たとえばパラメータ... ---この場合13になるのに必要なだけの"0"を数えたら、もう"1"... ---14などをエンコードする意味はないので、もはやターミネー... --モード2で、次の項が-1となるようなそんな差分を受け取った... ---この場合も-1になるのに必要なだけの"0"を数えたら、もう"... ---前の項が0だった場合、符号ビットが1だった時点でもう打ち... *** フッタ -特定の条件でのみフッタが存在する --モード0かモード1で、パラメータの数が2つ以上で、さらに最... -フォーマットは例によって"1"がくるまで"0"の数を数えるとい... -この値を、最後のパラメータから差し引く --モード0やモード1ではパラメータが増える一方で最後を小さ... --最後だけ減少で、あとはパラメータを増加させたいという状... --差し引く前の最後のパラメータが10だとしたら、当然"0"の数... *** デフォルトパラメータ -これだけの圧縮をしてパラメータを短くまとめても、それでも... --なぜならtek0はパラメータが固定されており、圧縮ファイル... --ある程度の大きさ以上ではtek0に負けることはまったくないが --しかしtek0を破棄してtek1への移行を推進するにはやはりほ... -ということで考え出されたのがデフォルトパラメータである --これは非常に短い形式で圧縮ファイル内に記述できる --デフォルトとしては平均的な内容のものを選んでいる --これにより小さいファイルでの圧縮率が改善したのはもちろ... -デフォルトパラメータも含めてUC0パラメータのエンコードフ... -更新ビット --このビットが0のとき、寿命にもかかわらず、パラメータを更... --これはたまたま圧縮対象の統計的性質が変わらなかった場合... --このビットが0なら、以降のフィールドはすべてない --ブロックの一番最初では必ずパラメータを設定しなければい... -非デフォルトビット --このビットが1なら、直後から上記で説明したUC0パラメータ... --このビットが0なら、デフォルトパラメータ利用ということで... --(1)byかlzのとき： ---3bitのパラメータがあり、仮にこれが0なら [ 1, 2, 3, 4, ... ---これが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, ... --(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である... -対応可能ファイルサイズについては最低でも2GB、符号寿命の... -tek1hについては、レベル0のみ（＝tek1hのノンサポート）で... * tek1h * こめんと欄 #comment

終了行:
TITLE:x * [[tek1]]の続き -ここでは全体像に影響しない、より些末なことを書く * 符号寿命 -まず最初は以下の符号寿命が初期値として設定されている。 --符号寿命A：2048 --符号寿命B：512 -また圧縮コード内では寿命が次のようにエンコードされている。 --（ここでは下位を右側に書くために、ストリームを右から左... 0 : 直前の寿命と同じ寿命 001 : 直前の寿命の2倍 011 : 直前の寿命の半分 1111 : 寿命は無限大 0111 : リザーブ 0000101 : リザーブ 0001101 : 直前の寿命に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：1bit (1+0) --1-16:6bit (2+4) --17-272:11bit (3+8) --273-1296:14bit (4+10) --1297-5392:16bit (4+12) -しかしたとえばあるブロックの展開中でdsを読み込むとき、現... -そうであれば、このテーブルを一時的にちょっと細工して、 [... -そしてさらに、59までしかないのなら、ここに8bitを割り当て... *** 実装 -当然実装に際しては、エンコード側とデコード側とで同じ最大... --byの値のときは、残りデコードバイト長-1が最大値（-1する... --lzの値のときも、残りデコードバイト長-1が最大値（-1する... ---実はlzの最大値はこれよりも小さくなる場合もありうるが（... --dsの値のときは、概念のところで紹介した59を算出する方法... --cpの値は(残りデコードバイト長)-(コピー長の最小)が最大値 -次にデコードの高速化のテクニックについて説明する。 --毎回UC0のデコードパラメータを再構築していたら圧倒的に時... --by、lz、cpでは、ブロックのデコードとともに最大値が小さ... --dsでは、これとは逆にブロックのデコードとともに最大値が... * UC0符号パラメータのフォーマット *** 基本 -ここは結構ややこしい。ブロックサイズが最大8MBなので、UC0... --短くエンコードできれば、パラメータ切り替えのオーバヘッ... --またここが少々ややこしかったとしても頻度は低いので展開... --ここに示す方法では [ 0, 4, 8, 10, 12 ] を19bitで表現で... --30→19ではたいした事はないと思うかもしれないが、 [ 0, 1,... *** モードヘッダ -最初はモードヘッダである。上記の例だと最初の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だ... ---残りの部分（最初の部分）については、1の数を数えて0がき... --モード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だったらさ... -(註)モード0でも直前の項に限ってデコード方法1になるのは、... -ターミネーション（終端処理） --パラメータの終わりを表すには、いくつかの方法があり、そ... --モード0で、たとえばパラメータの最大値の範囲が9-12の場合... ---13以上になるはずがないため ---この終端方法はモード0でしか使えないし、しかも最後のパ... --これはどのモードでも使える方法だが、たとえばパラメータ... ---この場合13になるのに必要なだけの"0"を数えたら、もう"1"... ---14などをエンコードする意味はないので、もはやターミネー... --モード2で、次の項が-1となるようなそんな差分を受け取った... ---この場合も-1になるのに必要なだけの"0"を数えたら、もう"... ---前の項が0だった場合、符号ビットが1だった時点でもう打ち... *** フッタ -特定の条件でのみフッタが存在する --モード0かモード1で、パラメータの数が2つ以上で、さらに最... -フォーマットは例によって"1"がくるまで"0"の数を数えるとい... -この値を、最後のパラメータから差し引く --モード0やモード1ではパラメータが増える一方で最後を小さ... --最後だけ減少で、あとはパラメータを増加させたいという状... --差し引く前の最後のパラメータが10だとしたら、当然"0"の数... *** デフォルトパラメータ -これだけの圧縮をしてパラメータを短くまとめても、それでも... --なぜならtek0はパラメータが固定されており、圧縮ファイル... --ある程度の大きさ以上ではtek0に負けることはまったくないが --しかしtek0を破棄してtek1への移行を推進するにはやはりほ... -ということで考え出されたのがデフォルトパラメータである --これは非常に短い形式で圧縮ファイル内に記述できる --デフォルトとしては平均的な内容のものを選んでいる --これにより小さいファイルでの圧縮率が改善したのはもちろ... -デフォルトパラメータも含めてUC0パラメータのエンコードフ... -更新ビット --このビットが0のとき、寿命にもかかわらず、パラメータを更... --これはたまたま圧縮対象の統計的性質が変わらなかった場合... --このビットが0なら、以降のフィールドはすべてない --ブロックの一番最初では必ずパラメータを設定しなければい... -非デフォルトビット --このビットが1なら、直後から上記で説明したUC0パラメータ... --このビットが0なら、デフォルトパラメータ利用ということで... --(1)byかlzのとき： ---3bitのパラメータがあり、仮にこれが0なら [ 1, 2, 3, 4, ... ---これが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, ... --(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である... -対応可能ファイルサイズについては最低でも2GB、符号寿命の... -tek1hについては、レベル0のみ（＝tek1hのノンサポート）で... * tek1h * こめんと欄 #comment

ページ名: