👨‍🏭

Rustでアセンブラを作ってみる

に公開
Rust
シミュレータ
アセンブラ
tech

はじめに

Rustでアセンブラを作成しました。
今回、ラベルを含むMIPS形式のアセンブリを解析する2パスアセンブラを作成しました。

アセンブリ言語とは、プロセッサが認識できる機械語(010B082Aのようなビット列)を、人間にわかりやすい命令形式で書いた言語で、1行1命令処理できます。C言語のような我々が記述する言語のプログラムは、C言語→アセンブリ→機械語のように変換され、プロセッサで実行されるのです。機械語のビット列の何ビット目が何を表すかといったパターンは同じ命令でも様々ですが、その中でも比較的わかりやすいMIPS形式を採用しています。以下に、C言語のプログラムの変換例を示します。

C言語
#include <stdio.h>

int main() {
    int N = 40;
    int a = 0;
    int b = 1;
    int i = 2; 
    int temp;
    int result;
    while (i < N) {
        temp = a + b;
        a = b; 
        b = temp;
        i = i + 1;
    }
    result = b;
    return 0; 
}
アセンブリ
addi $t0, $zero, 40
addi $t1, $zero, 0
addi $t2, $zero, 1
addi $t3, $zero, 2
loop: slt $at, $t0, $t3
bne $at, $zero, end
add $t4, $t1, $t2
add $t1, $t2, $zero (move $t1, $t2)
add $t2, $t4, $zero (move $t2, $t4)
addi $t3, $t3, 1
j loop
end: add $a0, $t2, $zero (move $a0, $t2)
addi $v0, $zero, 10
syscall
機械語
20080028
20090000
200A0001
200B0002
010B082A
14200006
012A6020
01404820
01805020
216B0001
08100004
01402020
2002000A
0000000C

アセンブラはこの変換のうち、アセンブリから機械語への変換を担います。
特に、2パスアセンブラでは、アセンブリファイルを２通り、上から下まで1行ずつ解析します。
まず、1回目ではラベルなどのシンボルの位置を記憶しておくシンボルテーブルを作成し、シンボルの位置を記憶します。このシンボルテーブルは、２回目の読み込みで、まだ読んでいないシンボルへのジャンプ(j, jal命令など)の際に参照します。
２回目ではシンボルテーブルを参照しながら実際にアセンブリを解析します。

実装する上で、以下の工程に分けて作成しました。

  1. Rustプロジェクトを作成する
  2. アセンブリファイルを読み込む
  3. シンボルテーブルを作成する
  4. 命令をラベル、オペコード、オペランドに分解する
  5. 命令を機械語に変換する
    1. オペランドを解析する
    2. 命令ごとに解析する

ディレクトリ階層は以下のようになっています。

assembler/
　├ main.rs
　├ symbol_table.rs
　├ parse_mips_line.rs
　├ transform/
　│　└ transform_instructions.rs
　│　└ transform_operands.rs
　│　└ transform_opecodes.rs
　│　└ transform_shamts.rs
　│　└ transform_functs.rs
　└ transform.rs

$0　Rustプロジェクトを作成する

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

まず、上のコマンドでRustをインストールします。質問には1と答えれば大丈夫です。

rustc --version

インストールが終わったらシェルを再起動し、上のコマンドでバージョンを確認してください。

あとはプロジェクトにmain.rsを作成し、以下のコマンドを叩くことでコンパイルおよび実行ができます。

rustc ./main.rs

./main

$1　アセンブリファイルを読み込む

main.rs
use std::fs::File;
use std::io::{BufRead, BufReader, Error, ErrorKind};

