Posts

1 语言处理器(language processor) language processor可以分为两种, 一种是编译器(compiler), 一种是解释器(interpreter). 编译器(compiler) 是将一种语言转换为另一种语言, 通常是高级语言向low-level语言转换. 在转化过程中如果有错误要向用户报告这个错误. 如果这个low-level语言是可执行的机器语言那它还可以被用户执行. 解释器(interpreter) 是另一类的language processor, 它不会将高级语言编译成low-level语言来执行, 而是直接执行该高级语言. 通常来说, 编译型语言要比解释型语言运行快, 但解释型语言可以更好的检查错误, 因为很多runtime error在编译期很难检测出来. 接下来主要以编译器为主进行介绍, 首先看一下编译器在编译一个文件时的流程图. 根据上图可以看出编译器在将源程序编译目标程序时是分步骤完成的: 预处理(preprocess) 编译(compile) 汇编(assemble) 链接(link) 加载(load) 预处理器(preprocessor) 的作用就是将这些分散的文件聚集起来和将替换文件中的宏(macros), 将结果传递至下一个阶段(编译). 编译器(compiler) 的作用就是将预处理器的结果转化成汇编语言(assembly language), 但是也可以直接转化为机器码, 这样也就可以跳过第3步的汇编阶段了, 但是因为汇编语言也是有语义的语言因此转化起来效率高, 且汇编器的效率也很高, 因此比较典型的编译型语言(C, C++)都是先转成汇编再编译为机器码. 且汇编语言debug也比较简单. 汇编器(assembler) 的作用是将上一步产生的汇编程序转换为可重定位机器码(relocatable machine code). Relocatable code is software whose execution address can be changed. ...

n balls with N different colors, number of balls with each color is same, randomly choose k balls from the n balls, the expected number of colors of the k balls can be estimated as: $$ N\left [ 1-\prod_{r=1}^{k} \left ( \frac{\frac{n(N-1)}{N}-r+1}{n-r+1} \right ) \right ] $$ 证明 要算取出的k个球的颜色数的期望, 根据期望的定义来算的话太复杂了. 因此, 可以先构造一个0-1分布, 取出的球中不包含一种颜色的情况用0表示, 则包含这种颜色的情况用1表示. 可以轻易的求出取出的球中不包含一种颜色的概率为: $$ P_{0}=\frac{C_{n - \frac{n}{N}}^{k}}{C_{n}^{k}}=\frac{(n-\frac{n}{N})(n-\frac{n}{N}-1)\cdots(n-\frac{n}{N}-k+1)}{n(n-1)\cdots(n-k+1)}=\prod_{r=1}^{k}\frac{\frac{n(N-1)}{N}-r+1}{n-r+1} $$ 易得$P_1=1-P_0$, 则该事件的期望为: $$ E_{0-1}=0\times P_0 + 1\times P_1=1-P_0=1-\prod_{r=1}^{k}\frac{\frac{n(N-1)}{N}-r+1}{n-r+1} $$ 而对于取出k个球中颜色数的数学期望, 可以先对N个不同的颜色编号$1\cdots N$, 利用上面的0-1分布, 设1号颜色的0-1分布为{0, 1}, 2号颜色的0-1分布为{0, 1}, …, N号颜色的0-1分布为{0, 1}(彼此为相互独立事件, 非互斥事件). ...

文中代码 对于如下代码: int array[] = { 0, 1, 2, 3, 4 }; printf("%p\n", &array); printf("%p\n", array); 可以看到输出的地址是相同的. 而对于如下代码: int **array = (int **)malloc(sizeof(int *) * 5); for (int i = 0; i < 5; i++) array[i] = (int *)malloc(sizeof(int)); printf("%p\n", &array); printf("%p\n", array); 可以看到输出的地址是不同的. 其实对于这一段代码是没有任何疑问的, 可以很轻松的 明白为什么输出的地址不同. 那么编译器是如何处理第一部分代码，使输出的地址相同的。 可以通过gdb调试可以很清晰的看到编译器是如何处理这种情况的。 int array[] = { 0, 1, 2, 3, 4 }; void *a1 = (void *)&array, *a2 = (void *)array; 可以看到void这一行的汇编代码为: 0x565561e4 <main+71>: lea 0x8(%esp),%eax 0x565561e8 <main+75>: mov %eax,(%esp) 0x565561eb <main+78>: lea 0x8(%esp),%eax 0x565561ef <main+82>: mov %eax,0x4(%esp) 0x565561f3 <main+86>: mov $0x0,%eax 可以看到不管是 array 还是 &array 的操作都是使用的 lea 操作将 0x8(%esp) 移动到 %eax 中然后在 mov 操作赋值到相关变量中. 而对于另一段代码: int **array = (int **)malloc(sizeof(int *) * 5); for (int i = 0; i < 5; i++) array[i] = (int *)malloc(sizeof(int)); void *a1 = (void *)&array, *a2 = (void *)array; 0x56556214 <main+103>: lea -0x2c(%ebp),%eax 0x56556217 <main+106>: mov %eax,-0x24(%ebp) 0x5655621a <main+109>: mov -0x2c(%ebp),%eax 0x5655621d <main+112>: mov %eax,-0x20(%ebp) 0x56556220 <main+115>: mov $0x0,%eax 可以看到在为 a2 赋值是使用的是 mov 指令而不是 lea 指令. ...

