建站
咨詢
售后
建站咨詢
新聞中心
1. 引言
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名申請、網(wǎng)站空間、營銷軟件、網(wǎng)站建設(shè)、富川網(wǎng)站維護(hù)、網(wǎng)站推廣。
本文將教你編寫一個自己的虛擬機（VM），這個虛擬機能夠運行匯編語言編寫的程序， 例如我朋友編寫的 2048 或者我自己的 Roguelike。如果你會編程，但希望 更深入地了解計算機的內(nèi)部原理以及編程語言是如何工作的，那本文很適合你。從零開始 寫一個虛擬機聽起來可能讓人有點望而生畏，但讀完本文之后你會驚訝于這件事原來如此簡 單，并從中深受啟發(fā)。
本文所說的虛擬機最終由 400 行左右 C 代碼組成。理解這些代碼只需要基本的 C/C++ 知識和二進(jìn)制運算。這個虛擬機可以在 Unix 系統(tǒng)（包括 macOS）上執(zhí)行。代碼中包含少 量平臺相關(guān)的配置終端（terminal）和顯示（display）的代碼，但這些并不是本項目的核 心。（歡迎大家添加對 Windows 的支持。）
注意：這個虛擬機是Literate Programming 的產(chǎn)物。本文會解釋每段代碼的原理，最終的實現(xiàn)就是將這些代碼片段連起來。
什么是虛擬機？
虛擬機就像計算機（computer），它模擬包括 CPU 在內(nèi)的幾個硬件組件，能夠執(zhí)行 算術(shù)運算、讀寫內(nèi)存、與 I/O 設(shè)備交互。最重要的是，它能理解機器語言（machine language），因此可以用相應(yīng)的語言來對它進(jìn)行編程。
一個虛擬機需要模擬哪些硬件要看它的使用場景。有些虛擬機是設(shè)計用來模擬特定類型的計算設(shè)備 的，例如視頻游戲模擬器。現(xiàn)在 NES 已經(jīng)不常見了，但我們還是可以用 NES 硬件模擬器來玩 NES 游戲。這些模擬器必須能忠實地 重建每一個細(xì)節(jié)，以及原硬件的每個主要組件。
另外一些虛擬機則完全是虛構(gòu)的，而非用來模擬硬件。這類虛擬機的主要用途是使軟件開發(fā) 更容易。例如，要開發(fā)一個能運行在不同計算架構(gòu)上的程序，你無需使用每種架構(gòu)特定的匯 編方言來實現(xiàn)一遍自己的程序，而只需要使用一個跨平臺的虛擬機提供的匯編語言。
注：編譯器也解決了類似的跨平臺問題，它將標(biāo)準(zhǔn)的高級語言編寫的程序編譯成能在不同 CPU 架構(gòu)上執(zhí)行的程序。
相比之下，虛擬機的跨平臺方式是自己創(chuàng)建一個標(biāo)準(zhǔn)的 CPU 架 構(gòu)，然后在不同的物理設(shè)備上模擬這個 CPU 架構(gòu)。編譯器方式的優(yōu)點是沒有運行時開銷 （runtime overhead），但實現(xiàn)一個支持多平臺的編譯器是非常困難的，但實現(xiàn)一個虛擬 機就簡單多了。
在實際中，人們會根據(jù)需求的不同混合使用虛擬機和編譯器，因為二者工 作在不同的層次。
Java Virtual Machine (JVM) 就是一個非常成功的例子。JVM 本身是一個中等大小、程序員完全能夠看懂的程序，因此很 容易將它移植到包括手機在內(nèi)的上千種設(shè)備上。只要在設(shè)備上實現(xiàn)了 JVM，接下來任何 Java、Kotlin 或 Clojure 程序都無需任何修改就可以直接運行在這個設(shè)備上。唯一的開銷 來自虛擬機自身以及機器之上的 進(jìn)一步抽象。大部分情況下，這完全是可以接受的。
虛擬機不必很大或者能適應(yīng)各種場景，老式的視頻游戲 經(jīng)常使用很小的虛擬機來提 供簡單的腳本系統(tǒng)（scripting systems）。
虛擬機還適用于在一個安全的或隔離的環(huán)境中執(zhí)行代碼。一個例子就是垃圾回收（GC）。要 在 C 或 C++ 之上實現(xiàn)一個自動垃圾回收機制并不容易 ，因為程序無法看到它自身的?；蜃兞?。但是，虛擬機是在它運行的程序“之外”的，因此它能夠看到棧上所有的內(nèi)存引用 。
另一個例子是以太坊智能合約 （Ethereum smart contracts）。智能合約是在區(qū)塊鏈網(wǎng)絡(luò)中被驗證節(jié)點（validating node）執(zhí)行的小段程序。這就要求 人們在無法提前審查這些由陌生人編寫的代碼的情況下，直接他們的機器上執(zhí)行這些代碼。
為避免合約執(zhí)行一些惡意行為，智能合約將它們放到一個 虛擬機 內(nèi)執(zhí)行，這個虛擬機沒有權(quán)限訪問文件系統(tǒng)、網(wǎng)絡(luò)、磁盤等等資源。以太坊也很好地展現(xiàn)了虛擬機的可移植性特性，因為以太坊節(jié)點可以運行在多種計算機和操作系統(tǒng)上。使用虛擬機 使得智能合約的編寫無需考慮將在什么平臺運行。
2. LC-3 架構(gòu)
我們的虛擬機將會模擬一個虛構(gòu)的稱為 LC-3 的計算機。LC-3 在學(xué)校中比較流行，用于教學(xué)生如何用匯編編程。與 x86 相比 ，LC-3 的指令集更 加簡化，但現(xiàn)代 CPU 的主要思想其中都包括了。
我們首先需要模擬機器最基礎(chǔ)的硬件組件，嘗試來理解每個組件是做什么的，如果 現(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ù)進(jìn)行處理，必須先將數(shù)據(jù)放到某個寄存器中。但 因為寄存器的數(shù)量很少，因此在任意時刻只能有很少的數(shù)據(jù)加載到寄存器。計算機的解決辦 法是：首先將數(shù)據(jù)從內(nèi)存加載到寄存器，然后將計算結(jié)果放到其他寄存器，最后將最終結(jié)果 再寫回內(nèi)存。
LC-3 總共有 10 個寄存器，每個都是 16 比特。其中大部分都是通用目的寄存器，少數(shù)幾 個用于特定目的。
- 8 個通用目的寄存器（R0-R7）
- 1 個程序計數(shù)器（program counter, PC）寄存器
- 1 個條件標(biāo)志位（condition flags，COND）寄存器
通用目的寄存器可以用于執(zhí)行任何程序計算。程序計數(shù)器（PC）是一個無符號整數(shù)，表示內(nèi) 存中將要執(zhí)行的下一條指令的地址。條件標(biāo)記寄存器記錄前一次計算結(jié)果的正負(fù)符號。
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í)行什么任務(wù)，例如將兩個數(shù)相加。一條指令包 含兩部分：
- 操作碼（opcode）：表示任務(wù)的類型
- 執(zhí)行任務(wù)所需的參數(shù)
每個操作碼代表 CPU “知道”的一種任務(wù)。在 LC-3 中只有 16 個操作碼。計算機能夠完成 的所有計算，都是這些簡單指令組成的指令流。每條指令 16 比特長，其中最左邊的 4 個 比特存儲的是操作碼，其余的比特存儲的是參數(shù)。
我們稍后會詳細(xì)介紹每條指令是做什么的，現(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 架構(gòu)有幾百條指令，而其他的架構(gòu)例如 ARM 和 LC-3 只有很少的指令 。較小的指令集稱為精簡指令集（RISC），較大 的指令集稱為復(fù)雜指令集（CISC）。更大 的指令集本質(zhì)上通常并沒有提供新特性，只是使得編寫 匯編更加方便 。一條 CISC 指令能做的事情可能需要好幾條 RISC 才能完成。
但是，對設(shè)計和制造工程 師來說，CISC 更加復(fù)雜和昂貴，設(shè)計和制造業(yè)更貴。包括這一點在內(nèi)的一些權(quán)衡使得指 令設(shè)計也在不斷變化。
2.4 條件標(biāo)志位
R_COND 寄存器存儲條件標(biāo)記，其中記錄了最近一次計算的執(zhí)行結(jié)果。這使得程序可以完成諸如 if (x > 0) { ... } 之類的邏輯條件。
每個 CPU 都有很多條件標(biāo)志位來表示不同的情形。LC-3 只使用 3 個條件標(biāo)記位，用來 表示前一次計算結(jié)果的符號：
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 不同的是， 這里沒有作用域符號 {} 或者控制結(jié)構(gòu)（例如 if 和 while），僅僅是一個扁平的聲 明列表（a flat list of statements）。這樣的程序更容易執(zhí)行。
注意，其中一些聲明中的名字和我們前面的定義的操作碼（opcodes）是一樣的。前面 介紹到，每條指令都是 16 比特，但這里的匯編程序看起來每行的字符數(shù)都是不一樣的。為什么會有這種不一致呢？
這是因為這些匯編聲明都是以人類可讀寫的格式編寫的，以純文本的形式表示。一種稱為 匯編器（assembler）的工具會將這些文本格式的指令轉(zhuǎn)換成 16 比特的二進(jìn)制指令， 后者是虛擬機可以理解的。這種二進(jìn)制格式稱為機器碼（machine code），是虛擬機可以 執(zhí)行的格式，其本質(zhì)上就是一個 16 比特指令組成的數(shù)組。
注：雖然在開發(fā)中編譯器（compiler）和匯編器（assembler）的角色是類似的，但二者 是兩個不同的工具。匯編器只是簡單地將程序員編寫的文本編碼（encode）成二進(jìn)制格式 ，將其中的符號替換成相應(yīng)的二進(jìn)制表示并打包到指令內(nèi)。
.ORIG 和 .STRINGZ 看起來像是指令，但其實不是，它們稱為匯編制導(dǎo)命令 （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í)行，不管這些程 序有多么復(fù)雜。理論上，這樣的虛擬機甚至可以運行一個瀏覽器或者 Linux 這樣的操作系 統(tǒng)。
如果深入地思考這個特性，你就會意識到這是一個在哲學(xué)上非常奇特的現(xiàn)象：程序能完成各種智能的事情，其中一些我們甚至都很難想象；但同時，所有這些程序最終都是用我們編 寫的這些少量指令來執(zhí)行的！我們既了解 —— 又不了解 —— 那些和程序執(zhí)行相關(guān)的的事情。圖靈 曾經(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. 跳轉(zhuǎn)到步驟 1
你可能會有疑問：“如果這個循環(huán)不斷遞增 PC，而我們沒有 if 或 while，那程序不會 很快運行到內(nèi)存外嗎？”答案是不會，我們前面提到過，有類似 goto 的指令會通過修改 PC 來改變執(zhí)行流。微信搜索公眾號：程序員開源社區(qū)，回復(fù)“資源”，獲取更多精品學(xué)習(xí)資料。
下面是以上流程的大致代碼實現(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)每一條指令。每條指令的詳細(xì)描述見 GitHub Repo 中附錄的 PDF 文檔。你需要 照著文檔的描述自己實現(xiàn)這些指令。這項工作做起來其實比聽起來要容易。下面我會拿其中 的兩個作為例子來展示如何實現(xiàn)，其余的見下一章。
5.1 ADD
ADD 指令將兩個數(shù)相加，然后將結(jié)果存到一個寄存器中。關(guān)于這條指令的描述見 526 頁。ADD 指令的編碼格式如下：
這里給出了兩張圖是因為 ADD 指令有兩種不同的“模式”。在解釋模式之前，先來看看兩張 圖的共同點：
- 1. 兩者都是以 0001 這 4 個比特開始的，這是 OP_ADD 的操作碼（opcode）
- 2. 后面 3 個比特名為 DR（destination register），即目的寄存器，相加的結(jié)果會放到 這里
- 3. 再后面 3 個比特是 SR1，這個寄存器存放了第一個將要相加的數(shù)字
至此，我們知道了相加的結(jié)果應(yīng)該存到哪里，以及相加的第一個數(shù)字。只要再知道第二個數(shù) 在哪里就可以執(zhí)行加法操作了。從這里開始，這兩者模式開始不同：注意第 5 比特 ，這個標(biāo)志位表示的是操作模式是立即模式（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（無符號）。這種方式很適合對一個值 進(jìn)行遞增。用匯編描述就是：
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， 填充之后值是不變的。但是，對于負(fù)數(shù)，這樣填充會導(dǎo)致問題。例如， -1 的 5 比特表示 是 11111。如果我們用 0 填充，那填充之后的 0000 0000 0001 1111 等于 32！這種 情況下就需要使用有符號擴展（ sign extension），對于正數(shù)填充 0，對負(fù)數(shù)填充 1。
uint16_t sign_extend(uint16_t x, int bit_count) {
if ((x >> (bit_count - 1)) & 1) {
x |= (0xFFFF << bit_count);
}
return x;
}
注：如果你如何用二進(jìn)制表示負(fù)數(shù)感興趣，可以查閱二進(jìn)制補碼（Two’s Complement） 相關(guān)的內(nèi)容。本文中只需要知道怎么進(jìn)行有符號擴展就行了。
規(guī)范中還有一句：
The condition codes are set, based on whether the result is negative, zero, or positive. (Pg. 526)
前面我們定義的那個條件標(biāo)記枚舉類型現(xiàn)在要派上用場了。每次有值寫到寄存器時，我們 需要更新這個標(biāo)記，以標(biāo)明這個值的符號。為了方便，我們用下面的函數(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é)包含了大量信息，這里再總結(jié)一下：
- ADD 接受兩個值作為參數(shù)，并將計算結(jié)果寫到一個寄存器中
- 在寄存器模式中，第二個值存儲在某個寄存器中
- 在立即模式中，第二個值存儲在指令最右邊的 5 個比特中
- 短于 16 比特的值需要執(zhí)行有符號擴展
- 每次指令修改了寄存器后，都需要更新條件標(biāo)志位（condition flags）
以上就是 ADD 的實現(xiàn)，你可能會覺得以這樣的方式實現(xiàn)另外 15 個指令將會是一件非常繁 瑣的事情。好消息是，前面的這些函數(shù)基本都是可以重用的，因為另外 15 條指令中，大部 分都會組合有符號擴展、不同的模式和更新條件標(biāo)記等等。
5.2 LDI
LDI 是 load indirect 的縮寫，用于從內(nèi)存加載一個值到寄存器，規(guī)范見 532 頁。LDI 的二進(jìn)制格式如下：
與 ADD 相比，LDI 只有一種模式，參數(shù)也更少。LDI 的操作碼是 1010，對應(yīng) OP_LDI 枚舉類型。和 ADD 類似，它包含一個 3 比特的 DR（destination register）寄存器，用 于存放加載的值。剩余的比特組成 PCoffset9 字段，這是該指令內(nèi)嵌的一個立即值（ immediate value），和 imm5 類似。由于這個指令是從內(nèi)存加載值，因此我們可以猜測 ，PCoffset9 是一個加載值的內(nèi)存地址。LC-3 規(guī)范提供了更多細(xì)節(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 比特，但 這次是將擴展之后的值加到當(dāng)前的程序計數(shù)器 PC（如果回頭去看前面的 while 循 環(huán)，就會發(fā)現(xiàn)這條指令加載之后 PC 就會遞增）。相加得到的結(jié)果（也就是 PC 加完之后的 值）表示一個內(nèi)存地址，這個地址中存儲的值表示另一個地址，后者中存儲的是需要加載到 DR 中的值。
這種方式聽上去非常繞，但它確是不可或缺的。LD 指令只能加載 offset 是 9 位的地址， 但整個內(nèi)存是 16 位的。LDI 適用于加載那些遠(yuǎn)離當(dāng)前 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 之后需要更新條件標(biāo)志位：
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));
}
后面會看到，這些指令的實現(xiàn)中，大部分輔助功能函數(shù)都是可以復(fù)用的。
以上是兩個例子，接下來就可以參考這兩個例子實現(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;
}
}
RET 在規(guī)范中作為一個單獨的指令列出，因為在匯編中它是一個獨立的關(guān)鍵字。但是，RET 本質(zhì)上是 JMP 的一個特殊情況。當(dāng) R1 為 7 時會執(zhí)行 RET。
6.5 Jump（跳轉(zhuǎn)）
{
/* Also handles RET */
uint16_t r1 = (instr >> 6) & 0x7;
reg[R_PC] = reg[r1];
}
6.6 Jump Register（跳轉(zhuǎn)寄存器）
{
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 提供了幾個預(yù)定于的函數(shù)（過程），用于執(zhí)行常規(guī)任務(wù)以及與 I/O 設(shè)備交換， 例如，用于從鍵盤接收輸入的函數(shù)，在控制臺上顯示字符串的函數(shù)。這些都稱為 trap routines，你可以將它們當(dāng)做操作系統(tǒng)或者是 LC-3 的 API。每個 trap routine 都有一個對應(yīng)的 trap code（中斷號）。要執(zhí)行一次捕獲， 需要用相應(yīng)的 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í)行任務(wù)的方式（和 C 中的系統(tǒng)函數(shù)類似 ）。在官方 LC-3 模擬器中，trap routines 是用匯編實現(xiàn)的。當(dāng)調(diào)用到 trap code 時，PC 會移動到 code 對應(yīng)的地址。CPU 執(zhí)行這個函數(shù)（ procedure）的指令流，函數(shù)結(jié)束后 PC 重置到 trap 調(diào)用之前的位置。
注：這就是為什么程序從 0x3000 而不是 0x0 開始的原因。低地址空間是特意留出來 給 trap routine 用的。
規(guī)范只定義了 trap routine 的行為，并沒有規(guī)定應(yīng)該如何實現(xiàn)。在我們這個虛擬機中， 將會用 C 實現(xiàn)。當(dāng)觸發(fā)某個 trap code 時，會調(diào)用一個相應(yīng)的 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 用于輸出一個以空字符結(jié)尾的字符串（和 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ù)打印這些字符，需要將每個值先轉(zhuǎn)換成 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ù)應(yīng)該很容易理解?，F(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í)行指令，但指令是如何進(jìn)入內(nèi)存的呢？將匯編程序轉(zhuǎn)換為 機器碼時，得到的是一個文件，其中包含一個指令流和相應(yīng)的數(shù)據(jù)。只需要將這個文件的內(nèi) 容復(fù)制到內(nèi)存就算完成加載了。
程序的前 16 比特規(guī)定了這個程序在內(nèi)存中的起始地址，這個地址稱為 origin。因此 加載時應(yīng)該首先讀取這 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），因此需要做大小端 轉(zhuǎn)換。如果你是在某些特殊的機器 （例如 PPC）上運行，那就不 需要這些轉(zhuǎn)換了。
uint16_t swap16(uint16_t x) {
return (x << 8) | (x >> 8);
}
注：大小端（Endianness）是指對于 一個整型數(shù)據(jù)，它的每個字節(jié)應(yīng)該如何解釋。在小端中，第一個字節(jié)是最低位，而在大端 中剛好相反，第一個字節(jié)是最高位。據(jù)我所知，這個順序完全是人為規(guī)定的。不同的公司 做出的抉擇不同，因此我們這些后來人只能針對大小端做一些特殊處理。要理解本文中大 小端相關(guān)的內(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) 存中為這些寄存器預(yù)留了特殊的地址。要讀寫這些寄存器，只需要讀寫相應(yīng)的內(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 使得我們可以輪詢設(shè)備的狀態(tài)然后繼續(xù)執(zhí) 行，因此程序不會阻塞。
enum {
MR_KBSR = 0xFE00, /* keyboard status */
MR_KBDR = 0xFE02 /* keyboard data */
};
內(nèi)存映射寄存器使內(nèi)存訪問稍微復(fù)雜了一些。這種情況下不能直接讀寫內(nèi)存位置，而要使 用 setter 和 getter 輔助函數(shù)。當(dāng)獲取輸入時，getter 會檢查鍵盤輸入并更新兩 個寄存器（也就是相應(yīng)的內(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. 平臺相關(guān)的細(xì)節(jié)
本節(jié)包含一些與鍵盤交互以及顯示相關(guān)的代碼。如果不感興趣可以直接復(fù)制粘貼。
如果不是在 Unix 類系統(tǒng)上運行本程序，例如 Windows，那本節(jié)內(nèi)容需要替換為相應(yīng)的平臺 實現(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 的設(shè)置終端輸入的代碼：
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);
}
當(dāng)程序被中斷時，我們需要將終端的設(shè)置恢復(fù)到默認(rèn)：
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í)行到 的指令是符合預(yù)期的。如果發(fā)現(xiàn)了不符合預(yù)期的行為，就需要重新查看 LC-3 規(guī)范，確認(rèn)你 的實現(xiàn)是否有問題。
13. C++ 實現(xiàn)（可選）
使用 C++ 會使代碼更簡短。本節(jié)介紹 C++ 的一些實現(xiàn)技巧。
C++ 有強大的編譯時泛型（compile-time generics）機制，可以幫我們自動生成部分指令 的實現(xiàn)代碼。這里的基本思想是重用每個指令的公共部分。例如，好幾條指令都用到了間接 尋址或有符號擴展然后加到當(dāng)前寄存器的功能。模板如下：
{Instruction C++ 14}
template
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 學(xué)來的。如果你對仿真或 NES 感興趣，強烈建議觀看他的視頻。
網(wǎng)站名稱：400行C代碼實現(xiàn)一個虛擬機
URL分享：http://m.fisionsoft.com.cn/article/dhsoosd.html
