概念

1. 字节，八位的位块，最小的可寻址内存单位
2. 虚拟内存，机器级程序将内存看成一个非常大的字节数组，称为虚拟内存。
3. （虚拟）地址，内存的每个字节都由一个唯一的数字标示，这个数字叫做这个字节的地址。
4. 虚拟地址空间，所有（虚拟）地址的集合称为虚拟地址空间。
5. 字长，指明指针数据的norminal size。一个字长为w位的机器，虚拟地址的范围从0到$2^w -1$。
6. 大端和小端。大端，最高有效字节在最前面；小端，最低有效字节在最前面。用于跨多字节的对象，它的地址是什么，如何排列这些字节。在网络传输二进制数据时，可能会出现问题。
7. 算术右移和逻辑右移。算术右移在左端补k个最高有效位的值，而逻辑右移在左端补k个0，C语言没有规定对于有符号数使用哪种右移，但是几乎所有的编译器和机器组合都对有符号数进行算术右移。对于无符号数，右移必须是逻辑右移。

信息的表示和处理

浮点数表达的范围大，但是确实近似的，精度有限。如$(3.14+1e20) - 1e20$的值是$0.0$，而$3.14+(1e20-1e20)$的值是$3.14$。
而整数的表示范围小，但是是精确的。比如：$200\times 300\times 400\times 500$会溢出，

信息的存储

虚拟内存和虚拟地址空间

字节是八位的位块，它是最小的可寻址内存单位。机器级程序将内存看成一个非常大的字节数组，称为虚拟内存。内存的每个字节都由一个唯一的数字标示，这个数字叫做这个字节的地址。虚拟地址空间，所有（虚拟）地址的集合称为虚拟地址空间。

字数据大小

每台计算机都有一个字长，指明指针数据的标称大小（norminal size）。虚拟地址就是用这样的一个字编码的，字长决定的最重要的参数就是虚拟地址空间的最大大小。一个字长为w位的机器，虚拟地址的范围从0到$2^w -1$。

寻址和字节顺序

为了寻找跨越多字节的程序对象，我们必须建立两个规则：

1. 这个对象的地址是什么。在几乎所有的机器上，多字节对象都存储为连续的字节序列，对象的地址就是所使用字节中的最小的地址。
2. 如何在内存中排列这些字节。通常有两个规则，大端，最高有效字节在最前面；小端，最低有效字节在最前面。字节顺序在以下三个地方变得很重要：
   • 在网络传输二进制数据时，可能会出现问题。
   • 阅读表示整数数据的字节序列时，通常是在检查机器级程序时。
   • 编写规避正常的类型系统的时候，比如C语言的强制类型转换时，把一个4字节的int转换成一个字符数组，大端小端输出的结果是不一样的。

一般情况下，数值变量在各类机器/操作系统中除了大端小端的区别外，没有其他区别。而指针变量在各类机器/操作系统之间差异显著。

字符串表示

使用ASCII码作为字符码的任何系统，它们对于字符串的表示是相同的。

函数表示

指令编码在不同的机器上是不同的。不同的机器类型使用不同的而且不兼容的指令和编码方式。

布尔代数和C语言的位运算

与或非，异或，这四个操作，都是对位进行操作的。更多关于位运算的介绍可以查看。

C的逻辑运算和移位运算

逻辑运算一定要记得加括号。
算术右移和逻辑右移。算术右移在左端补k个最高有效位的值，而逻辑右移在左端补k个0，C语言没有规定对于有符号数使用哪种右移，但是几乎所有的编译器和机器组合都对有符号数进行算术右移。对于无符号数，右移必须是逻辑右移。

整数表示

整数的类型

