MENU
Macintoshから始まった旅の続き。物語でめぐるUNIX・Linuxの歩き方。 | UNIX Cafe

C言語で作るLC-3仮想マシン 第5回: 小さいLC-3アセンブラを作る | UNIX Cafe

C言語で作る小さなシステム

＊ 当サイトでは、コンテンツの一部に広告を掲載しています。

System Note $ cat /proc/ai-disclosure

本記事の構成および論理分析にはAI（人工知能）を使用しています。情報の正確性は、システム管理者（UNIXユーザー）による手動検証済みです。

C言語で作るLC-3仮想マシン 第5回: 小さいLC-3アセンブラを作る | UNIX Cafe
目次

小さいLC-3アセンブラを作る

前回は、LC-3アセンブリでHello Worldを書き、既存のlc3asを使って.objファイルを作りました。さらに、printfで同じbyte列を直接書き出し、.objの中身も手作業に近い形で確認しました。

第5回では、前回lc3asが担当していた変換処理を、自分のCプログラムとして実装します。人間が読めるhello.asmを読み、ラベルを解決し、LC-3の16bit word列に変換し、big-endianの.objとして書き出す流れを作ります。

ただし、最初から汎用LC-3アセンブラを作るわけではありません。今回はHello Worldが通る範囲に絞り、.ORIG、.END、.STRINGZ、LEA、PUTS、HALTに対応する小さい2パスアセンブラを作ります。

第5回で使う入力ファイルと、完成する小さいLC-3アセンブラは、GitHubのlc3as-lab/に置いています。

Static Badge Static Badge Static Badge Static Badge

今回作るもの

前回は、Hello Worldの.objを2つの方法で作りました。

1つ目は、printfでbyte列を直接ファイルに書き出す方法。2つ目は、既存のlc3asを使ってLC-3アセンブリを.objに変換する方法です。

今回は、その変換処理を自分で作ります。ただし、最初からLC-3の全命令には対応しません。Hello Worldが通るだけの小さいアセンブラを作ります。

言い換えると、前回printfで手書きしたbyte列を、hello.asmから自動生成するプログラムを作ります。

.ORIG
.END
.STRINGZ
LEA
PUTS
HALT

ゴールは、既存のlc3asと同じ.objを出すことです。

lc3asで作った hello.obj
自作アセンブラで作った hello-minias.obj

この2つがbyte-for-byteで一致すれば成功です。

今回の作業の進め方

今回作るアセンブラ全体は、次の流れで動きます。

hello.asm
  ↓
Pass 1
  ラベルの番地を集める
  ↓
Pass 2
  命令と疑似命令を16bit wordにする
  ↓
big-endianで .obj に書き出す
  ↓
lc3asの出力と比較する
  ↓
自作VMで実行する

この記事では、この流れを小さい部品に分けて実装していきます。

なお、実際にminias.cを書くときは、Cコンパイラが上から読めるように、先に使う小さな補助関数から順番に定義していきます。そのため、記事本文の実装順は、最後に載せる完成コードの並びと同じにしています。

アセンブラは何をするプログラムか

アセンブラの仕事は、人間が読みやすい命令を、CPUが読めるbit列に変換することです。

        LEA R0, HELLO
        PUTS
        HALT

これはLC-3の機械語では次のword列になります。

e002 f022 f025

さらに.objファイルでは、先頭にoriginを置きます。

3000 e002 f022 f025 ...

なぜ2パスにするのか

今回のHello Worldには、HELLOというラベルがあります。

        LEA R0, HELLO
        PUTS
        HALT

HELLO   .STRINGZ "Hello, World!\n"

LEA R0, HELLOを機械語にするには、HELLOが何番地に置かれるかを知る必要があります。しかし、上から1回読むだけだと、LEAの行を読んだ時点ではHELLOの番地がまだ分かりません。

そこで、アセンブラでは2回に分けて読みます。

Pass 1: ラベルの番地を集める
Pass 2: ラベルを使って命令を機械語にする

つまり、1回目でHELLOがx3003にあることを先に調べておき、2回目でその番地を使ってLEA R0, HELLOを正しい機械語に変換します。

minias.cを作る

ここから、自作アセンブラ本体のminias.cを作ります。

