＊このブログは、インターン先の勉強会に向けて作った資料を、ブログとして公開するために一部書き直したものです。
動機
所属している研究室の発表があり、何か実装しなければならなかった。
今後の足がかりとして、アセンブリで何かを実装してみよう。
完成に至る順番
CPUやアセンブリの基礎を学ぶ
Cでlifegameを書いてみる。
そのコードを元に、自分でアセンブリを実装していく。(gccなどからのコピペはしない)
lifegameとは
https://ja.wikipedia.org/wiki/ライフゲーム
これを目指す。
パタヘネ
まずは、プログラムがどのように動くのかを、知るために、パタヘネの上巻、プロセッサの前の章までを読んだ。
今思えば、実装に直接必要のない知識も多いが、この時はよくわからなかったので、とりあえず、読んで、自分の理解をまとめてみた。
プログラムがどのように動いているか
まず、C言語をコンパイルしたものを、謎の数字列が大量に表示される。
catコマンドで見てみると、もっと謎な文字列が表示される。
これは、アセンブルされたものである。
アセンブラ、アセンブリ、アセンブルというよく似た単語は、それぞれ意味が微妙に異なっている。
先ほどの、大量の文字列は、アセンブリを、アセンブラを使い、アセンブルしたものである。
登場するcpu
MIPS 32bit - risc
x86 32bit - cisc
x86-64 64 bit - cisc
32bit cpuの場合
cpuの内部には、レジスタというものが存在する。
これは超高速であるが、そのぶん低容量な、記憶装置である。
記憶装置の価格は、
HDD < SSD < main memory < register
アクセス速度
HDD < SSD < main memory < register
その代わり、容量は、
HDD > SSD > main memory > register
みたいな関係になっている。つまり、CPUが超高速に扱える、変数を一時的に保管できる場所、ただし数は限られている、みたいな認識。
これらにはそれぞれ、役割があり、32という数字は、一度に解釈できるbit数を表している。
intでいうと、例えば、16bit cpuの場合、符号なしの場合は、0 ~ 2 ** 16 - 1 ( = 65535 ) までしか一度に扱うことができず、符号ありの場合は、-32768 から 32767までしか扱うことができない。
これは、各命令も同じであり、すべての命令の長さや、アドレス、数字は、各CPUがあつかうビット数に依存する。
x86 - 32bitCPUの説明に脱線
この記事は、x86(32bit)アーキテクチャのレジスタ一覧だが、
ここでいうと、eipレジスタが、命令を読み込む役割を担っている。
この、eipが読み込むことのできるbit数も、当然32bit以下になる。
32bitCPUがメモリを約4GBまでしか扱えない、というのも、ここからきている。
32bit cpuが扱える範囲は、
2 32 = (2 10) * (2 10) * (2 10) * 2 * 2
2 ** 10は1024なので、1000としてみなすと、
1000 * 1000 * 1000 * 4 bit しか扱えない。
これは、4000000KBであり、4000MBであり、4GBである。
さらに脱線して、64bit cpuの例
ここで、64bit cpuのアセンブリを見てみる。
pushやmovと書いてある部分が、命令。命令には、それぞれ、目的語のようなものがある。
ここでいうと、rbpだったり、rspだったり。これはレジスタの名前。
レジスタだけでなく、即値や、アドレスも目的語のようなものとして扱える。(それ以外は扱えない。)
(gdb) disass main # Dump of assembler code for function main: # 0x0000000100001e00 <+0>: push rbp # 0x0000000100001e01 <+1>: mov rbp,rsp # 0x0000000100001e04 <+4>: sub rsp,0x2a320 # 0x0000000100001e0b <+11>: lea rdi,[rbp-0xe110] # 0x0000000100001e12 <+18>: mov rax,QWORD PTR [rip+0x1e7] # 0x100002000 # 0x0000000100001e19 <+25>: mov rax,QWORD PTR [rax] # 0x0000000100001e1c <+28>: mov QWORD PTR [rbp-0x8],rax # 0x0000000100001e20 <+32>: mov DWORD PTR [rbp-0x2a314],0x0 # 0x0000000100001e2a <+42>: call 0x100001500 <define_init_val> # 0x0000000100001e2f <+47>: lea rsi,[rbp-0x1c210] # 0x0000000100001e36 <+54>: lea rdi,[rbp-0xe110] # 0x0000000100001e3d <+61>: call 0x1000015a0 <cp_first> # 0x0000000100001e42 <+66>: lea rdi,[rbp-0x1c210] # 0x0000000100001e49 <+73>: call 0x100001400 <print_func> # 0x0000000100001e4e <+78>: mov DWORD PTR [rbp-0x2a318],0x0 # 0x0000000100001e58 <+88>: cmp DWORD PTR [rbp-0x2a318],0x3e8 # 0x0000000100001e62 <+98>: jge 0x100001edd <main+221> # 0x0000000100001e68 <+104>: mov edi,0x1 # 0x0000000100001e6d <+109>: call 0x100001f1a # 0x0000000100001e72 <+114>: lea rdi,[rip+0x12b] # 0x100001fa4 # 0x0000000100001e79 <+121>: mov ecx,DWORD PTR [rbp-0x2a318] # 0x0000000100001e7f <+127>: add ecx,0x1 # 0x0000000100001e82 <+130>: mov esi,ecx # 0x0000000100001e84 <+132>: mov DWORD PTR [rbp-0x2a31c],eax # 0x0000000100001e8a <+138>: mov al,0x0 # 0x0000000100001e8c <+140>: call 0x100001f0e # 0x0000000100001e91 <+145>: lea rsi,[rbp-0x2a310] # 0x0000000100001e98 <+152>: lea rdi,[rbp-0x1c210] # 0x0000000100001e9f <+159>: mov DWORD PTR [rbp-0x2a320],eax # 0x0000000100001ea5 <+165>: call 0x1000016c0 <generational_change> # 0x0000000100001eaa <+170>: lea rdi,[rbp-0x2a310] # 0x0000000100001eb1 <+177>: call 0x100001400 <print_func> # 0x0000000100001eb6 <+182>: lea rsi,[rbp-0x2a310] # 0x0000000100001ebd <+189>: lea rdi,[rbp-0x1c210] # 0x0000000100001ec4 <+196>: call 0x100001630 <cp_prev_to_next> # 0x0000000100001ec9 <+201>: mov eax,DWORD PTR [rbp-0x2a318] # 0x0000000100001ecf <+207>: add eax,0x1 # 0x0000000100001ed2 <+210>: mov DWORD PTR [rbp-0x2a318],eax # 0x0000000100001ed8 <+216>: jmp 0x100001e58 <main+88> # 0x0000000100001edd <+221>: mov rax,QWORD PTR [rip+0x11c] # 0x100002000 # 0x0000000100001ee4 <+228>: mov rax,QWORD PTR [rax] # 0x0000000100001ee7 <+231>: mov rcx,QWORD PTR [rbp-0x8] # 0x0000000100001eeb <+235>: cmp rax,rcx # 0x0000000100001eee <+238>: jne 0x100001f02 <main+258> # 0x0000000100001ef4 <+244>: mov eax,0x1 # 0x0000000100001ef9 <+249>: add rsp,0x2a320 # 0x0000000100001f00 <+256>: pop rbp # 0x0000000100001f01 <+257>: ret # 0x0000000100001f02 <+258>: call 0x100001f08 # End of assembler dump.
risc cisc
この二つは、cpu アーキテクチャの、設計思想の違い。
ciscは命令の数がとにかく多い。命令の長さも可変。
反対に、riscは、命令の種類を減らし、回路を単純化することで、演算速度の向上を測るもの。
命令に長さは、固定されていて、すべての演算が1クロックで終了する。
他にも特徴があるが、だいたいこんな感じ。ciscでは、一つの命令で済むようなものも、小さくて高速な命令を組み合わせることで、全体の速度も上がるよねみたいな思想。
例として、分岐の際は、flagを使用したり。。。みたないのがあった気がする。
上にも書いてあるが、x86系は、cisc、armやMIPSは、risc
MIPSのアセンブリに関して。
MIPSは、riscであり、命令の長さが一定である。
今回扱ったのは、32bit cpuなので、一つの命令の中に、01が、32個しかない。
これのうち、最初の6bitが命令を表している。
基本的な命令は、この後、5bit, 5bit, 5bit, 5bit, 6bitとなっている。
000000 00000 00000 00000 00000 000000
左から、op rs rt rd shamt functとなっている。
それぞれの命令で、どれを使うかはすでに決まっている。
この32個の数字を繋げて、32bitになったものを、文字列にしたものが、最初に言ったやつ
MIPSには他にも、命令の形はある。つまり、6,5,5,5,5,6みたいな分け方になっていないものも当然ある。
これらは、最初の6bitの命令を見て、どこからどこまでが何かを判別する。
6,5,5,5,5,6となっているものは、R方式という。これは算術命令の形式。(add など)
6,5,5,16となっているものは、データ転送、分岐、即値命令の形式。
6,26となっているものは、ジャンプ命令の形式。
では、ここで、この5bitに入るものは、どんなものか、ということを考えてみる。
まずはいるのは、レジスタの名前。名前は、すでに決まっていて、$0とか$1みたいな名前。2種類ある。
当然、これより前の命令で、そのレジスタに値が入っていることが必須。
他には、即値。例えば、1など。
MIPSのレジスタ一覧
$zero 0
$v0 - $v1 結果及び式の評価のための値 ( 2 ~ 3 )
$a0 - $a3 引数 ( 4 ~ 7 )
$t0 - $t7 一時 ( 8 ~ 15 )
$s0 - $s7 退避 ( 16 ~ 23 )
$t8 - $t9 予備の予備の一時 ( 24 ~ 25 )
$gp グローバルポインタ 28
$sp スタックポインタ 29
$fp フレームポインタ 30
$ra 戻りアドレス 31
アドレシングモード
アドレスの扱い方。ちょっとよくわかってないので、いつか追記。
即値
レジスタアドレシング
ベース相対アドレシング
PC相対アドレシング
擬似直接アドレシング
ちょっとした例
00af8020
これが表している、アセンブリ言語の命令は何か。
こういう問いに対しては、
まず、2進数に戻す
16進数は、4bitなので、
0->0->0000
0->0->0000
a->10->1010
f->15->1111
8->8->1000
0->0->0000
2->2->0010
0->0->0000
並べると、
00000000101011111000000000100000
最初の6bit(31 ~ 26)が、
000000 00101011111000000000100000
となっているものはR形式だということがわかる(P116)ので、
000000 00101 01111 10000 00000 100000
このように分けられる
その中からさらに、最後の6bitを見てみると、100000となっているものは、addである。
op rs rt rd shamt functなので、それぞれに値を振り分けることができる。
rsが、00101 -> 5
rtが、01111 -> 15
rdが、10000 -> 16
であり、add命令の仕様を見ると、
この3つ全ては、レジスタであり、shamtは使用しないとなっている(00000)
したがって、この命令は、アセンブリにすると、
16 -> $s0
5 -> $a1
15 -> $t7
であることから、
add $s0, $a1, $t7
$s0 = $a1 + $t7
となる。
実装
以上の知識を前提に、x86-64アーキテクチャの資料を探しつつ、実装をしていった。
この記事を書いた時点で、実装は完了していなかったが、この後、実装が完了した。
https://github.com/dooooooooinggggg/lifegame
↑これ↑
もちろん、使った知識、使わなかった知識、どちらもあったが、ここで調べたことが割と役に立った。
が、やはり一番大事なのは、とりあえず手を動かすことだなと感じた。
この実装のそれぞれの要点に関してはいつか気が向いたら書いてみようかなと考えている。