ISO C给出了C中每个整形的最小取值范围（至少要满足这个范围，可以更大）。但是具体每个整形的长度是多少是和实现相关的。几个特殊的类型int32_t和uint32_t，``int64_t，uint64_t`，是和实现无关的，它们的长度通过类型中的数字显示出来。

无符号数的编码

假设一个w位的整数数据类型，用bit vector $x = [x_{w-1}, \cdots, w_0]$表示，其中每一位的取值都是0或者1。用一个函数$B2U_w$表示：
无符号数编码的定义
对于bit vector $x = [x_{w-1}, \cdots, w_0]$
$$ B2U_w (x) = \sum_{i=0}^{w-1} x_i 2^i $$
将一个长度为w的bit vector映射到一个非负整数。

有符号数的编码

补码

补码（Two’s Complement）是用来表示有符号的一种方法。这个定义中，将字的最高有效位解释为负权。用函数$B2T_w$表示：
补码的定义
对于bit vector $x = [x_{w-1}, \cdots, w_0]$
$$ B2U_w (x) = - x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i $$
最高有效位$x_{w-1}$也称为符号位，它的权重是$-2^{w-1} $。

反码

反码（Ones’ Complement）：最高有效位的权重是$ - (2^{w-1} -1) $而不是$ - 2^{w-1} $，其余的地方和补码一样：
$$ B2O_w (x) = - (x_{w-1} 2^{w-1} - 1) + \sum_{i=0}^{w-2} x_i 2^i $$

原码

原码（Sign-Magnitude）：最高有效位是符号位，用来确定剩下的位是正权还是负权：
$$ B2S_w (x) = (-1)^{x_{w-1} } \cdot \sum_{i=0}^{w-2} x_i 2^i $$

区别和联系

原码和反码，它们对于数字0都有两种不同的表示方法。注意，反码和补码，反码是Ones’而补码是Two’s，因为对于一个正整数$x$，求$-x$的表示时，使用反码是$[111…111]w - x$，而补码是$[1000…000]{w+1}-x$。

一个长度为$w$位的bit vector，可以解释成补码，也可以解释成无符号编码，当最高有效位为0时，它们都表示正整数；当最高有效位为$1$时，解释为补码时，它是负数，解释为无符号编码时，它是一个正整数，它们两个的绝对值相加等于$2^{w+1} $，

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

在C语言的大多数实现中，处理同样字长的有符号数和无符号数的转换的规则是：数值可能会改变，但是bite vector不变。

字长为16的整数补码

0
0000 0000 0000 0000
-1
1111 1111 1111 1111
-2^15
1000 0000 0000 0000
2^15-1
0111 1111 1111 1111

补码表示的有符号数转换为无符号数

给定bit vector的补码表示的无符号数和无符号数之间的关系可以表示为函数$T2U$：
对于满足$TMin_w \lt x \lt TMax_w $的$x$有：
$$T2U_w(x) = \begin{cases}x, x\ge 0 \\ 2^w + x\lt 0\end{cases}$$

无符号数转换为补码表示的有符号数

对于满足$0\le u \le UMax_w$的$u$，有：
$$U2T_w(u) = \begin{cases}u, u\le TMax_w \\u - 2^w\gt TMax_w\end{cases}$$

有符号数和补码表示的无符号数之间的关系

只要记住一条就行，上面的两个转换就能推导出来。
一个字长为$w$，最高有效位为$1$的bit vector，用补码方式解释为负数A，用无符号编码解释为整数B，A和B的绝对值之和为$2^w $。为什么？

假设字长为8，给定一个正整数$x$，比如$x=9$，无符号编码为$0000 1001$，$-x$的补码编码怎么计算，$2^8 - 9$，即$10000 0000 - 0000 1001$，结果是$1111 0111$。
$1111 0111$表示$-x$的补码，绝对值$x$的无符号编码表示是$0000 1001$，用无符号编码解释$1111 0111$，显然，$1111 0111$加上$0000 1001$，等于$2^w $。

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

对于相同字长的整形和无符号整形，如果一个运算的两个运算数一个是有符号的，一个是无符号的，C语言会隐式的将有符号参数强制转换为无符号的。

整形提升

无符号数的扩展，在左面添加0，叫做零扩展。
有符号数的扩展，在左面添加最高有效位的值，叫做符号扩展。
当强制类型转换同时涉及到操作数的大小和符号变化时，先改变操作数的大小，然后再改变操作数的符号。比如short转换成unsigned，先把short转换成int，然后再把它转换成unsigned的

整形截断

无符号数的截断

将长度为$w$的bit vector $\mathbf{x}$，丢弃最高位的值，将其截断为长度为$k$的bit vector $\mathbf{x’}$。令$x=B2U_w(\mathbf{x})$，$x’=B2U_k(\mathbf{x’})$，则$x’= x mod 2^k $。

补码数值截断

将长度为$w$的bit vector $\mathbf{x}$，丢弃最高位的值，将其截断为长度为$k$的bit vector $\mathbf{x’}$。令$x=B2U_w(\mathbf{x})$，$x’=B2T_k(\mathbf{x’})$，则$x’=U2T_k(x mod 2^k)$。
先截断为无符号数，然后将无符号数转换成有符号数。

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

1. 相同长度的无符号数和有符号数，在运算中有有符号数的话，就会把有符号数转换成无符号数。比如for循环中，for(unsigned i = 10; i >= 0; --i)，永远不会跳出for循环，因为当$i=0$时，--i就相当于得到了有符号数$-1$，而$-1$的补码形式和无符号数的$2^w -1 $的编码是一样的，而这里就是得到了$2^w -1$。
2. 两个无符号数相减。永远不可能小于0。

整数运算

无符号数加法

无符号数加法

无符号数加法：
对于满足$0\le x, y \lt 2^w $的无符号数$x$和$y$有：
$$x+y = \begin{cases}x+y, x+y \lt 2^w, 正常\\ x+y -2^w , 2^w \le x+y \le 2^{w+1}, 溢出 \end{cases}$$

算术溢出

当$x+y$的和超出$w$位能表示的最长长度时，就说它发生了算术溢出。

加法逆元

加法逆元，对于每一个值$0\le x \lt 2^w $，都存在一个值$0\le y \lt 2^w $$，使得$x+y = 0$，这个$y$就叫做$x$的加法逆元，反过来，$x$也是$y$的加法逆元。
$$y = \begin{cases}x, x=0\\ 2^w -x, x \gt 0\end{cases}$$

补码加法

补码加法：
对于满足$- 2^{w-1} \le x, y \lt 2^{w-1} -1 $的有符号整数$x$和$y$有：
$$x+y = \begin{cases}x+y - 2^w, x+y \ge 2^{w-1} \\ x+y, - 2^{w-1} \le x+y \lt 2^{w-1} \\ x + y + 2^w, x+y \le 2^{w-1} \le 2^{w+1} \end{cases}$$

可以先进行无符号数加法，然后将结果使用$U2T_w$转换成有符号数。为什么可以这样子呢？是因为，补码加法和无符号数加法有完全相同的位级表示，在很多实现中执行补码加法和无符号数加法的机器指令一样。

补码的非

这个非是什么意思？？？怎么感觉有问题，就是用$2^w - x$呗。不管怎么样，这一接就是介绍补码的逆元，只要$x+y % 2^2 =0$就行了。
对于满足$TMin_w \le x \le TMax_w$的每个数字$x$都有加法逆元$y$：
$$y = \begin{cases}TMin_w, x=TMin_w\\ -x, x\gt TMin_w \end{cases}$$

无符号乘法

对于满足$0\le x, y \lt 2^w $的w位无符号数$x$和$y$有，它们的乘积需要$2w$位来表示，而C语言中，无符号乘法定义为$w$位，从$2w$位中截取低$w$位，作为结果：
$$ x\times y = ((x\cdot y) mod 2^w)$$

补码乘法

对于满足$- 2^{w-1} \le x, y \lt 2^{w-1} -1 $的有符号整数$x$和$y$，先将它们当做无符号数相乘，然后截断为$w$位，再将无符号数转化成有符号数：
$$ x\times y = ((x\cdot y) mod 2^w)$$

为什么可以这样子。因为对于无符号和补码乘法来说，它们具有相同的位级表示。即：
$$T2B_w(x\cdot y) = U2B(x’ \cdot y’)$$
给定bit vector $\mathbf{x}, \mathbf{y}$，分别用无符号整数编码和补码进行编码，得到$x’,y’, x, y$。最后它们乘出来的结果截断为$w$位之后还是一样的。

乘以常数

整数乘法的指令相当的慢，需要十个或者更多个时钟周期，而其他整数运算（加法，减法，位级运算和移位），都只需要一个时钟周期。所以，编译器会尝试使用移位和加法的组合运算来提高运算速度。
对于和2的幂相乘的无符号乘法来说，其实就相当于左移一个数值。而固定大小的补码算术运算的位级操作和其无符号运算等价。

除以2的幂

浮点数的表示

IEEE754标准。

二进制小数

将一个含有小数值的二进制数转换为十进制。给出如下形式的二进制小数：
$$b_mb_{m-1}\cdots b_1b_0.b_{-1}b_{-2}\cdots b_{-n-1}b_{-n}$$
它表示的数字$b$定义如下：
$$b=\sum_{i=-n}^m 2^i\times b_i$$
小数点后的位，它的权值为$2$的负幂。

IEEE浮点运算

示例

舍入

浮点运算

C语言中的浮点数

参考文献

1.《CSAPP》第五版

链接

链接是将各种代码和数据片段收集并组合成一个单一文件的过程，这个文件可以被加载到内存并执行。链接可以在三个时刻进行：

• 编译时(compilation time)，也就是在源代码被翻译成机器代码时。
• 加载时(load time)，在程序被加载器加载到内存并执行时。
• 运行时(run time)，由应用程序负责加载。

早期链接是手动执行的，现代系统中链接是由链接器程序自动执行的，链接器使得分离编译变得可能。

编译器驱动程序

执行将源文件翻译成可执行目标文件过程的程序，即预处理器，编译器，汇编器和链接器，构成了编译系统。
编译器驱动程序负责完成整个编译过程，即在需要时分别调用预处理器，编译器，汇编器和连接器，整个编译过程都是由编译器驱动程序负责的。
可以使用GCC对这些步骤进行实践：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#1.预处理，生成ASCII码中间文件
cpp main.c main.i
cpp sum.c sum.i
#2. 编译，将中间文件翻译成ASCII码汇编文件
cc1 main.i -Og -o main.s
cc1 sum.i -Og -o sum.s
#3. 汇编，将汇编文件翻译成可重定位目标文件
as main.s -o main.o
as sum.s -o sum.o
#4. 链接，将可重定位目标文件连接成可执行目标文件
ld -o main.o sum.o prog
#5.执行
./prog
#shell调用操作系统的加载器函数(loader function)，将可执行目标文件prog的代码和数据复制到内存中，然后将控制转移到这个程序的开头。

目标文件

目标文件是字节块的集合，它们按照特定的目标文件格式来组织，代码，数据，还有包含引导链接器和load function的数据结构等。各个系统的目标文件格式都不相同，Linux和UNIX系统下使用的是可执行可连接格式(exceutable and linkable format, ELF)，windows使用的是PE格式，MAC用的是Mach-O格式。
不管哪个平台，目标文件都可以分为三种：

1. 可重定位目标文件。包含二进制代码和数据，在编译时可以和其他目标文件合并起来，创建一个可执行目标文件。编译器和汇编器生成可重定位目标文件。
2. 可执行目标文件。包含二进制代码和数据，可以被直接复制进内存并执行。链接器生成可执行目标文件。
3. 共享目标文件。一种特殊类型的可重定位目标文件，可以在加载或者运行时动态的加载进内存并链接。

C语言中如何读取一个ELF文件的ELF-header。shell中直接使用readelf命令。-h, -s

静态链接

LD是静态链接器，它的输入是一组ELF可重定位目标文件和命令行参数，输出是一个完全链接的，可以加载和运行的ELF可执行目标文件。
输入的ELF可重定位目标文件由不同的section组成，每个section存放代码数据等。

为了构造可执行文件，静态链接器有以下任务：

1. 符号解析。目标文件定义并且引用符号，每一个符号对应于一个函数，一个全部变量，或者一个静态变量。符号解析的目的是将每个符号引用和一个符号定义关联起来。
2. 重定位。编译器和汇编器生成的section都是从地址0开始的，链接器通过把每个符号定义和一个内存位置关联起来，对这些section进行重定位，然后修改对这些符号的引用，使得它们指向相应的内存位置。链接器使用汇编器产生的重定位条目执行这样的重定位。

可重定位目标文件

一个ELF可重定位目标文件由以下section组成：

1. .text section，存放的是已编译程序的机器代码。
2. .data section，存放的是已经初始化的全局和静态C变量。
3. .bss section，存放的未初始化的全局和静态C变量，以及所有被初始化为0的全局或者静态变量。它并不占据实际的空间，只是一个占位符。在运行时，通过exec函数在内存中将他们初始化为0。
4. symtab section，保存一个符号表，存放的是程序中定义和引用的函数和全局变量的信息。它不包含局部变量的entry。
5. debug section，调试符号表，其中的entry是程序中定义的局部变量和类型定义，程序定义和引用的全局变量，和原始的C源文件。
6. .rel.text section，.text section中的位置列表。链接器把这个目标文件和其他目标欧文件组合时，需要修改相应的位置。通常来说，调用外部函数或者引用全局变量的指令都需要修改，调用本地函数的指令不需要修改。通常可执行目标文件中不需要重定位信息。
7. .sttrtab section，保存字符串，主要是和.symtab,.debug section中entry相关的字符串，以及section headers中的section names。每一项都是以null结尾的字符串。

符号和符号表

编译器生成符号。
汇编器生成符号表。

符号

每一个可重定位模块m都有一个ELF符号表（.symtab)，它包含m定义和引用的各种符号的信息。在链接器的上下文中，有三种不同的符号：

1. 模块m定义的，能被其他模块引用的全局符号(global symbols)。Global linker symbols对应于non-static的C函数和global variables。
2. 其他模块定义的，能够被模块m引用的全局符号，也被称为外部符号(external symbol)，对应其他模块中定义的non-static的C函数和global variables。
3. 模块m定义的，只能被它自己使用的局部符号(local symbols)。Local linker symbols对应于C的static function和static global variables，static local variables，它们在模块m中的任何地方都可以使用，但是不能被其他模块使用。

Local liker symbols和local variables不是一回事，local linker symbols对应的是当前模块内（在C中就是一个文件）的函数或者变量，而local nonstatic variables对应的是函数内的自动变量。Local nonstatic variables在栈中管理，不是链接器的事情。而local static variables存放在.data或者.bss section中，并且在符号表中有一个唯一的local linker symbol。

.symtab符号表

.symtab section中包含ELF 符号表，它包含一个entry的数组，每个entry都是一个struct Elf64_Sym的结构体：

1
2
3
4
5
6
7
8

typedef struct{
    uint32_t      st_name;
    unsigned char st_info;
    unsigned char st_other;
    uint16_t      st_shndx;
    Elf64_Addr    st_value;
    uint64_t      st_size;
} Elf64_Sym;

st_name中存放的是字符串表中的字节偏移，指向一个字符串的名字，info存放的是符号类型。value是符号的地址。对于可重定位模块来说，value是离定义目标的section的起始位置的偏移；对于可执行目标文件来说，该值是一个绝对运行地址。
每一个符号都被分配到目标文件的某个section，section字段的取值还可以是在seciton header table中没有entry的三个特殊伪节(pseudosection)：

1. UNDER表示未定义的符号,
2. ABS表示不应该重定位的符号
3. COMMON表示还没有分配位置的未初始化的数据目标；对于COMMON符号，value字段给出对齐要求，size给出最小的大小。COMMON和.bss的区别：COMMON存放的是未初始化的全局变量，而.bss存放的是未初始化的静态变量，以及初始化为0的全局或者静态变量。

符号解析

链接器的输入是一组可重定位目标文件（模块），每个模块中都定义了一组符号。链接器将每个符号引用和输入的可重定位目标文件符号表中的一个确定的符号定义关联起来。

解析多重定义的全局符号

**函数和已经初始化的全局变量是强符号，未初始化的全局变量是弱符号。**在编译时，编译器向汇编器输出每个全局符号，或者是强或者是弱，汇编器会把这个信息编码在可重定位目标文件的符号表中。处理多重定义的符号的规则：

1. 不允许有多个重名的强符号。
2. 如果有一个强符号和多个弱符号，选择强符号。
3. 如果有多个弱符号同名，从这些弱符号中随机选择一个。

可以使用GCC的GCC-fno-common选项设置遇到多重链接时，触发一个错误。

和静态库链接

所有的编译系统都提供静态库的机制。
一个静态库包含多个可重定位文件，每个可重定位文件都是根据一个函数创建的。在应用时，只需要指定静态库的名字，链接器会只会复制其中被应用程序引用的目标模块。

Linux中的静态库以archive（后缀名为.a）的文件形式存在，它是一组连接起来的可重定位目标文件的集合，有一个头部描述每个目标文件的大小和位置。可以使用ar命令创建一个静态链接库，比如：

1

ar rcs libvector.a addvec.o mulvec.o

其中addvec.o和mulvec.o是两个可重定位目标文件，而libvector.a是我们要创建的静态库的名字。
使用gcc可以链接自定义或者C提供的静态库，gcc的-static参数告诉编译器驱动程序，链接器应该构建一个完全链接的可执行目标文件，它可以加载到内存并运行，在加载时无序进一步的链接；
-lvector参数是libvector.a的缩写或者可以使用
-Ldir libvector.a告诉链接器在目录dir下查找libvector.a文件。

链接器使用静态库解析引用

在符号解析阶段，链接器从左到右按照它们在编译器驱动程序命令上出现的顺序来扫描可重定位目标文件和存档文件。
在这个过程中，链接器维护一个可重定位目标文件的集合E，最后这个集合中的文件会被合并起来形成可执行文件；一个未解析符号的结合U，存放的是使用了但是还没有定义的符号；一个前面输入文件中已定义的符号集合D。
在开始的时候，E,U和D都是空的。
对于命令行中包含的每个输入文件f：

1. 如果没有文件，跳转到4，否则链接器会判断f是一个目标文件还是一个archive文件
2. 如果f是一个目标文件，那么链接器把f添加到集合E，修改U和D反应f中定义和使用的符号（就是把f中定义的符号加入到D中，把f中用到的但是没有定义的加到U中），并继续下一个输入文件，跳转到1
3. 如果f是一个archive文件，链接器就尝试匹配U中的符号和archive文件中定义的符号。如果archive中的某个文件成员m匹配了U中的一个引用，将m添加到E中，修改U和D反应m中定义和引用的符号。对于archive中的每一个文件都进行这个过程，任何不包含在E中的archive中的文件都被丢弃，链接器继续处理下一个文件，跳转到1
4. 当链接器处理完命令行中所有输入文件的扫描后，如果U是非空的，那么链接器输出一个错误并终止，否则，它会合并和重定位E中的目标文件，构建输出的可执行目标文件。
   从这个过程中我们可以看出来，命令行上库和目标文件的顺序非常重要，比如下面的两条命令，一个能够链接成功，另一个却会链接失败。

   1 2	gcc -static main2.o -L. libvector.a -o prog2 gcc -static -L. libvector.a main2.o -o prog2

重定位

当链接器完成了符号解析之后，代码中的每个符号引用和一个符号定义关联了起来，链接器就知道了它的输入目标模块中的code section和data section的确切大小，就可以进行重定位了。
重定位中会合并输入模块，并且为每个符号分配运行时地址。重定位分为两个步骤：

• 重定位section和符号定义。
• 重定位section中的符号引用。

重定位entry

当汇编器生成一个目标模块时，它并不知道数据和代码最终放在内存中的什么位置，它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位entry，告诉链接器在将目标文件合成可执行文件时如何修改这个引用。代码的重定位entry定义。

重定位符号引用

可执行目标文件

加载可执行目标文件

使用函数加载器，将可执行目标文件加载到内存。

动态链接共享库

静态库的问题：

1. 需要定期维护和更新，当静态库更新时，需要将引用程序和更新了的库重新链接。
2. 每一个进程都需要把这些函数复制到代码段中。

共享库是一个目标模块，在运行或者加载时，可以加载到任意的内存地址，并且和一个在内存中的程序链接起来。这个过程叫做动态链接。共享库也叫作共享目标(shared object)，在linux中用.so后缀，在windows中叫做DLL（动态链接库）。

共享库共享的方式：

1. 一个库只有一个.so文件，所有引用该文件的可执行目标文件共享这个。
2. 在内存中，一个共享库的.text节的副本可以被不同的进程共享。

使用-shared指示链接器创建一个共享的目标文件。共享库的编译必须总是使用该选项。
-fpic指示创建与位置无关的代码。

加载时链接共享库

运行时加载和链接共享库

位置无关代码

库打桩机制

处理目标文件的工具

总结

参考文献

1.《CSAPP》第七章
2.https://stackoverflow.com/questions/34960383/how-read-elf-header-in-c

C语言中的字符串

C语言中字符串不是一种类型，而是一种约定俗成的写法。按照约定，C风格字符串存放在数组中，并且以空字符'\0'结束。头文件<string.h>提供了操作C风格字符串的一些函数。

字符数组

1. 使用列表初始化。

   1 2	char str2[] = {'h', 'e', 'l', 'l', 'o'}; char str3[] = {'h', 'e', 'l', 'l', 'o', '\0'};

2. 使用字符串字面值初始化。

   1 2	char str1[] = "helloworld"; //编译器会隐式的在最后加一个"\0"，sizeof(str)会计算这个"\0", strlen(str)不会

这种方式是字符数组初始化的简便写法。

3. 指针和C风格字符串

   1	char *messages= "hello world";

对于以上三种方式来说，方式1和2是等价的，这种方式中的"helloworld"存放在栈中。而第三种有些特殊，在第三种方式中，"hello world"是一个字符串字面值常量，存放在数据区的字符串常量部分[6,7,8,9]。事实上，它是一个常量字符数组，是一个不可修改的左值[9]，把它作为右值时，会进行类型转换将左值转换成右值，即使用常量字符数组首字符的地址进行初始化。

C风格字符串操作函数

C语言标准库<string.h>或者C++版本的<string.h>提供了以下的字符串操作函数，它们的参数必须是指向以空字符结束的字符数组的指针。在函数内存不会验证这些字符串参数是否满足要求。

• strlen(p)，返回p指向的字符串的长度，不包括空字符
• strcmp(p1, p2)，p1==p2，返回0,p1>p2，返回正值，否则返回负值。
• strcat(p1, p2)，p2拼接到p1，返回p1
• sctcpy(p1, p2)，p2拷贝到p1，返回p1

有一点需要注意的是，p2必须能够容纳下拼接后或者拷贝后的字符串，编译器不会进行检查，这需要由程序员自己进行检查。

C风格字符串的比较

两个C风格字符串的比较，其实比较的是指针而不是字符串本身。如下所示：

1
2
3

char str1[] = "hello";
char str2[] = "world";
if(str1 < str2) //这行代码比较的不是两个字符串，而是两个指针。

string和C风格字符串的相互转换

1. 允许使用以空字符结束的字符数组初始化string对象或者为string对象赋值。
2. string对象的加法运算中允许使用空字符结束的字符数组作为其运算对象，不能两个都是。
3. string对象的复合赋值运算中允许使用以空字符结束的字符数组作为其右侧运算对象。

string转换成C风格字符串

1
2

string s("hello world!");
const char *str = s.c_str();

字符串转整数[2]

1
2
3
4
5
6
7
8

int my_atoi(char *p) {
    int res = 0;
    while (*p) {
        res = (res << 3) + (res << 1) + (*p) - '0';
        p++;
     }
     return res;
}

字符串分割[1]

重要的就是怎么存，返回一个指针数组，每个指针指向一个字符串，记得用完以后free。

去掉空白字符

参考文献

1.https://stackoverflow.com/a/34957656/8939281
2.https://stackoverflow.com/questions/17770202/remove-extra-whitespace-from-a-string-in-c

问题0-C和C++ 的命名规则

STL中的东西都放在了std命名空间中，并且使用了大小写字母等，为什么还需要使用leading underscore(single and double)前置的下划线？是标准，还是仅仅是习惯？
宏不遵守namespaces和其他上下文，为了避免冲突，就只能使用这种命名方式了，这不是一种编码标准，只是一种防止冲突的方式。具体示例可以看问题0的参考文献[1]。

那么C++ 的命名规则是什么呢？参见问题0的参考文献[2]。

1. Reserved in any scope(在任何scope都保留的命名规则)，包括宏的实现：
   • 下划线后紧跟大写字母的声明符。
   • 包含两个下划线的声明符。
2. Reserved in the global namespace(在全局的namespace中保留的命名规则）：
   • 使用一个下划线开头的声明符
3. 在std namespace中的所有东西都是保留的。

C通常会使用缩写，而C++ 中通常使用单下划线分隔单词，C/C++ 通常不使用驼峰命名法，除了STL模板类型。

问题1-C中为什么const int不能当做array size

The const qualifier really means ``read-only’’; an object so qualified is a run-time object which cannot (normally) be assigned to. The value of a const-qualified object is therefore not a constant expression in the full sense of the term, and cannot be used for array dimensions, case labels, and the like. (C is unlike C++ in this regard.) When you need a true compile-time constant, use a preprocessor #define (or perhaps an enum).

在C语言中，const修饰只代表只读，被const修饰的对象是一个运行时对象，通常不能被赋值。因此它不是一个常量表达式，这点和C++ 不一样。可以使用#define或者enum。
什么是常量表达式，在编译时就能获得它的值，而不是运行时。

A constant expression can be evaluated during translation rather than runtime, and accordingly may be used in any place that a constant may be.[ISO C11 Sec 6[ISO C11 Sec 6.6]

问题2-cc1和gcc的关系

C语言程序从ASCII转换到可执行目标文件分别经历了预处理器cpp，编译器cc1，汇编器as，以及链接器ld的处理，一个编译器驱动程序包含所有这几个部分，gcc是GNU编译系统上的编译驱动程序。
我在ubuntu 18.04上没有找到cc1，我的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

which gcc       # 查看gcc存放位置
#我的输出是: 
#/usr/bin/gcc
gcc --version # 查看当前gcc 版本
#我的输出是: 
#gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0,,,
cd /usr
sudo find . -name "cc1"
#我的输出是：
#./lib/gcc/x86_64-linux-gnu/7/cc1
#./lib/gcc/x86_64-linux-gnu/6/cc1
#然后根据gcc版本7.4，进入第一个目录

cp cc1 /usr/bin # 将它拷贝到和gcc相同的目录

参考文献

问题0
1.https://stackoverflow.com/questions/22319950/why-does-the-naming-convention-of-stl-use-so-many-leading-underscore
2.https://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier
3.https://stackoverflow.com/questions/1734277/name-of-c-c-stdlib-naming-convention
4.https://www.gnu.org/savannah-checkouts/gnu/libc/manual/html_node/Reserved-Names.html
5.https://isocpp.org/wiki/faq/coding-standards
问题1
1.https://stackoverflow.com/a/44268465/8939281
2.https://stackoverflow.com/a/18848583/8939281
3.http://c-faq.com/ansi/constasconst.html
问题2
1.https://unix.stackexchange.com/questions/77779/relationship-between-cc1-and-gcc
2.https://stackoverflow.com/a/51218063/8939281

构造函数

每个类都会定义它的对象被初始化的方式，类通过一个或者几个特殊的成员函数控制每个类的初始化过程,这些函数叫做构造函数。
构造函数的几个特征:

1. 构造函数的任务是初始化类对象的数据成员，无论何时只要类的对象被创建，就会执行构造函数。
2. 构造函数名字和类名相同。
3. 构造函数没有返回类型。
4. 构造函数可以有多个，和重载函数差不多。
5. 构造函数不能声明为const。当我们要创建一个const对象时,一直到构造函数完成初始化过程，对象才能获得常量属性。因此,构造函数在const对象的构造过程中可以向其写入。或者说，构造函数要更改对象，如果声明为const的话，就无法更改了。

默认构造函数

当类没有声明任何构造函数时，编译器提供一个特殊的构造函数，称为默认构造函数，默认构造函数不需要任何实参。默认构造函数的初始化规则为：如果存在类内初始值，用它初始化成员，否则使用默认初始化。
对于非常简单的类,可以使用默认构造函数,但是对于特别复杂的类,必须定义它自己的默认构造函数,有三个原因:

1. 编译器只有在发现类中不包含任何构造函数的情况下才会生成一个默认的构造函数.如果我们定义了一些其他的构造函数,那么编译器就不会提供默认构造函数了,如果需要默认构造函数需要程序员自己定义.
2. 编译器提供的默认构造函数可能指定错误的操作,因为执行默认初始化时,块中的内置类型或者复合类型的对象都是随机值,所以需要自己自己定义一个默认构造函数.
3. 编译器不能为某些类生成一个默认构造函数,如果类中包含一个其他类类型的成员,并且这个成员没有默认构造函数,那么编译器无法初始化该成员.这样的类,必须由程序员自己定义默认构造函数,否则没有可用的默认构造函数.

默认构造函数的作用

编译器生成的默认构造函数（是编译器需要）

Nontrivial default construct是编译器需要的那种构造函数，必要的话由编译器合成，它不会负责对data member进行初始化，这是程序员的责任。总共有四种nontrivial default construct：

1. 带有default constructor的member class object；
2. 带有default constructor的base class；
3. 带有virtual function的class；
4. 带有virtual base class的class。

拷贝构造函数的构建操作

有三种情况，会把一个object的内容当做另一个object的初值，即调用拷贝构造函数：

1. 用=号初始化一个对象。
2. 值传参。
3. 函数返回值。

默认memberwise的初始化

如果类没有提供explicit copy constructor，当使用类对象初始化另一个类对象时，其实是使用默认memberwise初始化完成的。
copy constructor只有在必要的时候通过编译器产生出来。

Bitwise Copy Semantics

定义构造函数

构造函数是可以重载的，一个类可以有多个构造函数。

=default的含义

=default是C++ 11标准的新用法,如果需要编译器提供的默认构造函数,在参数列表最后加上=default即可.其中,=default可以和声明一起出现在类的内部,也可以作为定义出现在类的外部.如果=default在类的内部,那么默认构造函数是内联函数,如果它在类的外部,该成员默认情况下不是内联的.

初始值列表

什么是初始值列表

在参数列表之后和花括号之前,加上冒号和一个特殊的列表,这个特殊的列表叫做构造函数初始值列表.这个列表由多个 成员变量的名字,括号括起来的成员变量初始值构成,不同成员变量的初始化通过逗号分隔开来.
如果初始值列表没有对部分或者全部数据成员变量进行初始化,那么这些的数据成员变量将根据类内初始值进行初始化,如果没有类内初始化值,执行默认初始化.

为什么要使用初始值列表？？？

初始值列表进行的是初始化，而在构造函数体内进行初始化执行的是赋值。对于引用和const对象来说，只能使用初始化，而不能使用赋值。

成员初始化的顺序

初始值列表只说明用于初始化的值，而不能限制初始化的具体顺序。成员初始化的顺序和他们在类定义中出现的顺序一致。

拷贝构造函数，拷贝赋值函数以及析构函数

这三个函数很重要，通常在含有指针成员的类中，需要定义拷贝构造函数和拷贝赋值函数。
在使用等号进行初始化，即拷贝初始化的时候，使用的是拷贝构造函数，先创建一个对象，然后调用拷贝构造函数复制这个对象到新创建的对象。
而不使用等号的初始化，也就是直接初始化时，使用的是函数匹配，即选择最合适的构造函数进行初始化。

委托构造函数

一个委托构造函数使用他所属的类中的其他构造函数执行它自己的初始化过程，或者说它把子集的一些或者全部工作委托给了其他构造函数。

explict构造函数

转换构造函数和重载函数调用运算符能够把一个类类型转换为另外一种类类型。
在需要使用某个类的对象的时候，有时候可以仅仅传递实参进入，如果该类有相应的构造函数可以创建该类对象的时候，编译器会自动的构造一个类对象参与运算。
可以通过在构造函数前面加上explict，阻止编译器隐式的调用构造函数进行转换，只有显式的调用构造函数时才可以。

explicit构造函数的性质：

1. explicit只能出现在类内部。
2. explicit只能用于直接初始化，不能用于拷贝初始化。
3. static_cast可以使用explicit构造函数。
4. 标准库中含有显示构造函数的类，接收一个容量参数的vector构造函数是explicit的。

聚合类

满足下列要求的类称为聚合类：

1. 所有成员都是public的；
2. 没有定义任何构造函数，可以定义其他函数（需要满足下面的条件）；
3. 没有指定类内初始值；
4. 没有基类，也没有virtual function。

使用初始值列表进行初始化。它的缺点：

1. 所有成员都是public
2. 让类的用户进行初始化，而不是让类的作者。
3. 添加或者删除一个成员后，所有的初始化语句都要改变。

字面值常量类

参考文献

1.《C++ Primer》第五版中文版

时间

获得时钟时间

linux的时间函数

三种获取时间的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 获得time_t或者,struct timespec或者struct timeval
// 1. 返回从1970年1月1日（UTC）开始的秒数。
time_t time(time_t *tloc);
// 2.1
// timespec -> tv_sec
int clock_gettime(clockid_t clk_id, struct timpespec *tp);
// 2.2
int clock_getres(clockid_t clk_id, struct timespec *res);
// 3.
// timeval -> tv_sec
int gettimeofday(struct timeval *tv, struct timezone *tz);

//将time_t结构化成struct tm
// 1.1
// 本地时间
struct tm *localtime(const time_t *timep);
// 1.2
// 协调世界时
struct tm *gmtime(const time_t *timep);
// 2.
// 将结构化时间转换成time_t
time_t mktime(struct tm *tm);

C的时间函数

1
2
3
4

// 1.格式化日期和时间
size_t strftime(char *s, size_t max, const char *format, const struct tm *tm);
// 2.
char *strptime(const char *s, const char *format, struct tm *tm);

获得进程时间

linux进程时间

1

clock_t clock(void);

C的进程时间

1

clock_t times(struct tms *buf);

数据结构

• struct timespec
• struct timeval
• struct tm
• struct tms
• struct timezone

struct timespec

1
2
3
4
5

struct timespec
{
    time_t tv_sec;
    long tv_nsec;
};

struct timeval

1
2
3
4
5

struct timeval
{
    time_t tv_sec;
    suseconds_t tv_usec;
};

struct tm

1
2
3
4
5
6
7
8
9
10
11

struct tm{
    int tm_sec;    /* Seconds (0-60) */
    int tm_min;    /* Minutes (0-59) */
    int tm_hour;   /* Hours (0-23) */
    int tm_mday;   /* Day of the month (1-31) */
    int tm_mon;    /* Month (0-11) */
    int tm_year;   /* Year - 1900 */
    int tm_wday;   /* Day of the week (0-6, Sunday = 0) */
    int tm_yday;   /* Day in the year (0-365, 1 Jan = 0) */
    int tm_isdst;  /* Daylight saving time */
};

struct tms

1
2
3
4
5
6
7
8

struct tms
{
    clock_t tms_utime;
    clock_t tms_stime;
    clock_t tms_cutime;
    clock_t tms_cstime;
    
};

struct timezone

1
2
3
4
5

struct timezone
{
    int tz_minuteswest;
    int tz_dsttime;
};

参考文献

1.《APUE》第三版
2.https://en.cppreference.com/w/c/chrono/timespec
3.https://www.gnu.org/software/libc/manual/html_node/Elapsed-Time.html

预处理器

预处理器是在编译之前执行的一段程序，可以部分的改变我们的程序。

include

当预处理看到#include时会用指定的头文件代替#include。

头文件保护符

头文件保护符依赖于预处理变量。预处理变量有两种状态：已定义和未定义。
#define定义一个预处理变量。
#ifdef当且仅当变量已定义为真。
#ifndef当且仅当变量未定义为真。
#ifdef或#ifndef为真之后，后续操作遇到#endif结束。

assert预处理宏

预处理宏其实是一个预处理器变量。assert就是一个预处理宏，assert定义在<cassert>头文件中。它使用一个表达式作为它的条件：

1

assert(expr);

对expr求值，如果为真，什么也不做，否则输出信息，终止程序执行。它用来检查某种错误条件，即当expr满足条件时什么也不做，当它出错时，就结束。

NDEBUG预处理变量

assert的行为依赖于一个名为NDEBUG的预处理器变量的状态。如果定义了NDEBUG，那么assert什么也不做。默认情况下没有定义NDEBUG，assert执行检查。

其他函数预处理变量

C++预处理器定义了四个对于程序调试很有用的名字：
__FILE__
__LINE__
__TIME__
__DATA__

注意：C++编译器提供了__func__变量存放函数名字。

参考文献

1.《C++ Primer》第五版

特殊语言特性

这一节介绍三种函数相关的语言特性，它们分别是默认实参，内联函数和constexpr函数，以及程序调用过程中的一些常用功能。

默认实参

默认实参是什么

默认实参是函数声明时就指定形参的值。一般某个形参被赋予了默认值，它后面的所有形参都必须要有默认值。
尽量让不怎么使用默认值的形参出现在前面，让那些经常使用默认值的形参出现在后面。

默认实参的声明

一般情况下，一个函数只声明一次，但是声明多次也是可以的。但是在一个定的作用域内，每一个形参只能被赋予一次默认实参。

1
2
3

typedef string::size_type sz;
string screen(sz , sz w, char='*'); //指定形参char的默认实参
string screen(sz h=80, sz w=80, char); //指定形参h, w的默认实参。

默认实参初始值

局部变量不能当做实参的初始值，除此之外，只要表达式的类型都够转换为形参的类型，这个表达式就可以当做默认实参。

内联函数

函数调用的代价要比表达式的代价高。一次函数调用（生成一个新的函数栈帧）包含一系列寄存器的保存和恢复，以及可能的实参拷贝，程序跳转到一个新的位置执行等等。
但是函数调用要比表达式有一些好处：

1. 阅读和理解函数调用要比等价的表达式容易
2. 函数可以重复利用，不用重复编写，使用函数可以确保行为的统一，修改也比较方便（不用找到所有等价表达式出现的地方进行替换）。

所以就有了内联函数，在函数名字前加上inline关键字就可以声明一个内联函数。内联函数可以避免函数调用的开销还有了函数的优势，通常就是将它在每个调用点上展开，相当于直接用内联函数的定义替换这个函数的名字。

constexpr函数

constexpr函数是指能用于常量表达式的函数。定义constexpr函数的方法和其他函数一样，但是函数的返回值以及所有形参的类型都必须是字面值类型，而且函数中必须有且只有一条return语句。
constexpr函数的返回值不一定是常量表达式。如果把它的返回值用在需要常量表达式的地方，编译器会进行检查。比如：

1
2
3
4
5
6
7
8

```的

