程序的转换和表示

本章我们将学习程序的转换和表示。包括我们平时写的高级语言程序是如何「转换」为计算机底层指令的，这些底层指令又是如何用 01 机器码来「表示」的。

以 C 语言为例，程序的转换涉及到以下流程：

\[ \begin{aligned} \text{源代码 $\xrightarrow[]{\text{预处理}}$ 源代码 $\xrightarrow{\text{编译}}$ 汇编代码 $\xrightleftharpoons[\text{反汇编}]{\text{汇编}}$ 机器代码 $\xrightarrow[]{\text{链接}}$ 机器代码} \end{aligned} \]

机器码都是 01 数字，不方便我们直接阅读，只能从更高层面的汇编来理解。从上图可以看出，汇编代码可以从源代码「编译」而来，也可以从机器代码「反汇编」而来，本章主要就是按 AT&T 格式对上述两种来源的汇编代码进行分析和理解。

基本概念¶

强烈建议先观看硬件科普视频从零开始认识主板，来对计算机硬件有一个初步认知。本文重点介绍其中的 CPU，并且主要关注 CPU 中的指令集。

指令集是 CPU 运作的一个重要部分，它定义了 CPU 理解和执行指令的规则和方法，也是程序员和编译器与 CPU 交互的接口。

机器指令与汇编指令¶

计算机只认识机器指令，但是机器指令只是一个 01 位串，可读性很差，因此引入汇编指令用于助记。由机器指令组成的程序叫机器语言程序，由汇编指令组成的程序叫汇编语言程序。将汇编语言转化为机器语言的程序叫「汇编程序」，将机器语言转化为汇编语言的程序叫「反汇编程序」。

但是汇编语言程序还是很抽象，因此引入高级语言程序。现在我们要解决的是如何将高级语言程序转化为机器语言程序。至于如何转化能够使得时间、空间都最优，这是编译优化要解决的事，这里不予讨论。

指令集体系结构¶

指令集体系结构 (Instruction Set Architecture, ISA) 是连接计算机硬件和软件之间的桥梁，将物理上的计算机硬件抽象成了逻辑上的虚拟计算机，称为机器语言级虚拟机。

ISA 定义了机器语言级虚拟机的所有功能，是一套与 CPU 交互的规则。

机器码与汇编语言¶

机器指令本质上就是一个人为定义的含有某些意义的 01 序列，查询相应的表可以得知对应的汇编语言格式。不需要记忆多少东西，遇到不懂的直接查表即可。下方表格展示了一个经典的转换：

机器码（十六进制格式）	汇编语言（AT&T 格式）
`C744 2404 0100 0000`	`movl $0x1, 0x4 (%esp)`

程序的转换¶

基本转换流程¶

假设当前有一个 C 语言文件 main.c，利用 gcc 工具完成程序的转换：

1）预处理。编译器首先处理源代码中的预处理指令（例如在 .cpp 源代码中插入所有用 #include 命令指定的文件和用 #define 声明指定的宏）：

gcc -E main.c -o main.i

生成的 main.i 是文本文件。

2）编译。将预处理后的源程序编译成汇编语言程序。

gcc -S main.i -o main.s

生成的 main.s 是文本文件。

3）汇编。汇编程序将编译出来的汇编语言程序转化为可重定位的目标文件（Windows 上是 .obj 文件，Linux/macOS 上是 .o 文件）：

gcc -c main.s -o main.o

生成的 main.o 是二进制文件，即机器码，其中的函数/变量地址等是未确定的。

*）反汇编。汇编得到的 main.o 文件是不可读的，但我们可以利用 objdump 工具将其反汇编成文本文件，命令如下：

1	`objdump -d main.o`

gcc 和 objdump 默认的汇编格式也是 AT&T，所以阅读起来比较方便。

4）链接。链接器将所有的目标文件以及项目所需的库文件（标准库或第三方库）捆绑在一起，解析并确定所有函数/变量的最终地址，最终生成一个单一的可执行文件（Windows 上是 .exe 文件，Linux/macOS 上没有特定后缀）：

gcc main.o -o main

过程调用的转换¶

CALL 调用指令：在执行调用过程之前需要将返回地址压入栈

RET 返回指令：在返回调用过程之前从栈中取出返回地址

过程调用的执行步骤（记调用者为 P，被调用者为 Q）

步骤	过程
P 将参数存储到 Q 可以访问到的地方	按参数列表从右往左依次压入栈
P 保存返回地址（即调用函数的下一个语句）并将控制权给 P	将返回地址入栈并执行 CALL 指令
Q 保存 P 的现场并为自己的非静态变量分配空间	一般由调用与被调用过程共同保存通用寄存器中的现场
执行 Q 的函数体	---
Q 恢复 P 的现场并释放局部变量空间	恢复现场并释放局部变量空间
Q 取出返回地址并将控制权给 P	通过 RET 指令

选择语句的转换¶

主要由常用指令组合而成，相比于过程调用更加简单。

循环语句的转换¶

同选择语句，主要由常用指令组合而成，相比于过程调用更加简单。

复杂数据的转换¶

程序中数据肯定也需要转换为机器码，主要考虑数据的分配和访问。

数组的分配与访问。采用相对寻址，大一学习 C 语言的数组时就学过相关概念了，关键有两点：

