必要的準(zhǔn)備工作及注意事項(xiàng)：

在開始之前需要做以下工作：

•     一個(gè)C編譯器——我使用了 clang 3.4，也可以用其它支持 c99/c11 的編譯器；
•     文本編輯器——我建議使用基于IDE的文本編輯器，我使用 Emacs;
•     基礎(chǔ)編程知識(shí)——最基本的變量，流程控制，函數(shù)，數(shù)據(jù)結(jié)構(gòu)等；
•     Make 腳本——能使程序更快一點(diǎn)。

為什么要寫個(gè)虛擬機(jī)？

有以下原因：

•     想深入了解計(jì)算機(jī)工作原理。本文將幫助你了解計(jì)算機(jī)底層如何工作，虛擬機(jī)提供簡(jiǎn)潔的抽象層，這不就是一個(gè)最好的學(xué)習(xí)它們?cè)淼姆椒▎幔?/li>
•     更深入了解一些編程語言是如何工作。例如，當(dāng)下多種經(jīng)常使用那些語言的虛擬機(jī)。包括JVM，Lua VM，F(xiàn)aceBook 的 Hip—Hop VM（PHP/Hack） 等。
•     只是因?yàn)橛信d趣學(xué)習(xí)虛擬機(jī)。

指令集

我們將要實(shí)現(xiàn)一種非常簡(jiǎn)單的自定義的指令集。我不會(huì)講一些高級(jí)的如位移寄存器等，希望在讀過這篇文章后掌握這些。

我們的虛擬機(jī)具有一組寄存器，A,B,C,D,E, 和F。這些是通用寄存器，也就是說，它們可以用于存儲(chǔ)任何東西。一個(gè)程序?qū)?huì)是一個(gè)只讀指令序列。這個(gè)虛擬機(jī)是一個(gè)基于堆棧的虛擬機(jī)，也就是說它有一個(gè)可以讓我們壓入和彈出值的堆棧，同時(shí)還有少量可用的寄存器。這要比實(shí)現(xiàn)一個(gè)基于寄存器的虛擬機(jī)簡(jiǎn)單的多。

言歸正傳，下面是我們將要實(shí)現(xiàn)的指令集：
 

PSH 5    ; pushes 5 to the stack
PSH 10   ; pushes 10 to the stack
ADD     ; pops two values on top of the stack, adds them pushes to stack
POP     ; pops the value on the stack, will also print it for debugging
SET A 0   ; sets register A to 0
HLT     ; stop the program

這就是我們的指令集，注意，POP 指令將會(huì)打印我們彈出的指令，這樣我們就能夠看到 ADD 指令工作了。我還加入了一個(gè) SET 指令，主要是讓你理解寄存器是可以訪問和寫入的。你也可以自己實(shí)現(xiàn)像MOV A B（將A的值移動(dòng)到B）這樣的指令。HTL 指令是為了告訴我們程序已經(jīng)運(yùn)行結(jié)束。

虛擬機(jī)是如何工作的呢？

現(xiàn)在我們已經(jīng)到了本文最關(guān)鍵的部分，虛擬機(jī)比你想象的簡(jiǎn)單，它們遵循一個(gè)簡(jiǎn)單的模式：讀??；解碼；執(zhí)行。首先，我們從指令集合或代碼中讀取下一條指令，然后將指令解碼并執(zhí)行解碼后的指令。為簡(jiǎn)單起見，我們忽略了虛擬機(jī)的編碼部分，典型的虛擬機(jī)將會(huì)把一個(gè)指令（操作碼和它的操作數(shù)）打包成一個(gè)數(shù)字，然后再解碼這個(gè)指令。
項(xiàng)目結(jié)構(gòu)

開始編程之前，我們需要設(shè)置好我們的項(xiàng)目。第一，你需要一個(gè)C編譯器（我使用 clang 3.4）。還需要一個(gè)文件夾來放置我們的項(xiàng)目，我喜歡將我的項(xiàng)目放置于~/Dev：
 

$cd ~/Dev/
mkdir mac
cd mac
mkdir src