开始 下面提到的变量均是在 main 函数中申请的变量。 文中代码 1. 二维数组 首先讨论二维数组, 他在内存中的布局是最简单的, 考虑如下变量 char str[][5] = { "jiao", "_shi", "_jie", }; 可以通过如下代码打印各个部分的地址 printf("str addr: %p\n\n", &str); for (int i = 0; i < 3; i++) { printf("str[%d] addr: %p\t", i, &str[i]); } printf("\n\n"); for (int i = 0; i < 3; i++) { for (int j = 0; j < 5; j++) { printf("str[%d][%d] addr: %p\n", i, j, &str[i][j]); } printf("\n"); } 可以看到地址从str[0][0]开始到结束是从低到高连续的。因为是在main函数中申请的 这个二维数组，因此它被存储在栈空间中(栈空间地址是高地址到低地址走的)，存储布局 大致如下： 2. 指针的指针 使用如下代码申请指针的指针的空间: char **d_ptr = (char **)malloc(sizeof(char *) * 3); for (int i = 0; i < 3; i++) { d_ptr[i] = (char *)malloc(sizeof(char) * 5); } memcpy(d_ptr[0], "jiao", 5); memcpy(d_ptr[1], "_shi", 5); memcpy(d_ptr[2], "_jie", 5); 使用如下代码输出各个部分的地址: printf("d_ptr addr: %p\n\n", &d_ptr); for (int i = 0; i < 3; i++) { printf("d_ptr[%d] addr: %p\n", i, &d_ptr[i]); } printf("\n\n"); for (int i = 0; i < 3; i++) { for (int j = 0; j < 5; j++) { printf("d_ptr[%d][%d] addr: %p\n", i, j, &d_ptr[i][j]); } printf("\n"); } 可以看到只有d_ptr的地址是在栈空间中的, 其余部分均是在堆空间中. ...

Introduction 第一次的源代码阅读, 可能解释的不是很好, tinyhttpd网上都说是一个不错的学习源代码的例子， 所以就用这个上手了。 tinyhttpd官方源码在这里下载 我的代码在这里 一些改动: 将cgi程序由perl语言改为python3 函数说明 startup() 初始化服务端套接字, 如果端口号没有指定，则使用随机的端口号 error_die() 打印服务端启动过程中的错误信息, 并退出程序 accept_request() 处理客户端请求 获取请求类型(GET or POST) 获取客户端要的网页文件的路径 使用stat()函数获取文件属性，判断是执行cgi还是发送普通网页 get_line() 获取网络字符串的一行(换行符为: \r\n ) unimplemented() 客户端请求不正确时(服务器不支持的请求)，发送给客户端501错误 not_found_file() 客户端请求网页内容不存在返回该函数404 cannot_execute() 不能执行cgi文件 bad_request() 客户端请求错误 serve_file() 发送网页文件到客户端 execute_cgi() 执行cgi文件并将结果发送到客户端 cgi介绍 cgi(Common Gateway Interface)规定Web服务器调用其他程序的接口协议(就是如何调用程序， 传递参数， 输出结果), 详细的cgi简介. cgi接口使用标准输入、标准输出和环境变量来交换数据 该程序中使用的环境变量: REQUEST_METHOD: 浏览器请求方法 CONTENT_LENGTH: post请求时的form表单的内容长度 QUERY_STRING: get请求时form表单的内容放到该环境变量中 cgi从标准输入中获取数据，把数据输出到标准输出 Linux系统函数 pipe()进程见通信的一种实现方法 // file_pipe[0] 为读取端(输出端), file_pipe[1]为写入端(输入端) int file_pipe[2]; pipe(file_pipe); fork()创建线程函数 int ipid = fork(); // 创建线程 if(ipid == 0) { // 子线程 } else { // 主线程 } dup2()重定向一个文件描述符 /** * stdin:0, stdout:1 * 下面两句将重定向stdin和stdout到file[0], 和file[1] */ dup2(file[0], 0); dup2(file[1], 1); putenv()设置环境变量(只在该进程中生效) execl()在该进程中执行外部程序 // 程序绝对路径 程序名称 参数 目标 NULL execl("/bin/ls", "ls", "-al", "/etc/passwd", NULL); Notes: 该函数执行时，会用这个新的进程替代当前进程就是该函数执行完后，就会退出整个进程，而不会执行下面的代码, 所以通常使用子线程执行该函数