PA1 数据的表示存取和运算

PA 是一门实验课，由四个主要部分组成，分别是：

• PA 1 数据的表示、存取和运算
• PA 2 程序的执行
• PA 3 存储管理
• PA 4 异常、中断与 I/O

这四个阶段大致对应模拟器中对 CPU、MMU 和 Device 的模拟。

该实验主要是作为《计算机系统基础》这门课的辅助性课程。

老师提供了实验手册以及已经很完善的程序代码框架，我们要做的只是按照实验手册的要求，去特定的文件中编写一些关键的函数。

这次的博客系列文章主要用于记录我的 PA 实验过程，一方面想要记录下自己在这些方面做过的第一个实验，另一方面也希望通过记录的过程去复习、巩固以及加深对相关知识的理解。

那么我们开始吧！

PA0 配置 Debian 环境

安装 Debian 虚拟机，方法与我之前的一篇文章「linux 虚拟机安装」类似。

选择 Debian 10 的 i386 版本，在虚拟机软件 vmware/virtual box 的辅助下完成 Debian 虚拟机的创建。

将用户加入 sudo 列表

在终端输入以下指令

su -root
// input your password
adduser your_username sudo
exit

然后注销用户，重新登录用户，就成功将该用户加入 sudo 列表了。

安装必要的工具

sudo apt-get install build-essential libreadline-dev libsdl1.2-dev vim git tmux dialog python python-rsa openssl

复制粘贴等一等就完事了。

获取 PA 项目的代码框架

老师使用了 Gitlab 网站来管理，使用下来感觉和 GitHub 区别不大。

弄好仓库，配置 SSH keys，然后完成一项任务就 push 下就 OK 了。

PA1-1 数据在计算机内的存储

这一节的内容主要是模拟寄存器和主存。

寄存器的模拟

我们的实验模拟的是 i386 体系结构，这里需要 8 个 32 位寄存器。

首先我们定义了一个全局的结构变量 CPU_STATUS，并实体化为 cpu，目标是：可以用 cpu.eax 访问寄存器 %eax，并且可以用 cpu.gpr[0]._16 访问到 cpu.eax 的低 16 位，用 cpu.gpr[0]._8[0] 访问 cpu.eax 的低 8 位。

为了实现用不同的访问方式访问同一变量以及该变量的部分内容，我们选择了 union。

对比一下 struct 与 union

• struct：内部各个变量的存储相互独立
• union：各变量共同拥有同一个空间，但只占用自身大小

下面是结构 CPU_STATUS 的定义。

union
{
  union
  {
    union
    {
      uint32_t_32;
      uint16_t_16;
      uint8_t_8[2];
		};
    uint32_t val;
	};
  gpr[8];
  struct
  {
    uint32_t eax,ecx,edx,ebx,esp,ebp,esi,edi;
	};
};

主存的模拟

约定我们的 NEMU 拥有 128MB 字节的内存，我们可以定义一个这么大的数组。

#define MEM_SIZE_B 128*1024*1024

uint8_t hw_mem[MEM_SIZE_B];

这样主存的物理空间就模拟好了，我们还需要定义一些函数用于对主存的读写操作。

主要有物理地址读写、线性地址读写和虚拟地址读写三类函数，但项目说明中提到「在 NEMU 工作模式下，这三种地址相同」，所以简化了这些函数的构造。这些东西将会在后续实验中再次出现。

PA1-2 整数的表示、存储和运算

这一节我们要用 C 语言实现 32 位无符号整数、有符号整数的加减、乘除、移位、逻辑运算，这中间需要我们自己设置 EFLAGS 标志位——ZF\CF\OF\SF\PF 等等。

几种标志位

ZF：结果为 0 时 ZF 为 1，否则 ZF 为 0。

PF：结果的低八位中 1 的个数的奇偶性，偶 1 奇 0。

SF：即结果的符号位。

以上三种标志位对于本节的大部分函数是通用的。

CF 与 OF：

这两个要特别说一下。

计算 CF 时，要把两个操作数的机器码视作无符号整数，在此情况下考虑是否溢出；计算 OF 时，要把两个操作数的机器码视作带符号整数，然后去看是否溢出。

