CSAPP-1:计算机系统漫游

1.1位与上下文

源程序是由0和1的位组成的序列，8位为1字节，对于程序是如何运行的：我们写的c语言每一个字符都用ascii来表示，被叫做文本文件。通过这个实例我们知道，在计算机中所有信息都是由一串比特所构成。

1.2高级到低级

我们的源代码由上图所示进行编译，预处理阶段是进行引用头文件，编译阶段是编译成汇编语言，文件后缀是.s，汇编阶段是编译成机器语言，这是最底层的语言，链接阶段，是将我们引用头文件中的函数进行调用。

在linux上我们在terminal中输入gcc -o file.c进行编译

1.3处理器读写并解释储存在内存中的指令

在UNIX系统上运行可执行文件，我们需要shell：shell是命令届时请，它输出提示符，我们输入命令，如果该命令行的第一个单词不是shell内置的命令，那么shell会认为这是个文件，运行后等待下一个指令的输入。

1.3.1系统的硬件

1.总线

总线是贯穿系统的一组电子管道，它可以用来携带信息字节，从而穿梭在各个部件之间串联起来整个系统。通常被设计成传送定长的字节块，我们成为字。字是一个参数，一般有32位和64位。

2、I/O设备

这是输入输出的设备每个设备都通过适配器或者控制器与总线相连。

适配器是一块插在主板上的卡，如显示屏。

控制器是I/O设备或者是系统主印制电路板（主板）上的芯片组。

3、主存

主存是临时储存设备，当CPU执行程序时，用来存放程序和程序处理数据，主存是由一组动态随机存取存储器DRAM芯片组成，每个字节上都有唯一的地址。

4、处理器

处理器就是cpu，是解释和存储在主存中的指令引擎，核心是寄存器，使其指向下一条指令，叫做pc，pc总指向某条机器语言的地址。

加载：由主存开始copy一个字节或一个字到寄存器，并覆盖寄存器内容

存储：从寄存器copy一个字节或一个字到主存，覆盖原来内容

操作：把两个寄存器的值copy到算数逻辑单元（ALU）中，ALU进行运算，并把结果给一个寄存器，覆盖其内容

跳转：从指令本身抽取一个字，并将该字copy到pc中，覆盖pc中的值

1.3.2运行程序

当我在shell中按下回车，代码被加载到主存，处理器执行程序机器语言，将字符串从主存复制到寄存器中，由寄存器在显示到显示设备中

1.4高速缓存

机械原理：较大存储设备要比较小存储设备运行的慢，而快速设备“造价”高，所以如何加快且消耗少。处理器存储信息少，速度fast，主存相反，我们采用高速缓存存储器，作为暂时集结区，比如cpu上L1高速缓存容量数万字节，访问速度和寄存器差不多，一个数百w的L2存储器通过总线连接到处理器，虽然L2不是那么fast，但仍比原来fast10倍。L1，L2是由静态随机访问存储器SRAM硬件技术实现，利用率高速缓存的局部性原理

1.5存储设备形成层次结构

上一级是下一级的高速缓存。

1.6操作系统功能

两个功能：1、防止硬件被失控的app滥用

2、向应用程序提供简单的机制来控制复杂且不同的低级硬件设备，操作系统通过抽象的概念实现功能

1.6.1进程

进程是操作系统对一个正在进行的程序的一种抽象，在一个系统上可以同时运行多个进程，而每个进程都在使用hardware，即我们的CPU是在不断进行交错执行，如下图。

操作系统保持跟踪进程运行所需的所有状态信息，这种状态称为上下文，切到另一个程序叫做上下文切换，保存上面进程恢复下面进程

一个进程转移另一个进程是由内核kernel管理的，shell是进程，但kernel并不是进程，他是系统管理全部进程所用代码和数据结构的集合

1.6.2线程

一般认为一个进程只有一个线程控制，但实际上一个进程由多个线程控制。

1.6.3虚拟内存

虚拟内存是个抽象概念，为每个进程提供给假象，，每个进程看到的内存都一样，成为虚拟地址空间

1.6.4文件

文件就是字节序列，所有的输入输出甚至设备都能看成文件。

1.7系统之间利用网络通信

如果将网络视为一个I/O设备，那么能得到下面的图片。

1.8.1Amdahl定律

1.8.2并发和并行

并发是指一个同时具有多个活动的系统

并行是指用并发使一个系统运行更快

1.线程级并发

使用线程我们能在一个进程中执行多个控制流

1.8.3指令级并行

如果cpu能达到比一个周期一条指令更快的执行速度，就称为超标量处理器。

1.8.4单指令、多数据并行

csapp-2：信息的表示和处理

2.1、信息存储

大多数计算器采用8位的块，或者字节，作为最小的可寻址的内存单位，而不是访问内存中单独的位。机器级程序将内存视为非常大的字节数组，成为虚拟内存。

程序对象：包括程序数据、指令和控制信息。

2.1.1、16进制表示法

二进制转换16进制，先分成4个一组，如果不足四个，最左侧可以不足4位前方补0，然后每4个转换成一个16进制数。

2.1.2、字数据大小

每个计算机都有一个字长，指明指针数据的标称大小，因为虚拟地址是以这一个字来编码的，字长决定系统参数也就是虚拟地址空间的最大大小

char虽然是单字节，但也能存储整数值，long在32位是4字节，在64是8字节，int32_t和int64_t分别是4和8字节，float是单精度，double是双精度，分别4字节和8字节

2.1.3、寻址和字节顺序

小端序和大端序：

通过实验我们知道，在linux 32、windows和linux 64用的都是小端序，sun用的是大端序

2.1.4、字符串

字符串在任何系统上都是一样的

2.1.5、代码

2.1.6、布尔代数

&：位上都是1才是1，其余是0

|：有1就是1，全0才是0

^：相同就是0

~：取反

2.1.7、c语言中的移位运算

向左移动x位，去掉前x位右边补0

向右移动分两种情况

加法的优先级高于移位，牵扯到移位要加括号

2.2、整数表示

2.2.1、整形数据类型

注意负数是比正数多一位的，因为有0.

2.2.2、无符号数的编码(B2U)

无符号数的编码是具有唯一性的，每一个二进制都完全等于一个整数，反过来同理。

2.2.3、补码编码（B2T)

表示负数，采用补码，当第一位是1，那么这个数就是负数，如果是0，那么这个表示正数

第一位是1，那么第1位就是负数，剩下的是整数相加

2.2.4、有符号数和无符号数转换

规则是，先把数据转换成二进制，如果是转换层无符号数，那么就按其标准转换，即不看第一位

如果是转换成有符号数，我们要考虑补码

2.2.5、c中的有符号和无符号数

创建无符号数必须要在字符后加‘u’或者’U’,其他声明都是有符号。当在运算时，一个是有符号，另一个没有符号，那么会强制把有符号转换成无符号，并假设两个数都是非负，在大于小于的比较中

2.2.6、拓展一个数字的位显示

将无符号数转换成一个更大的数据类型，我们只需要在开头加0，这叫做零拓展

前提是全部是有符号数

2.2.7、截断数字

截断无符号数：

留下后k位（k位截断数）

截断补码数：

2.3整数运算

从上述文字，我们知道，当x，y在定义域内，但x+y可不一定，若x+y溢出了区域，我们直接将二进制的第一位移除，或者用整数减去x定义域的最大值。判断是否溢出，用x+y是否小于x。

2.3.2、补码加法

与上面是一样的，如果超出则减去，低于则加上位数，即加法后的结果不能够超出本身的位数，否则截断！

2.3.3、补码的非

x=-（-x（非）+1）（负号）

2.3.4、无符号乘法

超出范围，用截断。

2.3.5、补码乘法

一样

2.3.6、乘常数

在位的模式下进行左移位，如果溢出，截断即可。乘法的使用代价是加法等的10倍

2.3.7、除以2的幂

除以2的幂我们需要将数据右移，无符号和补码数需要使用逻辑移位和算数移位来达到目的。

