しかくいさんかく

解答略のメモ

12日目: [x86] 数値とバイナリエディタ

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

昨日はx86アーキテクチャの概要を説明した。C言語ニーモニックに変換する手順も書いた。

今日は数値とバイナリエディタに関する注意点をまとめる。

バイナリエディタと聞くと「機械語をそのまま0と1で表示するやつ」とか「16進数で表示するやつ」などと思うかもしれない。 そこに大きな罠がある。 これは機械語をそのまま表示するのではなく、ひっくり返して表示するツールなのだ。

機械語ファイルをバイナリエディタで開く

誤解を避けるため、16進数表記の際、頭に0xをつけることにする。 つまり0xFFは十進数の255と同じ数を表す。

さてバイナリエディタの使い方を説明したい。例として

// C言語
void hoge() {
  int a=0x12345678;
}

というC言語のコードを考える。 これをgccで(所定のオプションをつけて)コンパイルすると、アセンブラのファイルが生成される。 その中には以下のようなニーモニックが含まれる(多分)。

mov eax, 0x12345678

この1行だけからなるhoge.asmというファイルを作り、 昨日の記事jmp imm8のあたりの手順に沿ってアセンブルすると、機械語hoge.binというファイルが得られる。 これをバイナリエディタxxdで見てみると

$ xxd -g 1 hoge.bin
00000000: b8 78 56 34 12   .xV4.
  • 左端の00000000:は、hoge.binの行番号(アドレス番号)
  • 中央のb8 ... 78の部分が、hoge.binの中身そのもの。
  • 右端の.xV4..D3".は、hoge.binをむりやりアスキーコードで表示したもので深い意味はない。

なにやら数字の順番が変だが、そのへんは後で徹底的にやる。 「16進表示はわからん」という人は、xxdコマンドの引数に-bオプションを追加すれば2進表示になる。

$ xxd -g 1 -b hoge.bin
00000000: 10111000 01111000 01010110 00110100 00010010           .xV4.

最初の10111000を考えると、左4桁の1011は16進数のbで、右四桁の1000は16進数の8なので、あわせると上のb8に一致している。

なぜ78 56 34 12になるのか

簡潔に答えると、x86はリトルエンディアンなので、バイナリエディタが1byte毎にbit順序を反転して表示しているからだ。

意味不明だと思うので図で説明する。

f:id:kaitou_ryaku:20171212022844p:plain:w600

画像中段の「バイナリファイル」の行には、hoge.binに含まれる0と1の列を、最初のbitから最後のbitまで順番通りに書いた。 右端から見ていくと、0x12345678の2進表記が逆順で書かれていることが分かるだろう。 ぜろぜろぜろいち(あ、1だ)、ぜろぜろいちぜろ(あ、2だ)と思って欲しい。

ここでバイナリファイルを最初のbitから最後のbitまで、4bit区切りで16進数に変換してみよう。 左端の00010x1に、次の11100xEに、その次の01100x6に、その次の10100xAに、、といった具合になり、元の0x12345678という数字からかけ離れた見た目になってしまう。

そこでバイナリエディタは、1byte毎にbit順序を反転し、その後16進数に変換して表示している。 赤と灰色の矢印がクロスしている箇所は、このbit順序の反転操作を表している。 これなら元の0x12345678とよく似た0x78 0x56 0x34 0x12が表示される。

ちなみにさっきのmov eax, 0x12345678バイナリエディタで表示すると0xb8 0x78 0x56 0x34 0x12となったが、b8の部分もビット順序が反転して表示されている。 バイナリエディタはどこが数値でどこがmovに対応するのか一切気にせず、ひたすら8bitずつ反転して表示するツールなのだ。

最後に重要なコメントだが、以降の数値に関する説明は、0と1の列も含め、全てバイナリエディタ形式で表示したので注意して欲しい。

負の整数

バイナリエディタの説明を終えたので、ここからは数値に関する注意を書きまくる。 まずはマイナスの数だ。

数学的には、マイナス1は「1と加算すると0になる数」として定義されている。 そして4bit同士の加算を考えると、

0001 + 1111 = 0000 (桁溢れは無視)

0001は4bitで1を表す(のが自然)なので、1111にはマイナス1っぽい雰囲気が漂っている。 この理屈を推し進めると

f:id:kaitou_ryaku:20171212022857p:plain

上段は符号無整数と呼ばれ、下段は符号付整数と呼ばれている。 下段同士足したり引いたりする際に、常に4桁で計算し、5桁に溢れた数を無視する約束の下で、1111はマイナス1と等価になる。

ところで0から7については、符号付整数と符号無整数は同じになるが、その先で困ったことになる。 4bitの下で、CPUは9とマイナス7をどのように区別しているのだろうか。

結論を言うと、4bitCPUは9とマイナス7を区別できない。どちらも純粋に1001というビット列にすぎない

f:id:kaitou_ryaku:20171212022905p:plain

これはC言語で書かれたソースコードをバイナリファイルに変換し、バイナリエディタで見た結果を表している。 5種類の代入文があるけど、CPUはこれらの命令を同一視する。 生成されるバイナリファイルも、当然全て同じになる。

繰り返しになるが、重要な点はC言語のsingned整数型もunsigned整数型も、機械語レベルでは全く同じということだ。 CPUができるのは、32個並んだ01の列を二つもってきて、加算器や減算器に入れて、結果に応じてフラグを立てるだけ。 CPUが勝手にsigned型か判定して演算の種類を変える、なんてことはない。 あくまでC言語側が、機械語命令の結果を符号付き/符号なし整数のつもりで解釈しているだけなのだ。

