assembly
アセンブラ
Brainf*ck
x64
アドベントカレンダー2018

はじめてのアセンブリ言語入門 -brainf*ckをコンパイルする-

Ateam Lifestyle x cyma Advent Calendar 2018、18日目は株式会社エイチームでcymaのエンジニアをしています@bayasistが担当します。新卒3年目です。


初めに

日ごろはWebエンジニアとしてPHP, Rails, Javascript等々高級言語でのお仕事をさせていただいております。そんな高級言語使いですが、C言語やアセンブリ言語でのOSの開発も趣味でやっておりました。そのような知識で自分の基礎力があがったなぁ感覚がなんとなくありまして、高級言語使いの方に逆に低級言語のことも知ってほしいと思い、今回はあえてアセンブリ言語に焦点を当てて記事を書いてみます。


最終ゴール

アセンブリ言語をなんとなく理解して、brainf*ckをアセンブリ言語に変換できるようにします

アセンブリ言語からさらに既存のソフトウェアを用いてx64に変換し実行します


この記事の対象者


  • アセンブリ言語をちょっと触ってみたい人

  • 高級言語にはよく触れるが、低級言語についてはほとんど知らない人

  • 変態的なエンジニアリングをやっている記事に興味がある人(笑)


brainf*ckとは?

命令が8種類しかない、とてもシンプルなプログラミング言語です。

非常にシンプルなので今回採用しました。ただ、シンプルがゆえに書いたプログラムを解読するのは非常に難解です。

詳しくはWikipedia等を見てみてください。また「brainf*ck」で調べればさまざまな解説記事が出てきます。

https://ja.wikipedia.org/wiki/Brainfuck

https://yryr.me/programming/brainfuck/brainfuck-spec-using.html

言語仕様を理解しておかないと、先を読み続けるのがしんどいので、理解しておきましょう。(題材選びを間違えたかも)

とてもシンプルなプログラミング言語なので、すぐ理解できるはずです。

brainf*ckを用いてHello Worldを書くと下記の通りとなります。書いたプログラムは本当に理解不能ですね。。。

(これが何故Hello Worldになるかは読み解かなくても後の記事の理解には影響ないとおもいます。)

>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++

++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++.


アセンブリ言語とは?

機械語を人間にわかりやすい記述にした言語です。機械語の1つの命令がアセンブリの1つの命令と基本的には一対一で対応します。

機械語では変数という概念は存在せず、メモリやレジスタ(下記参照)を直接操作して、変数で扱うような一時的なデータは保存されます。アセンブリ言語でもそれと同様の操作をしなければなりません。

今回はGNU Assembler(Gas)を用います


今回利用した環境

アセンブリ言語を扱うため、環境が多少変わっただけでも動かなくなる可能性があります。

ただ、UNIX系のOSで、x86が動くCPUであれば、少しの工夫で行けるはずです。


  • MacOS Sierra(Ver. 10.12.6)

  • gcc 4.2.1

  • Intel(R) Core(TM) i7-5650U CPU @ 2.20GHz

  • Apple LLVM version 9.0.0 (clang-900.0.39.2)


前提知識

ここではアセンブリ言語を理解するのに必要な概念を必要最低限説明します。


レジスタ

CPU内部にある記憶領域です。もっとも高速に書き込むことが可能ですが、容量は非常に小さいです。

一つのCPUには数十個程度のレジスタが存在し、64bitCPUの場合はレジスタ一つあたりの容量は一般的には64bit程度となります。数十個のレジスタ一つ一つには名前が付いています。下記にx64のレジスタの一覧が載っているので参考にしてください。

http://www.zombie-hunting-club.com/entry/2017/10/15/220724

見てもらうとわかるのですが、数十個あるレジスタを自由に使えるわけではなく、それぞれに役割が存在します。

自由に使えるレジスタは汎用レジスタのみとなります。


テキスト領域

プログラムを実行する際に使用する、メモリ領域の一つです。

プログラム起動直後に、機械語プログラムがメモリ上に展開されます。

この機械語プログラムが展開されている領域のことをテキスト領域と呼びます。

この部分は書き込み禁止となっており、このメモリ領域に書き込みを行おうとするとエラーでプログラムが強制終了します。


静的領域

