CSAPP 2e Datalab 题解 CSAPP 是 CMU 享誉全球的课程，尤其以其 lab 难度之高著称。这是课程的第一个 lab：datalab，为了让我们熟练掌握计算机中的数据存储而设计。前言：什么是 cheating之前在 B 站上 CSAPP 第一节课，教授就说了在 CMU，作弊的定义是什么，说实话有点 shocked：Cheating: DescriptionCheating: ConsequenceCMU CSAPP 的规定是，完成 lab 的时候不可以上网查资料，只要上网搜索了，不管有没有找结果，搜索的这个过程就算作 cheating（这只是课程实验！）。一个学期有 25 人因为 cheating 受到惩罚，而且后果十分严重。看看我们的 HNU，至今没听说过有谁因为作弊而受到处分……按照这个要求，lab 做得真的非常痛苦。有些题目要想很久还想不出来。而且说实话还是有一两个题目不会做，去网上看了别人的 solution。但是这样做完的 datalab，相比直接上网一通搜索抄来的代码，确实更加有成就感，也对自己的「二进制思维」能力有更大的锻炼。这也正是这几个 lab 的意义所在吧。所以，如果你在做 datalab 而上网搜索看到了这里，在继续看下去之前，不妨再继续独立思考一下吧。本实验的一些坑dlc 这个语法检查器按照 C89/C90（ANSI C）的标准，这个标准规定所有局部变量都要在代码块的开头定义。所以如果在函数中途定义一个局部变量，虽然用 make 可以正常编译（现在的编译器很少还用 ANSI C 标准），但是用 dlc 检查则会提示 parse error 的错误。实验环境必须是旧版本的 Linux 环境（如 Ubuntu 12.04 LTS）。使用较新的发行版可能会导致无法通过 fitsBits 这一关。（目前暂不清楚是编译器还是内核等的问题，据说是本 lab 本身的一个 bug）用 docker 创建运行环境在 x86 的主机上使用 docker 创建 Ubuntu 12.04 LTS 的容器，指定将容器内 /home 目录映射到容器外的目录，然后进入容器，安装相关软件：将容器内 /home 映射到容器外 /root/Lab/HNU-CSAPP/ex2/docker-env/home，这两个目录也可以自己指定docker run -itd --name datalab -v /root/Lab/HNU-CSAPP/ex2/docker-env/home:/home ubuntu:12.04进入容器内的 shelldocker exec -it datalab /bin/bash12.04 年代久远，需要将 sources 里 archive.ubuntu.com 改为 old-reloease.ubuntu.com 才能 apt-get updatesed -i -e 's/archive.ubuntu.com|security.ubuntu.com/old-releases.ubuntu.com/g' /etc/apt/sources.list获取软件包列表apt-get update安装本实验必要的软件包apt-get install gcc make gcc-multilib回到容器外，将文件移进指定的目录（/root/Lab/HNU-CSAPP/ex2/docker-env/home），编辑好后再进入容器测试。可以用 tmux 半屏开 vim 写代码，半屏进容器终端测试。注意如果在容器外测试过了，进入容器要 make clean 再重新 make，因为不同环境编译生成的二进制可执行文件可能不兼容。bitAnd用或和非实现与，用直接取反的方法即可：x and y = not ((not x) or (not y))。getByte很显然答案是 (x >> n8) & 0xFF。但是不允许使用乘法，如何获得 n8 呢？答案是直接用加法。8 个 n 相加会超过 ops 数量限制，我们可以先加出 2n、4n。logicalShift要求实现 logical shift，因为默认的 shift 是 arithmetic shift。本质的区别在于负数的 shr，前者左边出来的是 0 而右者出来的是 1。很容易想到可以 and 上一个 keeper，这个 keeper 的值是 0000111...11，右边的 1 就是要保留的那些位。这样可以去掉左边产生的 1。如何得到这个 keeper？显然 keeper = 0x7FFFFFFF >> (n-1)。有两个问题。首先是如何产生 0x7FFFFFFF 这个数字呢？因为游戏规则规定立即数赋值不能超过 2 Byte。答案是 ~(1 << 31)。接下来是如何处理 n = 0 的情况。好在这关允许我们用 ! 运算符，可以实现类似选择赋值的语句。具体来说，我们需要这样一个 flag 变量，当 n 为 0 时它是 0x00000000，当 n 非 0 时它是 0xFFFFFFFF。试试用 ! 运算符，直接对 n 取逻辑非 notn，这样 n 为 0 时我们得到 1，n 非 0 时我们得到 0。很显然，flag = notn - 1。现在我们分别计算出 n 为 0 和不为 0 的两种情况 result1 和 result2，则最后只需要返回 ((!flag) & result1) | (flag & result2)。是不是有点像数电里的「多路复用」呢。这种对 n = 0 特判的方法，在后面的关卡中会多次遇到。最后，这关不能用 - 减法，如何实现 -1 呢？直接用加上 0xFFFFFFFF 就行啦。bitCount（这题有点难想 😨）要求统计二进制中 1 的个数（就是 popcount）。其实对于每一位是 0 是 1 我们都可以通过 and 得知，最难的就是如何累加。累加的部分可以考虑分治，要累加 32 位的结果，我们假设得到了两个 16 位的结果，只考虑这两个如何相加；要计算 16 位的结果只考虑两个 8 位的结果如何相加，以此类推。那么两个 16 位的结果如何相加呢？我们假设两个结果分别存储在 32 位 int 的高 16 位和低 16 位，只要把两个部分取出来，前者右移 16 位相加即可。下面的也类似。除此之外，题目要求使用的立即数大小不超过 0xFF，需要用一些 tricky 的手段获得我们要的立即数，以免超出符号数量限制。可以参阅代码。bang要求计算逻辑反，也就是我们要返回这样一个值，当 x 为全 0 时其为 1，x 任何一位为 1 时其为 0。理所当然地可以想到应该把 x 每一位 or 起来（或者把 ~x 每一位 and 起来），结果放在最低位，得到 1 或 0。然而如果真的取出 32 位每一位进行 or，ops 会超过限制。可以用分治的方法，先将 [0,15] 和 [16,31] 这两段按位处理放入低的一段，再处理 [0,7] 和 [8,15]，以此类推，可以在 ops 数量限制内完成。tmin返回最小的 int，就是 1 << 31。fitsBits第一种方法是一开始想的奇怪方法，至少需要用到 19 个 ops，超过题目限制，其实不能通过。要我们返回 0 或 1 表示 x 是否能被 n 位补码表示，实际上就是返回是否 −2�−1≤�≤2�−1−1−2 n−1 ≤x≤2 n−1 −1。也就是 −2�−1≤�<0−2 n−1 ≤x<0 或 0≤�≤2�−1−10≤x≤2 n−1 −1。再变换一下，就是：0≤�+2�−1<2�−10≤x+2 n−1 <2 n−1 或 −2�−1≤�−2�−1≤−1−2 n−1 ≤x−2 n−1 ≤−1。也就是如果 �<0x<0 则要满足 �+2�−1≥0x+2 n−1 ≥0；如果 �≥0x≥0 则要满足 �−2�−1≤−1x−2 n−1 ≤−1。依然根据 x 的符号位选择一个结果返回。第二种方法则是可以通过的正解：根据算数移位的性质。假设给我们一个 n 位补码表示的数，我们直接将其左移至与 32 位 int 符号位对齐，然后再移回去，得到的结果应该是和原来一样的。据此即可判断。⚠️ 这题使用较新版本的环境测试是无法通过的，目前暂不清楚与什么因素有关。在 Ubuntu 12.04 LTS x86_64 中测试可以通过。详见开头「用 docker 创建运行环境」。divpwr2要求返回 �2�2 nx​ ，向 0 取整。对于正数当然就是 >> n 即可，对于负数就有些复杂，因为 >> 运算默认向下取整，需要进行修正。对于负数，列表可以发现，每个数字在计算之前要加上 2�−12 n −1 的偏移才能得到正确答案。因为出现了 n - 1，所以还要特别考虑 n = 0 的情况。使用 logicalShift 一样的「多路复用」方法即可。negate取负数，就是 (~x)+1，很简单。isPositive根据符号位，可以轻易判断出这个数是否 >= 0。既然本题要求判断 > 0，也就是 0 是特殊情况，依然可以根据前面的方法特殊判断。isLessOrEqual判断 �≤�x≤y，不能直接判断 �−�≥0y−x≥0，因为会 overflow。可以发现如果 x 和 y 同号，肯定不会 overflow。所以只需要对异号的情况进行判断。为了更加清晰，列出一个真值表：x 符号位 y 符号位 返回值1 0 10 1 00 0 y-x 的符号位取反1 1 y-x 的符号位取反依然是个分类讨论（「多路复用」）的思路，根据 x xor y 的值返回答案，如果为 1 答案是 x 的符号位，如果为 0 答案为 y-x 的符号位取反。ilog2要求返回 log2(x) 向下取整。很显然答案就是 x 的二进制中最左边的 1（最高位）在从右往左第几位。首先通过将 x 按位或 x >> k 的手段（k 分别等于 1、2、4……），可以将 x = 0001xxxxx 变为 x = 000111111，也就是最高位之后全都变成 1。然后可以做一遍之前的 bitCount，将结果减去 1 即可。float_neg这部分终于可以用 if 了。只要判断 NaN 的情况原封不动返回，否则修改符号位返回就行。对符号位取反可以对 1<<31 取异或。可以构造两个变量 get_exp 和 get_frac 分别用于和一个数按位与，从而取出这个数中的 exp 或 frac 片段。exp 就是 0xFF << 23，frac 则是 ~exp 再对符号位取反。float_i2f要将提供的 int 值 x 转换为 float。int 和 float 关于负数的概念是截然不同的，所以我们必须对 int 的绝对值进行处理。所以首先要对于 x < 0 的情况设置符号位后直接取相反数。（此时注意特判 tmin 的情况！它没有能由 int 表示的相反数）设置好 sign 后，只要处理 exp 和 frac 即可。假设 x 是个 n 位的二进制数，exp 就等于 n - 1 + bias。frac 就是右边的 n - 1 位（左对齐）。要考虑进位问题。将 frac 被截掉的部分拿出来（最多有 8 位），如果「大于 0x80」或者「等于 0x80 且frac 末位为 1」（round to even 的情况）则要进一位，frac 连续进位。注意到 frac 有可能进位进到 exp 里，但是我们的代码里不用判断，因为 frac 最高位之前就是 exp 最低位。（在这里是不是再次感到了 IEEE 浮点数设计的精妙？）最后注意这题 0 也要特判，因为 0 属于 denomilized。这题写起来很容易超过 ops 数量限制。需要省着点用。float_twice将给出的 float 翻两倍，要分别考虑 nomalized、denomolized 和 special 的情况。nomolized 很简单，直接修改 exp 部分即可。注意可能有 nomolized 进入 infinity 的情况。denomolized 只需要修改 frac 即可。注意可能有从 denomolized 进入 nomolized 的情况，要修改 exp。最后 infinity、NaN 这两种值都原样返回，需要特判。完整代码参考/*bitAnd - x&y using only ~ and |Example: bitAnd(6, 5) = 4Legal ops: ~ |Max ops: 8Rating: 1 */int bitAnd(int x, int y) { return ~((~x) | (~y));}/*getByte - Extract byte n from word xBytes numbered from 0 (LSB) to 3 (MSB)Examples: getByte(0x12345678,1) = 0x56Legal ops: ! ~ & ^ | + << >>Max ops: 6Rating: 2 */int getByte(int x, int n) { int n2 = n + n; int n4 = n2 + n2; int n8 = n4 + n4; return (x >> n8) & 0xFF;}/*logicalShift - shift x to the right by n, using a logical shiftCan assume that 0 <= n <= 31Examples: logicalShift(0x87654321,4) = 0x08765432Legal ops: ! ~ & ^ | + << >>Max ops: 20Rating: 3 */int logicalShift(int x, int n) { int sub1 = ~0; int keeper = ~(1 << 31); int result = (x >> n) & (keeper >> (n + sub1)); int notn = !n; int flag = notn + sub1; return ((~flag) & x) | (flag & result);}/*bitCount - returns count of number of 1's in wordExamples: bitCount(5) = 2, bitCount(7) = 3Legal ops: ! ~ & ^ | + << >>Max ops: 40Rating: 4 */int bitCount(int x) { int ret = x; int mask = 0; // 0x55555555 mask = 0x55 + (0x55 << 8); mask = mask + (mask << 16); ret = (ret & mask) + ((ret>>1) & mask); // 0x33333333 mask = 0x33 + (0x33 << 8); mask = mask + (mask << 16); ret = (ret & mask) + ((ret>>2) & mask); // 0x0f0f0f0f mask = 0x0f + (0x0f << 8) + (0x0f << 16) + (0x0f << 24); ret = (ret & mask) + ((ret>>4) & mask); // 0x00ff00ff mask = 0xff + (0xff << 16); ret = (ret & mask) + ((ret>>8) & mask); // 0x0000ffff mask = 0xff + (0xff << 8); ret = (ret & mask) + ((ret>>16) & mask); return ret;}/*bang - Compute !x without using !Examples: bang(3) = 0, bang(0) = 1Legal ops: ~ & ^ | + << >>Max ops: 12Rating: 4 */int bang(int x) { int ret = ~x; ret = ret & (ret >> 16); ret = ret & (ret >> 8); ret = ret & (ret >> 4); ret = ret & (ret >> 2); ret = ret & (ret >> 1); return ret&1;}/*tmin - return minimum two's complement integerLegal ops: ! ~ & ^ | + << >>Max ops: 4Rating: 1 */int tmin(void) { return 1 << 31;}/*fitsBits - return 1 if x can be represented as ann-bit, two's complement integer.1 <= n <= 32Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1Legal ops: ! ~ & ^ | + << >>Max ops: 15Rating: 2 */int fitsBits(int x, int n) {// int sub1 = ~0;// int get_sign = 1<<31;// int sign = x & get_sign;// int not_sign = !sign;// int power = 1 << (n + sub1);// int sub_power = (~power) + 1;// int result1 = !(((x + power) & get_sign) >> 31);// int result2 = ((x + sub_power) & get_sign) >> 31;// sign = !not_sign;// return (sign & result1) | (not_sign & result2); int subn = (~n) + 1; int to_shl = 32 + subn; int x_fix = (x << to_shl) >> to_shl; int not_ans = x ^ x_fix; return !not_ans;}/*divpwr2 - Compute x/(2^n), for 0 <= n <= 30Round toward zeroExamples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2Legal ops: ! ~ & ^ | + << >>Max ops: 15Rating: 2 */int divpwr2(int x, int n) {// Round to zero is the difficult part int sub1 = ~0; int super2sub1 = (1<<n) + sub1; int notn = !n; int flag = notn + sub1; int result = (x + ((x >> 31) & super2sub1)) >> n; return ((~flag) & x) | (flag & result);}/*negate - return -xExample: negate(1) = -1.Legal ops: ! ~ & ^ | + << >>Max ops: 5Rating: 2 */int negate(int x) { return (~x) + 1;}/*isPositive - return 1 if x > 0, return 0 otherwiseExample: isPositive(-1) = 0.Legal ops: ! ~ & ^ | + << >>Max ops: 8Rating: 3 */int isPositive(int x) { int sub1 = ~0; int notx = !x; int flag = notx + sub1; int result = !(x >> 31); return flag & result; // return ((~flag) & 0) | (flag & result); // the first part isn't necessary}/*isLessOrEqual - if x <= y then return 1, else return 0Example: isLessOrEqual(4,5) = 1.Legal ops: ! ~ & ^ | + << >>Max ops: 24Rating: 3 */int isLessOrEqual(int x, int y) { int xxory = (x >> 31) ^ (y >> 31); int subx = (~x) + 1; int ysubx = y + subx; int result_1 = (x >> 31) & 1; int result_2 = !(ysubx >> 31); return (xxory & result_1) | ((~xxory) & result_2);}/*ilog2 - return floor(log base 2 of x), where x > 0Example: ilog2(16) = 4Legal ops: ! ~ & ^ | + << >>Max ops: 90Rating: 4 */int ilog2(int x) { int sub1 = ~0; int x_fill = x; int ret, mask; x_fill |= x_fill >> 1; x_fill |= x_fill >> 2; x_fill |= x_fill >> 4; x_fill |= x_fill >> 8; x_fill |= x_fill >> 16;// perform bitCount ret = x_fill; mask = 0; // 0x55555555 mask = 0x55 + (0x55 << 8); mask = mask + (mask << 16); ret = (ret & mask) + ((ret>>1) & mask); // 0x33333333 mask = 0x33 + (0x33 << 8); mask = mask + (mask << 16); ret = (ret & mask) + ((ret>>2) & mask); // 0x0f0f0f0f mask = 0x0f + (0x0f << 8) + (0x0f << 16) + (0x0f << 24); ret = (ret & mask) + ((ret>>4) & mask); // 0x00ff00ff mask = 0xff + (0xff << 16); ret = (ret & mask) + ((ret>>8) & mask); // 0x0000ffff mask = 0xff + (0xff << 8); ret = (ret & mask) + ((ret>>16) & mask); return ret + sub1;}/*float_neg - Return bit-level equivalent of expression -f forfloating point argument f.Both the argument and result are passed as unsigned int's, butthey are to be interpreted as the bit-level representations ofsingle-precision floating point values.When argument is NaN, return argument.Legal ops: Any integer/unsigned operations incl. ||, &&. also if, whileMax ops: 10Rating: 2 */unsigned float_neg(unsigned uf) { unsigned change_sign = 1 << 31; unsigned get_exp = 0xFF << 23; unsigned get_frac = (~get_exp) ^ change_sign; if ((uf & get_exp) == get_exp && (uf & get_frac) != 0) return uf; return uf ^ change_sign;}/*float_i2f - Return bit-level equivalent of expression (float) xResult is returned as unsigned int, butit is to be interpreted as the bit-level representation of asingle-precision floating point values.Legal ops: Any integer/unsigned operations incl. ||, &&. also if, whileMax ops: 30Rating: 4 */unsigned float_i2f(int x) { int bias = 127; unsigned get_frac = 0x007fffff; unsigned get_frac_cut = 0x000000ff; unsigned tminf = 0xcf000000; int fix_x, n, nsub1, temp; unsigned sign, exp, frac, frac_cut;// special cases if (x == 0x80000000) return tminf; if (x == 0) return 0;// get abs / get sign fix_x = x; sign = 0; if (fix_x < 0) fix_x = -fix_x, sign = 0x80000000;// get count n = 0; temp = fix_x; while (temp) n++, temp>>=1; nsub1 = n - 1; //printf("count=%d\n",count);// get exp exp = ((nsub1 + bias) << 23);// get frac if (nsub1 <= 23){frac = (fix_x << (23 - nsub1)) & get_frac;} else {frac = (fix_x >> (nsub1 - 23)) & get_frac; frac_cut = (fix_x << (31 - nsub1)) & get_frac_cut; if ((frac_cut > 0x80) || (frac_cut == 0x80 && (frac & 1))) frac++; // carry}return sign + exp + frac;}/*float_twice - Return bit-level equivalent of expression 2*f forfloating point argument f.Both the argument and result are passed as unsigned int's, butthey are to be interpreted as the bit-level representation ofsingle-precision floating point values.When argument is NaN, return argumentLegal ops: Any integer/unsigned operations incl. ||, &&. also if, whileMax ops: 30Rating: 4 */unsigned float_twice(unsigned uf) { unsigned neg_inf = 0xff800000; unsigned pos_inf = 0x7f800000; unsigned get_exp = 0x7f800000; unsigned get_frac = 0x007fffff; unsigned exp = (uf & get_exp) >> 23; unsigned frac = uf & get_frac; unsigned ret = uf; if (exp == 0xff) return uf; if (exp == 0){ // denomolizedif (frac & (1<<23)){ // de -> no ret = ret | (1 << 23); return ret; } else { ret = ret - frac; frac = frac << 1; ret = ret + frac; return ret; }} else { // nomolizedret = ret - (exp << 23); exp++; if (exp > 0xff) { // no -> inf if (uf & (1<<31)) return neg_inf; else return pos_inf; } ret = ret + (exp << 23); return ret;}}

部署 Memos 接入 QQ 机器人 前几天部署了开源的浮墨笔记（flomo）替代品：Memos。这个项目已经有了 Android、iOS 客户端、浏览器拓展等等一系列生态。但是对比原版的浮墨笔记，少了 QQ / 微信的接入对于我来说不太方便。Memos 提供了简便的 API，我们可以自己动手，部署一个 QQ 机器人。前置准备服务器，最好是境内的。搭建好的 Memos 实例（我的实例：memos.skywt.cn）。一个可登录的闲置 QQ 账号。运行 go-cqhttp我们的机器人在服务端分为两个组件，这两个组件都要部署在我们的服务器上。go-cqhttp 负责与腾讯 QQ 服务器通信，管理我们的账号登录、消息收发等过程；NoneBot 负责将 go-cqhttp 收到的消息进行处理，控制发送消息的内容，运行我们想要的业务逻辑。首先部署 go-cqhttp。前往 GitHub 上的 release 下载最新适合服务器架构的版本，下载解压之后是一个单文件程序。第一次运行，在提示选择通信方式时，选择「反向 Websocket 通信」，之后程序就会在相同目录下生成配置文件。编辑配置文件，根据提示将 uin 和 password 字段分别改为自己的 QQ 和密码。虽然配置文件中说「密码为空时可以使用扫码登录」，但是经过实测只有在同一网络环境下 QQ 才会允许扫码登录。部署在服务器上扫码是无法登录的，只能使用密码。除此之外，修改文件底部 servers 部分 ws-reverse 中 universal 的地址。我设定的是 ws://127.0.0.1:8989/ws/。这个地址告诉 go-cqhttp，该从哪里与后端的 NoneBot 通信。修改完毕后，再次启动 go-cqhttp，可能会提示需要扫码、滑块验证、手机验证之类，跟着程序的提示进行即可。程序会提示，对于腾讯云的服务器需要修改 DNS 为 114.114.114.114。编辑 /etc/resolv.conf 并修改就行。出现以下消息就表明登录成功：此时可能会出现大量的「Connection Refused」消息，这是因为我们还没启动后端的 NoneBot。忽略他们即可。接下来，要将 go-cqhttp 放到后台运行，开始编写 NoneBot 的主程序。编写运行 NoneBot参阅 NoneBot 的官方指南编写主要的代码，包括 bot.py 和 config.py。在后者中要指定与 go-cqhttp 的 config.yml 中配置一致的 HOST 和 PORT。我的配置分别是 127.0.0.1 和 8989。接下来，我们可以通过编写插件的方式使 QQ 机器人实现 Memo 备忘录的功能。其实直接根据文档里的插件修改一下就可以了：from nonebot import on_command, CommandSessionimport requestsimport jsonplugin_name = 'Memos'plugin_usage = r"""memo [需要添加的 Memo 内容]"""MEMOS_API = 'https://memos.skywt.cn/api/memo?openId='@on_command('memo', aliases=('note'))async def memo(session: CommandSession):memo_text = session.current_arg_text.strip() if not memo_text: await session.send('Memo 内容不能为空！') return ret = await send_memo(memo_text) await session.send(ret) async def send_memo(memo_text: str) -> str:data_to_send = {'content': memo_text} r = requests.post(MEMOS_API, data=json.dumps(data_to_send)) if r.status_code == 200: return '添加成功' else: return '添加失败，请查阅日志'回到 NoneBot 的主目录启动 bot.py 并放在后台，发送消息 memo 这是一条测试笔记，可以看到正确的输出。进入 Memos 可以看到成功添加了一条 memo。聊天界面，机器人回复添加成功参考资料go-cqhttp 使用指南NoneBot 使用指南：文档通俗易懂，强烈推荐

欢迎使用 Typecho 如果您看到这篇文章,表示您的 blog 已经安装成功.