CSAPP 学习笔记 [ 持续更新中 ]

CSAPP

逻辑运算

布尔运算支持&对|的分配律：$a&(b|c)=(a&b)|(a&c)$，同时也支持|对&的分配律：$a|(b&c)=(a|b)&(a|c)$

通过xor我们也可以实现两个数的交换，但是并没有性能上的提升

相似的我们可以通过这个方式来实现数组的存储逆转，长度为偶数时函数会得到正确结果，以1234为例程序运行后的结果是4321，但是在长度为奇数个时，便会出现问题。以12345为例，输出的结果是54021。因为在中间到first和last相同时xor的是自己异或自己得到的便会是0，因此出现问题。对此我们只需要把first<=last修改为first<last即可。

我们可以利用位级和逻辑运算编写一个表达式，使其等价于x==y，即x和y相等时就返回1，否则就返回0。

return ！(x^y) ;

值得注意的是在移位时需要注意参数x的类型，在带符号位时需要对其用操作数的最高位(符号位)来进行补全。而不带符号的参数x则是补0即可。

对于补码转无符号数我们可以总结出来如下规律：

相反无符号数转补码为：

大致整理如下：

1. 无符号数转换为有符号数：看无符号数的最高位是否为1，如果不为1（即为0），则有符号数就直接等于无符号数；

2. 如果无符号数的最高位为1，则将无符号数取补码，得到的数就是有符号数。

3. 有符号数转换为无符号数 ：看有符号数的最高位是否为1，如果不为1（即为0），则无符号数就直接等于有符号数；

4. 如果有符号数的最高位为1，则将有符号数取补码，得到的数就是无符号数。

相关知识点：

1. 在C语言中，一个有符号数与一个无符号数进行运算，那么C语言会将有符号数强制转换为无符号数来执行运算。

2. 当一个有符号数从一个较小的数据类型转换成较大的数据类型时，进行符号位扩展，可以保持数值不变

3. 当一个有符号数从一个较大的数据类型转换成较小的数据类型时，会丢弃对应高位的数据，保留低位的数据，而可能改变其值。

   • 无符号数截断相当于对对应2的k次方进行取模
   • 有符号数截断相当于先将其无符号数对对应2的k次方进行取模，再将其得到的无符号数转为有符号数

4. C语言在执行加法时，不会对溢出发生报错，根据两个数的和必定大于两数之中任何一个，对此我们可以编写相关函数来检测是否发生了溢出。

   int over_flow(int a,int b){
   	int sum=a+b;
   	if(sum>=a){
   		return 1;
   	}else{
   		return 0;
   	}
   }

5. 对于有符号数加法数据溢出后的结果我们可以分为三类：

   

发生正数溢出时得到的结果时两个数的和减去对应二进制位长最大能表示的数据，而负数则是加上对应二进制位长最大能表示的数据。

6. 对于减法，我们引用一个概念加法逆元 ，我们减去一个数可以理解为加上一个数的相反数，对此我们对无符号数进行求解其逆元可以分为如下两个情况：

   

而对于有符号数可以分成：

7. 两个无符号数相乘可能需要2w位来存储数据，但是C语言中定义了无符号数的乘法所产生的结果是w位，因此，对于计算结果，会对其截断，保留低w位。即运算过程为：$( x * y )%2^w$

而对于有符号数的相乘于无符号数是相似的，但是需要把结果转换为有符号数，即：$U_2T_w( ( x * y )%2^w )$

8. 对于除法3而言可能会出现小数的情况，对此我们总是将其向0进行取整，与逻辑右移k位是相同的，而对于有符号的数进行除法时，我们需要引入一个偏置来修正不合适的舍入。偏置的值为1左移k位后减去1，而偏置是怎么参与其中的？

   对于x 大于等于 0的情况，我们可以直接进行算术右移，而当x小于0时，我们需要将x 加上对应的偏置后再进行右移。但可惜的是其不能推广到除以任意常数，仅限至于除以2 的 k 次幂

9. 浮点数的相关二进制位的权重如图：

   

但是这个方式无法表示较大的数据，在IEEE中我们引入一个新的方式来进行表示：

s ：符号位 | exp： 阶码 | frac：小数字段

其中数值大致可以分为三类：

• 规格化的值

  当阶码的二进制位不全为 0 ，且不全为 1 时，此时表示的是规格化的值。

  

  对于图中E的值并不是解码所对应的值，而是需要其减去一个偏置，对于float和double的偏置是不相同的，则以float为例，其最小最大 E 值如下：$E_{min}=-126\ \ \ \ | \ \ \ \ E_{max}=127$

在小数字段上，尾数 M 被定义为 1+f，尾数的二进制表示如图：

因为我们可以调整 E 的取指，使得尾数 M 的取值范围大于等于 1 ，小于 2 ，既然第一位总是一，那么就没有必要显示的表示出来，这也就是为什么尾数 M 的值需要加一。