プログラムを実行する際に使用する、メモリ領域の一つです。

プログラム起動直後に、プログラムの実行に必要なデータがメモリ上に展開されます。

このデータを保存する場所を静的領域と呼びます。


ヒープ領域

プログラムを実行する際に使用する、メモリ領域の一つです。

プログラム実行中に動的にメモリの確保を行なった場合に使われます。と、説明して高級言語を日常使っているとよくわからないかもしれませんね。一旦スルーします。知りたい方は調べましょう。


スタック領域

プログラムを実行する際に使用する、メモリ領域の一つです。

スタック領域はLast In First Outのデータ構造になっています。すなわち、あとに入れたデータが先に取り出せるデータ構造となります。

通常は関数実行に必要なデータ(例えばローカル変数や関数呼び出し元アドレスなど)を保存するために使われます。

x64ではrspレジスタ(スタックポインタレジスタ)にスタック領域のもっとも端のメモリアドレスが記録されており、スタック領域に値を追加する際は、rspの値をデクリメントし、その場所に保存したいデータを書き込みます。取り出す場合はrspに保存されているアドレスのデータを取り出し、rspをインクリメントします。ややこしいので下記の図を参考にしてください。

スタック領域にデータを保存するときの図

キャプチャ (2).PNG

スタック領域からデータを取り出すときの図

キャプチャ (1).PNG

データ領域まとめ(各領域はこのように配置されます)

キャプチャ.PNG


オペコード、オペランド

下記のコードを見てください

movq  %rsp, %rbp

これはrbpレジスタにrspレジスタの値を代入するという意味のコードです。

1つの命令内で操作を表す部分のことをオペコードといいます。(この場合はmovq)

関数でいう引数に相当する部分はオペランドといいます。


システムコール

例えばターミナルに文字を出力したい時を考えます。

ターミナルに文字を出力をする権限はアプリケーションにはないので、OSに作業を依頼する必要があります。

このようにOSに作業をお願いする動作や仕組みのことをシステムコールと呼びます。

OSが管理しているウィンドウ等の情報取得・変更や、ハードウェアへのアクセスなどのOSでしか行えない動作を実行したい際はシステムコールというOSに実装された仕組みを使って、OSに依頼をします。


初めてのアセンブリ

いろいろごちゃごちゃ説明していても面白くないので、早速アセンブリ言語でHello Worldを書きましょう。


main.s

  .globl  _main

_main:
# これから使うレジスタの値をスタック退避させとく
pushq %rbp
pushq %rax
pushq %rdi
pushq %rsi
pushq %rdx
movq %rsp, %rbp # 今のスタックの端を保存しておく
movq $0x2000004, %rax # システムコール番号 writeシステムコールを呼び出す
movq $1, %rdi # システムコール引数 標準出力に出力することを意味する
leaq _message(%rip), %rsi # システムコール引数 出力する文字が保存されているメモリアドレス
movq $13, %rdx # システムコール引数 13文字出力することを表す
syscall # システムコールを呼び出す
xorl %eax, %eax # 0をeaxに代入
# 退避したレジスタを元に戻す
popq %rdx
popq %rsi
popq %rdi
popq %rax
popq %rbp
retq # 呼び出し元へ戻る
.section __DATA,__data # ここから静的領域
_message:
.asciz "Hello World!\n"

はい、高級プログラミング言語のように直感的に理解できる言語ではないですね。

下記のコマンドでコンパイル及び実行が可能です。

$ as main.s -o main.out 

$ gcc main.out -o a.out
$ ./a.out
Hello World!

簡単に要点をかいつまんで説明しましょう。

まず、$から始まる数値は、即値(定数)です。movq $0x2000004, %rax$0x2000004がこれに該当します。また%から始まる文字は、レジスタを意味します。pushq %rbpであれば%rbpですね。

mov*命令は第1オペランドから第2オペランドへの代入を意味します。movq %rsp, %rbpであれば、rspレジスタの値をrbpレジスタに代入しています。movqは8byte分、movlは4byte分、movbは1byte分の代入を行います。movq %rsp, %rbpであれば、rspレジスタもrbpレジスタもどちらも8byte分のデータを保存できるレジスタとなっていますので、8byte分のデータ転送を行っております。

