しかくいさんかく

解答略のメモ

16日目: [x86] エミュレータ製作 (完成)

この記事はひとりでCPUとエミュレータとコンパイラを作る Advent Calendar 2017の16日目の記事です。

昨日の86のエミュレータ製作の続きをやる。

昨日の最後 に解説した、機械語を順番に実行する部分を再掲すると

for (int i = 0; i < 100000; i++) {
  const int opecode = readmem_next_uint8(&emu);
  ope[opecode].func(&emu);
  if (opecode == 0xF4) break;
}

このループで、機械語のフェッチ→実行→フェッチ→実行を繰り返しているのだった。

今日は機械語を解釈する構造体opeを作る。 これさえできれば、昨日の記事とあわせてエミュレータは完成だ。

ope構造体配列の初期化

昨日の「ニーモニックの解釈」のセクションに書いたように、main関数内で ope構造体を作成 していた。

これを行うinitialize_OPECODE関数は ここ で定義されている。

void initialize_OPECODE(OPECODE ope[OPECODE_NUM]) {

  // デフォルトの関数ポインタを not_defined_halt にする
  for (int i=0; i<OPECODE_NUM; i++) {
  ope[i].mnemonic  = "NOT_DEFINED";
  ope[i].func      = not_defined_halt;
  }

  // calc
  ope[0x01].mnemonic = "add [M+imm], R";
  ope[0x01].func     = add_Mimm_R;
  ope[0x09].mnemonic = "or  [M+imm], R";
  ope[0x09].func     = or__Mimm_R;
  // 略
}

初めに、未定義関数を表すnot_defined_haltope配列全体を初期化している。

その後、命令セット表の

オペコード ニーモニック
0x01 add [M+imm], R
0x09 or [M+imm], R
... ...

これらの情報を元に、ope配列を上書きしている。

ope構造体のメンバ関数 func

実際に機械語命令を実行するのは、ope構造体のfuncだった。 これは関数ポインタとして実装されていた。

つまりさっきのコードの

ope[i].func    = not_defined_halt;
ope[0x01].func = add_Mimm_R;
ope[0x09].func = or__Mimm_R;

これらの右辺値は機械語を実行する関数だ。

まずはデフォルトの not_defined_haltの実装 を見てみると

static void not_defined_halt(EMULATOR *emu) {
  EXIT_MSG("opecode NOT DEFINED. halt\n");
}

未定義の機械語に遭遇すると、エラーメッセージをはいて強制終了する。 ちなみにEXIT_MSG()は僕が適当に作った非標準的なマクロなので、参考にしないほうがいい。

add [M+imm], R を処理する関数

次に機械語0x01に対応する、 add_Mimm_R関数の定義 を見てみる。

この命令は 一昨日の記事[M+imm], R 型のセクションで詳しく解説したので、再読してから以下のコードを見て欲しい。

ニーモニックとModRMに関する画像を再掲しておく。

f:id:kaitou_ryaku:20171212024547p:plain

これを処理する関数は

static void add_Mimm_R( EMULATOR *emu) {
  MODRM m = read_modrm(emu);

  if        (m.mod < 3) {
    // add [M+imm], R ; 01 b([00~10] R M) none/imm8/imm32
    const uint32_t mem = modrm_M_imm_to_addr(m, emu);
    const uint32_t src = readmem_uint32(mem, *emu);
    update_flag(src, *m.R, emu);
    writemem_uint32( mem, src + *m.R, emu);

  } else if (m.mod == 3) {
    // add M, R ; 01 b(11 R M)
    update_flag(*m.M, *m.R, emu);
    *m.M += *m.R;
  }
}

上から順に処理を見ていく。

ModRMの処理

add_Mimm_R関数内では、まず最初にMODRM mという構造体を定義している。 read_modrm関数は、メモリから次の1byte(8bit)を読み込み、MODRM構造体を返す関数だ。

MODRM 構造体の宣言

typedef struct {
  uint8_t modrm;
  uint8_t   mod;
  uint8_t raw_r;
  uint8_t raw_m;
  uint32_t   *R;
  uint32_t   *M;
} MODRM;

メンバのmodrmはメモリの8bitの値そのもので、modraw_rraw_mmodrmを三分割したビット列を表している。 *R*Memu構造体メンバに含まれる汎用レジスタeax等へのポインタである。 raw_r,raw_mレジスタの対応は

raw_r or raw_m レジスタ raw_r or raw_m レジスタ
000 eax 100 esp
001 ecx 101 ebp
010 edx 110 esi
011 ebx 111 edi

これを読み取る read_modrm関数 は、ビット列をガチャガチャの操作して実装した。

[M+imm]のメモリアドレスを取得する処理

ModRMを取得したあとは、「何と何を足すか」をmodの値で場合分けしている。 modが0,1,2なら加算結果をメモリ[M+imm]に書き込み、3の場合はレジスタMに書き込む。

mod 二進表示 mod 十進表示 [M+imm]の型
00 0 [レジスタ]
01 1 [レジスタ+imm8]
10 2 [レジスタ+imm32]
11 3 レジスタ

メモリに書き込む部分の処理を見てみると

