L0: 直接运行在硬件上的小游戏 (amgame)

注意事项

请特别注意 academic integrity：“看见” 他人的代码、使用他人测试用例都是不道德的行为。只有遵守 academic integrity 才会使你受到真正的训练。在这个实验中，你应当主动地避免阅读任何人 (包括互联网) 上打印进程树或进程列表的代码。遇到问题时尽量自己调试解决，但可以向他人请教调试的技巧。

关于实验环境设置、提交方法、评分规则等，请阅读实验须知。获取代码后，在 os-workbench 中执行 git pull origin L0 下载代码。

---

Soft Deadline: 2020 年 3 月 28 日 23:59:59。

1. 背景

大家当然希望在《操作系统》课写一个自己的操作系统——但又多多少少有点怕怕的。一个普遍 (但片面) 的认识是写操作系统就是 “写汇编”、“跟底层硬件打交道”。也恰恰是因为计算机硬件对大众的 “神秘性”，成为广大爱好者们证明自己实力的象征。网上有不少教程：30 天自制操作系统、Orange's OS, XXX (JamesM, Bran, ...)'s Kernel Development Tutorial……这些材料通常会从硬件的底层开始介绍 (通常是 i386)：什么是 GDT, IDT, TSS、系统启动的过程……这些复杂而又琐碎的细节又劝退了很多人；而这些教程又大多是基于老旧的 i386 体系结构，看到 x86-64 复杂的手册又感到更害怕了，又不想学习 ARM 的汇编……？

实际上，操作系统和硬件之间的关系被夸大了。操作系统不过是一个直接运行在计算机上的 (高级语言) 程序，只是会在适当的时候调用操作系统提供的机制 (mechanisms)。在这门课程的 OSLab 系列实验中，我们就顺着 “操作系统是一个 C 程序” 的理解，开始对 “裸机” (bare-metal) 的编程。

在初始化完成后设置好一个没有标准库的 C 程序运行环境，其中有栈区、静态数据、堆区；代码从 main 函数开始执行，并允许我们在 C 代码运行的过程中直接、独占式地访问系统中的物理设备 (例如显示器、计时器) 和响应中断，我们就可以完全可以实现今天大家看到的操作系统。

2. 实验描述

2.1.实现 AbstractMachine 中 klib 中缺失的函数 (选做)

关于 AbstractMachine，请首先阅读 AbstractMachine 文档。AbstractMachine 的项目中包含一个基础运行库的框架 klib，其中包含了方便你编写 “bare-metal” 程序的系列库函数，例如 assert, printf, memcpy 等。我们不强制你实现所有 klib 函数，但随着操作系统实验的进展，不实现库函数将会使你寸步难行。

如果你在《计算机系统基础》中已经完成了实现，你可以直接复制你的实现 (但要小心！你的库实现可能有 bug，或是不能在多处理器的情况下工作)。这部分代码非常重要——会一直使用到这学期的最后，因此也请你非常小心地编写代码；klib 中的 bug 会使原本就已很困难的操作系统内核调试更加令人沮丧。

2.2. 实现可移植的、直接运行在计算机硬件上的小游戏 (必做)

你需要编写一个直接运行在 AbstractMachine 上 (仅仅启用 IOE 扩展，不使用其他硬件机制如中断/异常/虚拟存储/多处理器) 的小游戏；满足：

1. 有肉眼可辨认的图形输出；
2. 能使用键盘与游戏交互；
3. 游戏使用的内存 (代码、静态数据总和不超过 1 MiB、堆区 _heap 使用不超过 1 MiB)，因此你不必考虑复杂的图形；
4. 按 ESC 键后调用 _halt() 退出；除此之外游戏程序永不调用 _halt() 结束，Game Over 后按键重新开始。

只要程序不崩溃，哪怕只有几个像素点在屏幕上乱动也可以 (就可以获得 Online Judge 测试通过)，送分属性明显，但大家也可以根据自己的兴趣实现一些简单的游戏。

虽然不限实现什么游戏 (简单到弹球、贪吃蛇等 100 行以内搞定的游戏)，但你依然需要在可移植性/通用性上对你的代码做出一定的保证：

• 兼容很简单的处理器：即小游戏运行中只调用 TRM 和 IOE API，而不使用其他 API，且——这样大家的游戏就可以在各个 CPU 上广为流传下去啦！
• 你的游戏应当是可以在多个硬件体系结构之间移植的，考虑兼容以下情况：
  • 适配不同的屏幕大小。不同的体系结构中，屏幕大小可能是 $320\times 200$、$640 \times 480$、$800 \times 600$ 等，你的游戏最好能在所有分辨率下都获得不错的体验；
  • 同 minilabs 一样，你的程序可能运行在 32/64-bit 平台，因此你应当使用 intptr_t 或 uintptr_t 来保存指针数值；
  • 兼容大/小端，因此禁止把不同大小的指针类型强制转换；

