コンピュータシステムの理論と実装の6章のアセンブラを実装しました

コンピュータシステムの理論と実装 nand2tetris アセンブラ 機械語 C言語

前回の続きです。今回はコンピュータシステムの理論と実装（以下、nand2tetris本）の6章のアセンブラをC言語*1で実装してみました。

今回のコード

下記、タグv0.0.1になります。

github.com

下記で動かせます。

git clone -b v0.0.1 https://github.com/nihemak/nand2tetris.git
cd nand2tetris
# download nand2tetris environment
./setup.sh
# test all
./test.sh

概要

今回、実装したのはASMファイル(アセンブリコード)を入力として受け取りHACKファイル(バイナリコード)を生成するコマンドです。

f:id:nihma:20200506160824p:plain

ASMファイル(アセンブリコード)には下記の要素が含まれます。このうちの命令を対応するバイナリコードに翻訳していきます。

  • スキップするもの
    • 空白
    • コメント
    • 改行(EOL)
    • EOF
  • 命令
    • A命令: @value
      • value
        • アドレス(数値)
        • シンボル(数値以外から始まる)
          • 定義済みシンボル
          • ラベルシンボル
          • 変数シンボル
    • C命令: dest=comp;jump
      • destが省略の場合は=も省略
      • jumpが省略の場合は;も省略
  • ラベルシンボル: (Xxx)

下記はASMファイル(アセンブリコード)の例です。

04/mult/mult.asm

// Multiplies R0 and R1 and stores the result in R2.
// (R0, R1, R2 refer to RAM[0], RAM[1], and RAM[2], respectively.)

        @R1
        D=M
        @n
        M=D
        @R2
        M=0
(LOOP)
        @n
        D=M
        @END
        D;JEQ
        @R0
        D=M
        @R2
        M=D+M
        @n
        M=M-1
        @LOOP
        0;JMP
(END)
        @END
        0;JMP

生成するHACKファイル(バイナリコード)は次の形式です。

  • テキスト形式
  • 16ビットの機械語命令が0or1のASCII文字列として16文字並ぶ
  • 機械語命令の後ろに改行文字が入る

下記はHACKファイル(バイナリコード)の例です。

04/mult/mult.asmのバイナリコード

0000000000000001
1111110000010000
0000000000010000
1110001100001000
0000000000000010
1110101010001000
0000000000010000
1111110000010000
0000000000010010
1110001100000010
0000000000000000
1111110000010000
0000000000000010
1111000010001000
0000000000010000
1111110010001000
0000000000000110
1110101010000111
0000000000010010
1110101010000111

なお、今回は書籍で提示された設計にできるだけ従うようにしてみました。*2またASMファイル(アセンブリコード)にエラーが含まれていない前提としています。そして、実行時の例外に対応する処理もだいぶ省いています。*3

シンボルを含まないプログラムのためのアセンブラ

書籍ではまず下記の要素が含まれない前提のアセンブラを実装します。

  • 命令
    • A命令: @value
      • value
        • シンボル(数値以外から始まる)
          • 定義済みシンボル
          • ラベルシンボル
          • 変数シンボル
  • ラベルシンボル: (Xxx)

下記のように実装を行いました。コードは06/AssemblerL/です。

f:id:nihma:20200506175405p:plain

下記で使えます。

test.sh:L53-L84

cp ./nand2tetris/projects/06/max/MaxL.asm 06/AssemblerL/

# ...(省略)...

cd 06/AssemblerL/

clang --std=c11 -Wall -Wextra -o AssemblerL main.c Parser.c Code.c

echo "MaxL"
./AssemblerL MaxL.asm

Parserモジュール

ASMファイル(アセンブリコード)をパースするためのモジュールです。
main.cで利用する関数はParser.hで下記のように定義しました。parser構造体はtypedefして定義はParser.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はParser.cで行いました。

06/AssemblerL/Parser.h:L19-L28

typedef struct parser * Parser;

Parser Parser_init(FILE *fpAsm);
bool Parser_hasMoreCommands(Parser thisObject);
void Parser_advance(Parser thisObject);
Parser_CommandType Parser_commandType(Parser thisObject);
void Parser_symbol(Parser thisObject, char *symbol);
void Parser_dest(Parser thisObject, char *dest);
void Parser_comp(Parser thisObject, char *comp);
void Parser_jump(Parser thisObject, char *jump);

上記の関数の中で使う関数はParser.c内で下記のように定義しました。ASMファイルストリーム(FILE *fpAsm)に対するfgetcおよびungetcは下記で行うようにしています。

06/AssemblerL/Parser.c:L15-L23