fn main() -> Result<(), Error>{
    let input = File::open("input.asm")?;
    let buffered = BufReader::new(input);
    for line in buffered.lines() {
        let line = line.map_err(|e| Error::new(ErrorKind::Other, e))?;
    Ok(())
}

最初のステップとしてファイルからアセンブリを読み込むところからスタートしました。

Rustではuseを使ってライブラリやモジュールをインポートすることができます。
ファイル関係のBufRead, BufReaderとエラー処理関係のError, ErrorKindをインポートします。

main関数では返り値をResult<(), Error>型にします。
Result型はエラーが発生するかもしれない処理の結果を表現する型で、()の部分はなんでも良く、今回は正常に終了した際にOk(())を返しているので()にしています。

FIle::openはFileライブラリ内のopen関数を呼び出しており、ここでアセンブリファイルを読み込んでいます。

BufReader::new(input)ではBufReader構造体の新しいインスタンスを作成しています。
ここで、BufReaderとともにBufReadをインポートしていますが、BufReaderが構造体であるのに対し、BufReadはBufReader構造体のメソッドを定義し、共通の振る舞いを提供するトレイトです。
ちなみにバッファリングとは、ファイルからデータを読み込む際、プログラムが必要とするデータ量に関わらず、OSに対して一度に大きな塊のデータを読み込むことです。BufReaderはOSからデータを一度に読み込み、内部のバッファに格納し、プログラムには、内部バッファからデータを必要なときに即座に提供できます。これにより、OSとのやり取りの回数が大幅に減少し、読み込み速度が向上します。

let line = line.map_err(|e| Error::new(ErrorKind::Other, e))?;

この右辺のlineはResult型であり、エラーが生じた時にmap_errでエラー型を変換しています。Error::newで新しくエラーのインスタンスを作成し、ErrorKind::Otherでエラーの種類をOtherにしています。

最後の?演算子ですが、これはResultを簡単に扱うための構文糖衣で、エラーが発生したら早期にその関数からリターンすることができます。Ok(value)の場合、Okの中からvalueを取り出し、左辺のlineに代入します。Err(error)の場合、main関数の実行を即座に停止し、そのErr(error)をmain関数の戻り値として返します。

$2　シンボルテーブルを作成する

main.rs
...
fn main() -> Result<(), Error>{
...
    let mut symbol_table = HashMap::new();
    let mut line_number = 0;
    for line in buffered1.lines() {
        let line = line.map_err(|e| Error::new(ErrorKind::Other, e))?;
        symbol_table::make_symbol_table(&mut symbol_table, &line, line_number as i32)?;
        line_number += 1;
    }
...
}
symbol_table.rs
use std::collections::HashMap;
use std::io::Error;

pub fn make_symbol_table(symbol_table: &mut HashMap<String, i32>, line: &str, line_number: i32) -> Result<(), Error> {
    let label = match line.split_once(':') {
        Some((left, _)) => left,
        None => "",
    };
    if label != "" {
        symbol_table.insert(String::from(label.trim()), line_number);
    }
    Ok(())
}

次に、2パスアセンブラの1パス目である、シンボルテーブルの作成を行います。

上記のコードの...は省略を表しています。

シンボルテーブルにはHashMapを利用しました。HashMapはキーと値のペアを保存するための構造であり、キーに対応する値を探索する計算量が\mathcal{O}(1)で済みます。詳しくは以下の記事を見てください

ハッシュテーブル

処理の流れとしては、main関数からmake_symbol_table関数に1行ずつ渡し、シンボルがあればシンボルテーブルにシンボルとその行番目のペアを挿入するといった感じです。

新たにsymbol_table.rsを作成し、そこに関数make_symbol_tableを定義し、main関数で
mod symbol_tableと書いてインポートします。

symbol_tableをmain.rsで宣言するかsymbol_table.rsで宣言するか迷いましたが、これは2パスでやっている以上、main.rsがテーブルの所有権を保持しておいた方が良いと思い、main.rsで宣言しました。所有権については以下の記事を読むと良いです。let mutで宣言することでミュータブル(値が変更可能)になります。それを&mutで関数に渡すことで、関数がsymbol_tableに変更を加えることを可能にしました。

Rustの所有権について

$3　命令をラベル、オペコード、オペランドに分解する

ここから、2パスアセンブラの2パス目のアセンブラコード解析に移ります。
アセンブラはラベル、オペコード、オペランドに分かれており、ラベルはジャンプや分岐命令の目印、オペコードは命令の種類、オペランドは命令実行の対象をそれぞれ表しています。
例えば、以下の例ではendがラベル、addとswがオペコード、$v0, $v1, $v2, $v0, 100, $a0がオペランド、#以降はコメントです。

add $v0, $v1, $v2
end: sw $v0, 100($a0) # end of program
main.rs
...
pub struct Instruction {
    label: String,
    opecode: String,
    operands: Vec<String>,
}

// 2パスアセンブラ
fn main() -> Result<(), Error>{
    // シンボルテーブルを作成
...
    // 命令を解析
    let input2 = File::open("input.asm")?;
    let buffered2 = BufReader::new(input2);
    for line in buffered2.lines() {
        let line = line.map_err(|e| Error::new(ErrorKind::Other, e))?;
        let instruction: Instruction =　parse_mips_line::parse_mips_line(&line)?;
    }
    Ok(())
}

1パス目の時に読み込んだアセンブリファイルを入れておいたバッファですが、lines()メソッドを呼び出すと所有権のムーブが生じ、buffered1は所有権を持たなくなり使えない変数となるので、2パス目ではもう一度アセンブリファイルを読み込み、buffered2に格納します。lines()メソッドでは関数の呼び出し元としてselfを指定し、BufReader型はCopyトレイトを実装していないため、所有権のムーブが生じるのです。Copyトレイトが実装されていれば所有権のムーブは起きず、新しいオブジェクトが作成されて値がコピーされます。

また、新しくInstruction型を定義し、1つの命令をラベル、オペコード、オペランドのまとまりとして扱います。

parse_mips_line.rs
use std::io::{Error, ErrorKind};
use crate::Instruction;

pub fn parse_mips_line(line: &str) -> Result<Instruction, Error>{
    // ラベルを取得
    let label = match line.split_once(':') {
        Some((left, _)) => left,
        None => "",
    };
    let line = match line.split_once(':') {
        Some((_, right)) => right,
        None => line,
    };

    // コメントを削除
    let line = line.split('#').next().unwrap_or("").trim();
    // 空白とカンマとカッコで分割
    let parts: Vec<&str> = line.split(|c| c == ' ' || c == ',' || c == '(' || c == ')').filter(|s| !s.is_empty()).collect();
    if parts.len() < 2 && parts[0] != "syscall" {
        return Err(Error::new(ErrorKind::InvalidInput, "Invalid MIPS line"));
    }
    let opecode = parts[0];
    let operands: Vec<String> = parts[1..].iter().map(|&s| s.to_string()).collect();
    Ok(Instruction { label: label.to_string(), opecode: opecode.to_string(), operands: operands })
}

parse_mips_lineではMIPS形式のアセンブリをラベル、オペコード、オペランドに分割するのですが、データの流れは下のようになります。

ここで注意しないといけないのが、lineは&str型として受け取っているのでlabelやoperandなどは最初は&str型になっていますが、Instruction構造体ではString型で定義されているのでString型にパースしてやらないといけないことです。&strのままだと関数の実行終了時に値が消えてしまうことにも注意です。&strとStringの違いについて詳しくは下の記事を参考にしてください。

&strとStringの違い

$4　命令を機械語に変換する

いよいよ命令を機械語にします。ようやくゴールが見えてきました。

assembler/
　├ main.rs
　├ symbol_table.rs
　├ parse_mips_line.rs
　├ transform/
　│　└ transform_instructions.rs
　│　└ transform_operands.rs
　│　└ transform_opecodes.rs
　│　└ transform_shamts.rs
　│　└ transform_functs.rs
　└ transform.rs

最初にお見せしたディレクトリ階層の残りの部分(transform~)を作っていきます。

$4.1　オペランドを解析する

assembler/transform/配下にtransform_instructions.rs、transform_operands.rs、transform_opecodes.rsを作成します。transform_operands.rs、transform_opecodes.rsでそれぞれオペランド、オペコードを機械語にデコードしてからtransform_instructions.rsで結合します。

transform_instructions.rs
use std::io::Error;
use crate::Instruction;
use std::collections::HashMap;
use crate::transform::transform_operands;

pub fn transformed_instruction(instruction: &Instruction, symbol_table: &HashMap<String, i32>) -> Result<i32, Error> {
    for operand in &instruction.operands {
        let transformed_operand: i32 = transform_operands::transform_operand(&operand, &symbol_table)?;
        println!("transformed_operand: {}", transformed_operand);
    }
    Ok(decoded_instruction)
}
transform_operands.rs
use std::collections::HashMap;
use std::io::{Error, ErrorKind};
use crate::PROGRAM_START;

pub fn transform_operand(operand: &str, symbol_table: &HashMap<String, i32>) -> Result<i32, Error> {
    if operand.parse::<i32>().is_ok() {
        return Ok(operand.parse::<i32>().unwrap());
    }
    if operand.starts_with("$") {
        let reg_number = match operand {
            "$zero" => 0, "$at" => 1, "$v0" => 2, "$v1" => 3, "$a0" => 4,
            "$a1" => 5, "$a2" => 6, "$a3" => 7, "$t0" => 8, "$t1" => 9,
            "$t2" => 10, "$t3" => 11, "$t4" => 12, "$t5" => 13, "$t6" => 14,
            "$t7" => 15, "$s0" => 16, "$s1" => 17, "$s2" => 18, "$s3" => 19,
            "$s4" => 20, "$s5" => 21, "$s6" => 22, "$s7" => 23, "$t8" => 24,
            "$t9" => 25, "$k0" => 26, "$k1" => 27, "$gp" => 28, "$sp" => 29,
            "$fp" => 30, "$ra" => 31,
            _ => return Err(Error::new(ErrorKind::InvalidInput, "Invalid operand")),
        };
        return Ok(reg_number);
    }
    let line_number: i32 = match symbol_table.get(operand) {
        Some(line_number) => *line_number,
        None => return Err(Error::new(ErrorKind::InvalidInput, "Invalid symbol")),
    };
    Ok(line_number)
}

transform_operand関数ではオペランド以下の３つの種類に分けてデコードします。

  1. 即値(そのまま計算に使う値)を&str型からi32型にパースする。
  2. $raのようなレジスタネームをレジスタ番号(0~31)にする。
  3. ラベルをアドレスに変換する。

少し悩ましいのが1.の即値の処理です。オペコードは&str型で与えられ、どのオペコードが即値かを見抜くには文字列が数字から始まるかどうかを調べる必要があるので先頭が0,1のいずれかで始まるかどうかを調べれば良いです。しかし、オペランドをi32型にパースしようと試み、成功すればtrue、失敗すればfalseを返すという処理がrustでは備わっています。こちらの方がなんとなく汎用性が高そうなので今回はこちらを使いました。

2.は文字列が$から始まるという条件で分類でき、3.は1.,2.のどれでもない場合、とすれば良いです。
あとはこの関数をtransform_instructions.rsで呼び出せば良いです。

transform.rs
pub mod transform_instructions;
pub mod transform_operands;

そして今度はmain関数でtransform_instruction関数を呼び出すのですが、ここでRustの使用上の注意があります。Rustでは同じ階層にあるファイルからモジュールをインポートすることはできるのですが、階層が違うとそうはいきません。そこで、例外的にディレクトリ名.rsからは名前の一致するディレクトリのモジュールにアクセスできるという特性を利用します。具体的には、main.rsと同じ階層にtransform.rsをおくと、transform.rsはtransformディレクトリ直下のファイルからモジュールをインポートできるのです。transform_instructionsモジュールをtransform.rsにインポートし、transform.rsからtransform_instructionsモジュールをmain.rsにインポートすることで解決します。transform.rsを仲介してモジュールが上の階層に登っているわけですね。以下の記事がわかりやすいので目を通してみてください。

Rustのmodについて

$4.2　命令ごとに解析する

MIPS形式の命令はR形式、I形式、J形式に分類され、それぞれの機械語の32ビット列の形式は以下のようです。詳しくは以下の記事を見てください。

MIPSアーキテクチャ

R形式:　オペコード(6) | rs(5) | rt(5) | rd(5) | シフト量(5) | 機能(6) |
I形式:　 オペコード(6) | rs(5) | rt(5) |----------即値(16)-----------|
J形式:　オペコード(6) |---------------アドレス(26)--------------|

このrs,rt,rdは先程求めたレジスタ番号であり、I形式の分岐命令の即値とJ形式のアドレスには最初に求めたシンボルの位置などが入ります。

I,J形式はオペコードだけで命令の種類が確定しますが、R形式はオペコードに加えて機能(funct)で命令の種類が決まります。また、シフト命令はシフト量(shamt)でどれだけシフトするかが決まります。

よって以下ではオペコード、シフト量(shamt)、機能(funct)の解析をします。

transform_opecodes.rs
use std::io::{Error, ErrorKind};

pub fn transform_opecode(opecode: &str) -> Result<i32, Error> {
    match opecode {
        "add"
        | "sub"
        | "and"
        | "or"
        | "slt"
        | "sll"
        | "srl"
        | "jr"
        | "syscall" => Ok(0x00),
        "addi" => Ok(0x08),
        "lw" => Ok(0x23),
        "sw" => Ok(0x2B),
        "beq" => Ok(0x04),
        "bne" => Ok(0x05),
        "slti" => Ok(0x0A),
        "j" => Ok(0x02),
        "jal" => Ok(0x03),
        _ => Err(Error::new(ErrorKind::InvalidInput, "Invalid opecode")),
    }
}
transform_shamts.rs
use std::io::Error;

pub fn transform_shamt(opecode: &str) -> Result<i32, Error> {
    match opecode {
        "sll" => Ok(0x00),
        "srl" => Ok(0x02),
        _ => Ok(0x00),
    }
}
transform_functs.rs
use std::io::{Error, ErrorKind};

pub fn transform_funct(opecode: &str) -> Result<i32, Error> {
    match opecode {
        "add" => Ok(0x20),
        "sub" => Ok(0x22),
        "and" => Ok(0x24),
        "or" => Ok(0x25),
        "slt" => Ok(0x2A),
        "sll" => Ok(0x00),
        "srl" => Ok(0x02),
        "jr" => Ok(0x08),
        "syscall" => Ok(0x0C),
        _ => Err(Error::new(ErrorKind::InvalidInput, "Invalid funct")),
    }
}

オペコード、シフト量(shamt)、機能(funct)はそれぞれtransform_opecodes.rs,transform_shamts.rs,transform_functs.rs
で解析しました。解析といってもmatch文を用いで分類するだけです。

transform_instructions.rs
use std::io::{Error, ErrorKind};
use crate::Instruction;
use std::collections::HashMap;
use crate::transform::transform_operands;
use crate::transform::transform_opecodes;
use crate::transform::transform_shamts;
use crate::transform::transform_functs;
use crate::PROGRAM_START;

pub fn transforme_instruction(instruction: &Instruction, symbol_table: &HashMap<String, i32>, line_number: &i32) -> Result<i32, Error> {
    let decoded_instruction: i32;
    let transformed_opecode: i32 = transform_opecodes::transform_opecode(&instruction.opecode)?;

    match transformed_opecode {
        0x00 => {
            let transformed_funct: i32 = transform_functs::transform_funct(&instruction.opecode)?;
            match transformed_funct {
                0x0C => {
                    // システムコール
                    decoded_instruction = transformed_funct;
                },
                _ => {
                    // R形式命令
                    let transformed_rd: i32 = transform_operands::transform_operand(&instruction.operands[0], &symbol_table)?;
                    let transformed_rs: i32 = transform_operands::transform_operand(&instruction.operands[1], &symbol_table)?;
                    let transformed_rt: i32 = transform_operands::transform_operand(&instruction.operands[2], &symbol_table)?;
                    let transformed_shamt: i32 = transform_shamts::transform_shamt(&instruction.opecode)?;
                    decoded_instruction = transformed_opecode << 26 | transformed_rs << 21 | transformed_rt << 16 | transformed_rd << 11 | transformed_shamt << 6 | transformed_funct;
                },
            }
        },
        0x08 | 0x0A => {
            // I形式命令(即値演算)
            let transformed_rt: i32 = transform_operands::transform_operand(&instruction.operands[0], &symbol_table)?;
            let transformed_rs: i32 = transform_operands::transform_operand(&instruction.operands[1], &symbol_table)?;
            let transformed_imm: i32 = transform_operands::transform_operand(&instruction.operands[2], &symbol_table)?;
            decoded_instruction = transformed_opecode << 26 | transformed_rs << 21 | transformed_rt << 16 | transformed_imm;
        },
        0x23 | 0x2B => {
            // I形式命令(ロード・ストア)
            let transformed_rt: i32 = transform_operands::transform_operand(&instruction.operands[0], &symbol_table)?;
            let transformed_imm: i32 = transform_operands::transform_operand(&instruction.operands[1], &symbol_table)?;
            let transformed_rs: i32 = transform_operands::transform_operand(&instruction.operands[2], &symbol_table)?;
            decoded_instruction = transformed_opecode << 26 | transformed_rs << 21 | transformed_rt << 16 | transformed_imm;
        },
        0x04 | 0x05 => {
            // I形式命令(条件分岐)
            let transformed_rs: i32 = transform_operands::transform_operand(&instruction.operands[0], &symbol_table)?;
            let transformed_rt: i32 = transform_operands::transform_operand(&instruction.operands[1], &symbol_table)?;
            let transformed_imm: i32 = transform_operands::transform_operand(&instruction.operands[2], &symbol_table)? - line_number - 1; // 最後の定数は要調整
            decoded_instruction = transformed_opecode << 26 | transformed_rs << 21 | transformed_rt << 16 | transformed_imm;
        },
        0x02 | 0x03 => {
            // J形式命令
            let transformed_addr: i32 = transform_operands::transform_operand(&instruction.operands[0], &symbol_table)?;
            decoded_instruction = transformed_opecode << 26 | transformed_addr + (PROGRAM_START >> 2);
        },
        _ => {
            return Err(Error::new(ErrorKind::InvalidInput, "Invalid opecode"));
        },
    }
    Ok(decoded_instruction)
}

最後に、以上で作成したオペコード、shamt、funct、即値、アドレス、レジスタ番号を結合して機械語命令を完成させます。

今回、システムコールでアセンブリプログラムが停止するようにしたのでシステムコール用のオペコードとfunctを用意しました。

I形式命令は少しややこしく、即値演算、ロード・ストア、条件分岐でそれぞれ処理が異なります。
参考程度にそれぞれ以下のような命令形式をしています。immは即値です。

  • 即値命令：addi rt, rs, imm
  • ロード・ストア：sw rt, imm(rs)
  • 条件分岐：bne rs, rt, imm

ここで、条件分岐のimmはジャンプするシンボルのある行と現在読んでいる行の差であることにも注意です。

最初のuse文の部分ですが、transform_operands.rsなどは同じディレクトリなのでuse transform_operandsのみでインポートできると思っていたのですが、どうやらそれだとRust側がインポート先を認識できないらしく、use crate::transform::transform_operandsを使用しました。crateはクレート(Rustプロジェクトのルート)のディレクトリを指します。

これで完成です！！
試しに以下のフィボナッチプログラムをパースしてみます。

addi $t0, $zero, 40
addi $t1, $zero, 0
addi $t2, $zero, 1
addi $t3, $zero, 2
loop: slt $at, $t0, $t3
bne $at, $zero, end
add $t4, $t1, $t2
add $t1, $t2, $zero
add $t2, $t4, $zero
addi $t3, $t3, 1
j loop
end: add $a0, $t2, $zero
addi $v0, $zero, 10
syscall

出力は以下のようになりました。検算したところあってそうです！

20080028
20090000
200A0001
200B0002
010B082A
14200005
012A6020
01404820
01805020
216B0001
08100004
01402020
2002000A
0000000C

最後に

以上でアセンブリが完成したわけですが、実際に作ってみるとかなり歯応えのある内容です。最初の方はかなりエラーが出たのですが、基本的に所有権と型の問題であることが多かったです。Rustの練習としても良いと思うのでぜひやってみてください。以下にコードを置いておきます。

https://github.com/MitsumasaNaito/rust-2path-assembly

参考

https://zenn.dev/hakoten/articles/8ae9dd0d3a2080

https://zenn.dev/zenn/articles/markdown-guide#fnref-e2b9-1

https://qiita.com/shikuno_dev/items/139ea89a3af5d925ebf9

https://zenn.dev/collabostyle/articles/cfaf3316c8b32f

https://qiita.com/kikyo_nanakusa/items/a649bed9ffac808159e2

https://qiita.com/alswnd/items/428014509e52297b3a1b

Discussion