push*はスタック領域へのデータの保存、pop*はスタック領域からのデータの取り出しを意味します。これもmovと同様で、後ろにq,l,bがつくことによって、どれだけのデータ量を保存、取り出しするかが変わります。

syscall命令はシステムコールを呼び出す命令です。

これが実行されるときに、raxレジスタにどのような値が入っているかによって、呼び出されるシステムコールの種類が異なります。0x2000004はwriteシステムコールです(Mac以外のUnix系のOSの方はおそらく0x4で動きます)。

writeシステムコールはrdiレジスタに1が入っているときに標準入出力(ターミナルだと思ってもらえれば)に文字を出力できます。またrsiレジスタに文字列が格納されているメモリのアドレス、rdxレジスタに文字列の長さを代入しておく必要があります。

eaxレジスタは関数の戻り値を代入しておく必要があります。C言語をやったことはある方はわかると思いますが、main関数では普通は正常終了を表す0を返すので、同様にretq(関数の終了)が呼び出される際に、eaxレジスタに0が代入されている状態にしておきます。xor*は第一オペランドと第二オペランドをxorビット演算をしたのち、第二オペランドのレジスタにその結果を代入します。ですので両方に同じレジスタを指定した場合は、そのレジスタに0が代入されます。

なんとなくでも理解できましたか?


どうやってbrainf*ckプログラムを動かすか?


使用するデータの配置

brainf*ckの実行に必要なデータをどこにおくのかを考えましょう。

実行に必要なデータは下記の二つです


  • 大きなバイト配列

  • 上記バイト配列のどこかを指すポインタ

大きなバイト配列は静的領域に今回は置きます。本来であればヒープ領域におきたいところですが、ヒープ領域を確保するには実行後にbrkシステムコールを呼び出す必要があるため少々複雑となります。それに比べ静的領域に置くのはプログラムにデータを書いておくだけなので簡単です。その分プログラムのファイルサイズが多くなる等のデメリットはあります。今回は極力簡単にしたかったためそのような選択をしてます。

データ配列を指すポインタはrsiレジスタに置きます。

writeシステムコールをする時に単純になるからです。


プログラムの実行

今回は複雑になるため入力命令(,命令)はなかったことにします。

それ以外の7つの命令について考えていきます。

7つの命令を下記のように変換していけば、アセンブリ言語に変換できそうです。


+命令

rdiレジスタが指すメモリ上の値を1加算します。rsiレジスタの示しているアドレスの値を1度blレジスタに持ってきてから加算しています。

movb  (%rsi), %bl

addb $1, %bl
movb %bl, (%rsi)


-命令

rdiレジスタが指すメモリ上の値を1減算します。やり方は+と同様です。

movb  (%rsi), %bl

subb $1, %bl
movb %bl, (%rsi)


>命令

rsiレジスタに1を加算します

addq  $1, %rsi


<命令

rsiレジスタから1を減算します

subq  $1, %rsi


[命令

rsiが指す先と0を比較し、等しかったらjump。この直後にも飛べるようにlabelを追加しておきます。

cmpb  $0, (%rsi)

je 適当なラベルB
適当なラベルA:


]命令

rsiが指す先と0を比較し、等しくなかったらjump。この直後にも飛べるようにlabelを追加しておきます。

cmpb  $0, (%rsi)

jne 適当なラベルA
適当なラベルB:


.命令

writeシステムコールを呼び出し標準入出力にrsiが指す値を1文字だけ出力する。

movq  $0x2000004, %rax

movq $1, %rdi
movq $1, %rdx
syscall


初期化処理

pushq %rbp

pushq %rax
pushq %rbx
pushq %rdi
pushq %rsi
pushq %rdx
movq %rsp, %rbp
leaq _message(%rip), %rsi

ここでお気づきな方がいるかもしれませんがblレジスタの退避がなされてません。

blレジスタの実態はrbxレジスタの最下位1バイトなのでrbxさえ退避してしまえば問題ないのです。


終了処理

xorl  %eax, %eax

popq %rdx
popq %rsi
popq %rdi
popq %rbx
popq %rax
popq %rbp
retq


brainf*ckをアセンブリに直すプログラムを作ってみる

ここまで説明してきた内容を参考にC言語で作ってみた。

