400 行 C 代碼實現一個虛擬機

  1. 引言

本文將教你編寫一個自己的虛擬機（VM），這個虛擬機能夠運行彙編語言編寫的程序， 例如我朋友編寫的 2048 或者我自己的 Roguelike。如果你會編程，但希望 更深入地瞭解計算機的內部原理以及編程語言是如何工作的，那本文很適合你。從零開始 寫一個虛擬機聽起來可能讓人有點望而生畏，但讀完本文之後你會驚訝於這件事原來如此簡 單，並從中深受啓發。

本文所說的虛擬機最終由 400 行左右 C 代碼組成。理解這些代碼只需要基本的 C/C++ 知識和二進制運算。這個虛擬機可以在 Unix 系統（包括 macOS）上執行。代碼中包含少 量平臺相關的配置終端（terminal）和顯示（display）的代碼，但這些並不是本項目的核 心。（歡迎大家添加對 Windows 的支持。）

注意：這個虛擬機是 Literate Programming 的產物。本文會解釋每段代碼的原理，最終的實現就是將這些代碼片段連起來。

什麼是虛擬機？

虛擬機就像計算機（computer），它模擬包括 CPU 在內的幾個硬件組件，能夠執行 算術運算、讀寫內存、與 I/O 設備交互。最重要的是，它能理解機器語言（machine language），因此可以用相應的語言來對它進行編程。

一個虛擬機需要模擬哪些硬件要看它的使用場景。有些虛擬機是設計用來模擬特定類型的計算設備 的，例如視頻遊戲模擬器。現在 NES 已經不常見了，但我們還是可以用 NES 硬件模擬器來玩 NES 遊戲。這些模擬器必須能忠實地 重建每一個細節，以及原硬件的每個主要組件。

另外一些虛擬機則完全是虛構的，而非用來模擬硬件。這類虛擬機的主要用途是使軟件開發 更容易。例如，要開發一個能運行在不同計算架構上的程序，你無需使用每種架構特定的匯 編方言來實現一遍自己的程序，而只需要使用一個跨平臺的虛擬機提供的彙編語言。

注：編譯器也解決了類似的跨平臺問題，它將標準的高級語言編寫的程序編譯成能在不同 CPU 架構上執行的程序。

相比之下，虛擬機的跨平臺方式是自己創建一個標準的 CPU 架 構，然後在不同的物理設備上模擬這個 CPU 架構。編譯器方式的優點是沒有運行時開銷 （runtime overhead），但實現一個支持多平臺的編譯器是非常困難的，但實現一個虛擬 機就簡單多了。

在實際中，人們會根據需求的不同混合使用虛擬機和編譯器，因爲二者工 作在不同的層次。

Java Virtual Machine (JVM) 就是一個非常成功的例子。JVM 本身是一箇中等大小、程序員完全能夠看懂的程序，因此很 容易將它移植到包括手機在內的上千種設備上。只要在設備上實現了 JVM，接下來任何 Java、Kotlin 或 Clojure 程序都無需任何修改就可以直接運行在這個設備上。唯一的開銷 來自虛擬機自身以及機器之上的 進一步抽象。大部分情況下，這完全是可以接受的。

虛擬機不必很大或者能適應各種場景，老式的視頻遊戲 經常使用很小的虛擬機來提 供簡單的腳本系統（scripting systems）。

虛擬機還適用於在一個安全的或隔離的環境中執行代碼。一個例子就是垃圾回收（GC）。要 在 C 或 C++ 之上實現一個自動垃圾回收機制並不容易 ，因爲程序無法看到它自身的棧或變量。但是，虛擬機是在它運行的程序 “之外” 的，因此它能夠看到棧上所有的內存引用 。

另一個例子是以太坊智能合約 （Ethereum smart contracts）。智能合約是在區塊鏈網絡中被驗證節點（validating node）執行的小段程序。這就要求 人們在無法提前審查這些由陌生人編寫的代碼的情況下，直接他們的機器上執行這些代碼。

爲避免合約執行一些惡意行爲，智能合約將它們放到一個 虛擬機 內執行，這個虛擬機沒有權限訪問文件系統、網絡、磁盤等等資源。以太坊也很好地展現了虛擬機的可移植性特性，因爲以太坊節點可以運行在多種計算機和操作系統上。使用虛擬機 使得智能合約的編寫無需考慮將在什麼平臺運行。

  1. LC-3 架構

我們的虛擬機將會模擬一個虛構的稱爲 LC-3 的計算機。LC-3 在學校中比較流行，用於教學生如何用匯編編程。與 x86 相比 ，LC-3 的指令集更 加簡化，但現代 CPU 的主要思想其中都包括了。

我們首先需要模擬機器最基礎的硬件組件，嘗試來理解每個組件是做什麼的，如果 現在無法將這些組件拼成一張完整的圖也不要着急。

2.1 內存

LC-3 有 65,536 個內存位置（16 bit 無符號整形能尋址的最大值），每個位置可以存儲一 個 16-bit 的值。這意味着它總共可以存儲 128KB 數據（64K * 2 Byte），比我們平時接觸 的計算機內存小多了！在我們的程序中，這個內存會以簡單數組的形式存放數據：