对于补码数，分为两种情况，若最高位0，即正数，直接移位，若是1，左侧补1，其他位右移即可。

如果用x/2**k,那么如果是小数,那么就向下取整

2.4 浮点数

2.4.1 二进制小数

上述例子很好的反映了什么是二进制小数.

2.4.2 IEEE浮点表示

简单来说就是,将一个数分为三段,先看第一个值判断是正数还是负数,第三个部分是从右侧开始的0一直到左侧不为0的数,剩余的为第二部分.

2.4.3 数字示例

2.4.4、舍入

有4种规则

2.4.5、c语言的浮点数

默认32位int

CSAPP-3

从这章开始，开始接触汇编和机器语言！这章比上一章看的舒服点。

3.1、程序编码

在linux系统编码c语言指令需要掌握：

1	linux> gcc -Og -o p p1.c

3.1.1、机器代码

程序计数器：通常称为P，在x86-64通常用%rip来表示。

整数寄存器文件包含16个命名的位置，分别存储64位的值

条件码寄存器保存最近执行的算数或者逻辑运算，如实现if或while语句

一组向量寄存器可存放一个或多个整数或浮点数

3.2数据格式

在intel中规定字代表16位，双字代表32位，四字代表64位

计算机永远是占用内存越小越好，比如一个数是int，只用不到4位，那么这个数就是按4个位算。用不到32位。

3.3、操作数

三种操作数：

1.立即数，用$555表示

2.寄存器，16位寄存器用低字节寄存器作为操作数

3.内存引用，用【】表示内存引用

这样的运算是需要掌握的

3.3.1、数据传送指令

mov指令，mov a，b：是将a传送到b。

我们把指令后的第一个数据称为源操作数，第二个数据为目的操作数，下面是5种用法

访问寄存器比访问内存快，所以一般将局部变量保存在寄存器中

3.3.2、压入和弹出栈数据

栈是一种数据结构，可以添加或者删除值，要遵循后进先出的原则，用push将数据压入栈中，用pop删除数据，存在属性：弹出之永远是最近被压入而且仍然在栈中的值。，永远记得这个只有一个操作数：

push %rbp完全等价于sub 8，%rsp mov %rbp，（%rsp），也就是说在push的时候就已经开辟了空间

3.4、算数和逻辑操作

add一样也是4个指令addb，addw，addl，addq

其中lea主要是加载地址，上述所有运算几乎都是将源操作数与目的操作数进行运算后存入目的操作数。

3.4.1、加载有效地址

lea目的操作数必须是一个寄存器

3.4.2、一元和二元操作数

这个操作数既是源操作数还是目的操作数，比如inc（%rsp）让栈顶+1，相当于++

二元操作，第二个操作数既是源又是目的，很像x-=y sub %rax,%rdx是让rdx-rax的值

3.4.3、移位操作

左移：sal，shl无差别

右移：sar（算数移位）shr（逻辑移位）

3.4.4、特殊算数操作

3.5、控制

3.5.1、条件码

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

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

SF：符号标志。最近的操作得到的结果为负数。

OF：溢出标志。最近的操作导致一个补码溢出–正溢出活着负溢出

比如test %rax，%rax就是检查%rax是负数，0，还是正数。

如cmp的比较可以确定范围从而进行循环

3.5.2、访问条件码

条件码使用三种方法：

1.可以根据条件码的某种组合，将一个字节设为0或者1

2.可以跳转到程序的其他部分

3.可以有条件的传送数据

3.5.3、跳转指令

jmp是无条件跳转

3.5.4、跳转编码

分为两种，最常用的是PC相对的，会将跳转指令的地址与紧邻在跳转指令后面的那条指令的差作为编码，还有一种是给出绝对地址，用4个字节直接跳转到目标地址

3.5.5、用条件控制来实现条件分支

类似于goto的写法，就是先对比，对比来决定是否goto

3.5.6、用条件传送来实现条件分支

上面用条件控制实现是非常低效的。我们这种方法是将两种结果都进行计算，然后再根据条件满足与否来选择结果

3.5.7、循环

上述是讲的if这样的判断，但其实循环跟上面的原理是差不多的

先看do-while

这个底层的逻辑跟上层逻辑是一样的，先do然后判断

while函数与do-while是不同的，先对while中的参数进行求值，然后根据条件码进行是否进入循环体的判断

当然还有第二种方法，称之为guard-do，先用条件分支，如果初始条件不成立就跳过循环，然后变成do-while循环

for循环程序先对第一个参数求值，然后进入循环，再循环中测试第二个参数，在判断是否进入第三个参数是否继续到循环里执行2，通过不同的优化等级，也有两种汇编来执行，不再赘述。

switch语句，switch可通过一个整数索引值进行多重分支，通过跳转表来实现，相当于跳转表是数组，然后那个整数值就是索引值

jmp指令的操作数前有*代表是见解跳转。rodata叫做只读数据。

3.6、过程

过程是一种抽象，提供一种封装代码方法，简单来说就是由一组参数经过过程来产生一个返回值过程有很多种：函数，方法，子过程，子例程，处理函数等

3.6.1、运行时栈

栈是后进先出的，在过程p调用q过程的时候：

在x86-64过程中，若需要的存储空间超过寄存器能存放的大小时，就会在栈上分配空间，这个过程叫栈帧

一般的在过程中超过6个参数就需要栈了

3.6.2、转移控制

将控制从p转移到q只需要将PC设置成q代码起始地址，但仍要记得p当前指令地址

3.6.3、数据传送

传入参数不一定一定用r开头寄存器，可以根据传入参数位数选择寄存器，数据传送讲的就是6个以上参数，从第七开始会转移到栈上

3.6.4、栈上的局部存储

有几种情况局部内存必须放在内存中：
寄存器不足够存放所有本地数据

对一个局部变量使用地址运算符‘&’，因此必须要有地址

某些局部变量是数组或者结构，因此必须能够通过数组或结构引用访问

3.6.5、寄存器中的局部存储空间

寄存器是唯一被所有过程共享的资源，过程中的被调用者不会覆盖调用者稍后会使用寄存器

3.7、数组分配和访问

3.7.1、基本原则

3.7.2、指针运算

&和*可以产生和间接引用指针，我们要知道的就是下面这个表

3.7.3、嵌套的数组

对于二维数组

上面数组的以下面来解释：

我们从汇编求出来C就是列，L就是T的字节大小

3.7.4、定长数组

3.7.5、变长数组

3.8、异质的数据结构

主要介绍struct和union

3.8.1、结构

struct将不同类型的对象聚合到一个对象中，类似数组，一幅图直接理解

3.8.2、联合

一个联合总的大小等于它最大字段的大小，总之联合可以带来的节省很小

3.8.3、数据对齐

主要就是一个处理器要是从内存取8字节，那么地址必须是8的倍数

3.9、安全漏洞

3.9.1、gdb操作

3.9.2、内存越界和缓冲区溢出

这是pwn里的攻击方法,比如gets来输入字符串，超出输入范围那么就叫缓冲区溢出，当字符串边长，就会覆盖栈上存储的某些信息，比如未被使用的栈空间，返回地址，caller里保存的状态。。。当返回被破坏，那么我们完全可以ret到我们想要的地方，比如shell中

3.9.3、对抗缓冲区溢出

比如我们会在文件中加入防护措施。

1、栈随机化也叫ALSR

这个很常见，原理：在程序开始时，在栈上分配一段0~n字节的随机大小空间，程序不需要这段空间，所以每次栈空间都是随机的。

2、栈破坏检测也叫canary

我们尝试在数组即将越界时检测到它，其思想是在栈帧任何局部缓冲区与栈状态之间存储一个特殊的canary值，这个值随机产生，这个值是只读。

如果存贮值与canary值相同异或就为0，那么程序继续

3、限制可执行代码区域NX

这一招是消除攻击者插入代码的权力，只有保存在编译器产生的代码的那部分内存才是可执行的，其余只能读和写。

3.9.4、支持变长栈帧

%rbp作为帧指针，或者叫做基地址.

3.10、浮点代码

处理器的浮点体系结构包括多个方面：

