实现一个堆栈虚拟机

实现一个堆栈虚拟机

         本文我们实现一个基于堆栈的虚拟机，通过前面《简单虚拟机》和《栈虚拟机源码剖析》，对虚拟机结构和原理有了更深的理解和体会。下面我们给出堆栈虚拟机的示意图：

         堆栈虚拟机主要包括以上三部分：虚拟机、指令集、外部接口。

         其中虚拟机内部构造主要是数据、指令、堆栈三部分，指令对数据进行操作，将数据装载进堆栈中以备运算和处理。

         指令集的设计可以参考别人的设计也可以按照自己的理解逐步扩充改进，主要有PUSH、POP、TOP、INPUT、OUTPUT、JMP、JMP_TRUE、JMP_FALSE、JMP_EQUAL、JMP_NOT_EQUAL、JMP_BIGGER、JMP_SMALLER等指令，这里没有保护相关算术指令，算术指令可以进一步增加。

         虚拟机的外部接口主要是装载数据、装载指令、运行指令、复位等。

         下面我们给出虚拟机的实现，为了方便呈现，我们将代码放置于一个文件中：

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

// 指令集
enum InstructCode
{
    PUSH,                // 入栈
    POP,                 // 出栈
    TOP,                 // 栈顶
    INPUT,               // 输入
    OUTPUT,              // 输出
    JMP,                 // 跳转
    JMP_TRUE,            // 为真跳转
    JMP_FALSE,           // 为假跳转
    JMP_EQUAL,           // 等于跳转
    JMP_NOT_EQUAL,       // 不等跳转
    JMP_BIGGER,          // 大于跳转
    JMP_SMALLER          // 小于跳转
};

// 定义数据
// 我们定义的数据只有两种形式：整形和字符串
struct Data
{
    bool    isInt;
    int     intData;
    string  strData;

    Data() : isInt(true), intData(0) {}
    Data(int _n) : isInt(true), intData(_n) {}
    Data(const string& _s) : isInt(false), intData(0), strData(_s) {}
};

struct Instruct
{
    InstructCode insCode;
    int          operand;

    Instruct() {}
    Instruct(InstructCode _ic) : insCode(_ic) {}
    Instruct(InstructCode _ic, int _d) : insCode(_ic), operand(_d) {}
};

class VirtualBox
{
private:
    vector<Instruct> instruct; // 指令
    stack<Data>      stk;      // 堆栈

    vector<Data>     data;     // 数据

private:
    // 读取data
    void ReadData(Data& _d)
    {
        cout << "读取整型数 Y/N?";
        char ch;
        cin >> ch;
        if (toupper(ch) == 'Y')
        {
            cin >> _d.intData;
            _d.isInt = true;
        }
        else
        {
            cin >> _d.strData;
            _d.isInt = false;
        }
    }

    // 打印数据
    void PrintData(const Data& _d)
    {
        if (_d.isInt)
        {
            cout << _d.intData << endl;
        }
        else
        {
            cout << _d.strData << endl;
        }
    }
public:
    VirtualBox()
    {
        data.resize(101);
    }

    ~VirtualBox()
    {
        Reset();
    }

    void Reset()
    {
        data.clear();
        instruct.clear();
        while (!stk.empty())
        {
            stk.pop();
        }
        data.resize(101);

        cout << endl << "虚拟机复位" << endl;
    }

    void LoadData()                // 加载数据
    {
    }

    void LoadInstruct()            // 加载指令
    {
    }

    void LoadData_TestBigger()
    {
    }

    // 装在指令序列，其功能是：输入两个数，将其比较，输出较大的
    void LoadInstruct_TestBigger()
    {
        instruct.push_back(Instruct(INPUT, 0));           // 读取数据1
        instruct.push_back(Instruct(INPUT, 1));           // 读取数据2
        instruct.push_back(Instruct(PUSH , 0));           // 将数据1压栈
        instruct.push_back(Instruct(PUSH , 1));           // 将数据2压栈
        instruct.push_back(Instruct(JMP_BIGGER, 3));      // 如果数据1大于数据2，则前进3步
        instruct.push_back(Instruct(PUSH, 1));            // 如果数据1不大于数据2，则将数据2压栈
        instruct.push_back(Instruct(JMP , 2));            // 前进2步
        instruct.push_back(Instruct(PUSH, 0));            // 将数据1压栈，承接上面的前进3步
        instruct.push_back(Instruct(OUTPUT));             // 将较大的数输出
    }

    void LoadData_TestPrint()      // 测试打印数组——加载数据
    {        
        for (int i = 0; i != 10; ++i)
        {
            data[i] = Data(i);
        }
    }
    void LoadInstruct_TestPrint()  // 测试打印数组——加载指令
    {
        for (int i = 0; i != 10; ++i)
        {
            instruct.push_back(Instruct(PUSH, i));
            instruct.push_back(Instruct(OUTPUT));
        }
    }

