Own Virtual Machine

前言

什么是virtual machine

虚拟机就是一段表现得像一个电脑的程序，这段程序模仿了CPU以及其他的一些硬件，这使得这段程序表现得具有算术性（arithmetic），比如说能够读，写内存，能够和I/O设备交互，就像一台物理意义上的电脑一样。最重要的是，一个VM能够明白你用来编程时用到的机器语言。

虚拟机尝试模拟的计算机硬件数量取决于一个VM的用途。一些虚拟机被用来设计重现一些计算机的特定功能，比如说常见的游戏模拟器。大部分人并没有一台NES，但是我们仍然可以通过在一个程序中模拟NES的硬件环境来玩NES上的游戏。这种类型的模拟器必须忠实地重建原始设备中的每个细节和主要硬件组件。

而有其他一些虚拟机则不必表现得像一台真实的计算机，并且可以完全没有实物参考。这样做的首要目的是为了让一些软件的开发更容易一些。考虑一下你想要开发一个能在多个指令集框架下运行的程序，此时虚拟机可以被设计用来提供一个标准平台，为所有平台提供可移植性，而不是不断重写一个程序在不同指令集下的汇编的方言集。此时，只需要用每种指令集下的汇编语言编写小型虚拟机程序。 然后，每个程序只能使用虚拟机的汇编语言编写一次。

Note：编译器通过将标准的高级语言编译为几种CPU架构来解决类似的问题。 虚拟机创建一个标准的CPU体系结构，该体系结构可在各种硬件设备上进行仿真。 编译器的一个优势是不会带来运行时开销，而虚拟机却很难避免。但即使编译器做得很好，但是编写针对多个平台的新程序还是很困难的，因此虚拟机在跨平台时依然有很大的帮助。 实际上，虚拟机和编译器在各个级别上混合在一起。

JAVA虚拟机（JVM）就是一个非常成功的案例，JVM本身是一个中等大小的程序，其大小足以让一个程序员理解。这使得可以为包括电话在内的数千种设备编写内容。 在新设备上实现JVM之后，任何编写的Java，Kotlin或Clojure程序都可以在其上运行，而无需进行任何修改。唯一的成本是虚拟机本身的开销以及从计算机的进一步抽象。 大多数时候，这是一个很好的权衡。

虚拟机不必很大或无处不在（pervasive）即可提供这样的好处。 旧的视频游戏通常使用小型VM提供简单的脚本系统。

虚拟机对于以安全或隔离的方式执行代码也很有用。 一种应用是垃圾收集。 由于程序看不到自己的堆栈或变量，因此没有简单的方法可以在C或C ++上实现自动垃圾回收。 但是，虚拟机在其正在运行的程序“外部”，并且可以观察堆栈上的所有内存引用。

以太坊智能合约证明了这种行为的另一个例子。 智能合约是由区块链网络中每个验证节点执行的小程序。 这要求节点操作员在他们的计算机上运行完全陌生的人编写的程序，而且没有任何机会对其进行事先检查。 为了防止合同执行时的恶意操作，它们在无法访问文件系统，网络，磁盘等的虚拟机内运行。以太坊也是使用虚拟机的可移植性功能的良好应用。 由于以太坊节点可以在多种计算机和操作系统上运行，因此使用虚拟机可以编写智能合约，而无需考虑它们运行的许多平台。

LC-3 Architecture

我们要编写的虚拟机将会模拟一个叫做LC-3的虚构计算机，LC-3非常适合教大学生如何使用汇编语言进行编程，与x86相比，它具有简化的指令集，但包含了现代CPU中使用的所有主要思想。

首先，我们需要模拟机器的基本硬件组件。 尝试了解每个组件是什么，但是现在请不要担心以后这些代码会不会适用。 先开始创建一个C文件。 本节中的每个代码段都应放置在此文件的全局范围内。

内存

