第三章 程序的转换及机器级表示

概述

机器级指令和汇编指令一一对应，都是机器级指令。

• 机器指令是一个0/1序列，由若干字段组成。
  
• 汇编指令是机器指令的符号表示，在不同机器上格式可以不同
  比如说：Intel格式：mov [bx+di-6],cl
  AT&T格式：movb %cl, -6(%bx,%di)
  这两条指令的功能其实都是表示M[R[bx]+R[di]-6]←R[cl]，其中R表示的是寄存器内容，M表示的是存储单元内容。

IA-32 指令系统

概述

寄存器组织

编号	8位寄存器	16位寄存器	32位寄存器	64位寄存器	128位寄存器
000	AL	AX	EAX	MM0/ST(0)	XMM0
001	CL	CX	ECX	MM1/ST(1)	XMM1
010	DL	DX	EDX	MM2/ST(2)	XMM2
011	BL	BX	EBX	MM3/ST(3)	XMM3
100	AH	SP	ESP	MM4/ST(4)	XMM4
101	CH	BP	EBP	MM5/ST(5)	XMM5
110	DH	SI	ESI	MM6/ST(6)	XMM6
111	BH	DI	EDI	MM7/ST(7)	XMM7

字长不断扩充，指令保持兼容，ST(0) - ST(7)是80位，MM0 - MM7使用其低64位

IA-32中寄存器名称的含义：

• CS —— 代码段寄存器（Code Segment）
• SS —— 栈段寄存器（Stack Segment）
• DS —— 数据段寄存器（Data Segment）
• ES —— 扩展段寄存器（Extended Segment）
• FS，GS —— 数据段寄存器
• EAX —— 累加寄存器（Extended Accumulator Register）
• ECX —— 计数寄存器（Extended Counter Register）
• EDX —— 数据寄存器（Extended Data Register）
• EBX —— 指向数据段（DS）的指针（Extended Base Register）
• ESI —— 指向数据段（DS）的指针，表示字符串操作的源（Extended Source Index）
• EDI —— 指向数据段（ES）的指针，表示字符串操作的目标（Extended Destination Index）
• EBP —— 指向栈（SS）的指针，一般表示当前栈帧的底部（Extended Base Pointer）
• ESP —— 指向栈（SS）顶的指针（Extended Stack Pointer）
• EIP —— 指令寄存器（Enhanced Instruction Pointer）
• EFLAG —— 标志位寄存器

标志寄存器

• 6个条件标志

1. OF、SF、ZF、CF，功能在前文已经介绍，这里不再赘述
2. AF：辅助进位标志（在BCD码运算时才有意义）
3. PF：奇偶标志

• 3个控制标志

1. DF（Direction Flag）：方向标志（自动变址方向是增还是减）
2. IF（Interrupt Flag）：中断允许标志（仅对外部可屏蔽中断有用）
3. TF（Trap Flag）：陷阱标志（是否是单步跟踪状态）

保护模式下的寻址方式

寻址方式	说明
立即寻址	指令直接给出操作数
寄存器寻址	指定的寄存器R的内容为操作数
位移	$LA=(SR)+A$LA=(SR)+A
基址寻址	$LA=(SR)+(B)$LA=(SR)+(B)
基址加位移	$LA=(SR)+(B)+A$LA=(SR)+(B)+A
比例变址加位移	$LA=(SR)+(I) \times S + A$LA=(SR)+(I)×S+A
基址加变址加位移	$LA=(SR)+(B)+(I)+A$LA=(SR)+(B)+(I)+A
基址加比例变址加位移	$LA=(SR)+(B)+(I) \times S + A$LA=(SR)+(B)+(I)×S+A
相对寻址	$LA=(PC)+A$LA=(PC)+A 跳转目标指令地址

注：LA:线性地址，(X)：X的内容，SR：段寄存器，PC：程序计数器，R：寄存器，A：指令中给定地址段的位移量，B：基址寄存器，I：变址寄存器，S：比例系数

• 举例说明：

int x;
float a[100];
short b[4][4];
char c;
double d[10];

