memo0023 のバックアップ(No.5)

[ トップ | 一覧 | 単語検索 | 最終更新 | バックアップ | ヘルプ ]

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• memo0023 へ行く。
  • 1 (2007-03-03 (土) 00:18:53)
  • 2 (2007-03-03 (土) 00:32:35)
  • 3 (2007-03-03 (土) 12:26:54)
  • 4 (2007-03-03 (土) 14:24:49)
  • 5 (2007-03-18 (日) 14:08:18)

---

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

• 数学的な美しさでは、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

• 11〜26 111111xxxx

こめんと欄

コメント	お名前	NameLink

   

Modified by K-tan

PukiWiki 1.4.6 Copyright © 2001-2005 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji
Powered by PHP 5.6.40

HTML convert time to 0.034 sec.