LC-3虚拟机有65,536的内存地址（可通过16位无符号整数2 ^ 16寻址的最大值），每一个地址都会被用来存一个16位(bit)的值，这就意味着我们的虚拟机一共可以存储仅仅128kb，比之前所习惯使用的虚拟机小得多，在我们编写的程序中，这些内存将会存储在一个简单的数组中：

/* 65536 locations */
uint16_t memory[UINT16_MAX];

寄存器

寄存器是用于在CPU上存储单个值的插槽。 寄存器就像CPU的“工作台”。 为了使CPU处理一条数据，这条数据必须位于一个寄存器中。 但是，由于只有几个寄存器，因此在任何给定时间只能加载最少量的数据。 程序通过将内存中的值加载到寄存器中，计算值并存储到其他寄存器中，然后将最终结果存储回内存中来解决此问题。

LC-3一共有10个寄存器，每一个寄存器都是16位。它们中的大多数是通用的，但有少数具有特点的功能。

• 8个通用寄存器（R0-R7）
• 1个程序计数器（PC）寄存器
• 1个条件标志寄存器（COND）

通用寄存器可用于执行任何程序计算。 程序计数器中存储的是一个无符号整数，它是内存中要执行的下一条指令的地址。 条件标志寄存器则告诉我们有关先前计算的信息。

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
};

就像存储内存一样，我们用同样的方式在一个数组中存储寄存器：

uint16_t reg[R_COUNT];

指令集

一个指令是一个命令，会让CPU执行一些基本任务，例如将两个数字相加。 指令既具有指示要执行的任务类型的操作码，也提供执行指令时所需要的一系列参数。

每个操作码代表一个任务，CPU根据操作码将“知道”该怎么做。 LC-3中只有16个操作码。 计算机可以计算的所有内容都是这些简单指令的集合。 每条指令长16位，其中最左边的4位用于存储操作码， 其余的位用于存储参数。

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 */
}

Note: 英特尔x86架构具有数百条指令，而其他指令（例如ARM和LC-3）则很少。 小指令集称为RISC(精简指令集)，大指令集称为CISC(复杂指令集)。 较大的指令集通常从根本上来说没有提供新的功能，但是它们通常使编写汇编更为方便。 CISC中的一条指令可能会和RISC中的一系列指令发挥的作用一样。 但是，对于工程师来说，它们的设计和制造往往更为复杂和昂贵。 这些原因和其他的权衡取舍使得CISC变得逐渐过时。

条件标志位

R_COND寄存器存储条件标志位，这些条件标志位提供有关最近执行的计算的信息。 这使程序可以检查逻辑条件，例如 if（x> 0）{…}。

每个CPU都有各种条件标志位来发出各种情况的信号。 LC-3仅使用3个状态标志来指示先前计算的符号。

enum{
    FL_POS = 1 << 0, /* P */
    FL_ZRO = 1 << 1, /* Z */
    FL_NEG = 1 << 2, /* N */
};

现在我们完成了虚拟机硬件部分的设置。

汇编示例

现在，让我们看一下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语言中一样，该程序从顶部开始，一次执行一个语句。 但是，与C不同，没有嵌套的作用域{}或控制结构，例如if或while； 只是陈述的列出要执行的清单，这使得执行起来更加容易。

请注意，某些语句的名称与我们之前定义的操作码相匹配。 先前，我们了解到每条指令都是16位，但是每一行看起来都是不同数量的字符。 这种不一致是怎么实现的？

这是因为我们正在读取的代码是以汇编形式编写的，汇编语言是一种助记符的形式，以纯文本编码。 称为汇编程序的工具用于将每一行文本转换为虚拟机可以理解的16位二进制指令。 这种二进制形式本质上是一个16位指令的数组，称为机器代码，是虚拟机实际运行的形式。

NOTE: 尽管编译器和汇编器在开发中扮演相似的角色，但它们并不相同。 汇编器仅将程序员在文本中编写的内容编码为二进制，然后将符号替换为二进制表示形式并将其打包为指令。