我们会在 x86_64-qemu (64-bit) 和 x86-qemu (32-bit) 两个环境下运行你的游戏，你的游戏必须在两个环境下都能正确编译并运行良好。此外，AbstractMachine 假设 bare-metal 不支持浮点数指令。在 x86_64 的编译选项中，我们添加了 -mno-sse。尽管有浮点数的程序在 ARCH=native 下可以正确编译运行，但可能在其他架构下失效。这么做的目的是使 AbstractMachine 程序能运行在各种 (简化) 的处理器上；尤其是同学们自己编写的处理器——也许下个学期你就可以在自己的 CPU 上运行你自己的游戏了！

在我们的 am-kernels 项目中包含了一些运行在 AbstractMachine 上的代码，例如 NES 模拟器 LiteNES，欢迎大家参考——LiteNES 只使用了 IOE 的 API，和这个实验中你们所需要实现的类似。

可选项：考虑游戏性能

你的游戏可能运行在频率仅有 10MHz 的自制处理器上。因此，如果你希望你的游戏能在未来你自己写的处理器上流畅运行，减少每一帧的运算量和图形绘制就显得比较重要了。你可以计算出一个时钟周期大致允许运行的代码量 (假设绘制一个像素也需要若干条指令)，相应设计游戏的逻辑。

我们认为优秀的游戏会被收录到游戏池中，永久保存下来！

3. 正确性标准

本实验对游戏不做任何要求：你只需要响应键盘输入、输出变化的图形即可；任何游戏都是可以的。Online Judge 会：

1. 通过 qemu 的 -m 选项限制内存的大小；使用超过规定的内存可能导致程序 crash；
2. 在不同的环境下 (x86-qemu 或 x86_64-qemu, native) 运行你的程序，并且可能修改屏幕的分辨率；
3. 随机发送一定的键盘事件。

但 Online Judge 不试图理解游戏的逻辑，只做基本的正确性检查：

1. 除非按 ESC 键，我们假设游戏程序不结束；如果检测到 _halt() 的调用 (包括 assert 失败，我们可能会增加一些额外的合法性检查)，将判定为错 (Runtime Error 或 Wrong Answer)；
2. 如果按 ESC 键后游戏不 _halt()，将判定为错；
3. 如果虚拟机或进程发生崩溃、非预期的重启等 (由 undefined behavior 导致，例如访问某非法内存可能导致异常或 CPU Reset)，则被判定为错；
4. 其他违反 specifications 的问题，如在 _ioe_init() 之前调用 _io_read/_io_write，将被判定为错。

此外，我们会链接我们 klib 的参考实现，因此你不必担心你的 klib 有些许问题；但你要保持 klib 库函数的行为与 libc 一致。注意 native 会链接系统本地的 glibc (而非 klib)。

4. 实验指南

AbstractMachine 文档 和 AbstractMachine 项目中附带的代码 (包括 amgame) 是本次实验的主要阅读材料。

4.1. 实现库函数

实现库函数是普通的 C 语言练习题；互联网上也有很多代码可以参考，但不要照抄哦！值得注意的是，编写可移植代码时，尽量使用 C 标准提供的机制，而不是做一些对硬件的假设，例如在 i386 平台上的 printf 有以下 “高明” (其实并不高明) 的实现方法 (请你花时间理解一下)：

int printf(const char *fmt, ...) {
  int *args = (int *)&fmt + 1;
  //          (int *)(&fmt + 1) also works; why?
  // args[0], args[1], ... 分别是第 1, 2, ... 个可变参数
}

上述代码其实做了一些 i386 特定的假设：

1. 所有参数构成一个 (堆栈上的) “数组”，因此可以用 &fmt + 1 得到剩余参数的起始地址；
2. int 类型的长度与指针的长度相同。

但在 x86-64 上，上述两个假设都不再成立，前 6 个参数用寄存器传递，且 sizeof(int) 通常是 4。可移植的方式是使用 stdarg.h 中的 va_list, va_start, va_arg。机器相关的假设、数据类型大小的假设 ((int *)ptr 在 64-bit 平台上将会报错) 等都可能引起移植性问题。

注意你可以在本地通过修改 Makefile 绕过某些 warnings，使你的程序看起来正确地在多个平台上运行；但 Online Judge 会使用我们的 Makefile 和 AbstractMachine 实现，并且可能经过一定的修改 (例如设置为不同的屏幕分辨率)。

4.2. 访问 I/O 设备

没有库函数的 C 语言程序类似于状态机，只能完成纯粹的 “计算”。TRM 中唯一能够和外界交互的手段是 putch() 在调试终端上打印字符和 halt() 终止程序。我们的硬件提供了若干 I/O 设备，AbstractMachine 可以通过 IOE 访问它们。在调用 I/O 设备之前，需要调用 ioe_init() 初始化，然后就可以用

void ioe_read (int reg, void *buf);
void ioe_write(int reg, void *buf);

两个函数访问 AbstractMachine 中的 I/O “寄存器” 了。详情请参考 AbstractMachine 文档和 amgame 框架代码。在 klib-macros.h 中包含了更简化的 I/O 寄存器访问方法 io_read 和 io_write，请大家查看。用这组 API 你就可以省去手工定义变量的麻烦，例如直接

int width = io_read(AM_GPU_CONFIG).width;