/* 65536 locations */
uint16_t memory[UINT16_MAX];

2.2 寄存器

一個寄存器就是 CPU 上一個能夠存儲單個數據的槽（slot）。寄存器就像是 CPU 的 “工作臺”（workbench），CPU 要對一段數據進行處理，必須先將數據放到某個寄存器中。但 因爲寄存器的數量很少，因此在任意時刻只能有很少的數據加載到寄存器。計算機的解決辦 法是：首先將數據從內存加載到寄存器，然後將計算結果放到其他寄存器，最後將最終結果 再寫回內存。

LC-3 總共有 10 個寄存器，每個都是 16 比特。其中大部分都是通用目的寄存器，少數幾 個用於特定目的。

通用目的寄存器可以用於執行任何程序計算。程序計數器（PC）是一個無符號整數，表示內 存中將要執行的下一條指令的地址。條件標記寄存器記錄前一次計算結果的正負符號。

enum {
    R_R0 = 0,
    R_R1,
    R_R2,
    R_R3,
    R_R4,
    R_R5,
    R_R6,
    R_R7,
    R_PC, /* program counter */
    R_COND,
    R_COUNT
};

和內存一樣，我們也用數組來表示這些寄存器：

uint16_t reg[R_COUNT];

2.3 指令集

一條指令就是一條 CPU 命令，它告訴 CPU 執行什麼任務，例如將兩個數相加。一條指令包 含兩部分：

每個操作碼代表 CPU “知道” 的一種任務。在 LC-3 中只有 16 個操作碼。計算機能夠完成 的所有計算，都是這些簡單指令組成的指令流。每條指令 16 比特長，其中最左邊的 4 個 比特存儲的是操作碼，其餘的比特存儲的是參數。

我們稍後會詳細介紹每條指令是做什麼的，現在先定義下面的這些操作碼，確保它們 是按如下順序定義的，這樣每條指令就可以獲得正確的枚舉值：

enum {
    OP_BR = 0, /* branch */
    OP_ADD,    /* add  */
    OP_LD,     /* load */
    OP_ST,     /* store */
    OP_JSR,    /* jump register */
    OP_AND,    /* bitwise and */
    OP_LDR,    /* load register */
    OP_STR,    /* store register */
    OP_RTI,    /* unused */
    OP_NOT,    /* bitwise not */
    OP_LDI,    /* load indirect */
    OP_STI,    /* store indirect */
    OP_JMP,    /* jump */
    OP_RES,    /* reserved (unused) */
    OP_LEA,    /* load effective address */
    OP_TRAP    /* execute trap */
};

注：Intel x86 架構有幾百條指令，而其他的架構例如 ARM 和 LC-3 只有很少的指令 。較小的指令集稱爲精簡指令集（RISC），較大 的指令集稱爲複雜指令集（CISC）。更大 的指令集本質上通常並沒有提供新特性，只是使得編寫 彙編更加方便 。一條 CISC 指令能做的事情可能需要好幾條 RISC 才能完成。

但是，對設計和製造工程 師來說，CISC 更加複雜和昂貴，設計和製造業更貴。包括這一點在內的一些權衡使得指 令設計也在不斷變化。

2.4 條件標誌位

R_COND 寄存器存儲條件標記，其中記錄了最近一次計算的執行結果。這使得程序可以完成諸如 if (x > 0) { ... } 之類的邏輯條件。

每個 CPU 都有很多條件標誌位來表示不同的情形。LC-3 只使用 3 個條件標記位，用來 表示前一次計算結果的符號：

enum {
    FL_POS = 1 << 0, /* P */
    FL_ZRO = 1 << 1, /* Z */
    FL_NEG = 1 << 2, /* N */
};

注：<<和>> 表示移位操作。

至此，我們就完成了虛擬機的硬件組件的模擬。

  1. 彙編示例

下面通過一個 LC-3 彙編程序先來感受一下這個虛擬機運行的是什麼代碼。這裏無需知 道如何編寫彙編程序或者理解背後的工作原理，只是先直觀感受一下。下面是 “Hello World” 例子：

.ORIG x3000                        ; this is the address in memory where the program will be loaded
LEA R0, HELLO_STR                  ; load the address of the HELLO_STR string into R0
PUTs                               ; output the string pointed to by R0 to the console
HALT                               ; halt the program
HELLO_STR .STRINGZ "Hello World!"  ; store this string here in the program
.END                               ; mark the end of the file

和 C 類似，這段程序從最上面開始，每次執行一條聲明（statement）。但和 C 不同的是， 這裏沒有作用域符號 {} 或者控制結構（例如 if 和 while），僅僅是一個扁平的聲 明列表（a flat list of statements）。這樣的程序更容易執行。

注意，其中一些聲明中的名字和我們前面的定義的操作碼（opcodes）是一樣的。前面 介紹到，每條指令都是 16 比特，但這裏的彙編程序看起來每行的字符數都是不一樣的。爲什麼會有這種不一致呢？