如何存储和访问浮点数值。通常是通过某种寄存器方式完成

对浮点数据操作的指令

向函数传递浮点数参数和从函数返回浮点数结果的规则

函数调用过程中保存寄存器的规则：一些寄存器被指定为调用者保存，而其他的被指定为被调用者保存

历史问题：

3.10.1、浮点传送和转换操作

若把浮点数转换成整数时，指令进行截断，向0舍入。

上面忽略第二个操作数，因为他只会影响结果的高位字节，一半第二个操作数跟目的操作数是一样的。

vunpcklps通常交叉放置来自两个xmm寄存器的值，储存在第三个寄存器

3.10.2、过程中的浮点代码

过程：xmm寄存器用来向函数传参，然后返回值

若函数包含指针，整数和浮点数混合参数时，指针和整数通过寄存器传递，而浮点值通过xmm寄存器传递

3.10.3、浮点数运算操作

第一个源操作数可以是一个xmm寄存器或内存位置，第二个源操作数和目的操作数必须是xmm寄存器。每个操作都有一条针对单精度的指令和一条针对双精度的指令，结果存放在目的寄存器。

3.10.4、定义和使用浮点数

与整数操作不同，AVX浮点操作不能以立即数作为操作数。

3.10.5、在浮点代码中使用位级操作

3.10.6、浮点比较操作

类似于cmp指令

也有三个条件码

结束：

这篇学到了很多汇编知识，理解了底层的逻辑。

收获很多，继续加油！

CSAPP-LAB

DataLab

我只能说，太难想了。

/*

 * 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 if the shift amount
       is less than 0 or greater than 31.


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 implement 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 can use any arithmetic,
logical, or comparison operations on int or unsigned data.

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 operations (integer, logical,
       or comparison) that you are allowed to use for your implementation
       of the function.  The max operator count is checked by dlc.
       Note that assignment ('=') 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
//1
/* 

 * bitXor - x^y using only ~ and & 
 * Example: bitXor(4, 5) = 1
 * Legal ops: ~ &
 * Max ops: 14
 * Rating: 1
    */
   int bitXor(int x, int y) {

  return (~((~x) & (~y))) & (~(x & y));//int是4位，~4就是-5，前面的操作得到0b0101，我们只需0b1011即可，后面构造出来
}
/* 

 * tmin - return minimum two's complement integer 
 * Legal ops: ! ~ & ^ | + << >>
 * Max ops: 4
 * Rating: 1
    */
   int tmin(void) {

  return 0x80 << 24;//0x80 == 0b1000 0000

}
//2
/*

 * isTmax - returns 1 if x is the maximum, two's complement number,
 * and 0 otherwise 
 * Legal ops: ! ~ & ^ | +
 * Max ops: 10
 * Rating: 1
    */
   int isTmax(int x) {
     int i = x + 1;/*我们知道最大值+1就越界了，其实会等于最小值*/
     x = x + i;/*最大值加最小值= -1 ，即0xffff ffff*/
     x = ~x;/*因为0xffff ffff是全1，取反就是0*/
     i = !i;//针对x=-1的情况进行再次运算！
     x = x + 1;
     return !x;
   }
   /* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 * where bits are numbered from 0 (least significant) to 31 (most significant)
 * Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 * Legal ops: ! ~ & ^ | + << >>
 * Max ops: 12
 * Rating: 2
    */
   int allOddBits(int x)////如果x奇数位全为1，返回1;否则返回0
   {
     return !((~x) & 0XAAAAAAAA);//0XAAAAAAAA就是奇数位是1
     //若x奇数位上全是1，~x奇数位上全是0，(~X) & 0XAAAAAAAA则奇数位全是0，取！则为1
     //若x奇数位不全为1，~x总有奇数位为0，(~X) & 0XAAAAAAAA一定不为0，取！则为0。
   }
   /* 
 * negate - return -x 
 * Example: negate(1) = -1.
 * Legal ops: ! ~ & ^ | + << >>
 * Max ops: 5
 * Rating: 2
    */
   int negate(int x) //求x的相反数,我们知道~x + x = -1
   {
     return (~x + 1);
   }
   //3
   /* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 * Example: isAsciiDigit(0x35) = 1.
 * isAsciiDigit(0x3a) = 0.
 * isAsciiDigit(0x05) = 0.
 * Legal ops: ! ~ & ^ | + << >>
 * Max ops: 15
 * Rating: 3
    */
   int isAsciiDigit(int x) //计算输入值是否是数字 0-9 的 ASCII 值
   {
     return (!(x + ((~0x30) + 1)) >> 31) & ((x + ((~0x3a) + 1)) >> 31);//这个可以利用上面的求相反数来写，我们主要是拿x来与0~9的比较大小
     // ((~0x30) + 1))是求0x30的相反数，然后用x-0x30，再右移31位取符号位，如果符号位是1，则是负数。
   }
   /* 
 * conditional - same as x ? y : z 
 * Example: conditional(2,4,5) = 4
 * Legal ops: ! ~ & ^ | + << >>
 * Max ops: 16
 * Rating: 3
    */
   int conditional(int x, int y, int z) ////x为0返回z;否则返回y
   {
     int mask;
     mask = (!x + (~1) + 1);
     return (mask & y) | (~mask & z);
     //mask=(!x + (~1) + 1)，求的是！x-1，要么等于0，要么等于-1，等于-1就可以用补码！
   }
   /* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 * Example: isLessOrEqual(4,5) = 1.
 * Legal ops: ! ~ & ^ | + << >>
 * Max ops: 24
 * Rating: 3
    */
   int isLessOrEqual(int x, int y) ////x<=y返回1，否则返回0
   {
     int negX = ~x + 1;//求-x
     int addX = negX + y;//y-x，要和0，1比
     int checksign = (addX >> 31) &1;//看符号位
     int leftBit = 1 << 31;
     int xLeft = x & leftBit;//求x的符号
     int yLeft = y & leftBit;//求y的符号
     int bitXor = xLeft ^ yLeft;//x和y符号相同标志位，相同为0不同为1
     bitXor = (bitXor >> 31) & 1;//符号相同标志位格式化为0或1
     return ((!bitXor) & (!checksign)) | (bitXor & (xLeft >> 31)); //返回1有两种情况：符号相同标志位为0（相同）位与 y-x 的符号为0（y-x>=0）结果为1；符号相同标志位为1（不同）位与x的符号位为1（x<0）
   }//bitXor是判断x，y是否是同号。
   //4
   /* 
 * logicalNeg - implement the ! operator, using all of 
 * the legal operators except !
 * Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 * Legal ops: ~ & ^ | + << >>
 * Max ops: 12
 * Rating: 4 
    */
   int logicalNeg(int x)  //不用!的条件下实现!运算
   {
     return ((~x & ~(~x + 1)) >> 31) & 1;//(~x & ~(~x + 1))这个当x=0这个值就是1，当x为最小值，这个为0，其他情况，x和-x符号不同，所以等于0.
   }
   /* howManyBits - return the minimum number of bits required to represent x in
 * two's complement
 * Examples: howManyBits(12) = 5
 * howManyBits(298) = 10
 * howManyBits(-5) = 4
 * howManyBits(0)  = 1
 * howManyBits(-1) = 1
 * howManyBits(0x80000000) = 32
 * Legal ops: ! ~ & ^ | + << >>
 * Max ops: 90
 * Rating: 4
   */
   int howManyBits(int x) //一个数用补码表示最少需要几位？*******
   {
     int b16,b8,b4,b2,b1,b0;
     int sign = x >> 31;
     x = (sign & ~x) | (~sign & x);//如果x为正则不变，否则按位取反（这样好找最高位为1的，原来是最高位为0的，这样也将符号位去掉了）
     b16 = !!(x >> 16) << 4;//高十六位是否有1
     x = x >> b16;          //如果有（至少需要16位），则将原数右移16位
     b8 = !!(x >> 8) << 3;  //剩余位高8位是否有1
     x = x >> b8;           //如果有（至少需要16+8=24位），则右移8位
     b4 = !!(x >> 4) << 2;
     x = x >> b4;
     b2 = !!(x >> 2) << 1;
     x = x >> b2;
     b1 = !!(x >> 1);
     x = x >> b1;
     b0 = x;
     return b16 + b8 + b4 + b2 + b1 + b0 + 1;
   }
   //float
   /* 
 * floatScale2 - 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 floatScale2(unsigned uf) //求2乘一个浮点数 ******
   {
     int exp_ = (uf & 0x7f800000) >> 23;
     int s_ = uf & 0x80000000;
     if (exp_ == 0)
   return (uf << 1) | s_;
     if (exp_ == 255)
   return uf;
     ++exp_;
     if (exp_ == 255)
   return 0x7f800000 | s_;
     return (uf & 0x807fffff) | (exp_ << 23);
   }
   /* 
 * floatFloat2Int - 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 floatFloat2Int(unsigned uf)//将浮点数转换为有符号整数，float_f2i
   {
     int s_ = uf >> 31;
     int exp_ = ((uf & 0x7f800000) >> 23) - 127;
     int frac_ = (uf & 0x007fffff) | 0x00800000;
     if (!(uf & 0x7fffffff))
   return 0;

  if (exp_ > 31)
    return 0x80000000;
  if (exp_ < 0)
    return 0;

  if (exp_ > 23)
    frac_ <<= (exp_ - 23);
  else
    frac_ >>= (23 - exp_);

  if (!((frac_ >> 31) ^ s_))
    return frac_;
  else if (frac_ >> 31)
    return 0x80000000;
  else
    return ~frac_ + 1;
}
/* 

 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 * (2.0 raised to the power x) for any 32-bit integer x.
    *
 * The unsigned value that is returned should have the identical bit
 * representation as the single-precision floating-point number 2.0^x.
 * If the result is too small to be represented as a denorm, return
 * 0. If too large, return +INF.
 * 
 * Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 * Max ops: 30 
 * Rating: 4
    */
   unsigned floatPower2(int x) //计算浮点数2.0^x
   {
     if (x < -127)
   return 0;
     if (x > 128)
   return 0x7f800000;
     x += 127;
     x = x << 23;
     return x;
   }

