本文將探討堆疊（Stack）的運作原理，並依據 CHIP-8 的硬體規格實作堆疊資料結構，以及如何在 CHIP-8 模擬器中實作十六進制的虛擬鍵盤。
堆疊實作
在開發處理器或虛擬機時，堆疊（Stack）是一項不可或缺的機制，它讓程式能夠執行 subroutine 的呼叫以及 recursion。
在 CHIP-8 模擬器中，實作堆疊不僅是模擬硬體的必要步驟，更是確保相關指令（如 CALL 與 RET）能正確執行的基礎。接下來介紹一下原理吧！
堆疊的運作原理
我想應該蠻多人都聽過用洋芋片的譬喻：當我們把一片洋芋片放進去洋芋片筒時這個動作是 push，如果再放入第二個洋芋片，就會疊在第一片的上面。若需要洋芋片，我們就會需要拿走最上面，也就是最後一個放上去的洋芋片，這個動作叫做 pop。這個資料結構機制也就是「後進先出」（Last In, First Out，LIFO），我們會利用 stack 用來儲存虛擬機的 return address。
CHIP-8 堆疊規格與應用場景
常見的 CHIP-8 實作會配置一個可保存 16 個位址的堆疊，每個堆疊元素皆為 16-bit，因此最多可以保存 16 層副程式呼叫狀態。
當虛擬機執行 CALL 指令時，系統會將 return address 推入堆疊，接著把 PC 設定為副程式的起始位址。當副程式執行完畢並遇到 RET 指令時，系統會從堆疊中彈出先前保存的 return address，並將 PC 設定回該位址，讓程式從原本中斷的位置繼續執行。
堆疊 push 的具體 PC 數值會受到模擬器取指流程影響。例如，有些實作會在執行操作碼前先將 PC 增加 2，此時堆疊中保存的就已經是下一條指令的位址。只要 CALL 與 RET 的處理方式保持一致即可。
在專案中，我們首先在 config.h 定義一個常數 CHIP8_TOTAL_STACK_DEPTH 並設為 16。
#define CHIP8_TOTAL_STACK_DEPTH 16
接著，建立一個堆疊專屬的標頭檔 chip8_stack.h，在其中宣告一個名為 chip8_stack 的結構體，內部包含一個由 unsigned short 構成、大小為 16 的陣列（共佔用 32 位元組的記憶體空間）。
#include "config.h"
struct chip8;
struct chip8_stack
{
unsigned short stack[CHIP8_TOTAL_STACK_DEPTH];
};
特別需要注意的是，為了解決標頭檔互相引入所造成的循環相依問題，並讓函式宣告可以使用尚未完整定義的結構型態，須在此處使用前向宣告來參照 chip8 主結構體，而非直接 include 它。
當然在 chip8 內要引入 stack：
#include "chip8_stack.h"
struct chip8
{
...
struct chip8_stack stack;
};
實作 Push 與 Pop 函式
為了方便且安全地操作堆疊，我們會建立對應的檔案 chip8_stack.c，並實作兩個核心函式：
chip8_stack_pushchip8_stack_pop
Push 函式
chip8_stack_push 函式負責接收 CHIP-8 實例指標與要推入的位址數值。函式內部會將該數值存入陣列中當前堆疊指標（SP）所指向的索引位置，接著將堆疊指標加一（SP += 1）。
void chip8_stack_push(struct chip8* chip8, unsigned short value)
{
chip8->stack.stack[chip8->registers.SP] = value;
chip8->registers.SP++;
}
例如，當 SP 為 0 時，第一個數值會寫入 stack[0]，完成後 SP 會變成 1，指向下一個可用位置。
Pop 函式
chip8_stack_pop 的操作順序正好相反。因為 SP 指向的是下一個可寫入的位置，所以 pop 時必須先將 SP 減一，再讀取該位置的數值。
unsigned short chip8_stack_pop(struct chip8* chip8)
{
chip8->registers.SP--;
unsigned short value = chip8->stack.stack[chip8->registers.SP];
return value;
}
備註：spec 中的描述是「先增加指標再存入」，但因為 CHIP-8 的堆疊指標是一個無法被內部程式直接讀取的偽暫存器，因此實作時不必拘泥於特定的內部表示方式，只要 Push、Pop、CALL 與 RET 使用一致的規則即可。
邊界檢查與整合測試
引入斷言
為了防止堆疊 overflow，我們也是一樣透過引入 <assert.h> 函式庫，建立了一個 chip8_stack_in_bounds 的靜態檢查函式。
#include <assert.h>
static void chip8_is_stack_in_bounds(struct chip8* chip8)
{
assert(chip8->registers.SP < CHIP8_TOTAL_STACK_DEPTH);
}
該函式會斷言堆疊指標必須嚴格小於 CHIP8_TOTAL_STACK_DEPTH（即 16）。
由於我們將堆疊指標宣告為無號整數（Unsigned），其值永遠不為負數，因此目前先簡單實做概念的狀況下，就先不用檢查它是否小於零。這個邊界檢查函式會在 Push 寫入前，以及 Pop 指標遞減後被呼叫，確保記憶體存取安全。
再回到剛才的 pop 和 push 函式，新增邊界檢查：
void chip8_stack_push(struct chip8* chip8, unsigned short value)
{
chip8_is_stack_in_bounds(chip8); // 操作前先檢查
chip8->stack.stack[chip8->registers.SP] = value;
chip8->registers.SP++;
}
unsigned short chip8_stack_pop(struct chip8* chip8)
{
chip8->registers.SP--;
chip8_is_stack_in_bounds(chip8); // 操作前先檢查
unsigned short value = chip8->stack.stack[chip8->registers.SP];
return value;
}
主程式測試
實作完成後，需要將 chip8_stack.o 加入 Makefile 的編譯與連結規則中，這基本常識就不再多提（先前實做也是都要留意 Makefile 是否有更新）。
最後，我們可以在 main.c 中進行簡單的測試：依序將 0xFF 與 0xAA 兩個數值推入堆疊，接著連續呼叫兩次 pop 函式並將結果列印至終端機。
int main(int argc, char** argv)
{
struct chip8 chip8;
chip8.registers.SP = 0;
// Test stack functions
chip8_stack_push(&chip8, 0xff);
chip8_stack_push(&chip8, 0xaa);
printf("Popped value: %x\n", chip8_stack_pop(&chip8));
printf("Popped value: %x\n", chip8_stack_pop(&chip8));
return 0;
}
執行程式後，由於堆疊「後進先出」的特性，終端機應如預期印出 AA 接著 FF，這標誌著我們的堆疊模組已成功建置並可供後續的指令集使用了。
建立鍵盤輸入
最初使用 CHIP-8 語言的電腦，配備的是一組擁有十六個按鍵的十六進位鍵盤，按鍵範圍為 0 到 F，可參考先前規格介紹文章中的 Keyboard 段落。
由於現代電腦通常不具備這種鍵盤配置，我們無法直接讓使用者操作原始的 CHIP-8 按鍵。因此，需要在模擬器中建立一組虛擬鍵盤，並將桌面鍵盤上的實體按鍵對映至 CHIP-8 的 16 個虛擬按鍵。
接下來就要詳細介紹如何建構這個鍵盤模組，並將它整合至 SDL 的事件處理流程中。
鍵盤資料結構與基本設定
首先一樣在設定檔（config.h）中定義一個常數 CHIP8_TOTAL_KEYS 並賦值為 16，代表 CHIP-8 鍵盤的按鍵總數。
#define CHIP8_TOTAL_KEYS 16
接著建立標頭檔（chip8_keyboard.h），宣告一個包含 boolean 陣列的結構體。
#include "config.h"
#include <stdbool.h>
struct chip8_keyboard
{
bool keyboard[CHIP8_TOTAL_KEYS];
};
使用 boolean 是為了記錄每個按鍵目前的狀態：true 代表按鍵被按下（down），false 代表按鍵被放開（up）。
實作按鍵狀態管理函式
為了操作這個鍵盤陣列，我們在 chip8_keyboard.c 中實作了三個核心函式：
- 按下按鍵（Down）：
chip8_keyboard_down接收鍵盤指標與按鍵索引，將陣列中對應的位置設為true。 - 放開按鍵（Up）：
chip8_keyboard_up的運作方式相同，但會將陣列中的狀態設為false。 - 檢查狀態（Is Down）：
chip8_keyboard_is_down會回傳指定按鍵當前的布林狀態，讓模擬器知道某個鍵是否正被按下。
（老實說我覺得命名蠻爛的XDD 等整體完成後來調整一下）
void chip8_keyboard_down(struct chip8_keyboard* keyboard, int key)
{
keyboard->keyboard[key] = true;
}
void chip8_keyboard_up(struct chip8_keyboard* keyboard, int key)
{
keyboard->keyboard[key] = false;
}
bool chip8_keyboard_is_down(struct chip8_keyboard* keyboard, int key)
{
return keyboard->keyboard[key];
}
邊界檢查與安全防護
上述函式接收的 key 參數代表虛擬鍵盤的索引值，合法範圍為 0 到 15。
為了防止陣列越界存取，和先前一樣引入 <assert.h> 來進行邊界檢查。斷言機制會確保傳入的按鍵索引必須大於或等於零，並且嚴格小於總按鍵數。
#include <assert.h>
static void chip8_keyboard_is_key_valid(int key)
{
assert(key >= 0 && key < CHIP8_TOTAL_KEYS);
}
void chip8_keyboard_down(struct chip8_keyboard* keyboard, int key)
{
chip8_keyboard_is_key_valid(key); // 加入檢查
keyboard->keyboard[key] = true;
}
void chip8_keyboard_up(struct chip8_keyboard* keyboard, int key)
{
chip8_keyboard_is_key_valid(key); // 加入檢查
keyboard->keyboard[key] = false;
}
bool chip8_keyboard_is_down(struct chip8_keyboard* keyboard, int key)
{
chip8_keyboard_is_key_valid(key); // 加入檢查
return keyboard->keyboard[key];
}
按鍵對映機制
使用者實際按下的是桌面鍵盤，因此還需要一個函式，將 SDL 接收到的實體按鍵代碼轉換成 CHIP-8 虛擬按鍵。
以下使用 chip8_keyboard_map 函式，接收一份按鍵對映表，以及使用者實際按下的 SDL 按鍵代碼：
int chip8_keyboard_map(const char* map, char key)
{
for (int i = 0; i < CHIP8_TOTAL_KEYS; i++)
{
if (map[i] == key)
{
return i;
}
}
return -1;
}
這個函式會透過迴圈遍歷按鍵對映陣列中的 16 個元素，檢查陣列中的值是否與使用者按下的實體按鍵相符。如果找到相符的按鍵，就回傳該元素的索引值。這個索引值正好代表 CHIP-8 虛擬鍵盤上的按鍵（例如索引 5 代表虛擬按鍵 5）。
如果迴圈結束後仍未找到，則回傳 -1，代表該實體按鍵未被對映。
接著，我們宣告一個常數陣列，將 SDL 函式庫提供的鍵盤代碼（如 SDLK_0、SDLK_a 等）填入陣列中，藉此建構出完整的對映表。
// Corresponds to CHIP-8 keys:
// 1 2 3 C
// 4 5 6 D
// 7 8 9 E
// A 0 B F
const char keyboard_map[CHIP8_TOTAL_KEYS] = {
SDLK_x, SDLK_1, SDLK_2, SDLK_3, SDLK_q, SDLK_w, SDLK_e, SDLK_a, SDLK_s, SDLK_d, SDLK_z, SDLK_c, SDLK_4, SDLK_r, SDLK_f, SDLK_v
};
整合 SDL 事件處理
最後，一樣將實作好的模組加入 Makefile 進行編譯，並在主程式中與 SDL 整合。
在處理 SDL 事件的迴圈中，我們使用 switch 語法來捕捉 SDL_KEYDOWN 與 SDL_KEYUP 事件。當捕捉到鍵盤事件時，先取得使用者按下或放開的實體按鍵代碼，再將其傳入對映函式，轉換為 CHIP-8 的虛擬按鍵索引。
如果回傳值不為 -1，就呼叫對應的狀態管理函式，更新虛擬硬體的狀態，這樣我們就成功模擬了 CHIP-8 的第一件硬體設備：
while(SDL_PollEvent(&event))
{
switch (event.type)
{
case SDL_QUIT:
goto out;
case SDL_KEYDOWN:
{
char key = event.key.keysym.sym;
int vkey = chip8_keyboard_map(keyboard_map, key);
if (vkey != -1)
{
chip8_keyboard_down(&chip8.keyboard, vkey);
printf("Key is down: %x\n", vkey);
}
}
break;
case SDL_KEYUP:
{
char key = event.key.keysym.sym;
int vkey = chip8_keyboard_map(keyboard_map, key);
if (vkey != -1)
{
chip8_keyboard_up(&chip8.keyboard, vkey);
printf("Key is up.\n");
}
}
break;
default:
break;
}
}
完成整合後，使用者的桌面鍵盤輸入會經過以下流程：
桌面鍵盤輸入 -> SDL 鍵盤事件 -> 實體按鍵對映 -> CHIP-8 虛擬按鍵狀態後續在實作鍵盤相關操作碼時，就能透過 chip8_keyboard_is_down 查詢指定按鍵目前是否被按下。
後記
這邊一樣紀錄未來可能會修改的點：
- 堆疊的 push 與 pop 分別檢查 overflow 與 underflow，可能不能共用同一個「小於 16」條件。
- 型態方面也是一樣或許要改使用
uint16_t，明確表示堆疊元素為 16-bit。