這是因爲這些彙編聲明都是以人類可讀寫的格式編寫的，以純文本的形式表示。一種稱爲 彙編器（assembler）的工具會將這些文本格式的指令轉換成 16 比特的二進制指令， 後者是虛擬機可以理解的。這種二進制格式稱爲機器碼（machine code），是虛擬機可以 執行的格式，其本質上就是一個 16 比特指令組成的數組。

注：雖然在開發中編譯器（compiler）和彙編器（assembler）的角色是類似的，但二者 是兩個不同的工具。彙編器只是簡單地將程序員編寫的文本編碼（encode）成二進制格式 ，將其中的符號替換成相應的二進制表示並打包到指令內。

.ORIG 和 .STRINGZ 看起來像是指令，但其實不是，它們稱爲彙編制導命令 （assembler directives），可以生成一段代碼或數據。例如，.STRINGZ 會在它所在的 位置插入一段字符串。

循環和條件判斷是通過類似 goto 的指令實現的。下面是一個如何計時到 10 的例子：

AND R0, R0, 0                      ; clear R0
LOOP                               ; label at the top of our loop
ADD R0, R0, 1                      ; add 1 to R0 and store back in R0
ADD R1, R0, -10                    ; subtract 10 from R0 and store back in R1
BRn LOOP                           ; go back to LOOP if the result was negative
... ; R0 is now 10!

注：本文不需要讀者會編寫彙編代碼。但如果你感興趣，你可以使用 LC-3 工具來編寫和彙編你自己寫的彙編程序。

  1. 執行程序

前面的例子是給大家一個直觀印象來理解虛擬機在做什麼。實現一個虛擬機不必精通匯編編 程，只要遵循正確的流程來讀取和執行指令，任何 LC-3 程序都能夠正確執行，不管這些程 序有多麼複雜。理論上，這樣的虛擬機甚至可以運行一個瀏覽器或者 Linux 這樣的操作系 統。

如果深入地思考這個特性，你就會意識到這是一個在哲學上非常奇特的現象：程序能完成各種智能的事情，其中一些我們甚至都很難想象；但同時，所有這些程序最終都是用我們編 寫的這些少量指令來執行的！我們既瞭解 —— 又不瞭解 —— 那些和程序執行相關的的事情。圖靈 曾經討探討過這種令人驚歎的思想：

“The view that machines cannot give rise to surprises is due, I believe, to a fallacy to which philosophers and mathematicians are particularly subject. This is the assumption that as soon as a fact is presented to a mind all consequences of that fact spring into the mind simultaneously with it. It is a very useful assumption under many circumstances, but one too easily forgets that it is false.” — Alan M. Turing

過程（Procedure）

我們將編寫的這個過程（procedure）描述如下：

你可能會有疑問：“如果這個循環不斷遞增 PC，而我們沒有 if 或 while，那程序不會 很快運行到內存外嗎？” 答案是不會，我們前面提到過，有類似 goto 的指令會通過修改 PC 來改變執行流。

下面是以上流程的大致代碼實現：

int main(int argc, const char* argv[]) {
    {Load Arguments, 12}
    {Setup, 12}

    /* set the PC to starting position */
    enum { PC_START = 0x3000 }; /* 0x3000 is the default */
    reg[R_PC] = PC_START;

    int running = 1;
    while (running) {
        uint16_t instr = mem_read(reg[R_PC]++); /* FETCH */
        uint16_t op = instr >> 12;

        switch (op) {
            case OP_ADD: {ADD, 6} break;
            case OP_AND: {AND, 7} break;
            case OP_NOT: {NOT, 7} break;
            case OP_BR: {BR, 7} break;
            case OP_JMP: {JMP, 7} break;
            case OP_JSR: {JSR, 7} break;
            case OP_LD: {LD, 7} break;
            case OP_LDI: {LDI, 6} break;
            case OP_LDR: {LDR, 7} break;
            case OP_LEA: {LEA, 7} break;
            case OP_ST: {ST, 7} break;
            case OP_STI: {STI, 7} break;
            case OP_STR: {STR, 7} break;
            case OP_TRAP: {TRAP, 8} break;
            case OP_RES:
            case OP_RTI:
            default:
                {BAD OPCODE, 7}
                break;
        }
    }
    {Shutdown, 12}
}
  1. 指令實現

現在需要做的就是正確地實現每一條指令。每條指令的詳細描述見 GitHub Repo 中附錄的 PDF 文檔。你需要 照着文檔的描述自己實現這些指令。這項工作做起來其實比聽起來要容易。下面我會拿其中 的兩個作爲例子來展示如何實現，其餘的見下一章。

5.1 ADD

ADD 指令將兩個數相加，然後將結果存到一個寄存器中。關於這條指令的描述見 526 頁。ADD 指令的編碼格式如下：

這裏給出了兩張圖是因爲 ADD 指令有兩種不同的 “模式”。在解釋模式之前，先來看看兩張 圖的共同點：

