聽說你想寫個(gè)虛擬機(jī)（三）？

大家好，我是微微笑的蝸牛，??。

在上兩篇文章中，我們實(shí)現(xiàn)了一個(gè)最小的虛擬機(jī)。如果沒看過的同學(xué)，可以回過頭先去看看。

今天，繼續(xù)升級打怪，不過難度有所提高，將會模擬一個(gè)更加真實(shí)的環(huán)境，Little Computer-3 的實(shí)現(xiàn)，簡稱 LC-3。

LC-3 是用于教學(xué)的匯編語言，它有著相比于 x86 更為簡潔的指令集，同時(shí)包含了主流 CPU 的經(jīng)典思想。有關(guān) LC-3 的介紹可點(diǎn)此查看。

LC-3 麻雀雖小，五臟俱全。不過它的規(guī)范不算太多，我們模擬它的實(shí)現(xiàn)還是比較合適的。

LC-3 基礎(chǔ)

首先，介紹一些 LC-3 的前置知識：

  • 內(nèi)存地址空間 16 位，也就是最多可訪問 0x0000~0xffff 的范圍。
  • 通用寄存器 8 個(gè)，16 位。編號從 000~111，R0 ~ R7。
  • 三個(gè)標(biāo)志寄存器，N（Negative）、P（Postive）、Z（Zero），每個(gè) 1 位。
  • PC 寄存器。
  • 指令長度 16 位，操作碼 op 固定高 4 位。
  • 采用大端字節(jié)序。
  • 系統(tǒng)調(diào)用表。
  • 中斷向量表。
  • ...

另外，還有一些沒有列出來。但我們只打算實(shí)現(xiàn)它的一個(gè)子集，其他可以不用關(guān)注。

內(nèi)存空間

由于 LC-3 工作在 16 位下，內(nèi)存最大可訪問空間是 2^16-1。

這里我們?nèi)匀挥脭?shù)組來模擬，給它分配最大空間 UINT16_MAX 即可。

uint16_t mem[UINT16_MAX];

寄存器

這里我們定義 10 個(gè)寄存器，分別是：

  • 8 個(gè)通用寄存器
  • PC 寄存器
  • COND 標(biāo)志寄存器，用于表示 N/P/Z 狀態(tài)
// 寄存器定義
typedef enum
{
  R_R0,
  R_R1,
  R_R2,
  R_R3,
  R_R4,
  R_R5,
  R_R6,
  R_R7,
  R_PC,
  R_COND,
  R_COUNT
} Registers;

// 寄存器數(shù)組
uint16_t reg[R_COUNT];

R_COUNT 用于快速得到寄存器數(shù)量，reg[x] 可得到寄存器的值。

標(biāo)志寄存器

標(biāo)志寄存器用來標(biāo)識 N/P/Z 的狀態(tài)。取值定義如下：

// 標(biāo)志定義
typedef enum
{
  FL_POS = 1 << 0, // 正數(shù)
  FL_ZRO = 1 << 1, // 0
  FL_NEG = 1 << 2  //負(fù)數(shù)
} ConditionFlags;

指令格式

指定包括操作碼和操作數(shù)，有著如下標(biāo)準(zhǔn)格式：

  • 指令長度為 16 位，高 4 位為操作碼，最多可表示 16 種指令。操作碼范圍 0000~1111。
  • 低 12 位用于表示參數(shù)。不同的指令，有著不同的參數(shù)，占用長度和布局也不一樣。

指令的大體布局如下：

指令布局

注意：指令的參數(shù)中可能會包含寄存器、立即數(shù)等等。寄存器統(tǒng)一用 3 位來標(biāo)識，因?yàn)榭偣仓挥?8 個(gè)通用寄存器。

指令定義

這次，我們打算實(shí)現(xiàn)如下指令。