if (m.mod < 3) {
  // add [M+imm], R ; 01 b([00~10] R M) none/imm8/imm32
  const uint32_t mem = modrm_M_imm_to_addr(m, emu);
  const uint32_t src = readmem_uint32(mem, *emu);
  update_flag(src, *m.R, emu);
  writemem_uint32( mem, src + *m.R, emu);
}

まず[M+imm]に対応するメモリアドレスをmodrm_M_imm_to_addr関数で取得している。 この関数の実装

static uint32_t modrm_M_imm_to_addr(const MODRM m, EMULATOR *emu) {
  cut_esp_0x24(m.M, emu);
  uint32_t mem;
  if      (m.mod == 0) mem = *m.M;
  else if (m.mod == 1) mem = *m.M + (int8_t)readmem_next_uint8( emu);
  else if (m.mod == 2) mem = *m.M +         readmem_next_uint32(emu);
  else EXIT_MSG("ModRM Error. ModRM's M must be address. Therefore mod should not be 3\n");
  return mem;
}

最初にcut_esp_0x24を呼び出している。 これはModRMのMがespレジスタを表す場合にSIB拡張が発動するので、その対応用の関数なのだが、うーむ。 一昨日の記事 の一番最後に書いたように、x86にはModRMを拡張したSIB拡張があり、それを無視する処理をcut_esp_0x24で行っている。 要するに、ModRMの次に0x24という1バイトの値が来るので、それを読み飛ばす処理だ。 この辺は深く考えないで欲しい。

cut_esp_0x24のあとは、メモリアドレスを表すmemを宣言し、ModRMを元に値を計算し、returnしている。 素直な処理なので読めばわかるだろう。

加算結果をメモリに書き込む処理

まず、取得したアドレスmemの指すメモリの値を、readmem_uint32関数を用いてsrcに読み込む。 次にModRMのRレジスタの値とsrcを足して、結果をwritemem_uint32でメモリに書き込んでいる。

その際、計算結果に応じてcarry, overflow, sign, zero の4つのフラグを更新しなければならない。 この処理は update_flag関数 で行っている。 重要な部分だけ抜粋すると

// rnd1+rnd2でflagを更新
const int sign_1      = rnd1 >> 31;
const int sign_2      = rnd2 >> 31;

const uint64_t result = (uint64_t)rnd1 + (uint64_t)rnd2;
const int sign_result = (result >> 31) & 1;

FLAG flag = {0,0,0,0};
flag.carry    = (result >> 32) & 1;
flag.overflow = (sign_1 == sign_2 && sign_1 != sign_result);
flag.sign     = (sign_result == 1);
flag.zero     = (rnd1 + rnd2 == 0);

// あとはflagを`emu.eflags`に書き込むだけ

フラグ更新の詳細は、 数値関係の記事の 「キャリーフラグ」「オーバーフローフラグ」「比較条件」のセクションに詳しく書いた。 まとめておくと

フラグ名 rnd1+rnd2の結果、フラグが立つ条件
carry 加算結果が符号なしの32bit整数からはみ出る
over flow 加算結果が符号付きの32bit整数をはみ出る
zero 加算結果が0になる
sign 加算結果が符号付き32bit整数の負値になる

キャリーフラグについては、加算時にbit拡張して桁あふれするか調べれば良い。

オーバーフローフラグについては、rnd1, rnd2の符号から予想される加算結果と、実際の結果が一致するか調べれば良い。 もしrnd1 > 0, rnd2 > 0なら予想は正だし、rnd 1 < 0, rnd 2 < 0なら予想は負だ。 従ってフラグの立つ(予想の外れる)条件は

sign_1 == sign_2
&&
sign_1 != sign_result

となる。

フラグの値が得られたので、最後にeflagsflagで上書きする。 大した処理ではないので説明は省く。

レジスタに書き込む処理

ここまでadd [M+imm], Rのmodが0,1,2の場合を見てきた。modが3の場合も一応見ておこう。 この場合ニーモニックadd M, Rとなる。レジスタレジスタを足して、結果をレジスタに代入する命令だ。

else if (m.mod == 3) {
  // add M, R ; 01 b(11 R M)
  update_flag(*m.M, *m.R, emu);
  *m.M += *m.R;
}

update_flag関数でフラグを更新した後、素直に*m.M += *m.Rとしている。

sub命令とcmp命令

ここまで加算命令を見てきた。

今回つくるエミュレータの中で、加算以上に難しい命令はない。

命令セット表を再掲すると

f:id:kaitou_ryaku:20171211195350p:plain

他の重要な計算命令にsubcmpがある。 これらは、第二オペランドの符号を反転(2の補数)したあとに加算すれば実装できる。 2の補数の実装

uint32_t neg_uint32(const uint32_t arg) {
  return bit_reverse_uint32(arg) + 1;
}

わざわざこんな関数作らず普通にマイナスしてもよいと思う。

push命令とpop命令

スタック領域はメモリの最後尾に準備されるので、push時にはespを減らし、pop時には増やせばよい。 意味が分からなければ 昨日の記事 の「エミュレータのメモリに機械語を読み込む」のセクションを再読してほしい。

