尝试将上世纪 70 年代的 6502 CPU 的指令翻译成 JS 代码
去年折腾的一个东西，之前 blog 里也写过，不过那时边琢磨边写，所以比较杂乱，现在简单完整地讲解一下。
前言
当时看到一本虚拟机相关的书，正好又在想 JS 混淆相关的事，无意中冒出个想法：能不能把某种 CPU 指令翻译成等价的 JS 逻辑？这样就能在浏览器里直接运行。
注意，这里说的是「翻译」，而不是模拟。模拟简单多了，网上甚至连 JS 版的 x86 模拟器都有很多。
翻译原则上应该在运行之前完成的，并且逻辑上也尽可能做到一一对应。
为了尝试这个想法，于是选择了古董级 CPU 6502 摸索。一是简单，二是情怀~（曾经玩红白机时还盼望能做个小游戏，不过发现 6502 非常蛋疼而且早就过时了，还不如学点 VBScript 做网页版的小游戏~）
网上 6502 资料很多，比如这里有个 简单教程并自带模拟器，可以方便测试。
顺便再分享几个有趣的：
- 6502 —— 伟大的心（上）
- 6502 芯片视觉图
简单的指令很容易翻译
对于简单的指令，其实是很容易转成 JS 的，比如
STA 100
指令，就是把寄存器 A 写到地址空间 100 的位置。因为 6502 是 8 位 CPU，不用考虑内存对齐这些复杂问题，所以对应的 JS 很简单：
mem[100] = A;
由于 6502 没有 IO 指令，而是通过 Memory Mapped IO 实现的，所以理论上「写入空间」不一定就是「写入内存」，也有可能写到屏幕、卡带等设备里。不过暂时先不考虑这个，假设都是写到内存里：
var mem = new Uint8Array(65536);
同样的，读取操作也很简单，就是得更新标记位。为了简单，可以把状态寄存器里的每个 bit 定义成单独的变量：
// SR: NV-BDIZC
var SR_N = false,
SR_V = false,
SR_B = false,
...
SR_C = false;
比如翻译
LDA 100
这条指令，变成 JS 就是这样：
A = mem[100];
SR_Z = (A == 0);
SR_N = (A > 127);
类似的，数学计算、位运算等都是很容易翻译的。但是，跳转指令却十分棘手。
因为 JS 里没有 goto，流程控制能力只能到语块，比如 for 里面可以用 break 跳出，但不能从外面跳入。
而 6502 的跳转可以精确到字节的级别，跳到半个指令上，甚至跳到指令区外，将数据当指令执行。
这样灵活的特征，光靠「翻译」肯定是无解的。只能将模拟器打包进去，普通情况执行翻译的 JS ，遇到特殊情况用模拟解释执行，才能凑合着跑下去。
退一步考虑
不过为了简单，就不考虑特殊情况了，只考虑指令区内跳转，并且没有跳到半个指令中间，也不考虑指令自修改的情况，这样就容易多了。
仔细思考，JS 能通过 break、return、throw 等跳出语块，但没有任何「跳入语块」的能力。所以，要避开跳入的逻辑。
于是想了个方案：把指令中「能被跳入的地方」都切开，分割成好几块：
-------------
XXX 1 | block 0 |
JXX L2 --. | |
XXX 2 | | |
L1: | <-. ~~~~~~~~~~~~~~~~~~~
XXX 3 | | | block 1 |
XXX 4 | | | |
L2: <-| | ~~~~~~~~~~~~~~~~~~~
XXX 5 | | block 2 |
XXX 6 | | |
JXX L1 --| | |
XXX 7 -------------
这样每个块里面只剩跳出的，没有跳入的。
然后把每个块变成一个 function，这样就能通过「函数变量」控制跳转了：
var nextFn = block_0; // 通过该变量流程控制
function block_0() {
XXX 1
if (...) { // JXX L2
nextFn = block_2;
return;
}
XXX 2
nextFn = block_1 // 默认下一块
}
function block_1() {
XXX 3
XXX 4
nextFn = block_2 // 默认下一块
}
function block_2() {
XXX 5
XXX 6
if (...) { // JXX L1
nextFn = block_1;
return;
}
XXX 7
nextFn = null // end
}
于是用一个简单的状态机，就能驱动这些指令块：
while (nextFn) {
nextFn();
}
不过有些程序是无限循环的，例如游戏。这样就会卡死浏览器，而且也无法交互。
所以还需增加个控制 CPU 周期的变量，能让程序按照理想的速度运行：
function block_1() {
...
if (...) {
nextFn = ...
cycle_remain -= 8 // 在此跳出，当前 block 消耗 8 周期
return
}
...
cycle_remain -= 12 // 运行到此，当前 block 消耗 12 周期
}
...
// 模拟 1MHz 的速度（如果使用 50FPS，每帧就得跑 20000 周期）
setInterval(function() {
cycle_remain = 20000;
while (cycle_remain > 0) {
nextFn();
}
}, 20);
虽然函数之间切换会有一定的开销，但总比无法实现好。比起纯模拟，效率还是高一些。
借助现成工具实现
不过上述都是理论探讨而已，并没有实践尝试。因为想到个更取巧的办法，可以很方便实现。
因为 emscripten 工具可以把 C 程序编译成 JS，所以不如把 6502 翻译成 C 代码，这样就简单多了，毕竟 C 支持 goto。
于是写了个小脚本，把 6502 汇编码转成 C 代码。比如：
$0600 LDA #$01
$0602 STA $02
$0604 JMP $0600
变成这样的 C 代码：
L_0600: A = 0x01; ...
L_0602: write(A, 0x02);
L_0604: goto L_0600;
事实上 C 语言有「宏」功能，所以可将指令逻辑隐藏起来。这样只需更少的转换，符合基本 C 语法就行：
L_0600: LDA(0x01)
L_0602: STA(0x02)
L_0604: JMP(0600)
对应的宏实现，可参考这个文件：6502.h
对于「动态跳转」的指令，可通过运行时查表实现：
jump_map:
switch (pc) {
case 0x0600: goto L_0600;
case 0x0608: goto L_0608;
case 0x0620: goto L_0620;
...
}
然后再实现基本的 IO，可通过 emscripten 内置的 SDL 库实现。C 代码的主逻辑大致就是这样：
void render() {
cycle_remain = N;
input(); // 获取输入
update(); // 指令逻辑（执行到 cycle_remain <= 0）
output(); // 屏幕输出
}
// 通过浏览器的 rAF 接口实现
emscripten_set_main_loop(render);
演示
我们尝试将一个 6502 版的「贪吃蛇」翻译成 JS 代码。
这是 原始的机器码：
20 06 06 20 38 06 20 0d 06 20 2a 06 60 a9 02 85
02 a9 04 85 03 a9 11 85 10 a9 10 85 12 a9 0f 85
14 a9 04 85 11 85 13 85 15 60 a5 fe 85 00 a5 fe
....
ea ca d0 fb 60
通过现成的反编译工具，变成 汇编码：
$0600 20 06 06 JSR $0606
$0603 20 38 06 JSR $0638
$0606 20 0d 06 JSR $060d
$0609 20 2a 06 JSR $062a
$060c 60 RTS
$060d a9 02 LDA #$02
....
$0731 ca DEX
$0732 d0 fb BNE $072f
$0734 60 RTS
然后通过小脚本的正则替换，变成符合 C 语法的 代码：
L_0600: JSR(0606, 0600)
L_0603: JSR(0638, 0603)
L_0606: JSR(060d, 0606)
L_0609: JSR(062a, 0609)
L_060c: RTS()
L_060d: LDA_IMM(0x02)
....
L_0731: DEX()
L_0732: BNE(072f)
L_0734: RTS()
最后使用 emscripten 将 C 代码编译成 JS 代码：
在线演示（ASDW 控制方向，请用 Chrome 浏览器）
当然，这种方式虽然很简单，但生成的 JS 很大。而且所有的 6502 指令对应的 JS 最终都在一个 function 里面，对浏览器优化也不利。
2018-01-25 更新
有天在 GitHub 上看到有人把原版的《超级玛丽》汇编加上了详细的注释： https://gist.github.com/1wErt3r/4048722，立即回想起了本文。
于是在此基础上做了一些改进，加上了 NES 的图像、声音、手柄等接口。由于《超级玛丽》游戏的中断（NMI）逻辑很简单，只需简单定时调用即可，无需处理 CPU 周期等复杂的问题，因此很容易翻译。
然后用同样的方式，将 6502 ASM 翻译成 C，然后再通过 emscripten 编译成 JavaScript：
演示： https://www.etherdream.com/FunnyScript/smb-js/game.html
（由于最新版的浏览器会把 asm.js 代码自动转成 WebAssembly，所以部分浏览器初始化比较慢，比如 Chrome 启动需要等好几秒。像 FireFox 会缓存 asm.js 的解析，所以只有首次加载会慢）
需要注意的是，这不是模拟器！最明显的特征，就是性能。
点击 Benchmark 按钮可测试游戏逻辑的极限 FPS，目前最快的是 Firefox，在我笔记本上可以跑到 19 万 FPS ！就算 IE10 也能跑到 600 FPS。（ IE10 以下的浏览器不支持）
当然，这还只是没做任何性能优化的结果，之后还会尝试更好的翻译方案，比如指令层的 call/jump 尽可能翻译成代码层的函数调用、高级分支等。希望能达到 50 万 FPS 以上 😀