Bomb Lab

在gdb中进行反汇编调试，输入disas phase_1，出来第一关：

Dump of assembler code for function phase_1:
   0x0000000000400ee0 <+0>:     sub    rsp,0x8//开辟0x8的空间
   0x0000000000400ee4 <+4>:     mov    esi,0x402400//将0x402400存到esi中，里面可能会有字符串
   0x0000000000400ee9 <+9>:     call   0x401338 <strings_not_equal>//这个函数可能是对比函数
   0x0000000000400eee <+14>:    test   eax,eax//对比
   0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>//如果eax=0，则进入phase2；否则爆炸
   0x0000000000400ef2 <+18>:    call   0x40143a <explode_bomb>
   0x0000000000400ef7 <+23>:    add    rsp,0x8//返回0x8大小的内存
   0x0000000000400efb <+27>:    ret

用ida看的话更清楚，就是一个对比函数：

拿下！

Dump of assembler code for function phase_2:
   0x0000000000400efc <+0>:     push   rbp
   0x0000000000400efd <+1>:     push   rbx
   0x0000000000400efe <+2>:     sub    rsp,0x28//开辟0x28空间
   0x0000000000400f02 <+6>:     mov    rsi,rsp
   0x0000000000400f05 <+9>:     call   0x40145c <read_six_numbers>//输入6个数
   0x0000000000400f0a <+14>:    cmp    DWORD PTR [rsp],0x1//与1对比
   0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>
   0x0000000000400f10 <+20>:    call   0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:    jmp    0x400f30 <phase_2+52>//跳转到phase3
   0x0000000000400f17 <+27>:    mov    eax,DWORD PTR [rbx-0x4]
   0x0000000000400f1a <+30>:    add    eax,eax//eax += eax
   0x0000000000400f1c <+32>:    cmp    DWORD PTR [rbx],eax
   0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:    call   0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:    add    rbx,0x4//rbx+4这个地址在循环
   0x0000000000400f29 <+45>:    cmp    rbx,rbp//对比rbx。rbp
   0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>//进入循环
   0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:    lea    rbx,[rsp+0x4]
   0x0000000000400f35 <+57>:    lea    rbp,[rsp+0x18]
   0x0000000000400f3a <+62>:    jmp    0x400f17 <phase_2+27>
   0x0000000000400f3c <+64>:    add    rsp,0x28
   0x0000000000400f40 <+68>:    pop    rbx
   0x0000000000400f41 <+69>:    pop    rbp
   0x0000000000400f42 <+70>:    ret
End of assembler dump.

那么很清楚了，我们这个循环做的操作就是让eax*2，那么找到第一个值就行了，我们用ida反编译

所以6个数是1，2，4，8，16，32

Dump of assembler code for function phase_3:
   0x0000000000400f43 <+0>:     sub    rsp,0x18//开辟0x18空间
   0x0000000000400f47 <+4>:     lea    rcx,[rsp+0xc]//将[rsp+0xc]的值存在rcx寄存器
   0x0000000000400f4c <+9>:     lea    rdx,[rsp+0x8]
   0x0000000000400f51 <+14>:    mov    esi,0x4025cf//esi寄存器的值为0x4025cf
   0x0000000000400f56 <+19>:    mov    eax,0x0
   0x0000000000400f5b <+24>:    call   0x400bf0 <__isoc99_sscanf@plt>//scanf
   0x0000000000400f60 <+29>:    cmp    eax,0x1
   0x0000000000400f63 <+32>:    jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:    call   0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:    cmp    DWORD PTR [rsp+0x8],0x7
   0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>
   0x0000000000400f71 <+46>:    mov    eax,DWORD PTR [rsp+0x8]
   0x0000000000400f75 <+50>:    jmp    QWORD PTR [rax*8+0x402470]
   0x0000000000400f7c <+57>:    mov    eax,0xcf
   0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:    mov    eax,0x2c3
   0x0000000000400f88 <+69>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f8a <+71>:    mov    eax,0x100
   0x0000000000400f8f <+76>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f91 <+78>:    mov    eax,0x185
   0x0000000000400f96 <+83>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f98 <+85>:    mov    eax,0xce
   0x0000000000400f9d <+90>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f9f <+92>:    mov    eax,0x2aa
   0x0000000000400fa4 <+97>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400fa6 <+99>:    mov    eax,0x147
   0x0000000000400fab <+104>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fad <+106>:   call   0x40143a <explode_bomb>
   0x0000000000400fb2 <+111>:   mov    eax,0x0
   0x0000000000400fb7 <+116>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fb9 <+118>:   mov    eax,0x137
   0x0000000000400fbe <+123>:   cmp    eax,DWORD PTR [rsp+0xc]
   0x0000000000400fc2 <+127>:   je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>:   call   0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>:   add    rsp,0x18
   0x0000000000400fcd <+138>:   ret
End of assembler dump.

我认为这个不太好看出来，下面是关键

1 2	0x0000000000400f6a <+39>: cmp DWORD PTR [rsp+0x8],0x7 0x0000000000400f6f <+44>: ja 0x400fad <phase_3+106>

ja是大于则跳转，跳转就爆炸了，所以不能大于7，给了我们许多选择，我们选0-7都行，第二个数就对应switch上的另一个值，用ida更好看出！

我选2，就必须对应707。

