《CSAPP》笔记

信息的表示与处理

信息存储

大多数计算机使用8位的块成为字节(byte),作为最小的可寻址内存单元。机器级程序将内存视为一个庞大的字节数组，成为虚拟内存(virtual memory),内存每个字节由唯一的数字来标识，成为地址，所有可能地址集合成为虚拟地址空间（virtual address space）。实际实现将众多存储设备和操作系统管理结合起来实现。

十六进制表示法

字数据大小

字长：指明指针数据的标称大小(nominal size)，虚拟地址以一个字长编码，字长决定了虚拟地址空间的最大值。

将程序区分为32位和64位程序，区别在于该程序是如何编译的，而不是其运行的机器类型。

寻址和字节顺序

几乎所有机器，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。

• 大端法(big-endian)：高字节的数据存放在低地址

• 小端法(little-endian)：低字节的数据存放在低地址

  

  大小端转换

• 网络传输过程中要根据网络标准进行转换

• 机器码表示，小端时，与常规书写方式经常相反

• 编写程序绕过正常的类型系统

表示字符串

C语言中字符串被编码为以null(值为0)字符结尾的字符数组。

表示代码

相同代码在不同机器上产生的机器码不同，不同机器类型使用不同且不兼容的指令和编码方式。因而二进制代码不兼容，很难移植。

布尔代数

C语言中的位级运算

位运算：| 、&、~(非)、^（异或）

计算位级运算最好方法就是将十六进制转换成二进制计算后再转换为十六进制。

通常用 X&0xFFFF……计算X的掩码

C语言中的逻辑运算

逻辑运算：||、&&、！

• 逻辑运算认为所有非零都为TRUE，0位FALSE，位级运算被限定为0或1时才和逻辑运算相同
• 逻辑运算在对第一个参数求值就能确定表达式的值时，不对后续求值。

C语言中的移位运算

• 移位运算：<<(左移)、>>(右移)
  • 算术右移：一般有符号数进行算数右移，即补最高有效位的值
  • 逻辑右移：一般无符号数进行逻辑右移，即补0.

C语言未规定有符号数使用哪种类型的右移，实际上几乎所有编译器/机器组合都对有符号数使用算数右移。对于无符号数，右移必须是逻辑的。

Java对右移有明确的规定。

当移位k超过w-1时(w为数据位数)，C语言采取移位k=k mod w

整数表示

整数数据类型

仅long型字节数不同

​ C语言规定的最小取值范围：

除固定大小int32_t/int64_t相同外，其余均不同，且只要求正数和负数取值范围是对称的。

无符号数的编码

补码编码

有符号数和无符号数之间的转换

C语言中的有符号数与无符号数

扩展一个数字的位表示

截断数字

关于有符号数和无符号数的建议

整数运算

无符号加法

补码加法

补码的非

无符号乘法

补码乘法

乘以常数

除以2的幂

关于整数运算的最后思考

浮点数

二进制小数

IEEE浮点表示

数字实例

舍入

浮点运算

C语言中的浮点数

程序的机器表示

程序编码

机器级编程的两种抽象：

• 指令集架构(ISA):定义了机器级程序的格式和行为，定义了处理器状态、指令的格式、以及每条指令对状态的影响。
• 机器级程序使用的内存地址是虚拟地址，提供的内存模型看上去是一个非常大的字节数组。
  • X86-64虚拟地址采用64位，目前实现时地址高16位必须设置为0，所以实际能指定$2^{48}$或64TB范围。

Intel与AT&T语法区别：

1. 操作数位置相反

   In Intel-syntax:

   在操作数中添加”=”

   AT&T syntax: .

   在操作数中添加“→”

1. 寄存器前加%，立即数前加$

2. 操作后缀添加大小

   b — byte (8 bits)

   w — word (16 bits)

   l — long (32 bits)

   q — quad (64 bits)

3. 地址描述方式AT&T采用(),Intel采用[],寻址方式也不同。

数据格式

访问信息

对于使用寄存器存入小于64位的时候：

1. 如果使用1byte、2bytes，保持剩余高位不变
2. 如果使用4bytes，剩余4bytes高位被置0(此条规则扩展到64位后添加)

操作数指示符

1. 立即数(immediate)：用来表示常数值

2. 寄存器(register):表示寄存器内容

3. 内存引用：根据计算出的地址访问内存位置内容

   

   最后一种模式为通用模式，其他模式为其特殊情况，即立即数+基址寄存器+(变址寄存器*比例因子)。