当然，上面的说法不是他们的本质（CF 的 C 是 carry，OF 的 O 是 overflow），但这样的解释能让我更容易计算 CF 和 OF 的值。

一般情况下，机器并不知道你的操作数是否带符号，所以它不得不按照无符号、带符号两种方式都判断一下，提供给调用者两个结果，让调用者自己选择。

加减

本来我们应该分别实现无符号数的加减法以及带符号数的加减法，但在采用了补码表示法之后，带符号与无符号的整数加减法可以统一使用无符号整数的加减法来执行，因此我们只需实现无符号数的加减法操作即可。

主要涉及 add、adc、sub、sbb 四种指令。

add 是 dest+src，adc 则是 dest+src+CF，多加了一个 CF 位；同样，sbb 比 sub 多减了一个 CF。因此，计算 CF 的值时，adc 比 add 要多考虑一种特殊情况。但 OF 的计算，则完全一样。

以 sbb 函数为例大概说一下。

uint32_t alu_adc(uint32_t src,uint32_t dest,size_t data_size)

参数是两个 32 位的无符号整数 src、dest 和具体的操作数长度 data_size（8、16 或 32）。

OF 的设置：

考虑 OF 时把 dest、src 视为带符号数，正数减正数、负数减负数都不会溢出，只有负数减正数或者正数减负数会溢出，而且结果应该和被减数不同号。

此处忽略 sbb 比 sub 多减了 CF 这个细节。（具体原因我暂时不懂）

OF = (sign(dest)!=sign(src)) && (sign(result)==sign(src));

CF 的设置：

考虑 CF 时把 dest、src 视为无符号数，两个无符号数相减，再减去一个 CF，如果 CF==0，那么和 sub 一样，否则就会出现一种特殊情况：

设 32 位无符号整数能表示的最大值是 max，若 src==max-1，则 dest - src - CF == dest，这一种溢出的情况也要考虑到。

移位

我们的代码都是用 C 语言编写的。

C 语言中对于无符号、带符号整数的移位采用相同的符号、不同的操作。

如果对无符号整数进行 << 操作，就是逻辑左移；如果对带符号整数进行 <<，则是算术右移。

这个实验给我们提供的参数是一个 32 位的无符号整数 dest，要实现对它的逻辑左右移和算术左右移。

逻辑右/算术右：直接对 dest 进行 >> 即可。

逻辑左：dest 是无符号数，直接对其 << 即可。

算术右：

这里需要把 dest 强制类型转换为带符号整数，而且，dest 是一个 32 位的无符参数，但它的实际位数是 data_size，所以如果我们直接”<<“，系统会认为它的符号位是第 31 位，而实际上可能是第 7 位或者第 15 位。

因此整个过程是，先强制类型转换变成带符号数，然后把这个 32 位数截断成它自身的长度，进行左移完成后，再扩展回原来的 32 位。

逻辑

and、or、not、xor

比较简单，不再细说。

乘除

无符号乘法、带符号乘法、无符号除法、带符号除法，以及额外添加的无符号模和带符号模运算。

i386 手册中对于带符号乘法的标志位设置比较模糊，所以就不做设置了。

除法、模运算也不用设置标志位，所以没啥说的了。

强制类型转换就完事了。

PA1-3 浮点数的表示和运算

这次实验要实现的是单精度浮点数 Float 的加减乘除运算，整个过程中禁止使用类型转换，禁止使用 C 语言中对浮点数的操作，必须在机器码的状态下实现浮点数的四则运算。

浮点数的表示

typedef union
{
    struct
    {
        uint32_t fraction : 23;
        uint32_t exponent : 8;
        uint32_t sign : 1;
	  };
	  float fval;
	  uint32_t val;
}FLOAT;

此处有一个 C 语言的知识点叫「位域」。

比如 exponent 这个变量，虽然它是 uint32_t 类型的，但我只需要 8 个字节的空间，就可以这样来写。