1. 如何计算a[i]的地址？
   $104+i \times 4$104+i×4，当$i=99$i=99时，$Address=104+99 \times 4 = 500$Address=104+99×4=500
2. 如何计算b[i][j]的地址？
   $504 + i \times 8 + j \times 2$504+i×8+j×2，当$i=3,j=2$i=3,j=2时，$Address=504+24+4=532$Address=504+24+4=532
3. 如何计算d[i]的地址？
   $544+i \times 8$544+i×8，当$i=9$i=9时，$Address=544+9 \times 8 = 500$Address=544+9×8=500

机器指令格式

指令类型

传送指令

1.通用数据传送指令

• MOV：一般传送，包括movb、movw和movz等
• MOVS：符号扩展传送，如movsbw、movswl等
• MOVZ：零扩展传送，如movzwl、movzbl等
• XCHG：数据交换
• PUSH/POP：入栈/出栈，如pushl、pushw、popl、popw等

2.地址传送指令

• LEA：加载有效地址，如leal (%edx,%eax), %eax的功能为R[eax]←R[edx]+R[eax]，执行前，若R[edx]=i，R[eax]=j，则指令执行后，R[eax]=i+j

3.输入输出指令

• IN和OUT：I/O端口与寄存器之间的交换

4.标志传送指令

• PUSHF、POPF：将EFLAG压栈，或将栈顶内容送EFLAG

入栈 pushw %ax

1. 栈（Stack）是一种采用“先进后出”方式进行访问的一块存储区，用于嵌套过程调用。从高地址向低地址增长
2. “栈”不等于“堆栈”（由“堆”和“栈”组成）

出栈 popw %ax

定点算术指令

• 加/减运算（影响标志、不区分无/带符号）
  ADD：加，包括addb、addw、addl等
  SUB：减，包括subb、subw、subl等
• 增1/减1运算（影响除CF以外的标志、不区分无/带符号）
  INC：加，包括incb、incw、incl等
  DEC：减，包括decb、decw、decl等
• 取负运算（影响标志、若对0取负，则结果为0且CF清0，否则CF置1）
  NEG：取负，包括negb、negw、negl等
• 比较运算（做减法得到标志、不区分无/带符号）
  CMP：比较，包括cmpb、cmpw、cmpl等
• 乘/除运算（不影响标志、区分无/带符号）
  MUL/IMUL：无符号乘/带符号乘DIV/IDIV：带无符号除/带符号除

1.乘法指令：

• 指令中只给出一个操作数SRC：则另一个源操作数隐含在AL/AX/EAX中，将SRC和累加器内容相乘，结果存放在AX（16位）或DX-AX（32位）或 EDX-EAX（64位）中。DX-AX表示32位乘积的高、低16位分别在DX和AX中。
  得到的结果的位数：$n\text{位}\times n\text{位}=2n\text{位}$n位×n位=2n位
• 指令中给出两个操作数DST和SRC，则将DST和SRC相乘，结果在DST中。
  得到的结果的位数：$n\text{位}\times n\text{位}=n\text{位}$n位×n位=n位
• 指令中给出三个操作数REG、SRC和IMM，则将SRC和立即数IMM相乘，结果在REG中。
  得到的结果的位数：$n\text{位}\times n\text{位}=n\text{位}$n位×n位=n位

2.除法指令

只明显指出除数，用EDX-EAX中内容除以指定的除数

• 若为8位，则16位被除数在AX寄存器中，商送回AL，余数在AH
• 若为16位，则32位被除数在DX-AX寄存器中，商送回AX，余数在DX
• 若为32位，则被除数在EDX-EAX寄存器中，商送EAX，余数在EDX

按位运算

1.移位运算（左/右移时，最高/最低位送CF）

• SHL/SHR: 逻辑左/右移，包括shlb、shrw、shrl等
• SAL/SAR: 算术左/右移，左移判溢出，右移高位补符（移位前、后符号位发生变化，则OF=1 ）包括salb、sarw、sarl等
• ROL/ROR: 循环左/右移，包括rolb、rorw、roll等
• RCL/RCR: 带进位循环左/右移，即：将CF作为操作数 一部分循环移位，包括rclb、rcrw、rcll等
  