ここから先のコード断片は、最後に載せる完成コードと同じ順番で並べています。上から順番にminias.cへ追加していくと、1つのCファイルとしてつながる構成です。

今回作るのは、LC-3の全命令に対応した本格的なアセンブラではありません。Hello Worldに必要な範囲だけを実装します。

.ORIG
.END
.STRINGZ
LEA
PUTS
HALT

ファイル構成は次のようにします。

lc3as-lab/
├── minias.c
├── src/
│   └── hello.asm
├── build/
└── Makefile

最初に配列と構造体を用意する

この小さいアセンブラでは、入力行、ラベル表、出力word列をそれぞれ配列で持ちます。

// 空白処理、固定幅整数、ファイル入出力、文字列処理を使う
#include <ctype.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 今回は小さいアセンブラなので、固定長配列で持つ
#define MAX_LINES 1024
#define MAX_LABELS 256
#define MAX_WORDS 65536
#define MAX_TEXT 256

// コメントと空行を取り除いた入力行
typedef struct {
    char text[MAX_TEXT];
    int line_no;
} Line;

// ラベル名と、そのラベルが指すLC-3アドレス
typedef struct {
    char name[64];
    uint16_t address;
} Label;

// 入力行、ラベル表、出力word列をグローバルに持つ
static Line lines[MAX_LINES];
static int line_count;

static Label labels[MAX_LABELS];
static int label_count;

static uint16_t words[MAX_WORDS];
static int word_count;
static uint16_t origin;
static int have_origin;

lines[]には読み込んだアセンブリ行を入れます。labels[]にはHELLO = x3003のようなラベル情報を入れます。words[]には最終的に.objへ書き出す16bit wordを入れます。

エラー表示と文字列処理を用意する

まず、エラーを行番号付きで止める関数を作ります。

static void die_line(int line_no, const char *message)
{
    // どの行で失敗したかを表示して終了する
    fprintf(stderr, "line %d: %s\n", line_no, message);
    exit(1);
}

次に、行頭と行末の空白を取り除くtrim()です。

static char *trim(char *s)
{
    // 行頭の空白を読み飛ばす
    while (isspace((unsigned char)*s)) {
        ++s;
    }

    // 行末の空白を'\0'で切り落とす
    char *end = s + strlen(s);
    while (end > s && isspace((unsigned char)end[-1])) {
        --end;
    }
    *end = '\0';
    return s;
}

LC-3アセンブリでは、セミコロン以降をコメントとして扱います。ただし、文字列の中のセミコロンは消してはいけません。

static void strip_comment(char *s)
{
    int in_string = 0;
    for (; *s; ++s) {
        if (*s == '"') {
            in_string = !in_string;
        } else if (*s == ';' && !in_string) {
            // 文字列の外にある;以降はコメントとして捨てる
            *s = '\0';
            return;
        }
    }
}

命令名は大文字小文字を区別しないことにします。そのため、比較前に大文字へそろえます。

static void uppercase(char *s)
{
    // 命令名の比較を簡単にするため、大文字にそろえる
    for (; *s; ++s) {
        *s = (char)toupper((unsigned char)*s);
    }
}

先頭のトークンが命令や疑似命令でなければ、ラベルとして扱います。

static int starts_with_directive_or_opcode(const char *s)
{
    char token[64];
    if (sscanf(s, "%63s", token) != 1) {
        return 0;
    }
    uppercase(token);

    // 先頭がこれらならラベルではなく命令または疑似命令
    return token[0] == '.' ||
           strcmp(token, "LEA") == 0 ||
           strcmp(token, "PUTS") == 0 ||
           strcmp(token, "HALT") == 0;
}

数値とレジスタを読む

.ORIG x3000のような16進数と、#10のような10進数を読めるようにします。

static uint16_t parse_number(const char *s, int line_no)
{
    int base = 10;
    const char *p = s;

    // x3000 は16進数、#10 は10進数として読む
    if (*p == 'x' || *p == 'X') {
        base = 16;
        ++p;
    } else if (*p == '#') {
        base = 10;
        ++p;
    }

    char *end = NULL;
    long value = strtol(p, &end, base);
    // 変換できない文字が残った場合や、16bitを超えた場合はエラー
    if (*p == '\0' || *end != '\0' || value < 0 || value > 0xFFFF) {
        die_line(line_no, "invalid number");
    }
    return (uint16_t)value;
}

