GUIGUI01​/memo15 :: OSASK計画

ぐいぐい01に関するメモ-15

• (by K, 2008.12.23)
• メモのうち重要な部分をそのうちまとめてまともなページを作る

(30) helloの改良の歴史 (118→16）

• （参考として）DOSの.COM形式：
  • 22バイトが限界
  • ヘッダとかはない。AHとDXに代入してINT21H。終了はRETでいい。

    [レジスタ代入 INT21H RET で計8バイト] ["hello, wolrd\n$"で14バイト]

• 旧OSASK初期風：
  • 118バイトくらいが限界（非圧縮時）

    [計18バイトのシグネチャやワークエリア設定など] [API-callに標準で7バイト]
    [FS:EBXの設定に最低5バイト] [APIパケットは全部32bit固定なので、初期化func-
     ofs-表示func-opt-dev-len-(13文字)-終了func-opt-パケット終了func で88バイト]

• 旧OSASK中後期風：
  • optの指定でキャラクタコードは8bitでも記述できるようになる。
  • 82バイトくらいが限界（非圧縮時）

    [計18バイトのシグネチャやワークエリア設定など] [API-callに標準で7バイト]
    [FS:EBXの設定に最低5バイト] [初期化func-ofs-表示func-opt-dev-len-(13文字)-
     終了func-opt-パケット終了func で52バイト]

  • 当時は（といっても結構長い期間）この程度の仕様で喜んでいた。
• （参考として）「はりぼてOS」：
  • 読者への説明のしやすさを重視し、DOS風のAPIを採用（INT40H）。EDXにfunc番号、EBXにC文字列。
  • 52バイトが限界

    [ヘッダ27バイト] [EBX=ESP PUSH(2) POP(EDX) INT40H DL=4 INT40H で11バイト]
    ["hello, world\n\0"で14バイト]

  • OSASKと比べて30バイトものアドバンテージ！こんなことでいいのか！？
  • しかしAPI-callをタスクローカルにできないINTにはしたくないし、パケットAPIも好きなので変えたくない。
• 27バイトのhello：
  • DOS版が22バイトなのは16bitだからしょうがないと思えたが、「はりぼてOS」に負けたのは屈辱的だった。そこで設計をやり直す。
  • 適当な標準値を設けてそれを必要に応じて変更する方式で、スタックサイズなどを記述させることに。標準値は小規模プログラムには十分な値なので、helloでは変更の必要が全くない。
  • またパケット要素を32bit固定長から、eh4という4bit単位可変長エンコードに変更（のちにgh4にアップグレードするがhelloは影響なし）。小さい数値なら4bitで収まるので、パケット効率8倍に！
  • またレジスタ初期値を工夫したので、EBPの値を破壊しない限り、CALL(EBP)の2バイトでAPI-callができるようになった（EBXを変更しなければEIPからパケットが始まると見なされる）。終了もDOSと同じくRETだけでもOKに。初期化funcはシステムが事前に適当にやってくれるので、それを変更したいとき以外は省略可能。
  • 旧OSASKでは8バイトもあったシグネチャを2バイトに。
  • これで27バイト

    ['G' 01 で2バイト] [セクション記述用4バイト] [CALL(EBP)で2バイト]
    [5 0 13 "hello, world\n" 4 0 3 の内容で16.5バイト、パケットのフォーマット制御で2.5バイト]

  • 5は表示func（次の0はdev、フォーマット制御をfuncレベルではしなくてよくなったので表示funcのoptは廃止）、4は終了func、3はパケット終端func
  • 「はりぼてOS」版よりもはるかに小さくなったこともあり、この結果に大満足。
• 22バイトのhello：
  • そしてneriさんのCOM64plusが登場。シグネチャを小さくしてレジスタ初期値などのテクニックやスタックサイズ標準値のような手法を導入した結果、hello記述力が21バイト！僕はこのままではいけないと、仕様改良を断行。
  • まず.g01アプリには.textセクションしかない上にリロケーションも必要ない場合が少なくないと分かってきていたので（それらがなくても新APIの記述力のおかげで十分いろいろできる）、ファイル末端までを.textセクションイメージと見なすセクション記述法を導入。これは従来の拡張なので問題はない（従来フォーマットではありえない値を使用）。これで[セクション記述]は1バイトでよくなった。似たような簡易セクション記述モードの導入はCOM64plusでも既にやっていた（というか僕がそうしたらどうかと提案した、その結果が21バイト）。
    • こういう特別モードについては当初心理的な抵抗があった。小さいプログラム向けに特別な形式を用意するのなら、それは有利になるに決まっている。あくまでも汎用的な一通りの方法だけなのにこんなに小さくなる、ということこそ僕の美学だった。
    • しかし将来他のOSとのアプリサイズ競争になったときに、この美学のために小プログラムで全敗することになれば、他の評価すべき特徴と一緒に全部まとめて、「あれはだめだ、あれはうまくいかない、あれは負けたから」と評される心配がある。ここはやはり多くのケースで役立つのなら、積極的に導入するべきだと決断。
  • アプリ終了時に最後に表示した文字が'\n'ではない場合に'\n'を自動出力するモードを設けた（1バイトのセクション記述子内のフラグでこのモードの利用の有無を設定できる）。これで'\n'の出力を省略（これもCOM64plusでやっていた、僕の提案）。
  • .textセクションは多くの場合最後がRETになっているという性質を発見。それならリンカで末尾のRETを勝手に省いて出力し、ロード時に付加すればいいじゃないかと思った。もちろん稀に末尾がRETになっていないこともあるが、その場合もRETが勝手に付加されて特に困ることはない（これもCOM64plusでやっていた、僕の提案）。
  • これで22バイト

    ['G' 01 で2バイト] [セクション記述子1バイト] [CALL(EBP)で2バイト]
    [5 0 12 "hello, world" 3 の内容で14.5バイト、フォーマット制御で2.5バイト]

  • しかしCOM64plusのhelloは21バイトなので結局1バイト負けていた。
• 20バイトのhello：
  • どうにかしてあと1バイト減らしたい。そうすればCOM64plusと同点になれる。それで更に検討。
  • シグネチャは削りたくないし（それは同じ2バイトでがんばっているCOM64plusに対して失礼だ）、セクション記述子をなくしたら普通の形式との識別ができなくなるし、CALLはもちろんなくせない。そうなると、合計17バイトのパケットをどうにかするしかない。
  • それでうさんくさいと思ったのは、パケットのフォーマット制御だった（というか内容を削ると出力先の選択ができなくなる）。なんでこんなものに2.5バイトも食うのか。もっとうまくできないのか。これを分析した。
    • APIパケットは次のようなフォーマットだった。
    • 長さ(0.5B) 内容[5 0] モード変更(1.5B) 長さ[12] 内容[hello, world] 長さ(0.5B) 内容[3]
  • この長さ指定がうっとうしい。長さが尽きたときにモード変更や次の長さを指定するという方式ではなく、基本的に長さ指定なんかなくて、特別な値が来たらモード変更するように改良。このアイデアは、eh4からgh4へ拡張するときに、4bit形式の"7"を特別な値として使ってうまくいったので、それをヒントに思いついた。そしてその特別な数値は4bit形式の"6"ということにした。これでこうなった。
    • 内容[5 0] モード変更("6"+1.5B=2.0B) 長さ[12] 内容[hello, world] 内容[3]
  • しかしこれでは16.5バイトだ。COM64plusに追いつくにはもっと減らさなければ！
  • さらにモード変更について考察した結果、モード変更をしたくなる場所というのはほとんど決まっていた。ようするに文字列を指定する場所や、バッファを指定する場所である。しかも指定値はほとんど決まって8bit配列モードだった。
  • そういうことなら、こんな分かりきったことのために毎回2.0バイトも使うなんて非効率的過ぎる。そこで、APIパケットの文脈がこういう場所に差し掛かったときには、パケットに「モード変更：8bit配列モード」のコードを自動挿入させることにした。ただこれだけだと他のモードにする方法（もしくはモード変更しない方法）がなくなって柔軟性が損なわれるので、この文脈に差し掛かったときのパケット先頭が4bitの"5"なら、この"5"を読み捨てて自動挿入もしないということにした。これでこうなった。
    • 内容[5 0] モード変更(0.5B) 長さ[12] 内容[hello, world] 内容[3]
  • これで15バイトだ。モード変更を完全になくさなかったのは、8bit配列モードで使用頻度が高いものに直接モードと間接モード（＝ポインタ指定するもの）の両方があったため、そのどちらなのかを選ばせるためである。
  • これでアプリ全体は20バイト

    ['G' 01 で2バイト] [セクション記述用1バイト] [CALL(EBP)で2バイト]
    [5 0 12 "hello, world" 3 の内容で14.5バイト、フォーマット制御で0.5バイト]

  • なんとCOM64plusを追い抜いたことになる。しかしCOM64plusはECX初期値を.textの最初の1バイトで指定するというアイデアを導入したため（これも僕の提案）、すぐに20バイトになり追いつかれた。
• 18バイトのhello：
  • neriさんが、この手の小規模プログラムでは.textの末尾にCALL(EBP)が来ることがそれなりに多いから、これをなくせるフラグを用意したらどうかなと提案。確かに言われてみればそういう傾向はありそうだ。これをやられるとCOM64plusのhelloはなんと18バイトになり、もはや.g01に勝ち目はない（だって減らせるところはもうない）。
  • しかし僕も考えてみたところ、.g01では逆に.textの先頭にCALL(EBP)がある率はかなり高そうだ。じゃあこれをセクション記述子内のフラグを使って省略可能にしようか。ということで、neriさんのアイデアをいただいて、ついに18バイトのhelloが誕生。

    ['G' 01 で2バイト] [セクション記述子1バイト]
    [5 0 12 "hello, world" 3 の内容で14.5バイト、フォーマット制御で0.5バイト]

  • COM64plusではまだ末尾CALL(EBP)の自動挿入は導入していないらしいが、たぶん導入することになるのではないかと思われる。
• 17バイトのhello：
  • 2009.01.02に思いついた。APIパケットが1つしかないときは3を全く使わなくてもよくなった（逆にAPIパケットを2つ以上連続させるときは、先頭と末端に3を置く）。またslot番号0はファンクション5番のデフォルトとなり、このデフォルトを変更する場合は!4を置いてその後に目的の値を置くことになった。デフォルトのままでよければ、何も指定しなくていい。

    ['G' 01 で2バイト] [セクション記述子1バイト]
    [5 12 "hello, world" の内容で13.5バイト、フォーマット制御で0.5バイト]

• 16バイトのhello：
  • 2009.01.10に思いついた。コンソールへの文字列出力のとき、デフォルトの文字列は当然ASCIIなので（.g01ではモードを変更しないと日本語などは出せない）、いつも7bitしか必要ないのに1bitの0を補って8bit出力していることになっていた。これはなんかムダじゃないか？他ではものすごくがんばっているのにここでこんなムダを容認していいのか？ということで、7バイト出力するごとにMSBを集めて、これが0でなければもう一文字表示できるようにした。

    ['G' 01 で2バイト] [セクション記述子1バイト]
    [5 12 "hello, world" の内容で12.5バイト、フォーマット制御で0.5バイト]

  • 最近ではすっかりこの内部形式に慣れてしまい、27バイト程度で限界だと思えた過去の自分が不思議でしょうがない（笑）。

こめんと欄