// 指令定義
typedef enum
{
  OP_BR = 0,    // 條件分支
  OP_ADD = 1,   // 加法
  OP_LD = 2,    // 取內(nèi)存地址的值到寄存器
  OP_ST = 3,    // 存寄存器的值到內(nèi)存地址
  OP_JSR = 4,   // 跳轉(zhuǎn)函數(shù)
  OP_AND = 5,   // 與運(yùn)算
  OP_LDR = 6,   // 取值到寄存器
  OP_STR = 7,   // 存儲寄存器的值
  OP_RTI = 8,   // unused
  OP_NOT = 9,   // 取反
  OP_LDI = 10,  // 間接取值
  OP_STI = 11,  // 間接存值
  OP_JMP = 12,  // 跳轉(zhuǎn)
  OP_RES = 13,  // reserved
  OP_LEA = 14,  // 加載地址到寄存器
  OP_TRAP = 15, // 系統(tǒng)調(diào)用
} InstructionSet;

主要分為如下幾類：

  • 運(yùn)算
  • 數(shù)據(jù)存取
  • 跳轉(zhuǎn)
  • 系統(tǒng)調(diào)用
  • 保留指令，暫時(shí)為使用，可用于占位

由于指令有點(diǎn)多，且實(shí)現(xiàn)更復(fù)雜。全部寫完文章會拖的太長，因此打算分為 3 篇來講。這篇主要介紹運(yùn)算、跳轉(zhuǎn)和保留指令，使用匯編的方式說明用法（?? 0101.. 看著頭大）。

指令實(shí)現(xiàn)

ADD

加法指令，操作碼為 0001，總共三個(gè)參數(shù)。指令執(zhí)行之后，會更新標(biāo)志寄存器的值。

它有兩種模式，不同的模式通過指令第 6 位標(biāo)志位來區(qū)分。主要區(qū)別在于第三個(gè)參數(shù)。

  • 若標(biāo)志位為 1，則為立即數(shù)模式；
  • 若標(biāo)志位為 0，則為寄存器模式。

以下代碼中用于取出標(biāo)志位，instr 表示指令。

// 取出 flag，在第 6 位。
uint16_t flag = (instr >> 5) & 0x1;

1. 立即數(shù)模式

ADD R0, R1, #5 → RO = R1 + 5

第三個(gè)參數(shù)為數(shù)字，可直接使用，所以稱之為立即數(shù)。

指令布局如下，標(biāo)志位為 1。

image

低 5 位為立即數(shù)。由于寄存器是 16 位，與立即數(shù)相加時(shí)，需將立即數(shù)以有符號的方式擴(kuò)展到 16 位。

擴(kuò)展方式比較簡單，若最高位為 1，則全部填 1；若最高位為 0，則全部填 0。如下圖所示：

image

由于符號擴(kuò)展在很多指令中都會用到。因此，我們寫個(gè)通用的函數(shù)，專用于處理符號擴(kuò)展。

// 符號擴(kuò)展
uint16_t sign_extend(uint16_t x, int bit_count)
{
  // 最高位 1
  if ((x >> (bit_count - 1)) & 0x1)
  {
        // 全部補(bǔ) 1
    x |= 0xFFFF << bit_count;
  }

  return x;
}

搞清楚指令布局和符號擴(kuò)展后，實(shí)現(xiàn)就比較簡單了。

  1. 取出「目的寄存器 r0」，注意寄存器相關(guān)的值都是寄存器下標(biāo)。
  2. 取出「源寄存器 r1」。
  3. 取出「立即數(shù) imm」，并進(jìn)行符號擴(kuò)展。
  4. 相加求和，將結(jié)果放入「目的寄存器 r0」。
// 取出目的寄存器 r0，9~11，占 3 位，與上 111
uint16_t r0 = (instr >> 9) & 0x7;

// 源寄存器 r1，6~8 位
uint16_t r1 = (instr >> 6) & 0x7;

// 低五位，取出立即數(shù)。
uint16_t data = instr & 0x1F;

// 符號擴(kuò)展，若高位是 1，則全部補(bǔ) 1
uint16_t value = sign_extend(data, 5);

// 求和
reg[r0] = reg[r1] + value;

// 更新標(biāo)志寄存器
update_flags(r0);

最后，還剩一步，lc-3 規(guī)范中要求更新標(biāo)志寄存器。根據(jù)當(dāng)前操作寄存器的符號位，設(shè)定不同的狀態(tài)。如下所示：