.ORIG和.STRINGZ看起来像指令，但实际上并非如此， 它们是伪指令（assembler directives），可生成一段代码或数据（像宏一样）。 例如，.STRINGZ在程序二进制文件的写入位置插入一个字符串。

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!

NOTE:本教程不需要学习编写汇编。 但是如果有兴趣，可以使用LC-3工具编写和汇编自己的LC-3程序。

执行程序

前面的示例只是为了解虚拟机的功能。 编写虚拟机不需要精通汇编程序。 只要遵循正确的步骤来阅读和执行指令，无论它多么复杂，任何LC-3程序都将正确运行。 从理论上讲，它甚至可以运行Web浏览器或Linux之类的操作系统！

如果深入考虑过这个特性，那么这是一个哲学上非凡的想法。 程序本身可以执行我们从未预料到并且可能无法理解的各种智能操作，但是与此同时，它们可以执行的所有操作仅限于我们将要编写的简单代码！ 我们同时了解每个程序的工作原理，但同时却对它一无所知。 图灵观察到了这个奇妙的想法：

“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

执行过程

下面是我们需要编写的：

1. 从PC寄存器地址的存储器中加载一条指令。
2. 递增PC寄存器。
3. 查看操作码以确定应执行的指令类型。
4. 使用指令中的参数执行指令。
5. 返回步骤1。

你可能想知道，“如果循环不断增加PC，而我们又没有if或者while，那它不会很快用完指令吗？” 答案是不会，正如我们之前提到的，一些类似于goto的指令通过在PC上跳转来改变执行流程。

让我们开始在主循环中概述此过程：

int main(int argc, const char* argv[]){
    {Load Arguments, 5}
    {Setup, 12}

    /* set the PC to starting position */
    /* 0x3000 is the default */
    enum { PC_START = 0x3000 };
    reg[R_PC] = PC_START;

    int running = 1;
    while (running){
        /* FETCH */
        uint16_t instr = mem_read(reg[R_PC]++);
        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}
}

除了使用命令行直接输入命令外，我们也希望能够给出一个或者多个加载的路径给虚拟机直接执行。

if (argc < 2){
    /* show usage string */
    printf("lc3 [image-file1] ...\n");
    exit(2);
}

for (int j = 1; j < argc; ++j)
{
    if (!read_image(argv[j]))
    {
        printf("failed to load image: %s\n", argv[j]);
        exit(1);
    }
}

实现指令

现在的任务是为每个操作码用正确的实现去填充。 这比听起来容易。 每个说明的详细规范都包含在文档中。 每个规范都可以轻松转换为几行代码。 这里演示如何实现其中的两个。 其余代码可在下一部分中找到。

ADD

ADD指令取两个数字，将它们加在一起，然后将结果存储在寄存器中。每个ADD指令如下所示：

图中的编码有两行，说明此指令有两种不同的“模式”。 在解释模式之前，让我们尝试找到它们之间的相似之处。 在两行中，我们都可以看到从4位0001开始。这是OP_ADD的操作码值。 接下来的3位标记为DR， 这代表目的地寄存器。 目的地寄存器是将添加的总和存储的位置。 接下来的3位是SR1。 这是包含第一个要添加的数字的寄存器。

因此，我们知道要在哪里存储结果，并且知道要添加的第一个数字。 我们还需要的最后一点信息是第二个加数。 此时，两行开始看起来有所不同。 请注意，第一行的第5位为0，第二行为1。该位指示是立即模式还是寄存器模式。 在寄存器模式下，第二个数字与第一个数字一样存储在寄存器中。 标记为SR2，包含在位2-0中。 位3和4未使用。 在汇编中，它将写为：

ADD R2 R0 R1 ；将R0的内容添加到R1并存储在R2中。

立即模式提供了一种便利，减少了一些典型程序的长度。 第二个值没有存储在单独寄存器中，而是嵌入了指令本身，在图中标记为imm5。 这消除了编写指令以从存储器加载值的需要。 它在取值的范围内做了一些折衷，指令仅可寻找一个很小的空间，确切的说是2 ^ 5 = 32（无符号），这使得立即模式主要对递增和递减的运算来说很有用。 在汇编中，它可以写为：

