s7sの改良ネタ

  • (by K, 2007.03.02)

(1) tc203

  • 最初は1bit。それを2^0.25倍して任意の単位に切り上げる。そういうヘッダをつける。
  • バイト単位にするとするなら、こうなる。
    • 1B:0-(7) 12.500%
    • 2B:10-(14) [7*1.1892=8.3244]
    • 3B:110-(21) [14*1.1892=16.6488]
    • 4B:1110-(28) [21*1.1892=24.9732] 12.500%
    • 5B:11110-(35) [28*1.1892=33.29]
    • 6B:111110-(42) [41.6]
    • 8B:1111110-(57) [49.9] 10.938%
    • 10B:(8)-(72) [67.7]
    • 12B:(9)-(87) [85.6]
    • 15B:(10)-(110) [103.4] 8.333%

(2) tc103

  • 1B:(1)-(7)
  • 2B:(2)-(14) [7*1.41421356=9.89]
  • 3B:(3)-(21) [19.7]
  • 5B:(4)-(36) [29.6]
  • 7B:(5)-(51) [50.9]
  • 10B:(6)-(74) [72.1]

(3) eh8

  • いや待て、もっと改良できるのでは?
    • ヘッダ部分を段階的に2進化してはどうか?
  • s7sのよさは任意長にできることではなかったのか?そうすると、1.1892倍というルールは良くない。
  • 1B:0-(7) head=1bit
  • 2B:100-(13) head=2bit
  • 3B:101-(21) head=2bit
  • 4B:110-(29) head=2bit
  • 5B:111000-(34) head=3bit
  • 6B:111001-(42)
  • 7B:111010-(50)
  • 8B:111011-(58)
  • 9B:111100-(66)
  • 10B:111101-(74)
  • 11B:111110-(82) head=3bit 6.81%
  • 12B:1111110000-(86) head=4bit 10.42%
  • 13B:1111110001-(94)
  • 14B:1111110010-(102)
  • 15B:1111110011-(110) head=4bit 8.33%
  • 16B:1111110100-(118) head=4bit 7.81%
  • これは気に入った。これをeh8としてKHBIOSやkhabaで使うことにしよう。
    • とりあえず11Bまでサポートすれば十分っぽい。

(4) eh2, eh4, eh16

1W2bit: 0-(1)4bit: 0-(3)16bit: 0-(15)
2W4bit: 100-(1)8bit: 100-(5)32bit: 100-(29)
3W6bit: 101-(3)12bit: 101-(9)48bit: 101-(45)
4W8bit: 110-(5)16bit: 110-(13)64bit: 110-(61)
5W10bit: 111000-(4)20bit: 111000-(14)80bit: 111000-(7)
6W12bit: 111001-(6)24bit: 111001-(18)
7W14bit: 111010-(8)28bit: 111010-(22)
8W16bit: 111011-(10)32bit: 111011-(26)
  • 数学的な美しさでは、s8eよりはs4eやs16eのほうがよい。
  • 実用面ではどうか?
    • ストレージアドレスなど、最初から大きくなることが分かっているのなら、eh16は最適っぽい。
    • 細かい数値がたくさん出てきそうなら、eh4のほうがいい。
  • 統一的に使うならeh4かな。eh4をバイト単位で使うとこうなる。
    • 8bit: 100-(5)
    • 16bit: 110-(13)
    • 24bit: 111001-(18)
    • 32bit: 111011-(26)
  • ehで長さの同じ配列を作りたいのなら、ぞれぞれをehで書くのではなく、ビット長をeh4で書いて、そのあとでデータを並べる。

(5) エンディアンの問題

  • 文字列を考えると、a[3]はやはり先頭から3文字目(4文字目というべきか)であって、末尾から3文字目ではないはずだ。
    • そうなるとビット列についても同じだろう。
    • 0バイト目のbit0が最初のbit。x86にあわせるのは都合がよさそう。
    • そうなると、eh4の8ビット形式は、xxxxx001ということになるのではないか?
  • しかしこれが使いやすいだろうか?
    • しかし使いやすいなんていっていていいのか?数学的な美しさを重視したのではなかったのか?
  • 最初のヘッダでベキを指定して、後ろは0.xxxxxxを表現していると考えてはどうか?
  • というか、バイト列の中のビット位置の数え方を変えればいい。
    • 01234567_89abcdef_... (今までは 76543210_fedcba98)
    • 右シフトは第0ビットを取り出す。
    • CPUのbit数が増えるということは、大きな数が扱えるようになったわけではなく、精度が上がったのだと考える。
  • これはよい。つまりeh系はビッグエンディアン。