数据传送指令

​ MOV指令：

最后movabsq处理64位立即数，常规movq只能以表示为32位补码数字的立即数作为源操作数，然后将符号扩展得到64位的值，放入目的位置。movabsq能以任意64位立即数作为源操作数，并且只能以寄存器作为目的。

​ 五种可能：

不存在内存到内存，如需要则要经过寄存器中转。

较小源值移动到较大目的时(寄存器/内存到寄存器)：

• 注意零扩展比符号扩展少了movzlq，因为已经规定了32位复制到64位时，高32位自动置为0。
• cltq相当于movslq，只是总以寄存器eax为源和rax为目的，不过编码更紧凑。

压入和弹出栈指令

pushq %rbp (1 byte)相当于一下两条指令(5 bytes)

popq %rax 同理

算术和逻辑操作

加载有效地址

lea指令(load effective address):从内存读数据到寄存器，实际上根本没有引用内存，第一个操作数为内存引用，但是并不在指定位置读入数据，而是将有效地址写入目的寄存器。

例如用于计算加法和乘法：

一元和二元操作

• 一元操作：一个操作数即是源也是目的
• 二元操作 ：第二个操作数即是源也是目的(可以是寄存器、内存)，第一个为源操作数(可以是立即数、寄存器、内存)

移位操作

移位量是一个立即数或单字节寄存器%cl中，即最高255位。

• 由寄存器%cl确定时，移位操作对w位数据值进行操作，移位量由%cl寄存器的低位进行决定$2^m=w$,高位被忽略。

  例如：

  

特殊的算术操作

控制

条件码

CF: (Carry flag)最高位产生进位，可用来检查无符号数的溢出。

ZF: (Zero flag)结果为0

SF: (Sign flag)结果为负数

OF: (Overflow flag)结果导致补码溢出—正溢出或负溢出

除lea不改变任何条件码，其他上表中的算术逻辑操作均会改变条件码

1. 逻辑操作,例如XOR改变进位标志和溢出标志位0
2. 移位操作，进位标志设置为最后一个被移出的位，溢出标志设置为0
3. INC和DEC设置溢出和零标志，不会改变进位标志。

​ 比较和测试指令：

更多关于条件码参见

访问条件码

1. 根据条件码某种组合将一个字节置0或置1
2. 根据条件码进行条件跳转
3. 有条件的传送数据

目的操作数是低位单字节寄存器，或是一个字节的内存位置，一般需要接命令将高位清零。

跳转指令

• 直接跳转： jmp label (条件跳转只能是直接跳转)

• 间接跳转： jmp * Operand (operand为寻址方式的任一种)

  

跳转指令的编码

汇编中跳转指令用符号标号书写，汇编器和链接器会产生跳转目标的编码

• 采用相对地址，将跳转目标地址与跳转指令后那条指令的差作为编码，为1、2、

  4个字节，较短。

• 采用绝对地址，用4个字节直接指定目标。

  

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

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

实现条件操作传统方法是使用控制，另一种是使用数据的条件转移，只有一些受限情况才可行，但可以高效的使用一条简单的条件传送指令实现它。

循环

1. do-while

   

2. while

   • 中间跳转法(jump to middle):

     

   • guarded-do 如果初始条件不成立就跳过循环，把代码变换为do-while循环

     

3. for

   相当于：

   

   翻译为两种while形式分别为：

   

   

switch语句

使用跳转表，优点是执行开关语句的时间与开关情况数量无关

L4为跳转表

过程

• 传递控制
• 传递数据
• 分配和释放内存

运行时栈

许多函数小于等于6个参数可以用寄存器传递参数，不用栈，当局部变量可以用寄存器

转移控制

数据传送

eg：

栈上的局部存储

1. 寄存器不足够存放时

2. 对局部变量使用&地址运算符生成地址时

3. 局部变量是数组或结构，需要通过数组或结构引用访问。

   

   

寄存器中的局部存储空间

• rbx、rbp、r12-r15由被调用者保存

• 其他除rsp外，都由调用者保存

  

  

递归过程

数组分配和访问

基本原则

指针运算

异数的数据结构

在机器级程序中将控制与数据结合

浮点代码

处理器体系结构

优化程序性能

存储器层次结构

链接

异常控制流

虚拟内存

系统级I/O

网络编程

并发编程

未完待续…………