如上，我們先 cd 進(jìn)入~/Dev 目錄，或者任何你想放置的位置，然后新建一個(gè)目錄（我稱這個(gè)虛擬機(jī)為"mac"）。然后再 cd 進(jìn)這個(gè)目錄并新建我們 src 目錄，這個(gè)目錄用于放置代碼。

Makefile

makefile 相對(duì)直接，我們不需要將什么東西分成多個(gè)文件，也不用包含任何東西，所以我們只需要用一些標(biāo)志來編譯文件：
 

SRC_FILES = main.c
CC_FLAGS = -Wall -Wextra -g -std=c11
CC = clang
 
all:
  ${CC} ${SRC_FILES} ${CC_FLAGS} -o mac

這對(duì)目前來說已經(jīng)足夠了，你以后還可以改進(jìn)它，但是只要它能完成這個(gè)工作，我們應(yīng)該滿足了。
指令編程（代碼）

現(xiàn)在開始寫虛擬機(jī)的代碼了。第一，我們需要定義程序的指令。為此，我們可以使用一個(gè)枚舉類型enum，因?yàn)槲覀兊闹噶罨旧鲜菑?到X的數(shù)字。事實(shí)上，可以說你是在組裝一個(gè)匯編文件，它會(huì)使用像 mov 這樣的詞，然后翻譯成聲明的指令。
我們可以只寫一個(gè)指令文件，例如 PSH, 5 是0, 5，但是這樣并不易讀，所以我們使用枚舉器！
 

typedef enum {
  PSH,
  ADD,
  POP,
  SET,
  HLT
} InstructionSet;

現(xiàn)在我們可以將一個(gè)測(cè)試程序存儲(chǔ)為一個(gè)數(shù)組。我們寫一個(gè)簡(jiǎn)單的程序用于測(cè)試：將5和6相加，然后將他們打印出來（用POP指令）。如果你愿意，你可以定義一個(gè)指令將棧頂?shù)闹荡蛴〕鰜怼?/p>

指令應(yīng)該存儲(chǔ)成一個(gè)數(shù)組，我將在文檔的頂部定義它；但你或許會(huì)將它放在一個(gè)頭文件中，下面是我們的測(cè)試程序：
 

const int program[] = {
  PSH, 5,
  PSH, 6,
  ADD,
  POP,
  HLT
};

上面的程序?qū)?huì)把5和6壓入棧，調(diào)用 ADD 指令，這將會(huì)把棧頂?shù)膬蓚€(gè)值彈出，相加后將結(jié)果壓回棧中，接下來我們彈出結(jié)果，因?yàn)?POP 指令將會(huì)打印這個(gè)值，但是你不必自己再做了，我已經(jīng)做好并測(cè)試過了。最后，HLT 指令結(jié)束程序。

很好，這樣我們有了自己的程序?，F(xiàn)在我們實(shí)現(xiàn)了虛擬機(jī)的讀取，解碼，求值的模式。但是要記住，我們沒有解碼任何東西，因?yàn)槲覀兘o出的是原始指令。也就是說我們只需要關(guān)注讀取和求值！我們可以將它們簡(jiǎn)化成兩個(gè)函數(shù) fetch 和 evaluate。

取得當(dāng)前指令

因?yàn)槲覀円呀?jīng)將我們的程序存成了一個(gè)數(shù)組，所以很簡(jiǎn)單的就可以取得當(dāng)前指令。一個(gè)虛擬機(jī)有一個(gè)計(jì)數(shù)器，一般來說叫做程序計(jì)數(shù)器，指令指針等等，這些名字是一個(gè)意思取決于你的個(gè)人喜好。在虛擬機(jī)的代碼庫里，IP 或 PC 這樣的簡(jiǎn)寫形式也隨處可見。

如果你之前有記得，我說過我們要把程序計(jì)數(shù)器以寄存器的形式存儲(chǔ)...我們將那么做——在以后。現(xiàn)在，我們只是在我們代碼的最頂端創(chuàng)建一個(gè)叫 ip 的變量，并且設(shè)置為 0。
 