注：sarw $1,%ax可简写成sarw %ax

2.逻辑运算

• NOT：非，包括notb、notw、notl等
• AND：与，包括andb、andw、andl等
• OR：或，包括orb、orw、orl等
• XOR：异或，包括xorb、xorw、xorl等
• TEST：做“与”操作测试，仅影响标志

仅NOT不影响标志，其他指令OF=CF=0，而ZF和SF则根据结果设置：若全0，则ZF=1；若最高位为1，则SF=1

控制转移指令

指令执行可按顺序或跳转到转移目标指令处执行

• 无条件转移指令
  JMP DST：无条件转移到目标指令DST处执行
• 条件转移
  Jcc DST：cc为条件码，根据标志（条件码）判断是否满足条件，若满足，则转移到目标指令DST处执行，否则按顺序执行
• 条件设置
  SETcc DST：按条件码cc判断的结果保存到DST（是一个8位寄存器）
• 调用和返回指令（用于过程调用）
  CALL DST：返回地址RA入栈，转DST处执行
  RET：从栈中取出返回地址RA，转到RA处执行
• 中断指令

这里我们可以注意到，调用的函数返回地址是RA，这非常重要

C语言程序的机器级表示

过程调用的机器级表示

过程调用的执行步骤

过程调用的执行步骤(P为调用者，Q为被调用者)

1. P将入口参数（实参）放到Q能访问到的地方；
2. P保存返回地址，然后将控制转移到Q； （CALL指令）
3. Q保存P的现场，并为自己的非静态局部变量分配空间；
4. 执行Q的过程体（函数体）；
5. Q恢复P的现场，释放局部变量空间；
6. Q取出返回地址，将控制转移到P。（RET指令）

IA-32的寄存器使用约定

• 调用者保存寄存器：EAX、EDX、ECX
  当过程P调用过程Q时，Q可以直接使用这三个寄存器，不用将它们的值保存到栈中。如果P在从Q返回后还要用这三个寄存器的话，P应在转到Q之前先保存，并在从Q返回后先恢复它们的值再使用。
• 被调用者保存寄存器：EBX、ESI、EDI
Q必须先将它们的值保存到栈中再使用它们，并在返回P之前恢复它们的值。
• EBP和ESP分别是帧指针寄存器和栈指针寄存器，分别用来指向当前栈帧的底部和顶部。

注意：

1. 所以为了减少准备和结束阶段的开销，每个过程应该先使用EAX、ECX、EDX，这样就不用存栈。
2. 返回参数总在EAX中

过程（函数）的结构

一个C过程的大致结构如下：
准备阶段：

• 形成帧底：push指令 和mov指令
• 生成栈帧（如果需要的话）：sub指令或and指令
• 保存现场（如果有被调用者保存寄存器）：mov指令（为什么？因为所有过程共享一套GPRs）

过程（函数）体：

• 分配局部变量空间，并赋值
• 具体处理逻辑，如果遇到函数调用时，
  (1) 准备参数：将实参送栈帧入口参数处
  (2) CALL指令：保存返回地址并转被调用函数
• 在EAX中准备返回参数

第一个入口参数在EBP+8的位置（EBP存EBP在Caller中的旧值，EBP+4存返回地址）

结束阶段：

• 退栈：leave指令或pop指令
• 取返回地址返回：ret指令

选择和循环语句

1.switch-case语句

movl    8(%ebp),%eax
subl    $10,%eax
cmpl    $7,%eax
ja      .L5
jmp     *.L8(,%eax,4)
.L1
	...
.L2
	...
.L3
	...
.L4
	...
.L5
	...
.L7
	...

跳转表在目标文件的只读节中，按4字节边界对齐。

2.循环结构与递归结构的比较

循环结构一般使用的都是简单变量，直接保存到寄存器中。而递归结构每次都要分配栈空间，时间和空间的开销都非常得大。（比如递归写法的快速幂和迭代写法的快速幂，速度会差几十倍至几十倍（取决于数据范围）。所以，为了提高程序性能，能使用非递归方式执行则最好用非递归结构。