总体来看，struct 的总空间依旧是 32 位，由于外部是 union 类型，所以可以直接通过变量 val 访问 struct 的 32 位机器码（用于做实验），还可以通过 fval 直接访问该浮点数（用于测试）。

浮点数的加减乘除

实验指导中非常详细的介绍了，我就大概讲一下我的理解吧。

两个单精度浮点数相加

变量 a：1、8、23

变量 b：1、8、23

第一步，排除掉特殊情况。比如说其中一个数是正负零，或者正负无穷，或者 NaN（非数值）。这些情况可以直接得出结果了。

第二步，提取尾数。把变量的尾数 23 位提取出来（存储在 uint32_t 变量中），把隐藏位添加上去，非规格化数隐藏位是 0，规格化数隐藏位是 1。

第三步，阶码对齐。加法的话，谁的阶码大，谁的值就大，要把阶码小的变量的尾数变小，阶码变大，一直到对齐。

第四步，确保精度。上一步要求移动尾数，这样会丢弃末尾的一部分数据，为了保证计算的精度，我们在变量的尾数后再添加 3 个字节位，也参与运算，已增加加法的精度。（如何添加 3 位？可以左移三位，这样尾部就空出来 3 位了）这三位是 G、R、S 位，S 位又叫做「粘滞位」，只要 S 位变为 1，它就一直是 1 了。（原理我还不懂，但感觉为了计算的精度，这样做也挺有道理的）

第五步，尾数相加，并规格化。我们为什么要规格化？尾数相加之后，可能出现进位，导致尾数超出或者少于 23+3 位（grs 三位），这样的话我们就该把它移回去，同时要修改 exp 的值，在修改的过程中就会出现 exp 溢出、exp 等于 0 的特殊情况。在这中间，要经常性地去考虑这个浮点数是否是变成了非规格化数。

下面是「规格化」整个过程的伪代码，适用于加减乘除。

inline uint32_t internal_normalize(uint32_t sign,int32_t exp,uint64_t sig_grs)
{
    if(/*需要右规*/)
    {
        while(/*需要右规 且 没有发生上溢出*/)
        {
        	  /*右规一次*/
        }
        if(/*阶码上溢出*/)
        {
        		/*结果置为正负无穷*/
				}
				if(/*阶码全0，变成了非规格化数*/)
				{
						/*右移一次变成非规格化数*/
				}
				if(/*阶码仍然小于0，阶码下溢出*/)
				{
						/*浮点数太小，无法表示，置为正负零*/
				}
    }
    else if(/*需要左规 且 阶码大于0*/)
    {
    		while(/*需要左规 且 阶码大于0*/)
    		{
    				/*左规一次*/
    		}
    		if(/*阶码==*/)
    		{
    				/*右移一次变为非规格化数*/
    		}
    }
    else if(/*两个规格化数运算后得到了非规格化数*/)
    {
    		exp++;
    }
    if(/*未发生溢出*/)
    {
    		/*最后三位（grs）采用就近舍入到偶数的方式*/
    		/*移除最后三位*/
    		if(/*进位导致了规格化被迫坏*/)
    				/*再判断并规格化*/
    }

    /*规格化数删除隐藏位*/
}

对于减法：把操作数换成补码之后，和加法一样。

乘法：

可以免去阶码对齐的过程，用 uint64_t 表示更加方便。

除法：

尾数相除，为了提高精度，可以把被除数使劲放大（左移到底），除数使劲缩小（右移到底），这样得到的结果再移回原有的位置，精度更高。

最后的阶码如何设定呢？我们加入了 GRS bits 后，相当于约定中间结果 fraction 是 26 位数，但是我们用 23 位乘以 23 位得到的是 46 位，因此 46-26=20，这个 20 需要阶码来处理。最终的阶码就是 fa.exponent + fb.exponent - 127 - 20。这一部分比较难以理解。

最后

PA 1 结束了。

这一部分我们设计了寄存器、主存以及标志位的模拟，定义了浮点数类型变量，同时也编写了定点数、浮点数的一些常用的运算操作，称为「数据的表示、存取和运算」。

要开始「程序的执行」了。

下次见。