Implementing a virtual machine in C(虚拟机C语言实现)
介绍
Github上展示了我们将要做的东西，你可以对比项目中的代码以防你遇到任何错误GitHub Repository
这是一篇关于使用C语言建造你自己的虚拟机的文章。我喜欢研究底层应用，例如编译器，解释器，编辑器，虚拟机等。
预备知识和提醒
在我们继续之前，有一些东西是你必须知道的：
一个编译器 — 我在使用clang3.4,但是你可以使用支持c99/c11的任何编译器 编辑器 — 我会建议你使用文本编辑器而不是IDE，我会使用Emacs 基本的编程知识 — 只是基本，例如变量，控制符，函数，结构体等 Make — 一个编译体系，让我们不必在控制台写重复的命令去编译我们的代码为什么你应该写一个虚拟机
1
这里有一些你应该写一个虚拟机的原因：
指令集
我们会实现自己的指令集，它非常的简单。
我将简单提及一些指令，例如从寄存器中移动值，或者跳转到其他指令，但是希望你在度过这篇文章以后弄清楚它们。
我们的虚拟机会有一系列的寄存器A,B, C, D, E, 和 F。这些都是目的寄存器，你可以使用来存储任何东西。一个程序是一个只读的指令序列。这是一个基于栈的虚拟机，也就是说我们拥有一个栈来进行进栈和出栈的操作，另外还有少量的寄存器供我们使用。基于栈的虚拟机比基于寄存器的虚拟机更加容易实现。
不再多说，这里是我们将会用到的指令集。分号后是对每一行作用的说明。
PSH 5 ; 将5进栈
PSH 10 ; 将10进栈
ADD ; 将栈顶的两个值相加，然后将结果进栈
POP ; 将栈顶元素出栈，将会用于调试
SET A 0 ; 将寄存器A置零
HLT ; 停止程序
这就是我们的指令集，注意POP指令会打印出栈的值，这样更加便于调试(ADD指令会将结果入栈，所以我们使用POP来判断是否操作正确)
你也可以自己尝试实现类似MOV A,B。HLT指令表示我们的程序结束。
怎么使虚拟机工作？
虚拟机比你想的要简单，它们遵循一个简单的模式：取指令，解析，执行。一些先进的虚拟机可能会有另外的步骤，但是核心就是这些。我们从代码或指令集做取得下一条指令，然后去解析指令和执行解析后的指令。为了简单起见，我们不会去解析指令，典型的虚拟机会打包一个指令到一个值，然后去解析它。
项目结构
在我们开始编程之前，我们虚拟创建工程。首先，你需要一个C编辑器。我们需要一个文件夹来放置你的工程，我喜欢将工程放置在~/Dev下。我们在目标文件夹中创建工程。这里假设你已经有了~/Dev/目录，但是你也可以在任何地方创建你工程。
$cd ~/Dev/ mkdir mac cd mac mkdir src
在目标文件夹中，我们创建一个文件夹(称为VM”mac”)。然后我们cd进入这个文件夹，创建src文件夹，这里是我们放置代码的地方。
Makefile
我们没有任何的子文件，并且不会包含任何东西，所以我们只是需要makefile来进行编译
SRC_FILES = main.c
CC_FLAGS = -Wall -Wextra -g -std=c11
CC = clang
all:
${CC} ${SRC_FILES} ${CC_FLAGS} -o mac
这些目前已经足够了，我们以后改进它，但是只要它能完成工作就好。
程序指令(代码)
现在是虚拟机代码部分。首先我们需要为程序定义指令集。为此，我们使用enum，因为我们的指令集只是简单的从数字0-X。实际上，当你汇编文件的时候，汇编会将类似mov等指令转换成.\。例如，我们可以用0,5来代替PSH,5,但是这样的可读性非常差，所以我们使用枚举。
typedef enum {
PSH,
ADD,
POP,
SET,
HLT
} InstructionSet
现在我们将程序存储为数据。用于测试，我们会写一个简单的程序，将5和6相加，然后打印出来(使用POP指令)。如果你想的话，你可以创造一条打印栈顶元素的指令。
指令会存储成数组形式，我会在文档的开头定义它，但是你可以将它放入头文件。这是我们的测试程序：
const int program[] = {
PSH, 5,
PSH, 6,
ADD,
POP,
HLT
};
上面的程序会将5,6入栈，调用ADD指令，将两者出栈，然后将相加的结果入栈。我们会将结果出栈然后打印它，但是你不需要自己去做这个事情。我们只是用它来测试。最后，HLT指令被调用表示程序结束。
现在我们有程序了。所以现在我们实现取值，解析，求值的虚拟机操作。但是记住，我们不解析任何东西，因为这里只是原始指令。这意味着我们只需要关心取值，和求值。我们简化出两个函数fetch和evaluate
取出当前指令
因为我们将程序存储到数组中了，取出指令就变得很简单。虚拟机有一个计数器，通常称为程序计算器，指令指针…这些名字都是一个意思，取决于你个人喜好。我将这些缩写成IP或PC，因为他们在VM代码中非常常见。
如果你还记得，我说过我们会将程序计数器当成一个寄存器..我们会这样做，但是还要等一下。现在，我们只是在程序的开头，创建一个变量，叫ip,将其值设置为0。
int ip = 0;
ip表示指令指针。因为我们将程序存储成数组，我们使用ip变量去指向当前的index。例如，如果我们创建了一个变量x，值为为ip指向的程序，它会存储我们程序的第一条指令(加上ip值为0)
int ip = 0;
int main() {
int instr = program[ip];
return 0;
}
我们打印变量instr，它会给我们PSH,也就是0，因为这是我们enum的第一个值。我们可以将这个过程写出一个函数
int fetch() {
return program[ip];
}
这个函数会方法当前执行的指令。那么下一条指令呢？我们只要递增指令指针即可。
int main() {
int x = fetch(); // PSH
ip++; // increment instruction pointer
int y = fetch(); // 5
}
那么我们怎么使之自动化呢？我们知道程序会一直运行，知道HLT指令被调用。所以我们使用一个死循环，用于保证程序的运行。
// INCLUDE !
bool running = true;
int main() {
while (running) {
int x = fetch();
if (x == HLT) running = false;
ip++;
}
}
这里完美运行，但是有一点混乱。我们遍历每个指令，检查其是否是HLT，如果是停止循环，否则执行指令，并继续。
执行指令
这里我们的目的是真正地执行指令，并且让它看起来更加清晰。由于这个虚拟机很简单，我们可以利用enum写一个巨大的switch结构。eval有一个参数，表示要执行的指令。我们不会增加指令指针，除非我们消耗掉操作数。
void eval(int instr) {
switch (instr) {
case HLT:
running = false;
break;
}
}
回到main函数，我们可以将eval结合进去
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
}
}
栈！
在我们增加其他指令之前，我们需要一个栈。幸运的是，这很简单，我们只需要一个数组。数组有一个合适的大小，在这里是256。我们也需要一个栈指针，通常缩写为sp。它指向我们的栈数组的当前index。
为了更加形象，这是我们的栈(数组)
[] // empty
PSH 5 // put 5 on top of the stack
[5]PSH 6
[5, 6]POP
[5]POP
[] // emptyPSH 6
[6]PSH 5
[6, 5]
所以继续我们的程序。
PSH, 5,
PSH, 6,
ADD,
POP,
HLT
首先将5入栈
[5]
然后6入栈
[5,6]
然后ADD指令会将这两个数出栈，相加以后将结果入栈
[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 pide 5 / 6 is not the same >as 6 / 5
result = b + a;
push result // push the result to the stack
[11] // stack contents
所以我们栈指针在哪里呢？栈指针，或者说sp一般默认为-1,表示栈为空。数组从0开始，所以如果sp表示是0，那么C编译器会造成混乱。
现在如果我们将3个数入栈，sp会是2。
sp points here (sp = 2)
|
V
[1, 5, 9]
0 1 2 <- these are the array indices
当我们想看栈顶元素，我们只是看到sp指向的值。所以现在你应该明白栈是怎么工作的了。C语言实现也很简单。除了ip变量，我们还定义了一个sp变量，其默认值是-1!现在stack只是一个数组，我们有如下定义：
int ip = 0; int sp = -1; int stack[256]; // use a define or something here preferably // other c code here...
现在如果我们想将元素入栈，我们自增栈指针，然后将值设置到sp指向的位置。注意，顺序非常重要！
// pushing 5 // sp = -1 sp++; // sp = 0 stack[sp] = 5; // top of stack is now [5]
所以我们可以在eval函数中增加push操作：
void eval(int instr) {
switch (instr) {
case HLT: {
running = false;
break;
}
case PSH: {
sp++;
stack[sp] = program[++ip];
break;
}
}
}
现在,你可能会注意到一些以前的eval函数之间的区别。首先,每个case中有括号。如果你不熟悉这个技巧,它给了这样一个范围,这样你就可以在case中定义变量。我们现在不需要它,但我们稍后会用到,这样方便所有的case保持一致。
另外，program[++ip]表示自增操作。我们的程序是存储在一个数组中。我们PSH指令消耗一个操作数。一个操作数基本上是一个参数,就像当你调用一个函数你可以传递一个参数。在这种情况下,我们说要把5入栈。所以我们必须得到这个操作数,要做到这一点,我们增加指令指针。所以我们的IP为零，这意味着它指向PSH，但是现在我们在PSH的指令，我们想获得下一个指示。要做到这一点就要增加指令。注意增量的位置是很重要的，我们得到的指令之前，我们要增加指令指针否则我们只会得到PSH，然后就跳过下一个指令造成一些奇怪的错误。我可以将sp++简写为stack[++sp]。
现在说POP指令，它很简单。我们只需要自减栈指针，但是我也想打印出我们出栈的那个值。我省略了其他的代码指令和switch语句,这里只包括POP指令的case部分：
// REMEMBER TO INCLUDE !
case POP: {
int val_popped = stack[sp--];
printf("popped %d\n", val_popped);
break;
}
所以我们所做的就是我们栈顶值保存到val_popped中,然后我们将栈指针自减。如果我们先将栈指针自减，你会得到一些垃圾值,因为sp可以是0,那么我们将栈指针自减并设置val_popped到stack[-1]基本上,这并不妙。
最后是ADD指令。这里用到了上面提到的case作用范围。
case ADD: {
// first we pop the stack and store it as a
int a = stack[sp--];
// then we pop the top of the stack and store it as b
int b = stack[sp--];
// we then add the result and push it to the stack
int result = b + a;
sp++; // increment stack pointer **before**
stack[sp] = result; // set the value to the top of the stack
// all done!
break;
}
寄存器
对于虚拟机，寄存器是可选的。寄存器很容易实现，我们提到我们有寄存器A, B, C, D, E, 和 F。我们可以这样定义枚举：
typedef enum {
A, B, C, D, E, F,
NUM_OF_REGISTERS
} Registers;
最后一个值NUM_OF_REGISTERS只是一个简单的技巧，这样我们得到寄存器的数量。现在我们需要一个数组来存储寄存器。
int registers[NUM_OF_REGISTERS];
我们可以这样来使用寄存器A
printf("%d\n", registers[A]); // prints the value at the register A
指令指针
什么是分支？我把它留给你。记住一个指令指针指向当前的指令。现在,因为这是在虚拟机源代码,你最好的选择是有指令指针寄存器,这样从虚拟机可以读取和操作程序。
typedef enum {
A, B, C, D, E, F, PC, SP,
NUM_OF_REGISTERS
} Registers;
现在我们可以实际使用这些指令和堆栈指针。一个快捷的方法，是进行宏定义
#define sp (registers[SP]) #define ip (registers[IP])
应该是一个不错的解决方法,这样你不需要重写代码,并且保证功能正常。然而,这可能不便于扩展,可能会导致代码混淆，所以我建议不使用这种方法,但对于一个简单的玩具虚拟机它足够了。
当涉及到我们的代码中的分支,我给你一个提示。利用我们新的IP寄存器,我们可以给这个IP写入不同的值。试试下面这个示例,看它做什么：
PSH 10
SET IP 0
和人们熟悉的BASIC程序相似
10 PRINT “Hello, World”
20 GOTO 10
然而，因为我总是要将值入栈，所以最终会造成栈溢出。在你的VM中，这也是一个需要处理的边界情况。
; these are the instructions
PSH 10 ; 0 1
PSH 20 ; 2 3
SET IP 0 ; 4 5 6
如果你想调到第二条SET指令，我们会将IP寄存器设置为2而不是0。
最后
你可以在这里获得代码。如果你想要看到包含MOV,SET指令的版本，你可以下载bettervm.c。如果你遇到问题，你也可以将你的实现和上面的文件对比。如果你想要教程代码，你可以下载main.c。
你可以在项目文件夹下执行make命令，如果正确编译，你可以执行./mac文件。
如果你对这个话题感兴趣并且向扩展，网上有很多的资源。Notch写了DCPU-16，一个16位的虚拟机。Github上也有很多的实现，你可以模仿它们。如果你写了一个类似的模拟器，检查它的语法规则，看看你是否能够执行指令和设置寄存器。
谢谢阅读。