bool isSpace(FILE *fpAsm);
bool isComment(FILE *fpAsm);
bool isEndOfFile(FILE *fpAsm);
bool isEndOfLine(FILE *fpAsm);
bool isAdvance(FILE *fpAsm);
void skipSpaces(FILE *fpAsm);
void skipEndOFLines(FILE *fpAsm);
void skipComment(FILE *fpAsm);
void moveNextAdvance(FILE *fpAsm);

Codeモジュール

C命令のニーモニックとバイナリのマッピングするためのモジュールです。
main.cで利用する関数はCode.hで下記のように定義しました。それぞれの実装はCode.cで行いました。

06/AssemblerL/Code.h:L4-L6

void Code_dest(char *mnemonic, char *dest);
void Code_comp(char *mnemonic, char *comp);
void Code_jump(char *mnemonic, char *jump);

それぞれの関数はC命令のニーモニックとバイナリのマッピングを行いますが可読性を向上させるためCode.cに下記の関数マクロを定義して使いました。

06/AssemblerL/Code.c:L4

#define IF_CMP_CPY(condVar, condStr, destVar, destStr) if (strcmp(condVar, condStr) == 0) strcpy(destVar, destStr)

それぞれのマッピングは下記の通りです。

06/AssemblerL/Code.c:L6-L50

void Code_dest(char *mnemonic, char *dest)
{
    IF_CMP_CPY(mnemonic,    "", dest, "000");
    IF_CMP_CPY(mnemonic,   "M", dest, "001");
    IF_CMP_CPY(mnemonic,   "D", dest, "010");
    IF_CMP_CPY(mnemonic,  "MD", dest, "011");
    IF_CMP_CPY(mnemonic,   "A", dest, "100");
    IF_CMP_CPY(mnemonic,  "AM", dest, "101");
    IF_CMP_CPY(mnemonic,  "AD", dest, "110");
    IF_CMP_CPY(mnemonic, "AMD", dest, "111");
}

void Code_comp(char *mnemonic, char *comp)
{
    IF_CMP_CPY(mnemonic,   "0", comp, "0101010");
    IF_CMP_CPY(mnemonic,   "1", comp, "0111111");
    IF_CMP_CPY(mnemonic,  "-1", comp, "0111010");
    IF_CMP_CPY(mnemonic,   "D", comp, "0001100");
    IF_CMP_CPY(mnemonic,   "A", comp, "0110000"); IF_CMP_CPY(mnemonic,   "M", comp, "1110000");
    IF_CMP_CPY(mnemonic,  "!D", comp, "0001101");
    IF_CMP_CPY(mnemonic,  "!A", comp, "0110001"); IF_CMP_CPY(mnemonic,  "!M", comp, "1110001");
    IF_CMP_CPY(mnemonic,  "-D", comp, "0001111");
    IF_CMP_CPY(mnemonic,  "-A", comp, "0110011"); IF_CMP_CPY(mnemonic,  "-M", comp, "1110011");
    IF_CMP_CPY(mnemonic, "D+1", comp, "0011111");
    IF_CMP_CPY(mnemonic, "A+1", comp, "0110111"); IF_CMP_CPY(mnemonic, "M+1", comp, "1110111");
    IF_CMP_CPY(mnemonic, "D-1", comp, "0001110");
    IF_CMP_CPY(mnemonic, "A-1", comp, "0110010"); IF_CMP_CPY(mnemonic, "M-1", comp, "1110010");
    IF_CMP_CPY(mnemonic, "D+A", comp, "0000010"); IF_CMP_CPY(mnemonic, "D+M", comp, "1000010");
    IF_CMP_CPY(mnemonic, "D-A", comp, "0010011"); IF_CMP_CPY(mnemonic, "D-M", comp, "1010011");
    IF_CMP_CPY(mnemonic, "A-D", comp, "0000111"); IF_CMP_CPY(mnemonic, "M-D", comp, "1000111");
    IF_CMP_CPY(mnemonic, "D&A", comp, "0000000"); IF_CMP_CPY(mnemonic, "D&M", comp, "1000000");
    IF_CMP_CPY(mnemonic, "D|A", comp, "0010101"); IF_CMP_CPY(mnemonic, "D|M", comp, "1010101");
}

void Code_jump(char *mnemonic, char *jump)
{
    IF_CMP_CPY(mnemonic,    "", jump, "000");
    IF_CMP_CPY(mnemonic, "JGT", jump, "001");
    IF_CMP_CPY(mnemonic, "JEQ", jump, "010");
    IF_CMP_CPY(mnemonic, "JGE", jump, "011");
    IF_CMP_CPY(mnemonic, "JLT", jump, "100");
    IF_CMP_CPY(mnemonic, "JNE", jump, "101");
    IF_CMP_CPY(mnemonic, "JLE", jump, "110");
    IF_CMP_CPY(mnemonic, "JMP", jump, "111");
}

main.c

