😴

Zig は状態機械の夢を見るか?

に公開
WebAssembly
CPU
Zig
6502
tech

Overview

今年で50周年を迎える 6502 CPU を、トリビュートとして Zig で書き直した時の話になります。Apple II やファミリーコンピュータとして世界的に有名なチップの話です

今回は Zig で書きましたが、命令セットは 56 程 (アドレッシングモードはあるものの) で、レジスタも十分にシンプルな構成となっており、今流行りの Rust の学習などにも最適な選択に思えます

他にもまったくの一人で完全理解可能で、比較的短期間で実装出来るアーキテクチャとして Z80 や 68k などあります。暇と興味があれば是非どうぞ (RISC-V もいいよ)

Source Code

私はこれを Nyxx と名付けました
https://github.com/keix/nyxx

Document

英語ですがこちらです
https://6502.notion.site/

Live Demo

WASM でコンパイルして JavaScript Runtime を走ります
https://6502.city

Web Interface

WebAssembly 呼び出しの JS コードはこちらです
https://github.com/keix/6502.city/tree/develop

Why Zig

前述した様にトリビュートという事ですが、Zig で書いた理由は、ネットを探しても Zig による NES 実装がほとんどなかった事と (最近では Rust ばかり) ハードウェアエミュレーションにおいて、Zig が非常に強力であるという事です

Architecture

実機のアーキテクチャでは CPU / PPU / APU という3つのユニットに分かれていて、CPU は Bus を経由して VRAM / WRAM を操作します

Nyxx では CPU は Bus のポインタしか持たず、Bus は PPU / APU を持ち、VRAM へのアクセスは PPU のみに依存します

Mnemonics

6502 ではニモニック自体の種類は決して多くありません。しかし、それを補うように アドレッシングモードが異常なほど柔軟で強力に設計されています。結果として、限られた命令でも多彩なメモリアクセス・即値操作・間接参照を実現でき、当時の 8bit CPU としては十分以上の表現力があります

本実装において CPU 構造体は、1 サイクルごとに後述する PC から命令をフェッチし、対応する処理にディスパッチするという、ごくシンプルなステップ構造を持っています

pub const CPU = struct {
    registers: Registers,
    bus: *Bus,
    
    pub fn step(self: *CPU) u8 {
        // Check for NMI before fetching instruction
        self.checkNMI();

        const instr = self.fetch();
        self.execute(instr);
        return self.calculateNextCycles(instr);
    }

    fn execute(self: *CPU, instr: Opcode.Instruction) void {
        switch (instr.mnemonic) {
            .LDA => self.opLda(instr.addressing_mode),
            .TAX => self.opTax(),
            ...
            .DCP => self.opDcp(instr.addressing_mode),
            .ISB => self.opIsb(instr.addressing_mode),
            else => {
                // std.debug.print("Unimplemented mnemonic: {}\n", .{instr.mnemonic});
            },
        }
    }
}

また Zig では、上記の様に構造体にメソッドを定義していても、それは実行時のオブジェクト指向的な振る舞いを意味しません。メソッドはコンパイル時に単なる関数として展開され、必要に応じてインライン化されます

構造体はあくまで C 同様に、純粋なメモリレイアウト (CPU レジスタや MMIO をそのまま表現できる) として扱われ、追加のランタイムコストを持ちません。これは Zig の持つ「ゼロコスト抽象」の特徴であり、エミュレータや OS のような低レイヤー開発において非常に相性が良い点です

Registers

A, X, Y の3つのレジスターと Stack Pointer, flags の8bitが5本と、PC として 16 bit が1本。これを Zig で実装すると以下の様になります

const Flags = packed struct {
    c: bool = false, // Carry
    z: bool = false, // Zero
    i: bool = false, // Interrupt Disable
    d: bool = false, // Decimal (unused in NES)
    b: bool = false, // Break
    _: bool = true, // Bit 5 is always set in NES
    v: bool = false, // Overflow
    n: bool = false, // Negative
};