至此，我們知道了相加的結果應該存到哪裏，以及相加的第一個數字。只要再知道第二個數 在哪裏就可以執行加法操作了。從這裏開始，這兩者模式開始不同：注意第 5 比特 ，這個標誌位表示的是操作模式是立即模式（immediate mode）還是寄存器模式 （register mode）。在寄存器模式中，第二個數是存儲在寄存器中的，和第一個數類似。這個寄存器稱爲 SR2，保存在第 0-2 比特中。第 3 和 第 4 比特沒用到。用匯編代碼描 述就是：

ADD R2 R0 R1 ; add the contents of R0 to R1 and store in R2.

在立即模式中，第二個數直接存儲在指令中，而不是寄存器中。這種模式更加方便，因 爲程序不需要額外的指令來將數據從內存加載到寄存器，直接從指令中就可以拿到這個值。這種方式的限制是存儲的數很小，不超過 2^5 = 32（無符號）。這種方式很適合對一個值 進行遞增。用匯編描述就是：

ADD R0 R0 1 ; add 1 to R0 and store back in R0

下面一段解釋來自 LC-3 規範：

If bit [5] is 0, the second source operand is obtained from SR2. If bit [5] is 1, the second source operand is obtained by sign-extending the imm5 field to 16 bits. In both cases, the second source operand is added to the contents of SR1 and the result stored in DR. (Pg. 526)

這段解釋也就是我們前面討論的內容。但什麼是 “sign-extending”（有符號擴展）？雖然立即 模式中存儲的值只有 5 比特，但這個值需要加到一個 16 比特的值上。因此，這些 5 比 特的數需要擴展到 16 比特才能和另一個數相匹配。對於正數，我們可以在前面填充 0， 填充之後值是不變的。但是，對於負數，這樣填充會導致問題。例如， -1 的 5 比特表示 是 11111。如果我們用 0 填充，那填充之後的 0000 0000 0001 1111 等於 32！這種 情況下就需要使用有符號擴展（ sign extension），對於正數填充 0，對負數填充 1。

uint16_t sign_extend(uint16_t x, int bit_count) {
    if ((x >> (bit_count - 1)) & 1) {
        x |= (0xFFFF << bit_count);
    }
    return x;
}

注：如果你如何用二進制表示負數感興趣，可以查閱二進制補碼（Two’s Complement） 相關的內容。本文中只需要知道怎麼進行有符號擴展就行了。

規範中還有一句：

The condition codes are set, based on whether the result is negative, zero, or positive. (Pg. 526)

前面我們定義的那個條件標記枚舉類型現在要派上用場了。每次有值寫到寄存器時，我們 需要更新這個標記，以標明這個值的符號。爲了方便，我們用下面的函數來實現這個功能：

void update_flags(uint16_t r) {
    if (reg[r] == 0) {
        reg[R_COND] = FL_ZRO;
    }
    else if (reg[r] >> 15) { /* a 1 in the left-most bit indicates negative */
        reg[R_COND] = FL_NEG;
    } else {
        reg[R_COND] = FL_POS;
    }
}

現在我們就可以實現 ADD 的邏輯了：

{
    uint16_t r0 = (instr >> 9) & 0x7; /* destination register (DR) */
    uint16_t r1 = (instr >> 6) & 0x7; /* first operand (SR1) */
    uint16_t imm_flag = (instr >> 5) & 0x1; /* whether we are in immediate mode */

    if (imm_flag) {
        uint16_t imm5 = sign_extend(instr & 0x1F, 5);
        reg[r0] = reg[r1] + imm5;
    } else {
        uint16_t r2 = instr & 0x7;
        reg[r0] = reg[r1] + reg[r2];
    }

    update_flags(r0);
}

本節包含了大量信息，這裏再總結一下：

以上就是 ADD 的實現，你可能會覺得以這樣的方式實現另外 15 個指令將會是一件非常繁 瑣的事情。好消息是，前面的這些函數基本都是可以重用的，因爲另外 15 條指令中，大部 分都會組合有符號擴展、不同的模式和更新條件標記等等。

5.2 LDI

LDI 是 load indirect 的縮寫，用於從內存加載一個值到寄存器，規範見 532 頁。LDI 的二進制格式如下：

與 ADD 相比，LDI 只有一種模式，參數也更少。LDI 的操作碼是 1010，對應 OP_LDI 枚舉類型。和 ADD 類似，它包含一個 3 比特的 DR（destination register）寄存器，用 於存放加載的值。剩餘的比特組成 PCoffset9 字段，這是該指令內嵌的一個立即值（ immediate value），和 imm5 類似。由於這個指令是從內存加載值，因此我們可以猜測 ，PCoffset9 是一個加載值的內存地址。LC-3 規範提供了更多細節：

An address is computed by sign-extending bits [8:0] to 16 bits and adding this value to the incremented PC. What is stored in memory at this address is the address of the data to be loaded into DR. (Pg. 532)

和前面一樣，我們需要將這個 9 比特的 PCoffset9 以有符號的方式擴展到 16 比特，但 這次是將擴展之後的值加到當前的程序計數器 PC（如果回頭去看前面的 while 循 環，就會發現這條指令加載之後 PC 就會遞增）。相加得到的結果（也就是 PC 加完之後的 值）表示一個內存地址，這個地址中存儲的值表示另一個地址，後者中存儲的是需要加載到 DR 中的值。

