计算机系统基础第一章到第三章知识点梳理

第一章系统概述

1-1

这张图说的真的好，虽然和知识没有什么关系，最初看到也觉得没什么，但是学了大半学期再倒回来看这些话，我认为是十分正确的。同样的代码，不同的写法，效率可能差上成百上千倍。然后就是特别是通过bomb lab，做了之后我对整个C语言的理解都不一样了。知其然，更要知其所以然，可能这就是系统的魅力吧！

为什么要学习计算机系统

为了编程序的时候少出错（逻辑性，准确性，内存溢出等）
为了在程序出错的时候很快找到出错的地方（gdb调试，或者直接查看汇编指令，找到错误）
为了明白程序是怎样在计算机上执行的（利用程序执行的原理，可以编写出更快的程序）
作为计算机专业的同学应该具有的底层意识。

计算机基本工作原理

一些基本的概念。

冯·诺依曼体系

冯·诺依曼结构最重要的思想是存储程序。

计算机的基本部件：控制器、存储器、运算器、输入设备和输出设备。~~（计导必考题目！！）~~
存储器不仅能存放数据，而且也能存放指令，形式上两者没有区别，但计算机应能区分数据还是指令。
控制器应能自动取出指令来执行。
运算器应能进行加/减/乘/除四种基本算术运算，并且也能进行一些逻辑运算和附加运算。
操作人员可以通过输入设备、输出设备和主机进行通信。
内部以二进制表示指令和数据。每条指令由操作码和地址码两部分组成。操作码指出操作类型，地址码指出操作数的地址。由一串指令组成程序。
采用“存储程序”工作方式。

计算机是如何工作的

1-1-2

图中的部件解释：

CPU：中央处理器
PC：程序计数器
MAR：存储器地址寄存器
ALU：算术逻辑部件
IR：指令寄存器
MDR：存储器数据寄存器
GPRs：通用寄存器组（由若干通用寄存器组成，早期就是累加器）

程序执行前：

数据和指令事先存放在存储器中，每条指令和每个数据都有地址，指令按序存放，指令由OP、ADDR字段组成，程序起始地址置PC

注意：

程序启动前，指令和数据都存放在存储器中，形式上没有差别，都是0/1序列
采用”存储程序“工作方式：程序由指令组成，程序被启动后，计算机能自动取出一条一条指令执行，在执行过程中无需人的干预。
指令中需要给出的信息：
(1) 操作性质（操作码）
(2) 源操作数1 或/和源操作数2（立即数、寄存器编号、存储地址）
(3) 目的操作数地址（寄存器编号、存储地址）

开始执行程序：

第一步：根据PC取指令
第二步：指令译码
第三步：取操作数
第四步：指令执行
第五步：回写结果
第六步：修改PC的值
继续执行下一条指令

程序的开发和执行

机器语言

机器语言就是0/1代码啦！在计算机科学导论中我们也动手写了图灵机的操作（虽然我们班好像没有要求，但因为某种原因我写过几份，现在回想起来也挺有趣的）。感觉机器语言和图灵机有点类似，通过读写纸带和打孔之类的。

但是，如果要修改，或者打错了，那么就要从头再来，非常地崩溃，可读性也非常差。

汇编语言

用助记符表示操作码
用标号表示位置
用助记符表示寄存器

优点：

不会因为增减指令而需要修改其他指令
不需记忆指令编码，编写方便
可读性比机器语言强

1-2-2

高级语言

它们与具体机器结构无关
面向算法描述，比机器级语言描述能力强得多
高级语言中一条语句对应几条、几十条甚至几百条指令
有“面向过程”和“面向对象”的语言之分
处理逻辑分为三种结构：顺序结构、选择结构、循环结构
有两种转换方式：“编译”和“解释”
• 编译程序(Complier)：将高级语言源程序转换为机器级目标程序，执行时只要启动目标程序即可，比如C++、C、Java等
• 解释程序(Interpreter )：将高级语言语句逐条翻译成机器指令并立即执行，不生成目标文件，比如Python等

源代码的处理

1-2-3-1

1-2-3-2

计算机的层次结构

1-3-1

