-
Notifications
You must be signed in to change notification settings - Fork 21
/
ch_pa-1-2_alu.md
147 lines (88 loc) · 10.4 KB
/
ch_pa-1-2_alu.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
# PA 1-2 整数的表示、存储和运算
我们首先考察整数的表示、存储和运算问题。在计算机中，一切都是离散的。用于表示各类信息的数据，尽管其含义可能千差万别，但最终在计算机内的表示总可以在形式上归于整数（机器数）形式。因此，从整数开始讨论计算机内数据的表示、存储和运算，是一个较为理想的切入点。
## §1-2.1 预备知识
在计算机中，采用二进制表示任何的数。整数可分为无符号整数和带符号整数两种。带符号整数的表示可分为原码表示和补码表示两种方法。数据的存储方式又可分为大端方式和小端方式两种。具体的背景知识请参见理论课的内容，在实验指导中不再赘述。
## §1-2.2 代码导读和实验理解
#### §1-2.2.1 EFLAGS寄存器
在进行整数的算术和逻辑运算之前，我们需要先为运算提供必要的支撑。在CPU内部有一个刻画当前CPU状态的寄存器称为标志寄存器`EFLAGS`。其结构请参见i386手册第2.3.4节。`EFLAGS`中包含一系列重要的标志位如我们现在就要用到的`CF`、`PF`、`ZF`、`SF`、`DF`、`OF`和将来要到PA 4-1用到的`IF`。在`nemu/include/cpu/reg.h`头文件中我们已经给出了`EFLAGS`寄存器的一个实现，其中使用到了C语言的位域（bit field），如不理解请上网搜索。
#### §1-2.2.2 整数的算术和逻辑运算
在整数表示的基础上，我们就能够来模拟CPU对整数的算术和逻辑运算功能了。在CPU内部，这一功能通过算术逻辑部件（Arithmetic Logic Unit，ALU）来实现。在NEMU中，对应于头文件`nemu/include/cpu/alu.h`和源文件`nemu/src/cpu/alu.c`。在模拟这些运算功能时，我们的最终目标是要配合x86指令模拟的需求，为相应的算术和逻辑运算指令提供封装好的函数。因此，尽管目前还没有进展到对指令和指令的执行进行模拟的步骤，我们仍需从指令模拟的需求出发，对运算函数的需求进行刻画。
##### * 整数的加减操作
首先，我们需要模拟整数的加减运算。在采用补码表示法后，带符号和无符号的整数加减法可以统一使用无符号整数加减法来执行。因此，我们只需要实现无符号整数加减法即可。同时，考虑是否带进位和借位的加减法，我们一共需要实现四个无符号加减法函数，如下表所示。
```c
// 返回 dest + src，截取低 data_size 位，高位置零，根据运算结果设置各标志位（AF不模拟，下同）
uint32_t alu_add(uint32_t src, uint32_t dest, sizt_t data_size);
// 返回 dest + src + CF，截取低 data_size 位，高位置零，并设置各标志位
uint32_t alu_adc(uint32_t src, uint32_t dest, sizt_t data_size);
// 返回 dest - src ，截取低 data_size 位，高位置零，并设置各标志位
uint32_t alu_sub(uint32_t src, uint32_t dest, sizt_t data_size);
// 返回 dest - src - CF，截取低 data_size 位，高位置零，并设置各标志位
uint32_t alu_sub(uint32_t src, uint32_t dest, sizt_t data_size);
// 返回 dest - src - CF，截取低 data_size 位，高位置零，并设置各标志位
uint32_t alu_sbb(uin32_t src, uint32_t dest, sizt_t data_size);
```
在实现上述函数时，我们仅需要使用C语言本身所提供的运算符号即可。运算的具体语义可参照i386手册中对应指令（指令名称和函数名对应）的说明。在进行各标志位的设置时，参考i386手册附录C（Appendix C Status Flag Summary）的相关内容以及对应的指令的详细说明。再次申明，作为简化的x86模拟器，我们目前不对`AF`标志位进行操作。
在`nemu/src/cpu/test/alu_test.c`源文件中，包含了一些针对整数算术和逻辑运算的单元测试用例。针对整数加减法需要通过`alu_test_add()`、`alu_test_adc()`、`alu_test_sub()`、`alu_test_sbb()`这四个测试用例即可。仔细观察这四个测试用例，可以发现框架代码所采用的测试方法是构造一系列的测试输入（test input），然后将被测程序（我们的实现）包含运算结果和标志位在内的输出与一个“黄金版本”（golden version）的输出进行比较。框架代码通过内联汇编的方式来实现所谓的“黄金版本”。当然，聪明的各位不难想到可以直接采用测试程序中所使用的内联汇编法来实现整数的算术和逻辑运算操作。虽然此法简单高效正确，但无助于我们更深入地理解运算过程以及标志位设置的条件。
**在此我们明确禁止各位采用内联汇编的方法来实现整数的算术和逻辑运算**。
在`nemu/src/cpu/test/alu_test.c`源文件中我们只提供了一些样例测试输入。你可以通过增加测试输入的方法来提高测试覆盖率，提高找到潜在bug的可能性。
##### * 整数的移位操作
整数的移位操作从方向上可以分为左移和右移两种，从对符号位的处理方式上又可以分为逻辑移位和算术移位两种，因此一共可以分为算术左移（SAL）、逻辑左移（SHL）、算术右移（SAR）和逻辑右移（SHR）四种。可以参照i386手册对应的指令说明和附录C（Appendix C Status Flag Summary）的相关内容来具体了解这四种操作具体的语义和符号位的设置方法。在框架代码中，移位操作对应下表所示的四个函数。
```c
// 返回将 dest 算术左移 src 位后的结果， data_size 用于指明操作数长度（比特数），
// 可以是 8、16、32 中的一个用于判断标志位的取值，标志位设置参照手册说明
uint32_t alu_sal(uint32_t src, uint32_t dest, size_t data_size);
// 同 alu_sal()
uint32_t alu_shl(uint32_t src, uint32_t dest, size_t data_size);
// 返回将 dest 算术右移 src 位后的结果（高位补符）， data_size 用于指明操作数长度，标志位设置参照手册说明
uint32_t alu_sar(uint32_t src, uint32_t dest, size_t data_size);
// 返回将 dest 逻辑右移 src 位后的结果（高位补零）， data_size 用于指明操作数长度，标志位设置参照手册说明
uint32_t alu_shr(uint32_t src, uint32_t dest, size_t data_size);
```
同样的，在完成了对应的移位操作函数后，可以通过执行测试用例来检测程序中的问题。
*注意手册中提到移位指令只在单次移位时才会对OF位进行设置，在NEMU中我们忽略这个细节，不对移位操作后的OF位进行测试。同时，移位操作也要结合data_size，将高位清零。*
##### * 整数的逻辑运算
整数的逻辑运算包括整数的与（AND）、或（OR）、非（NOT）、异或（XOR）操作。在我们的实验中，目前只需要实现与、或、异或这三个操作，NOT操作由于太过简单，可以在之后的指令实现中直接实现：
```c
// dest AND src
uint32_t alu_and(uint32_t src, uint32_t dest, size_t data_size);
// dest OR src
uint32_t alu_or(uint32_t src, uint32_t dest, size_t data_size);
// dest XOR src
uint32_t alu_xor(uint32_t src, uint32_t dest, size_t data_size)
```
在实现相应的函数后，同样可以通过执行测试用例来检查实现中可能存在的bug。
##### * 整数的乘除运算
最后我们需要实现整数的乘除运算。整数的乘除运算按照是否带符号可以分为两组，无符号乘除法和有符号乘除法。现代计算机中有专门的乘法器来实现整数的乘除运算，在这里我们简化这一实现方案，将乘除法也归于ALU的功能。
对于乘法而言，其能乘数和被乘数最大位数为32位，所得乘积的最大位数为64位。根据i386手册的描述，对于乘法指令而言，当乘积为64位（32位）时，其高32位（16位）置于`EDX`（`DX`）寄存器中，而低32位（16位）置于`EAX`（`AX`）寄存器中。在目前阶段，我们尚不考虑乘积在寄存器中的存放方式。而仅仅实现两个32位整数乘法得到一个64位整数的运算操作。
而对于除法而言，当其除数为32位时，其被除数取最大位数为64位。同样根据i386手册，对于除法指令而言，当被除数为64位时，其高32位放在`EDX`寄存器中，而低32位放在`EAX`寄存器中。与乘法操作类似，在目前阶段，我们不关心在除法的除数和被除数在寄存器中如何存放，而仅关心两个64位整数相除得到一个32位整数的问题。
为了实现对乘除运算的支持，需要实现6个函数，如下表所示：
```c
// 返回两个操作数无符号乘法的乘积， data_size 为操作数长度（比特数），在设置标志位时有用
uint64_t alu_mul(uint32_t src, uint32_t dest, size_t data_size);
// 返回两个操作数带符号乘法的乘积
int64_t alu_imul(int32_t src, int32_t dest, size_t data_size);
// 返回无符号除法 dest / src 的商，遇到 src 为0直接报错（对应Linux是Floating Point Exception）退出程序
uint32_t alu_div(uint64_t src, uint64_t dest, size_t data_size);
// 返回带符号除法 dest / src 的商，遇到 src 为0直接报错退出程序
int32_t alu_idiv(int64_t src, int64_t dest, size_t data_size);
// 返回无符号模运算 dest % src 的结果
// 实际上，整数除法和取余运算是由div或idiv指令同时完成的，我们这里为了方便，把模运算单独独立了出来
uint32_t alu_mod(uint64_t src, uint64_t dest);
// 返回带符号模运算 dest % src 的结果
int32_t alu_imod(int64_t src, int64_t dest);
```
最后两个模运算操作是NEMU新增的，在IA32指令集中并不存在。事实上，除法运算会在给出商的同时给出除法的余数，具体内容请参照i386手册中有关除法指令（div和idiv）的描述。在当前阶段，我们将除法和模运算分开设置，方便将来在实现除法指令时调用。
注意手册对于imul指令对标志位设置的描述较为模糊，因此在框架代码中，我们针对imul操作的标志位设置不进行测试。
## §1-2.3 实验过程及要求
##### * 代码要求
1. 实现`nemu/src/cpu/alu.c`中的各个整数运算函数；
2. 使用
> make clean
>
> make
命令编译项目；
3. 使用
> make test_pa-1
命令执行NEMU并通过各个整数运算测试用例。
## 本阶段要修改的代码清单（参考）
* `nemu/src/cpu/alu.c`