复杂数据类型的分配和访问

数组

数组定义	数组名	数组元素类型	数组元素大小(B)	数组大小(B)	起始地址	元素i的地址
char S[10]	S	char	1	10	&S[0]	&S[0]+i
char* SA[10]	SA	char*	4	40	&SA[0]	&SA[0]+4*i
double D[10]	D	double	8	80	&D[0]	&D[0]+8*i
double* DA[10]	DA	double*	4	40	&DA[0]	&DA[0]+4*i

数组元素和指针变量的表达式计算示例：

序号	表达式	类型	值的计算方式	汇编代码
1	A	int*	SA	leal (%ecx),%eax
2	A[0]	int	M[SA]	movl (%ecx),%eax
3	A[i]	int	M[SA+4*i]	movl (%ecx,%edx,4),%eax
4	&A[3]	int*	SA+12	leal 12(%ecx),%eax
5	&A[i]-A	int	(SA+4*i-SA)/4=i	movl %edx,%eax
6	*(A+i)	int	M[SA+4*i]	movl (%ecx,%edx,4),%eax
7	*(&A[0]+i-1)	int	M[SA+4*i-4]	movl -4(%ecx,edx,4),%eax
8	A+i	int*	SA+4*i	leal (%ecx,%edx,4),%eax

指针数组和多维数组：

• 由若干指向同类目标的指针变量组成的数组称为指针数组。
  其定义的一般形式如下：
  存储类型 数据类型 *指针数组名[元素个数]
  例如，int *a[10];定义了一个指针数组a，它有10个元素，每个元素都是一个指向int型数据的指针。
• 一个指针数组可以实现一个二维数组

结构体和联合体

结构体成员在内存的存放和访问

• 分配在栈中的auto结构型变量的首地址由EBP或ESP来定位
• 分配在静态区的结构型变量首地址是一个确定的静态区地址
• 结构型变量 x 各成员首址可用“基址加偏移量”的寻址方式

结构体数据作为入口参数：

首先，当结构体变量需要作为一个函数的形参时，形参和调用函数中的实参应具有相同结构。

然后，其传递有两种方式：

• 若采用按值传递，则结构成员都要复制到栈中参数区，这既增加时间开销又增加空间开销，且更新后的数据无法在调用过程使用
• 通常应按地址传递，即：在执行CALL指令前，仅需传递指向结构体的指针而不需复制每个成员到栈中

联合体数据的分配和访问

联合体各成员共享存储空间，按最大长度成员所需空间大小为目标

注：联合体通常用于特殊场合，如，当事先知道某种数据结构中的不同字段的使用时间是互斥的，就可将这些字段声明为联合，以减少空间。但有时会得不偿失，可能只会减少少量空间却大大增加处理复杂性。

数据的对齐存放

为什么要对齐

各种不同长度的数据存放时，有两种处理方式:

• 按边界对齐（若一个字为32位）
  字地址：4的倍数(低两位为0)
  半字地址：2的倍数(低位为0)
  字节地址：任意
• 不按边界对齐
  坏处：可能会增加访存次数

对齐方式的设定

#pragma pack(n)

• 为编译器指定结构体或类内部的成员变量的对齐方式。
• 当自然边界（如int型按4字节、short型按2字节、float按4字节）比n大时，按n字节对齐。
• 缺省或#pragma pack() ，按自然边界对齐。

__attribute__((aligned(m)))

• 为编译器指定一个结构体或类或联合体或一个单独的变量(对象)的对齐方式。
• 按m字节对齐(m必须是2的幂次方)，且其占用空间大小也是m的整数倍，以保证在申请连续存储空间时各元素也按m字节对齐。

__attribute__((packed))

• 不按边界对齐，称为紧凑方式。

越界访问和缓冲区溢出

先看一个例子直观感受：

当i>1的时候，就出现了问题，因为数组访问越界了，影响到了其他位置的值甚至直接爆栈。

C语言程序中对数组的访问可能会有意或无意地超越数组存储区范围而无法发现。