**通常将内联函数和`constexpr`函数定义在头文件中。**
内联函数允许多次定义，但是每次的定义必须一致，为什么？什么是内联函数，在每个调用点上将函数内联的展开。如果有两个文件foo.cpp和bar.cpp都需要调用一个相同的内联函数myinline，在编译这两个头文件的时候，需要将函数myinline进行展开，所以它们都需要定义myinline，但是在生成目标文件的时候，因为函数是强类型，就会出错，所以内联函数允许多次一致的定义。而最简单的方法就是将内联函数定义在头文件中，然后使用它的源文件包含它即可。


## `assert`预处理宏
`assert`定义在`<cassert>`头文件中。它使用一个表达式作为它的条件：

assert(expr);

对`expr`求值，如果为真，什么也不做，否则输出信息，终止程序执行。它用来检查某种错误条件，即当`expr`满足条件时什么也不做，当它出错时，就结束。

## NODEBUG预处理变量
`assert`的行为依赖于一个名为`NDEBUG`的预处理器变量的状态。如果定义了`NDEBUG`，那么`assert`什么也不做。默认情况下没有定义`NDEBUG`，`assert`执行检查。

## 参考文献
1.《C++ Primer》第五版

函数指针

函数指针指向的是函数而不是对象。和其他指针一样，函数指针指向某种特定类型。函数的类型由它的返回值和形参共同决定，和函数名无关。例如：