Dump of assembler code for function phase_4:
   0x000000000040100c <+0>:     sub    rsp,0x18//开辟空间
   0x0000000000401010 <+4>:     lea    rcx,[rsp+0xc]
   0x0000000000401015 <+9>:     lea    rdx,[rsp+0x8]
   0x000000000040101a <+14>:    mov    esi,0x4025cf
   0x000000000040101f <+19>:    mov    eax,0x0
   0x0000000000401024 <+24>:    call   0x400bf0 <__isoc99_sscanf@plt>//输入两个值
   0x0000000000401029 <+29>:    cmp    eax,0x2
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
   0x000000000040102e <+34>:    cmp    DWORD PTR [rsp+0x8],0xe
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>
   0x0000000000401035 <+41>:    call   0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    edx,0xe
   0x000000000040103f <+51>:    mov    esi,0x0
   0x0000000000401044 <+56>:    mov    edi,DWORD PTR [rsp+0x8]
   0x0000000000401048 <+60>:    call   0x400fce <func4>
   0x000000000040104d <+65>:    test   eax,eax
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
   0x0000000000401051 <+69>:    cmp    DWORD PTR [rsp+0xc],0x0
   0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>
   0x0000000000401058 <+76>:    call   0x40143a <explode_bomb>
   0x000000000040105d <+81>:    add    rsp,0x18
   0x0000000000401061 <+85>:    ret
End of assembler dump.

jbe小于等于则跳转，所以eax要≤ 14，第一个参数要≤ 14

接下来第二个参数要看func4

Dump of assembler code for function func4:
   0x0000000000400fce <+0>:     sub    rsp,0x8
   0x0000000000400fd2 <+4>:     mov    eax,edx
   0x0000000000400fd4 <+6>:     sub    eax,esi
   0x0000000000400fd6 <+8>:     mov    ecx,eax
   0x0000000000400fd8 <+10>:    shr    ecx,0x1f
   0x0000000000400fdb <+13>:    add    eax,ecx
   0x0000000000400fdd <+15>:    sar    eax,1
   0x0000000000400fdf <+17>:    lea    ecx,[rax+rsi*1]
   0x0000000000400fe2 <+20>:    cmp    ecx,edi
   0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36>
   0x0000000000400fe6 <+24>:    lea    edx,[rcx-0x1]
   0x0000000000400fe9 <+27>:    call   0x400fce <func4>
   0x0000000000400fee <+32>:    add    eax,eax
   0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
   0x0000000000400ff2 <+36>:    mov    eax,0x0
   0x0000000000400ff7 <+41>:    cmp    ecx,edi
   0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57>
   0x0000000000400ffb <+45>:    lea    esi,[rcx+0x1]
   0x0000000000400ffe <+48>:    call   0x400fce <func4>
   0x0000000000401003 <+53>:    lea    eax,[rax+rax*1+0x1]
   0x0000000000401007 <+57>:    add    rsp,0x8
   0x000000000040100b <+61>:    ret
End of assembler dump.

func4()函数的返回值(保存在寄存器eax中), 如果eax不是0的话, 则会跳转到引爆炸弹的地方. 因此函数func4()返回值eax必须是0

很明显，在我们选择第二个参数时，我们如果让第二个参数=0，那么这些问题顺利解决，因为在func4函数中没有v3==0这个选项，当a1=7，a2=0时非常完美的做到了上述一切。

Dump of assembler code for function phase_5:
   0x0000000000401062 <+0>:     push   rbx
   0x0000000000401063 <+1>:     sub    rsp,0x20
   0x0000000000401067 <+5>:     mov    rbx,rdi
   0x000000000040106a <+8>:     mov    rax,QWORD PTR fs:0x28
   0x0000000000401073 <+17>:    mov    QWORD PTR [rsp+0x18],rax
   0x0000000000401078 <+22>:    xor    eax,eax
   0x000000000040107a <+24>:    call   0x40131b <string_length>
   0x000000000040107f <+29>:    cmp    eax,0x6//flag长度为6
   0x0000000000401082 <+32>:    je     0x4010d2 <phase_5+112>
   0x0000000000401084 <+34>:    call   0x40143a <explode_bomb>
   0x0000000000401089 <+39>:    jmp    0x4010d2 <phase_5+112>
   0x000000000040108b <+41>:    movzx  ecx,BYTE PTR [rbx+rax*1]
   0x000000000040108f <+45>:    mov    BYTE PTR [rsp],cl
   0x0000000000401092 <+48>:    mov    rdx,QWORD PTR [rsp]
   0x0000000000401096 <+52>:    and    edx,0xf
   0x0000000000401099 <+55>:    movzx  edx,BYTE PTR [rdx+0x4024b0]
   0x00000000004010a0 <+62>:    mov    BYTE PTR [rsp+rax*1+0x10],dl
   0x00000000004010a4 <+66>:    add    rax,0x1
   0x00000000004010a8 <+70>:    cmp    rax,0x6
   0x00000000004010ac <+74>:    jne    0x40108b <phase_5+41>
   0x00000000004010ae <+76>:    mov    BYTE PTR [rsp+0x16],0x0
   0x00000000004010b3 <+81>:    mov    esi,0x40245e
   0x00000000004010b8 <+86>:    lea    rdi,[rsp+0x10]
   0x00000000004010bd <+91>:    call   0x401338 <strings_not_equal>
   0x00000000004010c2 <+96>:    test   eax,eax
   0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>
   0x00000000004010c6 <+100>:   call   0x40143a <explode_bomb>
   0x00000000004010cb <+105>:   nop    DWORD PTR [rax+rax*1+0x0]
   0x00000000004010d0 <+110>:   jmp    0x4010d9 <phase_5+119>
   0x00000000004010d2 <+112>:   mov    eax,0x0
   0x00000000004010d7 <+117>:   jmp    0x40108b <phase_5+41>
   0x00000000004010d9 <+119>:   mov    rax,QWORD PTR [rsp+0x18]
   0x00000000004010de <+124>:   xor    rax,QWORD PTR fs:0x28
   0x00000000004010e7 <+133>:   je     0x4010ee <phase_5+140>
   0x00000000004010e9 <+135>:   call   0x400b30 <__stack_chk_fail@plt>
   0x00000000004010ee <+140>:   add    rsp,0x20
   0x00000000004010f2 <+144>:   pop    rbx
   0x00000000004010f3 <+145>:   ret
End of assembler dump.

属实不想看汇编了，直接ida搞了。

unsigned __int64 __fastcall phase_5(__int64 a1)
{
  __int64 i; // rax
  char v3[8]; // [rsp+10h] [rbp-18h] BYREF
  unsigned __int64 v4; // [rsp+18h] [rbp-10h]

  v4 = __readfsqword(0x28u);
  if ( (unsigned int)string_length(a1) != 6 )
    explode_bomb();
  for ( i = 0LL; i != 6; ++i )
    v3[i] = array_3449[*(_BYTE *)(a1 + i) & 0xF];
  v3[6] = 0;
  if ( (unsigned int)strings_not_equal(v3, "flyers") )
    explode_bomb();
  return __readfsqword(0x28u) ^ v4;
}

也就爆破一下就行了

flag = ""
a = "maduiersnfotvbyl"
b = "flyers"
for i in range(6):
    for j in range(65,127):
        c = ord(a[(j) & 0xf])
        if c == ord(b[i]):
            flag += chr(j)
            break
print(flag)
#IONEFG

成功！最后一关！