ADD R0 R0 1； 将1加到R0并存储回R0

综上：

如果bit[5]为0，则从SR2获得第二个源操作数。 如果bit[5]为1，则通过将imm5字段中符号扩展为16位来获得第二个源操作数。 在两种情况下，都将第二个源操作数添加到SR1的内容中，并将结果存储在DR中。

什么是“符号扩展”？ 立即模式值只有5位，但是需要将其添加到16位数字中。 要进行加法运算，需要将这5位扩展为16位以匹配其他数字。 对于正数，我们可以简单地为其他位填充0。 对于负数，这会引起问题。 例如，五位中的-1为11111。如果我们将其扩展为0，则为0000 0000 0001 1111，等于31。符号扩展通过将0填充为正数，将1填充为负数来纠正此问题， 以便保留原始值。

uint16_t sign_extend(uint16_t x, int bit_count){
    if ((x >> (bit_count - 1)) & 1) {
        x |= (0xFFFF << bit_count);
    }
    return x;
}

NOTE: 如果对到底如何用二进制表示负数感兴趣，可以阅读有关二进制的补码。 但是这不是必需的。 可以仅复制上面的代码，并在任何需要时使用它。

此时状态位需要根据结果是负数，零，还是正数来设置。

之前我们定义了条件标志位的枚举，现在是时候使用它们了。 每当将值写入寄存器时，我们都需要更新标志以指示其符号。 我们将编写一个函数，以便可以复用：

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;
    }
}

现在可以编写操作码为ADD时的情况了

{
    /* destination register (DR) */
    uint16_t r0 = (instr >> 9) & 0x7;
    /* first operand (SR1) */
    uint16_t r1 = (instr >> 6) & 0x7;
    /* whether we are in immediate mode */
    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);
}

本节包含很多信息，现在来总结一下。

• ADD取两个值并将它们存储在寄存器中。

• 在寄存器模式下，要添加的第二个值在寄存器中找到。

• 在立即模式下，第二个值嵌入在指令的最右5位中。

• 小于16位的值需要进行符号扩展。

• 每当指令修改寄存器时，都需要更新条件标志。

你可能对编写15条以上的指令感到不知所措。 但是剩下指令的编写过程中，在这里学到的所有内容都将被重用。 大多数指令使用符号扩展，不同模式和更新标志的某种组合。

LDI

LDI代表“间接加载”。 该指令用于将值从内存中的位置加载到寄存器中。

二进制布局如下所示：

与ADD相比，LDI没有多种模式，而且参数更少。 此时操作码是1010，它对应于OP_LDI枚举值。 就像ADD一样，它包含一个3位DR（目标寄存器），用于存储加载的值。 其余位标记为PCoffset9。 这是嵌入在指令中的立即值（类似于imm5）。 由于该指令是从内存中加载的，因此我们可以猜测该数字是某种地址，它告诉我们从何处加载。

通过将bit[8：0]扩展到16位并将该值与递增的PC相加，就可以计算出地址。 内存中此地址存储的就是要加载到DR中的数据的地址。

像之前一样，我们需要对该9位值进行符号扩展，但这一次将其添加到当前PC中。 （如果回头看执行循环，则在加载该指令后PC会立即增加。）结果总和是内存中某个位置的地址，并且该地址还存储着另一个值，该值是等待加载的值的地址。

这似乎是一种从内存中读取值的一种迂回方式，但这是必不可少的。 LD指令限于9位的地址偏移量，而存储器需要16位的地址。 LDI对于加载存储在远离当前PC的位置中的值很有用，但是要使用它，最终位置的地址需要存储在附近能访问到的邻居中。 可以理解为它就像在C中具有一个局部变量，该局部变量是指向某些数据的指针：

// 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