int ip = 0;

ip 變量代表指令指針。因?yàn)槲覀円呀?jīng)將程序存成了一個(gè)數(shù)組，所以使用 ip 變量去指明程序數(shù)組中當(dāng)前索引。例如，如果創(chuàng)建了一個(gè)被賦值了程序 ip 索引的變量 x，它將存儲(chǔ)我們程序的第一條指令。

[假設(shè)ip為0]
 

int ip = 0;
 
int main() {
  int instr = program[ip];
  return 0;

如果我們打印變量 instr，本來應(yīng)是 PSH 的它將顯示為0，因?yàn)樵谒俏覀兠杜e里的第一個(gè)值。我們也可以寫一個(gè)取回函數(shù)像這樣：
 

int fetch() {
  return program[ip];
}

這個(gè)函數(shù)將會(huì)返回當(dāng)前被調(diào)用指令。太棒了，那么如果我們想要下一條指令呢？很容易，我們只要增加指令指針就好了：
 

int main() {
  int x = fetch(); // PSH
  ip++; // increment instruction pointer
  int y = fetch(); // 5
}

那么怎樣讓它自己動(dòng)起來呢？我們知道一個(gè)程序直到它執(zhí)行 HLT 指令才會(huì)停止。因此我們使用一個(gè)無限的循環(huán)持續(xù)直到當(dāng)前指令為HLT。
 

// INCLUDE <stdbool.h>!
bool running = true;
 
int main() {
  while (running) {
    int x = fetch();
    if (x == HLT) running = false;
    ip++;
  }
}

這工作的很好，但是有點(diǎn)凌亂。我們正在循環(huán)每一條指令，檢查是否 HLT，如果是就停止循環(huán)，否則“吃掉”指令接著循環(huán)。

判斷一條指令

因此這就是我們虛擬機(jī)的主體，然而我們想要確實(shí)的評(píng)判每一條指令，并且使它更簡(jiǎn)潔一些。好的，這個(gè)簡(jiǎn)單的虛擬機(jī)，你可以寫一個(gè)“巨大”的 switch 聲明。讓 switch 中的每一個(gè) case 對(duì)應(yīng)一條我們定義在枚舉中的指令。這個(gè) eval 函數(shù)將使用一個(gè)簡(jiǎn)單的指令的參數(shù)來判斷。我們?cè)诤瘮?shù)中不會(huì)使用任何指令指針遞增除非我們想操作數(shù)浪費(fèi)操作數(shù)。
 

void eval(int instr) {
  switch (instr) {
    case HLT:
      running = false;
      break;
  }
}

因此如果我們?cè)诨氐街骱瘮?shù)，就可以像這樣使用我們的 eval 函數(shù)工作：
 

bool running = true;
int ip = 0;
 
// instruction enum here
 
// eval function here
 
// fetch function here
 
int main() {
  while (running) {
    eval(fetch());
    ip++; // increment the ip every iteration
  }
}

棧！

很好，那會(huì)很完美的完成這個(gè)工作?，F(xiàn)在，在我們加入其他指令之前，我們需要一個(gè)棧。幸運(yùn)的是，棧是很容易實(shí)現(xiàn)的，我們僅僅需要使用一個(gè)數(shù)組而已。數(shù)組會(huì)被設(shè)置為合適的大小，這樣它就能包含256個(gè)值了。我們也需要一個(gè)棧指針（常被縮寫為sp）。這個(gè)指針會(huì)指向棧數(shù)組。

為了讓我們對(duì)它有一個(gè)更加形象化的印象，讓我們來看看這個(gè)用數(shù)組實(shí)現(xiàn)的棧吧：
 

[] // empty
 
PSH 5 // put 5 on **top** of the stack
[5]
 
PSH 6
[5, 6]
 
POP
[5]
 
POP
[] // empty
 
PSH 6
[6]
 
PSH 5
[6, 5]

那么，在我們的程序里發(fā)生了什么呢？
 

PSH, 5,
PSH, 6,
ADD,
POP,
HLT