突貫工事で作ったプログラムなのでエラー処理などはされていません。

メモリリークなどに注意しつつ使ってください。


brainfxxk.c

#include <stdio.h>

void writeStart() {
puts(" .globl _main");
puts("_main:");
puts(" pushq %rbp");
puts(" pushq %rax");
puts(" pushq %rbx");
puts(" pushq %rdi");
puts(" pushq %rsi");
puts(" pushq %rdx");
puts(" movq %rsp, %rbp");
puts(" leaq _message(%rip), %rsi");
}

void writeEnd() {
int i;
puts(" xorl %eax, %eax");
puts(" popq %rdx");
puts(" popq %rsi");
puts(" popq %rdi");
puts(" popq %rbx");
puts(" popq %rax");
puts(" popq %rbp");
puts(" retq");
puts(" .section __DATA,__data");
puts("_message:");
printf(" .asciz \"");
for(i = 0; i < 1000; i++) {
printf("\\000");
}
printf("\"\n");
}

void writeText(char *text) {
int i;
int labelIndex;
int labelLayer;
int labelLayers[100];
labelIndex = 0;
labelLayer = 0;
for(i = 0; text[i] != '\0'; i++) {
switch(text[i]) {
case '+':
puts(" movb (%rsi), %bl");
puts(" addb $1, %bl");
puts(" movb %bl, (%rsi)");
break;
case '-':
puts(" movb (%rsi), %bl");
puts(" subb $1, %bl");
puts(" movb %bl, (%rsi)");
break;
case '>':
puts(" addq $1, %rsi");
break;
case '<':
puts(" subq $1, %rsi");
break;
case '.':
puts(" movq $0x2000004, %rax");
puts(" movq $1, %rdi");
puts(" movq $1, %rdx");
puts(" syscall");
break;
case '[':
labelLayers[labelLayer] = labelIndex;
puts(" cmpb $0, (%rsi)");
printf(" je B%d\n", labelLayers[labelLayer]);
printf("A%d:\n", labelLayers[labelLayer]);
labelIndex++;
labelLayer++;
break;
case ']':
puts(" cmpb $0, (%rsi)");
labelLayer--;
printf(" jne A%d\n", labelLayers[labelLayer]);
printf("B%d:\n", labelLayers[labelLayer]);
break;
default:
break;
}
}
}

void fileOpen(char* filename, char* output) {
FILE *fp;
char str;
int i;
i = 0;
fp = fopen(filename,"r");
while((str = fgetc(fp))!=EOF){
output[i++] = str;
}
output[i] = '\0';
fclose(fp);
}

int main(int argc, char* argv[]) {
char text[1000];
if(argc <= 1) {
return 0;
}
fileOpen(argv[1], text);
writeStart();
writeText(text);
writeEnd();
return 0;
}


上記のプログラムをコンパイルしましょう。

$ gcc brainfxxk.c -o brainfxxk

brainf*ckのHelloWorldも用意しておきます。

$ echo ">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++

++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++."
> hello.bf

あとはhello.bfをコンパイルしましょう!!

$ ./brainfxxk hello.bf > hello.s

$ as hello.s -o hello.out
$ gcc hello.out -o hello.out
$ ./hello.out
Hello World!

やった!Hello Worldが実行できたよ!


終わりに

いかがだったでしょうか?プログラミング言語のように高級な機能はないため、メモリの使い方、レジスタの使い方など、普段何も考えていないことを色々考えなければいけないことは分かっていただけましたでしょうか?

このような知識をさらに深ぼっていくと、色々な発見があります。

例えばシステムコールの実行には一般の関数呼び出しより時間がかかりますが、システムコールの呼び出し原理を知っていればその理由が分かるはずです。

深く理解した知識は、プログラミング中に無意識的に使える知識にもなるかと思います。

是非、たまには低級言語のことも思い出してあげてくださいね。


参考文献


Ateam Lifestyle x cyma Advent Calendar 2018、明日の19日目は同じくcymaの@shimura_atsushiさんに書いてもらう予定です。お楽しみに!


エイチームグループでは、一緒に働けるチャレンジ精神旺盛な仲間を募集しています。興味を持たれた方はぜひエイチームグループ採用サイトを御覧ください。

https://www.a-tm.co.jp/recruit/