アセンブラのエントリポイントです。
main.cではコマンド引数の解析、ParserモジュールおよびCodeモジュールを用いたアセンブル処理を行います。main.cの中で使う関数はmain.c内で下記のように定義しました。

06/AssemblerL/main.c:L16-L20

bool getHackFileName(char *asmFileName, char *hackFileName);
void assemble(FILE *fpAsm, FILE *fpHack);
void assembleACommand(Parser parser, FILE *fpHack);
void assembleCCommand(Parser parser, FILE *fpHack);
void getACommandValueString(int valueNumber, char *valueString);

アセンブル処理の実装は下記の通りです。ASMファイルとHACKファイルのファイルポインタを受け取りアセンブル出来次第、HACKファイルにfputsでバイナリコードを追記しています。シンボルを含まない前提のためA命令は数値の前提で処理しています。

06/AssemblerL/main.c:L94-L148

void assemble(FILE *fpAsm, FILE *fpHack)
{
    Parser parser = Parser_init(fpAsm);
    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_A_COMMAND:
            assembleACommand(parser, fpHack);
            break;
        case PARSER_COMMAND_TYPE_C_COMMAND:
            assembleCCommand(parser, fpHack);
            break;
        default:
            break;
        }
    }
}

void assembleACommand(Parser parser, FILE *fpHack)
{
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];
    int valueNumber;
    char value[A_COMMAND_VALUE_LENGTH + 1];

    Parser_symbol(parser, symbol);
    sscanf(symbol, "%d", &valueNumber);
    getACommandValueString(valueNumber, value);

    // 0 value
    fputs("0", fpHack);
    fputs(value, fpHack);
    fputs("\n", fpHack);
}

void assembleCCommand(Parser parser, FILE *fpHack)
{
    char mnemonic[PARSER_MNEMONIC_MAX_LENGTH + 1];
    char dest[PARSER_DEST_LENGTH + 1], comp[PARSER_COMP_LENGTH + 1], jump[PARSER_JUMP_LENGTH + 1];

    Parser_dest(parser, mnemonic);
    Code_dest(mnemonic, dest);

    Parser_comp(parser, mnemonic);
    Code_comp(mnemonic, comp);

    Parser_jump(parser, mnemonic);
    Code_jump(mnemonic, jump);

    // 111 comp dest jump
    fputs("111", fpHack);
    fputs(comp, fpHack);
    fputs(dest, fpHack);
    fputs(jump, fpHack);
    fputs("\n", fpHack);
}

シンボルを含むプログラムのためのアセンブラ

下記のように実装を行いました。コードは06/Assembler/です。

f:id:nihma:20200506175436p:plain

下記で使えます。

test.sh:L86-L126

cp ./nand2tetris/projects/06/add/Add.asm 06/Assembler/

# ...(省略)...

cd 06/Assembler/

clang --std=c11 -Wall -Wextra -o Assembler main.c Parser.c Code.c SymbolTable.c

echo "Add"
./Assembler Add.asm

SymbolTableモジュール

シンボルとアドレスの対応を記録するためのモジュールです。
main.cで利用する関数はSymbolTable.hで下記のように定義しました。symbol_table構造体はtypedefして定義はSymbolTable.c内に隠蔽するようにしオブジェクトとして使うようにしました。後処理が必要となるため書籍と違いSymbolTable_deleteがあります。それぞれの実装はSymbolTable.cで行いました。

06/Assembler/SymbolTable.h:L6-L12

typedef struct symbol_table * SymbolTable;

SymbolTable SymbolTable_init(void);
void SymbolTable_addEntry(SymbolTable thisObject, char *symbol, int address);
bool SymbolTable_contains(SymbolTable thisObject, char *symbol);
int SymbolTable_getAddress(SymbolTable thisObject, char *symbol);
void SymbolTable_delete(SymbolTable thisObject);

今回は単純な単方向連結リストで実装しました。

06/Assembler/SymbolTable.c:L7-L18

typedef struct entry Entry;
struct entry
{
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];
    int address;
    Entry *nextEntry;
};

struct symbol_table
{
    Entry *table;
};

main.c

下記が新規および変更した関数です。A命令のアセンブルを行うassembleACommand関数はSymbolTableへの変数シンボル登録に対応するために引数にSymbolTable symbolTableとint ramAddressを追加してramAddressを返却するよう変更しました。

06/Assembler/main.c:20-L23

int assembleACommand(Parser parser, SymbolTable symbolTable, int ramAddress, FILE *fpHack);
void setDefinedSymbol(SymbolTable symbolTable);
void setLabelSymbol(SymbolTable symbolTable, Parser parser);

まず、定義済みシンボルをSymbolTableへ登録する関数です。

06/Assembler/main.c:175-L201