LEA R0, HELLOでは、R0を0として取り出す必要があります。

static int parse_register(const char *s, int line_no)
{
    // R0からR7だけを受け付ける
    if ((s[0] != 'R' && s[0] != 'r') || s[1] < '0' || s[1] > '7' || s[2] != '\0') {
        die_line(line_no, "invalid register");
    }
    return s[1] - '0';
}

ラベル表を作る

ラベルは名前と番地の組です。同じラベルが2回出てきたらエラーにします。

static void add_label(const char *name, uint16_t address, int line_no)
{
    if (label_count >= MAX_LABELS) {
        die_line(line_no, "too many labels");
    }

    // 同じラベルを2回定義するのはエラー
    for (int i = 0; i < label_count; ++i) {
        if (strcmp(labels[i].name, name) == 0) {
            die_line(line_no, "duplicate label");
        }
    }

    // ラベル名と現在のlocation counterを保存する
    snprintf(labels[label_count].name, sizeof(labels[label_count].name), "%s", name);
    labels[label_count].address = address;
    ++label_count;
}

Pass 2では、ラベル名から番地を引けるようにします。

static uint16_t find_label(const char *name, int line_no)
{
    // Pass 1で作ったラベル表から番地を探す
    for (int i = 0; i < label_count; ++i) {
        if (strcmp(labels[i].name, name) == 0) {
            return labels[i].address;
        }
    }
    die_line(line_no, "unknown label");
    return 0;
}

トークンを1つずつ読む

命令行は、空白とカンマで区切って読みます。これでLEA R0, HELLOをLEA、R0、HELLOに分けられます。

static char *next_token(char **cursor)
{
    // 現在位置から次のトークンを取り出す
    char *s = trim(*cursor);
    if (*s == '\0') {
        *cursor = s;
        return NULL;
    }

    char *start = s;
    // 空白またはカンマまでを1トークンとする
    while (*s && !isspace((unsigned char)*s) && *s != ',') {
        ++s;
    }

    if (*s) {
        *s++ = '\0';
    }
    while (isspace((unsigned char)*s) || *s == ',') {
        ++s;
    }
    *cursor = s;
    return start;
}

.STRINGZは文字数分のwordに加えて、終端の0も1word使います。そのため、文字列のword数を数える関数を先に用意しています。

static int stringz_word_count(const char *s, int line_no)
{
    // .STRINGZのダブルクォート範囲を探す
    const char *start = strchr(s, '"');
    const char *end = strrchr(s, '"');
    if (start == NULL || end == NULL || start == end) {
        die_line(line_no, "invalid .STRINGZ");
    }

    // 文字数分 + 終端の0の分を数える
    int count = 1;
    for (const char *p = start + 1; p < end; ++p) {
        if (*p == '\\' && p + 1 < end) {
            ++p;
        }
        ++count;
    }
    return count;
}

入力ファイルを読む

load_lines()では、入力の.asmを読み、コメントと空行を取り除いてlines[]へ保存します。

static void load_lines(const char *path)
{
    // 入力の.asmファイルを開く
    FILE *file = fopen(path, "r");
    if (file == NULL) {
        perror(path);
        exit(1);
    }

    char buffer[MAX_TEXT];
    while (fgets(buffer, sizeof(buffer), file) != NULL) {
        if (line_count >= MAX_LINES) {
            fprintf(stderr, "too many lines\n");
            exit(1);
        }
        // コメントと空白だけの行は、ここで取り除く
        strip_comment(buffer);
        char *clean = trim(buffer);
        if (*clean == '\0') {
            continue;
        }
        // 後続のPassで使えるよう、きれいにした行を保存する
        snprintf(lines[line_count].text, sizeof(lines[line_count].text), "%s", clean);
        lines[line_count].line_no = line_count + 1;
        ++line_count;
    }

    fclose(file);
}

Pass 1を実装する

Pass 1では、まだ機械語は出しません。location counterだけを進めながら、ラベルの番地を集めます。

今回のプログラムの場合、メモリ配置は次のようになります。

x3000  LEA R0, HELLO
x3001  PUTS
x3002  HALT
x3003  'H'
x3004  'e'
...