到这里，大家可能会产生的一个疑问是：运行在 “裸机” 上的程序可以用哪些标准库？我们知道，libc 中相当一部分函数都调用操作系统，例如 printf, malloc 等，即便引用了 stdio.h 这样的头文件，它们的实现依然是缺失的；另一方面，我们引用了一些库的头文件，例如 stdint.h (包含诸如 int32_t 这些类型的定义)、stdarg.h 等，却可以正常工作。这是为什么？

事实上，AbstractMachine 的程序运行在 freestanding 的环境下 (操作系统上的 C 程序运行在 hosted 环境下)：The __STDC_HOSTED__ macro expands to 1 on hosted implementations, or 0 on freestanding ones. The freestanding headers are: float.h, iso646.h, limits.h, stdalign.h, stdarg.h, stdbool.h, stddef.h, stdint.h, and stdnoreturn.h. You should be familiar with these headers as they contain useful declarations you shouldn't do yourself. GCC also comes with additional freestanding headers for CPUID, SSE and such.

这些头文件中包含了 freestanding 程序也可使用的声明。有兴趣的同学可以发现，可变参数经过预编译后生成了类似 __builtin_va_arg 的 builtin 调用，由编译器翻译成了特定的汇编代码。

4.3. 实现游戏

在这里，我们提供一个与 amgame 不同的框架代码，主循环使用轮询 (polling) 中不断等待下一帧时刻的到来，一旦到来，就读取键盘按键并处理，然后模拟这一帧中游戏发生的事情。

next_frame = 0;
while (1) {
  while (uptime() < next_frame) ; // 等待一帧的到来
  while ((key = readkey()) != _KEY_NONE) {
    kbd_event(key);         // 处理键盘事件
  }
  game_progress();          // 处理一帧游戏逻辑，更新物体的位置等
  screen_update();          // 重新绘制屏幕
  next_frame += 1000 / FPS; // 计算下一帧的时间
}

大家见过的 LiteNES 和仙剑奇侠传，都是这样的循环。我们以弹球游戏为例，你只需要维护弹球的坐标 $(x,y)$ 和弹球两个方向的速度 $(v_x, v_y)$ (以 pixel/秒为单位)，然后每一帧时更新坐标 $$(x', y') \leftarrow (x + v_x/\textrm{FPS}, y + v_y/\textrm{FPS})$$ 即可，加上以下两点就是很酷的弹球游戏啦！

1. 使用键盘 (如上下左右) 可以修改 $(v_x, v_y)$；
2. 弹球到屏幕边缘时，相应方向的速度符号取反，即 “完全弹性反射”。

提示

这个实验的目的是让大家熟悉 AbstractMachine 编程环境 (将会使用一整个学期)，而不是让大家 “内卷”。只要你的游戏满足最低标准 (附有正常的实验报告)，就可以得到满分。

4.4. 小游戏和操作系统

最后，为什么我们要在第一个实验里做一个游戏？首先，这是为了有一个给分的理由，能让大家都通过。其实还是因为游戏和操作系统的工作原理有那么一点相似。大家不妨可以看一下课程发布代码中的 NES 模拟器 LiteNES，简化的模拟器 (游戏) 的 “主循环” (fce.c) 代码如下：

while (1) {
  // 在每一个时间片，例如每 16.7ms (60 fps)
  wait_for_frame();

  // 做完这一个时间片内需要完成的工作
  int scanlines = 262;
  while (scanlines-- > 0) {
    ppu_cycle();      // 更新游戏图像
    psg_detect_key(); // 读取按键，更新游戏逻辑
  }
}

受到上面代码的启发，我们不妨在程序的主循环里不再是一次执行一帧，而在 “每一帧” 中都执行另一个程序，程序执行完后返回主循环。因此类似于游戏，批处理系统也是一个大循环：

while (1) {
  // 等待键盘输入需要运行的命令
  Job *job = wait_for_job();

  // 加载并执行命令
  load(job);
}

不妨假设 “批处理” 系统是这样工作的：

1. 批处理系统执行的命令由键盘输入，因此 wait_for_job() 就是从键盘读取按键并解析成命令，和游戏读取按键类似。
2. 执行的命令 (job) 是保存在磁盘上的 ELF 格式的二进制文件，使用硬件提供的 I/O 指令，从存储设备中将二进制文件加载到内存中。(实验代码中有一份 x86/x86_64 通用的二进制文件加载代码，位于 abstract-machine/am/src/x86/qemu/boot/main.c）；简化的代码如下：

copy_from_disk(elf32, 4096, 0); // 从磁盘读取 ELF 文件头
if (elf->e_machine == EM_386) {  // x86 (32-bit)
  load_elf32(elf32); // 从磁盘加载二进制文件到 ELF 文件描述的位置
  ((void(*)())(uint32_t)elf32->e_entry)(); // 跳转到加载的代码执行
}

跳转后，控制权就交给了 job；job 结束后函数返回，重新回到批处理系统——嘿！我们已经在第一个实验里体验了一个 “简易” 的操作系统！原来实现操作系统也没那么可怕嘛。从下个实验开始将正式开启多处理器，开始现代操作系统的旅程。