1-3-2

计算机性能的定义

这部分在书上有，mooc上没有。其主要指标为吞吐率(throughput)和响应时间(response time)

吞吐率：在单位时间内所完成的工作量。
响应时间：从作业提交开始到作业完成所用的时间。

第二章数据的机器级表示与处理

数制和编码

十进制、二进制、十六进制、八进制……
定/浮点表示

数制

十进制(Decimal)：结尾加D表示。
二进制(Binary)：结尾加B表示。
八进制(Octal)：结尾加O表示。
十六进制(Hexadecimal)：结尾加H表示或者前缀加0x表示。

进制转换：

整数部分：除基取余，上左下右
小数部分：乘基取整，上左下右

定点数和浮点数

计算机中只能通过约定小数点的位置来表示小数点

小数点位置约定在固定位置的数称为定点数
小数点位置约定为可浮动的数称为浮点数

实数的定义： $X=(-1)^s \times M \times R^E$
其中 $S$ 取值为 $0$ 或者 $1$ ，用来决定数 $X$ 的符号； $M$ 是尾数， $E$ 是阶/指数。 $R$ 是基数。

定点数的编码

原码、补码、移码、反码

原码：最高位的 $0$ / $1$ 表示正负，数值部分不变。但是缺点有： $0$ 的表示不唯一，不利于编程；加减运算方式不统一；对硬件设计的要求较高；特别是当 $a<b$ 时候，实现 $a-b$ 比较困难。
补码（从50年代以来整数采用的编码方式）： $[X]_\text{补}=2^n + X$ 。同时补码实现了加和减的统一。
结论一：一个负数的补码等于模减该负数的绝对值
结论二：对于某一确定的模，某数减去小于模的另一数，总可以用该数加上另一数负数的补码来代替实现了加法和减法的统一。
变形补码：采用双符号位存放可能溢出的中间结果。
负数的补码的简便求法：从右至左遇到的第一个 $1$ 的前面各位取反（不含这个 $1$ ）
移码：将每一个数值加上一个偏置常数bias。
反码：直接将二进制按位取反，一般没什么用。

C语言中的数

整数

2-2-1-1

其中整数类型分为带符号整数和无符号整数。

2-2-1-2

整数表示比较简单，大概熟悉C语言的程序员都掌握的比较好。

浮点数

浮点数的表示就很复杂了，编码上有许多细节。

首先是对科学计数法的概念：

2-2-2-1

浮点数的表示范围：

2-2-2-2

第0位数符S；第1-8位为8位移码表示阶码 $E$ （偏置常数为128）
第9～31位为24位二进制原码小数表示的尾数 $M$ 。规格化尾数的小数点后第一位总是1，故规定第一位默认的“1”不明显表示出来。这样可用23个数位表示24位尾数

最大正数： $0.11 \dots 1 \times 2^{11 \dots 11} = (1-2^{-24}) \times 2 ^{127}$
最小正数： $0.10 \dots 0 \times 2^{00 \dots 0} = (1/2) \times 2^{-128}$

2-2-2-3

IEEE 754 标准(重点)

2-2-2-4

规格化数

Exponent	Significand
1-254	任意小数点前隐含1
0	0	+/-0
255	0	+/-inf
255	nonzero	NaN

非规格化数

当 $Exponent == 0$ 并且 $Significand != 0$ 时，用来表示非规格化数。

2-2-2-5

非数值表示

西文字符

ASCII控制字符