這種方式聽上去非常繞，但它確是不可或缺的。LD 指令只能加載 offset 是 9 位的地址， 但整個內存是 16 位的。LDI 適用於加載那些遠離當前 PC 的地址內的值，但要加載這 些值，需要將這些最終地址存儲在離 PC 較近的位置。可以將它想想成 C 中有一個局部變 量，這變量是指向某些數據的指針：

// the value of far_data is an address
// of course far_data itself (the location in memory containing the address) has an address

char* far_data = "apple";

// In memory it may be layed out like this:

// Address Label      Value
// 0x123:  far_data = 0x456
// ...
// 0x456:  string   = 'a'

// if PC was at 0x100
// LDI R0 0x023
// would load 'a' into R0

和 ADD 類似，將值放到 DR 之後需要更新條件標誌位：

The condition codes are set based on whether the value loaded is negative, zero, or positive. (Pg. 532)

下面是我對 LDI 的實現（後面章節中會介紹 mem_read）：

{
    uint16_t r0 = (instr >> 9) & 0x7; /* destination register (DR) */
    uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); /* PCoffset 9*/

    /* add pc_offset to the current PC, look at that memory location to get the final address */
    reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset));
    update_flags(r0);
}

後面會看到，這些指令的實現中，大部分輔助功能函數都是可以複用的。

以上是兩個例子，接下來就可以參考這兩個例子實現其他的指令。注意本文中有兩個指令是 沒有用到的：OP_RTI 和 OP_RES。你可以忽略這兩個指令，如果執行到它們直接報錯。將 main() 函數中未實現的 switch case 補全後，你的虛擬機主體就完成了！

  1. 全部指令的參考實現

本節給出所有指令的實現。如果你自己的實現遇到問題，可以參考這裏給出的版本。

6.1 RTI & RES

這兩個指令本文沒用到。

abort();

6.2 Bitwise and（按位與）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t imm_flag = (instr >> 5) & 0x1;

    if (imm_flag) {
        uint16_t imm5 = sign_extend(instr & 0x1F, 5);
        reg[r0] = reg[r1] & imm5;
    } else {
        uint16_t r2 = instr & 0x7;
        reg[r0] = reg[r1] & reg[r2];
    }
    update_flags(r0);
}

6.3 Bitwise not（按位非）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;

    reg[r0] = ~reg[r1];
    update_flags(r0);
}

6.4 Branch（條件分支）

{
    uint16_t pc_offset = sign_extend((instr) & 0x1ff, 9);
    uint16_t cond_flag = (instr >> 9) & 0x7;
    if (cond_flag & reg[R_COND]) {
        reg[R_PC] += pc_offset;
    }
}

6.5 Jump（跳轉）

RET 在規範中作爲一個單獨的指令列出，因爲在彙編中它是一個獨立的關鍵字。但是，RET 本質上是 JMP 的一個特殊情況。當 R1 爲 7 時會執行 RET。

{
    /* Also handles RET */
    uint16_t r1 = (instr >> 6) & 0x7;
    reg[R_PC] = reg[r1];
}

6.6 Jump Register（跳轉寄存器）

{
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t long_pc_offset = sign_extend(instr & 0x7ff, 11);
    uint16_t long_flag = (instr >> 11) & 1;

    reg[R_R7] = reg[R_PC];
    if (long_flag) {
        reg[R_PC] += long_pc_offset;  /* JSR */
    } else {
        reg[R_PC] = reg[r1]; /* JSRR */
    }
    break;
}

6.7 Load（加載）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1ff, 9);
    reg[r0] = mem_read(reg[R_PC] + pc_offset);
    update_flags(r0);
}

6.8 Load Register（加載寄存器）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t offset = sign_extend(instr & 0x3F, 6);
    reg[r0] = mem_read(reg[r1] + offset);
    update_flags(r0);
}

6.9 Load Effective Address（加載有效地址）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1ff, 9);
    reg[r0] = reg[R_PC] + pc_offset;
    update_flags(r0);
}

6.10 Store（存儲）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1ff, 9);
    mem_write(reg[R_PC] + pc_offset, reg[r0]);
}

6.11 Store Indirect（間接存儲）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1ff, 9);
    mem_write(mem_read(reg[R_PC] + pc_offset), reg[r0]);
}

6.12 Store Register（存儲寄存器）

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;
    uint16_t offset = sign_extend(instr & 0x3F, 6);
    mem_write(reg[r1] + offset, reg[r0]);
}
  1. Trap Routines（中斷陷入例程）

LC-3 提供了幾個預定於的函數（過程），用於執行常規任務以及與 I/O 設備交換， 例如，用於從鍵盤接收輸入的函數，在控制檯上顯示字符串的函數。這些都稱爲 trap routines，你可以將它們當做操作系統或者是 LC-3 的 API。每個 trap routine 都有一個對應的 trap code（中斷號）。要執行一次捕獲， 需要用相應的 trap code 執行 TRAP 指令。