1

bool lengthCompare(const string &, const string &);

这个函数的类型是bool(const string &, const string &)，要想声明一个指向该函数的指针，只需要使用指针代替函数名字即可：

1

bool (*pf)(const string &, const string &);

从声明符中的变量名字开始，pf前面有个*，所以pf是个指针，右侧是形参列表，左侧是函数的返回值类型。因此，pf是一个指向函数的指针，函数的参数是两个const string的引用，返回值是bool类型，指针类型是boo(*)(const string &, const string &)

使用函数指针

**当我们把函数名作为一个值使用时，这个函数自动的转换成指针。**如下所示的两个语句是等价的：

1
2

pf = lengthCompare;
pf = &lengthCompare;

同时，可以直接使用指向函数的指针调用函数，而不需要进行解引用运算。下面的三个语句是等价的：

1
2
3

bool b1 = pf("hello", "world");
bool b2 = (*pf)("hello", "world");
bool b3 = lengthCompare("hello", "world");

指向不同函数类型之间的指针不存在转换规则，但是可以为函数指针赋值nullptr或者0，表示它不指向任何函数。

重载函数的指针

当函数重载之后，上下文必须能够告诉编译器到底选择哪个函数，指针必须和重载函数中的某一个精确匹配。

函数指针形参

和数组类似，虽然不能定义函数类型的形参，但是形参可以是指向函数的指针。这个时候，形参看起来是函数类型，实际上是当成指针使用。
可以直接把函数作为实参使用，这个时候它会自动的转换成指针：