const Registers = struct {
    // 6502 registers
    a: u8 = 0x00,
    x: u8 = 0x00,
    y: u8 = 0x00,
    s: u8 = 0xFD, // Stack pointer starts at 0xFD
    pc: u16 = 0x34,
    flags: Flags = .{}, // Default values are all false
};

初期化された状態でメモリに展開すると、期待するイメージは以下となり、メモリ上に 7 byte の領域を確保します

/* Registers struct */
00000000
00000000
00000000
11111101
00110100 00000001
00100000

例えば Flags の i を立てようと思った場合では以下の様に書けるのですが、十分過ぎるほどの糖衣で、完全に bit 単位の制御が可能であります

self.registers.flags.i = true;  // IRQを禁止

当然ながらメモリは以下の様に変化します

/* Registers struct */
00000000
00000000
00000000
11111101
00110100 00000001
00100100 // 1 bit だけ変化

比較として Python で書くなら、bool オブジェクトひとつで 24~28byte となります

$ python
Python 3.10.0 (default, Aug 28 2024, 03:56:33) [GCC 13.2.1 20240210] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.getsizeof(True)
28
>>> sys.getsizeof(False)
24

A (Accumulator)

中央的なレジスタで、算術演算 (ADC, SBC, AND, ORA, EOR …) も メモリとのやり取り (LDA, STA) も全部 A を経由しています。プログラムの「実務」を担うレジスタで、ほとんどの命令が A を前提にしていると言っても問題ないレベルです

X / Y (Index Registers)

アドレス計算の補助に特化しています。繰り返し処理やテーブルアクセスに便利です

SP (Stack Pinter)

6502 のスタックポインタ（SP）は 8bit しかありませんが、実際にアクセスされるアドレスは 16bit です。上位 8bit は常に $01 に固定されており、SP の値はその下位 8bit 部分として使われます

つまり SP は「$0100〜$01FF の 256バイト（=1ページ）」を指すためのオフセットとして働き、この範囲をスタック領域として実装しています

PC (Program Counter)

PC (Program Counter) は、CPU が次に実行する命令のアドレスを保持するレジスタで x86_64 の RIP に相当します。命令実行ごとに自動で進みますが、ジャンプ命令や割り込みにより書き換えられることもあります

Memory Mapped I/O

メモリ領域は CPU / WRAM 2KB, PPU / VRAM 2KB を搭載しています。それ以外は別デバイスへの読み書きと、ミラーリングとして機能します。アクセス可能な領域は 16bit アドレスとなります

CPU

アドレス範囲 サイズ 用途 備考
$0000 - $07FF 2 KB 内蔵RAM ミラーリングあり
$0800 - $0FFF 2 KB ミラー1 $0000 - $07FF にミラー
$1000 - $17FF 2 KB ミラー2 同上
$1800 - $1FFF 2 KB ミラー3 同上
$2000 - $2007 8 bytes PPU レジスタ PPU I/O
$2008 - $3FFF 8 bytes × 1024 PPU レジスタミラー $2000 - $2007 を繰り返し
$4000 - $4017 24 bytes APU & I/O レジスタ パッド入力やDMA含む
$4018 - $401F 8 bytes テストモード/未使用 一部拡張音源で使用
$4020 - $5FFF ~8 KB 拡張ROM/拡張RAM 一部カートリッジで使用される
$6000 - $7FFF 8 KB SRAM バッテリ付きカートリッジ用
$8000 - $FFFF 32 KB PRG-ROM カートリッジ上のプログラム本体

CPU $2006 への書き込みで PPU レジスタに VRAM アドレスを書き込み、$2007 へ書き込む事で、PPU は VRAM に値を書き込みます

PPU

