400 行 C 代碼實現(xiàn)一個虛擬機
鏈接：https://arthurchiao.art/blog/write-your-own-virtual-machine-zh/
1. 引言
本文將教你編寫一個自己的虛擬機（VM），這個虛擬機能夠運行匯編語言編寫的程序， 例如我朋友編寫的 2048 或者我自己的 Roguelike。如果你會編程，但希望 更深入地了解計算機的內(nèi)部原理以及編程語言是如何工作的，那本文很適合你。從零開始 寫一個虛擬機聽起來可能讓人有點望而生畏，但讀完本文之后你會驚訝于這件事原來如此簡 單，并從中深受啟發(fā)。
本文所說的虛擬機最終由 400 行左右 C 代碼組成。理解這些代碼只需要基本的 C/C++ 知識和二進制運算。這個虛擬機可以在 Unix 系統(tǒng)（包括 macOS）上執(zhí)行。代碼中包含少 量平臺相關的配置終端（terminal）和顯示（display）的代碼，但這些并不是本項目的核 心。（歡迎大家添加對 Windows 的支持。）
注意：這個虛擬機是Literate Programming 的產(chǎn)物。本文會解釋每段代碼的原理，最終的實現(xiàn)就是將這些代碼片段連起來。
什么是虛擬機？
虛擬機就像計算機（computer），它模擬包括 CPU 在內(nèi)的幾個硬件組件，能夠執(zhí)行 算術運算、讀寫內(nèi)存、與 I/O 設備交互。最重要的是，它能理解機器語言（machine language），因此可以用相應的語言來對它進行編程。
一個虛擬機需要模擬哪些硬件要看它的使用場景。有些虛擬機是設計用來模擬特定類型的計算設備 的，例如視頻游戲模擬器?，F(xiàn)在 NES 已經(jīng)不常見了，但我們還是可以用 NES 硬件模擬器來玩 NES 游戲。這些模擬器必須能忠實地 重建每一個細節(jié)，以及原硬件的每個主要組件。
另外一些虛擬機則完全是虛構的，而非用來模擬硬件。這類虛擬機的主要用途是使軟件開發(fā) 更容易。例如，要開發(fā)一個能運行在不同計算架構上的程序，你無需使用每種架構特定的匯 編方言來實現(xiàn)一遍自己的程序，而只需要使用一個跨平臺的虛擬機提供的匯編語言。
注：編譯器也解決了類似的跨平臺問題，它將標準的高級語言編寫的程序編譯成能在不同 CPU 架構上執(zhí)行的程序。
相比之下，虛擬機的跨平臺方式是自己創(chuàng)建一個標準的 CPU 架 構，然后在不同的物理設備上模擬這個 CPU 架構。編譯器方式的優(yōu)點是沒有運行時開銷 （runtime overhead），但實現(xiàn)一個支持多平臺的編譯器是非常困難的，但實現(xiàn)一個虛擬 機就簡單多了。
在實際中，人們會根據(jù)需求的不同混合使用虛擬機和編譯器，因為二者工 作在不同的層次。
Java Virtual Machine (JVM) 就是一個非常成功的例子。JVM 本身是一個中等大小、程序員完全能夠看懂的程序，因此很 容易將它移植到包括手機在內(nèi)的上千種設備上。只要在設備上實現(xiàn)了 JVM，接下來任何 Java、Kotlin 或 Clojure 程序都無需任何修改就可以直接運行在這個設備上。唯一的開銷 來自虛擬機自身以及機器之上的 進一步抽象。大部分情況下，這完全是可以接受的。
虛擬機不必很大或者能適應各種場景，老式的視頻游戲 經(jīng)常使用很小的虛擬機來提 供簡單的腳本系統(tǒng)（scripting systems）。
虛擬機還適用于在一個安全的或隔離的環(huán)境中執(zhí)行代碼。一個例子就是垃圾回收（GC）。要 在 C 或 C++ 之上實現(xiàn)一個自動垃圾回收機制并不容易 ，因為程序無法看到它自身的?；蜃兞?。但是，虛擬機是在它運行的程序“之外”的，因此它能夠看到棧上所有的內(nèi)存引用 。
另一個例子是以太坊智能合約 （Ethereum smart contracts）。智能合約是在區(qū)塊鏈網(wǎng)絡中被驗證節(jié)點（validating node）執(zhí)行的小段程序。這就要求 人們在無法提前審查這些由陌生人編寫的代碼的情況下，直接他們的機器上執(zhí)行這些代碼。
為避免合約執(zhí)行一些惡意行為，智能合約將它們放到一個 虛擬機 內(nèi)執(zhí)行，這個虛擬機沒有權限訪問文件系統(tǒng)、網(wǎng)絡、磁盤等等資源。以太坊也很好地展現(xiàn)了虛擬機的可移植性特性，因為以太坊節(jié)點可以運行在多種計算機和操作系統(tǒng)上。使用虛擬機 使得智能合約的編寫無需考慮將在什么平臺運行。
2. LC-3 架構
我們的虛擬機將會模擬一個虛構的稱為 LC-3 的計算機。LC-3 在學校中比較流行，用于教學生如何用匯編編程。與 x86 相比 ，LC-3 的指令集更 加簡化，但現(xiàn)代 CPU 的主要思想其中都包括了。
我們首先需要模擬機器最基礎的硬件組件，嘗試來理解每個組件是做什么的，如果 現(xiàn)在無法將這些組件拼成一張完整的圖也不要著急。
2.1 內(nèi)存
LC-3 有 65,536 個內(nèi)存位置（16 bit 無符號整形能尋址的最大值），每個位置可以存儲一 個 16-bit 的值。這意味著它總共可以存儲 128KB 數(shù)據(jù)（64K * 2 Byte），比我們平時接觸 的計算機內(nèi)存小多了！在我們的程序中，這個內(nèi)存會以簡單數(shù)組的形式存放數(shù)據(jù)：
/*?65536?locations?*/
uint16_t?memory[UINT16_MAX];
2.2 寄存器
一個寄存器就是 CPU 上一個能夠存儲單個數(shù)據(jù)的槽（slot）。寄存器就像是 CPU 的 “工作臺”（workbench），CPU 要對一段數(shù)據(jù)進行處理，必須先將數(shù)據(jù)放到某個寄存器中。但 因為寄存器的數(shù)量很少，因此在任意時刻只能有很少的數(shù)據(jù)加載到寄存器。計算機的解決辦 法是：首先將數(shù)據(jù)從內(nèi)存加載到寄存器，然后將計算結果放到其他寄存器，最后將最終結果 再寫回內(nèi)存。
LC-3 總共有 10 個寄存器，每個都是 16 比特。其中大部分都是通用目的寄存器，少數(shù)幾 個用于特定目的。
8 個通用目的寄存器（R0-R7） 1 個程序計數(shù)器（program counter, PC）寄存器 1 個條件標志位（condition flags，COND）寄存器
通用目的寄存器可以用于執(zhí)行任何程序計算。程序計數(shù)器（PC）是一個無符號整數(shù)，表示內(nèi) 存中將要執(zhí)行的下一條指令的地址。條件標記寄存器記錄前一次計算結果的正負符號。
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
};
和內(nèi)存一樣，我們也用數(shù)組來表示這些寄存器：
uint16_t?reg[R_COUNT];
2.3 指令集
一條指令就是一條 CPU 命令，它告訴 CPU 執(zhí)行什么任務，例如將兩個數(shù)相加。一條指令包 含兩部分：
操作碼（opcode）：表示任務的類型 執(zhí)行任務所需的參數(shù)
每個操作碼代表 CPU “知道”的一種任務。在 LC-3 中只有 16 個操作碼。計算機能夠完成 的所有計算，都是這些簡單指令組成的指令流。每條指令 16 比特長，其中最左邊的 4 個 比特存儲的是操作碼，其余的比特存儲的是參數(shù)。
我們稍后會詳細介紹每條指令是做什么的，現(xiàn)在先定義下面的這些操作碼，確保它們 是按如下順序定義的，這樣每條指令就可以獲得正確的枚舉值：
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）。更大 的指令集本質(zhì)上通常并沒有提供新特性，只是使得編寫 匯編更加方便 。一條 CISC 指令能做的事情可能需要好幾條 RISC 才能完成。
但是，對設計和制造工程 師來說，CISC 更加復雜和昂貴，設計和制造業(yè)更貴。包括這一點在內(nèi)的一些權衡使得指 令設計也在不斷變化。
2.4 條件標志位
R_COND 寄存器存儲條件標記，其中記錄了最近一次計算的執(zhí)行結果。這使得程序可以完成諸如?if (x > 0) { ... }?之類的邏輯條件。
每個 CPU 都有很多條件標志位來表示不同的情形。LC-3 只使用 3 個條件標記位，用來 表示前一次計算結果的符號：
enum?{
????FL_POS?=?1?<0,?/*?P?*/
????FL_ZRO?=?1?<1,?/*?Z?*/
????FL_NEG?=?1?<2,?/*?N?*/
};
注：<< 和 >> 表示移位操作。
至此，我們就完成了虛擬機的硬件組件的模擬。
3. 匯編示例
下面通過一個 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 類似，這段程序從最上面開始，每次執(zhí)行一條聲明（statement）。但和 C 不同的是， 這里沒有作用域符號 {} 或者控制結構（例如 if 和 while），僅僅是一個扁平的聲 明列表（a flat list of statements）。這樣的程序更容易執(zhí)行。
注意，其中一些聲明中的名字和我們前面的定義的操作碼（opcodes）是一樣的。前面 介紹到，每條指令都是 16 比特，但這里的匯編程序看起來每行的字符數(shù)都是不一樣的。為什么會有這種不一致呢？
這是因為這些匯編聲明都是以人類可讀寫的格式編寫的，以純文本的形式表示。一種稱為 匯編器（assembler）的工具會將這些文本格式的指令轉換成 16 比特的二進制指令， 后者是虛擬機可以理解的。這種二進制格式稱為機器碼（machine code），是虛擬機可以 執(zhí)行的格式，其本質(zhì)上就是一個 16 比特指令組成的數(shù)組。
注：雖然在開發(fā)中編譯器（compiler）和匯編器（assembler）的角色是類似的，但二者 是兩個不同的工具。匯編器只是簡單地將程序員編寫的文本編碼（encode）成二進制格式 ，將其中的符號替換成相應的二進制表示并打包到指令內(nèi)。
.ORIG?和?.STRINGZ?看起來像是指令，但其實不是，它們稱為匯編制導命令 （assembler directives），可以生成一段代碼或數(shù)據(jù)。例如，.STRINGZ?會在它所在的 位置插入一段字符串。
循環(huán)和條件判斷是通過類似 goto 的指令實現(xiàn)的。下面是一個如何計時到 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 工具來編寫和匯編你自己寫的匯編程序。
4. 執(zhí)行程序
前面的例子是給大家一個直觀印象來理解虛擬機在做什么。實現(xiàn)一個虛擬機不必精通匯編編 程，只要遵循正確的流程來讀取和執(zhí)行指令，任何 LC-3 程序都能夠正確執(zhí)行，不管這些程 序有多么復雜。理論上，這樣的虛擬機甚至可以運行一個瀏覽器或者 Linux 這樣的操作系 統(tǒng)。
如果深入地思考這個特性，你就會意識到這是一個在哲學上非常奇特的現(xiàn)象：程序能完成各種智能的事情，其中一些我們甚至都很難想象；但同時，所有這些程序最終都是用我們編 寫的這些少量指令來執(zhí)行的！我們既了解 —— 又不了解 —— 那些和程序執(zhí)行相關的的事情。圖靈 曾經(jīng)討探討過這種令人驚嘆的思想：
“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）描述如下：
1. 從 PC 寄存器指向的內(nèi)存地址中加載一條指令
2. 遞增 PC 寄存器
3. 查看指令中的 opcode 字段，判斷指令類型
4. 根據(jù)指令類型和指令中所帶的參數(shù)執(zhí)行該指令
5. 跳轉到步驟 1
你可能會有疑問：“如果這個循環(huán)不斷遞增 PC，而我們沒有 if 或 while，那程序不會 很快運行到內(nèi)存外嗎？”答案是不會，我們前面提到過，有類似 goto 的指令會通過修改 PC 來改變執(zhí)行流。
下面是以上流程的大致代碼實現(xiàn)：
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}
}
5. 指令實現(xiàn)
現(xiàn)在需要做的就是正確地實現(xiàn)每一條指令。每條指令的詳細描述見 GitHub Repo 中附錄的 PDF 文檔。你需要 照著文檔的描述自己實現(xiàn)這些指令。這項工作做起來其實比聽起來要容易。下面我會拿其中 的兩個作為例子來展示如何實現(xiàn)，其余的見下一章。
5.1 ADD
ADD 指令將兩個數(shù)相加，然后將結果存到一個寄存器中。關于這條指令的描述見 526 頁。ADD 指令的編碼格式如下：
這里給出了兩張圖是因為 ADD 指令有兩種不同的“模式”。在解釋模式之前，先來看看兩張 圖的共同點：
1. 兩者都是以 0001 這 4 個比特開始的，這是 OP_ADD 的操作碼（opcode）
2. 后面 3 個比特名為 DR（destination register），即目的寄存器，相加的結果會放到 這里
3. 再后面 3 個比特是 SR1，這個寄存器存放了第一個將要相加的數(shù)字
至此，我們知道了相加的結果應該存到哪里，以及相加的第一個數(shù)字。只要再知道第二個數(shù) 在哪里就可以執(zhí)行加法操作了。從這里開始，這兩者模式開始不同：注意第 5 比特 ，這個標志位表示的是操作模式是立即模式（immediate mode）還是寄存器模式 （register mode）。在寄存器模式中，第二個數(shù)是存儲在寄存器中的，和第一個數(shù)類似。這個寄存器稱為 SR2，保存在第 0-2 比特中。第 3 和 第 4 比特沒用到。用匯編代碼描 述就是：
ADD R2 R0 R1 ; add the contents of R0 to R1 and store in R2.
在立即模式中，第二個數(shù)直接存儲在指令中，而不是寄存器中。這種模式更加方便，因 為程序不需要額外的指令來將數(shù)據(jù)從內(nèi)存加載到寄存器，直接從指令中就可以拿到這個值。這種方式的限制是存儲的數(shù)很小，不超過 2^5 = 32（無符號）。這種方式很適合對一個值 進行遞增。用匯編描述就是：
ADD R0 R0 1 ; add 1 to R0 and store back in R0
下面一段解釋來自 LC-3 規(guī)范：
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)
這段解釋也就是我們前面討論的內(nèi)容。但什么是 “sign-extending”（有符號擴展）？雖然立即 模式中存儲的值只有 5 比特，但這個值需要加到一個 16 比特的值上。因此，這些 5 比 特的數(shù)需要擴展到 16 比特才能和另一個數(shù)相匹配。對于正數(shù)，我們可以在前面填充 0， 填充之后值是不變的。但是，對于負數(shù)，這樣填充會導致問題。例如， -1 的 5 比特表示 是 11111。如果我們用 0 填充，那填充之后的 0000 0000 0001 1111 等于 32！這種 情況下就需要使用有符號擴展（ sign extension），對于正數(shù)填充 0，對負數(shù)填充 1。
uint16_t?sign_extend(uint16_t?x,?int?bit_count)?{
????if?((x?>>?(bit_count?-?1))?&?1)?{
????????x?|=?(0xFFFF?<????}
????return?x;
}
注：如果你如何用二進制表示負數(shù)感興趣，可以查閱二進制補碼（Two’s Complement） 相關的內(nèi)容。本文中只需要知道怎么進行有符號擴展就行了。
規(guī)范中還有一句：
The condition codes are set, based on whether the result is negative, zero, or positive. (Pg. 526)
前面我們定義的那個條件標記枚舉類型現(xiàn)在要派上用場了。每次有值寫到寄存器時，我們 需要更新這個標記，以標明這個值的符號。為了方便，我們用下面的函數(shù)來實現(xiàn)這個功能：
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;
????}
}
現(xiàn)在我們就可以實現(xiàn) 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);
}
本節(jié)包含了大量信息，這里再總結一下：
ADD 接受兩個值作為參數(shù)，并將計算結果寫到一個寄存器中 在寄存器模式中，第二個值存儲在某個寄存器中 在立即模式中，第二個值存儲在指令最右邊的 5 個比特中 短于 16 比特的值需要執(zhí)行有符號擴展 每次指令修改了寄存器后，都需要更新條件標志位（condition flags）
以上就是 ADD 的實現(xiàn)，你可能會覺得以這樣的方式實現(xiàn)另外 15 個指令將會是一件非常繁 瑣的事情。好消息是，前面的這些函數(shù)基本都是可以重用的，因為另外 15 條指令中，大部 分都會組合有符號擴展、不同的模式和更新條件標記等等。
5.2 LDI
LDI 是 load indirect 的縮寫，用于從內(nèi)存加載一個值到寄存器，規(guī)范見 532 頁。LDI 的二進制格式如下：
與 ADD 相比，LDI 只有一種模式，參數(shù)也更少。LDI 的操作碼是 1010，對應 OP_LDI 枚舉類型。和 ADD 類似，它包含一個 3 比特的 DR（destination register）寄存器，用 于存放加載的值。剩余的比特組成 PCoffset9 字段，這是該指令內(nèi)嵌的一個立即值（ immediate value），和 imm5 類似。由于這個指令是從內(nèi)存加載值，因此我們可以猜測 ，PCoffset9 是一個加載值的內(nèi)存地址。LC-3 規(guī)范提供了更多細節(jié)：
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 比特，但 這次是將擴展之后的值加到當前的程序計數(shù)器 PC（如果回頭去看前面的 while 循 環(huán)，就會發(fā)現(xiàn)這條指令加載之后 PC 就會遞增）。相加得到的結果（也就是 PC 加完之后的 值）表示一個內(nèi)存地址，這個地址中存儲的值表示另一個地址，后者中存儲的是需要加載到 DR 中的值。
這種方式聽上去非常繞，但它確是不可或缺的。LD 指令只能加載 offset 是 9 位的地址， 但整個內(nèi)存是 16 位的。LDI 適用于加載那些遠離當前 PC 的地址內(nèi)的值，但要加載這 些值，需要將這些最終地址存儲在離 PC 較近的位置?？梢詫⑺胂氤?C 中有一個局部變 量，這變量是指向某些數(shù)據(jù)的指針：
//?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 的實現(xiàn)（后面章節(jié)中會介紹 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);
}
后面會看到，這些指令的實現(xiàn)中，大部分輔助功能函數(shù)都是可以復用的。
以上是兩個例子，接下來就可以參考這兩個例子實現(xiàn)其他的指令。注意本文中有兩個指令是 沒有用到的：OP_RTI 和 OP_RES。你可以忽略這兩個指令，如果執(zhí)行到它們直接報錯。將 main() 函數(shù)中未實現(xiàn)的 switch case 補全后，你的虛擬機主體就完成了！
6. 全部指令的參考實現(xiàn)
本節(jié)給出所有指令的實現(xiàn)。如果你自己的實現(xiàn)遇到問題，可以參考這里給出的版本。
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 在規(guī)范中作為一個單獨的指令列出，因為在匯編中它是一個獨立的關鍵字。但是，RET 本質(zhì)上是 JMP 的一個特殊情況。當 R1 為 7 時會執(zhí)行 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]);
}
7. Trap Routines（中斷陷入例程）
LC-3 提供了幾個預定于的函數(shù)（過程），用于執(zhí)行常規(guī)任務以及與 I/O 設備交換， 例如，用于從鍵盤接收輸入的函數(shù)，在控制臺上顯示字符串的函數(shù)。這些都稱為 trap routines，你可以將它們當做操作系統(tǒng)或者是 LC-3 的 API。每個 trap routine 都有一個對應的 trap code（中斷號）。要執(zhí)行一次捕獲， 需要用相應的 trap code 執(zhí)行 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 帶來任何新功能，只是提供了一種方便地執(zhí)行任務的方式（和 C 中的系統(tǒng)函數(shù)類似 ）。在官方 LC-3 模擬器中，trap routines 是用匯編實現(xiàn)的。當調(diào)用到 trap code 時，PC 會移動到 code 對應的地址。CPU 執(zhí)行這個函數(shù)（ procedure）的指令流，函數(shù)結束后 PC 重置到 trap 調(diào)用之前的位置。
注：這就是為什么程序從 0x3000 而不是 0x0 開始的原因。低地址空間是特意留出來 給 trap routine 用的。
規(guī)范只定義了 trap routine 的行為，并沒有規(guī)定應該如何實現(xiàn)。在我們這個虛擬機中， 將會用 C 實現(xiàn)。當觸發(fā)某個 trap code 時，會調(diào)用一個相應的 C 函數(shù)。這個函數(shù)執(zhí)行 完成后，執(zhí)行過程會返回到原來的指令流。
雖然 trap routine 可以用匯編實現(xiàn)，而且物理的 LC-3 計算機也確實是這樣做的，但對虛 擬機來說并不是非常合適。相比于實現(xiàn)自己的 primitive I/O routines，我們可以利用操 作系統(tǒng)上已有的。這樣可以使我們的虛擬機運行更良好，還簡化了代碼，提供了一個便于移 植的高層抽象。
注：從鍵盤獲取輸入就是一個例子。匯編版本使用一個循環(huán)來持續(xù)檢查鍵盤有沒有輸入 ，這會消耗大量 CPU 而實際上沒做多少事情！使用操作系統(tǒng)提供的某個合適的輸入函 數(shù)的話，程序可以在收到輸入之前一直 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;
}
和前面幾節(jié)類似，我會拿一個 trap routine 作為例子展示如何實現(xiàn)，其他的留給讀者自己 完成。
7.1 PUTS
PUT trap code 用于輸出一個以空字符結尾的字符串（和 C 中的 printf 類似）。規(guī) 范見 543 頁。
顯示一個字符串需要將這個字符串的地址放到 R0 寄存器，然后觸發(fā) trap。規(guī)范中說：
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)
意思是說字符串是存儲在一個連續(xù)的內(nèi)存區(qū)域。注意這里和 C 中的字符串有所不同：C 中每個字符占用一個 byte；LC-3 中內(nèi)存尋找是 16 位的，每個字符都是 16 位，占用 兩個 byte。因此要用 C 函數(shù)打印這些字符，需要將每個值先轉換成 char 類型再輸出：
{
????/*?one?char?per?word?*/
????uint16_t*?c?=?memory?+?reg[R_R0];
????while?(*c)?{
????????putc((char)*c,?stdout);
????????++c;
????}
????fflush(stdout);
}
這就是 PUTS trap routine 的實現(xiàn)了。如果熟悉 C 的話，這個函數(shù)應該很容易理解。現(xiàn) 在你可以按照 LC-3 規(guī)范，自己動手實現(xiàn)其他的 trap routine 了。
8. Trap Routine 參考實現(xiàn)
本節(jié)給出所有 trap routine 的一份參考實現(xiàn)。
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 暫停程序執(zhí)行（Halt Program）
puts("HALT");
fflush(stdout);
running?=?0;
9. 加載程序
前面提到了從內(nèi)存加載和執(zhí)行指令，但指令是如何進入內(nèi)存的呢？將匯編程序轉換為 機器碼時，得到的是一個文件，其中包含一個指令流和相應的數(shù)據(jù)。只需要將這個文件的內(nèi) 容復制到內(nèi)存就算完成加載了。
程序的前 16 比特規(guī)定了這個程序在內(nèi)存中的起始地址，這個地址稱為 origin。因此 加載時應該首先讀取這 16 比特，確定起始地址，然后才能依次讀取和放置后面的指令及數(shù) 據(jù)。
下面是將 LC-3 程序讀到內(nèi)存的代碼：
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 比特之后，對這個值執(zhí)行了 swap16()。這是因為 LC-3 程序是大端 （big-endian），但現(xiàn)在大部分計算機都是小端的（little-endian），因此需要做大小端 轉換。如果你是在某些特殊的機器 （例如 PPC）上運行，那就不 需要這些轉換了。
uint16_t?swap16(uint16_t?x)?{
????return?(x?<8)?|?(x?>>?8);
}
注：大小端（Endianness）是指對于 一個整型數(shù)據(jù)，它的每個字節(jié)應該如何解釋。在小端中，第一個字節(jié)是最低位，而在大端 中剛好相反，第一個字節(jié)是最高位。據(jù)我所知，這個順序完全是人為規(guī)定的。不同的公司 做出的抉擇不同，因此我們這些后來人只能針對大小端做一些特殊處理。要理解本文中大 小端相關的內(nèi)容，知道這些就足夠了。
我們再封裝一下前面加載程序的函數(shù)，接受一個文件路徑字符串作為參數(shù)，這樣更加方便：
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;
}
10. 內(nèi)存映射寄存器（Memory Mapped Registers）
某些特殊類型的寄存器是無法從常規(guī)寄存器表（register table）中訪問的。因此，在內(nèi) 存中為這些寄存器預留了特殊的地址。要讀寫這些寄存器，只需要讀寫相應的內(nèi)存地址。這些稱為 內(nèi)存映射寄存器（MMR）。內(nèi)存映射寄存器通常用于處理與特殊硬件的交互。
LC-3 有兩個內(nèi)存映射寄存器需要實現(xiàn)，分別是：
KBSR：鍵盤狀態(tài)寄存器（keyboard status register），表示是否有鍵按下 KBDR：鍵盤數(shù)據(jù)寄存器（keyboard data register），表示哪個鍵按下了 雖然可以用 GETC 來請求鍵盤輸入，但這個 trap routine 會阻塞執(zhí)行，知道從鍵盤獲得 了輸入。KBSR 和 KBDR 使得我們可以輪詢設備的狀態(tài)然后繼續(xù)執(zhí) 行，因此程序不會阻塞。
enum?{
????MR_KBSR?=?0xFE00,?/*?keyboard?status?*/
????MR_KBDR?=?0xFE02??/*?keyboard?data?*/
};
內(nèi)存映射寄存器使內(nèi)存訪問稍微復雜了一些。這種情況下不能直接讀寫內(nèi)存位置，而要使 用 setter 和 getter 輔助函數(shù)。當獲取輸入時，getter 會檢查鍵盤輸入并更新兩 個寄存器（也就是相應的內(nèi)存位置）。
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];
}
這就是我們的虛擬機的最后一部分了！只要你實現(xiàn)了前面提到的 trap routine 和指令，你 的虛擬機就即將能夠運行了！
11. 平臺相關的細節(jié)
本節(jié)包含一些與鍵盤交互以及顯示相關的代碼。如果不感興趣可以直接復制粘貼。
如果不是在 Unix 類系統(tǒng)上運行本程序，例如 Windows，那本節(jié)內(nèi)容需要替換為相應的平臺 實現(xiàn)。
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();
12. 運行虛擬機
現(xiàn)在你可以編譯和運行這個 LC-3 虛擬機了！
使用你喜歡的 C 編譯器編譯這個虛擬機（ https://arthurchiao.art/assets/img/write-your-own-virtual-machine-zh/lc3-vm.c ），然后下載匯 編之后的兩個小游戲：
2048?下載: https://arthurchiao.art/assets/img/write-your-own-virtual-machine-zh/2048.obj Rogue?下載: https://justinmeiners.github.io/lc3-vm/supplies/rogue.obj
用如下命令執(zhí)行：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 |
| |
| |
| |
+--------------------------+
調(diào)試
如果程序不能正常工作，那可能是你的實現(xiàn)有問題。調(diào)試程序就有點麻煩了。我建議通讀 LC-3 程序的匯編源代碼，然后使用一個調(diào)試器單步執(zhí)行虛擬機指令，確保虛擬機執(zhí)行到 的指令是符合預期的。如果發(fā)現(xiàn)了不符合預期的行為，就需要重新查看 LC-3 規(guī)范，確認你 的實現(xiàn)是否有問題。
13. C++ 實現(xiàn)（可選）
使用 C++ 會使代碼更簡短。本節(jié)介紹 C++ 的一些實現(xiàn)技巧。
C++ 有強大的編譯時泛型（compile-time generics）機制，可以幫我們自動生成部分指令 的實現(xiàn)代碼。這里的基本思想是重用每個指令的公共部分。例如，好幾條指令都用到了間接 尋址或有符號擴展然后加到當前寄存器的功能。模板如下：
{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?<????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++ 實現(xiàn)見:
https://justinmeiners.github.io/lc3-vm/src/lc3-alt.cpp