csapp

信息的表示和处理

整数的运算满足乘法结合律和交换律，溢出的结果是一致的

而浮点运算不满足结合律

(3.14+1e20)-1e20=0.0

3.14+(1e20-1e20)=3.14

虚拟地址空间 字节数组

十进制下x=2^n n=i+4j i∈[0,3]

该数的十六进制表示为1(i=0) 2(i=1) 4(i=2) 8(i=3)后j个0

2048=0x800

字长w 虚拟地址的范围是0-2

数据通路的宽度（CPU内部总线的宽度，运算器的位数，通用寄存器的宽度都应该等于）

字没有什么意义好像 可能是16位

大端法 最高有效字节在最前面 （正常书写数字规则）

小端法 最低有效字节在最前面

较新的微处理器采用双端法两种都能处理

异或应用

从异或的真值表可以看出，不管是0还是1，和0做异或保持原值不变，和1做异或得到原值的相反值。可以利用这个特性配合掩码实现某些位的翻转

如果a 1 ^a 2 ^a 3 ^…^a n 的结果是1，则表示a 1 、a 2 、a 3 …a n 之中1的个数为奇数个，否则为偶数个。可用于奇偶校验

由于x^x=0 x^x^y=y 可用于交换变量

//不适用于a=b
*a = *a ^ *b;
*b = *b ^ *a;
*a = *a ^ *b;

指向原始笔记的链接

练习题2.13

bis(x,m)=x|m bic(x,m)=x&!m

移位运算

左移在后面补0 位移量应该是0~w-1 移位运算是可左结合

逻辑右移 高位补0

算术右移 在左边补k个最高有效位的值

所有编译器几乎都对有符号数进行算术右移，而无符号数必须是逻辑的

移动k位 当k超过w时 移位k mod w

加减法运算优先级高于移位运算

补码编码

由位级表示计算真值

$$B2T_w(\vec{x})\dot{=}-x_{w-1}{2}^{w-1}+\sum _{i=0}^{w-2}{x}_i{2}^i$$

n位补码机器数与真值关系

$$[X{]}_{补}=2^n+X(-2^n\le X<2^n,\text{mod}{2}^n)$$

其中[X]补是机器数，X是真值

对于定点小数，模为2

补码转无符号

$$T2U_w(x)=\begin{array}{r}\{\begin{array}{cc}x+2^w& x<0\\ x& x>=0\end{array}\end{array}$$

无符号转补码

TMaxw为w位下最大有符号补码数

$$U_{w}2T(u)=\begin{array}{r}\{\begin{array}{cc}u& u<=TMa{x}_w\\ u-2^w& u>TMa{x}_w\end{array}\end{array}$$

C语言中默认为有符号，为了创建无符号常量需要加上后缀字符U或u

在运算中同时含有有符号和无符号时，会转为无符号的

与负号没啥关系

位表示扩展

补码在高位填充最高有效位

short转为unsigned时等价于(unsinged)(int)short

数值截断

好像就是直接截断

$$B2U_k(\vec{x})=B2U_w(\vec{x})mod{2}^k$$ $$B2T_k(\vec{x})=U2T_k(B2U_w(\vec{x})mod{2}^k)$$

整数运算

2个w位的数之和最大需要w+1位来表示，被称为字节膨胀(lisp支持)

无符号加法

结果被直接截断

检测溢出的方法：比结果是否大于加数

$$x{+}_w^{u}y=\begin{array}{r}\{\begin{array}{ccc}x+y& x+y<2^w& 正常\\ x+y-2^w& 2^w<=x+y<2^{w+1}& 溢出\end{array}\end{array}$$

无符号数的加法逆元

在无符号加法中，0是单位元，每个元素都有加法逆元

$${-}_w^{u}x=\begin{array}{r}\{\begin{array}{cc}x& x=0\\ 2^w-x& x>0\end{array}\end{array}$$

补码加法

$$x{+}_w^{t}y=\begin{array}{r}\{\begin{array}{ccc}x+y-2^w& 2^{w-1}<=x+y& 正溢出\\ x+y& -2^{w-1}<=x+y<2^{w-1}& 正常\\ x+y+2^w& x+y<-2^{w-1}& 负溢出\end{array}\end{array}$$

补码的加法逆元

除了TMinw的逆元为自身，其余数x的逆元都为-x

乘法

无符号与有符号的乘法的结果的位级表示相同，但只看结果（n位乘n位应是2n位 被截断到n位）不能判断是否发生溢出

计算补码的非

取反+1

0xf的补（反）是0x0 如0xa的补（反）是0x5 故0xfffffffa是6的补码非 即-6的补码表示

形如Xw-1,Xw-2,…Xk+1,Xk=1,0,0,0…的数，其补码非为Xw-1到Xk+1取反，后面的10…0不变，如1100（-4）和0100（4），0101（5）和1011（-5）

舍入

向偶数舍入：如果在某两个数中间，则舍入到偶数(0)，否则根据大小向上或向下

条件分支

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

并不一定等价

v = test-statement ? then-expr : else-expr
//equal to
v = then-expr;
ve = else-expr;
t = test-expr;
if(!t) v = ve;

do
	body-statement
	while (test-expr);
//equal to
loop:
	body-statement
	t = test-expr;
	if(t)
		goto loop;

while (test-expr)
	body-statement
//ver 1 jump to middle
	goto test;
loop:
	body-statement
test:
	t = test-expr;
	if (t)
		goto loop;
//ver 2 guarded do
	t = test-expr;
	if(!t)
		goto done;
loop://do-while
	body-statement
	t = test-expr;
	if (t)
		goto loop;
done:

for (init-expr; test-expr; update-expr)
	body-statement
//ver 1
	init-expr;
	goto test;
loop:
	body-statement
	update-expr;
test:
	t = test-expr;
	if (t)
		goto loop;
//ver 2
	init-expr;
	t = test-expr;
	if(!t)
		goto done;
loop://do-while
	body-statement
	update-expr;
	t = test-expr;
	if (t)
		goto loop;
done:
 

过程调用

传递控制 调用时设置PC为被调用函数的起始地址，返回时设置为调用函数的地址

传递数据

分配和释放内存

运行时栈

局部数据存放在内存中的情况

1.最多在寄存器上传递6个整数值，超过的就放在栈帧中

2.局部变量为数组或结构

3.对局部变量使用了地址运算符，因此必须要能寻址他

寄存器使用惯例

被调用者保存寄存器(%rbx %rbp %r12-15)，被调用函数要保证寄存器的值在返回时与他被调用时保持一致

调用者保存寄存器(除栈指针)

数据对齐

保证某种类型的数据的地址必须是K的倍数

K	类型
1	char
2	short
4	int,float
8	long,double,char*

指针强制类型转换的效果是改变指针运算的伸缩

char *p的值为q

(int *)p+7 = q+28 (int *)(p+7) = q+7

对抗缓冲区溢出攻击

栈随机化

攻击者插入攻击代码需要知道插入代码存放的栈地址

使得程序运行的栈位置变化 在每次程序运行前在栈上随机分配空间。

nop sled 在攻击代码前插入很长一段nop，只要猜中序列中的某个地址就能到达攻击代码

栈破坏检测

在栈帧中存储canary值，返回时检测是否发生改变