与以前一样，将值存入DR后需要更新标志：

下面是实现案例：(mem_read将会在后续中讨论)

{
    /* destination register (DR) */
    uint16_t r0 = (instr >> 9) & 0x7;
    /* PCoffset 9*/
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 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);
}

就像之前说的那样，这条指令使用了许多从ADD学到的代码和知识。 在剩下的几个指令的实现中也是同样道理。

现在，可以去把switch中的剩余case给实现完整。 请遵循规范来完成其他指令。 之前指定的两个操作码将不使用，它们是OP_RTI和OP_RES。 您可以忽略两个指令的实现或者执行这两个指令时抛出错误。 完成后，您的VM的大部分将完成！

指令实现

如果遇到困难，本节包含其余说明的完整实现。

RTI & RES

(不会用到)

abort();

Bitwise and(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);
}

Bitwise not(NOT)

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t r1 = (instr >> 6) & 0x7;

    reg[r0] = ~reg[r1];
    update_flags(r0);
}

Branch(BR)

{
    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;
    }
}

Jump(JMP)

RET在LC-3中被列为单独的指令，因为它是汇编中的另一个关键字。 但是，实际上这是JMP的特例。 只要R1为7，就会发生RET。

{
    /* Also handles RET */
    uint16_t r1 = (instr >> 6) & 0x7;
    reg[R_PC] = reg[r1];
}

Jump Register(JSR)

{
    uint16_t long_flag = (instr >> 11) & 1;
    reg[R_R7] = reg[R_PC];
    if (long_flag)
    {
        uint16_t long_pc_offset = sign_extend(instr & 0x7FF, 11);
        reg[R_PC] += long_pc_offset;  /* JSR */
    }
    else
    {
        uint16_t r1 = (instr >> 6) & 0x7;
        reg[R_PC] = reg[r1]; /* JSRR */
    }
    break;
}

Load(LD)

{
    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);
}

Load Register(LDR)

{
    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);
}

Load Effective Address(LEA)

{
    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);
}

Store(ST)

{
    uint16_t r0 = (instr >> 9) & 0x7;
    uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);
    mem_write(reg[R_PC] + pc_offset, reg[r0]);
}

Store Indirect(STI)

{
    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]);
}

Store Register(STR)

{
    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]);
}

Trap Routine

LC-3提供了一些预定义的例程(predefined routines)，用于执行常见任务并与I / O设备进行交互。 例如，有一些例程可以从键盘获取输入并在控制台上显示字符串。 这些称为trap routines，您可以将其视为LC-3或操作系统的API。 每个trap routines都分配有一个标识它的trap code（类似于操作码）。 如果想要执行其中一个，用所需例程的 trap code调用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 */
};

你可能想知道为什么指令中不包含陷阱代码。 这是因为陷阱代码实际上并未向LC-3引入任何新功能，而只是提供了一种方便的方式来执行任务（类似于C中的系统功能）。 在官方的LC-3仿真器中，陷阱例程以汇编形式编写。 调用陷阱代码时，会将PC移至该代码的地址。 CPU执行该过程的指令，完成后，将PC重置为调用陷阱的位置。

注意：这就是为什么程序从地址0x3000而不是0x0开始的原因。 低位地址留空，以留出陷阱例程代码的空间。

其实并没有任何关于必须如何执行trap routines的规定，只有应该执行的trap routines应该实现什么。 在我们的虚拟机中，我们将通过用C编写它们来做一些稍有不同的事情。调用trap routines时，将调用C函数。 完成后，执行将返回指令。

即使trap routines可以用汇编语言编写，而且这实际上是一台LC-3计算机的工作方式，但这并不是最适合虚拟机的方法。 除了编写自己的原始I / O例程，我们还可以利用OS上可用的例程。 这将使VM在我们的计算机上更好地运行，简化代码，并为可移植性提供更高级别的抽象。