数组存储区可看成是一个缓冲区，超越数组存储区范围的写入操作
称为缓冲区溢出。
例如，对于一个有10个元素的char型数组，其定义的缓冲区有10个字节。若写一个字符串到这个缓冲区，那么只要写入的字符串多于9个字符（结束符‘\0’占一个字节），就会发生“写溢出”。

带来的破坏：

• 缓冲区溢出是一种非常普遍、非常危险的漏洞，在各种操作系统、
  应用软件中广泛存在。
• 缓冲区溢出攻击是利用缓冲区溢出漏洞所进行的攻击。利用缓冲区
  溢出攻击，可导致程序运行失败、系统关机、重新启动等后果。

x86-64 体系

x86-64操作数格式

操作数的寻址有如下方式：

• 立即数，用来表示常数值，书写方式为’$'加标准C表示法表示的整数，如$-577或$0x1F。
• 寄存器，R[ra]表示ra寄存器的内容。
• 内存引用，M[Addr]表示地址为Addr的存储单元内的值

立即数Imm、基址寄存器rb、变址寄存器ri、比例因子s（其值为1、2、4、8）。

类型	格式	操作数值	名称
立即数	$Imm	Imm	立即数寻址
寄存器	ra	R[ra]	寄存器寻址
存储器	Imm	M[Imm]	绝对寻址
存储器	(ra)	M[R[ra]]	间接寻址
存储器	Imm(rb)	M[Imm+R[rb]]	（基址+偏移量）寻址
存储器	(rb,ri)	M[R[rb]+R[ri]]	变址寻址
存储器	Imm(rb,ri)	M[Imm+R[rb]+R[ri]]	变址寻址
存储器	(,ri,s)	M[R[ri]*s]	比例变址寻址
存储器	Imm(,ri,s)	M[Imm+R[ri]*s]	比例变址寻址
存储器	(rb,ri,s)	M[R[rb]+R[ri]*s]	比例变址寻址
存储器	Imm(rb,ri,s)	M[Imm+R[rb]+R[ri]*s]	比例变址寻址

x86-64寄存器

X86-64有16个64位寄存器，分别是：rax，rbx，rcx，rdx，esi，edi，rbp，rsp，r8，r9，r10，r11，r12，r13，r14，r15。其中：

• rax 作为函数返回值使用。
• rsp 栈指针寄存器，指向栈顶
• rdi，rsi，rdx，rcx，r8，r9 用作函数参数，依次对应第1参数，第2参数……
• rbx，rbp，r12，r13，r14，r15 用作数据存储，遵循被调用者使用规则，简单说就是随便用，调用子函数之前要备份它，以防他被修改
• r10，r11 用作数据存储，遵循调用者使用规则，简单说就是使用之前要先保存原值

注：

• 最多有六个整形或指针型参数通过寄存器传递，超过六个只能通过栈来传递（所以在传递参数的时候尽量保证传递的参数个数在6个以内，如果是数组就用传递指针，这样可以提高程序的运行效率）
• 在函数中尽量使用rax,r10，r11，若使用rbx,rbp,r12，r13，r14,r15则需要将它们先保存在栈中在使用，最后返回前再恢复其值

63~0位	31~0位	15~0位	7~0位	用途
%rax	%eax	%ax	%al	返回值
%rbx	%ebx	%bx	%bl	被调用者保存
%rcx	%ecx	%cx	%cl	第4个参数
%rdx	%edx	%dx	%dl	第3个参数
%rsi	%esi	%si	%sil	第2个参数
%rdi	%edi	%di	%dil	第1个参数
%rbp	%ebp	%bp	%bpl	被调用者保存
%rsp	%esp	%sp	%spl	栈指针
%r8	%r8d	%r8w	%r8b	第5个参数
%r9	%r9d	%r9w	%r9b	第6个参数
%r10	%r10d	%r10w	%r10b	调用者保存
%r11	%r11d	%r11w	%r11b	调用者保存
%r12	%r12d	%r12w	%r12b	被调用者保存
%r13	%r13d	%r13w	%r13b	被调用者保存
%r14	%r14d	%r14w	%r14b	被调用者保存
%r15	%r15d	%r15w	%r15b	被调用者保存