f:id:kaitou_ryaku:20171212033457p:plain

この緑のスタック領域に対し、pushpopを実装する。

push eaxの実装

static void push_eax(EMULATOR *emu) {
  *(emu -> esp) -= 4;
  writemem_uint32( *(emu -> esp), *(emu -> eax), emu);
}

pop eaxの実装

static void pop_eax( EMULATOR *emu) {
  *(emu -> eax)  = readmem_uint32(  *(emu -> esp), *emu);
  *(emu -> esp) += 4;
}

スタックには4byte(32bit)の値を積むので、espは4ずつ増減している。

ジャンプ系命令

ジャンプ命令とは、次回読む機械語のアドレスを変更する命令であり、そのためにはプログラムカウンタのeipを変更すればよかった。

jmp imm32の実装

// jmp
static void jmp_imm32(EMULATOR *emu) {
  // jmp  0x5 ; e8 05 00 00 00 (普通に命令更新した後のeipからの差分をimmで与える)
  uint32_t imm32 = readmem_next_uint32(emu);
  *(emu -> eip) += imm32;
}

jmp命令のオペランドは、次回読むメモリアドレスとの差分であり、さっき読んだメモリアドレスとの差分ではない。 間違いやすいので、jmp 0 は nop と同じ と覚えるのが良いだろう。1。 この対応は自然だと思う。

条件付きジャンプは、フラグの値に応じてジャンプするかどうか決める命令だった。 特に重要なのはjl, jge, jle, jgの四種類で、C言語のint型整数a,bとの対応がある。

機械語 ニーモニック C言語
0x7c imm8 jl imm8 if (a < b)
0x7d imm8 jge imm8 if (a >= b)
0x7e imm8 jle imm8 if (a <= b)
0x7f imm8 jg imm8 if (a > b)

これらの実装 のうち、jl imm8だけを書くと

static void jl__imm8(EMULATOR *emu) {
  //7c ff
  // cmp a, bにより a-b の結果でフラグ更新した後に実行

  const int8_t imm8 = readmem_next_uint8(emu);
  int SF = read_flag(FLAG_NAME_SIGN    , *emu);
  int OF = read_flag(FLAG_NAME_OVERFLOW, *emu);
  if (SF != OF) *(emu -> eip) += imm8;
}

ここでif (SF != OF)という条件式がif (a < b)に対応している。 この証明は 4日前の記事 の「符号付き整数の大小関係」のセクションに書いた。

関数呼出

2日前の記事call, leave, retの3つの命令を説明した。

結局これらの命令は、以下のスタックとレジスタの操作に分解できるのだった。

関数呼出 対応する操作
call imm32 push eip+4したあとjmp imm32
leave mov esp, ebpしたあとpop ebp
ret pop eip

call imm32の実装

static void call_imm32(EMULATOR *emu) {
  uint32_t imm32 = readmem_next_uint32(emu);
  *(emu -> esp) -= 4;
  writemem_uint32( *(emu -> esp), *(emu -> eip), emu);
  *(emu -> eip) += imm32;
}/*}}}*/

1行目のreadmem_next_uint32は、ジャンプしなかったと仮定した場合の、次回読み込む機械語のメモリアドレスを取得する関数。 その後のスタック操作はpush命令の解説を読めば分かるだろう。

leaveの実装

static void leave(EMULATOR *emu) {
  *(emu -> esp) = *(emu -> ebp);
  pop_ebp(emu);
}

retの実装

static void ret_near(EMULATOR *emu) {
// pop eip
  *(emu -> eip) = readmem_uint32( *(emu -> esp), *emu);
  *(emu -> esp) += 4;
}

どちらも素直な処理なので、読めばわかると思う。

これでエミュレータは一通り完成した。めでたい。

どうでもいい話

駆け足だったが、x86エミュレータ製作の重要なポイントは解説できたと思う。 結果を表示する関数については全く触れなかったが、そこは各人の趣味にあわせて適当に作って欲しい。 main関数のループ の中に、表示したい情報をprintfする関数を入れれば良い。

ところで、このアドベントカレンダーは低層(トランジスタ回路)から高層(C言語)に向かって毎日階段を登っている。エミュレータはその中間地点だ。 しかしこれは、僕が実際に制作した順番とは大きく異なっている。

僕はまず最初にtd4と呼ばれる超単純なCPUのエミュレータ(1時間あれば作れる)を作った。 そこでコツを掴んでからx86エミュレータを作った2。一通り完成させた後に https://book.mynavi.jp/ec/products/detail/id=41347

という本の存在を知った。機械語命令表を関数ポインタで実装する手法を知り、目からウロコだった。switch文はいらんかったんや。。

振り返ると、低レイヤの入口として最も良い題材はエミュレータの製作だと思う。 これをしっかり作ったことで、FPGAコンパイラに挑戦する前段階として、CPUの挙動が直感的につかめるようになった。

そういうわけで、みんなもエミュレータを作ろう~


  1. 命令長は異なる。nopは1byteだが、jmp 0は即値の分だけ命令長が伸びる。

  2. 何事もトイモデルからスタートするのが、良いものを素早く作るための鉄則だと信じている。