注意：从键盘获取输入就是一个具体示例。 汇编版本使用循环来连续检查键盘的输入。 这会浪费大量的CPU时间！ 使用适当的OS输入功能可使程序进入休眠状态，直到接收到输入为止。

在操作码有关Trap的switch case中，添加一个switch：

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;
}

与其他指令一样，接下来将演示如何实现单个陷阱例程，并将其余部分可以由自己实现。

PUTS

PUTS的trap code用于输出以空值结尾的字符串（类似于C中的printf）。

要显示一个字符串，我们必须给trap routine一个要显示的字符串。 这是通过在开始自陷(trap)之前将第一个字符的地址存储在R0中来完成的。

将一串ASCII字符写入控制台显示屏。 这些字符存储在在连续的存储位置中，每个存储位置一个字符，从R0中指定的地址开始。 写入终止于在存储单元中出现x0000。

请注意，与C字符串不同，字符不是存储在单个字节中，而是存储在单个存储位置中。 LC-3中的存储位置为16位，因此字符串中的每个字符均为16位宽。 要使用C函数显示此内容，我们需要将每个值转换为char并分别输出。

{
    /* one char per word */
    uint16_t* c = memory + reg[R_R0];
    while (*c)
    {
        putc((char)*c, stdout);
        ++c;
    }
    fflush(stdout);
}

这就是例程的全部内容。 如果熟悉C的话那么trap routines非常简单。接下来请实施其他例程。

Trap Routine 实现

本节包含其余Trap Routine的完整实现。

Input Character(GETC)

/* read a single ASCII char */
reg[R_R0] = (uint16_t)getchar();

Output Character(OUT)

putc((char)reg[R_R0], stdout);
fflush(stdout);

Prompt for Input Character(IN)

{
    printf("Enter a character: ");
    char c = getchar();
    putc(c, stdout);
    reg[R_R0] = (uint16_t)c;
}

Output String(PUTSP)

{
    /* 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);
}

Halt Program(HALT)

puts("HALT");
fflush(stdout);
running = 0;

程序加载

我们已经学习了很多关于从内存中加载和执行指令的知识，但是指令首先是如何进入内存的呢？ 将汇编程序转换为机器代码时，结果是一个包含指令和数据数组的文件。 只需将内容直接复制到内存中的地址中即可加载该文件。

程序文件的前16位指定程序应在内存中启动的地址。 此地址称为原点(origin)。 必须先读取它，然后才能从起始地址开始将其余数据从文件读取到内存中。

这是用于将LC-3程序读入内存的代码：

void read_image_file(FILE* file){
    /* the origin tells us where in memory to place the image */
    uint16_t origin;
    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;
    }
}

注意，在每个加载的值上调用了swap16。 因为LC-3程序是大端的，但是我们使用的大多数现代计算机都是小端。 因此我们需要交换每个已加载的uint16。 （如果碰巧使用的是奇怪的计算机（例如PPC），则不应进行交换。）

uint16_t swap16(uint16_t x){
    return (x << 8) | (x >> 8);
}

NOTE： 字节顺序是指如何解释整数的字节。 在小字节序中，第一个字节是最低有效数字，在大字节序中，它是相反的。 据我所知，该决定主要是任意的。 不同的公司做出不同的决定，所以现在我们有了不同的实现方式。 您不需要了解有关此项目的字节序的其他信息。

还可以为read_image_file添加一个便捷函数，该函数采用字符串路径；

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;
}

存储器映射寄存器

有时无法从普通寄存器表访问某些特殊寄存器。 此时需要为它们在存储器中保留一个特殊的地址。 要读写这些寄存器，只需读写它们的存储位置。 这些称为存储器映射寄存器。 它们通常用于与特殊的硬件设备进行交互。

LC-3具有两个需要实现的存储器映射寄存器。 它们是键盘状态寄存器（KBSR）和键盘数据寄存器（KBDR）。 KBSR指示是否已按下某个键，KBDR标识已按下哪个键。