• 非规格化的值

  当阶码的二进制位全为 0 时，此时表示的是非规格化的值。其大概有两个用途，其一是表示 0 ，其二是表示非常接近 0 的数。

  

  若表示非常接近 0 的数，则阶码字段全为 0 ，阶码 E 的值等于E = 1 - bias, 尾数 M 的值是 f ( M = f )。

  +0.0 和 -0.0 在某些方面认为时不同的，而在其他方面是相同的。

• 特殊值

  当阶码的二进制位全为 1 时，表示的数值是特殊值。特殊值分为两类，一类表示无穷大或者无穷小，另外一类表示不是一个数。

  

​ 如我们输出下列数据，得到的返回值便是 NaN(不是一个数)，如：$\sqrt{-1}\ \ \ \ | \ \ \ \ \infty-\infty$

10. 向偶数舍入，取决于那边是偶数位，如 1.5 处于 1 和 2 中间，那么向偶数舍入便是向 2 进行舍入，得到结果 2，再以 2.5 为例子，其处于 2 和 3 中间，向偶数舍入便是 2 。
11. 浮点数的计算不符合结合律和分配律
12. 乘法指令运行时需要多个时钟周期，因此运行会十分缓慢，多数情况下技术按及会使用移位加减法来实现对应的乘法运算。也正如第 7 点所提到的，计算机会在溢出时采取截尾的方式来存储数据。
13. 源码取反加一为补码

对此我们总结一般不要使用无符号数，并且大多编译器都不支持无符号数，它带来的问题总是比其所具有的优势多，也需要十分小心的使用浮点数运算，因为其只有有限的范围和精度，且补遵守普遍的算术属性，如结合性。

程序的机器级表示

MOV 指令

ATT格式的汇编代码中，立即数的书写方式是$后面更衣柜用标准 C 表示的整数，如$-577或者$0x1F。用$r_a$表示任意寄存器a，引用$R[r_a]$来表示其值，用$M_b[Addr]$表示对存储在内存中从地址Adrr开始的 b 字节的引用。

操作数格式：
操作数可以表示立即数 ( 常数 ) 值 、寄存器值或者是来自内存的值 ，比例因子 s 必须是 1、2、4 或者 8

MOV指令在后面加上对应的字母表示传送不同字节大小的数据，其中b -> 1字节 w -> 2字节 l -> 4字节 q -> 8字节

源操作数指定的值是一个立即数，春促与寄存器或者内存之中。目的操作数指定一个位置，要么是是一个寄存器或者，要么是一个内存地址。MOV指令的两个操作数不能都指向内存地址，将一个值从内存位置复制到另一个内存位置需要两条指令，第一条将源值加载到寄存器中，第二条指令将该寄存器写入目的位置。

在两类数据移动指令中MOVZ类中的指令会把目的中剩余的字节填充为0，而MOVS类中的指令会进行符号位的扩展，即用符号位来填充剩余的字节。

3-5中并没有明确指令把 4 字节源值扩展到 8 字节的目的，按逻辑上应该被称为movzlq但是并不存在这样的指令，不过可以通过以寄存器为目的的movl指令来实现。原理是，生成 4 字节值并以寄存器为目的的指令会把高 4 字节设置为 0 。

我们举一个传送数据的例子来了解一下MOV是如何传递值来改变寄存器的

可以看到左边是源数据，右边是目的数，将左边的数据传递到右边，在这个过程中，我们需要注意到-1的 16 进制位是FF···F，而对于寄存器rax的结构如下图：

