融会贯通: 实现更多的指令

为了让NEMU支持大部分程序的运行, 目前你需要实现以下指令:

• Data Movement Instructions: mov xchg push pop leave movsx movzx cwtl/cltd(在i386手册中为 cwd/cdq)
• Binary Arithmetic Instructions: add adc sub sbb cmp inc dec neg mul imul div idiv
• Logical Instructions: not and or xor sal(shl) shr sar setcc test
• Control Transfer Instructions: jmp call ret jcc
• String and Character Translation Instructions: movs stos lods scas rep
• Miscellaneous Instructions: lea nop

你只需要实现上述带有下划线的指令, 它们不多不少都和以下的某些内容相关: EFLAGS, 堆栈, 整数扩展, 加减溢出判断. 我们需要针对 movs, stos, lods 和 scas 这四条字符串操作指令进行补充说明: 这四条指令的执行涉及到段寄存器, 但我们目前并没有在NEMU中实现段寄存器, 因此我们先忽略和段寄存器相关的描述. 例如i386手册中对 movs 指令有如下描述:

Move DS:[(E)SI] to ES:[(E)DI]

目前我们只需要理解成

Move [(E)SI] to [(E)DI]

即可.

框架代码已经把其它指令实现好了, 但并没有填写 opcode_table . 此外, 某些需要更新EFLAGS的指令, 以及有符号立即数的译码函数(在 nemu/src/cpu/decode/decode-template.h 中定义)并没有完全实现好(框架代码中已经插入了 panic() 作为提示), 你还需要编写相应的功能.

断点(2)

我们在PA1中介绍了如何通过监视点来模拟断点, 不过这种方法需要提前知道设置断点的地址, 下面来介绍一种不需要提前知道断点地址的设置方法.

在x86中有一条叫 int3 的特殊指令, 它是专门给调试器准备的, 一般的程序不应该使用这条指令. 当程序执行到int3指令的时候, CPU将会抛出一个含义为"程序触发了断点"的异常(exception), 操作系统会捕捉到这个异常, 然后操作系统会通过信号机制(signal), 向程序发送一个SIGTRAP信号, 这样程序就知道自己触发了一个断点. 如果你现在觉得上述过程很难理解, 不必担心, 你只需要知道

当程序执行到 int3 指令的时候, 调试器就能够知道程序触发了断点

设置断点, 其实就是在程序中插入 int3 指令. int3 指令的机器码为 0xcc , 长度为一个字节. 如果你看过PA1中关于断点的阅读材料, 你会发现断点真正的工作原理比较复杂, 根据KISS法则, 我们采用一种简单的方法来实现断点的功能. 在 lib-common/trap.h 中提供了一个函数 set_bp() , 它的功能就是马上执行 int3 指令. 当NEMU发现程序执行的是 int3 指令时, 输出一句话提示用户触发了断点, 最后返回到 ui_mainloop() 循环中等待用户的命令.

框架代码已经实现上述功能了. 要使用断点, 你只要在用户程序的源代码中调用 set_bp() 函数, 就可以达到设置断点的效果了. 你可以在 testcase/src/mov-c.c 中插入断点, 然后重新编译mov-c程序并运行NEMU来体会这种断点的设置方法. 需要注意的是, 这种简化的做法其实是对 int3 指令的滥用, 因为在真实的操作系统中, 一般的程序不应该使用 int3 指令, 否则它将会在运行时异常终止.

不过这种方法也有不足之处: 一行C代码可能会对应很多条机器指令, 因此上述方法并不能在任意位置设置断点. 例如我们熟知的函数调用语句, 其对应的机器指令分为压入实参和控制转移两部分, 我们很难使用 set_bp() 在程序压入实参后, 执行 call 指令前设置断点, 不过这对监视点来说就不在话下了.

测试用例

未测试代码永远是错的, 你需要足够多的测试用例来测试你的NEMU. 我们在 testcase 目录下准备了一些测试用例, 需要更换测试用例时, 修改工程目录下 Makefile 中的 USERPROG 变量, 改成测试用例的可执行文件( obj/testcase/xxx , 不是C源文件)即可.

testcase 目录下的大部分测试用例都可以直接在NEMU上运行, 除了以下几个测试用例:

• hello-inline-asm
• hello
• integral
• quadratic-eq
• print-FLOAT

其中运行hello-inline-asm和hello需要系统调用的支持, 在PA2中我们无法提供系统调用的功能, 这两个测试用例将会在PA4中用到, 目前你可以忽略它们; 要运行print-FLOAT需要使一些与运行时代码相关的小技巧, 我们在PA2的最后再来讨论如何运行它; 而integral和quadratic-eq涉及到浮点数的使用, 我们先来讨论如何处理浮点数.

实现binary scaling

要在NEMU中实现浮点指令也不是不可能的事情. 但实现浮点指令需要涉及x87架构的很多细节, 而且我们并不打算在用户程序中直接使用浮点指令. 为了在保持程序逻辑的同时不引入浮点指令, 我们通过整数来模拟实数的运算, 这样的方法叫binary scaling.

我们先来说明如何用一个32位整数来表示一个实数. 为了方便叙述, 我们称用binary scaling方法表示的实数的类型为 FLOAT . 我们约定最高位为符号位, 接下来的15位表示整数部分, 低16位表示小数部分, 即约定小数点在第15和第16位之间(从第0位开始). 从这个约定可以看到, FLOAT 类型其实是实数的一种定点表示.

31  30                  16                    0
+----+-------------------+--------------------+
|sign|      integer      |      fraction      |
+----+-------------------+--------------------+