定義所有 trap code：

enum {
    TRAP_GETC = 0x20,  /* get character from keyboard, not echoed onto the terminal */
    TRAP_OUT = 0x21,   /* output a character */
    TRAP_PUTS = 0x22,  /* output a word string */
    TRAP_IN = 0x23,    /* get character from keyboard, echoed onto the terminal */
    TRAP_PUTSP = 0x24, /* output a byte string */
    TRAP_HALT = 0x25   /* halt the program */
};

你可能會覺得奇怪：爲什麼 trap code 沒有包含在指令編碼中？這是因爲它們沒有給 LC-3 帶來任何新功能，只是提供了一種方便地執行任務的方式（和 C 中的系統函數類似 ）。在官方 LC-3 模擬器中，trap routines 是用匯編實現的。當調用到 trap code 時，PC 會移動到 code 對應的地址。CPU 執行這個函數（ procedure）的指令流，函數結束後 PC 重置到 trap 調用之前的位置。

注：這就是爲什麼程序從 0x3000 而不是 0x0 開始的原因。低地址空間是特意留出來 給 trap routine 用的。

規範只定義了 trap routine 的行爲，並沒有規定應該如何實現。在我們這個虛擬機中， 將會用 C 實現。當觸發某個 trap code 時，會調用一個相應的 C 函數。這個函數執行 完成後，執行過程會返回到原來的指令流。

雖然 trap routine 可以用匯編實現，而且物理的 LC-3 計算機也確實是這樣做的，但對虛 擬機來說並不是非常合適。相比於實現自己的 primitive I/O routines，我們可以利用操 作系統上已有的。這樣可以使我們的虛擬機運行更良好，還簡化了代碼，提供了一個便於移 植的高層抽象。

注：從鍵盤獲取輸入就是一個例子。彙編版本使用一個循環來持續檢查鍵盤有沒有輸入 ，這會消耗大量 CPU 而實際上沒做多少事情！使用操作系統提供的某個合適的輸入函 數的話，程序可以在收到輸入之前一直 sleep。

TRAP 處理邏輯：

switch (instr & 0xFF) {
    case TRAP_GETC: {TRAP GETC, 9} break;
    case TRAP_OUT: {TRAP OUT, 9} break;
    case TRAP_PUTS: {TRAP PUTS, 8} break;
    case TRAP_IN: {TRAP IN, 9} break;
    case TRAP_PUTSP: {TRAP PUTSP, 9} break;
    case TRAP_HALT: {TRAP HALT, 9} break;
}

和前面幾節類似，我會拿一個 trap routine 作爲例子展示如何實現，其他的留給讀者自己 完成。

7.1 PUTS

PUT trap code 用於輸出一個以空字符結尾的字符串（和 C 中的 printf 類似）。規 範見 543 頁。

顯示一個字符串需要將這個字符串的地址放到 R0 寄存器，然後觸發 trap。規範中說：

Write a string of ASCII characters to the console display. The characters are contained in consecutive memory locations, one character per memory location, starting with the address specified in R0. Writing terminates with the occurrence of x0000 in a memory location. (Pg. 543)

意思是說字符串是存儲在一個連續的內存區域。注意這裏和 C 中的字符串有所不同：C 中每個字符佔用一個 byte；LC-3 中內存尋找是 16 位的，每個字符都是 16 位，佔用 兩個 byte。因此要用 C 函數打印這些字符，需要將每個值先轉換成 char 類型再輸出：

{
    /* one char per word */
    uint16_t* c = memory + reg[R_R0];
    while (*c) {
        putc((char)*c, stdout);
        ++c;
    }
    fflush(stdout);
}

這就是 PUTS trap routine 的實現了。如果熟悉 C 的話，這個函數應該很容易理解。現 在你可以按照 LC-3 規範，自己動手實現其他的 trap routine 了。

  1. Trap Routine 參考實現

本節給出所有 trap routine 的一份參考實現。

8.1 輸入單個字符（Input Character）

/* read a single ASCII char */
reg[R_R0] = (uint16_t)getchar();

8.2 輸出單個字符（Output Character）

putc((char)reg[R_R0], stdout);
fflush(stdout);

8.3 打印輸入單個字符提示（Prompt for Input Character）

printf("Enter a character: ");
char c = getchar();
putc(c, stdout);
reg[R_R0] = (uint16_t)c;

8.4 輸出字符串（Output String）

{
    /* one char per byte (two bytes per word) here we need to swap back to
       big endian format */
    uint16_t* c = memory + reg[R_R0];
    while (*c) {
        char char1 = (*c) & 0xFF;
        putc(char1, stdout);
        char char2 = (*c) >> 8;
        if (char2) putc(char2, stdout);
        ++c;
    }
    fflush(stdout);
}

8.5 暫停程序執行（Halt Program）

puts("HALT");
fflush(stdout);
running = 0;
  1. 加載程序

前面提到了從內存加載和執行指令，但指令是如何進入內存的呢？將彙編程序轉換爲 機器碼時，得到的是一個文件，其中包含一個指令流和相應的數據。只需要將這個文件的內 容複製到內存就算完成加載了。