つまり、Pass 1で作りたいラベル表はHELLO = x3003です。

static void first_pass(void)
{
    // locは、いま見ている行が配置されるLC-3アドレス
    uint16_t loc = 0;

    for (int i = 0; i < line_count; ++i) {
        char line[MAX_TEXT];
        snprintf(line, sizeof(line), "%s", lines[i].text);
        int line_no = lines[i].line_no;

        char *cursor = trim(line);
        if (!starts_with_directive_or_opcode(cursor)) {
            // 行頭が命令でなければラベルとして登録する
            char *label = next_token(&cursor);
            add_label(label, loc, line_no);
        }

        char rest[MAX_TEXT];
        snprintf(rest, sizeof(rest), "%s", trim(cursor));
        cursor = rest;
        char *op = next_token(&cursor);
        if (op == NULL) {
            continue;
        }
        uppercase(op);

        if (strcmp(op, ".ORIG") == 0) {
            // .ORIGでプログラムの開始番地を決める
            char *arg = next_token(&cursor);
            if (arg == NULL) {
                die_line(line_no, ".ORIG needs an address");
            }
            origin = parse_number(arg, line_no);
            loc = origin;
            have_origin = 1;
        } else if (strcmp(op, ".END") == 0) {
            return;
        } else if (!have_origin) {
            die_line(line_no, "missing .ORIG");
        } else if (strcmp(op, ".STRINGZ") == 0) {
            // 文字列は文字数分と終端0の分だけlocを進める
            loc = (uint16_t)(loc + stringz_word_count(cursor, line_no));
        } else if (strcmp(op, "LEA") == 0 ||
                   strcmp(op, "PUTS") == 0 ||
                   strcmp(op, "HALT") == 0) {
            // 今回対応する命令はどれも1word
            ++loc;
        } else {
            die_line(line_no, "unsupported operation");
        }
    }
}

これで、HELLO .STRINGZ ...のような行を見つけたときに、HELLOの番地をラベル表へ登録できます。

Pass 2を実装する

Pass 2では、実際に16bit wordをwords[]へ積んでいきます。

PUTSとHALTは固定のTRAP命令にできます。PUTSはTRAP x22なので0xF022、HALTはTRAP x25なので0xF025です。

static void emit(uint16_t word, int line_no)
{
    // 出力する16bit wordをwords[]へ積む
    if (word_count >= MAX_WORDS) {
        die_line(line_no, "too much output");
    }
    words[word_count++] = word;
}

.STRINGZは、文字を1つずつwordとして出力します。今回は\n、\t、\\、\"だけをエスケープとして扱います。

static void emit_stringz(const char *s, int line_no)
{
    // .STRINGZの文字列部分だけを取り出す
    const char *start = strchr(s, '"');
    const char *end = strrchr(s, '"');
    if (start == NULL || end == NULL || start == end) {
        die_line(line_no, "invalid .STRINGZ");
    }

    for (const char *p = start + 1; p < end; ++p) {
        if (*p == '\\' && p + 1 < end) {
            // \nなどのエスケープを実際の文字コードに変換する
            ++p;
            switch (*p) {
                case 'n': emit('\n', line_no); break;
                case 't': emit('\t', line_no); break;
                case '\\': emit('\\', line_no); break;
                case '"': emit('"', line_no); break;
                default: die_line(line_no, "unsupported escape sequence");
            }
        } else {
            // 通常の文字は、そのまま1文字1wordで出力する
            emit((uint16_t)(unsigned char)*p, line_no);
        }
    }
    // PUTSが止まれるよう、最後に終端0を置く
    emit(0, line_no);
}

命令のエンコード本体はsecond_pass()に書きます。

LEAだけはラベルを使います。LEA命令がx3000にあり、HELLOがx3003にある場合、fetch後のPCはx3001なので、offsetはx3003 - x3001 = 2になります。