Dump of assembler code for function phase_6:
   0x00000000004010f4 <+0>:     push   r14
   0x00000000004010f6 <+2>:     push   r13
   0x00000000004010f8 <+4>:     push   r12
   0x00000000004010fa <+6>:     push   rbp
   0x00000000004010fb <+7>:     push   rbx
   0x00000000004010fc <+8>:     sub    rsp,0x50
   0x0000000000401100 <+12>:    mov    r13,rsp
   0x0000000000401103 <+15>:    mov    rsi,rsp
   0x0000000000401106 <+18>:    call   0x40145c <read_six_numbers>//读入6个数字
   0x000000000040110b <+23>:    mov    r14,rsp
   0x000000000040110e <+26>:    mov    r12d,0x0
   0x0000000000401114 <+32>:    mov    rbp,r13//rsp赋值给rbp
   0x0000000000401117 <+35>:    mov    eax,DWORD PTR [r13+0x0]//取第一个参数
   0x000000000040111b <+39>:    sub    eax,0x1//参数1-1
   0x000000000040111e <+42>:    cmp    eax,0x5//参数1-1 =< 5，所以参数一小于6
   0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52>
   0x0000000000401123 <+47>:    call   0x40143a <explode_bomb>
   0x0000000000401128 <+52>:    add    r12d,0x1//r12控制循环次数
   0x000000000040112c <+56>:    cmp    r12d,0x6
   0x0000000000401130 <+60>:    je     0x401153 <phase_6+95>
   0x0000000000401132 <+62>:    mov    ebx,r12d
   0x0000000000401135 <+65>:    movsxd rax,ebx
   0x0000000000401138 <+68>:    mov    eax,DWORD PTR [rsp+rax*4]//这个循环是使后面的参数不能等于参数1
   0x000000000040113b <+71>:    cmp    DWORD PTR [rbp+0x0],eax
   0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>
   0x0000000000401140 <+76>:    call   0x40143a <explode_bomb>
   0x0000000000401145 <+81>:    add    ebx,0x1//又是循环
   0x0000000000401148 <+84>:    cmp    ebx,0x5
   0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>
   0x000000000040114d <+89>:    add    r13,0x4//参数2
   0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32>
   0x0000000000401153 <+95>:    lea    rsi,[rsp+0x18]//这个是'\0'
   0x0000000000401158 <+100>:   mov    rax,r14
   0x000000000040115b <+103>:   mov    ecx,0x7//ecx永远是7
   0x0000000000401160 <+108>:   mov    edx,ecx
   0x0000000000401162 <+110>:   sub    edx,DWORD PTR [rax]//7-当前参数
   0x0000000000401164 <+112>:   mov    DWORD PTR [rax],edx
   0x0000000000401166 <+114>:   add    rax,0x4//地址+4，即下一个参数
   0x000000000040116a <+118>:   cmp    rax,rsi
   0x000000000040116d <+121>:   jne    0x401160 <phase_6+108>
   0x000000000040116f <+123>:   mov    esi,0x0
   0x0000000000401174 <+128>:   jmp    0x401197 <phase_6+163>
   0x0000000000401176 <+130>:   mov    rdx,QWORD PTR [rdx+0x8]//rdx是node1
   0x000000000040117a <+134>:   add    eax,0x1//内层循环
   0x000000000040117d <+137>:   cmp    eax,ecx
   0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>
   0x0000000000401181 <+141>:   jmp    0x401188 <phase_6+148>
   0x0000000000401183 <+143>:   mov    edx,0x6032d0//链表处
   0x0000000000401188 <+148>:   mov    QWORD PTR [rsp+rsi*2+0x20],rdx
   0x000000000040118d <+153>:   add    rsi,0x4//每次加4的进行循环到0x18循环结束
   0x0000000000401191 <+157>:   cmp    rsi,0x18
   0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183>
   0x0000000000401197 <+163>:   mov    ecx,DWORD PTR [rsp+rsi*1]
   0x000000000040119a <+166>:   cmp    ecx,0x1
   0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>
   0x000000000040119f <+171>:   mov    eax,0x1
   0x00000000004011a4 <+176>:   mov    edx,0x6032d0
   0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>
   0x00000000004011ab <+183>:   mov    rbx,QWORD PTR [rsp+0x20]//指针数组存在rsp中
   0x00000000004011b0 <+188>:   lea    rax,[rsp+0x28]
   0x00000000004011b5 <+193>:   lea    rsi,[rsp+0x50]
   0x00000000004011ba <+198>:   mov    rcx,rbx
   0x00000000004011bd <+201>:   mov    rdx,QWORD PTR [rax]
   0x00000000004011c0 <+204>:   mov    QWORD PTR [rcx+0x8],rdx
   0x00000000004011c4 <+208>:   add    rax,0x8
   0x00000000004011c8 <+212>:   cmp    rax,rsi
   0x00000000004011cb <+215>:   je     0x4011d2 <phase_6+222>
   0x00000000004011cd <+217>:   mov    rcx,rdx
   0x00000000004011d0 <+220>:   jmp    0x4011bd <phase_6+201>
   0x00000000004011d2 <+222>:   mov    QWORD PTR [rdx+0x8],0x0
   0x00000000004011da <+230>:   mov    ebp,0x5
   0x00000000004011df <+235>:   mov    rax,QWORD PTR [rbx+0x8]
   0x00000000004011e3 <+239>:   mov    eax,DWORD PTR [rax]
   0x00000000004011e5 <+241>:   cmp    DWORD PTR [rbx],eax
   0x00000000004011e7 <+243>:   jge    0x4011ee <phase_6+250>//参数1>参数2
   0x00000000004011e9 <+245>:   call   0x40143a <explode_bomb>
   0x00000000004011ee <+250>:   mov    rbx,QWORD PTR [rbx+0x8]
   0x00000000004011f2 <+254>:   sub    ebp,0x1
   0x00000000004011f5 <+257>:   jne    0x4011df <phase_6+235>
   0x00000000004011f7 <+259>:   add    rsp,0x50
   0x00000000004011fb <+263>:   pop    rbx
   0x00000000004011fc <+264>:   pop    rbp
   0x00000000004011fd <+265>:   pop    r12
   0x00000000004011ff <+267>:   pop    r13
   0x0000000000401201 <+269>:   pop    r14
   0x0000000000401203 <+271>:   ret
End of assembler dump.

在read_six_numbers函数中我们看出用rsp开辟了0x18空间，所以输入数在rsp中

我们发现这个就是对链表进行升序排序:{14C,1,A8,2,39C,3,2B3,4,1DD,5,1BB,6}

所以答案是；4 3 2 1 6 5

起飞！！！这个比datalab好玩多了

CSAPP-7-END

链接

链接时将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可以被加载到内存并执行。链接可以执行于编译时，也可以执行与加载时，甚至可以执行于运行时。在现代系统中，链接是由链接器程序自动执行。

链接可以是软件开发中分离编译

7.1、编译器驱动程序

main.c执行过程：先通过c预处理器，成为ascii码编写的main.i程序，接下来由c编译器将其编为ascii汇编语言文件main.s，然后汇编器将其变成可重定位目标文件main.o，如果需要链接，最后运行链接器ld，将必要文件链接，成为可执行文件，在shell里运行需要调用loader即加载器。

7.2、静态链接

链接器的两大任务：

符号解析。目标文件定义和引用符号，每个符号对应于1个函数，一个全局变量或者一个静态变量，其目的就是为了将每个符号引用正好和一个符号定义关联起来。

重定位。编译器和汇编器生成从0开始的代码和数据节。链接器通过把每个符号定位于一个内存位置关联起来，从而重定位这些节，再修改符号引用，使得他们指向这个内存位置。

7.3、目标文件

三种文件：

可重定位目标文件：含二进制代码和数据，其形式能于其他可重定位目标文件合并起来。

可执行文件：包含二进制和数据，其形式可以直接复制到内存中并执行

共享目标文件：一种特殊的可重定位目标文件，可在加载或者运行时被动态的加载进内存并链接

目标文件就是以文件形式存放再磁盘中的目标模块，而目标模块时一个字节序列

7.4、可重定位目标文件

7.5、符号和符号表

每个重定位的目标模块都存在一个符号表,其包括m定义和引用符号的消息.在链接器的上下文,存在三种符号

由m定义并能被其他模块引用的全局符号.全局链接器符号对应于非静态的c函数和全局变量

由其他模块定义并被m引用的全局符号.这些符号叫外部符号,对应其他模块中定义的非静态c函数和全局变量

只被模块m定义和引用的局部符号,他们对应于带static的c函数和全局变量.这些符号全局可见,但不可引用

本地链接器符号和本地程序变量不同

.symtab中的符号表不包括对应于本地非静态程序变量的任何符号,这些符号是在栈中管理的,也就是局部变量

static的变量在.data或者.bss中为其分配空间

name是字符串表的字节偏移,指向符号以null结尾的字符串名字.value是符号地址,size是目标大小,type通常是数据或函数,blinging表明是全局还是本地。

每个符号都被分配到某个节,由section字段表示。

7.6、符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。

对于全局符号解析采用假设法,如果不是就终止。