程序的前 16 比特規定了這個程序在內存中的起始地址，這個地址稱爲 origin。因此 加載時應該首先讀取這 16 比特，確定起始地址，然後才能依次讀取和放置後面的指令及數 據。

下面是將 LC-3 程序讀到內存的代碼：

void read_image_file(FILE* file) {
    uint16_t origin; /* the origin tells us where in memory to place the image */
    fread(&origin, sizeof(origin), 1, file);
    origin = swap16(origin);

    /* we know the maximum file size so we only need one fread */
    uint16_t max_read = UINT16_MAX - origin;
    uint16_t* p = memory + origin;
    size_t read = fread(p, sizeof(uint16_t), max_read, file);

    /* swap to little endian */
    while (read-- > 0) {
        *p = swap16(*p);
        ++p;
    }
}

注意讀取前 16 比特之後，對這個值執行了 swap16()。這是因爲 LC-3 程序是大端 （big-endian），但現在大部分計算機都是小端的（little-endian），因此需要做大小端 轉換。如果你是在某些特殊的機器 （例如 PPC）上運行，那就不 需要這些轉換了。

uint16_t swap16(uint16_t x) {
    return (x << 8) | (x >> 8);
}

注：大小端（Endianness）是指對於 一個整型數據，它的每個字節應該如何解釋。在小端中，第一個字節是最低位，而在大端 中剛好相反，第一個字節是最高位。據我所知，這個順序完全是人爲規定的。不同的公司 做出的抉擇不同，因此我們這些後來人只能針對大小端做一些特殊處理。要理解本文中大 小端相關的內容，知道這些就足夠了。

我們再封裝一下前面加載程序的函數，接受一個文件路徑字符串作爲參數，這樣更加方便：

int read_image(const char* image_path) {
    FILE* file = fopen(image_path, "rb");
    if (!file) { return 0; };
    read_image_file(file);
    fclose(file);
    return 1;
}
  1. 內存映射寄存器（Memory Mapped Registers）

某些特殊類型的寄存器是無法從常規寄存器表（register table）中訪問的。因此，在內 存中爲這些寄存器預留了特殊的地址。要讀寫這些寄存器，只需要讀寫相應的內存地址。這些稱爲 內存映射寄存器（MMR）。內存映射寄存器通常用於處理與特殊硬件的交互。

LC-3 有兩個內存映射寄存器需要實現，分別是：

enum {
    MR_KBSR = 0xFE00, /* keyboard status */
    MR_KBDR = 0xFE02  /* keyboard data */
};

內存映射寄存器使內存訪問稍微複雜了一些。這種情況下不能直接讀寫內存位置，而要使 用 setter 和 getter 輔助函數。當獲取輸入時，getter 會檢查鍵盤輸入並更新兩 個寄存器（也就是相應的內存位置）。

void mem_write(uint16_t address, uint16_t val) {
    memory[address] = val;
}

uint16_t mem_read(uint16_t address)
{
    if (address == MR_KBSR) {
        if (check_key()) {
            memory[MR_KBSR] = (1 << 15);
            memory[MR_KBDR] = getchar();
        } else {
            memory[MR_KBSR] = 0;
        }
    }
    return memory[address];
}

這就是我們的虛擬機的最後一部分了！只要你實現了前面提到的 trap routine 和指令，你 的虛擬機就即將能夠運行了！

  1. 平臺相關的細節

本節包含一些與鍵盤交互以及顯示相關的代碼。如果不感興趣可以直接複製粘貼。

如果不是在 Unix 類系統上運行本程序，例如 Windows，那本節內容需要替換爲相應的平臺 實現。

uint16_t check_key() {
    fd_set readfds;
    FD_ZERO(&readfds);
    FD_SET(STDIN_FILENO, &readfds);

    struct timeval timeout;
    timeout.tv_sec = 0;
    timeout.tv_usec = 0;
    return select(1, &readfds, NULL, NULL, &timeout) != 0;
}

下面是特定於 Unix 的設置終端輸入的代碼：

struct termios original_tio;

void disable_input_buffering() {
    tcgetattr(STDIN_FILENO, &original_tio);
    struct termios new_tio = original_tio;
    new_tio.c_lflag &= ~ICANON & ~ECHO;
    tcsetattr(STDIN_FILENO, TCSANOW, &new_tio);
}

void restore_input_buffering() {
    tcsetattr(STDIN_FILENO, TCSANOW, &original_tio);
}

當程序被中斷時，我們需要將終端的設置恢復到默認：

void handle_interrupt(int signal) {
    restore_input_buffering();
    printf("\n");
    exit(-2);
}
signal(SIGINT, handle_interrupt);
disable_input_buffering();
  1. 運行虛擬機

現在你可以編譯和運行這個 LC-3 虛擬機了！

使用你喜歡的 C 編譯器編譯這個虛擬機（ https://arthurchiao.art/assets/img/write-your-own-virtual-machine-zh/lc3-vm.c ），然後下載匯 編之後的兩個小遊戲：

