memo0035 のバックアップ(No.4)

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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• memo0035 へ行く。
  • 1 (2008-11-16 (日) 12:01:43)
  • 2 (2008-11-16 (日) 12:20:55)
  • 3 (2008-11-16 (日) 19:47:32)
  • 4 (2008-11-17 (月) 09:15:19)
  • 5 (2008-11-18 (火) 16:13:28)

---

何でもかんでも4bit単位で統一してみる

• (by K, 2008.11.16)

(0)

• 現在ではなんでも8bit（バイト）での区切りがあって、あとはその倍数ですべてが設計されている。そうではなくて、4bitで区切って、さらに4bitずつでしか区切らないとしたら一体どうなるかを検討。はっきり言ってただの遊び。

(1)

• ダンプ
  • 従来：

    0000 01 23 45 67 89 AB CD EF 01 23 45 67 89 AB CD EF

    • これが16行並ぶと256バイト
  • 案：

    0000 0123 4567 89AB CDEF

    • これが16行並ぶと128バイト
  • 一つのアドレスに4bitが存在するため、アドレスが0x10進むとその中に64bit（＝8バイト）が存在することになる。
• 切りのいい大きさ
  • 4bit、64bit（8バイト）、1024bit（128バイト）、2KB、32KB、512KB、8MB、128MB
    • 4bitがアドレスの一単位、8バイトをパラグラフ、128バイトをセクタ長、2KBをページ長・・・なんてやったらどうかな？

(2)