// 更新標(biāo)志寄存器
void update_flags(uint16_t r)
{
  uint16_t value = reg[r];
  if (value == 0)
  {
    COND = FL_ZRO;
  }
  else if ((value >> 15) & 0x1)
  {
    // 最高位 1，負(fù)數(shù)
    COND = FL_NEG;
  }
  else
  {
    COND = FL_POS;
  }
}

這樣，立即數(shù)模式的實(shí)現(xiàn)就完成了。

下面再來舉個(gè)實(shí)際的 ??，說明下指令的布局。

假設(shè)我們想做這樣的操作：ADD R1,R2,#6，那么指令數(shù)據(jù)如下圖所示：

image

其中 操作碼=0001；第一個(gè)參數(shù)=001；第二個(gè)參數(shù)=010；第三個(gè)參數(shù)=00110，最終的十六進(jìn)制表示為：0x12A6。

2. 寄存器模式

ADD RO, R1, R2 → RO = R1 + R2

第三個(gè)參數(shù)為寄存器，需從寄存器中取值。

指令布局如下，標(biāo)志位為 0。

image

寄存器模式的實(shí)現(xiàn)更加簡單，取出「源寄存器 2」的值，與「源寄存器 1」相加，結(jié)果放入「目的寄存器」。

// 取出源寄存器 2，低 3 位
uint16_t r2 = instr & 0x7;

// 相加
reg[r0] = reg[r1] + reg[r2];

// 更新標(biāo)志寄存器
update_flags(r0);

寄存器模式下的指令，你也可以試著舉個(gè)實(shí)例栗子，動手寫寫看。

AND

與運(yùn)算，操作碼 0101。和 ADD 一樣，有兩種模式，指令格式一模一樣。把求和改成求與就好，就不重復(fù)了。

兩種模式的指令布局如下圖所示：

image

NOT

NOT R0, R1; R0 = ~R1

取反指令，操作碼 1001。取反之后同時(shí)更新標(biāo)志寄存器。

指令布局如下所示，低六位沒有使用，全是 1。

image

目的寄存器和源寄存器的取法跟 ADD 指令是一樣，代碼實(shí)現(xiàn)如下：

// 取出目的寄存器 r0，9~11，占 3 位，與上 111
uint16_t r0 = (instr >> 9) & 0x7;

// 源寄存器 r1，6~8 位，
uint16_t r1 = (instr >> 6) & 0x7;

reg[r0] = ~reg[r1];

// 更新標(biāo)志寄存器
update_flags(r0);

JMP

JMP R1

跳轉(zhuǎn)指令，操作碼 1100，只有一個(gè)寄存器參數(shù)，在 6~8 位。作用是更新 PC 為寄存器的值。

指令布局如下：

image

代碼實(shí)現(xiàn)如下：

// 取出寄存器
uint16_t r1 = (instr >> 6) & 0x7;

// 更新 PC
PC = reg[r1];

RET

RET 并不在我們要實(shí)現(xiàn)的指令列表中。這里之所以單獨(dú)拎出來講，是因?yàn)?RET 是 JMP 指令的特例。

RET 是在函數(shù)調(diào)用完成后，用于恢復(fù) PC 寄存器的值。

只不過這時(shí)候寄存器固定是 R7，所以參數(shù)就為 111。如下圖所示：

image

也就相當(dāng)于：

RET = JMP R7

JSR

全稱為 Jump to Subroutine，也就是函數(shù)調(diào)用，操作碼 0100。

它有兩種模式，通過指令第 12 位 flag = instr[11] 來區(qū)分。

兩種模式的前置操作均為保存現(xiàn)場：將當(dāng)前 PC 值保存到 R7 中，目的是為了在函數(shù)調(diào)用完成之后恢復(fù)原 PC 值。

1. 標(biāo)簽?zāi)Ｊ?/strong>

JSR label

跳轉(zhuǎn)到 label 標(biāo)簽處的函數(shù)執(zhí)行，標(biāo)簽就是一個(gè)名稱。

注意，實(shí)際上 JSR 的參數(shù)是「相對于 PC 的偏移量」，是個(gè)數(shù)值，其中 PC 指向要執(zhí)行的下一條指令。因?yàn)樽罱K肯定是跳轉(zhuǎn)到某個(gè)地址。這里是匯編的形式說明用法。