知道数组存的是什么类型的数据（进而知道每一个元素占用多少字节）
知道数组首地址。以二维数组为例，运算公式就是 &a + (typeof a) * (i * M) + j，其中 typeof a 就表示单个元素的字节数，i, j 就表示下标索引，M 就表示行数（默认按行优先规则）

结构体数据的分配与访问。采用首地址+偏移的逻辑分配与访问数据，与数组类似。同时，一个结构体存储所有字段的数据。

联合体数据的分配与访问。同样采用首地址+偏移的方式分配和访问数据。一个联合体在同一时刻只存储一种数据类型。即相同的位序列可以在不同时刻存储不同的数据类型变量。

数据的对齐。对于 32 位操作系统而言，存储器一行存储 32 位共 4 个字节，计算机系统一次访问存储空间只能读写固定长度的位。假定最多可以读写 64 位，则称为 8 字节宽的存储器机制。一般采用 按边界对齐 的对齐策略，尽管这样会浪费一些存储空间，但是有利于数据的快速访问。

举个例子。对于下面的程序：

struct {
    int a;
    short b;
    double c;
    char d;
    short e;
}

按边界对齐：

边界不对齐：

越界访问和缓冲区溢出¶

越界访问和缓冲区溢出其实是一个东西，只不过缓冲区溢出是单独针对栈空间中对局部数组进行了越界访问。一般而言的越界访问往往表示错误访问了栈空间中的返回地址导致程序出现意想不到的错误。

IA-32 指令系统¶

数据类型及其格式¶

IA-32 支持的数据类型及格式与 C 语言之间的对应关系：

C 语言声明	Intel 操作数类型	汇编指令长度后缀	存储长度（位）
`(unsigned) char`	整数/字节	$b$	`8`
`(unsigned) short`	整数/字	$w$	`16`
`(unsigned) int`	整数/双字	$l$	`32`
`(unsigned) long int`	整数/双字	$l$	`32`
`(unsigned) long long int`	-	-	`2*32`
`char *`	整数/双字	$l$	`32`
`float`	单精度浮点数	$s$	`32`
`double`	双精度浮点数	$l$	`64`
`long double`	扩展精度浮点数	$t$	`80/96`

寄存器和寻址方式¶

在 IA-32 指令系统中，寄存器共有三大类：

8 个通用寄存器，其中
- EAX, EBX, ECX, EDX 均为 32 位寄存器
- AX, BX, CX, DX 均为 16 位寄存器
- AH, BH, CH, DH 均为高 8 位寄存器
- AL, BL, CL, DL 均为低 8 位寄存器
2 个专用寄存器
6 个段寄存器

如下图所示：

IA-32 指令系统的寻址方式主要有三种：

立即寻址：指令直接给出操作数。无需寻址；
寄存器寻址：指定寄存器的内容为操作数。在寄存器中找数据；
存储器寻址：基址 $+$ 变址 $\times$ 比例因子 $+$ 偏移地址。在内存或者硬盘中找数据。

常用指令¶

传送指令。符号辨析：$\text{R}$ 即 $\text{Register}$ 表示取寄存器操作数，$\text{M}$ 即 $\text{Memory}$ 表示取存储器操作数，$\text{mov}$ 即 $\text{Move}$ 用于数据传送，$\text{lea}$ 即 $\text{Load Effective Address}$ 用于地址计算。

数据传送语句：mov 0x8(%ebp,%edx,4), %eax 实现的功能为 R[eax] = M[R[ebp] + R[edx] * 4 + 8]。表示将计算出来的地址 R[ebp] + R[edx] * 4 + 8 对应的在存储器中的值 M[R[ebp] + R[edx] * 4 + 8] 赋给寄存器 %eax，此时寄存器中存储的信息为操作数的值 R[eax]。

地址计算语句：lea 0x8(%ebp,%edx,4), %eax 实现的功能为 R[eax] = R[ebp] + R[edx] * 4 + 8。表示将计算出来的地址 R[ebp] + R[edx] * 4 + 8 赋给寄存器 %eax，此时寄存器中存储的信息为操作数的地址 R[eax]。

定点算数运算指令。加减乘除分别为：add, sub, mul, div，都是将「源地址」的值运算到「目的地址」，即左边对应的值运算到右边对应的值。可以记忆为右边的数 +=, -=, *=, /=。

按位运算指令。常用的有按位运算，以及算数、逻辑的左移和右移。按位运算中有一个用于判定单个数情况的指令为 test，test 不修改右边对应的值，其余都遵循上述「左的值运算到右进而改变右」的规则。

移位指令大约有：shl, sal, shr, sar，分别为逻辑左移、算数左移、逻辑右移、算数右移。

控制转移指令。常用的有无条件转移，对应 C 语言中的 goto 关键字，汇编表示为 jmp 等。以及有条件转移，比如 je, jne 等，取决于逻辑运算的结果。转移的位置统称为「目标地址」。

C 语言声明	Intel 操作数类型	汇编指令长度后缀	存储长度（位）
`(unsigned) char`	整数/字节	\(b\)	`8`
`(unsigned) short`	整数/字	\(w\)	`16`
`(unsigned) int`	整数/双字	\(l\)	`32`
`(unsigned) long int`	整数/双字	\(l\)	`32`
`(unsigned) long long int`	-	-	`2*32`
`char *`	整数/双字	\(l\)	`32`
`float`	单精度浮点数	\(s\)	`32`
`double`	双精度浮点数	\(l\)	`64`
`long double`	扩展精度浮点数	\(t\)	`80/96`