void setDefinedSymbol(SymbolTable symbolTable)
{
    // LABEL, RAM Address
    SymbolTable_addEntry(symbolTable, "SP",         0);
    SymbolTable_addEntry(symbolTable, "LCL",        1);
    SymbolTable_addEntry(symbolTable, "ARG",        2);
    SymbolTable_addEntry(symbolTable, "THIS",       3);
    SymbolTable_addEntry(symbolTable, "THAT",       4);
    SymbolTable_addEntry(symbolTable, "R0",         0);
    SymbolTable_addEntry(symbolTable, "R1",         1);
    SymbolTable_addEntry(symbolTable, "R2",         2);
    SymbolTable_addEntry(symbolTable, "R3",         3);
    SymbolTable_addEntry(symbolTable, "R4",         4);
    SymbolTable_addEntry(symbolTable, "R5",         5);
    SymbolTable_addEntry(symbolTable, "R6",         6);
    SymbolTable_addEntry(symbolTable, "R7",         7);
    SymbolTable_addEntry(symbolTable, "R8",         8);
    SymbolTable_addEntry(symbolTable, "R9",         9);
    SymbolTable_addEntry(symbolTable, "R10",       10);
    SymbolTable_addEntry(symbolTable, "R11",       11);
    SymbolTable_addEntry(symbolTable, "R12",       12);
    SymbolTable_addEntry(symbolTable, "R13",       13);
    SymbolTable_addEntry(symbolTable, "R14",       14);
    SymbolTable_addEntry(symbolTable, "R15",       15);
    SymbolTable_addEntry(symbolTable, "SCREEN", 16384);
    SymbolTable_addEntry(symbolTable, "KBD",    24576);
}

そして、ラベルシンボルをSymbolTableへ登録する関数です。書籍に1回目のパスと記されている処理です。

06/Assembler/main.c:203-L223

void setLabelSymbol(SymbolTable symbolTable, Parser parser)
{
    int romAddress = 0;
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];

    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_A_COMMAND:
        case PARSER_COMMAND_TYPE_C_COMMAND:
            romAddress++;
            break;
        case PARSER_COMMAND_TYPE_L_COMMAND:
            Parser_symbol(parser, symbol);
            SymbolTable_addEntry(symbolTable, symbol, romAddress);
            break;
        default:
            break;
        }
    }
}

最後がアセンブル処理です。シンボルに関する処理が追加されています。書籍に2回目のパスと記されている処理です。assembleCCommand関数は変更ありませんので省略しました。

06/Assembler/main.c:98-L151

void assemble(FILE *fpAsm, FILE *fpHack)
{
    Parser parser = Parser_init(fpAsm);
    int ramAddress = VARIABLE_SYMBOL_RAM_ADDRESS_START;
    SymbolTable symbolTable = SymbolTable_init();

    setDefinedSymbol(symbolTable);
    setLabelSymbol(symbolTable, parser);

    parser = Parser_init(fpAsm);
    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_A_COMMAND:
            ramAddress = assembleACommand(parser, symbolTable, ramAddress, fpHack);
            break;
        case PARSER_COMMAND_TYPE_C_COMMAND:
            assembleCCommand(parser, fpHack);
            break;
        default:
            break;
        }
    }

    SymbolTable_delete(symbolTable);
}

int assembleACommand(Parser parser, SymbolTable symbolTable, int ramAddress, FILE *fpHack)
{
    char symbol[PARSER_SYMBOL_MAX_LENGTH + 1];
    int valueNumber;
    char value[A_COMMAND_VALUE_LENGTH + 1];

    Parser_symbol(parser, symbol);
    if (! isdigit(symbol[0])) {  // symbol is /^[^\d].*/
        if (SymbolTable_contains(symbolTable, symbol)) {
            valueNumber = SymbolTable_getAddress(symbolTable, symbol);
        } else {
            SymbolTable_addEntry(symbolTable, symbol, ramAddress);
            valueNumber = ramAddress;
            ramAddress++;
        }
    } else {
        sscanf(symbol, "%d", &valueNumber);
    }
    getACommandValueString(valueNumber, value);

    // 0 value
    fputs("0", fpHack);
    fputs(value, fpHack);
    fputs("\n", fpHack);

    return ramAddress;
}

まとめ

前回から間が空いてしまいましたがようやくアセンブラの実装ができました。7章以降もできれば進めたいです。C言語が大変だった。。

*1:久しぶりすぎてだいぶ忘れている。。環境はApple LLVM version 10.0.0 (clang-1000.11.45.5)です。

*2:モジュールを表現するのに抽象データ型にしてみたりとかとか。モジュール化してる割にはあまりカプセル化できてない設計だったりで気になりましたけど

*3:mallocなんかの戻り値もチェックしてなかったり