static void second_pass(void)
{
    // Pass 2でも現在番地を追いながら命令を出力する
    uint16_t loc = 0;

    for (int i = 0; i < line_count; ++i) {
        char line[MAX_TEXT];
        snprintf(line, sizeof(line), "%s", lines[i].text);
        int line_no = lines[i].line_no;

        char *cursor = trim(line);
        if (!starts_with_directive_or_opcode(cursor)) {
            // ラベル部分はPass 1で処理済みなので読み飛ばす
            (void)next_token(&cursor);
        }

        char *op = next_token(&cursor);
        if (op == NULL) {
            continue;
        }
        uppercase(op);

        if (strcmp(op, ".ORIG") == 0) {
            // .objの先頭wordとしてoriginを書き出す
            char *arg = next_token(&cursor);
            loc = parse_number(arg, line_no);
            emit(loc, line_no);
        } else if (strcmp(op, ".END") == 0) {
            return;
        } else if (strcmp(op, ".STRINGZ") == 0) {
            // 文字列をword列に変換する
            emit_stringz(cursor, line_no);
            loc = (uint16_t)(origin + word_count - 1);
        } else if (strcmp(op, "LEA") == 0) {
            // LEA DR, LABEL をエンコードする
            char *dr_text = next_token(&cursor);
            char *label = next_token(&cursor);
            if (dr_text == NULL || label == NULL) {
                die_line(line_no, "LEA needs register and label");
            }

            int dr = parse_register(dr_text, line_no);
            uint16_t target = find_label(label, line_no);
            // LC-3のPC相対offsetは、次の命令番地からの差分
            int offset = (int)target - ((int)loc + 1);
            if (offset < -256 || offset > 255) {
                die_line(line_no, "LEA target is out of range");
            }
            emit((uint16_t)(0xE000 | (dr << 9) | (offset & 0x1FF)), line_no);
            ++loc;
        } else if (strcmp(op, "PUTS") == 0) {
            // PUTSはTRAP x22
            emit(0xF022, line_no);
            ++loc;
        } else if (strcmp(op, "HALT") == 0) {
            // HALTはTRAP x25
            emit(0xF025, line_no);
            ++loc;
        } else {
            die_line(line_no, "unsupported operation");
        }
    }
}

LEAでは、Pass 1で作ったラベル表から目標番地を取り出し、現在の命令の次の番地からの差分をPCoffset9に入れます。

.objファイルを書き出す

最後に、words[]をbig-endianでファイルへ書き出します。

static void write_obj(const char *path)
{
    // .objはバイナリファイルとして書く
    FILE *file = fopen(path, "wb");
    if (file == NULL) {
        perror(path);
        exit(1);
    }

    for (int i = 0; i < word_count; ++i) {
        // LC-3の.objはbig-endianなので、上位byteから書く
        unsigned char bytes[2];
        bytes[0] = (unsigned char)(words[i] >> 8);
        bytes[1] = (unsigned char)(words[i] & 0xFF);
        fwrite(bytes, 1, 2, file);
    }

    fclose(file);
}

mainでつなぐ

最後に、ここまで作った関数をmain()から順番に呼びます。

int main(int argc, char **argv)
{
    // 入力.asmと出力.objの2つを受け取る
    if (argc != 3) {
        fprintf(stderr, "usage: %s input.asm output.obj\n", argv[0]);
        return 2;
    }

    // 入力を読み、Pass 1、Pass 2、書き出しの順に処理する
    load_lines(argv[1]);
    first_pass();
    if (!have_origin) {
        fprintf(stderr, "missing .ORIG\n");
        return 1;
    }
    second_pass();
    write_obj(argv[2]);
    return 0;
}

これで、hello.asmからhello-minias.objを生成するプログラムになりました。完成版のminias.c全体は、記事の最後にまとめて載せます。

minias.cをコンパイルして実行する

ここまででminias.cが完成したので、まずはCコンパイラで実行ファイルを作ります。minias.cとMakefileがあるlc3as-lab/へ移動してから実行します。

cd lc3as-lab
mkdir -p build
cc -Wall -Wextra -pedantic -std=c99 minias.c -o build/minias

コンパイルできたら、自作アセンブラを直接実行してsrc/hello.asmからbuild/hello-minias.objを作ります。

./build/minias src/hello.asm build/hello-minias.obj

何も表示されずに終了すれば成功です。作られた.objをxxdで見ると、先頭に3000、続いてe002 f022 f025が並んでいることを確認できます。

xxd build/hello-minias.obj
00000000: 3000 e002 f022 f025 0048 0065 006c 006c  0....".%.H.e.l.l
00000010: 006f 002c 0020 0057 006f 0072 006c 0064  .o.,. .W.o.r.l.d
00000020: 0021 000a 0000                           .!....