1
2
3
4
5
6

//第三个参数是函数类型，它会自动的转换成指向函数的指针
void useBigger(const string &s1, const string &s2, bool pf(const string &, const string &));
//第三个参数是显式声明的指向函数的指针
void useBigger(const string &s1, const string &s2, bool (*pf)(const string &, const string &));
// 函数lengthCompare会被自动的转换成函数指针
useBigger(s1, s2, lengthCompare);

使用typedef和delctype简化函数指针

可以使用下列语句定义函数指针：

1
2
3
4
5
6
7
8

//下面两个是函数类型：
typedef bool Func(const string&, const string&);
typedef delctype(lengthCompare) Func2; 


//下面两个是函数指针类型：
typedef bool (*FuncP)(const string&, const string&);
typedef delctype(lengthCompare) *FuncP2;

需要注意的是，decltype返回函数类型，不会将函数自动转换成指针类型，只有在前面加上*才能得到指针。

返回指向函数的指针

和数组类似，虽然不能返回一个函数，但是可以返回指向函数类型的指针。**然后，我们必须把返回类型手动写成指针，编译器不会自动的将函数返回类型当成对应的指针类型处理。**最好的办法是使用类型别名：

1
2

using F = int(int*, int);   //F是函数，不是指针
using PF = int(*)(int*, int);   //PF是指针类型

必须注意的是，和函数类型的形参不一样，返回类型不会自动的转换成指针，我们必须显式的将返回类型指定为指针。

auto和decltype作用于函数指针

将decltype作用于某个函数时，它返回函数类型而非指针类型，需要我们显式的加上*表示我们需要返回指针，而非函数本身。当decltype作用于函数指针时，它返回的是函数指针类型。

参考文献

1.《C++ Primer》第五版