用如下命令執行：lc3-vm path/to/2048.obj。

Play 2048!
{2048 Example 13}
Control the game using WASD keys.
Are you on an ANSI terminal (y/n)? y
+--------------------------+
|                          |
|                          |
|                          |
|                     2    |
|                          |
|   2                      |
|                          |
|                          |
|                          |
+--------------------------+

調試

如果程序不能正常工作，那可能是你的實現有問題。調試程序就有點麻煩了。我建議通讀 LC-3 程序的彙編源代碼，然後使用一個調試器單步執行虛擬機指令，確保虛擬機執行到 的指令是符合預期的。如果發現了不符合預期的行爲，就需要重新查看 LC-3 規範，確認你 的實現是否有問題。

  1. C++ 實現（可選）

使用 C++ 會使代碼更簡短。本節介紹 C++ 的一些實現技巧。

C++ 有強大的編譯時泛型（compile-time generics）機制，可以幫我們自動生成部分指令 的實現代碼。這裏的基本思想是重用每個指令的公共部分。例如，好幾條指令都用到了間接 尋址或有符號擴展然後加到當前寄存器的功能。模板如下：

{Instruction C++ 14}
template <unsigned op>
void ins(uint16_t instr) {
    uint16_t r0, r1, r2, imm5, imm_flag;
    uint16_t pc_plus_off, base_plus_off;

    uint16_t opbit = (1 << op);
    if (0x4EEE & opbit) { r0 = (instr >> 9) & 0x7; }
    if (0x12E3 & opbit) { r1 = (instr >> 6) & 0x7; }
    if (0x0022 & opbit) {
        r2 = instr & 0x7;
        imm_flag = (instr >> 5) & 0x1;
        imm5 = sign_extend((instr) & 0x1F, 5);
    }
    if (0x00C0 & opbit) {   // Base + offset
        base_plus_off = reg[r1] + sign_extend(instr & 0x3f, 6);
    }
    if (0x4C0D & opbit) { // Indirect address
        pc_plus_off = reg[R_PC] + sign_extend(instr & 0x1ff, 9);
    }
    if (0x0001 & opbit) {
        // BR
        uint16_t cond = (instr >> 9) & 0x7;
        if (cond & reg[R_COND]) { reg[R_PC] = pc_plus_off; }
    }
    if (0x0002 & opbit) {  // ADD
        if (imm_flag) {
            reg[r0] = reg[r1] + imm5;
        } else {
            reg[r0] = reg[r1] + reg[r2];
        }
    }
    if (0x0020 & opbit) {  // AND
        if (imm_flag) {
            reg[r0] = reg[r1] & imm5;
        } else {
            reg[r0] = reg[r1] & reg[r2];
        }
    }
    if (0x0200 & opbit) { reg[r0] = ~reg[r1]; } // NOT
    if (0x1000 & opbit) { reg[R_PC] = reg[r1]; } // JMP
    if (0x0010 & opbit) {  // JSR
        uint16_t long_flag = (instr >> 11) & 1;
        pc_plus_off = reg[R_PC] +  sign_extend(instr & 0x7ff, 11);
        reg[R_R7] = reg[R_PC];
        if (long_flag) {
            reg[R_PC] = pc_plus_off;
        } else {
            reg[R_PC] = reg[r1];
        }
    }

    if (0x0004 & opbit) { reg[r0] = mem_read(pc_plus_off); } // LD
    if (0x0400 & opbit) { reg[r0] = mem_read(mem_read(pc_plus_off)); } // LDI
    if (0x0040 & opbit) { reg[r0] = mem_read(base_plus_off); }  // LDR
    if (0x4000 & opbit) { reg[r0] = pc_plus_off; } // LEA
    if (0x0008 & opbit) { mem_write(pc_plus_off, reg[r0]); } // ST
    if (0x0800 & opbit) { mem_write(mem_read(pc_plus_off), reg[r0]); } // STI
    if (0x0080 & opbit) { mem_write(base_plus_off, reg[r0]); } // STR
    if (0x8000 & opbit) {  // TRAP
         {TRAP, 8}
    }
    //if (0x0100 & opbit) { } // RTI
    if (0x4666 & opbit) { update_flags(r0); }
}
{Op Table 14}
static void (*op_table[16])(uint16_t) = {
    ins<0>, ins<1>, ins<2>, ins<3>,
    ins<4>, ins<5>, ins<6>, ins<7>,
    NULL, ins<9>, ins<10>, ins<11>,
    ins<12>, NULL, ins<14>, ins<15>
};

這裏的技巧是從 Bisqwit’s NES emulator 學來的。如果你對仿真或 NES 感興趣，強烈建議觀看他的視頻。

完整版 C++ 實現見:
https://justinmeiners.github.io/lc3-vm/src/lc3-alt.cpp

譯者：ArthurChiao

來源：https://arthurchiao.art/blog/write-your-own-virtual-machine-zh/

原文鏈接：

https://justinmeiners.github.io/lc3-vm/

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/wfxXSana4oYdWW6nzpwAUA

猜你喜歡