另外，這里 PC 的含義跟前面文章中說的稍微有些區(qū)別，前面的 PC 指的是當(dāng)前執(zhí)行指令，這里指的是下一條指令。這對理解無大礙，只不過實(shí)現(xiàn)方式不一樣而已。

此時(shí)，flag = 1。 指令布局如下：

image

0~10 位為相對于 PC 的偏移量，將其取出來進(jìn)行符號擴(kuò)展，然后與 PC 相加。

// long_pc_offset
uint16_t long_pc_offset = sign_extend(instr & 0x7ff, 11);

// 更新 pc
PC += long_pc_offset;

2. 寄存器模式

JSRR R1

跳轉(zhuǎn)到 R1 寄存器中的地址，寄存器在 6~8 位。

此時(shí)，flag = 0。 指令布局如下：

image

取出寄存器，將 PC 更新為寄存器中的值即可。

// 取出寄存器
uint16_t r1 = (instr >> 6) & 0x7;

// 更新
PC = reg[r1];

BR

根據(jù)「條件標(biāo)志位」進(jìn)行跳轉(zhuǎn)，操作碼是 0000。跳轉(zhuǎn)參數(shù)是相對于 PC 的偏移量，在 0~8 位。

指令布局如下：

image

condition_flag 中包含 n/z/p 的狀態(tài)，只要任意一個(gè)狀態(tài)與當(dāng)前標(biāo)志寄存器相符，則進(jìn)行跳轉(zhuǎn)。

// 取出標(biāo)志參數(shù)
uint16_t cond_flag = (instr >> 9) & 0x7;

// 偏移量
uint16_t pc_offset = sign_extend(instr & 0x1FF, 9);

// 傳入標(biāo)識是否與標(biāo)志寄存器的值相符，n,z,p
if (cond_flag & COND)
{
    PC += pc_offset;
}

保留指令

RTI 和 RES 未使用，不處理即可。不過它們倒是可以用作占位指令，下面會講到。

手寫指令

實(shí)現(xiàn)了這么些指令，還得上手操練一下，檢查下正確性。可現(xiàn)在我們還沒有定義程序退出的指令，不然運(yùn)行虛擬機(jī)會進(jìn)入死循環(huán)。

LC-3 中的退出指令定義在 TRAP 系統(tǒng)調(diào)用中，后面的文章會專門講 TRAP 指令，操作碼是 1111。

那我們先簡單處理下，約定只要遇到操作碼是 1111 的指令，就認(rèn)為是程序退出，不用管后面的參數(shù)。所以暫且將退出指令定為 0xf000。

最后，我寫了些指令，不得不說真的很麻煩??。它的功能如下：

  • 先執(zhí)行兩個(gè) ADD 指令。
  • 執(zhí)行 JSR， 跳轉(zhuǎn)到第六條指令 RES。
  • 執(zhí)行 RES 指令，繼續(xù)執(zhí)行，直至退出。
// 內(nèi)存區(qū)
uint16_t mem[UINT16_MAX] = {
    // ADD R0,R1,R2
    0x1042,

    // ADD R1,R2,#6
    0x12A6,

    // JSR 2;
    // 下一條是第 4 條指令，PC=3，跳轉(zhuǎn)到 PC=3+2，也就是第 6 條指令 RES。
    0x4802,

    // JMP R1;跳轉(zhuǎn)到第 6 條指令
    0xC040,

    // RTI;占位
    0X8000,

    // RES;占位
    0XD000,

    // NOT R3, R1
    0x967F,

    // trap-halt
    0xf000,
};

為了方便調(diào)試，在每條指令執(zhí)行時(shí)，打印了當(dāng)前操作碼。指令執(zhí)行完成后，最后再打印出了 r0~r3 寄存器的值。

執(zhí)行完上述代碼后，結(jié)果如下所示：

exe op:ADD
exe op:ADD
exe op:JSR
exe op:RES
exe op:NOT
exe op:TRAP
r0,0
r1,6
r3,65529

另外，你也可以添加自己的指令試試，絕對值得體驗(yàn)一下效率暴跌的感覺??。

完整代碼可點(diǎn)此查看。

參考資料

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容