我們首先把5壓入了棧

 [5]

然后壓入6：
 

[5, 6]

接著添加指令，取出這些值，把它們加在一起并把結(jié)果壓入棧中：
 

[5, 6]
 
// pop the top value, store it in a variable called a
a = pop; // a contains 6
[5] // stack contents
 
// pop the top value, store it in a variable called b
b = pop; // b contains 5
[] // stack contents
 
// now we add b and a. Note we do it backwards, in addition
// this doesn't matter, but in other potential instructions
// for instance divide 5 / 6 is not the same as 6 / 5
result = b + a;
push result // push the result to the stack
[11] // stack contents

那么我們的棧指針在哪起作用呢？棧指針（或者說sp）一般是被設(shè)置為-1，這意味著這個(gè)指針是空的。請(qǐng)記住一個(gè)數(shù)組是從0開始的，如果沒有初始化sp的值，那么他會(huì)被設(shè)置為C編譯器放在那的一個(gè)隨機(jī)值。

如果我們將3個(gè)值壓棧，那么sp將變成2。所以這個(gè)數(shù)組保存了三個(gè)值：
 
sp指向這里（sp = 2）
       |
       V
[1, 5, 9]
 0  1  2 <- 數(shù)組下標(biāo)

現(xiàn)在我們從棧上出棧一次，我們僅需要減小棧頂指針。比如我們接下來把9出棧，那么棧頂將變?yōu)?：
 
sp指向這里（sp = 1）
    |
    V
[1, 5]
 0  1 <- 數(shù)組下標(biāo)

所以，當(dāng)我們想知道棧頂內(nèi)容的時(shí)候，只需要查看sp的當(dāng)前值。OK，你可能想知道棧是如何工作的，現(xiàn)在我們用C語言實(shí)現(xiàn)它。很簡(jiǎn)單，和ip一樣，我們也應(yīng)該定義一個(gè)sp變量，記得把它賦為-1！再定義一個(gè)名為stack的數(shù)組，代碼如下：
 

int ip = 0;
int sp = -1;
int stack[256]; // 用數(shù)組或適合此處的其它結(jié)構(gòu)
 
// 其它C代碼

現(xiàn)在如果我們想入棧一個(gè)值，我們先增加棧頂指針，接著設(shè)置當(dāng)前sp處的值（我們剛剛增加的）。注意：這兩步的順序很重要！
 

// 壓棧5
 
// sp = -1
sp++; // sp = 0
stack[sp] = 5; // 棧頂現(xiàn)在變?yōu)?

所以，在我們的執(zhí)行函數(shù)eval()里，可以像這樣實(shí)現(xiàn)push出棧指令：
 

void eval(int instr) {
  switch (instr) {
    case HLT: {
      running = false;
      break;
    }
    case PSH: {
      sp++;
      stack[sp] = program[++ip];
      break;
    }
  }
}

現(xiàn)在你看到，它和我們之前實(shí)現(xiàn)的eval()函數(shù)有一些不同。首先，我們把每個(gè)case語句塊放到大括號(hào)里。你可能不太了解這種用法，它可以讓你在每條case的作用域里定義變量。雖然現(xiàn)在不需要定義變量，但將來會(huì)用到。并且它可以很容易得讓所有的case語句塊保持一致的風(fēng)格。

其次是神奇的表達(dá)式program[++ip]。它做了什么？呃，我們的程序存儲(chǔ)在一個(gè)數(shù)組里，PSH指令需要獲得一個(gè)操作數(shù)。操作數(shù)本質(zhì)是一個(gè)參數(shù)，就像當(dāng)你調(diào)用一個(gè)函數(shù)時(shí)，你可以給它傳遞一個(gè)參數(shù)。這種情況我們稱作壓棧數(shù)值5。我們可以通過增加指令指針（譯者注：一般也叫做程序計(jì)數(shù)器）ip來獲取操作數(shù)。當(dāng)ip為0時(shí)，這意味著執(zhí)行到了PSH指令，接下來我們希望取得下一條指令——即壓棧的數(shù)值。這可以通過ip自增的方法實(shí)現(xiàn)（注意：增加ip的位置十分重要，我們希望在取得指令前自增，否則我們只是拿到了PSH指令），接下來需要跳到下一條指令否則會(huì)引發(fā)奇怪的錯(cuò)誤。當(dāng)然我們也可以把sp++簡(jiǎn)化到stack[++sp]里。

