CSAPP 是 CMU 享誉全球的课程,尤其以其 lab 难度之高著称。这是课程的第一个 lab:datalab,为了让我们熟练掌握计算机中的数据存储而设计。

前言:什么是 cheating

之前在 B 站上 CSAPP 第一节课,教授就说了在 CMU,作弊的定义是什么,说实话有点 shocked:

Cheating: Description

Cheating: Consequence

CMU CSAPP 的规定是,完成 lab 的时候不可以上网查资料,只要上网搜索了,不管有没有找结果,搜索的这个过程就算作 cheating(这只是课程实验!)。
一个学期有 25 人因为 cheating 受到惩罚,而且后果十分严重。看看我们的 HNU,至今没听说过有谁因为作弊而受到处分……

按照这个要求,lab 做得真的非常痛苦。有些题目要想很久还想不出来。而且说实话还是有一两个题目不会做,去网上看了别人的 solution。但是这样做完的 datalab,相比直接上网一通搜索抄来的代码,确实更加有成就感,也对自己的「二进制思维」能力有更大的锻炼。这也正是这几个 lab 的意义所在吧。

所以,如果你在做 datalab 而上网搜索看到了这里,在继续看下去之前,不妨再继续独立思考一下吧。

本实验的一些坑

用 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
# 进入容器内的 shell
docker exec -it datalab /bin/bash
# 12.04 年代久远,需要将 sources 里 archive.ubuntu.com 改为 old-reloease.ubuntu.com 才能 apt-get update
sed -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 >> n*8) & 0xFF。但是不允许使用乘法,如何获得 n*8 呢?
答案是直接用加法。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^{n-1} \le x \le 2^{n-1}-1$。
也就是 $-2^{n-1} \le x \lt 0$ 或 $0 \le x \le 2^{n-1}-1$。
再变换一下,就是:$0 \le x+2^{n-1} < 2^{n-1}$ 或 $-2^{n-1} \le x-2^{n-1} \le -1$。
也就是如果 $x < 0$ 则要满足 $x+2^{n-1} \ge 0$;如果 $x \ge 0$ 则要满足 $x-2^{n-1} \le -1$。依然根据 x 的符号位选择一个结果返回。

第二种方法则是可以通过的正解:

根据算数移位的性质。假设给我们一个 n 位补码表示的数,我们直接将其左移至与 32 位 int 符号位对齐,然后再移回去,得到的结果应该是和原来一样的。据此即可判断。

⚠️ 这题使用较新版本的环境测试是无法通过的,目前暂不清楚与什么因素有关。在 Ubuntu 12.04 LTS x86_64 中测试可以通过。详见开头「用 docker 创建运行环境」。

divpwr2

要求返回 $\frac{x}{2^n}$,向 0 取整。
对于正数当然就是 >> n 即可,对于负数就有些复杂,因为 >> 运算默认向下取整,需要进行修正。
对于负数,列表可以发现,每个数字在计算之前要加上 $2^n-1$ 的偏移才能得到正确答案。
因为出现了 n - 1,所以还要特别考虑 n = 0 的情况。使用 logicalShift 一样的「多路复用」方法即可。

negate

取负数,就是 (~x)+1,很简单。

isPositive

根据符号位,可以轻易判断出这个数是否 >= 0。既然本题要求判断 > 0,也就是 0 是特殊情况,依然可以根据前面的方法特殊判断。

isLessOrEqual

判断 $x \le y$,不能直接判断 $y-x \ge 0$,因为会 overflow。
可以发现如果 x 和 y 同号,肯定不会 overflow。所以只需要对异号的情况进行判断。
为了更加清晰,列出一个真值表:

x 符号位y 符号位返回值
101
010
00y-x 的符号位取反
11y-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) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y) {
  return ~((~x) | (~y));
}
/* 
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 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 shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 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 word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 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) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 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 integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1 << 31;
}
/* 
 * fitsBits - return 1 if x can be represented as an 
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 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 <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 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 -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return (~x) + 1;
}
/* 
 * isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 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 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 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 > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 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 for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 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) x
 *   Result is returned as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point values.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 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 for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 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){ // denomolized
    if (frac & (1<<23)){ // de -> no
      ret = ret | (1 << 23);
      return ret;
    } else {
      ret = ret - frac;
      frac = frac << 1;
      ret = ret + frac;
      return ret;
    }
  } else { // nomolized
    ret = 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;
  }
}