CPUから実装してどこまで行けるか？　その２－アセンブラ

リンク情報システムのアドベントカレンダーで書いた[CPUから実装してどこまで行けるか？](https://qiita.com/dgkz/items/437426b6b50f41e718c7)の続きです。
前回はツブツブ論理回路からCPUとRAMなどを作成しました。今回は第２回としてアセンブラを作成します。

[コンピュータシステムの理論と実装](https://www.oreilly.co.jp/books/9784873117126/)の仕様を元にして、CPUに入力可能な機械語をアセンブリを元にアセンブラで生成します。機械語の命令１つに対してアセンブリ１行が対応付けられますので非常に簡単です。
アセンブラは、ほぼ文字列操作なので超高級言語で書いたほうが断然楽なのですが、勉強も兼ねてRustでトライしています。Rustは初心者なので誤りがあったら指摘ください。
[コンピュータシステムの理論と実装](https://www.oreilly.co.jp/books/9784873117126/)で記載されているアセンブラの詳細仕様に準拠すると書きづらいのは分かっているので、適当にプログラム構造は変えています。

今回、アセンブラ実装と一緒にVRAM対応を行ってVGAに描画可能としました。VGA出力の実装は次回か次々回の記事に書く予定です。
以下はVGA出力した際の画像です。VRAMサイズの都合により白黒です。
![VGA.png](https://qiita-image-store.s3.amazonaws.com/0/272860/63811b84-f6ee-8efd-b8ec-e99aa9a73a68.png)
VGA出力をちまちまやっていると、この位置に出力されてて本当にあっているか不安になるので、網目を一緒に出力しています。


# Myアセンブラの構造
これだけです。

``` 疑似コード
main()
    Assembler::exec()
        for 指定されたDir内のasmファイルでグルグル
            create_symbol_tble()            // シンボルテーブルの作成
            assemble()                      // アセンブル
                Parser::get_command_type()  // コマンドタイプの取得
                if A命令だったら
                    if A命令が数値だったら
                        リテラル、または直アドレスとしてA命令の機械語を出力
                    else
                        シンボルテーブルからアドレスを取得
                        取得出来なかったら、そのシンボルとアドレスをシンボルテーブルに登録
                        アドレスをA命令として機械語を出力
                if C命令だったら
                    C命令として機械語を出力
```

# コード
## main.rs
まずはmain()です。
引数の入力チェックとアセンブルを実行しているだけです。
引数は１つで、*.asmが格納されているディレクトリか、asmファイルを１つ指定します。

```rust:main.rs
use std::env;

extern crate asm;
use asm::assembler::Assembler;

fn main() {
    // 引数チェック
    if env::args().len() != 2 {
        println!("引数が不正です。*.asmが格納されているディレクトリかファイルを１つ指定してください");
        return;
    }

    // asmファイル
    let args: Vec<String> = env::args().collect();
    let filepath = &args[1];
    println!("filepath = {}", filepath);

    // アセンブル
    let mut assembler = Assembler::new();
    assembler.exec(filepath.to_string());
}
```
Rust的な記述は以下。

```rust
extern crate asm;
use asm::assembler::Assembler;
```
外部モジュールを呼ぶときは`extern crate xxx`とすると後述のlib.rsを読み込んでくれます。
`use asm::assembler::Assembler;` はクレート名を省略して Assembler を直で書けるようにしてくれます。
一番単純なプログラムは main.rs がルートになるbinクレートだけのプログラムですが、外部ファイルのプログラムを利用する場合は lib.rs をルートとするxxx クレートを作成します。
なので、今回はbinクレートとasmクレートを作った感じです。

## lib.rs
```rust:lib.rs
extern crate regex;
pub mod assembler;
pub mod code;
pub mod parser;
pub mod symbol_table;
```
asmクレートに所属するファイルを書きます。
正規表現を使ったのでregexをexternしています。各ファイル内で使用する他のクレートは各ファイルに書いてもコンパイル通らないです。lib.rsに書く必要があります。今回はregexがそれにあたります。


## assembler.rs
ちょっと長いので、ソース内にコメント付けて説明します。

```rust:assembler.rs
use code::Code;
use parser;
use parser::Parser;
use std::fs;

use std::io::{BufRead, BufReader, BufWriter, Write};
use std::path::Path;
use std::string::ToString;
use symbol_table::SymbolTable;

// Rustにクラスはないです。structがそれにあたります。
// structブロックにフィールドを定義して、implブロックでメソッドを書きます。
pub struct Assembler {
    ram_addr: u16,
}

// メソッドの実装です
impl Assembler {
    // コンストラクタです。
    pub fn new() -> Assembler {
        // フィールドの初期化はここで行います。
        Assembler { ram_addr: 0x0010 }
    }

    ///
    /// アセンブルの実行
    ///
    pub fn exec(&mut self, filepath: String) {
        let infilepath = filepath.to_string();

        // 引数のパスから.asmファイルのリストを取得する
        let file_list = self.get_file_list(&infilepath);

        // ファイル数分、回します。
        for asm_file_path in file_list {
            // 入出力のパス
            let inpath = Path::new(&asm_file_path);
            let mut outfilepath = String::from(
                inpath
                    .with_file_name(inpath.file_stem().unwrap())
                    .to_str()
                    .unwrap(),
            );
            outfilepath = outfilepath + ".code";

            // シンボルテーブルの作成
            // パースする前に全なめしてシンボルをテーブルに登録します。
            let st = self.create_symbol_tble(asm_file_path.to_string());

            // アセンブルの実行
            self.assemble(st, asm_file_path.to_string(), outfilepath.to_string());
            println!(
                "assemble in:{} out:{}",
                asm_file_path.to_string(),
                outfilepath
            );
        }
    }

    ///
    /// シンボルテーブルを作成する
    ///
    fn create_symbol_tble(&self, filepath: String) -> SymbolTable {
        let mut st = SymbolTable::new();
        st.init();
        let parser = Parser::new();

        let infile = fs::File::open(filepath.to_string()).unwrap();
        let reader = BufReader::new(infile);
        let mut rom_addr = 0;
        for line in reader.lines() {
            // コメント、空白行などを除去
            let line = parser.get_valid_line(&mut line.unwrap());
            if line.is_empty() {
                continue;
            }

            println!("{}: line = {}", rom_addr, line);

            // 括弧で囲まれていたらシンボル。括弧を取り除いてシンボルテーブルに登録
            // 括弧が無かったら通常の命令としてアドレスをインクリ
            if line.starts_with("(") {
                let line = line.replace("(", "");
                let line = line.replace(")", "");
                st.add_entry(line, rom_addr);
            } else {
                rom_addr += 1;
            }
        }

        return st;
    }

    ///
    /// パスから.asmファイルのリストを取得する
    /// ディレクトリの場合は配下のファイルのリストを返す
    ///
    fn get_file_list(&self, inpath_str: &str) -> Vec<String> {
        let mut vec: Vec<String> = vec![];
        let inpath = Path::new(inpath_str);

        // ファイル指定
        if !inpath.is_dir() {
            vec.push(String::from(inpath.to_str().unwrap()));
            return vec;
        }

        // ディレクトリ指定
        let paths = fs::read_dir(inpath_str).unwrap();
        for path in paths {
            let path = path.unwrap().path();
            let ext = path.extension().unwrap().to_str().unwrap();
            if "asm" != ext {
                continue;
            }

            let asm_path = path.display().to_string();
            vec.push(asm_path.to_string());
        }
        return vec;
    }

    ///
    /// アセンブル
    ///
    fn assemble(&mut self, mut st: SymbolTable, filepath: String, outfilepath: String) {
        let parser = Parser::new();
        let code = Code::new();

        let infile = fs::File::open(filepath.to_string()).unwrap();
        let mut out_buf = BufWriter::new(fs::File::create(outfilepath).unwrap());

        let reader = BufReader::new(infile);
        for line in reader.lines() {
            // コメント、空白行などを除去
            let line = parser.get_valid_line(&mut line.unwrap());
            if line.is_empty() {
                continue;
            }

            // コマンドタイプの取得
            let command_type = parser.get_command_type(line.to_string());

            // シンボルの取得
            let mut symbol: String = "".to_string();
            if command_type == parser::A_COMMAND || command_type == parser::L_COMMAND {
                symbol = parser.get_symbol(line.to_string());
                //println!("get_symbol line = {} -> {}", line, symbol);
            }

            let mut out_code = "".to_string();

            // A命令
            if command_type == parser::A_COMMAND {
                let mut address;

                // 数値はそのままアドレス
                if symbol.parse::<u16>().is_ok() {
                    address = symbol.parse::<u16>().unwrap();
                } else {
                    // シンボルテーブルに存在したらアドレスをもらう
                    if st.contains(&symbol) {
                        address = *st.get_address(symbol);
                    } else {
                        // シンボル登録
                        st.add_entry(symbol, self.ram_addr);
                        address = self.ram_addr;
                        self.ram_addr += 1;
                    }
                }

                out_code = format!("{:0>16b} //{}\n", address, line.to_string());
            }

            // C命令
            if command_type == parser::C_COMMAND {
                // dest=comp;jmp の取得
                let comp = parser.get_comp(line.to_string());
                let dest = parser.get_dest(line.to_string());
                let jump = parser.get_jmp(line.to_string());

                // dest=comp;jmp をコード化
                let comp_code = code.comp(comp.to_string());
                let dest_code = code.dest(dest.to_string());
                let jump_code = code.jump(jump.to_string());
                let code_val = (7 << 13) | (comp_code << 6) | (dest_code << 3) | jump_code;

                out_code = format!("{:0>16b} //{}\n", code_val, line.to_string());
            }

            // ファイルに出力
            //print!("{}", out_code);
            out_buf.write(out_code.as_bytes()).unwrap();
        }
    }
}
```

Rust は unwrap() が少々ウザったい感触を受けます。
unwrapは戻り値が Option&lt;T&gt; や Result&lt;T,E&gt; でラップされている場合などで、処理結果を取り出すときに使用します。エラーが発生していた場合にunwrap()を呼ぶとpanicで落ちます。
プログラム言語はエラーを戻り値か例外で扱いますが、Rustは戻り値方式です。
エラーが発生しうる処理は戻り値を Option&lt;T&gt; や Result&lt;T,E&gt; でラップして返却します。呼び出し元は Optiont&lt;T&gt;またはResult&lt;T,E&gt; をunwrap()して結果を取得しますが、エラーの場合はpanicになるという方式。


## symbol_table.rs
シンボルを保持するやつです。
ここでのシンボルはアドレスを示す文字列のことです。
シンボルは２通りあって、ジャンプ先を示すシンボルと、変数としてのシンボルがあります。両方ともアドレスを割り当てます。
ジャンプ先アドレスは「(symbol)」のように括弧で囲んだ形で書かれます。変数は「<span>@</span>symbol」の形式です。

定義済みシンボルというものがあって、スタックの先頭ポインタ（SP）を格納するアドレスや、メモリにマップされるSCREENの先頭アドレスなどが定義されます。
シンボルテーブルには定義済みシンボルと、プログラムで定義されたシンボルをHashMapに格納、管理します

```rust:symbol_table.rs
use std::collections::HashMap;

pub struct SymbolTable {
    symbol_map: HashMap<String, u16>,
}

impl SymbolTable {
    pub fn new() -> SymbolTable {
        SymbolTable {
            symbol_map: HashMap::new(),
        }
    }

    ///
    /// 初期化
    /// 定義済みシンボルをMapに入れとく
    ///
    pub fn init(&mut self) {
        self.symbol_map.insert("SP".to_string(), 0x0000);
        self.symbol_map.insert("LCL".to_string(), 0x0001);
        self.symbol_map.insert("ARG".to_string(), 0x0002);
        self.symbol_map.insert("THIS".to_string(), 0x0003);
        self.symbol_map.insert("THAT".to_string(), 0x0004);
        self.symbol_map.insert("R0".to_string(), 0x0000);
        self.symbol_map.insert("R1".to_string(), 0x0001);
        self.symbol_map.insert("R2".to_string(), 0x0002);
        self.symbol_map.insert("R3".to_string(), 0x0003);
        self.symbol_map.insert("R4".to_string(), 0x0004);
        self.symbol_map.insert("R5".to_string(), 0x0005);
        self.symbol_map.insert("R6".to_string(), 0x0006);
        self.symbol_map.insert("R7".to_string(), 0x0007);
        self.symbol_map.insert("R8".to_string(), 0x0008);
        self.symbol_map.insert("R9".to_string(), 0x0009);
        self.symbol_map.insert("R10".to_string(), 0x000A);
        self.symbol_map.insert("R11".to_string(), 0x000B);
        self.symbol_map.insert("R12".to_string(), 0x000C);
        self.symbol_map.insert("R13".to_string(), 0x000D);
        self.symbol_map.insert("R14".to_string(), 0x000E);
        self.symbol_map.insert("R15".to_string(), 0x000F);
        self.symbol_map.insert("SCREEN".to_string(), 0x4000);
        self.symbol_map.insert("KBD".to_string(), 0x6000);
    }

    ///
    /// 指定のシンボルが登録済みか？
    ///
    pub fn contains(&self, symbol: &String) -> bool {
        return self.symbol_map.contains_key(symbol);
    }

    ///
    /// シンボルを登録する
    ///
    pub fn add_entry(&mut self, symbol: String, address: u16) {
        self.symbol_map.insert(symbol, address);
    }

    ///
    /// 指定のシンボルのアドレスを返す
    ///
    pub fn get_address(&self, symbol: String) -> &u16 {
        return self.symbol_map.get(&symbol).unwrap();
    }
}
```


## parser.rs
アセンブリのパーサです。
入力されたアセンブリを解析してコマンドのタイプやニーモニックを返します。アセンブリの文法が単純なので楽ちんなパーサです。
解析位置の管理はパーサでは行わなず、呼び出し元が読んだ行を渡してもらって、その内容に従って解析結果を返却します。


```rust:parser.rs
use regex::Regex;

pub const A_COMMAND: &str = "A";
pub const C_COMMAND: &str = "C";
pub const L_COMMAND: &str = "L";

///
/// パーサ
///
pub struct Parser {}

impl Parser {
    pub fn new() -> Parser {
        Parser {}
    }

    ///
    /// 空白行、コメントの場合、ブランク文字列を返す
    ///
    pub fn get_valid_line(&self, line: &mut String) -> String {
        let mut line = line.trim().to_string();

        if line.is_empty() {
            return "".to_string();
        }
        if line.starts_with("//") {
            return "".to_string();
        }

        if line.contains("//") {
            let comment_line = line;
            let sep: Vec<&str> = comment_line.split("//").collect();
            line = sep.get(0).unwrap().to_string();
        }

        return line.trim().to_string();
    }

    ///
    /// コマンドタイプを返す
    ///
    pub fn get_command_type(&self, line: String) -> &str {
        if line.starts_with("@") {
            return A_COMMAND;
        }
        if line.contains("=") {
            return C_COMMAND;
        }
        if line.contains(";") {
            return C_COMMAND;
        }

        return L_COMMAND;
    }

    ///
    /// シンボルを抽出する
    ///
    pub fn get_symbol(&self, line: String) -> String {
        let line = line.trim().to_string();
        if line.contains("@") {
            return line.replace("@", "");
        }
        if line.contains("(") {
            let re = Regex::new(r"\(|\)").unwrap();
            return String::from(re.replace_all(&line, ""));
        }

        return line;
    }

    ///
    /// C命令のdestニーモニックを返す
    ///
    pub fn get_dest(&self, line: String) -> String {
        let line = line.trim().to_string();
        let sep: Vec<&str> = line.split("=").collect();
        if sep.len() == 2 {
            return sep.get(0).unwrap().to_string();
        }

        return "".to_string();
    }

    ///
    /// C命令のcompニーモニックを返す
    ///
    pub fn get_comp(&self, line: String) -> String {
        let line = line.trim().to_string();
        let sep: Vec<&str> = line.split("=").collect();
        if sep.len() == 2 {
            return sep.get(1).unwrap().to_string();
        }

        let comp_sep: Vec<&str> = line.split(";").collect();
        if comp_sep.len() == 2 {
            return comp_sep.get(0).unwrap().to_string();
        }

        return "".to_string();
    }

    ///
    /// C命令のjumpニーモニックを返す
    ///
    pub fn get_jmp(&self, line: String) -> String {
        let line = line.trim().to_string();
        let sep: Vec<&str> = line.split(";").collect();
        if sep.len() == 2 {
            return sep.get(1).unwrap().to_string();
        }

        return "".to_string();
    }
}
```

## code.rs
アセンブリの各部位をコードに変換します。

```rust:code.rs
pub struct Code {}

impl Code {
    pub fn new() -> Code {
        Code {}
    }

    // dest部のパース
    pub fn dest(&self, mnemonic: String) -> u16 {
        match mnemonic.as_str() {
            "" => 0,
            "0" => 0,
            "M" => 1,
            "D" => 2,
            "MD" => 3,
            "A" => 4,
            "AM" => 5,
            "AD" => 6,
            "AMD" => 7,
            _ => panic!("Invalid dest mnemonic: {}", mnemonic),
        }
    }

    // comp部のパース
    pub fn comp(&self, mnemonic: String) -> u16 {
        match mnemonic.as_str() {
            "" => 0,
            "0" => 0b0101010,
            "1" => 0b0111111,
            "-1" => 0b0111010,
            "D" => 0b0001100,
            "A" => 0b0110000,
            "M" => 0b1110000,
            "!D" => 0b0001101,
            "!A" => 0b0110001,
            "!M" => 0b1110001,
            "-D" => 0b0001111,
            "-A" => 0b0110011,
            "-M" => 0b1110011,
            "D+1" => 0b0011111,
            "A+1" => 0b0110111,
            "M+1" => 0b1110111,
            "D-1" => 0b0001110,
            "A-1" => 0b0110010,
            "M-1" => 0b1110010,
            "D+A" => 0b0000010,
            "D+M" => 0b1000010,
            "D-A" => 0b0010011,
            "D-M" => 0b1010011,
            "A-D" => 0b0000111,
            "M-D" => 0b1000111,
            "D&A" => 0b0000000,
            "D&M" => 0b1000000,
            "D|A" => 0b0010101,
            "D|M" => 0b1010101,
            _ => panic!("Invalid comp mnemonic: {}", mnemonic),
        }
    }

    // jump部のパース
    pub fn jump(&self, mnemonic: String) -> u16 {
        match mnemonic.as_str() {
            "" => 0,
            "JGT" => 1,
            "JEQ" => 2,
            "JGE" => 3,
            "JLT" => 4,
            "JNE" => 5,
            "JLE" => 6,
            "JMP" => 7,
            _ => panic!("Invalid jump mnemonic: {}", mnemonic),
        }
    }
}
```

これだけです。アセンブラとかいうと身構えるかも知れませんが、コメントを含めても490ステップでした。

# 出力
一応、アセンブルした結果サンプルを張っておきます。
以下は極短いファイルのサンプルですが、長いのやシンボル付きのファイルもちゃんとアセンブルできます。

```asm:Add.asm（入力）
@2
D=A
@3
D=D+A
@0
M=D
```

```bin:Add.code（出力結果）
0000000000000010 //@2
1110110000010000 //D=A
0000000000000011 //@3
1110000010010000 //D=D+A
0000000000000000 //@0
1110001100001000 //M=D
```


# 展望
コンピュータシステムの理論と実装のCPU仕様により、少々回りくどい機械語を書く必要があります。
例えば、以下をやりたい場合、

```asm
R0 = 2 + 3
```

こんなアセンブリを書く必要があります。

```asm
@2      // 2をAレジスタに設定
D=A     // Aレジスタの値（2）をDレジスタにコピー
@3      // 3をAレジスタに設定
D=D+A   // Dレジスタ（2）とAレジスタ（3）を足し算して、Dレジスタに5を書き戻す
@0      // R0のアドレス（0）をAレジスタに設定
M=D     // Dレジスタ（5）をM[R0(0)]に入れる
```

まだ今はアセンブリを機械語に変換するだけなので良いのですが、VM言語コンパイラを書く時に楽したいです。（VM言語コンパイラは、VM言語をアセンブリにコンパイルします）
なので、展望として以下の形でアセンブリを書けるようにします。出力する機械語は上記と同じ。

```asm
@0=2+3
@R0=val1+val2
```

今回は基本部分の作成までとして、上記は対応していません。次回です。