尽管可以使用GETC请求键盘输入，但这会阻塞住直到收到输入。 KBSR和KBDR允许您轮询设备的状态并继续执行，因此程序可以在等待输入时保持响应状态。

enum{
    MR_KBSR = 0xFE00, /* keyboard status */
    MR_KBDR = 0xFE02  /* keyboard data */
};

存储器映射寄存器使访存更加复杂。 我们不能直接读写存储阵列，而必须调用setter和getter函数。 从KBSR读取内存时，getter将检查键盘并更新两个存储位置。

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];
}

这样就完成了虚拟机的最后一个组件！ 只要您实现了其余的trap routines和指令，几乎就可以运行了。

{Memory Mapped Registers}
{TRAP Codes}

{Memory Storage}
{Register Storage}

{Sign Extend}
{Swap}
{Update Flags}
{Read Image File}
{Read Image}
{Check Key}
{Memory Access}
{Input Buffering}
{Handle Interrupt}

{Main Loop}

平台特性(Unix)

本节包含一些繁琐的细节，这些细节对于使用键盘和使功能表现良好而言是必需的。 这些不是必须学习的，不与学习虚拟机有关。 随时复制粘贴！

注意：跳至下一部分，以获取这些功能的Windows版本。

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();

当程序中断时，我们希望将终端设置恢复为正常。

restore_input_buffering();

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <signal.h>
/* unix */
#include <unistd.h>
#include <fcntl.h>

#include <sys/time.h>
#include <sys/types.h>
#include <sys/termios.h>
#include <sys/mman.h>

平台特性(Windows)

本节包含一些繁琐的细节，这些细节对于使用键盘和使功能表现良好而言是必需的。 这些不是必须学习的，不与学习虚拟机有关。 随时复制粘贴！

注意：如果已经包含Unix版本，请不要添加这些版本！

uint16_t check_key()
{
    return WaitForSingleObject(hStdin, 1000) == WAIT_OBJECT_0 && _kbhit();
}

DWORD fdwMode, fdwOldMode;

void disable_input_buffering()
{
    hStdin = GetStdHandle(STD_INPUT_HANDLE);
    GetConsoleMode(hStdin, &fdwOldMode); /* save old mode */
    fdwMode = fdwOldMode
            ^ ENABLE_ECHO_INPUT  /* no input echo */
            ^ ENABLE_LINE_INPUT; /* return when one or
                                    more characters are available */
    SetConsoleMode(hStdin, fdwMode); /* set new mode */
    FlushConsoleInputBuffer(hStdin); /* clear buffer */
}

void restore_input_buffering()
{
    SetConsoleMode(hStdin, fdwOldMode);
}

signal(SIGINT, handle_interrupt);
disable_input_buffering();

当程序中断时，我们希望将终端设置恢复为正常。

restore_input_buffering();

#include <stdint.h> // uint16_t
#include <stdio.h>  // FILE
#include <signal.h> // SIGINT
/* windows only */
#include <Windows.h>
#include <conio.h>  // _kbhit

HANDLE hStdin = INVALID_HANDLE_VALUE;

运行虚拟机

现在可以构建并运行LC-3 VM！

1. 使用您最喜欢的C编译器进行编译。 对于gcc：$ gcc lc3.c -o lc3

2. 下载2048或Rogue的汇编版本。

3. 使用obj文件作为参数运行程序：

4. $ lc3 path/to/2048.obj

玩2048！

Control the game using WASD keys.
Are you on an ANSI terminal (y/n)? y
+--------------------------+
|                          |
|                          |
|                          |
|                     2    |
|                          |
|   2                      |
|                          |
|                          |
|                          |
+--------------------------+

Debugging

如果程序无法正常运行，则可能是因为对指令的编程不正确。 这可能很难调试。 我建议通读LC-3程序的汇编源代码，同时使用调试器一次遍历虚拟机的指令。 在阅读程序集时，请确保虚拟机按照您期望的说明进行操作。 如果出现差异，则知道引起该问题的原因。 重新阅读其说明说并仔细检查代码。