重载:对于一些方法在源代码中有相同的名字,却有不同参数列表,c++和java使用重载函数.,是因为编译器将每一个唯一的方法和参数列表组合编码成一个,对链接器来说是唯一的名字,这就是重载,相反的过程叫恢复。

7.6.1、链接器如何解析多重定义的全局变量

多个模块定义同名的全局符号:

首先分为强和弱,函数和已初始化的变量是强符号,未初始化的全局变量是弱符号。

有三个规则,不允许有多个同名的强符号,如果有一个强符号与多个弱符号同名,选择强符号,如果有多个弱符号同名,任选一个。

7.6.2、与静态库链接

所有编译系统提供机制：将所有相关的目标模块打包成为一个单独的文件，成为静态库，可作为链接库的输入。这样的操作减少内存的使用或者减少操作每个函数的重复性，直接调用库函数就解决问题了。

7.6.3、链接器如何使用静态库来解析引用

在linux链接器及逆行符号解析阶段时，链接器从左到右扫描命令行出现顺序的可重定位目标文件和存档文件。在这当中链接器维护一个可重定位目标文件的集合E（被认为是可执行文件），一个违背解析符号的集合U（被引用但未被定义的符号），以及一个在前面输入文件已定义的符号集合D。

对于命令行上的输入文件，如果是目标文件f，链接器把f添加到E，修改U和D来反映f中的符号定义和引用，并继续下一个输入文件。

如果是存档文件，那么链接器久长时匹配U中未解析的符号和有存档文件成员定义的符号，对于其中成员m，定义一个符号解析U中的一个引用，将m加入E，修改U和D来反映m中的符号定义和引用。当U和D都不变,不再在E中包含的成员，都被丢弃，输入下个文件。

如果扫描后U非空，直接输出错误，否则U会和重定位E中的目标文件，构建输出的可执行文件、

7.7、重定位

链接器完成符号解析后，就把代码中的每个符号引用和正好一个符号定义关联起来，此时，链接器直到目标module中代码节和data节大小，就可以重定位了：

1.重定位和符号定义。链接器将相同类型的节合并成同一类型的聚合节，比如.data节合成一个.data节，这就成为了可执行文件的.data节，然后链接器将运行时内存地址付给新的聚合节，赋给输入模块定义的每个节以及符号，完成时，程序每条指令和全局变量都有唯一的运行时内存地址

2.重定位节的符号引用。链接器修改代码节和数据节中对每个符号的引用，使得她们指向正确的运行时地址，这一步依赖于可重定位目标模块中成为重定位条目的数据结构

7.7.1、重定位条目

重定位条目会告诉链接器在将目标文件合并成可执行文件时如何修改这个引用，代码重定位条目存放在.rel.text中，已初始化的放在.rel.data

7.7.2、重定位符号引用

重定位算法：

汇编器会为每一个引用产生一个重定位条目，在引用后面的一行

1.重定位PC相对引用

sum正好处于第6行，而且是0xf位，在内存中运行时的地址=基址+偏移=0x4004d0 + 0xf

这个等式，其中0x5就是第6行有5字节，执行完是0x5字节

2.重定位绝对引用

7.8、可执行目标文件

.init节定义了小函数，会被藏东西的，程序初始化代码会调用它，因为可执行文件是完全链接的，已经重定位，所以不需要.rel节

可执行文件的连续的片（chunk）被映射到连续的内存段，程序头部表描述映射关系

第2行的大小0x69c，包含ELF头和程序头部表，init，text，rodata节

3，4行存储.data节和.bss节

7.9、加载可执行目标文件

我们用加载器来加载可执行文件，运行时存在内存映像，从0x400000开始，后面是数据段，运行时堆在数据段后，通过调用malloc库向上增长，用户栈总是从最大合法用户地址2的48次幂-1开始，想较小内存地址增长。栈上区域从地址2d的48次幂开始，是为内核kernel中的代码和数据进行保留的，内核就是操作系统驻留在内存的部分

7.10、动态链接共享库

共享库是致力于解决静态库缺陷的一个现代产物，运行加载时可以加载到任意模块，并和一个在内存中的程序链接起来，可以加载到任何内存地址，并和内存中的程序连接起来，这个过程称为动态链接，是由动态链接器执行的。共享库也叫做共享目标，在linux中用.so文件，微软使用的共享库成为dll

7.11、从应用程序中加载和链接共享库

7.12、位置无关代码

共享库是为了节约内存资源而诞生的，如果多个进程共用一个库，那么再每个内存的位置，甚至大小都不同，那么就应该使用：位置无关代码PIC，可以加载无需重定位的代码叫做PIC，这个东西可以把库加载到内存任何位置且不用修改链接器。

1、PIC数据引用

无论我们在内存加载什么模块，数据段和代码段的距离一直不变，即，代码段任何指令与数据段的变量之间的距离在运行时都是一个常量，与二者的绝对内存位置是无关的。PIC在数据段的开始处创建一个表，即全局偏移量表GOT。在GOT中，每个被这个目标module引用的全局数据目标都有一个8字节的条目。编译器还为GOT中的条目生成重定位记录，加载时动态链接器重定位每个条目并使其包含正确的绝对地址

2、PIC函数调用

程序调用一个共享库中的函数，该函数可以存在于内存中任何地址，这就很折磨了，但通过延迟绑定，我们将过程地址的绑定推迟到第一次调用该过程时。

延迟绑定是通过GOT和过程链接表PLT，这两个数据结构完成的、GOT属于数据段，PLT属于代码段

PLT：是个数组，每个条目是16字节代码，PLT【0】很特殊，器跳转到动态链接器中，每个库函数都有自己的条目

GOT：是个数组，每个条目是8字节代码，GOT[0]和GOT[1]是加载时的函数，其余的会与PLT一一对应

7.13、库打桩机制

简单来说就是欺骗系统调用的包装函数，插入自己的函数进去，想拿到什么值都可以。

异常控制流

异常控制流指的是：现代系统通过使控制流繁盛突变来对这些情况做出反应，这些突变叫做异常控制流（ECF）。异常控制流发生在计算机的每个层次上，在硬件层上会发生，在操作系统层上，内核通过上下文切换进行进程的切换，在应用层中，一个进程可以发送信号到另一个进程

8.1、异常

异常是异常控制流的一种形式，一部分由硬件实现，一部分由操作系统实现。

当处理器检测到由事件发生时，它会通过一张叫做异常表的跳转表，进行间接的调用，到专门处理此类事件的操作系统子程序，即异常处理程序，处理完成，出现三种情况：

1.控制返回原指令

2.返回给原指令，没异常就执行下一条指令

3.终止被中断的程序

8.1.1、异常处理

系统中每种异常都有一个唯一的非负整数的异常号

8.1.2、异常的类别

1.中断

中断是异步，硬件中断的异常处理程序通常称为中断处理程序，

中断处理将控制返回给应用程序的下一条指令。

2.陷阱和系统调用

陷阱是有意的异常，是执行一条指令的结果。返回下一条指令。其最重要的功能是在用户程序和内核之间提供一个像过程一样的接口，叫做系统调用。

读取文件，创建新的进程，加载新的程序，结束程序都要像内核请求

3.故障

故障由错误引起，当发生故障时，交给故障处理程序。它会返回引起故障的指令，重新执行

4.终止

终止是不可恢复的致命错误造成的结果，通常是硬件错误。直接终止应用程序

8.1.3、linux/x86-64的异常

对于linux的系统调用，每个应用想要请求内核服务时，都有唯一一个整数号对应于一个内核中的跳转表的偏移量，c语言用syscall函数来调用系统调用，但实际上对于大多数系统调用，c语言采用包装函数，包装函数将参数打包在一起，以适当系统调用使指令陷入内核。

系统调用和包装函数统称为系统级函数。在linux的系统调用通常使用寄存器不通过栈传递。

%rax为系统调用号，剩下rdi，rsi，rdx，r10，r8，r9当参数，rax还返回返回值，-4095到-1的负数返回值表示出错

8.2、进程

异常是允许操纵系统内核提供进程概念的基本构造块。