手で打つ場合は上の3つのコマンドで十分です。Makefileを使う場合は、同じ作業を次のターゲットで実行できます。

比較して実行する

lc3as-lab/Makefileには、自作アセンブラ用のターゲットを用意しています。

make compare
make run-mini

make compareでは、既存のlc3asが作った.objと、自作アセンブラが作った.objを比較します。

00000000: 3000 e002 f022 f025 0048 0065 006c 006c  0....".%.H.e.l.l
00000010: 006f 002c 0020 0057 006f 0072 006c 0064  .o.,. .W.o.r.l.d
00000020: 0021 000a 0000                           .!....

make run-miniで、自作アセンブラが作った.objを自作VMに渡します。

Hello, World!
HALT

今回の完成コード

lc3as-lab/minias.cの全体です。

#include <ctype.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LINES 1024
#define MAX_LABELS 256
#define MAX_WORDS 65536
#define MAX_TEXT 256

typedef struct {
    char text[MAX_TEXT];
    int line_no;
} Line;

typedef struct {
    char name[64];
    uint16_t address;
} Label;

static Line lines[MAX_LINES];
static int line_count;

static Label labels[MAX_LABELS];
static int label_count;

static uint16_t words[MAX_WORDS];
static int word_count;
static uint16_t origin;
static int have_origin;

static void die_line(int line_no, const char *message)
{
    fprintf(stderr, "line %d: %s\n", line_no, message);
    exit(1);
}

static char *trim(char *s)
{
    while (isspace((unsigned char)*s)) {
        ++s;
    }

    char *end = s + strlen(s);
    while (end > s && isspace((unsigned char)end[-1])) {
        --end;
    }
    *end = '\0';
    return s;
}

static void strip_comment(char *s)
{
    int in_string = 0;
    for (; *s; ++s) {
        if (*s == '"') {
            in_string = !in_string;
        } else if (*s == ';' && !in_string) {
            *s = '\0';
            return;
        }
    }
}

static void uppercase(char *s)
{
    for (; *s; ++s) {
        *s = (char)toupper((unsigned char)*s);
    }
}

static int starts_with_directive_or_opcode(const char *s)
{
    char token[64];
    if (sscanf(s, "%63s", token) != 1) {
        return 0;
    }
    uppercase(token);

    return token[0] == '.' ||
           strcmp(token, "LEA") == 0 ||
           strcmp(token, "PUTS") == 0 ||
           strcmp(token, "HALT") == 0;
}

static uint16_t parse_number(const char *s, int line_no)
{
    int base = 10;
    const char *p = s;

    if (*p == 'x' || *p == 'X') {
        base = 16;
        ++p;
    } else if (*p == '#') {
        base = 10;
        ++p;
    }

    char *end = NULL;
    long value = strtol(p, &end, base);
    if (*p == '\0' || *end != '\0' || value < 0 || value > 0xFFFF) {
        die_line(line_no, "invalid number");
    }
    return (uint16_t)value;
}

static int parse_register(const char *s, int line_no)
{
    if ((s[0] != 'R' && s[0] != 'r') || s[1] < '0' || s[1] > '7' || s[2] != '\0') {
        die_line(line_no, "invalid register");
    }
    return s[1] - '0';
}

static void add_label(const char *name, uint16_t address, int line_no)
{
    if (label_count >= MAX_LABELS) {
        die_line(line_no, "too many labels");
    }

    for (int i = 0; i < label_count; ++i) {
        if (strcmp(labels[i].name, name) == 0) {
            die_line(line_no, "duplicate label");
        }
    }

    snprintf(labels[label_count].name, sizeof(labels[label_count].name), "%s", name);
    labels[label_count].address = address;
    ++label_count;
}

static uint16_t find_label(const char *name, int line_no)
{
    for (int i = 0; i < label_count; ++i) {
        if (strcmp(labels[i].name, name) == 0) {
            return labels[i].address;
        }
    }
    die_line(line_no, "unknown label");
    return 0;
}