可以看到低 8 位是al，在第二行的代码中movb将``-1的值传递给了其低 8 位 ( 低两位字节 ) ，而其余字节保持不变，movw把低 16 位( 低位四字节 ) 设置为了FFFF ，而其余字节保持不变，movl将低 32 位( 低位八字节 )设置为FFFFFFFF同时把高位四字节设置为00000000，而最后的movq把整个寄存器值设置为了FFFFFFFFFFFFFFFF`

习题 3.3

相关指令的错误使用：

movb $0xF,(%ebx) 错误：不能使用%ebx作为地址寄存器
movl %rax,(%rsp) 错误：指令后缀和寄存器id不匹配
movw (%rax),4(%rsp) 错误：不能直接从内存移动到内存
movb %al,%sl 错误：没有叫做%sl的寄存器
movq %rax,$0x123 错误：目的操作数不能是立即数
movl %eax,%rdx 错误：目的操作数大小不正确
movb %si,8(%rbp) 错误：指令后缀和寄存器id不匹配（%si是16bit寄存器）

在栈这个数据结构中我们可以使用push将数据压入栈，通过pop把数据删除，其具有一个属性：弹出的值永远是最近被压入而且仍在栈中的值。栈指针 ( %rsp ) ，压栈是减小栈指针的值，并将数据存放到内存中，而出栈是从内存中读取数据，并增加栈指针的值。

(1）ESP：栈指针寄存器(extended stack pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的栈顶。

（2）EBP：基址指针寄存器(extended base pointer)，其内存放着一个指针，该指针永远指向系统栈最上面一个栈帧的底部。

ADD 指令

ADD指令由四条加法组成：addb、addw、addl、addq分别表示字节加法、字加法、双字加法、和四字加法。通常来说，每个指令都会存在上述对应的b、w、l、q，对应着处理字节、字、双字、四字。

上图中大多数指令，既可以用于无符号运算，也可以用于补码运算，同时只有右移操作要求区分有符号数和无符号数，这个特性使得不嘛孕栓成为实现有符号整数运算的一种比较好实现的方法原因之一。

leaq指令是用于加载有效地址，通常用来执行简单的算术操作。本质上算是movq指令的一种变形。其指令形式是从内存读取数据到寄存器，但是它更本上就没有引用内存，其操作数看上去是一个内存引用，但其实际上是将有效地址写入到目的操作数。举个例子设%rdx的值是x那么我们执行leaq 7(%rdx,%rdx,x) , %rax指令则是相当于把%rax的值设置为了5x+7。需要注意的是目的操作数必须是一个寄存器。

在利用寄存器进行移位操作时，先给出移位量，然后第二位给出要移位的数，可以执行算术 ( 要补符号位 ) 或者逻辑右移( 高位补 0 ) ，位移量可以是一个立即数，或者存放在单字节寄存器%cl里 ( 仅允许把这个寄存器作为操作数 ) 。因为寄存器%cl是单字节的所以在其值为0xFF时拥有最大的位移量，即256-1，此时对应的指令salb会移 7 位，salw会移 15 位，sall会移 31 位，salq会移 63 位。

左移拥有两个名字sal和shl，两种指令效果是一样的，但是在右移指令的两种形式中却不相同sar是算术右移，会填上符号位，而shr是逻辑右移，是填充 0 。

例：

long shift_left4_rightn(long x, long n){
	x<<=4;
	x>>=n;
	return x;
}
//现有 x in %rdi , n in %rsi , 使用算术右移
//则对应汇编代码为:
/*
shift_left4_rightn:
	movq %rdi, %rax
	shlq $4, %rax
	movl %esi, %ecx
	sarl %cl, %rax
	ret
*/

对于两个 64 位无符号或者有符号的整数相乘是需要 128 位来表示，但是x86-64指令集对128位（ 16字节 ）数的操作提供有限的支持，对此Intel把 16 字节的数称为八字，下图位支持两个 64 位数字的全 128 位乘积以及除法的指令。

上述指令中mulq和imulq都要求一个参数必须在%rax中，而晾衣杆作为指令的源操作数给出，然后将成绩存放在寄存器%rdx (高64位)和%rax (低64位)中，虽然imulq可以用于两个不同的乘法操作，但是汇编器能够通过计算操作数的数目分辨出想用哪条指令。

而对于除法或者取模操作，这些操作是由单操作数除法指令来提供的，类似于单操作数乘法指令。有符号除法指令idaivl将寄存器%rdx (高64位)和%rax (低64位)中的 128 位数作为被除数，而除数作为至零点操作数给出。指令将商存储在寄存器%rax中，将余数存储在寄存器%rdx中。

对于大多数 64 位除法来说，除数也常常是一个 64 位的值。这个值应该存放在%rax中，%rdx的位应该设置位全 0 （无符号运算）或者%rax的符号位（有符号运算）。后面这个操作可以用cqto [Intel 文档中叫做 cqo] 来完成。这条指令不需要操作数，它能隐含读出%rax的符号位，将其复制到%rdx的所有位。

下面举出乘法的相关实现的例子：

可以看到存储乘积需要两个movq指令：一个存储低 8 字节（第 4 行），一个村粗高 8 个字节（第 5 行）。

下面举出除法的相关实现的例子：

条件码

CF：进位标志。最近的操作使最高位产生了进位。可以用来检查无符号操作的溢出。

CF进位标志的作用：
1.当两个数相加时，若最高位向上形成进位，则CF=1；
2.当两个数相减时，若最高位向上形成借位，则CF=1；
3.当两个无符号数相乘时，若乘积的高一半为0，则CF=0；
4.当两个带符号数相乘时，若乘积的高一半是低一半的符号扩展，则CF=0.

ZF：零标志。最近的操作得出的结果为 0 。

SF：符号标志。最近的操作得到的结果为负数。设置为 1 表示最近运算小于 0 为真，设置为 0 表示最近运算小于 0 为假。

OF：溢出标志。最近的操作导致一个补码溢出——正溢出或者负溢出。设置为 0 表示无溢出。

指令TEST S1, S2基于S1 & S2，如用testq %rax, %rax来检查%rax是负数还是正数还是零，或其中一个操作数是一个掩码，用来指示哪些位为应该被测试。

对于逻辑操作，进位标志和溢出标志会被设置成 0 。对于移位操作，进位标志将设置为最后一个被移出的位，而一处标志设置为 0 。INC (加一)和DEC (减一)会设置溢出和零标志，但是不会改变进位标志。同时特殊的CMP 、SUB、AND、TEST指令根据两个操作数的差来设置条件码而不改变其他寄存器。

值得注意的是setl与setb指令表示小于时设置和低于时设置，而并非设置长字和设置字节。

1. 分析setl。当SF^OF为1时（此条指令代表的是a<b，即为1时有a<b），会将D设置为1，否则设置为0。有两种情况SF^OF为1：
   a. SF = 1 OF = 0，此时OF = 0即没有发生溢出，那么结果t就是正常结果。SF = 1即结果t是负数，即a-b<0即a<b。符合情况。
   b. SF = 0 OF = 1，此时OF = 1即发生了溢出，且SF = 0说明结果t为非负数，所以很明显这里是发生的负溢出，所以溢出结果为非负数。a-b>=0这里负溢出，所以两个部分都为负，a为负，-b为负，所以b为正，既然a为负，b为正，那儿必有a<b。符合情况。

2. 分析setle。既然SF^OF = 1代表小于且ZF = 1代表等于，那么(SF^OF) | ZF = 1就代表小于或者等于。

3. 分析setge。既然SF^OF = 1代表小于，那么整体取反后，~(SF^OF) = 1，就代表大于等于。（小于的反面就是大于等于）

4. 分析setg。既然(SF^OF) | ZF = 1就代表小于等于，那么整体取反后，~(SF^OF) & ~ZF = 1（注意取反后或符号变为与符号），就代表大于。

SET指令的目的操作数是低位单字节寄存器元素之一，或是一个字节的内存位置，指令会将这个字节设置成 0 或者 1 。为了得到一个 32 位或者 64 位结果，我们必须对高位清零。

对于无符号数比较来说其进行比较时使用的是惊为标志和零标志的组合。大多情况下机器代码对有符号和无符号的运算中的两种情况都是使用一样的指令，因为许多算术运算对无符号和补码算术都有一样的位级行为，而对于右移、除法、乘法时使用的指令和条件码不相同。

跳转指令

JMP：无条件跳转，跳转目标从寄存器或者内存位置读出。

直接跳转是给出一个标号作为跳转目标的，而间接跳转是*后面跟一个操作数指示符。

jmp *%rax：用寄存器%rax中的中的值作为跳转目标

jmp *(%rax)：以寄存器%rax中的值作为读地址，从内存中读出跳转目标。

在实现跳转时，目的跳转地址可以通过指令的字节码来计算，目的跳转地址是本行对应 16 进制数据加上下一行指令的地址的和得到对应的跳转地址。举个例子：

通过如此计算 ( 相对寻址 ) ，程序计数器的值是跳转指令后面的那条指令的地址，而不是跳转指令本身的地址。

在寻址计算时如果出现了负数时，我们利用补码等于源码取反加一的方式来计算所需要减去的值的大小，以上图为例子 f8 的二进制位是1111 1000我们对其求补码可以得到0000 1000此时值为 8 ，那么下一条指令的地址减去该值便是所跳转到的地址。

举个例子：

有题目可以知道这个是一个小端序的字节顺序，所以在读取数据时是从右往左进行读取，我们可以看到其为一个负数，而求其跳转地址，我们已知跳转地址=操作数+下一条指令的地址，那么求这个跳转的地址我们可以用两种方式来求解。

方式一

我们直接拿4005ed减去0x73可以得到400560，而这个数据也便是我们跳转到的地址。

方式二

我们将ff ff ff 73的二进制位列出来可以看到1111 1111 1111 1111 1111 1111 0111 0011，我们对其取反可以得到1000 1100将其转换为 16 进制数据可以得到0x8C我们再对取反后的数据加一，可以得到其补码，便是0x8D我们此时将下一条指令的地址减去对应的补码便可以得到我们跳转到的地址，即400560

条件分支

在C中我们实现一个if - else的分支结构采用如下方式：

if(test-expr){
	then-statement
}else{
	else-statement
}

但是在汇编语言中其会转变为goto语句来进行分支，来确保不会执行到错误的部分，上述的C代码转换为汇编模式则是（ 我们以C语法描述控制流 ）：

	t=test-expr;
	if(!t)
		goto false;
	then-statement
	goto done;
false:
else-statement
done:

也就是汇编器为then-statement和else-statement产生各自的代码块。它会插入条件和无条件分支，来确保执行正确的命令。

上述实现条件操作是一种传统简单但低效的一种方式，在现代处理器上，常常以条件传送来实现，我们同样举出相应的例子来看：

需要注意的是：使用条件赋值时不会改变lt_cnt或ge_cnt的值，其只是简单地计算函数要返回的值。

---

对于分支预测错误的处罚计算：

假设计算错误的概率是p，如果没有预测错误，执行代码的时间是$T_{ok}$,而预测错误==的处罚是 $T_{MP}$，模式为随机是执行所需要的时间周期为 $T_{ran}$,模式为非常可预测时执行所需要的时间周期为 $T_{OK}$，则有关系式：$T_{MP} = 2\ ( T_{ran} - T_{OK} )$

即函数需要的时间范围大约是：$T_{OK}\ \ —\ \ T_{OK} + T_{MP}$

---

条件传送中，处理器无需预测测试的结果就可以执行条件攒送。处理器只是读源值 (可能是从内存中)，检查条件码，然后要么更新目的寄存器，要么保存不变。

循环分支

do-while

一般来说在汇编中会将循环变成低级的测试和条件跳转的组合，以do-while为例：

可以看出在汇编里采用了条件跳转和低级测试实现的一个do-while循环，最为关键的便是第 7 汇编语句，其决定了是否继续重复和退出循环。

while

while与do-while不同的是while可能一次循环都不会执行，而do-while至少执行一次，对此我们需要先进行测试然后再跳转到对应的循环体里，GCC在生成while循环时常使用两种翻译方式：

• 跳转到中间

  通常的模板形式是

  goto test;
   loop:
  	body-statement
   test:
  	t = test-expr;
     	if(t)
     		goto loop;

可以看到程序先跳转到的是测试循环成立与否的条件判断处，然后判断成立时再次进行跳转。

• 条件分支

  第二种方式是采用判断条件是否成立，如果不成立则直接跳过循环，把代码转换为do-while循环。大致可以表示成如下形式

  t = test-expr;
  if(!t)
  	goto done;
  do 
  	body-statement
  while (test-expr);
  done:

  相应的还可以翻译成goto代码如下：

  t = test-expr;
  if(!t)
  	goto done;
  loop: 
  	body-statement
  	t = test-expr;
    	if(t)
    		goto loop;
  done:

  

for

for循环的行为与while比较相似，for的通用形式如下：

for (init-expr; test-expr; update-expr)
	body-statement

对此转换成while可以如下表示：

init-expr;
while (test-expr){
	body-statement
	update-expr;
}

程序会先对初始表达式进行求值，然后进入循环，进行测试表达式的结果来判断是否执行循环内容。

由于for在编译时与while效果相似，在编译成汇编时，会根据优化程度来采用while的两个方式之一来进行转换。

小总结

C语言中的三种形式的循环都可以采用简单的策略来进行翻译，以条件分支和逻辑判断来实现，产生包含一个或多个条件分支的代码。控制的条件转移提供了将循环翻译成机器代码的基本机制。

switch

switch更具一个整数索引值进行多重分支，同时可以通过跳转表 ( 一个数组 ) 来使其更加高效。[ 一般在开关情况过多时 ( 4 个以上 )，并且值的范围跨度比较小时采用跳转表 ] 。

在上图中我们可以看到在跳过一个不连续的区域时在对应的跳转表里所对应的是default区段，会在对应指向执行def的代码段。

&& 创建一个指向代码位置的指针

同时可以注意到上面代码段有一个对index > 6的判断语句，这个是干什么的呢？我们试想一个补码表示的负数会被映射成一个无符号的最正大数，利用这个减少了分支的可能性。转换为汇编则为如下形式：

上述代码的关键是第 16 行的goto跳转语句，转换为汇编便是第 5 行的jmp语句，采用间接跳转来实现，操作数指定一个内存位置，由寄存器%rsi给出，这个寄存器保存着index的值。在跳转表中重复的便是打上相同标号，而对于确实则是采用def标号跳转到对应的default块进行处理。

而寻找多个标号的下标只需要对照后面的L X进行查找，可看到case 2和case 4、case 0和case 7的情况标号相同。

我们以练习题 3.31的练习题为例，可以根据给出的汇编代码和其相应的跳转表，写出对应的C代码：

对应转换出来的C语言代码为：

void switcher(long a,long b,long c,long* dest){
	long val;
	switch(a){
		case 5:
			c = b ^ 15;
		case 0:
			val = c + 112;
			break;
		case 2:
		case 7:
			val = (b+c)*4;	//	(b+c)<<2
			break;
		default:
			val = b ;
	}
	*dest = val;
}

栈

在x86-64中栈空间向低地址方向增长，同时当x86-64过程需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间，这个部分称为过程的栈帧。

当过程P调用过程Q时，会把返回的地址压入栈中，指明当Q返回时，要从P的程序的哪个位置继续执行。我们把返回地址也当作P的栈帧的一部分，因为其存放的是于P相关的状态。而Q代码部分会扩展当前栈的边界，分配其栈帧所需要的空间大小。

简单来说，当S要调用Q函数时，会先将下一条命令的地址压入栈中，并保存相关寄存器的值，然后将Q函数的栈帧压入

以下图为例，有如下执行顺序：

在上述的调用过程中大部分的数据传送是通过寄存器完成的，当P调用Q时，P的代码必须先把参数复制到适当的寄存器中，同样的当Q返回到P时，P的代码可以从%rax中取得返回值。

在x86-64中可以通过寄存器最多传递 6 个整型( 例如整数和指针)参数。当一个函数有大于 6 个整型参数时，超过的部分便需要通过栈来进行传递。同时通过栈来传递参数时，所有数据都向 8 的倍数对齐，当参数到位的时候程序便可以通过call指令来将控制转移到Q。

存放在局部变量的值不需要进行字节对齐，而当值被当作参数传入到函数中时，便需要进行字节对齐。

可以看到1-6的参数值都是通过寄存器传递而多出来的7-n的参数便是在栈顶以 8 的倍数进行压入。

有些时候局部数据必须放在内存中，包括如下情况：

• 寄存器不足存放所有的本地数据
• 对一个局部变量使用&，因此必须能够为它产生一个地址。
• 某些局部变量是数组或者结构，因此必须能通过数组或结构引用被访问到。

栈指针加上某一个数值代表着栈的缩减，而压入数据的时候栈顶指针进行减数值，栈空间向上移动。

寄存器是唯一被所有过程共享的资源，虽然是在给定时刻只有一个是活动的但是，我们仍然需要确保一个过程调用另一个过程的时候时，被调用者不会覆盖调用者稍后使用的寄存器的值。

寄存器%rbp、%rbx和%r12 - %r15被划分为被调用者保存寄存器，除了栈指针%rsp都分类为调用者保存器。

通过上述例子，可以更好的理解到程序在调用栈的过程中是如何对寄存器的操作的。值得注意的是最后恢复原来的数据的时候是先弹出%rbx再弹出%rbp，体现出栈的先进后出的原则。

下面以习题 3 .34 为例：

一个函数P生成名为a0 ~ a7的局部变量然后调用函数Q

从汇编来看我们可以知道在x86-64中可以通过寄存器最多传递 6 个整型，所以a0到a5共 6 个变量是保存在寄存器中的，而a6和a7存储在栈空间里面，对于程序而言，不能把所有变量均存储在寄存器上是因为寄存器不够用，因而无法存取。

递归调用

汇编使用寄存器%rbx来进行保存参数n，先把已有的值保存在栈上( 第二行 )，随后在返回前恢复该值( 第十一行)。根据栈的使用特性和寄存器保存规则，可以保证当递归调用rfact(n-1)返回时( 第九行 )：

• 该次调用的结果会保存在寄存器%rax中
• 参数n的值仍然在寄存器%rbx中

递归调用对程序的栈空间消耗十分大，如果程序中对递归调用的次数过大时，可能会引发溢出。

数组

通常来说对于一个数组的引用可以通过内存引用的方式来进行简化数组的访问，如果有一个int E[i]，E的地址存放在寄存器%rdx中，而i存放在寄存器%rcx中时，可以利用指令movl (%rdx,%rcx,4),%eax也就是取出%rdx向下4 * %rcx + %rdx的内存位置的值，同理于取出其他数据。而对于引用了指针的数据也是可以进行如上的过程。

需要注意的是，对数组的地址进行访问也要乘以字节数

对于多维的数组时，其值时保存在栈空间内部，我们依然可以把其理解为一个线性的空间，同样的可以通过对其地址空间的偏移来取其值。

通常要访问多维度的元素，编译器会以数组起始为基地址，然后以偏移量为索引，产生期望的元素偏移量，然后使用对应的mov指令。对于如下声明的一个数组：T D[R][C]，其数组元素D[i][j]的内存地址为$$&D[i][j] = x_D+L(C*i+j)$$。

定长数组

C语言编译器能优化定长多维数组上的操作代码。编译器可能会去除整数索引，转换为指针间接引用，于此编译器还可能采用某个指针指向对应数组的固定部分，在后续的运算中在这个指针上进行如下图所示

可以看出来GCC生成了一个指针，命名为Aptr指向A的行i中连续的元素，也生成了一个指针，命名为Bptr指向B的列k中连续的元素，利用指针来对其进行运算，同时省去对变量j的定义过程，利用判别式来判断函数停止的条件。

变长数组

定义变长数组时不得不用malloc或者calloc函数进行分配存储空间，而不得不显示地编码，用行优先索引将多维数组映射到一维数组，但是在ISOC99允许数组的维度是一个表达式，在数组分配的时候才计算出来。我们声明一个数组A[expr1][expr2]，我们访问该元素的A[i][j]可以编写如下的函数：

int var_ele(long n,int A[n][n],long i,long j){
	return A[i][j];
}

则在变长数组中会产生如下汇编代码：

而在GCC的优化下会变成如下：

将优化后的C代码进行转换为汇编时程序会采取上述方式对数组进行取值保存，利用指针的变化改变其取值的偏移量，进而进行优化其结构。

结构体

结构体可以将多个不同数据组合在一起，与多维数组相似，其在栈空间上是线性存储的，于是我们也可以通过其首地址加上对应的偏移量来取到对应的结构体数据。

我们声明一个结构体变量：

struct rec{
	int i;
	int j;
	int a[2];
	int *p;
};

则其对应的空间分配为如下图：

假设r存储在寄存器%rdi时，如果我们需要取出i的值时可以直接用偏移量进行取值：

movl	(%rdi),%eax		;r->i
movl	4(%rdi),%eax	;r->j

而对于存储在结构体中的数组我们可以利用偏移量对其进行取值。

;r in %rdi	i in %rsi
leaq	8(%rdi,%rsi,4),%rax		; Set %rax to &r->a[i] 

如果我们要实现r->p = &r->a[r->i + r->j]时，也可以l向上述过程中一样将r->i和r->j的和相加得到一个偏移量，将结构体的首地址值加上对应的字节长度(r->i + r->j)和数据a的字节长度乘以相应长度值。

;r in %rdi
movl	4(%rdi),%eax	; Get r->j
addl	(%rdi),%eax		; Add r->i
cltq				    ; Extend to 8 bytes
leaq	8(%rdi,%rax,4),%rax		; Compute &r->a[r->i + r->j]
movq	%rax,16(%rdi)	; Store in r->p

下面以一个结构体为例：

联合

union与结构体不同，其在栈上分配的空间是定义变量中最大的一个，当在union中进行嵌套多个结构体时，如果需要对某一个结构体中的变量进行调用时，其余的结构体变量则会不占用对应的空间，而union对应的首地址也变成对应调用结构体的首地址。有如下定义：

union a{
	struct a0{
		int a;
         int b;
	};
	struct a1{
		int c;
		int d;
	};
}

当我们需要对a1中的c调用时，此时共用体a的首地址变成嵌套结构体a1中c的地址，其偏移量为 0 ，调用a1中d的话其对应的偏移量为 4 。

数据对齐

许多计算机系统对基本数据类型的合法地址做出了一些吸纳之，要求某种类型对象的地址必须值K(通常是 2 、4、8 )的倍数。这种方式产生相应的字节对齐必须是K的倍数。在汇编中会出现如下指令：

.align 8

表示后面的数据会遵循 8 字节的对其长度，而对于结构体，也会在其中进行插入间隙来完成对应的字节对齐。整个结构体的对齐值一般是结构体中最大数据类型所占的空间。与此如果一个类型按n字节对齐，那么该类型的变量起始地址必须是n的倍数。

如果一个结构体变量中最后一个数据不满足字节对齐时编译器也会对其进行补齐，而补齐的空间也造成了内存浪费。

指针

指针是C语言中的一个核心特色，以一种统一的方式对不同数据结构中的元素产生引用。

• 每一个指针都对应一个类型，表明指针指向的是哪一类对象
• 每一个指针都有一个值。这个值是某个指定类型的对象地址。特殊的NULL( 0 )表示该指针没有指向任何地方。
• 指针用&运算符创建，leaq指令是设计用来计算内存引用的地址的，&运算符的机器代码实现存储用这个指令来计算表达式的值。
• *操作符用于间接引用指针，结果是一个值，间接引用时用内存引用来实现的，要么存储到一个指定的地址，要么时从指定的地址读取。
• 指针的强制转换只改变类型不改变值，相当于在指向的时候偏移量发生了变换。如表达式(int *)p + 7则会计算为：p + 28
• 指针可以指向函数，来对其进行调用。

GDB

内存越界引用和缓冲区溢出

C对于数组引用不做任何边界检查，而且局部变量和状态信息( 例如保存的寄存器值和返回地址 )都存放在栈中。这两种情况结合到一起就引发严重的程序错误，对越界的数组元素的写操作会破坏存储在栈中的状态信息。当程序使用这个破坏的状态，试图重新加载寄存器或者执行ret时，会发生严重的错误。( PWN 中ret2漏洞 )

缓冲区溢出时如果覆盖了返回地址值，那么程序会跳转到对应的地址值处，而不是返回到原来的地址上去，因此可能执行不愿意执行的函数，而引发错误。

对抗缓冲区溢出

栈随机化(ASLR)

为了在系统中插入攻击代码，攻击者及需要插入代码也需要插入指向这段代码的指针，这个指针也是攻击字符传递一部分。产生这个指针需要知道这个字符串放置的栈地址，而栈随机化在程序开始时，在栈上分配0 ~ n字节之间的随机大小的空间，入使用分配函数alloca在栈上分配指定字节数量的空间，程序并不使用这段空间，但是它会导致程序每次执行的时候栈的地址空间进行了变化，分配的n必须足够打，才能获得足够多的栈地址变化，但也要足够小，避免浪费程序过多的空间。

int main(){
	long local;
	printf("local at %p\n",&local);
	return 0;
}

在上述程序中，仅仅只是输出对应的main的地址，但是每次执行时发现输出并不一样，则证明开启了栈地址随机化。

对于这种防护，攻击者可以在实际攻击的代码前加入很长一段的nop，只要攻击者猜中了这段序列中的某个地址程序就会经过这个序列，到达攻击代码。这个序列常常被称作“空操作雪橇”。

破解的随机化大小 = 枚举的地址长度 * nop sled长度

尝试穷尽起始地址次数 = 地址范围 / nop sled长度

其中需要保证已经在栈上插入了攻击代码，于此再在栈顶上加入对应的随机化长度的 nop

栈破坏检测(Canary)

其思想是在栈帧中任何局部缓冲区于栈状态之间存储一个特殊的Canary值，其大小是程序每次运行时随机产生的，程序会对这个值进行检查，如果被某个操作数或者函数改变时会引发异常导致程序终止。

对于这个的绕过则需要将溢出的数据在Canary处将其还原，然后覆盖到后面的数据。实现溢出。

限制可执行代码区域(NX)

在典型的程序中，只有保存编译器产生的代码的那部分内存才需要是可执行的，其他部分限制为只允许读和写。而NX将读和写的模式进行分开，将栈变为可读可写但是不可执行，减少了损失效率。

浮点代码

每个YMM寄存器都是256位(32字节)。当对标量进行数据操作时，这些寄存器只保存浮点数，而且只使用低 32 位( float )或64位( double )。每个XMM都是对应YMM寄存器的低128位。

对应浮点传送指令为：

对应运算指令：

对应位级运算：

第三章总结

程序的机器级表示

在调用一个函数时，寄存器可能会有重复使用的情况发生，因此需要在调用前对寄存器的值进行保存，这里保存策略分为两大类：调用者保存和被调用者保存：

对应寄存器的保存方式如下：

基本类型与内存访问

C语言中对应的基本类型在汇编中的后缀表示：

一个指令包括操作码和操作数，同时部分操作码可能没有对应的操作数( 如：ret )，同时可能一个操作码对应的是多个操作数。而在操作数中包含着：立即数、寄存器、内存引用 (一个寄存器加上了括号来表示)。

对应的内存引用(一般数组会采用如下方式进行取址) ：

内存访问，CPU支持将复杂的访存结果直接作为操作数，不需要先把地址进行计算出来在到内存进行读取

指令

寄存器与数据传送指令

对于MOV指令有如下使用方式：

特别的当源操作数是一个立即数时，该立即数只能是 32 位补码表示，同时程序会对这个立即数进行符号位扩展到64位( 32 -> 64 )，将得到的 64 位数保存到寄存器。

如果操作的立即数是 64 位呢？程序引入了一个新的指令movabsq，该指令的源操作数可以是任意64位立即数，但是目的操作数只能是寄存器。

movl的目的操作数是寄存器时，会把该寄存器上的高 4 字节设置为 0.

任何位寄存器生成32位值的指令都会把该寄存器的高位部分设置为 0.

当源操作数的数位小于目的操作数的时候，有对应的mov指令对其进行符号位扩展或者零扩展。

零扩展指令：

符号位扩展：

同理于零扩展指令，s表示的是符号位扩展(sign的缩写)，最后面两个都是大小指示符(源操作数 - 目的操作数)。

同时存在一个cltq指令，其源操作数只能是%eax，目的操作数只能是%rax。

栈与数据传送指令

%rdi和%rsi一般用于保存传入的参数的第一位、第二位。

pushq %rax等价于sub $8, %rsp + movq %rax, (%rsp)两条指令的组合
popq %rbx等价于movq (%rsp), %rbx + addq $8, %rsp两条指令的组合，但是对应原来栈上的%rbx的值仍然存在，知道下次push操作，此处保存的数值才会被覆盖。

算术和逻辑运算指令

leaq可以加载一个有效的地址，其中q表示地址的长度，源操作数可以像内存引用一样，通过计算偏移量来进行把对应的有效的地址值保存到目的操作数，需要注意的是，其执行的操作并不是到对应的内存地址处读取数据，而是将这个有效的地址值进行保存到目的操作数。

同时lea指令也可以完成对应的算术运算：

单操作数指令：

移位操作指令：

对于移位量k可以是一个立即数，或者存放在寄存器cl中的数，对于移位指令，只允许以特定的寄存器cl作为操作数

cl的长度为 8 个二进制位，意味着最多可以移位的长度位为 255 ，移位对应的数据时采用cl的不同低位来进行保存。

对于此程序在进行乘法时，为什么不直接使用对应的乘法指令？这是因为在使用lea指令进行运算时所开销的时间周期更短，编译器会将程序进行优化，采用时间周期开销更短的进行编译。

指令与条件码

执行一个指令时会用到相应的算术逻辑单元(ALU)，ALU重寄存器中读取数据后，执行相应的运算，并设置对应的条件码寄存器。

条件码寄存器由CPU进行维护长度为单个比特位，用于描述最近操作的属性。

CF - 进位标志 可以用来进行检测是否发生了正溢出
ZF - 零标志 记录最近的操作结果是否为 0 ，为 0 则将其置为 1
SF - 符号标志 当最近的操作结果小于 0 时，其会置为 1
OF - 溢出标志，针对有符号数，当发生溢出时便会置 1 (发生正/负溢出时)

cmp指令和test指令只是设置条件码寄存器，不更新目的寄存器的值。

一般程序不会直接对条件码寄存器进行访问，但程序可以通过setx来对条件码寄存器进行间接访问，保存对应的值于一个寄存器中，通过对应寄存器的值进行返回或者判断。(Bool类型)

对于大于和等于的情况可以直接通过相应的寄存器进行判断，而小于则需要SF ^ OF来进行判断，如不发生溢出时可以通过对应符号寄存器SF进行判断，但是发生溢出时就需要借助OF溢出标志进行判断。

跳转指令与循环

在程序中，使用较多的条件判断语句会使程序的执行效率不高，因为程序通常会对每个分支用分支预测器进行判断每个分支是否会进行，当发生错误的预测时，会浪费较多的时间。程序因此会将其优化，将循环变成低级的测试和条件跳转的组合。