二进制	十进制	十六进制	缩写	可以显示的表示法	名称/意义
0000 0000	0	00	NUL	␀	空字符（Null）
0000 0001	1	01	SOH	␁	标题开始
0000 0010	2	02	STX	␂	本文开始
0000 0011	3	03	ETX	␃	本文结束
0000 0100	4	04	EOT	␄	传输结束
0000 0101	5	05	ENQ	␅	请求
0000 0110	6	06	ACK	␆	确认回应
0000 0111	7	07	BEL	␇	响铃
0000 1000	8	08	BS	␈	退格
0000 1001	9	09	HT	␉	水平定位符号
0000 1010	10	0A	LF	␊	换行键
0000 1011	11	0B	VT	␋	垂直定位符号
0000 1100	12	0C	FF	␌	换页键
0000 1101	13	0D	CR	␍	归位键
0000 1110	14	0E	SO	␎	取消变换（Shift out）
0000 1111	15	0F	SI	␏	启用变换（Shift in）
0001 0000	16	10	DLE	␐	跳出数据通讯
0001 0001	17	11	DC1	␑	设备控制一（XON 启用软件速度控制）
0001 0010	18	12	DC2	␒	设备控制二
0001 0011	19	13	DC3	␓	设备控制三（XOFF 停用软件速度控制）
0001 0100	20	14	DC4	␔	设备控制四
0001 0101	21	15	NAK	␕	确认失败回应
0001 0110	22	16	SYN	␖	同步用暂停
0001 0111	23	17	ETB	␗	区块传输结束
0001 1000	24	18	CAN	␘	取消
0001 1001	25	19	EM	␙	连接介质中断
0001 1010	26	1A	SUB	␚	替换
0001 1011	27	1B	ESC	␛	跳出
0001 1100	28	1C	FS	␜	文件分割符
0001 1101	29	1D	GS	␝	组群分隔符
0001 1110	30	1E	RS	␞	记录分隔符
0001 1111	31	1F	US	␟	单元分隔符
0111 1111	127	7F	DEL	␡	删除

ASCII可显示字符

二进制	十进制	十六进制	图形
0010 0000	32	20	（空格）(␠)
0010 0001	33	21	!
0010 0010	34	22	"
0010 0011	35	23	#
0010 0100	36	24	$
0010 0101	37	25	%
0010 0110	38	26	&
0010 0111	39	27	'
0010 1000	40	28	(
0010 1001	41	29	)
0010 1010	42	2A	*
0010 1011	43	2B	+
0010 1100	44	2C	,
0010 1101	45	2D	-
0010 1110	46	2E	.
0010 1111	47	2F	/
0011 0000	48	30	0
0011 0001	49	31	1
0011 0010	50	32	2
0011 0011	51	33	3
0011 0100	52	34	4
0011 0101	53	35	5
0011 0110	54	36	6
0011 0111	55	37	7
0011 1000	56	38	8
0011 1001	57	39	9
0011 1010	58	3A	:
0011 1011	59	3B	;
0011 1100	60	3C	<
0011 1101	61	3D	=
0011 1110	62	3E	>
0011 1111	63	3F	?

二进制	十进制	十六进制	图形
0100 0000	64	40	@
0100 0001	65	41	A
0100 0010	66	42	B
0100 0011	67	43	C
0100 0100	68	44	D
0100 0101	69	45	E
0100 0110	70	46	F
0100 0111	71	47	G
0100 1000	72	48	H
0100 1001	73	49	I
0100 1010	74	4A	J
0100 1011	75	4B	K
0100 1100	76	4C	L
0100 1101	77	4D	M
0100 1110	78	4E	N
0100 1111	79	4F	O
0101 0000	80	50	P
0101 0001	81	51	Q
0101 0010	82	52	R
0101 0011	83	53	S
0101 0100	84	54	T
0101 0101	85	55	U
0101 0110	86	56	V
0101 0111	87	57	W
0101 1000	88	58	X
0101 1001	89	59	Y
0101 1010	90	5A	Z
0101 1011	91	5B	[
0101 1100	92	5C	\
0101 1101	93	5D	]
0101 1110	94	5E	^
0101 1111	95	5F	_