(6) リトルエンディアン向きのデコードしやすいエンコードは?

  • ビッグエンディアンおよび汎用としては、eh系で問題はないと思う。しかしデコードのやりやすさという特徴をリトルエンディアンで使えるような、そんなエンコードがあってもいいはずだ。たとえばx86専用のOSのAPIとかに使える。OSASKのなんでも32bit固定というのはあまり頭が良くなさそう。オプションフィールドでモードをつけ拡張するというのはオプションの浪費になりかねない。やっぱり統一的に。
  • っていうかもうめんどくさいから、逆順に読ませようかな。EBXで指定すると、[EBX-1]、[EBX-2]、[EBX-3]の順序で読んでいきます、みたいな。
    • こうしなければいけない理由:
      • アラインや制御ビットの位置に問題のない特別な場合に2バイトデータや4バイトデータをMOVで読めなければいけない(=デコードを省略できる。eh系はビッグエンディアンCPUならこれが成立している)。制御ビットがかぶる場合もunsignedであればANDでマスクすればそれでデコード完了。書き込む場合は適当にORすればいい。
      • もし正順で書いたとすると、制御ビットは下位に来る。制御ビットが3bitとかだったら、データはbit3から始まることになり、読むときにシフト演算が必要になってくる。書くときもシフトしてORということになる。このシフトは余計だ。
      • シフトが必要になってしまう原因はデータと制御ビットをまとめて読んだときに制御ビットが下位に来てしまうのが根本的な原因だ。制御ビットが上位にあればいい。でも制御ビットが上位だと、全体を逆順に読まないと制御ビットを見失ってしまう。
    • 逆順ってことは、文字列も逆順なわけ?・・・うーん、それは違う。仮に逆順に読んでいくとしても、それは書くほうも逆順みたいな感じかな。だから結局正順。
      • 4bitエンコードの場合
            DB  0+0x80      ; EOC  (DW_0+0xc000やDD_0+0xec000000でも可)
            DB  "Hello, world"
            DB  12+0x80     ; len
            DB  コマンドコード+0x80
      • OSの苦労を考えたら8bitエンコードのほうがいいかな。もはやここで美しさを求めてもしょうがないんだし。
            DB  0   ; EOC  (DW_0+0x8000やDD_0+0xc0000000でも可)
            DB  "Hello, world"
            DB  12+0x80     ; len
            DB  コマンドコード+0x80

  • うーん、だめだ。そもそも制御ビットとデータビットが交互に来るというのがダメだ。制御は一括で来るべきだ。うんそれだ。これなららくだ。これなら制御部分にlzを入れることだってできそうだぞ。デコードの際は、ポインタを2つ持つことになる。
  • フォーマット情報はビッグエンディアン。eh4かeh8かeh16かeh32でいいかな。読み込んでおいた制御ビット列が尽きると、またデータ列から制御ビット列を読みに行く。
    • 0〜1:lz(0はdisフィールドなし):disありのlen=0でスペシャルモード
      • カスタマイズとか最大のdisの指定とか、eoc(end of control)とか、データフィールドjmpとか(データと制御情報を同じ場所に置けないというのはまあまあある)。lenがinfのlzとか。
      • eocが0。len=infが1。カスタマイズ指定が2(カスタム長とunitとstart)。jmp系は3以降。
    • 2:nop
    • 3:len=1
    • 4:len=2
    • 7:len=5
  • 全部32bitだよという場合:
    • 34,1,0,1 : 12+4+4+4=24 =6W
    • 4+24=28...まあ32bitのヘッダで済むということ。これいいな!っていうか最強くさい。
    • lzのせいでちょっと面倒だということはあるけれど、32までだったらまあいいんじゃない?32バイトのバッファで十分でしょ?
    • デフォルトカスタムで、4-8-16-32-64にしておくと、6-1-0-1みたいになって、4+16の20にできる。まあ32bitのヘッダなら関係ないけど。
      • 1-2-3-4-6-8-12-16-24-32-48-64のほうがいいかな。32bitなら12-1-0-1なので4+20。
  • だめだやりなおし。

eh0

012345678910
0100101110111000111001111010111011111100111101111110
  • 11〜26 111111xxxx

(7)

  • まずeh4の制御ビット長。これがゼロならデータ混在型。制御ビット長にはこの長さ自身は含まない。実際の値の半分を書く。
    • 混在型の場合はeh4/eh8/eh16とかから選ぶ。
  • 次にエンコードタイプ。0/10/11でeh0/eh2/eh4。次にeh0でモード。0ならnopもlzもなし。1ならいきなりinf。2ならnopやlzあり。
    • オール32の場合、4+2(11)+3(100)+8(???01001)=17以上。32bitにする場合でも最初の4のところで14を指定すればいいのでぎりぎり収まる。
    • オール16の場合は、4+1+3+6(111010)=14以上。だからこれも1wordしかくわない。
    • オール8の場合は、4+1+3+6(111001)=14以上。これは2byte必要になる。まあしょうがない。
  • 制御ビット長を省略できるようにしたい気もするけど、そんなことをしたらアラインがやりにくい。・・・そうでもないかも。0000...001でスタートとか?そうすれば最低1bitにできる。
    • エンコードタイプ、eh0でモード、その次に必要ならeh4の制御ビット長。
    • 1+3+8+1=13以上
    • 苦労して考えた割にはたいしたことない。アラインのこともあるから、やっぱり元通りの先にeh4でいいよ。

こめんと欄


コメントお名前NameLink

リロード   新規 編集 差分 添付   トップ 一覧 検索 最終更新 バックアップ   ヘルプ   最終更新のRSS
Last-modified: 2007-03-18 (日) 15:18:18 (5579d)