アドレス範囲 サイズ 内容 説明
$0000 - $0FFF 4KB パターンテーブル 0 背景やスプライトのタイル定義
$1000 - $1FFF 4KB パターンテーブル 1 同上
$2000 - $23FF 1KB ネームテーブル 0 背景マップ（名前テーブル）
$2400 - $27FF 1KB ネームテーブル 1
$2800 - $2BFF 1KB ネームテーブル 2
$2C00 - $2FFF 1KB ネームテーブル 3
$3000 - $3EFF 4KB ネームテーブルミラー $2000〜$2FFF のミラー
$3F00 - $3F1F 32B パレットテーブル 背景用とスプライト用の色定義
$3F20 - $3FFF 224B ミラーリングされたパレット $3F00〜$3F1F のミラー

物理的な VRAM 領域は 2KB で、ユーザーが見ている画面を構成するために 1KB (厳密には 960 bytes + 64 bytes) が必要となります

8x8 pixel のタイルを 32x30 枚展開し、見えていない部分を先に書き直して、スクロールした後でも画面が続いている様に見せているイメージとなります

バイナリヘッダーから垂直・水平で折り畳む方向を取得してミラーリングする事で、マップされる領域を 4KB に拡張し、ROM プログラマは 4枚 の画面へのアクセスを可能にします

  • プレイヤーが見ている画面 - 1枚 (1KB)
  • 物理 VRAM サイズ - 2枚 (2KB)
  • ROM プログラマが見ている画面 - 4枚 (4KB)
pub const VRAM = struct {
    memory: [0x800]u8 = [_]u8{0} ** 0x800,
    palette: [32]u8 = [_]u8{0} ** 32,
    buffer: u8 = 0, // Buffer for PPU data reads
    mirroring: Mirroring,

    ...

    fn resolveMirroredAddr(self: *VRAM, addr: u16) u16 {
        const offset = addr - 0x2000;
        const name_table_index = offset / 0x400;
        const local_offset = offset % 0x400;

        return switch (self.mirroring) {
            .Vertical => switch (name_table_index) {
                0, 2 => local_offset,
                1, 3 => 0x400 + local_offset,
                else => std.debug.panic("Invalid name table index: {d}", .{name_table_index}),
            },
            .Horizontal => switch (name_table_index) {
                0, 1 => local_offset,
                2, 3 => 0x400 + local_offset,
                else => std.debug.panic("Invalid name table index: {d}", .{name_table_index}),
            },
        };
    }
};

実装を整理すれば以下の様になります

PPU Address Space (0x2000〜0x2FFF) — 4KB（論理上の4画面）
 ├─ Name Table #0 (0x2000〜0x23FF)
 ├─ Name Table #1 (0x2400〜0x27FF)
 ├─ Name Table #2 (0x2800〜0x2BFF)
 └─ Name Table #3 (0x2C00〜0x2FFF)

Physical VRAM (0x000〜0x7FF) — 2KB（実体は2面だけ）
 ├─ Physical Table A (0x000〜0x3FF)
 └─ Physical Table B (0x400〜0x7FF)

Mirroring (iNES Header の設定により割り当てが決まる)
 ├─ Vertical   → NT0/A, NT1/B, NT2/A, NT3/B
 └─ Horizontal → NT0/A, NT1/A, NT2/B, NT3/B

VRAM 2KB に対して、アドレス空間上は 4KB の画面が存在するように見せる。わずかな物理リソースを巧妙に折り畳み、論理的な世界を成立させる。この矛盾を破綻なく実現しているのが、ファミコンの PPU という装置です

そして、この”論理と物理の差をどう扱うか”という問題は、CPU や OS、エミュレーションの世界では常に現れるテーマでもあります。Zig はこの構造を曖昧にせず、メモリレイアウトも状態遷移も、すべてをそのまま書ける言語です

Zig は状態機械の夢を見る。Nyxx という小さなエミュレータを書く事で、半世紀前に生まれた小さなチップとともに、その夢の続きを見ているのは私なのかもしれません

Acknowledgments

Special thanks to the pioneers of the 6502, to the NES community, and to everyone who continues to explore low-level systems with curiosity.

My gratitude also goes to the Advent Calendar organizers for giving me the opportunity to share this project. Your work made Nyxx possible.

Discussion