二进制	十进制	十六进制	图形
0110 0000	96	60	`
0110 0001	97	61	a
0110 0010	98	62	b
0110 0011	99	63	c
0110 0100	100	64	d
0110 0101	101	65	e
0110 0110	102	66	f
0110 0111	103	67	g
0110 1000	104	68	h
0110 1001	105	69	i
0110 1010	106	6A	j
0110 1011	107	6B	k
0110 1100	108	6C	l
0110 1101	109	6D	m
0110 1110	110	6E	n
0110 1111	111	6F	o
0111 0000	112	70	p
0111 0001	113	71	q
0111 0010	114	72	r
0111 0011	115	73	s
0111 0100	116	74	t
0111 0101	117	75	u
0111 0110	118	76	v
0111 0111	119	77	w
0111 1000	120	78	x
0111 1001	121	79	y
0111 1010	122	7A	z
0111 1011	123	7B	{
0111 1100	124	7C	\|
0111 1101	125	7D	}
0111 1110	126	7E	~

汉字

汉字的区位码：由94行、94列组成，行号为区号，列号为位号。
汉字的国标码：将区号和位号各自加上32(20H)。国标码中区号和位号各占7位。在计算机内部，为方便处理与存储，前面添一个0，构成一个字节。
至少需要2个字节才能表示一个汉字内码（因为汉字总数超过6万个）

数据宽度和储存容量

容量单位

中文	表示	转化
千字节	KB	$1KB = 2^{10} \text{字节} = 1024 B$
兆字节	MB	$1MB = 2^{20} \text{字节} = 1024 KB$
千兆字节	GB	$1GB = 2^{30} \text{字节} = 1024 MB$
兆兆字节	TB	$1TB = 2^{40} \text{字节} =1024 GB$

通信中的带宽单位

中文	表示	转化
千比特/秒	kb/s	$1kbps = 10^{3} b/s = 1000 bps$
兆比特/秒	Mb/s	$1Mb/s = 10^{6} b/s = 1000 kbps$
千兆比特/秒	Gb/s	$1Gb/s = 10^{9} b/s = 1000 Mbps$
兆兆比特/秒	Tb/s	$1Tb/s = 10^{12} b/s =1000 Gbps$

注意：容量单位和带宽单位里面明显大小写有一些不一样，因为表示的含义不同，一个是1000，一个1024.

C语言中数据类型的宽度

C声明	典型32位机器(单位：字节)	典型64位机器(单位：字节)
char	1	1
short int	2	2
int	4	4
long int	4	8
char*	4	8
float	4	4
double	8	8

long double 的确切精度没有规定，所以对于不同平台来说，有的是8字节，有的是10字节，有的是12字节或者16字节。

数据的存储和排列顺序

80年代开始，几乎所有通用计算机都采用字节编址。在高级语言中声明的基本数据类型有char、short、int、long、long long、float、double、long double等各种不同长度数据，一个基本数据可能会占用多个存储单元。所以有一些问题我们还需要考虑，比如说：变量的地址是其最大地址还是最小地址？多个字节在存储单元中存放的顺序如何？

大/小端方式

2-5-1-1

测试代码：

#include &lt; cstdio &gt;
#include &lt; cstring &gt;
#include &lt; algorithm &gt;
using namespace std;
const int maxn=200005;

int main()
{
	union NUM
	{
		int a;
		char b;
	} num;
	num.a=0x12345678;
	if(num.b==0x12) printf("Big Endian\n");
	else printf("Little Endian\n");
	printf("num.b=0x%X\n",num.b);
	return 0;
}

在我的机器上运行的结果：

2-5-1-2

大小端非常重要，因为在看指令的时候，大小端不同，表示的值就不同。
注意：IA-32采用的是小端方式。

数字逻辑电路

布尔代数

$A$	$B$	$A \cdot B$	$A+B$	$\bar{A}$	$A \oplus B$
0	0	0	0	1	0
0	1	0	1	1	1
1	0	0	1	0	1
1	1	1	1	0	0

全加器(一位加法器)

两个加数为 $A$ 和 $B$ ，低位进位为Cin，和为 $F$ ，向高位的进位为Cout。
化简之后，逻辑表达式如下：

$F=A \oplus B \oplus Cin$

$Cout=A \cdot B + A \cdot Cin + B \cdot Cin$

2-6-2

n位加法器

n位加法器可用n个全加器实现

无符号整数加

2-6-3-1-1

2-6-3-1-2

带符号整数加

溢出标志OF： $OF=C_n \oplus C_{n-1}$
符号标志SF： $SF=F_{n-1}$
零标志ZF： $ZF=1$ 当且仅当 $F=0$
进位/借位标志CF： $CF=Cout \oplus Cin$

2-6-3-2-1

2-6-3-2-2

n位整数加/减运算器

$[A+B]_{\text{补}} = [A]_{\text{补}} + [B]_{\text{补}} (mod\;\;2^n)$
$[A-B]_{\text{补}} = [A]_{\text{补}} + [-B]_{\text{补}} (mod\;\;2^n)$

2-6-4-1

当 $Sub$ 为 $1$ 时，做减法。
当 $Sub$ 为 $0$ 时，做加法。

算术逻辑部件ALU：

2-6-4-2

数据的运算

高级语言程序中涉及的运算（以C语言为例）

整数算术运算、浮点数算术运算
按位、逻辑、移位、位扩展和位截断等运算

指令集中涉及到的运算：

涉及到的定点数运算：

算术运算：

带符号整数：取负/ 符号扩展/ 加/ 减/ 乘/ 除 / 算术移位
无符号整数：0扩展/ 加/ 减/ 乘/ 除/ 逻辑左移/ 逻辑右移

逻辑运算：

逻辑操作：与/ 或/ 非/ …

涉及到的浮点数运算：加、减、乘、除

指令中的运算操作在运算电路中进行

基本运算部件ALU、通用寄存器组，以及其他部件

整数的加减运算

计算机中所有运算都基于加法器实现。
加法器不知道所运算的是带符号数还是无符号数。
加法器不判定对错，总是取低n位作为结果，并生成标志信息。

无符号数

加法：

当 $x+y < 2^n, result=x+y$
当 $2^n \leq x+y < 2^{n+1}, result=x+y-2^n$

减法：

当 $x-y<0, result=x-y+2^n$
当 $x-y \geq 0, result=x-y$

带符号数

加法：

当 $x+y<-2^{n-1}, result=x+y+2^n$ ，负溢出
当 $-2^{n-1} \leq x+y < 2^{n-1}, result=x+y$ ，正常
当 $x+y \geq 2^{n-1}, result=x+y-2^n$ ，正溢出

减法：

当 $x-y<-2^{n-1}, result=x-y+2^n$ ，负溢出
当 $-2^{n-1} \leq x-y <2^{n-1}, result=x-y$ ，正常
当 $x-y \geq 2^{n-1}, result=x-y-2^n$ ，正溢出

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

概述

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

机器指令是一个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 指令系统

概述

寄存器组织

3-2-1-1

编号	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个条件标志

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

3个控制标志

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

保护模式下的寻址方式

寻址方式	说明
立即寻址	指令直接给出操作数
寄存器寻址	指定的寄存器R的内容为操作数
位移	$LA=(SR)+A$
基址寻址	$LA=(SR)+(B)$
基址加位移	$LA=(SR)+(B)+A$
比例变址加位移	$LA=(SR)+(I) \times S + A$
基址加变址加位移	$LA=(SR)+(B)+(I)+A$
基址加比例变址加位移	$LA=(SR)+(B)+(I) \times S + 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];

3-2-1-3

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

机器指令格式

3-2-1-4

指令类型

传送指令

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

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

3-2-2-1-1

出栈 popw %ax

3-2-2-1-2

定点算术指令

加/减运算（影响标志、不区分无/带符号）
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{位}$
指令中给出两个操作数DST和SRC，则将DST和SRC相乘，结果在DST中。
得到的结果的位数： $n\text{位}\times n\text{位}=n\text{位}$
指令中给出三个操作数REG、SRC和IMM，则将SRC和立即数IMM相乘，结果在REG中。
得到的结果的位数： $n\text{位}\times n\text{位}=n\text{位}$

2.除法指令

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

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

3-2-2-2-1

按位运算

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，这非常重要

3-2-2-4

C语言程序的机器级表示

过程调用的机器级表示

过程调用的执行步骤

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

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

3-3-1-1

IA-32的寄存器使用约定

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

注意：

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

过程（函数）的结构

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

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

过程（函数）体：

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

3-3-1-3

第一个入口参数在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字节边界对齐。

3-3-1-4-1

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))

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

越界访问和缓冲区溢出

先看一个例子直观感受：

3-4-4-4

当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	被调用者保存