C 语言学习笔记(前言及第一章)

前言

距离上次写博客已经一年了。

上次写的博客在一年的时间里,起到了一定的效果。当时主要有两个目标,一是换一份满意的工作,二是展开数位文艺生活。订完目标之后没有几个月,工作就换好了;但是数位文艺生活迟迟没有展开。

考展开失败原因,我觉得是 C 语言没有学好。

虽然我经常吹牛,号称八岁编程,其实用的是 QBASIC 。号称初一默写排序搜索,其实用的是 Pascal ,而且不会字符串匹配。

更加危机的是,我在工作上也得到了一些经验。产品方面安排下任务来,就明白七八分,有时候十二分,透彻。万一实在处理不了,就推给领导,他处理好了我再拿走,马上就能学会。工作陷入安定。

必须自己想办法突破了。

中学时我曾读过侯捷先生的《深入浅出 MFC 》,虽然书的内容没有看懂,但是序言中的一句话记忆至今:勿在浮沙筑高台。我个人本身也是基础薄弱,写起程序来总觉得内心有愧,正好借着这次突破自我的机会,认真学习一下基础知识,顺便展开数位文艺生活。

愿计算机原理眷顾每一位程序员。谢谢!

第一章 环境配置、编译及调试入门

下面我会介绍如何在 Mac 上搭建一个基本的 C 语言学习环境。

入门的话我还是推荐大家用 IDE 。IDE 我选择 Xcode ,在支持 GCC 标准的同时,可以取得最好的系统兼容性。同时集成调试功能,配置也最简单。Xcode 可以在 App Store 中免费获取。

但是对于有些小工程,比如为学习算法而写的 Demo ,其实完全可以手动编译、手动调试。既能加深对程序本身的认识,同时可以获得乐趣。

接下来我会展示如何部署一个手动的环境。

编辑器我选择 vim ,因为 vim 被广泛地集成在各种 *nix 环境中,适应性比较强。当然你可以选择任何文本编辑器。

~/.vimrc 中加入以下内容,打开缩进功能和语法高亮。

1
2
3
4
5
6
7
8
9
filetype plugin indent on
" show existing tab with 4 spaces width
set tabstop=4
" when indenting with '>', use 4 spaces width
set shiftwidth=4
" On pressing tab, insert 4 spaces
set expandtab

syntax on

编译器和调试器我选择 Clang 和 LLDB ,iOS 和 OS X 的标准环境。

下面我们以一个快速排序的 Demo 作为例子,讲一下如何用命令行工具编译及调试。首先写程序:在终端键入 vi QuickSort.c ,把快排的程序写进去。
快速排序实现
输入 :wq 保存退出。然后,用 Clang 编译这个程序:

cc QuickSort.c -o QuickSort.out

编译成功通过。如果失败了,就会看到 Clang 给出的错误信息。业界第一清楚的错误信息哦。然后我们输入 ./QuickSort.out 运行看看。
BUG
显然结果不对。那么大的数,肯定是程序跑飞了,把不知道哪里的内存给读出来了。于是我们打开 LLDB ,开始调试程序。

在命令行键入 lldb ./QuickSort.out ,成功载入后,准备设置一个断点。经过分析,源代码中 main() 函数问题不大,将问题出现的区域锁定在 QuickSort 函数中。于是在 LLDB 控制台输入:

1
2
(lldb) b QuickSort
Breakpoint 1: where = QuickSort.out`QuickSort, address = 0x0000000100000ca0

可以看到设置了一个在 QuickSort 入口的断点。在控制台输入 r ,运行程序,成功地断在了 QuickSort 函数的入口点处。
LLDB 断点功能
LLDB 默认显示4行程序,太短了。在控制台输入:

(lldb) set set stop-disassembly-count 100

让它变长一些。再在控制台打 f ,显示当前运行的帧:
LLDB 设置显示 100 行
这样就好看多了。

先来简单介绍一下程序的前6行:

1
2
3
4
5
6
7
8
frame #0: 0x0000000100000ca0 QuickSort.out`QuickSort
QuickSort.out`QuickSort:
-> 0x100000ca0 <+0>: pushq %rbp
0x100000ca1 <+1>: movq %rsp, %rbp
0x100000ca4 <+4>: subq $0x30, %rsp
0x100000ca8 <+8>: movq %rdi, -0x8(%rbp)
0x100000cac <+12>: movl %esi, -0xc(%rbp)
0x100000caf <+15>: movl %edx, -0x10(%rbp)

这几行程序是一个标准的函数入口。首先保护现场, pushq %rbp 将原栈顶指针入栈保护好,然后 movq %rsp, %rbp 将栈底指针赋给 rbp ,作为新的栈顶指针。然后执行 subq $0x30, %rsp 在栈上开辟大小为0x30的空间,由于栈是从高到低向下生长所以这里是减法。根据苹果 AMD64 平台的调用约定,函数的前三个参数分别存放在 rdirsirdx 中。这段程序的后三条指令即是把这三个参数依次入栈。虽然我之前没有接触过 Mac ,也没有接触过 AT&T 格式汇编,但是这段程序和 Windows 上面是一模一样的。

我的 QuickSort 函数是这样写的:

void QuickSort(int arr[], int lo, int hi)

可见第一个参数是要排序的数组。结合刚才函数入口的信息,可以发现这个数组被保存在了 [rbp + (-0x8)] 。程序的 BUG 是数组被写坏了,因此先在源代码中找到所有写数组的操作,如下:

1
2
3
4
    if (i < j) swap(&arr[i], &arr[j]);
}
arr[lo] = arr[i];
arr[i] = arr[x];

整个程序中只有这三个地方操作了数组。我们在反汇编结果中找到这三行程序:
操作数组的地方
蓝色区域的上方是调用 swap 函数之前的准备。下方是调用 QuickSort 函数的准备。问题就在蓝色区域当中。经过对源代码的分析,swap 函数不太可能出错,于是重点分析下面的操作:

1
2
3
4
5
6
7
8
9
10
11
12
0x100000db0 <+272>: movslq -0x14(%rbp), %rax
0x100000db4 <+276>: movq -0x8(%rbp), %rcx ; rcx = arr
0x100000db8 <+280>: movl (%rcx,%rax,4), %edx
0x100000dbb <+283>: movslq -0xc(%rbp), %rax
0x100000dbf <+287>: movq -0x8(%rbp), %rcx
0x100000dc3 <+291>: movl %edx, (%rcx,%rax,4) ; 写数组
0x100000dc6 <+294>: movslq -0x1c(%rbp), %rax
0x100000dca <+298>: movq -0x8(%rbp), %rcx ; rcx = arr
0x100000dce <+302>: movl (%rcx,%rax,4), %edx
0x100000dd1 <+305>: movslq -0x14(%rbp), %rax
0x100000dd5 <+309>: movq -0x8(%rbp), %rcx
0x100000dd9 <+313>: movl %edx, (%rcx,%rax,4) ; 写数组

根据前面的分析,数组被装进了 [rbp + (-0x8)] ,不难发现数组的首地址被装进了 rcx(见注释)。随后也就能定位到写数组的地方(见注释)。AT&T 格式汇编的寻址操作这样定义的:

(base, index, scale) = base + index * scale

比 Intel 格式难看太多了。因此两个写数组的语句翻译过来就是:

movl %edx, (%rcx,%rax,4) ; 写数组

arr[rax * 4] = edx

分别在这两行的地址上下断点:

1
2
3
4
(lldb) b 0x100000dc3
Breakpoint 2: where = QuickSort.out`QuickSort + 291, address = 0x0000000100000dc3
(lldb) b 0x100000dd9
Breakpoint 3: where = QuickSort.out`QuickSort + 313, address = 0x0000000100000dd9

控制台输 c 继续运行。随后断在第一个断点处。在控制台输入:

1
2
(lldb) p $edx
(unsigned int) $0 = 14

打出 edx 的值,14,没毛病。再打 c 继续运行,断在第二个断点。在控制台打:

1
2
(lldb) p $edx
(unsigned int) $1 = 1606417256

这什么玩意?读到这么大一个数,毛病就在这。翻回源代码看对应的操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void QuickSort(int arr[], int lo, int hi) {
if (lo < hi) {
int i = lo, j = hi, x = arr[lo];
while (i < j) {
while (i<j && arr[j]<=x) j--;
while (i<j && arr[i]>=x) i++;
if (i < j) swap(&arr[i], &arr[j]);
}
arr[lo] = arr[i];
arr[i] = arr[x];
QuickSort(arr, lo, i-1);
QuickSort(arr, i+1, hi);
}
}

出问题的地方对应的源代码是这里:arr[i] = arr[x]; ,其中 x 是从数组中取出来的哨兵值,我把它当成下标用了。把这行改成 arr[i] = x; ,重新编译运行:
BUG 解决
这样结果就对了!

以上过程根据真实情况改编。真实情况是:数组写坏了,有三个地方写数组,然后一眼就看出第三个写错了,连调试器都没开。开调试器主要还是为了节目效果。