Linux

首先需要安装一下额外的工具包，一个是 libc6-dbg，这是带有debug symbol信息的 libc.so；另一个是libc6-dev，这是glibc的源代码，获取之后我们就可以在gdb中查看代码了。 在Ubuntu/Debian 系统上，我们可以通过以下2条命令获得： $sudo apt-get install libc6-dbg $sudo apt-get source libc6-dev 在Fedora/Red Hat 系的OS上，需要安装的软件包的名字不叫 libc6-dbg，libc6-dev，貌似应该是glibc-debuginfo。 之后，以一段小程序为例来演示整个过程，小程序包含了一个系统调用fork()，一个库函数printf() int main(){ pid_t son; if((son=fork())==0) printf("I am son\n"); else printf("I am farther\n"); return 0; } 接着，编译产生带有调试信息的可执行文件 $gcc -g -o f fork.c 然后开启gdb调试 $gdb fork 在开始调试之前，需要指定一下刚刚获得的带有libc6-dev源码文件夹的路径，比如我把这些源码放在了 ~/glibc/lib 文件夹下，通常一般程序需要的是stdio-common这个目录内的文件， 于是输入 (gdb) directory ~/glibc/lib/stdio-common 注意看其中几条命令的用法。 程序在调用fork函数后，其实执行的是glibc包装过的__libc_fork ，并且我们可以查看其源代码。 这里有几个常用命令： s 单步执行； list 查看源代码； start 程序开始执行，并在main函数处停下，相当于在main处加断点。 但是在执行了几步之后出现了这样的错误： _IO_list_lock () at genops.c:1299 1299 genops.c: No such file or directory. in genops.c ...

时间倒回到2011年5月的一天，大学的最后一门课《计算机信息安全技术》，讲到《缓冲区溢出》这一章，并且给出了一段示例代码来演示缓冲区溢出，回到宿舍后出于好奇我运行了一下这段代码，发现结果并不是书上所说的那样，当时在人人网也发过一篇吐槽的日志，但是一直拖到现在都没有仔细的去研究过，正好现在十一放假没事，就花点时间搞搞啦。 书第136页-137页。代码如下，出于简单考虑（其实书上的C++代码格式也是错的），我除去了头文件和cout函数，这样就跟纯C语言代码是一样了。 void function(int a) { char buffer[5]; char *ret; ret = buffer + 12; *ret += 8; } int main() { int x; x = 10; function(7); x = 1; return 0; } 书上说最后x的值是10，不是1，而我的结果恰恰相反。 接着用gcc产生汇编代码，在这里用 gcc -O0 -S命令告诉编译器不采用任何优化措施，产生最原始的汇编代码，这样有利于我们分析，即使是采用-O1级优化的时候，汇编代码已经很难读了，大家可以试一试。 function: pushl %ebp movl %esp, %ebp subl $16, %esp leal -9(%ebp), %eax addl $12, %eax movl %eax, -4(%ebp) movl -4(%ebp), %eax movzbl (%eax), %eax addl $8, %eax movl %eax, %edx movl -4(%ebp), %eax movb %dl, (%eax) leave main: pushl %ebp movl %esp, %ebp subl $20, %esp movl $10, -4(%ebp) movl $7, (%esp) call function movl $1, -4(%ebp) leave ret 书上详细的解释了为什么结果是10，下面我来逐条分析。首先画一张内存图，同样处于简洁考虑，只画function函数附近的内存分布，不影响分析。 ...

Table {:toc} 问题 有一个数组 31,-41,59,26,-53,58,97,-93,-23,84 。现在要求出它的连续子串的最大值。 比如，31,-41,59,26是它的一个连续的子串，他们的和为75。但是75并不是最大值，有一个子串 59,26,-53,58,97它们的和187才是最大的。 解答 《Programming Pearls》第77页开始一共给出了4种解法，前两种非常简单，是大多数人思考几分钟就能想出的方法，但是复杂度却很高，分别为O(n^3)和O(n^2)。后两种解法则非常巧妙，更神奇的是第四种方法居然只有线性复杂度O(n) 解法1、解法2略。 解法 3：分治法 复杂度为O(nlogn)。 分治法在结构上是递归的，在保证不改变原问题的条件下，将问题的规模减小，生成多个子问题，并多次递归调用自身来解决子问题，之后再将子问题的求解结果合并成原问题的解。 对于case1，我们只要比较 ma 和 mb 的大小就可以得出原数组的最大子串的和了。 对于case2, 只要把ma和mb相加即可。以上只是将问题一次分解的过程，我们还需要将问题再分解直到不能在分解或是能直接得出结果为止。 什么时候能直接得出结果？当子数组只有一个元素的时候，此时ma就是它本身（为负数时我们让它为0）。 因此，原数组的最大和 = 2个子数组中最大和的较大者，或者，包括中间分界线的一段连续区域的和。 即，maxsum(orignial)=max(mc，maxsum(a)，maxsum(b)) 递归结束的条件是，子数组只有一个元素，如果是正返回它本身，为负返回0 代码如下。 int maxSubArray(std::vector<int>& nums) { return maxsum(nums, 0, nums.size()-1); } int maxsum(std::vector<int> &nums, int left, int right) { if (left > right) { return 0; } if (left == right) { return nums[left]; } int mid = (left + right)/2; int left_max = INT_MIN, right_max = INT_MIN; int tmp_max = 0; for (int i = mid; i >= left; i--) { tmp_max += nums[i]; left_max = std::max(left_max, tmp_max); } tmp_max = 0; for (int i = mid+1; i <= right; i++) { tmp_max += nums[i]; right_max = std::max(right_max, tmp_max); } return std::max(left_max+right_max, std::max(maxsum(nums, left, mid), maxsum(nums, mid+1, right))); } 解法4：扫描法 一次扫描数组即可得出答案，复杂度O(n)。这种方法用文字描述不容易说清楚，下面用每一步运算的图示来表达。伪代码如下： ...