對(duì)于POP指令，實(shí)現(xiàn)非常簡(jiǎn)單。只需要減小棧頂指針，但是我一般希望能夠在出棧的時(shí)候打印出棧值。

我省略了實(shí)現(xiàn)其它指令的代碼和swtich語句，僅列出POP指令的實(shí)現(xiàn)：

// 記得#include <stdio.h>!
 
case POP: {
  int val_popped = stack[sp--];
  printf("popped %d\n", val_popped);
  break;
}

現(xiàn)在，POP指令能夠工作了！我們剛剛做的只是把棧頂放到變量val_popped里，接著棧頂指針減一。如果我們首先棧頂減一，那么將得到一些無效值，因?yàn)閟p可能取值為0，那么我們可能把stack[-1]賦給val_popped，通常這不是一個(gè)好主意。

最后是ADD指令。這條指令可能要花費(fèi)你一些腦細(xì)胞，同時(shí)這也是我們需要用大括號(hào){}實(shí)現(xiàn)case語句內(nèi)作用域的原因。
 

case ADD: {
  // 首先我們出棧，把數(shù)值存入變量a
  int a = stack[sp--];
 
  // 接著我們出棧，把數(shù)值存入變量b
 
  // 接著兩個(gè)變量相加，再把結(jié)果入棧
  int result = a + b;
  sp++; // 棧頂加1 **放在賦值之前**
  stack[sp] = result; // 設(shè)置棧頂值
 
  // 完成！
  break;
}

寄存器

寄存器是虛擬機(jī)中的選配件，很容易實(shí)現(xiàn)。之前提到過我們可能需要六個(gè)寄存器：A，B，C，D，E和F。和實(shí)現(xiàn)指令集一樣，我們也用一個(gè)枚舉來實(shí)現(xiàn)它們。
 

typedef enum {
  A, B, C, D, E, F,
  NUM_OF_REGISTERS
} Registers;

小技巧：枚舉的最后放置了一個(gè)數(shù) NUM_OF_REGISTERS。通過這個(gè)數(shù)可以獲取寄存器的個(gè)數(shù)，即便你又添加了其它的寄存器?，F(xiàn)在我們需要一個(gè)數(shù)組為寄存器存放數(shù)值：

int registers[NUM_OF_REGISTERS];

接下來你可以讀取寄存器內(nèi)的值：
 

printf("%d\n", registers[A]); // 打印寄存器A的值

修訂

我沒有在寄存器花太多心思，但你應(yīng)該能夠?qū)懗鲆恍┎僮骷拇嫫鞯闹噶睢１热?，如果你想?shí)現(xiàn)任何分支跳轉(zhuǎn)，可以通過把指令指針（譯者注：或叫程序計(jì)數(shù)器）和/或棧頂指針存到寄存器里，或者通過實(shí)現(xiàn)分支指令。

前者實(shí)現(xiàn)起來相對(duì)快捷、簡(jiǎn)單。我們可以這樣做，增加代表IP和SP的寄存器：
 

typedef enum {
  A, B, C, D, E, F, PC, SP,
  NUM_OF_REGISTERS
} Registers;

現(xiàn)在我們需要實(shí)現(xiàn)代碼來使用指令指針和棧頂指針。一個(gè)簡(jiǎn)單的辦法——?jiǎng)h掉上面定義的sp和ip變量，用宏定義實(shí)現(xiàn)它們：

#define sp (registers[SP])
#define ip (registers[IP])  

譯者注：此處應(yīng)同Registers枚舉中保持一致，IP應(yīng)改為PC

這個(gè)修改恰到好處，你不需要重寫很多代碼，同時(shí)它工作的很好。

最新評(píng)論