• 指数付き整数
  • 浮動小数点とアイデアは近い。eh4でこんなことができるという例。
  • ルールはeh4を2つ書くこと。一つ目は指数で、それを2倍した数がシフト量。もうひとつが仮数部。似たようなルールは、 OSA:GUIGUI01/man0003 のスタックサイズ指定などに見られる。
  • これだとたった16bitしかなくても、こんなに表現力がある。
    • 仮数部に12bitを割り振る場合、(0〜511) * (1〜16384）。最大は約8メガ。
    • 仮数部に8bitを割り振る場合、(0〜31) * (1〜2^62)。最大は約2^67。
  • もしHDDのパーティションテーブルがこの形式で記述されていたらどうだっただろうか。8メガセクタというのはつまり4GBだが、たったの16bitで4GBまでサポートできていたことになる。既存の形式は24bitのCHSでも、8GBくらいまでしか扱えなかった。
• もちろん16bitの指数付きeh4ではさすがに有効数字不足だが、これを同条件にするために24bitの指数付きeh4にすれば、有効数字も0〜16383や0〜8191となり、事実上不便を感じることはないだろう。しかも遠い将来指数部8bitでも足りなくなるようなら指数部を12bitにすることも考えられるが、その場合は指数部だけでも2^1022という途方もない最大値を指定できることになり、拡張性は全く申し分ない。
• KHBIOSではもちろん自前のパーティションテーブルをもち（これは非AT互換機との互換性をとりやすくするためにも必要な処置）、そのときはこれでいこうと思っていた。そうすれば小さいテーブルでもかなりの記述力と拡張性を担保できるから。

(3) 脱線

• eh4を改造してdh4という形式を考えてみる。

  4bit	0xxx	3(0-7)	eh4では3	s3sでは3
  8bit	10xxxxxx	6(0-63)	eh4では5	s3sでは6
  12bit	1100xxxxxxxx	8(0-255)	eh4では9	s3sでは9
  16bit	1101xxxx....xxxx	12(0-4095)	eh4では13	s3sでは12
  20bit	1110xxxx....xxxx	16(0-65535)	eh4では14	s3sでは15
  24bit	111100xxxx....xxxx	18	eh4では18	s3sでは18
  28bit	111101xxxx....xxxx	22	eh4では22	s3sでは21
  32bit	111110xxxx....xxxx	26	eh4では26	s3sでは24
  36bit	11111100xxxx....xxxx	28	eh4では30	s3sでは27

• eh4の用途を考えると、短い形式はよく使うが長い形式はまず使わない。だから短い形式での効率を重視したほうがよい（eh4はむしろ長い形式でヘッダが長くなりすぎないことを重視していた）。せいぜい24bit型くらいまでの比較で十分。
• 24bitでは、eh4もdh4もs3sも同じ。その前の20bitではdh4の効率が最もよい。
• むしろs3sでもいいんじゃないか。4〜24bitの挙動を見る限りでは。s3sだと継続ビットが間に入るので、それを先頭に持ってくるという工夫は必要だが。エンコード名はsh4かな。CPUの名前みたいで紛らわしいけど。
• sh4

  4bit	0xxx	3(0-7)	eh4と同じ
  8bit	10xxxxxx	6(0-63)	eh4よりも1bit多い
  12bit	110xxxxxxxxx	9(0-511)	eh4と同じ
  16bit	1110xxxx....xxxx	12(0-4095)	eh4よりも1bit少ない
  20bit	11110xxxx....xxxx	15(0-32767)	eh4よりも1bit多い
  24bit	111100xxxx....xxxx	18	eh4と同じ

• eh4と比べると短い形式（特に8bit）で勝ちがあることは大きい。しかも規則が単純なこともメリットだ。これでhellok0.g01はより小さくなるなんてことはあるだろうか？ないだろうな。まあ増えることもないはず。・・・とりあえず42をエンコードしている部分があるのでそこで4bit減らせる。でも4bitじゃ効果ないので、結局NOPを入れるしかない。
• これだと上の指数付き整数も変わる。

  16=4+12	(1-16384)x(0-511)	最大は約8メガ
  16=8+8	(1-2^126)x(0-63)	最大は約2^132
  24=4+20	(1-16384)x(0-32767)	最大は約512メガ
  24=8+16	(1-2^126)x(0-4095)	最大は約2^138

• fh4
  • しかしやっぱりsh4では全ビットの25%が常にヘッダとして無駄になるわけで（＝データを表すビットとしては活用できないわけで）、これはいかにももったいない。そもそも24bit形式の次に28bit形式などがあったとして、こんなのを使いたいと思うだろうか。そんなのすっ飛ばして、32bit形式でいいじゃないかと思わないだろうか。僕はそう思うのだが、これができない理由があって、それは半端な隙間が開いてしまったときにそれを解消するすべがないことである。しかし隙間を空けないで済むように、パディング用のコードがあれば、この問題は起きない。
  • ということで次のようなエンコードを考えた。

    4bit	0xxx	3(0-6)	sh4と同じ、"7"は8bit形式以上でエンコード
    4bit	0111	prefix	主にパディング用（註）
    8bit	10xxxxxx	6(0-63)	sh4と同じ
    12bit	110xxxxxxxxx	9(0-511)	sh4と同じ
    16bit	1110xxxx....xxxx	12(0-4095)	sh4と同じ
    24bit	11110xxxx....xxxx	19	sh4よりも1bit多い
    32bit	111110xxxx....xxxx	26	sh4よりも2bitも多い
    48bit	1111110xxxx....xxxx	41	sh4よりも5bitも多い
    64bit	11111110xxxx....xxxx	56	sh4よりも8bitも多い

  • 註：
    • 4bit形式の7はプリフィクスであって、"7"を意味しない。またプリフィクスの直後に通常の4bit形式、8bit形式、12bit形式が続くことはない。それらはプリフィクスを含まない8bit形式、12bit形式、16bit形式をとれば済むからである。
    • プリフィクスである4bit形式の7は、連続でいくつでもつなげられる。しかしいくつつなげても単にスペースを埋める以上の意味はなく、制御コードとしても意味が変わることはない。
    • プリフィクスの後の0-511は制御コードとして特別な意味を持つ。・・・かもしれないので（笑）、基本的に使ってはいけない。たとえばこれらをヘッダに使うことができる。pre-0やpre-1を"111111110"や"1111111110"などの代わりにすれば、長い形式でのビット効率はさらに増す。
  • fh4だとエンコード自体にNOP用コードがあるようなものなので、このエンコードを使う仕様ではNOP的なファンクションを入れる必要はないかもしれない。
• gh4
  • fh4では20bit形式、28bit形式、40bit形式、56bit形式を飛ばしているが、これらを入れたほうがいいかもしれない。入れたのがgh4である。この場合制御コードは0-2Mまで定義できることになる。

こめんと欄

コメント	お名前	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.023 sec.