uxf

Universal eXecutable Format

• (by K, 2016.09.14)

これは何？

• プログラミング言語を作っていると、実行速度が出なくて悩ましいことがある。
• でもプログラムのうち高速化の必要があるところは全体の2割くらいなので、そこだけアセンブラで書けたらいいなと思う。
• こういうときの逃げ道としてC言語が用意しているのはインラインアセンブラだけど、インラインアセンブラをやることにするとアセンブラを解釈できなければいけないので、言語処理系の負担が大きい（naskをライブラリとして呼び出す方法もあるかもしれないけど、それはnaskがないと動かないということになって、情けない）。
  • Cはどっちにしてもアセンブラが必要になるので、インラインアセンブラという手法はいい選択だった。
• それで、実行バイナリを扱うわけだけど、COFFやELFはオーバースペック過ぎて「僕がほしいのはこれじゃない」感が強い。こんな複雑なフォーマットを解釈しなければいけないのだとしたら、それだけで処理系も相当に肥大化してしまう。必要十分な機能があればそれでいい。
• 第二世代OSASK（efg01）の技術をそのまま使うことも考えたけど、あれはサイズを極端に小さくするために頑張っているので、それもなんかしっくりこない。もっとシンプルでいいんだ。
• ということで、efg01の技術をもっとずっとシンプルにしたようなものを考えた。

sh8

• まず、このuxfで使われる可変長整数のエンコードを紹介します(sh8)。このエンコードでセクションサイズやアライン情報などをエンコードします。

  0～0x7f:      0xxxxxxx
  0～0x3fff:    10xxxxxx xxxxxxxx
  0～0x1fffff:  110xxxxx xxxxxxxx xxxxxxxx
  0～0xfffffff: 1110xxxx xxxxxxxx xxxxxxxx xxxxxxxx

• これより大きな表現も考えられますが、x86の32ビットだけを想定するのなら、これくらいで十分でしょう。

フォーマット内容

01 (アライン情報) (.textのサイズ) (.dataのサイズ) (.bssのサイズ) [.textの生データ] [.textのリロケーション情報] [.dataの生データ] [.dataのリロケーション情報]

• アライン情報は、4ビットずつで、(.bssのアライン) << 8 | (.dataのアライン) << 4 | (.textのアライン) となっています。この12ビット値を一つの整数として、上記のエンコードでエンコードします。
• アラインは0～15まで指定できるわけですが、「0」の1バイトアライン指定は別の意味があり、この場合はデフォルトのアラインが利用されます。デフォルトのアラインは16バイトです。したがって、どれも16バイトのアラインで十分なら、アライン情報は0を書いておけば十分です。
• 各セクションの生データは、サイズ情報が1以上の場合のみ記述されます。リロケーション情報は、生データが存在した場合のみ記述されます。
• リロケーション情報は少し複雑で、次のようになっています。

  (リロケーション要素数) (リロケーション間隔の単位) { (次の位置までの間隔) << 2 | セクション番号 } ...

  • リロケーション要素数が0の場合は、リロケーション位置の単位も記述されませんし、その後の { } も記述されません。

• エントリポイントは.textの先頭に固定されています。

ローダプログラム例

void *load_uxf(const unsigned char *p)
{
     if (get_sh8(&p) != 0x01) return NULL; // フォーマット不一致.
     int i, j, k, l, u, m, siz[3], algn = get_sh8(&p);
     unsigned char *sct[3];
     for (i = 0; i < 3; i++) {
         siz[i] = get_sh8(&p);
         sct[i] = NULL;
         if (siz[i] > 0)
             sct[i] = malloc_aligned(siz[i], (algn >> (i * 4)) & 0xf);
     }
     for (i = 0; i < 2; i++) {
         if (siz[i] == 0) continue;
         for (j = 0; j < siz[i]; j++)
             sct[i][j] = *p++; // 生データのロード.
         j = get_sh8(&p);
         if (j == 0) continue;
         u = get_sh8(&p);
         l = 0;
         while (j > 0) {
             m = get_sh8(&p);
             l += (m >> 2) * u;
             int *q = (int *) (sct[i] + l);
             *q += (int) sct[m & 3];
             l += 4;
             j--;
         }
     }
     for (j = 0; j < siz[2]; j++)
         sct[2][j] = 0; // bss領域のクリア.
     // sct[0]の領域に、実行権限を付与する.
     return sct[0];
}

int get_sh8(const unsigned char **pp)
{
    const unsigned char *p = *pp;
    unsigned char c = *p++, b;
    int i, j;
    i = c;
    for (b = 0x80; (i & b) != 0; b >>= 1)
        i ^= b;
    for (b = 0x80; (c & b) != 0; b >>= 1)
        i = i << 8 | *p++;
    *pp = p;
    return i;
}

void *malloc_aligned(int siz, int algn)
{
    if (algn == 0) algn = 4;
    algn = 1 << algn;
    // このsizとalgnでメモリ領域を確保 → p
    // まあ簡易的には以下の方法で実現できる(freeのことは考えてない).
    int p = (int) malloc(siz + algn);
    if ((p & (algn - 1)) != 0)
        p = (p + (algn - 1)) & ~(algn - 1);
    return (void *) p;
}

uxfのプログラムはどうやって書くの？

• 基本的にはC言語で書きます。アセンブラで書いてもいいですが。
• ただ現状ではuxfを出力できるリンカがないので、それを適当に作らないといけません。まあそのうちやります。

拡張仕様

• リロケーション情報でセクション番号に3を指定した場合、それはexternリンクで以下の形式になる、というのはどうだろうか？
  • {(次の位置までの間隔) << 2 | 3} { 識別子長 << 2 | リンクタイプ } { 識別子 } ...
  • これでダイナミックリンクも記述できる
  • リンクタイプ:
    • 0: 補正なし（リンク位置にある値はもちろん加算する）
    • 1: 相対アドレス指定に配慮し、上記の値から(書き込み位置のアドレス+4)を引く
    • 2: publicラベル宣言（リロケーション作業については何もしない）
  • リンクタイプ=3をプライベートラベルにするか、それともさらなる拡張にするか・・・
  • 識別子長を0にしたときに拡張動作にするという道もある
  • 識別子はバイト単位なので、長さもバイト数で記述される
• リンクタイプ0と1の拡張によって、未解決シンボルを記述できるので、api呼び出しなどを記述できる
• リンクタイプ2の拡張によって、publicラベルが宣言できるようになるので、先頭以外をentryにさせることもできるし、uxfをobjファイルの別形式として使うこともできる。

こめんと欄

• リンカはできました。 -- K 2016-09-23 (金) 20:00:34
• 拡張仕様についてもサポートできました。 -- K 2016-09-27 (火) 10:43:36
• uxfのリンカはどこでダウンロードできますか？ -- 名無しさん 2017-07-17 (月) 11:05:05
• まだどこにもアップロードしていません、すみません。 -- K 2017-07-31 (月) 11:09:02