csapp学习笔记

感觉还是做一下笔记比较好,虽然有点浪费时间,但是可以借此梳理知识,要不然感觉会很快忘掉.

chapter2

操作系统用一个字去编码内存地址,字是一个几个字节组合起来的一个单元。字长:字是由几个字节构成的。X位操作系统的X:每个字的位数。
所以32位操作系统的内存地址范围是0~2^32-1,所以32位操作系统最大支持4GB内存,同理64位: 0~2^64-1,所以最大16EB

大端小端

1
2
3
4
int a = 0xAABBCCDD;
unsigned char *b = (unsigned char*)(&a);
for(int i = 0; i < 4; ++i)
printf("%.2x ",b[i]); //逐字节输出

如果是大端储存,那么a在内存里是AA BB CC DD,输出为aa bb cc dd

如果是小端储存,那么在内存里是DD CC BB AA,输出为dd cc bb aa

Intel机器上一般用小端储存

位移运算

1
2
int a = 1;
printf("%d %d",a<<34,a<<2);

c语言会把位移的位数%一个该变量类型总位数,int类型总位数32,34 % 32 == 2,所以输出两个4

有无符号数的各种操作

补码编码

位数为w的负数的补码可以看作一个-1 * 2^(w - 1) + 正数得到的。具体看图

补码转无符号

很显然当正数时一一对应,负数时映射到无符号数那块更大的的正数区域里

怎么对应呢?见图:

你可以想象把负数区域用剪刀剪下来贴到正数区域的最左边,-4就对应到4,-1对应到7。

而这种操作就相当于每个数+8,因为跨越了原先的负数区域(len = 4)和正数区域(len = 4)对吧.

可以据此推出公式:


可以根据上面那张图自行想象。

无符号转补码

这个就相当于再把那块区域贴回去嘛,这就简单了:

补码位数扩展

正数直接高位全填成0,负数高位全填成1。

假设一个位数=3的数-3,它的表示是:

1
-3(101) = -1*(2^2) + 1*(2^0)

当位数变为5时(11101),它的表示变为:

1
2
3
4
5
    -1*(2^4) + 1*(2^3) + 1*(2^2) + 1*(2^0)
= (-1*(2^4) + 1*(2^3)) + 1*(2^2) + 1*(2^0)
= -1*(2^3) + 1*(2^2) + 1*(2^0)
= -1*(2^2) + 1*(2^0)
= 原式

把情况推广到w位扩展w+n位也是对的。

补码/无符号截断

假设要把一个数截成k位,直接把>k-1位的所有位变成0就行了,原理就类似于如果是负数把它变成该数对应的无符号数然后%2^k再变回补码。

所以很显然截取w位等价于 % 2^w

无符号加法

显然对于两个w位的正数x< 2^w, y < 2 ^ w, x + y = (x + y) % (2^w)

检测溢出:若s = x + y,s < x or s < y,则溢出.

显然若s >= x且溢出,则y = k * 2^w,但 y < 2^w,所以得证

模数加法

取模加法也有逆元运算。对于逆元:假设(a + b) % p = c, c + (b的逆元) = a

很显然任意数k的逆元 = p - k,你可以想象一个0~p-1的一个环,a+b相当于从a顺时针走一个劣弧b到点c,c到a就相当于再走一个优弧p - b。

这个东西叫阿尔贝群。

补码加法

对于补码来说,你可以把-2^(w - 1) ~ 2^(w - 1) - 1的直线首尾相接变成一个环,如图

这样一看无论是正溢出还是负溢出都一目了然了。比如-2-3 = -5,肯定是溢出了。这里可以看成-2逆时针走三个格子,就到了3。

实际上无论相同位数的无符号数/补码在机器眼中都是一样的,只是表示方式不同,所以说补码加法实际上也是 (x + y) % (2^w) ,当然当你运算负数取模时在这里(注:只是在这里)可能要把 x + y 先加一个 2^w变成相应的无符号数在%运算,但是计算机中直接截取前w位就好了。

如果还是不懂可以去看原书的公式和证明。

溢出判断:若 x > 0 && y > 0 && x + y < 0 || x < 0 && y <0 && x + y > 0则溢出。

习题2.31

1
2
3
4
int tadd_ok(int x,int y) {
int sum = x + y;
return (sum - x == y) && (sum - y == x);
}

以上函数用于判断x+y是否溢出,当然这样做很显然是错的。

以为根据取模加法逆元的那个性质,sum - x == (sum + (2^w - x)) % 2^w ,所以说这样做只是加了一个x的模数加法逆元,所以无论溢出与否都肯定等于y,实在不理解可以画一个取模环自己走走看。

习题2.32

1
2
3
int tsub_ok(int x,int y) {
return tadd_ok(x,-y);
}

要检测x - y是否溢出所以这样写,但是什么情况下这样会出错呢?

很显然当y = -(2^32)时,-y因为int范围的缘故无法变成2^32,试了试这样的话-y依然等于-(2^32),所以应该加一个特判。

chapter 3

ex 3.2

l w b b q l

很显然,在x86-64平台上,任意指针大小都是8 bytes(这也是为什么描述内存地址的寄存器大小都是8 bytes的)。所以指针类型只是告诉编译器该指针所指向的内存区域的大小,以至于生成相应的mov*汇编

ex 3.3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
movsbl (%rdi),%eax
movl %eax,(%rsi)

movsbl (%rdi),%eax
movl %eax,(%rsi)

movsbq ($rdi),%eax
movq %eax,(%rsi)

movb (%rdi),%ax
movb %ax,(%rsi)

movb (%rdi),%ax
movb %ax,(%rsi)

当既改变符号又改变大小时,先改变大小再改变符号。所以只看源类型是否是有无符号,在根据这个判断是否符号扩展

如果是截取,就直接截就行。

leaq

leaq指令看似是输出一个内存引用的地址,但是因为不会读取实际的内存,所以可以用其加上内存地址计算的一些用法直接进行一些算术运算:

1
leaq 6(%rdi,%rdi,4), %rax // %rax = %rdi * 5 + 6

注意算术运算类似于复合运算(+=,-=),比如subq %rax %rdi%rdi = %rdi - %rax,别弄反了。