這篇文章主要介紹了用C語(yǔ)言來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的虛擬機(jī),其中棧數(shù)組的部分非常值得學(xué)習(xí),需要的朋友可以參考下

必要的準(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è)淼姆椒▎?

更深入了解一些編程語(yǔ)言是如何工作。例如，當(dāng)下多種經(jīng)常使用那些語(yǔ)言的虛擬機(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í)的如位移寄存器等，希望在讀過(guò)這篇文章后掌握這些。

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

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

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

這就是我們的指令集，注意，POP 指令將會(huì)打印我們彈出的指令，這樣我們就能夠看到 ADD 指令工作了。我還加入了一個(gè) SET 指令，主要是讓你理解寄存器是可以訪問(wèn)和寫入的。你也可以自己實(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è)文件夾來(lái)放置我們的項(xiàng)目，我喜歡將我的項(xiàng)目放置于~/Dev：

1. $cd ~/Dev/ 
2. mkdir mac 
3. cd mac 
4. mkdir src 

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

Makefile

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

1. SRC_FILES = main.c 
2. CC_FLAGS = -Wall -Wextra -g -std=c11 
3. CC = clang 
4.  
5. all: 
6. ${CC} ${SRC_FILES} ${CC_FLAGS} -o mac 

這對(duì)目前來(lái)說(shuō)已經(jīng)足夠了，你以后還可以改進(jìn)它，但是只要它能完成這個(gè)工作，我們應(yīng)該滿足了。

指令編程（代碼）

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

我們可以只寫一個(gè)指令文件，例如 PSH, 5 是0, 5，但是這樣并不易讀，所以我們使用枚舉器!

1. typedef enum { 
2. PSH, 
3. ADD, 
4. POP, 
5. SET, 
6. HLT 
7. } InstructionSet; 

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

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

1. const int program[] = { 
2. PSH, 5, 
3. PSH, 6, 
4. ADD, 
5. POP, 
6. HLT 
7. }; 

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

很好，這樣我們有了自己的程序。現(xiàn)在我們實(shí)現(xiàn)了虛擬機(jī)的讀取，解碼，求值的模式。但是要記住，我們沒有解碼任何東西，因?yàn)槲覀兘o出的是原始指令。也就是說(shuō)我們只需要關(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ù)器，一般來(lái)說(shuō)叫做程序計(jì)數(shù)器，指令指針等等，這些名字是一個(gè)意思取決于你的個(gè)人喜好。在虛擬機(jī)的代碼庫(kù)里，IP 或 PC 這樣的簡(jiǎn)寫形式也隨處可見。

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

1. int ip = 0; 

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

[假設(shè)ip為0]

1. int ip = 0; 
2.  
3. int main() { 
4. int instr = program[ip]; 
5. return 0; 

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

1. int fetch() { 
2. return program[ip]; 
3. } 

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

1. int main() { 
2. int x = fetch(); // PSH 
3. ip++; // increment instruction pointer 
4. int y = fetch(); // 5 
5. } 

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

1. // INCLUDE <stdbool.h>! 
2. bool running = true; 
3.  
4. int main() { 
5. while (running) { 
6. int x = fetch(); 
7. if (x == HLT) running = false; 
8. ip++; 
9. } 
10. } 

這工作的很好，但是有點(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ù)來(lái)判斷。我們?cè)诤瘮?shù)中不會(huì)使用任何指令指針遞增除非我們想操作數(shù)浪費(fèi)操作數(shù)。

1. void eval(int instr) { 
2. switch (instr) { 
3. case HLT: 
4. running = false; 
5. break; 
6. } 
7. } 

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

1. bool running = true; 
2. int ip = 0; 
3.  
4. // instruction enum here 
5.  
6. // eval function here 
7.  
8. // fetch function here 
9.  
10. int main() { 
11. while (running) { 
12. eval(fetch()); 
13. ip++; // increment the ip every iteration 
14. } 
15. } 

棧！

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

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

1. [] // empty 
2.  
3. PSH 5 // put 5 on **top** of the stack 
4. [5] 
5.  
6. PSH 6 
7. [5, 6] 
8.  
9. POP 
10. [5] 
11.  
12. POP 
13. [] // empty 
14.  
15. PSH 6 
16. [6] 
17.  
18. PSH 5 
19. [6, 5] 

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

1. PSH, 5, 
2. PSH, 6, 
3. ADD, 
4. POP, 
5. HLT 

我們首先把5壓入了棧

1. [5] 

然后壓入6：

1. [5, 6] 

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

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

那么我們的棧指針在哪起作用呢?棧指針(或者說(shuō)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)在我們從棧上出棧一次，我們僅需要減小棧頂指針。比如我們接下來(lái)把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語(yǔ)言實(shí)現(xiàn)它。很簡(jiǎn)單，和ip一樣，我們也應(yīng)該定義一個(gè)sp變量，記得把它賦為-1!再定義一個(gè)名為stack的數(shù)組，代碼如下：

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

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

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

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

1. void eval(int instr) { 
2. switch (instr) { 
3. case HLT: { 
4. running = false; 
5. break; 
6. } 
7. case PSH: { 
8. sp++; 
9. stack[sp] = program[++ip]; 
10. break; 
11. } 
12. } 
13. } 

現(xiàn)在你看到，它和我們之前實(shí)現(xiàn)的eval()函數(shù)有一些不同。首先，我們把每個(gè)case語(yǔ)句塊放到大括號(hào)里。你可能不太了解這種用法，它可以讓你在每條case的作用域里定義變量。雖然現(xiàn)在不需要定義變量，但將來(lái)會(huì)用到。并且它可以很容易得讓所有的case語(yǔ)句塊保持一致的風(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。我們可以通過(guò)增加指令指針(譯者注：一般也叫做程序計(jì)數(shù)器)ip來(lái)獲取操作數(shù)。當(dāng)ip為0時(shí)，這意味著執(zhí)行到了PSH指令，接下來(lái)我們希望取得下一條指令——即壓棧的數(shù)值。這可以通過(guò)ip自增的方法實(shí)現(xiàn)(注意：增加ip的位置十分重要，我們希望在取得指令前自增，否則我們只是拿到了PSH指令)，接下來(lái)需要跳到下一條指令否則會(huì)引發(fā)奇怪的錯(cuò)誤。當(dāng)然我們也可以把sp++簡(jiǎn)化到stack[++sp]里。

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

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

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

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

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

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

寄存器

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

1. typedef enum { 
2. A, B, C, D, E, F, 
3. NUM_OF_REGISTERS 
4. } Registers; 

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

1. int registers[NUM_OF_REGISTERS]; 

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

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

修訂

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

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

1. typedef enum { 
2. A, B, C, D, E, F, PC, SP, 
3. NUM_OF_REGISTERS 
4. } Registers; 

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

1. #define sp (registers[SP]) 
2. #define ip (registers[IP]) 

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

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