static char *next_token(char **cursor)
{
    char *s = trim(*cursor);
    if (*s == '\0') {
        *cursor = s;
        return NULL;
    }

    char *start = s;
    while (*s && !isspace((unsigned char)*s) && *s != ',') {
        ++s;
    }

    if (*s) {
        *s++ = '\0';
    }
    while (isspace((unsigned char)*s) || *s == ',') {
        ++s;
    }
    *cursor = s;
    return start;
}

static int stringz_word_count(const char *s, int line_no)
{
    const char *start = strchr(s, '"');
    const char *end = strrchr(s, '"');
    if (start == NULL || end == NULL || start == end) {
        die_line(line_no, "invalid .STRINGZ");
    }

    int count = 1;
    for (const char *p = start + 1; p < end; ++p) {
        if (*p == '\\' && p + 1 < end) {
            ++p;
        }
        ++count;
    }
    return count;
}

static void load_lines(const char *path)
{
    FILE *file = fopen(path, "r");
    if (file == NULL) {
        perror(path);
        exit(1);
    }

    char buffer[MAX_TEXT];
    while (fgets(buffer, sizeof(buffer), file) != NULL) {
        if (line_count >= MAX_LINES) {
            fprintf(stderr, "too many lines\n");
            exit(1);
        }
        strip_comment(buffer);
        char *clean = trim(buffer);
        if (*clean == '\0') {
            continue;
        }
        snprintf(lines[line_count].text, sizeof(lines[line_count].text), "%s", clean);
        lines[line_count].line_no = line_count + 1;
        ++line_count;
    }

    fclose(file);
}

static void first_pass(void)
{
    uint16_t loc = 0;

    for (int i = 0; i < line_count; ++i) {
        char line[MAX_TEXT];
        snprintf(line, sizeof(line), "%s", lines[i].text);
        int line_no = lines[i].line_no;

        char *cursor = trim(line);
        if (!starts_with_directive_or_opcode(cursor)) {
            char *label = next_token(&cursor);
            add_label(label, loc, line_no);
        }

        char rest[MAX_TEXT];
        snprintf(rest, sizeof(rest), "%s", trim(cursor));
        cursor = rest;
        char *op = next_token(&cursor);
        if (op == NULL) {
            continue;
        }
        uppercase(op);

        if (strcmp(op, ".ORIG") == 0) {
            char *arg = next_token(&cursor);
            if (arg == NULL) {
                die_line(line_no, ".ORIG needs an address");
            }
            origin = parse_number(arg, line_no);
            loc = origin;
            have_origin = 1;
        } else if (strcmp(op, ".END") == 0) {
            return;
        } else if (!have_origin) {
            die_line(line_no, "missing .ORIG");
        } else if (strcmp(op, ".STRINGZ") == 0) {
            loc = (uint16_t)(loc + stringz_word_count(cursor, line_no));
        } else if (strcmp(op, "LEA") == 0 ||
                   strcmp(op, "PUTS") == 0 ||
                   strcmp(op, "HALT") == 0) {
            ++loc;
        } else {
            die_line(line_no, "unsupported operation");
        }
    }
}

static void emit(uint16_t word, int line_no)
{
    if (word_count >= MAX_WORDS) {
        die_line(line_no, "too much output");
    }
    words[word_count++] = word;
}

static void emit_stringz(const char *s, int line_no)
{
    const char *start = strchr(s, '"');
    const char *end = strrchr(s, '"');
    if (start == NULL || end == NULL || start == end) {
        die_line(line_no, "invalid .STRINGZ");
    }

    for (const char *p = start + 1; p < end; ++p) {
        if (*p == '\\' && p + 1 < end) {
            ++p;
            switch (*p) {
                case 'n': emit('\n', line_no); break;
                case 't': emit('\t', line_no); break;
                case '\\': emit('\\', line_no); break;
                case '"': emit('"', line_no); break;
                default: die_line(line_no, "unsupported escape sequence");
            }
        } else {
            emit((uint16_t)(unsigned char)*p, line_no);
        }
    }
    emit(0, line_no);
}