这样, 对于一个实数 a , 它的 FLOAT 类型表示 A = a * 2^16 (截断结果的小数部分). 例如实数 1.2 和 5.6 用 FLOAT 类型来近似表示, 就是

1.2 * 2^16 = 78643 = 0x13333
+----+-------------------+--------------------+
| 0  |         1         |        3333        |
+----+-------------------+--------------------+


5.6 * 2^16 = 367001 = 0x59999
+----+-------------------+--------------------+
| 0  |         5         |        9999        |
+----+-------------------+--------------------+

而实际上, 这两个 FLOAT 类型数据表示的数是:

0x13333 / 2^16 = 1.19999695
0x59999 / 2^16 = 5.59999084

对于负实数, 我们用相应正数的相反数来表示, 例如 -1.2 的 FLOAT 类型表示为:

-(1.2 * 2^16) = -0x13333 = 0xfffecccd

接下来我们来考虑 FLOAT 类型的常见运算, 假设实数 a , b 的 FLOAT 类型表示分别为 A , B .

• 由于我们使用整数来表示 FLOAT 类型, FLOAT 类型的加法可以直接用整数加法来进行:

  A + B = a * 2^16 + b * 2^16 = (a + b) * 2^16
  

• 由于我们使用补码的方式来表示FLOAT类型数据, 因此FLOAT类型的减法用整数减法来进行.

  A - B = a * 2^16 - b * 2^16 = (a - b) * 2^16
  

• FLOAT 类型的乘除法和加减法就不一样了:

  A * B = a * 2^16 * b * 2^16 = (a * b) * 2^32 != (a * b) * 2^16
  

  也就是说, 直接把两个 FLOAT 数据相乘得到的结果并不等于相应的两个浮点数乘积的 FLOAT 表示. 为了得到正确的结果, 我们需要对相乘的结果进行调整: 只要将结果除以 2^16 , 就能得出正确的结果了. 除法也需要对结果进行调整, 至于如何调整, 当然难不倒聪明的你啦.
• 如果把 A = a * 2^16 看成一个映射, 那么在这个映射的作用下, 关系运算是保序的, 即 a <= b 当且仅当 A <= B , 故 FLOAT 类型的关系运算可以用整数的关系运算来进行.

有了这些结论, 要用 FLOAT 类型来模拟实数运算就很方便了. 除了乘除法需要额外实现之外, 其余运算都可以直接使用相应的整数运算来进行. 例如

用 FLOAT 类型来模拟就是

其中还引入了一些类型转换函数来实现和 FLOAT 相关的类型转换.

/* lib-common/FLOAT.h */
int32_t F2int(FLOAT a);
FLOAT int2F(int a);
FLOAT F_mul_int(FLOAT a, int b);
FLOAT F_div_int(FLOAT a, int b);
/* lib-common/FLOAT/FLOAT.c */
FLOAT f2F(float a);
FLOAT F_mul_F(FLOAT a, FLOAT b);
FLOAT F_div_F(FLOAT a, FLOAT b);
FLOAT Fabs(FLOAT a);

--- Makefile
+++ Makefile
@@ -12,2 +12,2 @@
 LIBC = $(LIBC_LIB_DIR)/libc.a
-#FLOAT = obj/$(LIB_COMMON_DIR)/FLOAT/FLOAT.a
+FLOAT = obj/$(LIB_COMMON_DIR)/FLOAT/FLOAT.a

编写自己的测试用例

从测试的角度来说, testcase 目录下的测试用例还不够完备, 很多指令可能都没有被覆盖到. 想象一下你编写了一个 if 语句, 但程序运行的时候根本就没有进入过这个 if 块中, 你怎么好意思说你写的这个 if 语句是对的呢? 因此我们鼓励你编写自己的测试用例, 尽可能地覆盖到你写的所有代码. 用户程序的来源有很多, 例如程序设计作业中的小程序, 或者是已经完成的数据结构作业等等. 但你需要注意NEMU提供的运行时环境, 用户程序不能输出, 只能通过 nemu_assert() 来进行验证. 你可以按照以下步骤编写一个测试用例:

• 先使用 printf() 根据数组的格式输出测试结果, 此时你编写的是一个运行在GNU/Linux下的程序, 直接用gcc编译即可.
• 运行程序, 得到了数组格式的输出, 然后把这些输出结果作为全局数组添加到源代码中, 你可以通过 >> 将输出重定向追加到源代码中.
• 去掉代码中的 printf() 和头文件, 包含 trap.h , 使用 nemu_assert() 进行验证.
• 把修改后的.c文件放到 testcase/src 目录下即可.

这样你就成功添加了一个测试用例了, 按照上文提到的步骤更换测试用例, 就可以使用你的测试用例进行测试了.

我们还鼓励你把测试用例分享给大家, 我们在提交网站中创建了一个"测试用例分享"的讨论版, 你可以在讨论版中分享你的测试用例, 同时也可以使用其它同学提供的测试用例进行测试. 你的程序通过越多的测试, 程序的健壮性就越好, 越有希望通过"在NEMU上运行仙剑奇侠传"的终极考验.

V = V + 1
V = V - 1
IF V != 0 GOTO LABEL

    # Assume a = 0, x and y are initialized with some positive integers.
    # Other temporary variables are initialized with 0.
    # Let "jnz" carries a variable: jnz v, label.
    # It means "jump to label if v != 0".
    # Compute a = x + y used only these three instructions: inc, dec, jnz.
    # No other instructions can be used.
    # The result should be stored in variable "a".
    # Have a try?