在一个执行中程序的实例就是进程，系统的每个程序都运行在某个进程的上下文中。

上下文是由程序正确运行所需的状态组成的。这个状态包括放在内存中的程序的代码和数据，它的栈，通用目的寄存器的内容，程序技术器，环境变量以及打开文件描述符号的集合。

8.2.1、逻辑控制流

不多解释，已经很清楚

8.2.2、并发流

一个逻辑流的执行在时间上与另一个流重叠，这个就是字面意思，并发运行就是两个程序运行有时间上的交错。

8.2.3、私有地址空间

在一个程序中，进程为其提供自己的私有地址空间，这个空间是不能被别的进程进行r or w。

8.2.4用户模式和内核模式

为了使操作系统内核提供一个无懈可击的进程抽象，处理器必须提供一种机制，限制一个应用可以执行的指令以及它可以访问的地址空间范围

处理器通常使用某个控制寄存器中的一个模式位来提供这种功能，该寄存器在该进程中有特权。当设置了模式位，进程就运行在内核模式中，即超级用户模式。

用户模式改变为内核模式唯一方法就是通过中断，故障或者陷入系统调用这种异常。

linux中存在/proc文件系统，可允许用户访问内核数据结构的内容。

8.2.5、上下文切换

操作系统内核使用上下文切换的较高层形式的异常控制流来实现多任务。在进程执行的时候，内核可以决定抢占当前进程，这就叫调度，由内核中的调度器代码完成。

8.3、进程控制

8.3.1、获取进程ID

每个进程都有自己的PID。

getpid函数返回调用进程的PID。

getppid函数返回它的父进程PID。

8.3.2、创建和终止进程

进程总是有三种状态，

1.运行：要么在cpu上执行，要么就在等待内核的调度

2.停止：进程执行要么被挂起，且不会调度。当收到sigstop，sigtstp，sigttn或者sigttou时，进程就停止，并且停止直到收到sigcont信号，然后运行

3.终止：进程停止，进程停止有三种原因：收到信号，return从主函数，exit

父进程通过调用fork函数创建新子进程，子进程几乎与父进程相同，子进程得到与父进程用户级虚拟地址空间相同的副本，当父进程调用fork时，子进程可以读写父进程中打开的任何文件。父子进程最大区别是PID不同

fork函数被调用一次，却返回两次，一次在调用父进程中，一次是在新创建的子进程中，父进程中，返回子进程的PID。子进程中返回0，通过返回值我们能直到程序是在父进程中进行还是子进程中执行

#include<stdio.h>
#include<sys/types.h>
#include<unistd.h>
int main()
{
    pid_t pid;
    int x = 1;
    pid = Fork();
    if (pid == 0){
        printf("child: x = %d\n",++x);
        exit(0);
    }
    printf("parent: x = %d\n",--x);
    exit(0);
}

在linux下运行，发现先返回parent是0，再返回child是2，那么以下就是几个特性了：

1.调用1次，返回了两次

2.并发执行：先返回父进程再返回子进程，但实际上来说并不一定，在另一台机器上就可能不是这样的情况

3.相同但是独立的地址空间：子进程和父进程的地址空间以及值什么的都相同，我们发现x的值并无变化，所以再两个进程中是独立的过程，不互相影响

4.共享文件：输出都在屏幕上

8.3.3、回收子进程

如果父进程终止了，内核会安排init进程成为其父进程。init的PID为1，其不会终止时所有进程的祖先。一个进程可以通过waitpid函数来等待其子进程终止或停止。

1	pid_t waitpid(pid_t pid, int *statusp, int options)

1.pid = -1 ,等待的集合就是父进程的所有子进程

pid>0，单独子进程，进程ID为pid

2.修改默认行为

1 2	pid_t wait (int *statusp) wait(&s) 完全等价于 waitpid(-1, &s, 0)

回收顺序时这台电脑的特殊属性，不确定

8.3.4、进程休眠

1	unsigned int sleep（unsigned int second）

sleep让一个进程挂起一段时间

1	int pause（void）

让调用函数休眠，征集到该进程接收到一个信号

8.3.5、加载并运行程序

1	int execv（const char filename, const char argv[],const char *envp[])

该函数加载运行可执行文件filename，且带参数argv和环境变量列表envp，找不到filename就返回其调用程序，这个函数调用一次从不返回。

8.4、信号

Linux信号属于软件形式的异常，一个信号就是一个小消息，其通知进程系统种发生了某件类型的事件，如下图：

低层的硬件异常是由内核异常处理程序处理的

8.4.1、信号术语

传送一个信号到目的进程由两个步骤组成：

发送信号：内核通过更新目的进程上下文的状态来发送一个信号给目的进程，或者一个进程调用kill函数，显示的要求内核发信号给目的进程。

接收信号：当目的进程被内核强迫以某种方式对信号的发送做出反应时，就接受了信号

一个发出但没接收到的信号叫做待处理信号，一种类型的待处理信号在一个进程中最多只有一个，其余的都被丢弃。当然还可以通过阻塞这种方式选择性接受信号。

在内核中有一个集合，这个集合有所有信号，一旦接收到信号，这个信号就会从集合中被剔除。

8.4.2、发送信号

发送信号的机制基于进程组这个概念

1.进程组

每个进程属于一个进程组，进程组是由一个正整数进程组ID来标志的。

1	pid_t getpgrp(void);//返回当前进程的id

默认的，一个子进程和其父进程同属于一个进程组

1	int setpgid(pid_t pid, pid_t pgid);//若成功返回0，不成功返回-1，该函数可以改变自己和其他进程的进程组

pid的进程改为pidg,若pid为0，使用当前进程PID，弱pgid为0，用pid的PID为进程组ID，如果进程15213是调用进程，再把两个参数设为0，会创建新的进程组，其ID是15213，并把这个进程加到新进程组中。

2.用/bin/kill程序来发送信号

4.调用kill函数发送信号

1	int kill(pid_t pid, int sig);

若pid大于0，发送信号号码给sig给pid，若等于0发送给进程组每个进程，小于0，发送绝对值的pid到每个进程。

5.alarm函数发送信号

1	unsigned int alarm(unsigned int secs);//返回前一次闹钟秒数，若未设闹钟则为0

该函数安排内核在secs秒后发送SIGALARM信号给调用进程

8.4.3、接收信号

当内核模式变成用户模式时，进程检查未被阻塞的待处理信号的集合，若不为空，该进程接收某个信号，每个信号都有一个预定义默认行为：

进程终止，进程终止并转储内存，进程挂起直到被SIGCONT信号重启，进程忽略该信号

8.4.4、阻塞和解除阻塞信号

隐式阻塞机制。内核默认阻塞任何当前处理程序正在处理信号类型的待处理的信号。

显式阻塞机制。调用函数，来明确阻塞信号

8.4.5、编写信号处理程序

1.安全的信号处理

信号处理程序回合主程序和其他信号处理程序并发运行，要注意以下事项：

输出的唯一安全方法是write，还有一些专门开发函数：

2.正常信号处理

未处理的信号是不排队的，直接被丢弃了。

3.可移植的信号处理

signal函数语义不同，在一些unix系统上，如信号k被捕获后必须将信号k恢复成默认值，所以每次运行后都要调用signal函数，显式的重新设置自己

系统调用可以中断，read write accept这些系统调用会阻塞进程一段进程一段时间，称为慢速系统调用

8.4.6、同步流避免并发错误

看不懂了

8.4.7、显式地等待信号

不懂。

8.5、非本地跳转

c语言提供一种用户级的异常控制流形式，称为非本地跳转，他将控制直接从一个函数转移到另一个当前正在执行的函数，通过setjmp，longjmp函数来提供。

1
2
3

#include<setjmp.h>
int set jmp(jmp_buf, env);
int sigsetjmp(sigjmp_buf env, int savesigs)

env保持调用环境，这个函数返回值为0，但不能赋值给变量

1
2
3

#include<setjmp.h>
void longjmp(jmp_buf env, int retval);
void siglongjmp(sigjmp_buf env, int retval);