static void second_pass(void)
{
    uint16_t loc = 0;

    for (int i = 0; i < line_count; ++i) {
        char line[MAX_TEXT];
        snprintf(line, sizeof(line), "%s", lines[i].text);
        int line_no = lines[i].line_no;

        char *cursor = trim(line);
        if (!starts_with_directive_or_opcode(cursor)) {
            (void)next_token(&cursor);
        }

        char *op = next_token(&cursor);
        if (op == NULL) {
            continue;
        }
        uppercase(op);

        if (strcmp(op, ".ORIG") == 0) {
            char *arg = next_token(&cursor);
            loc = parse_number(arg, line_no);
            emit(loc, line_no);
        } else if (strcmp(op, ".END") == 0) {
            return;
        } else if (strcmp(op, ".STRINGZ") == 0) {
            emit_stringz(cursor, line_no);
            loc = (uint16_t)(origin + word_count - 1);
        } else if (strcmp(op, "LEA") == 0) {
            char *dr_text = next_token(&cursor);
            char *label = next_token(&cursor);
            if (dr_text == NULL || label == NULL) {
                die_line(line_no, "LEA needs register and label");
            }

            int dr = parse_register(dr_text, line_no);
            uint16_t target = find_label(label, line_no);
            int offset = (int)target - ((int)loc + 1);
            if (offset < -256 || offset > 255) {
                die_line(line_no, "LEA target is out of range");
            }
            emit((uint16_t)(0xE000 | (dr << 9) | (offset & 0x1FF)), line_no);
            ++loc;
        } else if (strcmp(op, "PUTS") == 0) {
            emit(0xF022, line_no);
            ++loc;
        } else if (strcmp(op, "HALT") == 0) {
            emit(0xF025, line_no);
            ++loc;
        } else {
            die_line(line_no, "unsupported operation");
        }
    }
}

static void write_obj(const char *path)
{
    FILE *file = fopen(path, "wb");
    if (file == NULL) {
        perror(path);
        exit(1);
    }

    for (int i = 0; i < word_count; ++i) {
        unsigned char bytes[2];
        bytes[0] = (unsigned char)(words[i] >> 8);
        bytes[1] = (unsigned char)(words[i] & 0xFF);
        fwrite(bytes, 1, 2, file);
    }

    fclose(file);
}

int main(int argc, char **argv)
{
    if (argc != 3) {
        fprintf(stderr, "usage: %s input.asm output.obj\n", argv[0]);
        return 2;
    }

    load_lines(argv[1]);
    first_pass();
    if (!have_origin) {
        fprintf(stderr, "missing .ORIG\n");
        return 1;
    }
    second_pass();
    write_obj(argv[2]);
    return 0;
}

今回できたこと

今回は、Hello World専用の小さいLC-3アセンブラを作りました。

  • .ORIGでoriginを読む
  • .ENDで読み取りを終える
  • .STRINGZを16bit word列にする
  • PUTSをf022にする
  • HALTをf025にする
  • LEA R0, HELLOをe002にする
  • .objをbig-endianで書き出す
  • lc3asの出力と完全一致することを確認する
  • 自作VMで実行する

アセンブラというと大きなプログラムに見えますが、最小構成なのでやっていることは限られています。

ラベルの番地を調べる
命令を16bit wordにする
wordをbig-endianで書き出す

ここから先は、ADD, AND, BR, LD, STなどを1つずつ足していけば、より普通のLC-3プログラムをアセンブルできるようになります。

次回はVMの動きをトレースする

今回は、Hello World専用の小さいLC-3アセンブラを作り、hello.asm を .obj に変換する流れを確認しました。

次回は、その .obj をVMがどの番地から読み、どの命令として実行しているのかを、--trace オプションで見えるようにします。

UNIX Cafe フロア案内（ハブページ）

ホームに戻る ｜ 全館案内（サイトマップ）

C言語で作る小さなシステム
C言語 LC-3 Mac UNIX アセンブラ コンパイラ入門 自作VM
よかったらシェアしてね！
  • URLをコピーしました！
  • URLをコピーしました！

この記事を書いた人

のいのアバター のい UNIX Cafe マスター

Macintosh Color Classicから始まった旅は、長いWindows時代を経て、Windows10のサポート終了をきっかけにUNIXの世界へ戻ってきました。UNIX Cafeでは、UNIX・Linux・そしてMacな世界を、むずかしい言葉を使わず、物語のように書いています。プログラミングは、アイデアをコンピューターに伝えるための言葉です。簡単な単語と文法を覚えれば、誰でもコマンドを使えます。ぜひ一度、やさしいプログラミングの世界をのぞいてみてください。

関連記事

目次