    void Run()
    {
        int ip  = 0; // 指令索引
        int ipc = 1; // 指令前移量
        Data a, b;
        for (; ip < instruct.size(); )
        {
            ipc = 1;
            switch (instruct[ip].insCode)
            {
            case PUSH:
                stk.push(data[instruct[ip].operand]);           // 堆栈中存储实际的值，而非data的索引
                break;

            case POP:
                stk.pop();
                break;

            case TOP:
                data[instruct[ip].operand] = stk.top();
                break;

            case INPUT:
                ReadData(data[instruct[ip].operand]);
                break;

            case OUTPUT:
                PrintData(stk.top());
                stk.pop();
                break;

            case JMP:
                ipc = instruct[ip].operand;
                break;

            case JMP_TRUE:
                if (stk.top().isInt && stk.top().intData != 0 || !stk.top().isInt && !stk.top().strData.empty())
                {
                    ipc = instruct[ip].operand;
                }
                stk.pop();
                break;

            case JMP_FALSE:
                if (!(stk.top().isInt && stk.top().intData != 0 || !stk.top().isInt && !stk.top().strData.empty()))
                {
                    ipc = instruct[ip].operand;
                }
                stk.pop();
                break;

            case JMP_EQUAL:
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                if (a.isInt == b.isInt && a.isInt && a.intData == b.intData)
                {
                    ipc = instruct[ip].operand;
                }
                if (a.isInt == b.isInt && !a.isInt && a.strData == b.strData)
                {
                    ipc = instruct[ip].operand;
                }
                break;

            case JMP_NOT_EQUAL:
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                if (!(a.isInt == b.isInt && a.isInt && a.intData == b.intData))
                {
                    ipc = instruct[ip].operand;
                }
                if (!(a.isInt == b.isInt && !a.isInt && a.strData == b.strData))
                {
                    ipc = instruct[ip].operand;
                }
                if (a.isInt != b.isInt)
                {
                    ipc = instruct[ip].operand;
                }
                break;

            case JMP_BIGGER:
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                if (a.isInt == b.isInt && a.isInt && a.intData > b.intData)
                {
                    ipc = instruct[ip].operand;
                }
                if (a.isInt == b.isInt && !a.isInt && a.strData > b.strData)
                {
                    ipc = instruct[ip].operand;
                }
                break;

            case JMP_SMALLER:
                b = stk.top();
                stk.pop();
                a = stk.top();
                stk.pop();
                if (a.isInt == b.isInt && a.isInt && a.intData < b.intData)
                {
                    ipc = instruct[ip].operand;
                }
                if (a.isInt == b.isInt && !a.isInt && a.strData < b.strData)
                {
                    ipc = instruct[ip].operand;
                }
                break;

            default:
                break;
            }
            ip += ipc;
        }
    }
};

int main()
{
    VirtualBox vb;

    vb.LoadData_TestPrint();
    vb.LoadInstruct_TestPrint();

    vb.Run();

    vb.Reset();

    vb.LoadData_TestBigger();
    vb.LoadInstruct_TestBigger();
    vb.Run();
    

    return 0;
}

         下面我们对虚拟机代码进行逐步讲解。

         指令集

         我们总共定义了12个指令，指令类型为enum型，便于switch-case结构处理。

         数据

         我们的数据类型目前支持两种类型：整型和字符串。Data结构体的定义如下：

struct Data

{

    bool    isInt;

    int     intData;

    string  strData;

 

    Data() : isInt(true), intData(0) {}

    Data(int _n) : isInt(true), intData(_n) {}

    Data(const string& _s) : isInt(false), intData(0), strData(_s) {}

};

         isInt用于标识Data存储的数据是整型还是字符串。

         指令

         我们对指令的定义包含了两部分：操作码和操作数，其中操作数为Data集的索引，而非实际的Data。

struct Instruct

{

    InstructCode insCode;

    int          operand;

 

    Instruct() {}

    Instruct(InstructCode _ic) : insCode(_ic) {}

    Instruct(InstructCode _ic, int _d) : insCode(_ic), operand(_d) {}

};

         虚拟机VirtualBox

         VirtualBox主要包含三部分：

         vector<Instruct> instruct; // 指令

         stack<Data>      stk;      // 堆栈

         vector<Data>     data;     // 数据

         其中，data用于存储待处理或已处理的数据，instruct为待执行的指令，stk为根据指令实际操作数据的场所。

         VirtualBox定义了两个private成员函数ReadData、PrintData用于读取和打印数据。

         其余就是VirtualBox的外部接口，其中LoadData用于装载数据，LoadInstruct用于装载指令，Run函数式用于实际的执行指令，其内部有局部变量ip用于记录当前指令索引，ipc用于记录指令跳转量，主要是switch-case结构，根据指令集中的12个指令，执行相应的操作。

         另外还有一个Reset复位函数。

 

         测试

         我们对该虚拟机进行了两个测试分别是打印0-9十个数字，输入两个数（整型数或字符串），打印出其中较大的数。

         打印0-9十个数字的LoadData为：

       for (int i = 0; i != 10; ++i)

       {

           data[i] = Data(i);

       }

         LoadInstruct为：

       for (int i = 0; i != 10; ++i)

       {

           instruct.push_back(Instruct(PUSH, i));

           instruct.push_back(Instruct(OUTPUT));

       }

         打印较大数的LoadData为空，LoadInstruct为：

                   instruct.push_back(Instruct(INPUT, 0));           // 读取数据1

                   instruct.push_back(Instruct(INPUT, 1));           // 读取数据2

                   instruct.push_back(Instruct(PUSH , 0));           // 将数据1压栈

                   instruct.push_back(Instruct(PUSH , 1));           // 将数据2压栈

                   instruct.push_back(Instruct(JMP_BIGGER, 3));      // 如果数据1大于数据2，则前进3步

                   instruct.push_back(Instruct(PUSH, 1));            // 如果数据1不大于数据2，则将数据2压栈

                   instruct.push_back(Instruct(JMP , 2));            // 前进2步

                   instruct.push_back(Instruct(PUSH, 0));            // 将数据1压栈，承接上面的前进3步

                   instruct.push_back(Instruct(OUTPUT));             // 将较大的数输出

 

         总结

         以上是我们实现的基于堆栈的虚拟机，有关指令集方面的扩展尤其是对于算术指令扩展，有待我们进一步改进。VirtualBox的源码以及后续扩展更新可以参见Github。