精华内容
参与话题
问答
  • 经典的课本的答案(csapp 中文译名:深入理解计算机系统
  • 深入理解计算机系统CSAPP)第三版,适用于kindle,经典好书!
  • 深入理解计算机系统,带完整标签,源文件500M,超高清,优化体积后清晰的几乎无影响,文件只有45M了,自用电子版,保证质量。
  • CSAPP深入理解计算机系统笔记

    千次阅读 2019-04-26 22:19:25
    csapp的学习从2019.3.18开始。从05.10-08.01这几个月一直工作,重心转去学了点软件工程和面向对象的东西,中断了这部分的学习。从08.01重新继续这部分的学习,但平时工作忙,只能挤出很少的时间。 前言: 如果是第...

    csapp的学习从2019.3.18开始。从05.10-08.01这几个月一直工作,重心转去学了点软件工程和面向对象的东西,中断了这部分的学习。从08.01重新继续这部分的学习,但平时工作忙,只能挤出很少的时间。


    前言:

    如果是第一次看csapp这本书,建议先不要看,直接去看上交软院的课程主页,按照上面的课件学习。推荐一个个人博客“不周山之读薄CSAPP”,也可以按这个博客学习。

    这本书的必读章节:1,2,3,5,7;选读章节:8,9;有更好替代的章节:4,6,第三部分(10,11,12)

    第4,5,6章会感到稍许吃力,因为涉及很多硬件东西可能缺少铺垫,读的时候也可以先跳过。2-3章对应“汇编语言”;4-6章对应“计算机系统要素”;7-8章对应“程序员的自我修养”;9-12章对应“现代操作系统”

     

                                             目录

    1. A tour of computer systems
    2. Representing and manipulating information
    3. Machine-level representation of programs
    4. Processor architecture
    5. Optimizing program performance
    6. The memory hierarchy
    7.  Linking
    8. Exceptional control flow
    9. Virtual memory
    10. System-level I/O
    11. Network programming
    12. Concurrent programming

    第二章:信息的表示和处理

    2.1 信息的存储

    2.2 整数的表示

    2.3 整数算法

    2.4 浮点数

    2.5 总结

    三种最常用的表示数字的方法:1)unsigned无符号整型, 2)two‘s-complement补码, 3)浮点型:2为基的科学记数法,用以表示实数

    特点:整型表达可编码的数字范围较小但更精确,浮点型能编码的数字范围更大但只是近似表示。

    了解数字在计算机中被表达(编码)的原理对于写出适用于全数域和移植性好的代码至关重要。

    2.1 信息的存储

    最小可寻址单元是字节byte,每个字节对应一个地址address。

    hexadecimal notation:

    2进制转16进制:快速写出2^11对应的十六进制数:2^11==(2^4)^2  *  2^3=0x800

    words:

    一个地址是用一个“字”来编码,每个机器上对应的字长也就是该机器的integer的长度,也与该机器上虚地址空间最大位置对应。例如,若字长为w位,则对应寻址空间为2^w字节。通常一个字要么是4字节(32位机),要么是8字节(64位机)

    如今大多数机器的字长都是64位的。

    data sizes:

    数据类型char代表了一个单个字节,虽然从字面上看char类型应该是用于存储一个英文字母的,但它实际上也可用于存放整型数值。

    在C语言中为不同数据类型分配的字节数通常如下表,当然也可能随机器和编译器改变而有所不同:

    C declaration 32-bit 64-bit
    char 1 1
    short int 2 2
    int 4 4
    long int 4 8
    long long int 8 8
    char* 4 8
    float 4 4
    double 8 8

    牢记下述准则:
    * ANSI C标准规定,一个char的长度一定是8位。
    *尽管没有规定int类型的长度是32位,但在Linux当前所有支持的体系结构中,它都是32位的。short类型也类似,虽然没有明文规定,但我们知道的都是16位的。
    *决不应该假定指针和long的长度,它们原则上可以在32位和64位中变化。
    *由于不同的体系结构long的长度不同,决不应该假设sizeof( int ) == sizeof( long )。
    *类似地,也不要假设指针和int长度相等。
    评注:C语言标准为各数据类型的具体字节数设置了下限但没有上限。在80年代32位机大行其道的时候,按当时的标准通常认为一个int类型的对象也可以用来保存指针。但时至今日多数机器已经是64位,所以以前的代码如果直接移植到现在的机器上来可能会产生问题。作为程序员,为了写出可移植性高的代码,必须尽量降低程序对数据类型真实长度的敏感性。

    addressing and bytes ordering:

    当一个保存在内存中的数据对象跨过了几个字节时,其占据的最低地址被认为是该对象的起始地址。比如,int x长度为4字节,在内存中占据的地址总共有四个:0x100,0x101,0x102,0x103,其地址就是0x100。在保存它的值时我们总是一个字节一个字节地存。假设我们想要保存的这个整型的值为x==0x01234567,分为01,23,45,67这四个字节来存,那么它保存在内存中的顺序有两种:

    1)第一种big-endian,大端(尾)序。所谓大尾,也就是说字串的末尾放在大地址一侧(低位字节存放在高地址):

    ... 0x100 0x101 0x102 0x103 ...
    big endian 01 23 45 67 大端序

    2)第二种是little-endian,小端(尾)序。所谓小尾,也就是说把字串的尾巴放在小地址一侧(低位字节放在低地址)。注意,在保存每一个字节时该字节内部的位序总是顺序存储的:

    ... 0x100 0x101 0x102 0x103 ...
    little endian 67 45 23 01 小端序

    注:如何记忆?从英文名称上顾名思义即可:big-endian,也就是说末尾放在大地址一侧;little-endian类比。也可以这样记忆:大端序是按照数字的书写顺序进行存储的,而小端序是颠倒书写顺序进行存储的。

    一般来说如何处理这些存放方式是交给机器自己处理的,但有些时候程序员不得不亲自上手处理:

    1)当需要在一个big-endian和一个little-endian机器之间传输数据时,必须协商和转换好数据信息,这需要程序员自己注意;

    2)在进行机器级别的编程时,小端序机器产生的机器码中数据字节是与我们的阅读习惯反着的。

    3)当使用强制类型转换来访问和打印不同类型对象在内存中的字节表示时。强制类型转换在系统级编程中很常用,比如如下代码:

    void show_int(int x){
       show_bytes((unsigned char*)&x, sizeof(int));
    }
    
    void show_bytes(unsigned char* start, int len){
       for(int i=0; i<len; i++)
          printf("%.2x", start[i]); 
          //在这里使用数组表示法来引用指针,表示我们想要读取
          //以start指向的位置为起始的第i个位置处的字节
    }

    为了输出int x在内存中的字节表示,必须将指向int的指针强制转换为unsigned char*指针,这样就可以一次打印一个字节了。这种强制类型转换告诉编译器,程序应该把这个指针看成指向一个字节序列,而不是指向一个原始数据类型的对象。从输出结果我们可以看到该字节序列在内存中是按little endian还是big endian存放的。

    另外有时候我们会直接以二进制文件来保存数据,读写二进制文件时就需要按字节操作并分清楚其采用的保存顺序,从而进行正确的解析。关于这一点可参考我另一篇文章中的介绍:https://mp.csdn.net/postedit/88124002

    representing strings:

    字串是以null(值为零)字符结尾的字符数组。英文字符可使用ASCII字符码进行编码;而更一般的语言文本可使用Unicode的统一字符集进行编码(每个字符使用4字节编码)。简化版的替代编码例如UTF-8,使用单字节编码一个字符(与ASCII一样)。

    representing code:

    即便是同样的机器,由于安装不同操作系统,导致同一段源代码编译后得到的机器码也是不同的。

    introduction to boolean algebra:

    布尔运算~:逻辑运算非NOT

    布尔运算&:逻辑运算与AND

    布尔运算|:逻辑运算或OR

    布尔运算^:逻辑运算异或(两者一真一假时为真)

    bit-level operations in C:

    C的一个特点就是支持按位进行布尔运算,这些运算可以对任何“整型的”数据类型,如type char或int生效。

    异或运算的结果体现的是两个操作数之间的不同(只有两个数在某位上不同时,对应结果位才为1;只要相同那么结果位就是0),记住以下三条关于异或的规则:

    1) 0与任何数进行异或,不改变该数的值

    2) 一个整数自己跟自己异或,结果为0   

    3) 异或满足结合律和交换律

    一个应用:怎样不使用额外的内存空间交换两个整型变量的值?

    void inplace_swap(int* x, int* y)
    {
       *y = *x ^ *y;
       *x = *x ^ *y;
       *y = *x ^ *y;
    }

    其实现过程是这样的:

             Step         *x        *y
           initially          a         b
           step1          a        a^b
           step2         a^(a^b) = b        a^b
           step3         b       b^(a^b)=a

    这种交换过程是利用了异或运算体现了两个操作数之间的差异这一性质。当然,也有别的方法来实现原地交换,比如使用加法操作。先将a加上b,再利用这个新的a减去b就得到b,从而实现将b换成了a。

    logical operations in C:

    逻辑或,与,非操作:||,&&,!。任何非零的值在逻辑上都被看作TRUE,只有值为零时被看作FALSE。

    shift operations in C:

    shift操作从左边结合。例如,x<<i<<j满足左结合律,即等价于(x<<i)<<j。

    加法运算的优先级高于shift操作。

    左移时右边补零。

    右移分为两种情况——逻辑右移:即右移时左边补零;算数右移:即右移时左边补最高位的值。例如,1001 0101算数右移4位得到:1111 1001。对于无符号数,必须使用逻辑右移;对于有符号数,原则上两种右移都可以采用,但实际中几乎所有编译器都使用算数右移。

    2.2 整数的表示

    整数的编码方法总体分为两种:一种只能表示非负整数;一种则能表示负数,零和正数。

    integral data type:

    在32位机上常见的C整形数据的数值表示范围如下表:

    C数据类型 最小值 最大值
    char(只有一个字节共8bits) -128 127
    unsigned char 0 255
    short [int] -32768 32767
    unsigned short [int] 0 65535
    int -2147483648(-2^31) 2147483647(2^31-1)
    unsigned [int] 0 4294967295
    long [int] -2147483648 2147483647
    unsigned long [int] 0 4294967295

    long long [int]

    -9223372036854775808(-2^63) 9223372036854775807(2^63-1)
    unsigned long long [int] 0 18446744073709551615

    在64位机上,唯一的改变是long的范围变成了跟32位机上long long的范围一样,64位机上用8字节表示long,而32位机上用4字节。

    64位机上的long long跟32位机维持一样。

    注意:

    C标准中只规定了数据类型最小的size,而不是规定精确的size,因而不同机器上使用long所表示的具体数值范围可能是不一样的,这一点要特别注意。为解决这一问题,在ISO C99中在文件stdint.h中引入了一种新的整数类:intN_t和uintN_t,用于显式地指定N位有符号和无符号整数。同时还定义了一些宏:INTN_MIN, INTN_MAX和UINTN_MAX表示N位数的最大最小值。

    如果对int型能表示的整数范围不太有把握,只需记住:绝对值在10^9范围内的整数都可以定义为int型。如果超过了2*10^9,就最好采用long long来表示。

    unsigned encodings:

    无符号整形编码时,w位二进制数能表示的最大值为[1,1,...,1],即UMax = 2^w-1,最小值为0。

    two‘s-complement encodings:

    最常用的负整数编码方式是使用补码:二进制数的最高位采用负权重:如1011 = -1*2^3+1*2^1+1*2^0 = -8+2+1 = -5。在这种编码方式下,最小的数形为:[1,0,...,0];最大的数形为:[0,1,...,1]。即最小值为:TMin = -2^(w-1),最大值为:TMax = 2^(w-1)-1。

    在补码编码下,负整数-1的形式就是:[1,1,...,1],这恰好是unsigned形式能表达的最大值。

    关于补码原理的说明:

    https://blog.csdn.net/qq_41230365/article/details/88763908

    conversions between signed and unsigned:

    UMax = 2TMax + 1:[0,1,...,1](TMax)->[1,1,...,1](UMax).

    casting(强制类型转换):数据的二进制表示都是相同的,只是解释这些bits的方式被改变了。

    总结起来:当x的值处在范围:0<=x<=2^(w-1)时,其无符号和补码表示都是相同的;当超过这个范围,两种表示间相差2^w。

    例子:

    int i = -1;
    unsigned int j = static_cast<unsigned int>(i);
    cout << j <<endl;    //输出结果是2^32-1 == 4294967295

    上面这种用法:unsigned int invalid_unsigned_int = static_cast<unsigned int>(-1);常用来表示能被写成unsigned整型的最大数字,在实际代码中时有见到。

    signed vs. unsigned in C:

    使用printf打印变量时,不考虑变量本身被声明的类型,而只看采用的是%d(有符号十进制), %u(无符号十进制)还是%x(十六进制)。例如:

    int x = -1;
    printf("x = %u = %d\n",x,x);

    输出结果为:x = 4294967295 = -1.

    当有符号数和无符号数之间产生运算时,C会隐式地把有符号数转换为无符号数。例如下面这个比较运算:

    -1 < 0U,由于这里的0是无符号数,因此在比较时会先把-1转为unsigned,导致无符号的-1大于0.

    又比如:

    unsigned i;
    for(i = cnt-2; i >= 0; i--)
       a[i] += a[i+1];

    对于上面这个程序,将导致永远的循环。

    更不容易debug的程序如:

    #define DELTA sizeof(int)
    
    for(int i=CNT; i-DELTA>=0; i-=DELTA)
       ...

    在这里sizeof()函数返回的是一个unsigned的类型!!那么i-DELTA的结果也是一个unsigned,从而永远大于等于零!

    正确使用unsigned作loop index的方法是:

    unsigned i;
    for(i = cnt-2; i < cnt; i--) //不要将unsigned与0比较,而是与其最大值比较
       a[i] += a[i+1] 

    因为在C标准严格规定unsigned加法会类似modular算法一样,也就是0减去1得到的是UMAX。

    更好的做法是:

    size_t i;
    for(i = cnt-2; i < cnt; i --)
       ...

    这里size_t定义了长度等于word size的一个unsigned值。即使cnt==UMAX,代码也能运行。

    expanding the bit representation of a number:

    把无符号数扩展为一个更大的数字类型时,只需要加0即可(zero extension);

    把有符号数扩展为更大的数字类型时,需要采用sign extension,即把最高位(符号位)进行扩展。比如-8 = 1000 = 11000(-2^4 + 2^3 = -2^3*(2-1))。解释:对一个有符号w位的二进制数,添加一个最高位1代表增加-2^w,由于增加了新最高位,原先的最高位就变为了正值2^(w-1),因而新的值为-2^w+2^(w-1) = -2^(w-1),与原先的值是一样的。

    注意:从short变为unsigned int的(C标准要求)步骤:先把short扩展为int,再把int变为unsigned int;而不是先unsigned short,再unsigned int。

    truncating numbers:

    把w位数字截取为k位时,直接丢掉高w-k位。

    对于无符号数x,截取为k位等价于取模(余):x mod 2^k,直接理解就是把高于2^k权重的位全扔掉,只保留小于2^k权重的余数。

    对于补码形式的x,先当作无符号数那样取模x mod 2^k,再将结果转为有符号数。比如:

    -6 = 1 1010-->1010,截取为4位,仍为-6。-6 mod 2^4 = (26u mod 16) = 10u = -6。

    如果在截取时符号位的值发生了改变,即符号发生了改变,则值可能变化。例如:

    10 = 0 1010-->1010,变为了-6。10 mod 16 = (10u mod 16) = 10u = -6。

     

    2.3 整型算法

    unsigned addition:

    由于机器能保存的字长是有限的,故计算和的时候可能会发生溢出。这导致的效果跟数学上的模运算效果是一样的。也就是说,我们可以使用模运算来描述计算机上进行无符号运算的特性。例如下面的代码,233+213的和是446,但由于8位长度模为256,溢出舍去最高位后实际的运算结果是190,这与446 mod 256=190是一致的。

    unsigned char  1110 1001    E9    233
                 + 1101 0101  + D5  + 213
                 -----------  ----  -----
                 1 1011 1110  1 BE    446
                 -----------  ----  -----
                   1011 1110    BE    190

    two's-complement addition:

    补码的加法在bit-level上的操作与无符号加法是一样的,不产生溢出时其结果可以理解,只不过在产生溢出时其结果较难理解。以4bits为例,其补码能表示的范围是[-8, 7]。当求和结果超过范围时,分为两种溢出情况:

    若sum >= 2^(w-1)(正溢出):值变成负值。例如:

    0101(5)+0101(5)=01010(10),舍最高位,得到1010(-6)。

    若sum < -2^(w-1)(负溢出) :值变为正值。例如:

    1000(-8)+1011(-5) = 10011(-13),舍最高位,得到0011(3)

    two's-complement negation:

    ...

    unsigned multiplication:

    两个w-bit的数相乘,乘积最大字长为2w bits。故而做乘法时可能需要扩展字长,当然这是交给软件来做。默认处理方法仍然是截断,其效果就是module运算。

    two's-complement multiplication:

    两个w-bit的数相乘,最小值(负)可达:2w-1 bits;最大值(正)可达:2w bits

    multiplying by constants:

    如果是乘以2^k,直接左移k位即可。可利用这种移位来构造对任意数的乘法:

    (u<<5)-(u<<3)== u*24

    大多数机器执行移位比执行乘法快,编译器自动产生上述的代码。

    从理论上讲,二进制乘法运算过程如下:

               1010
               1110    拆为1*2^3 + 1*2^2 + 1*2^1 + 0*2^0
           --------
               0000    先乘以0*2^0
              1010     再乘以1*2^1,即左移一位
             1010      ...
            1010
           --------
           10001100    各项累加起来

    dividing by powers of two:

    unsigned:如果是除以2^k,直接右移k位即可(逻辑右移补最高位)。

    two‘s complement:

    y      -951 1111_1100 0100_1001
    y>>4   -60  1111_1111 1100_0100  真实结果应该是-59.4375

    当无法整除时要舍入,区别在于:补码计算舍入时是往负无穷方向取约数(round),而无符号数是往0取约数。

    乘以一个非2^k的数可以转变为2^m-2^n这种形式,但在除法中没有这种类似的处理方法。

    negation:complement & increment:

    将补码按位取反(包括符号位也取反)再加一得到的是原数的相反数,因为:~x + x==11...11==-1,所以~x + 1 == -x

    这里有个特例是对Tmin(1000)求相反数:按位取反为0111,加1得到1000。也就是说Tmin的相反数还是Tmin!

    final thoughts on integer arithmetic:

    ...

    2.4 浮点数

    fractional binary numbers:

    首先我们类比常用的十进制小数的表达方式,看一下如果类比地用在二进制数上,得到的表达式如何理解。

    1011.101代表什么意义?

    小数点右边依次代表2^(-1),2^(-2)...代表分数。

    值                表达式
    5 3/4 = 23/4      101.11     = 4+1+1/2+1/4
    2 7/8 = 23/8       10.111    = 2+1/2+1/4+1/8
    1 7/16= 23/16       1.0111   = 1+1/4+1/8+1/16     

    从上面可以看到:

    * 小数点的位置是不变的,我们把二进制表达式右移意味着除以二

    * 0.11111...这个数的值无限接近1.0但比1.0小

    * 能精确表达的只是x/2^k这种形式的值,其他有理数会出现无穷循环,如1/3=0.0101010101...

    注意,由于计算机只能精确地表示x/2^k这样形式的数,所以很多小数都只能近似表示。事实上,对于所有的最后一位以5结尾的十进制有限小数,都可以化成二进制的有限小数(虽然这个小数可能长到没谱),而不是以5结尾的小数就不可能精确地表示为二进制浮点数。所以,由于浮点数的非精确存储,在程序中两个浮点数往往不能直接比较相等,而只能使用“if(fabs(x-y) < epsilon )”这种方法。在这个链接中有相关说明。

    ieee floating-point representation:

    如果采用上一节介绍的方法(即定点表示法positional notation,与浮点相对),本质上是使用小数点位置来表征每个数位的权重。这种方法的缺点是不够高效,随着数位增多,每两位之间的所表示的权值差越来越小,因此为了表达一个很接近于0的小数,需要用相当长的数位(这其实就是y=2^x这个函数在趋近于x轴时的特性)。为了解决在有限位数里,能表示的小数太少 这一问题,我们采用下面介绍的二进制编码方法,即直接给出科学记数法 x * 2^y 中x和y的值。

    关于为什么浮点数编码方式来编码小数,在这个链接中作了更详细的解释:https://www.jianshu.com/p/a755e01e6eb4

    在制定浮点数标准时,numerical analyst主导而非硬件设计师主导,这在标准制定的历史上是很罕见的。这些标准很好地支持了rounding,overflow,underflow,但在硬件上很难再提升速度。

    在ieee标准中,规定浮点数以科学记数法形式表示:(-1)^{s}M2^{E}。例如:15213_{10}= (-1)^{0} * 1.1101101101101_{2} * 2^{13} 。其中:

    * 符号位s:决定其正负;

    * 有效数字M:通常是位于[1.0,2.0)的一个分数。实际上,这部分的编码方式就是上面介绍过的定点小数表示法,只不过在这里只将其用于编码有效数部分;

    * 指数E:将值乘以2的幂次

    编码如下:

                                             高位                                                                                                 低位

    s exp frac        

    其中s是符号位;exp编码了E(但不等于E);frac编码了M(但不等于M)

    precision options:

    一般来说可按下面所述规定exp和frac占的位数,但关于这点没有严格规定。exp影响能表达的数字的范围;frac影响能表达的精度。

    单精度:32bits。有效数字大概为7位十进制,能表示的大小大概为10(+-38)量级。

    尾数用23位存储,加上小数点前有一位隐藏的1(IEEE754规约数表示法),2^(23+1) = 16777216。因为 10^7 < 16777216 < 10^8,所以说单精度浮点数的有效位数是7位。

    指数部分用了8位,能表示的指数大小大概为-126~127,2^127 约等于10^(+-38)。可见这个量级比同样位数能表示的整数的量级都大得多。但浮点表示法的有效数位很小,所以如果还用这种方法来编码int,就无法精确编码有效数字很长的整数。int采用的补码,表达出的整数数值是完全精确的。

    s:1 exp:8-bits frac       :23-bits 

    双精度:64bits。有效数字大概为16位十进制,能表示的大小大概为10^(+-308)量级。

    s:1 exp:11-bits frac       :52-bits 

    注:

    在使用浮点数时,我们更关注的是其有效精度范围,而非其数值大小范围

    float小数点前后加起来有效数字只有6~7位(按十进制);double小数前后加起来的有效数字只有15~16位。所以一条使用准则是,在需要浮点数的时候,不要使用float,而是尽量都采用double来存储。可以看看这里的代码示例:https://blog.csdn.net/cbnotes/article/details/38920511


    在具体解释编码的含义时,根据exp的值,又可以以三种不同的方式进行翻译:

    case 1: normalized values(有效数位的编码暗含一个1)

    s ≠0 & ≠255                                  23-bits                        

    当exp既不是0,也不是11...11时判定该数字是按normalized方式编码的。

    x = (-1)^{s}M2^{E}

    * 指数域的编码被解释为一个经过偏置的有符号整数:    E = exp - bias

    其中bias = 2^(k-1)-1,可将exp编码值[1,254]映射到E=[-126,127]区间。

    * 有效数字编码被解释的方式是: M = 1.xxxx

    其中xxxx就是frac区的编码,也就是说编码本身没有包含1,这个1是暗含的。frac最小为000...0,对应M=1.0;frac最大为111...1,对应M≈2。这样编码是为了节省一位,使得能多一位精度。

    例子:

    15213d = 11101101101101                
           = 1.1101101101101 * 2^13
    significand
      M    = 1.1101101101101 
      frac =   1101101101101 0000000000
    exponent
      E    = 13
      bias = 127
      exp  = 140 = 10001100
    最终编码:0 10001100 11011011011010000000000
            s   exp           frac

    case 2: denormalized values

    s 0000 0000                                  23-bits                           

    在这种情况下,指数域编码全为0。

    * 指数值:E = 1-bias(而不是exp-bias)

    * 有效数字:M=0.xxxx(而不是1.xxxx),其中xxxx就是frac编码。

    * 特例:当exp=000...0,frac=000...0时,代表0值,注意+0和-0的区别。当exp=000...0,frac≠000...0时,数值非常接近0。

    * 能表示的最小的数大概是0.11111..*2^(-126),刚好与normalized case里能表示的最接近0的数1.0*2^(-126)接上。

    case 3: infinity

    s   1111 1111       000 0000 0000 0000 0000 0000 

    * 当计算发生溢出时,exp变为最大1111..,frac全为0,则M=1.0,此时代表了正无穷。

    * 例如:1.0/0.0 = -1.0/-0.0 = infinity

    case 4:NaN

    s   1111 1111                                     ≠0                           

     

    * 当exp变为最大1111...,而frac并不是0说明并没有溢出。这代表这不是一个正常的数。

    * 例如:sqrt(-1)

    关于浮点数更详细些的介绍,这个教程不错:https://www.cnblogs.com/zhcncn/articles/3782286.html

    floating-point operations(rounding, addition, multiplication):

    舍入分为:

    * towards zero:往零凑整

    * round down(-inf):往负无穷凑整

    * round up(+inf):往正无穷凑整

    * nearest even*(默认模式):往最近的偶数凑整,如果恰好在中点处例如1.5,则往偶数舍入:2。

    在小数模式下,rounding应向使得rounding后数字的最低有效位为偶数。例如,7.895000rounding to  nearest hundredth,有两种选择:7.89或7.90,应选择7.90。

    在二进制中,当保留位的右侧为1000...这种形式时就代表处在中点位置,既可以向上舍入也可以向下舍入。应使得舍入后的数字的最低位为偶数。

    乘法:

    (-1)^{s1}M_{1} 2^{E1} x (-1)^{s2}M_{2} 2^{E2}

    精确结果:(-1)^{s}M2^{E}

    * sign s:s1^s2

    * significand M:M1 x M2

    * exponent E:E1+E2

    修订:

    * 若M≥2,将M往右移,并增加指数E的值

    * 若指数E超过了范围,发生溢出

    * 舍入M以适应frac能表达的精度

    例子(小数部分使用4bits):

    1.010*2^2 x 1.110*2^3 = 10.001100*2^5
                          = 1.00011*2^6
                          = 1.001*2^6     舍入

    加法例子:

    1.010*2^2 + 1.110*2^3 = (0.1010 + 1.1100)*2^3 取较大指数,对齐底数
                          = 10.0110*2^3  有效数大于2,进位
                          = 1.00110*2^4
                          = 1.010 * 2^4

    浮点数加法:大多数情况下都满足一般加法的运算性质,除了结合律:

    (3.14+1e10)-1e10 = 0,   //一个大数与一个小数想加会发生截断,这就造成舍入误差。
    3.14+(1e10-1e10) = 3.14

    浮点数乘法:不满足结合律和分配律:

    由于可能发生了溢出,或者舍入误差导致
    不满足结合律:
    (1e20*1e20)*1e-20 = inf
    1e20 *(1e20*1e-20)=1e20
    
    不满足分配律:
    1e20*(1e20-1e20) = 0.0
    1e20*1e20 - 1e20*1e20 = NaN

    floating point in C:

    转换关系:

    * 在int,float,double间的强制转换会改变bit表达式
    * double/float->int:

       截断fraction部分;

       往0取整;

       对于NaN,设置为Tmin

    * int->double:

       只要int字长小于等于53位,就是精确转换

    * int->float:

       float能表示的最大范围很可能小于int值,此时会根据rounding mode进行舍入

    第三章:机器级的代码表示

    3.1 历史观点

    3.2 程序编码

    3.3 数据格式

    3.4 获取信息

    3.5 算数和逻辑操作

    3.6 控制

    3.7 程序

    3.8 数组分配和获取

    3.9 各种数据结构

    3.10 汇总:理解指针

    3.11 工程实际:使用调试器

    3.12 访问越界和缓存溢出

    3.13 x86-64:扩展IA32到64位

    3.14 浮点程序的机器级别表示

    3.1 历史观点

    第一代单芯片16位微处理器称为8086,之后经过几十年时间发展出了很多版本。我们通常以x86来代指Intel处理器的整个系列,此外它也有名字IA32(Intel architecture 32-bit),以及其扩展版本x86-64。

    ISA:instruction set architecture——指令集体系结构:即为了写出汇编或机器码必须了解的关于处理器设计的部分,包括intel系列的x86,IA32,x86-64;ARM系列的等。

    3.2 程序编码

    machine-level code:

    反汇编指令:

    objdump -d code.o    //使用反汇编器objdump将目标文件code.o进行反汇编
    objdump -d prog      //将可执行文件prog进行反汇编

    notes on formatting:

    >> gcc -O1 -S code.c       //采用1级optimization,得到汇编代码code.s
    >> gcc -O1 -c code.c       //采用1级optimization,得到二进制目标代码code.o

    得到的汇编代码中,以单点 . 开头的行是专用于汇编器和链接器的一些指令,通常我们可以忽略它们。 

    3.3 数据格式

    * “integer”型的1,2,4,8字节:1)整型数据;2)地址值(无类型的指针)

    * 浮点型的4,8,10字节

    * (SIMD向量数据类型,8,16,32,64字节)

    * 代码:字节序列,编码了一系列指令

    * 数组和结构体:内存中连续分配的字节

    3.4 获取信息

    operand specifiers:

     

    data movement instructions:

    不能直接从内存到内存进行数据传递,而必须要经过寄存器周转!

    movq source dest src, dest

    C analog

    Imm

    (立即数)

    Reg
    Mem
    movq $0x4, %rax
    movq $-147,(%rax)
    temp=0x4;
    *p=-147;

    Reg

    (寄存器)

    Reg
    Mem
    movq $rax, %rdx
    movq $rax,(%rdx)
    tmp2=tmp1;
    *p=temp;

    Mem

    (内存)

    Reg
    movq (%rax),%rdx
    temp=*p; 

    3.5 算数和逻辑操作

    load effective address:
    地址计算格式:

    D(Rb,Ri,S)-->Mem[Reg[Rb]+S*Reg[Ri]+D]

    其中:

    D:常量位移,1,2或4字节
    Rb:Base寄存器(任意16位整数寄存器)
    Ri:index寄存器(任意,除了%rsp)
    S:Scale:1,2,4或8

    例子:假设%rdx=0xf000,那么0x80(, %rdx, 2)表示的地址是: 2*0xf000+0x80 = 0x1e080

    leaq a(b, c, d), %rax
    
    功能:
    先计算地址a + b + c * d,然后把最终地址载到寄存器rax中。

    lea指令是mov指令的变种,据说,lea指令是x86体系结构中,是一条最古老但是从某个方面来讲又是最神奇的指令。
    表面上看它做的事情非常简单,根据括号里的源操作数来计算地址,然后把地址加载到目标寄存器中。最逗的是leaq不引用源操作数里的寄存器,只是单纯的计算。那这样的完全可以把它当作乘法指令使用。

    例如: 要计算rbx * 3 - 1,按如下指令:

    movq $8, %rbx                  //%rbx存放8
    leaq -1(%rbx, %rbx, 2), %rax   //-1+%rbx+2*%rbx,即-1+3*%rbx,然后放入%rax

    什么时候用lea指令呢: 在打算用五六条指令来完成某个乘法运算之前,看看能否通过两三条lea指令来代替它。

    注意事项: d的取值范围是1,2,4,8(64位cpu)
     

    unary and binary operations:

    格式 含义
    addq Src, Dest Dest = Dest + Src
    subq Src, Dest Dest = Dest - Src
    imulq Src, Dest             Dest = Dest * Src
    salq Src, Dest Dest = Dest<<Src     //也称为shlq
    sarq Src, Dest   Dest = Dest>>Src     //算数右移
    shrq Src, Dest Dest = Dest<<Src     //逻辑右移
    xorq Src, Dest   Dest = Dest ^ Src
    andq Src, Dest     Dest = Dest & Src
    orq Src, Dest Dest = Dest | Src

    实际例子:

    long arith(long x, long y, long z)  arith:
    {
       long t1 = x+y;                   leaq (%rdi, %rsi), %rax     //%rdi+%rsi,放入rax中
       long t2 = z+t1;                  addq %rdx, %rax             //将rax加上rdx,即将z加到t1上
       long t3 = x+4;                   leaq (%rsi, %rsi, 2), %rdx  //y+2*y,即得到3y并放入rdx
       long t4 = y * 48;                salq $4, %rdx               //将rdx值左移4位,即3y乘以2^4,得48y
       long t5 = t3+t4;                 leaq 4(%rdi, %rdx), %rcx    //4+%rdi+%rdx,即4+x+t4
       long rval = t2*t5;               imulq %rcx, %rax            //将rcx乘到rax上
       return rval;                     ret                         //返回rax
    }
    
    注:第一个参数放在%rdi,第二个参数放在%rsi,第三个参数放在%rdx,返回值放在%rax
    (%rdi, %rsi)的含义是将寄存器rdi与rsi的值相加,即x+y
    (%rsi, %rsi, 2)的含义是%rsi+2*%rsi,即y+2*y

    在上面的计算中,由于使用了leaq和salq运算,使得真正的multiplication运算只用到了一次,这使得代码更高效。

    shift operations:

     

    special arithmetic operations:

    下表给出了有符号和无符号数的全64位乘法和除法。一对寄存器%edx和%eax组成一个64位的四字。 

    指令 效果 描述

    imull S

    mull S

    R[%edx]:R[%eax]<--S x R[%eax]

    R[%edx]:R[%eax]<--S x R[%eax]

    有符号全64位乘法,

    乘积存放在register %edx(高32)和%eax(低32)中

    无符号全64位乘法

    cltd R[%edx]:R[%eax]<--SignExtend(R[%eax]) convert long to double转为4字
    idivl S

    R[%edx]<--R[%edx]:R[%eax] mod S;

    R[%eax]<--R[%edx]:R[%eax]÷S

    有符号除法
    divl S

    R[%edx]<--R[%edx]:R[%eax] mod S;

    R[%eax]<--R[%edx]:R[%eax]÷S

    无符号除法

    3.6 控制

    condition codes:

    accessing the condition codes:

     

    jump instructions and their encodings:

    指令 效果 指令 效果
    jmp Always jump ja Jump if above(unsigned >)
    je/jz Jump if eq / zero jae Jump if above / equal
    jne/jnz Jump if !eq / !zero jb Jump if below(unsigned <)
    jg Jump if greater jbe Jump if below / equal
    jge Jump if greater / eq js Jump if sign bits is 1(neg)
    jl Jump if less jns Jump if sign bit is 0 (pos)
    jle Jump if less / eq x x

    translating conditional branches:

     

    loops:

     

    conditional move instructions:

     

    switch statements:

     

    3.7 过程(procedures)

    machanisms:

    * 传递控制权

    * 传递数据

    * 内存管理

    * 使用机器指令来实现其机制

    我们使用机器指令来实现其机制,但个中选择依赖于设计者。这些不同的选择构成了application binary interface(ABI)。

    stack frame structures:

    pushq Src
    
    功能:
    1)获取Src处的操作数
    2)将%rsp值减8
    3)在%rsp指向的地址处写入操作数
    popq Dest
    
    功能:
    1)读取%rsp指向的地址处的值
    2)将%rsp值加8
    3)将读取的值存入Dest(通常是个寄存器)

    栈帧是实现递归的机制。

                           -------------------
                            |               |
                            |   previous    |
                            |    frame      |
                            |               |
                            |---------------|
                            | arguments 7+  |    //可能保存着当前被调函数的参数
                            |---------------|
                            | return addr   |    //返回地址是由call指令push入栈的
                            |---------------|
      frame pointer: %rbp-> |  old %rbp     |
               (optional)  -------------------      
                            |saved registers|    //保存寄存器值
                            |       +       |
                            |local variables|    //局部变量,如果无法保存在寄存器中就入栈
                            |               |
                            |---------------|
                            |argument build |    //调用其他函数时可能需要的参数
                            |  (optional)   |
      stack pointer: %rsp->-------------------
    
    //调用者的返回地址就存放在ebp+4地址单元处。存放完返回地址,
    //紧挨着的高位地址处存放的就是调用者传递给被调者的输入参数(ebp+8, ebp+12....)

    举个例子:

    void i386_init(void)
    {
       test_backtrace(5);
    }

    在进入test_backtrace()之前,%esp == 0xf010ffe0,%ebp==0xf010fff8。

    即当前i386_init()函数的栈帧为:0xf010ffe0~0xf010fff8。而它把即将要调用test_backtrace()需传入的参数‘5’保存在地址0xf010ffe0处。

    在进入test_backtrace()之前,保存返回地址,即将%esp值下移并压入返回地址。此时%esp==0xf010ffdc。

    然而进入test_backtrace()的范围,先执行几条准备命令:

    push %ebp            //保存上一栈帧的%ebp值
    mov  %esp, %ebp      //现在%ebp是当前函数栈帧底,它指向的地址保存的是上一栈帧的%ebp!
    push %ebx            //保存%ebx的值,以备在test_backtrace()中使用
    sub  $0xc, %esp      //将栈指针下移,即为当前函数开辟栈帧空间

    这几条命令执行完之后,新的栈帧建立起来,%esp==0xf010ffc8,%ebp==0xf010ffd8。

    即当前test_backtrace()的栈帧为:0xf010ffc8~0xf010ffd8。

    如果在test_backtrace()中继续调用子函数,那么在进入进一步的栈帧之前,%esp指向的地址将保存返回地址。

    总结:在运行时,每一栈帧将对应两个寄存器:%ebp指向的单元保存上一栈帧的%ebp;在进入下一函数前,%esp指向的单元保存当前栈帧的返回地址。


    栈帧中的内容有:

    1)返回信息

    2)局部存储信息(如果需要的话)

    3)暂时的空间(如果需要的话)

    管理方法:

    1)当进入某一过程时开辟空间

         * “set-up”代码

         *call指令包含了push

    2)离开过程时释放空间

         *“finish”代码

         *ret指令包含了pop

    transfering control:

    在执行程序时,指令寄存器%rip始终保存下一指令的地址(指向指令),栈指针寄存器%rsp始终保存栈顶地址(指向栈顶)。当需要调用子函数时,先将该函数的下一条指令的地址入栈,然后%rip变成子函数的入口地址。

    register usage conventions:

    函数的参数用哪些寄存器来存放呢?

    按惯例,前6个arguments存放在:

    %rdi
    %rsi
    %rdx
    %rcx
    %r8
    %r9

    如果超过了6个,更多的参数则存放到栈中。

    函数的返回值使用寄存器%rax来保存。

    在函数调用时由谁保管暂时值?

    “caller saved”:由caller在它自己的frame中保管暂存值,在执行call之前保管

    “callee saved”:由callee在它的frame中保管;callee负责在返回给caller时恢复它们的值

    按惯例,%eax,%edx,%ecx归类为caller-save寄存器,主调函数用于暂存它需要的值,当主调函数调用其他函数时需要先把这些寄存器的值入栈;%ebx,%esi,%edi被归类为callee-save寄存器,被调函数用于暂存它需要的值,当被调函数被调用时需要先把这些寄存器的值入栈。

    procedure example:

     

    recursive procedures:

     

    3.8

     

    3.12 存储器的越界引用和缓冲区溢出

     

    第十章 系统级IO(2019.8.17我直接跳到这里开始学习)

    10.1 Unix I/O

    1. 一个linux“文件”实际上就是m个bytes组成的序列:B0,B1,...,Bm-1

    2. 所有I/O设备都用“文件”来表示:/dev/sdat2(/usr disk partition);/dev/tty2(终端)

    3. 甚至内核也是用文件来表示的:/boot/vmlinuz-3.13.0-55-generic(kernel镜像)

    10.2打开和关闭文件

    每个文件有个type用于指示它在系统中的角色:1.regular file:包含任意数据;2.directory:相关的一组文件的索引;3.socket:为了与另一台机器上的进程通信

    其他的一些文件类型(在这里我们不深究):Named pipes(FIFOs)、Symbolic links、Character and block devices

    Regular files:

    在应用中常常区分为文本文件和二进制文件:文本文件是只含ASCII或Unicode字符的regular file;所有其余的文件都是二进制文件(包括JPEG图像、视频文件、目标文件等)。但注意,内核并不能区分出一个文件到底是文本文件还是二进制文件,这种区别仅仅只有应用程序能区别。

    文本文件是一系列test lines的序列:每个文本行都使用一个newline字符(‘\n’,0xa)来结束。

    Opening files:

    //打开一个文件,通知内核你已经准备好访问该文件了
    int fd;    //file descriptor
    
    if((fd = open("/etc/hosts", O_RDONLY)) < 0){
        perror("open");
        exit(1);
    }
    //返回一个标识整数file descriptor(例如,这个数是1024,表示能同时打开的文件数量最多为1024个),如果为-1,表示发生了错误

    * 每一个linux shell在创建进程时,会自动打开三个与终端相关联的文件:

       0: 标准输入(stdin) 

       1: 标准输出(stdout)

       3: 标准错误(stderr)

    Closing files:

    int fd;        //file descriptor
    int retval;    //return value
    
    if((retval = close(fd)) < 0){
        perror("close");
        exit(1);
    }
    

    * 尝试关闭一个本已经关闭的文件常常是多线程程序中灾难的原因。 

    10.3 读和写文件

    Reading files:

    char buf[512];
    int fd;        //file descriptor
    int nbytes;    //number of bytes read
    
    //打开文件fd, 然后从中读取最多512个字节的数据到buf。称之为short write。
    //从当前文件位置开始读,拷贝到内存中,然后刷新当前指向的文件位置
    if((nbytes = read(fd, buf, sizeof(buf))) < 0){
        perror("read");
        exit(1);
    }

    Writing files:

    char buf[512];
    int fd;        //file descriptor
    int nbytes;    
    
    //写最多512字节到fd文件中去
    if((nbytes = write(fd, buf, sizeof(buf))) < 0){
        perror("write");
        exit(1);
    }

    例子:

    #include "csapp.h"
    
    int main(){
        char c;
        while(Read(STDIN_FIELD, &c, 1) != 0)        //读文件STDIN
            Write(STDOUT_FIELD, &c, 1);             //写文件STDOUT   
        exit(0);
    }

    short count:

    在有些时候,read和write传送的字节数比应用程序要求的少,返回的值称为“不足值”(short count),这些不足值不表示有错误。出现这种情况的原因有:

    1. 读时遇到EOF,此时读函数返回0以表示读到了文件末尾;

    2. 从终端读文本行。若打开文件是与终端相关联的,那么每个read函数将一次传送一个文本行,返回的不足值等于文本行的大小。

    3. 读和写网络套接字(socket)。若打开的文件对应于网络套接字,那么较长的网络延迟和内部缓冲约束会引起read和write返回不足值。对unix管道调用read和write时也可能出现不足值。

    10.4 用RIO包健壮地读写

    在上面我们讲到了使用系统I/O函数进行读写时会发生返回不足值的问题,为了自动处理这些不足值的情况,可以自己编写一些更稳定的I/O函数来使用。

    Unbuffered RIO Input and Output:

    与Unix的read和write有相同的接口,尤其适用于在网络sockets上传输数据。

    #include "casapp.h"
    
    ssize_t rio_readn(int fd, void *usrbuf, size_t n);
    ssize_t rio_writen(int fd, void *usrbuf, size_t n);
    
    //如果传输正常,返回num字节;如果遇到EOF(只对rio_readn),返回0;如果错误,返回-1

    1.  rio_readn 只在遇到EOF时返回short count。只有当你知道需要读取多少字节时才使用这个函数。

    2. rio_writen 永远不会返回short count。

    //rio_readn - robustly read n bytes (unbuffered)
    //由于系统的I/O函数可能会产生short count的问题,所以我们自己写一个更稳定一点的读写函数
    ssize_t rio_readn(int fd, void *usrbuf, size_t n){
        size_t nleft = n;
        ssize_t nread;
        char* bufp = usrbuf;
        
        while(nleft > 0){
            if((nread = read(fd, bufp, nleft)) < 0){
                if(errno == EINTR)    //interrupted by sig handler return
                    nread = 0;        //and call read() again
                else
                    return -1;        //errno set by read()
            }
            else if(nread == 0)
                break;                //EOF
            nleft -= nread;
            bufp += nread;
        }
        return (n - nleft);           //return >= 0
    }
    

     

    10.5 读取文件元数据

     

    10.6 共享文件

     

    10.7 I/O重定向

     

    10.8 标准I/O

     

    10.9 综合:我该使用哪些I/O函数

    第十一章  网络编程

    11.1 客户端-服务器编程模型

    11.2 网络

    每台主机上有个网络适配器,从网络上接收到的数据经由适配器->I/O总线->存储总线->到达主存。

    适配器一端连接主机,另一端连接到集线器的一个端口上。集线器不加分辨地将从一个端口上收到的每个“位”复制到其他所有端口上。因此,每台主机都能看到每个位。每个适配器有一个唯一的48位地址(MAC address,如f0:18:98:4f:d0:be),当它发送一段“位”(帧)到网段上的任何主机时,每个主机适配器都能看到这个帧,但只有目的主机实际读取它。

    这样的多个计算机(host)由一些电缆连接到一个集线器上(hub)构成的网络称为以太网段,这是最底层的网络结构。比如,一个机房内的十多台电脑连到一个集线器上,它们就构成一个以太网段。hub的功能本质上就是个复读机+广播,它把从任意端口接收到的信息都复制,再广播给其他端口。

    如果把不同区域的集线器使用被称作“网桥”(bridge)(高密度端口的网桥其实就是交换机)的盒子连接起来,那就组成覆盖域更大一些的所谓“桥接以太网”。比如一个公司、一个学校就可以采用这种方式来互联通信。集线器只是复读机,而网桥则更聪明,它能学会有选择性地传输信息。到这个层面依然只是局域网(LAN)。

    如果把不同区域的不兼容局域网采用被称作“路由器”(router)的盒子连接起来,那就组成了所谓的“互联网”(internet)。

    问题来了:如何在不兼容的局域网、广域网之间传输信息呢?

    策略:在每个主机和路由器上运行协议软件(protocol software)——

    1)提供命名格式:为每台主机地址定义统一的格式host address,根据主机所处的网络拓扑结构为其分配ip地址

    2)提供传输机制:定义一种标准的传输单元packet = header + payload

    11.3 全球IP因特网

    基于TCP/IP协议族:

    * IP(Internet Protocol):提供基本命名格式和不可靠的传输机制,是host-to-host的;

    * UDP(Unreliable Datagram Protocol):稍微扩展了IP协议,包可以在process-to-process间传递,而不是在主机间传送;

    * TCP(Transmission Control Protocol):构建在IP协议之上的复杂协议,提供了可靠的process-to-process连接(connections)。

    A Programmer‘s View of the Internet:

    1. 主机被映射到一个32位的IP地址:如 172.20.10.9(每个字节写成一个十进制数,例如0x8002C2F2 == 128.2.194.242)

    2. IP地址被映射为域名:如www.cs.cmu.edu,注:域名与IP地址是多对多的映射。DNS(域名服务器)

    3. 一个位于网络上的主机上的进程可以通过一个“connection”与另一个主机上的进程进行信息交流。

    注:32位的IP地址是IPv4(第四代),升级到128位之后称为IPv6

    Internet Connections:

    客户端和服务端是通过“连接”(connections)来传输字节流的。

    一个套接字是连接的一个端点,每个套接字有相应的套接字地址,由一个因特网地址和一个16位的整数端口组成:IPaddress:port

    一个端口用于标记一个进程。当客户端发起连接请求时,其套接字地址中的端口是由内核自动分配,称为临时端口。然而,服务器套接字地址中的端口通常是某个知名端口,例如ssh servers:22/ssh;email server:25/smtp;Web servers:80/http。在unix机器上,在/etc/services中包含了这台机器提供的服务及其知名端口。

    由客户端发起一个请求:128.2.194.242: 80(即网页服务),服务端128.2.194.242的内核收到该信号,建立起与自己的Web server的连接。套接字对:(cliaddr::cliport, servaddr::servport)

                                           

    Sockets:

    对于开发者来说,一个Socket就是一个file descriptor,它使得应用程序能读或者写网络。注:所有Unix I/O设备,包括网络,都被抽象成了文件!

    对于内核来说,一个socket就是通信的一个端点。

     

     

    展开全文
  • CSAPP深入理解计算机系统(第二版)》课后答案
  • CSAPP深入理解计算机系统实验一

    千次阅读 2018-01-30 16:32:27
    /* * CS:APP Data Lab * * * * bits.c - Source file with your solutions to the Lab. * This is the file you will hand in to your instructor. * * WARNING: Do not include the header;
    /* 
     * CS:APP Data Lab 
     * 
     * <Please put your name and userid here>
     * 
     * bits.c - Source file with your solutions to the Lab.
     *          This is the file you will hand in to your instructor.
     *
     * WARNING: Do not include the <stdio.h> header; it confuses the dlc
     * compiler. You can still use printf for debugging without including
     * <stdio.h>, although you might get a compiler warning. In general,
     * it's not good practice to ignore compiler warnings, but in this
     * case it's OK.  
     */
    
    #if 0
    /*
     * Instructions to Students:
     *
     * STEP 1: Read the following instructions carefully.
     */
    
    You will provide your solution to the Data Lab by
    editing the collection of functions in this source file.
    
    INTEGER CODING RULES:
     
      Replace the "return" statement in each function with one
      or more lines of C code that implements the function. Your code 
      must conform to the following style:
     
      int Funct(arg1, arg2, ...) {
          /* brief description of how your implementation works */
          int var1 = Expr1;
          ...
          int varM = ExprM;
    
          varJ = ExprJ;
          ...
          varN = ExprN;
          return ExprR;
      }
    
      Each "Expr" is an expression using ONLY the following:
      1. Integer constants 0 through 255 (0xFF), inclusive. You are
          not allowed to use big constants such as 0xffffffff.
      2. Function arguments and local variables (no global variables).
      3. Unary integer operations ! ~
      4. Binary integer operations & ^ | + << >>
        
      Some of the problems restrict the set of allowed operators even further.
      Each "Expr" may consist of multiple operators. You are not restricted to
      one operator per line.
    
      You are expressly forbidden to:
      1. Use any control constructs such as if, do, while, for, switch, etc.
      2. Define or use any macros.
      3. Define any additional functions in this file.
      4. Call any functions.
      5. Use any other operations, such as &&, ||, -, or ?:
      6. Use any form of casting.
      7. Use any data type other than int.  This implies that you
         cannot use arrays, structs, or unions.
    
     
      You may assume that your machine:
      1. Uses 2s complement, 32-bit representations of integers.
      2. Performs right shifts arithmetically.
      3. Has unpredictable behavior when shifting an integer by more
         than the word size.
    
    EXAMPLES OF ACCEPTABLE CODING STYLE:
      /*
       * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
       */
      int pow2plus1(int x) {
         /* exploit ability of shifts to compute powers of 2 */
         return (1 << x) + 1;
      }
    
      /*
       * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
       */
      int pow2plus4(int x) {
         /* exploit ability of shifts to compute powers of 2 */
         int result = (1 << x);
         result += 4;
         return result;
      }
    
    FLOATING POINT CODING RULES
    
    For the problems that require you to implent floating-point operations,
    the coding rules are less strict.  You are allowed to use looping and
    conditional control.  You are allowed to use both ints and unsigneds.
    You can use arbitrary integer and unsigned constants.
    
    You are expressly forbidden to:
      1. Define or use any macros.
      2. Define any additional functions in this file.
      3. Call any functions.
      4. Use any form of casting.
      5. Use any data type other than int or unsigned.  This means that you
         cannot use arrays, structs, or unions.
      6. Use any floating point data types, operations, or constants.
    
    
    NOTES:
      1. Use the dlc (data lab checker) compiler (described in the handout) to 
         check the legality of your solutions.
      2. Each function has a maximum number of operators (! ~ & ^ | + << >>)
         that you are allowed to use for your implementation of the function. 
         The max operator count is checked by dlc. Note that '=' is not 
         counted; you may use as many of these as you want without penalty.
      3. Use the btest test harness to check your functions for correctness.
      4. Use the BDD checker to formally verify your functions
      5. The maximum number of ops for each function is given in the
         header comment for each function. If there are any inconsistencies 
         between the maximum ops in the writeup and in this file, consider
         this file the authoritative source.
    
    /*
     * STEP 2: Modify the following functions according the coding rules.
     * 
     *   IMPORTANT. TO AVOID GRADING SURPRISES:
     *   1. Use the dlc compiler to check that your solutions conform
     *      to the coding rules.
     *   2. Use the BDD checker to formally verify that your solutions produce 
     *      the correct answers.
     */
    
    
    #endif
    /* Copyright (C) 1991-2014 Free Software Foundation, Inc.
       This file is part of the GNU C Library.
    
       The GNU C Library is free software; you can redistribute it and/or
       modify it under the terms of the GNU Lesser General Public
       License as published by the Free Software Foundation; either
       version 2.1 of the License, or (at your option) any later version.
    
       The GNU C Library is distributed in the hope that it will be useful,
       but WITHOUT ANY WARRANTY; without even the implied warranty of
       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
       Lesser General Public License for more details.
    
       You should have received a copy of the GNU Lesser General Public
       License along with the GNU C Library; if not, see
       <http://www.gnu.org/licenses/>.  */
    /* This header is separate from features.h so that the compiler can
       include it implicitly at the start of every compilation.  It must
       not itself include <features.h> or any other header that includes
       <features.h> because the implicit include comes before any feature
       test macros that may be defined in a source file before it first
       explicitly includes a system header.  GCC knows the name of this
       header in order to preinclude it.  */
    /* glibc's intent is to support the IEC 559 math functionality, real
       and complex.  If the GCC (4.9 and later) predefined macros
       specifying compiler intent are available, use them to determine
       whether the overall intent is to support these features; otherwise,
       presume an older compiler has intent to support these features and
       define these macros by default.  */
    /* wchar_t uses ISO/IEC 10646 (2nd ed., published 2011-03-15) /
       Unicode 6.0.  */
    /* We do not support C11 <threads.h>.  */
    /* 
     * addOK - Determine if can compute x+y without overflow
     *   Example: addOK(0x80000000,0x80000000) = 0,
     *            addOK(0x80000000,0x70000000) = 1, 
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 20
     *   Rating: 3
     */
     //求和溢出问题
    int addOK(int x, int y) {
    	int sum = x + y;
    	return !((x ^ sum) & (y ^ sum));
    }/*会一个整形数字的符号位的判别*/
    //ops 6
    /* 
     * allEvenBits - return 1 if all even-numbered bits in word set to 1
     *   Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 12
     *   Rating: 2
     */
     //所有的偶数为都为1
     //way 1
    int allEvenBits(int x) {
    	int k0 = x & 0xff;
    	int k1 = (x >> 8) & 0xff;
    	int k2 = (x >> 16) & 0xff;
    	int k3 = (x >> 24) & 0xff;
    	k0 = 0x55 + (~k0 + 1);
    	k1 = 0x55 + (~k1 + 1);
    	k2 = 0x55 + (~k2 + 1);
    	k3 = 0x55 + (~k3 + 1);
    	x = k0 | k1 | k2 | k3;
    	return !x;
    }
    //ops 23
    //way 2
    int allEvenBits(int x)
    {
    	int EvenBits = (((0x55 << 8) | 0x55) << 16) | (0x55 << 8) | 0x55;//结果0x55555555
    	return !((EvenBits & x) ^ EvenBits);
    	//如果x是0x55555555或者含有0x55555555的数,EvenBits & x得到0x55555555,否则得到0
    	//0x55555555 ^ 0x55555555 = 0
    	//0 ^ 0x55555555 = 0x55555555
    }
    /*
     * bitParity - returns 1 if x contains an odd number of 0's
     *   Examples: bitParity(5) = 0, bitParity(7) = 1
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 20
     *   Rating: 4
     *  00000111 -> 7
     *  00000101 -> 5
     */
     //统计0的个数
    int bitParity(int x) {
    	x ^= x >> 16;
    	x ^= x >> 8;
    	x ^= x >> 4;
    	x ^= x >> 2;
    	x ^= x >> 1;
    	return x&1;
    }
    /* 
     * float_f2i - Return bit-level equivalent of expression (int) f
     *   for floating point argument f.
     *   Argument is passed as unsigned int, but
     *   it is to be interpreted as the bit-level representation of a
     *   single-precision floating point value.
     *   Anything out of range (including NaN and infinity) should return
     *   0x80000000u.
     *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
     *   Max ops: 30
     *   Rating: 4
     */
     //求浮点数变整形
    int float_f2i(unsigned uf) {
    	int sign = uf >> 31;//0xffffffff或者0
    	int temp = (uf >> 23) & 0xff;//阶码
    	int num = uf & ((1 << 23) - 1);//尾数
    	int ans;
    	if(temp < 127)//e = E - 127
    		ans = 0;
    	if(temp > 157)
    		ans = 0x80000000u;
    	ans = ((1 << 30) + (num << 7)) >> (157 - temp);
    	if(sign)
    		ans = ~ans + 1;
    	return ans;
    }
    /* 
     * byteSwap - swaps the nth byte and the mth byte
     *  Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
     *            byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
     *  You may assume that 0 <= n <= 3, 0 <= m <= 3
     *  Legal ops: ! ~ & ^ | + << >>
     *  Max ops: 25
     *  Rating: 2
     */
     //交换字节
     //way 1
    int byteSwap(int x, int n, int m) {
    	int x1 = (0xff << (n << 3)) & x;
    	int x2 = (0xff << (m << 3)) & x;
    	x = x ^ x1 ^ x2;
    	x1 = ((x1 >> (n << 3)) & 0xff) << (m << 3);
    	x2 = ((x2 >> (m << 3)) & 0xff) << (n << 3);
    	x = x | x1 | x2;
        return !x;
    }
    //way 2
    int byteSwap(int x, int n, int m)
    {
    	int xn = n << 3;
    	int xm = m << 3;
    	int x1 = x >> xn;
    	int x2 = x >> xm;
    	return (((x & (~(0xff << xn))) & (~(0xff << xm))) | (x1 << xm) | (x2 << xn);
    	//和way 1差不多的思路
    }
    /* 
     * float_twice - Return bit-level equivalent of expression 2*f for
     *   floating point argument f.
     *   Both the argument and result are passed as unsigned int's, but
     *   they are to be interpreted as the bit-level representation of
     *   single-precision floating point values.
     *   When argument is NaN, return argument
     *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
     *   Max ops: 30
     *   Rating: 4
     */
     //返回一个浮点数的两倍
    unsigned float_twice(unsigned uf) {
    	unsigned sign = uf & 0x80000000;
    	unsigned temp = uf & 0x7f800000;
    	if(temp)
    	{
    		if(temp != 0x7f800000){
    			uf = uf + 0x00800000;
    			if(temp == 0x7f800000)//not a number
    				uf = uf & 0xff800000;
    		}
    	}
    	else 
    		uf = (uf << 1) | sign;//如果阶码为0,那么尾数部分向左移动移位就是乘2
    	return uf;
    }
    /* 
     * isGreater - if x > y  then return 1, else return 0 
     *   Example: isGreater(4,5) = 0, isGreater(5,4) = 1
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 24
     *   Rating: 3
     */
     //比较两个数的大小
    int isGreater(int x, int y) {
    	int signx = x >> 31;
    	int signy = y >> 31;//结果,0xffffffff或者0
    	int signxy = !(signx ^ signy);//结果,同号为1,异号为0
    	return !((signxy & ((x + (~y)) >> 31)) | (( !signxy ) & signx));
    	//x + (~y) = x - y - 1,如果x < y会使得结果为0
    }
    /*
     * satAdd - adds two numbers but when positive overflow occurs, returns
     *          maximum possible value, and when negative overflow occurs,
     *          it returns minimum positive value.
     *   Examples: satAdd(0x40000000,0x40000000) = 0x7fffffff
     *             satAdd(0x80000000,0xffffffff) = 0x80000000
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 30
     *   Rating: 4
     */
     //求和问题
    int satAdd(int x, int y) {
    	int ans = x + y;
    	int overflow = ((x ^ ans) & (y ^ ans)) >> 31;//结果有两种,溢出为0xffffffff,不溢出为0
    	return ((ans >> (overflow & 31)) + (overflow << 31);
    	//正正溢出,0xffffffff + 1 = 0x7fffffff
    	//负负溢出,0 + 0x80000000(0xffffffff << 31)
    	//不溢出,(ans >> 0) + (0 << 31)
    }
    /* 
     * copyLSB - set all bits of result to least significant bit of x
     *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
     *   Legal ops: ! ~ & ^ | + << >>
     *   Max ops: 5
     *   Rating: 2
     */
     //复制最低位
    int copyLSB(int x) {
      return ((x << 31) >> 31);
    }/*注意逻辑移位和算术移位的区别*/
    

    如果想更加的了解题目的解法,可以参考:

    http://blog.csdn.net/y_universe/article/details/79075963

    
    展开全文
  • 配套的实验http://csapp.cs.cmu.edu/3e/labs.html 原作者的公开课http://www.cs.cmu.edu/~213/schedule.html 热心人士搬运到B站上的视频(无字幕)卡内基梅隆大学 Introduction to Computer Systems CMU 15-213 Fall ...

    CMU

    nju

    南京大学袁春风的研究生余子豪同学设计了一个配套实验 ics2015 NEMU.做这个实验才是学习的真正方法。这个实验挺有意思的,不是一个个CMU的零散实验,而是类似于写一个小型的OS,是余同学他们模仿MIT的QEMU写的,前半部分类似于写一个简单的GDB,最终目标是在NEMU上面跑仙剑奇侠传。
    做完南大的PA(programming-assignment),再把MIT的QEMU JOS实验做一遍就真的很深入理解计算机及操作系统了。

    Other

    备注

    整理自https://www.zhihu.com/question/20402534

    展开全文
  • 转载自 http://condor.depaul.edu/glancast/374class/docs/csapp_compile_guide.html Compiling with the CSAPP library ...The csapp collection of useful auxilliary functions are declared in the file cs...

    转载自   http://condor.depaul.edu/glancast/374class/docs/csapp_compile_guide.html

     

    Compiling with the CSAPP library


    The csapp collection of useful auxilliary functions are declared in the file csapp.h and defined in the csapp.c file.

    These functions include the utility functions for Unix file i/o, sockets, signals, threads and semaphores.

    The threads (and semphores) functions require linking with libraries other than the standard C library.

    The threads functions require the pthread library.

    On some systems (not ctilinux1), the semaphores also require the rt (run time) library.

    Example 1

    Goal: Compile a program sample.c that includes "csapp.h"

    Assumptions: csapp.h and csapp.c are in the same directory as sample.c

          gcc -O2 -lpthread -o sample sample.c csapp.c
        

    On systems that also need to explicitly use the run time library, the command would just add another -l option:

          gcc -O2 -lpthread -lrt -o sample sample.c csapp.c
        

    Example 2

    Goal: Same as Example 1, but avoid recompiling csapp.c every time.

    In Example 1, the file csapp.c is recompiled every time you compile sample.c or any program that uses the csapp lib even though csapp.c doesn't change.

    So you could compile (but not link) csapp.c just once to get an object file csapp.o:

          gcc -O2 -c csapp.c
        

    Then to compile sample.c

          gcc -O2 -lpthread -o sample sample.c csapp.o
        

    Example 3

    Goal: Same as Example 2, but avoid having to type so much.

    To reduce the amount of typing required, we could create a make file. The make command looks for files named makefile or Makefile.

    We want the make command to read the makefile and automatically create the executable file sample from the files it depends on: sample.c and csapp.o.

    But csapp.o depends on csapp.c.

    So the makefile can have 2 targets: sample and csapp.o.

    For each target we need to provide the command(s) to create the target. Each command line should begin with a tab!

          sample: sample.c csapp.o
                 gcc -O2 -lpthread -o sample sample.c csapp.o
    
          csapp.o: csapp.c
                 gcc -O2 -c csapp.c
        

    To build sample all we need to type is:

          make
        

    Example 4

    Goal: Compile any one of a fixed set of files that uses the csapp library without having to type too much.

    Now suppose we have 3 separate programs: sample1.c, sample2.c, and sample3.c that use the csapp library.

    We could write a makefile that has a target and rule for each one:

          sample1: sample1.c csapp.o
                 gcc -O2 -lpthread -o sample1 sample1.c csapp.o
    
    
          sample2: sample2.c csapp.o
                 gcc -O2 -lpthread -o sample2 sample2.c csapp.o
    
    
          sample3: sample3.c csapp.o
                 gcc -O2 -lpthread -o sample3 sample3.c csapp.o
    
          csapp.o: csapp.c
                 gcc -O2 -c csapp.c
        

    To compile, say sample2, just type:

          make sample2
        

    Example 5

    Goal: Compile any file that uses the csapp library without having to modify the makefile.

    Instead of having to write an entry for each of the 3 programs in Example 4, we can also write a "rule" in the makefile that handles all 3 cases (and even an named xxx.c that uses csapp if it is added later):

          .c:
                gcc -O2 -lpthread -o $* $< csapp.o
    
          csapp.o: csapp.c
                gcc -O2 -c csapp.c
        

    With this makefile, we can now compile and link any one of the .c files that uses csapp. For example to compile and link sample2.c:

          make sample2
        

    If csapp.c has not yet been compiled, this make command will automatically execute two commands:

          gcc -O2 -c csapp.c
          gcc -O2 -lpthread -o sample2 sample2.c csapp.o
        

    Now sample2 can be executed and csapp.c has been also been compiled to produce csapp.o for further use.

    So if we now want to compile sample3, we again just type

          make sample3
        

    Since csapp.o exists and is "up to date", only one command will be executed (automatically):

          gcc -O2 -lpthread -o sample3 sample3.c csapp.o
        

    Example 6

    Goal: Same as Example 5, but also using only one copy of csapp.h and csapp.c that are located in one fixed separate directory.

    All the preceding examples assume the csapp.h and csapp.c files are in the same directory as the file that will use them.

    There is no reason to keep making copies of these files if they are not changing.

    So suppose these files are in the subdirectory, say cslib, of your login directory: ~/cslib. That is, suppose the paths to the two files csapp.h and csapp.c are:

        ~/cslib/csapp.h
        ~/cslib/csapp.c
        

    In some other directory, say ~/examples/threads in your account you have files sample1.c, sample2.c, etc. that will use the csapp library.

    There is no need to copy the csapp.h or csapp.c files to the ~/examples/threads directory.

    Instead, create a make file (named makefile) in the ~/examples/threads directory:

          .c:
                cd ~/cslib; make csapp.o
                gcc -O2 -I ~/cslib -lpthread -o $* $<
        

    This makefile has 2 commands to make the target.

    The first command (temporarily) changes to the cslib directory and makes the csapp.o. Note that if csapp.o already exists, it will not be recompiled.

    The second command (gcc ...) has an -I ~/cslib option. This tells the compiler to look in the ~/cslib directory for include files (csapp.h). It will also look there for any missing object files (csapp.o).

    转载于:https://www.cnblogs.com/li-daphne/p/5418330.html

    展开全文
  • 看完这一本《CSAPP深入理解计算机系统
  • csapp 深入理解计算机系统读书笔记CHAPTER 1 计算机系统漫游1.1 信息就是位上下文预处理阶段 将库中系统文件插入代码 hello.c->hello.i 文本编译阶段 将高级语言翻译成汇编语言 hello.i->hello.s 文本汇编阶段...
  • 陆陆续续花了一个月的时间,终于看完了...从同宿舍的鲁博士那里第一次听说这本书,了解到该书从一个程序员的视角详细剖析了整个计算机系统,涵盖了组成原理、汇编语言、体系结构、操作系统、网络等计算机基础知识,当
  • 计算机的移位运算有一种很重要的作用就是利用掩码运算去提取一个位模式的一段信息。 2、在C语言中的条件语句,以及三目的条件运算符,都可以用移位的方式来做。 3、在进行位扩展操作的时候,比较讲一个32位的有符号...
  • 隐藏关卡。Secretphase 这个隐藏关卡还是很难发现的,自己带的班上的学生中,仅有3个学生发现并解除了炸弹。中间也出现了一些小小问题,在给他们验收的时候也有意识的去引导他们发现一些小问题,并讨论解决。...
  • CSAPP大名鼎鼎了,网上许多人都完成了其独具特色的实验,特别是二进制炸弹、缓冲区炸弹等。  二进制炸弹实验,主要锻炼学习者使用反汇编工具对二进制可执行程序调试、分析的能力。学习者首先需要使用调试器调试bomb...
  • Level1 Level1是和level0一样调用完getbuf以后我们不返回getbuf的调用者test而是去执行fizz函数,区别就是这个fizz函数要求我们传入参数,而且传入的参数必须是我们的cookie。所以在level0的方法我们轻松的知道了...
  • 由于实验太长所以还是采用分开 其实感觉之前做过那个bomb实验以后,这个实验相对来说还是很容易的,主要是要搞懂缓冲区...做这个实验首先是要建立在bomb实验和对函数调用栈过程的基础上,如果你觉得你理解起来有困难
  • level4 前面4个level都是栈基址是固定的,所以我们可以猜测到栈帧的结构进行覆盖篡改,这一关就是引入了缓冲区溢出攻击的一种保护措施,就是栈基址随机化,让栈基址不可以猜测,我们来实施缓冲区溢出攻击,那么我们...
  • Level0 首先是test函数和getbuf函数以及smoke函数的c代码如下:   Level0 就很简单,就是本来test函数调用getbuf函数,调用完以后还返回test函数,现在我们要做的是调用getbuf函数后,通过输入我们的exploit,...
  • level2 Level2是更进了一步,也是不返回到test,而是去执行函数bang,但是区别是bang也要传入参数,但是参数是是一个全局变量,这里就是不同于level1那样在栈上覆盖了,因为全局变量要去内存地址中修改了,但是又不...
  • level3 前面的几个实验都是不管是去执行别的函数比如bang还是去执行我们自己的exploit的函数,最后都没有返回就退出了,我们通过我们的漏洞利用代码可以修改内存(比如把全局变量修改为我们的cookie)修改寄存器中...
  • 深入理解计算机系统(第二版)》CSAPP 第三章 家庭作业 这一章介绍了AT&T的汇编指令 比较重要 本人完成了《深入理解计算机系统(第二版)》(以下简称CSAPP)第三章的家庭作业,并与网上的一些答案进行了对比修正。 ...
  • 超高清扫描的最新版本深入理解计算机系统,与第二版相比,从以IA32和x86-64为基础转变为完全以x86-64为基础,编程人应人手一本的五星好书,本书号称“实际价值等同于同等重量的黄金”,如果想要写出高效代码,对...
  • 做该实验,务必已经看完了深入理解计算机系统的第三章节。了解常见c语言结构对应的汇编代码的常见形式。 2. 同时,请务必去卡梅隆大学课程官网,查看说明文件。下载gdb,一般ubuntu自带了。然后,去网上搜索,常见...
  • 经典教材深入理解计算机系统最新版实验材料! 经典教材深入理解计算机系统最新版实验材料!
  • CSAPP(深入理解计算机系统)

    千次阅读 2016-10-19 23:44:13
    CSAPP MIPS 学习笔记
  • 书的确是难得的书。我第一次试图读这本书是几个月以前,当时第2章“信息的表示和处理”没看完就放下了,觉得讲了一大堆数字表达方式很没意思……这次稍微坚持了一下,没想到就一口气读下来了…… ...

空空如也

1 2 3 4 5 ... 20
收藏数 11,052
精华内容 4,420
关键字:

csapp