byte拡張

昨日の記事 のジャンプ命令の辺りを読むと

jmp 0x12       ; 機械語は 0xeb 0x12
jmp 0x12345678 ; 機械語は 0xef 0x78 0x56 0x34 0x12

このように、jmp命令の即値は1byteと4byteの2種類があるのだった。

一方x86 (IA-32)のレジスタは全て32bit(4byte)なので、1byteの即値をレジスタに入れる際に4byteに変換する必要がある。

これを説明するために、例として1byteの0x02-0x02=0xEFの2つの数を考える。 これらを4byteに変換するには

f:id:kaitou_ryaku:20171212022912p:plain:w400

要するに

1 byte 4 byte
0x02 0x02000000
-0x02=0xFE -0x02000000=0xFEFFFFFF

キャリーフラグ

「負の整数」のセクションで

「CPUができるのは、32個並んだ01の列を二つもってきて、加算器や減算器に入れて、結果に応じてフラグを立てるだけ」

と書いた。フラグは数種類あり、その中にキャリーフラグがある。 これは CPU編で全加算器を作った 時に一応説明した。

x86の場合は、32個並んだ0と1の列を二つもってきて、全加算器に入れて、33桁目に溢れたらキャリーフラグを立てれば良い。

分かりやすいように4bitのCPUの場合で説明すると

f:id:kaitou_ryaku:20171212022922p:plain:w400

要するに4bitのレジスタ符号なし整数だと考えて、計算の結果が0~15範囲外にはみ出すと、キャリーフラグが立つ。

オーバーフローフラグ

これは初登場だ。

要するに4bitのレジスタ符号付き整数だと考えた場合に、計算の結果が-8~7範囲外にはみ出すと、オーバーフローフラグが立つ。

f:id:kaitou_ryaku:20171212022933p:plain:w400

オーバーフローフラグが立つのは、計算結果の符号が予想とずれた場合だ

  • 正の大きな数同士を足すと、マイナスになった!
  • 負の大きな数から、さらに引くと、プラスになった!

逆に計算結果の符号が二つのオペランドの符号から予想できない場合、オーバーフローフラグは立たない。

  • 正数から正数を引く
  • 負数から負数を引く
  • 正数と負数を足す

これらの計算結果が範囲内に収まるのは、ほぼ自明だろう。

比較条件

他にもいくつかフラグがある。表にまとめると

記号 正式名称 フラグが立つ条件
CF キャリーフラグ 符号なし整数が範囲外にはみ出る
OF オーバーフローフラグ 符号付き整数が範囲外にはみ出る
ZF ゼロフラグ 計算結果が0になる
SF サインフラグ 計算結果を符号付き整数と思うと負値になる
PF パリティフラグ 計算結果の下位1byteに1が偶数個ある

最後にcmp a, b命令(a-bを計算したつもりでフラグを更新)と、その後の条件付きジャンプ命令の関係表を貼っておく。

機械語 オペコード 飛ぶ場合のフラグの条件 前回のcmp a, bの結果
70 jo OF == 1 符号付き整数計算に失敗したとき
71 jno OF == 0 符号付き整数計算に成功したとき
72 jc CF == 1 a < b (符号なし整数)
73 jnc CF == 0 a >= b (符号なし整数)|
74 jz ZF == 1 a == b
75 jnz ZF == 0 a != b
76 jbe CF == 1 or ZF == 1 a <= b (符号なし整数)
77 ja CF == 0 and ZF == 0 a > b (符号なし整数)
78 js SF == 1
79 jns SF == 0
7a jp PF == 1 a-bの下1byteに1が偶数個あるとき
7b jnp PF == 0 a-bの下1byteに1が奇数個あるとき
7c jl SF != OF a < b (符号付き整数)
7d jge SF == OF a >= b (符号付き整数)
7e jle SF != OF or ZF == 1 a <= b (符号付き整数)
7f jg SF == OF and ZF == 0 a > b (符号付き整数)

特に重要なのは、下4段の符号付き整数の大小関係。

符号付き整数の大小関係

a < b

機械語7cのところ。

ここではa < bSF != OFが対応している。この説明をしておく。

a < ba - b < 0と等価だ。ここで

  1. a > 0, b > 0 ならば、引算結果の符号は予想できないのでOF=0。結果は範囲内なのでSF=1
  2. a < 0, b > 0, OF=0ならば、結果は範囲内なのでSF=1
  3. a < 0, b > 0, OF=1ならば、結果は範囲外なのでSF=0
  4. a < 0, b < 0 ならば、引算結果の符号は予想できないのでOF=0。結果は範囲内なのでSF=1

これら全パターンでSF != OFが満たされている。

a >= b

機械語7dのところ。

機械語7c同様の考察を機械語a >= bに対して行うと、SF == OFが得られる。

この結果から、a < bSF != OFに対応し、a >= bSF == OFに対応していることが分かる。

a \<= b

機械語7eのところ。

既に求めたa < bに対する条件に、a == bに対応するフラグ条件ZF == 1をorで結合すればよい。

a > b

機械語7fのところ。

既に求めたa >= bに対する条件に、a != bに対応するフラグ条件ZF != 1をandで結合すればよい。

全パターン求まった。証明完了!