CSAPP-Lab-1 实验报告: datalab

发表于 更新于 分类于 ， ， ， 阅读次数： 本文字数： 7.9k 阅读时长 ≈ 14 分钟

摘要

本篇是 CSAPP datalab 的实验报告，该 lab 的目的是验证对整数 / 浮点数表示及相关操作的理解能力。该 lab 要求仅使用有限的位运算，实现各种操作。

实验内容共 13 个函数，可以分为整数和浮点数两部分：

  • 整数部分：仅允许使用移位、&, |, ^ 等运算，不允许使用类型转换、循环分支等
  • 浮点数部分：在整数的基础上，允许使用循环分支

具体的操作限制因题而异。除了正确性之外，实验还对每个函数允许进行的操作数进行了限制，满足限制才可以得到额外 2 分性能分。

整数

bitXor

只使用～与 & 实现异或操作。考虑简单的两个 bit a，b：

a^b=1 <=> a=1, b=0 or a=0, b=1 <=> a&b=0 and a|b=1

然而 | 是不能使用的，因此可以反过来思考：

a|b=1 <=> a,b 至少有 1 个 1 <=> ~a&~b=0

因此可以得到如下：

1
2
3
4
5
6
7
8
9
10
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(x & y) & ~(~x & ~y);
}

tmin

返回补码下最小的数字，只有权重为负的最高位值为 1，其余位均为 0

1
2
3
4
5
6
7
8
9
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1 << 31;
}

isTmax

判断一个数是否是补码下的最大整数。

Tmax 只有最高位为 0，观察可以发现 \(\sim Tmax=Tmax+1=Tmin\ne 0\)，因此可以得到下面的式子。\(\ne 0\) 是考虑到输入为 - 1 的情况。

1
2
3
4
5
6
7
8
9
10
11
12
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
  int plusOne = x + 1;
  int notX = ~x;
  return !(notX + (~plusOne + 1)) & !!plusOne;
}

allOddBits

判断 x 的奇数位是否均为 1。直接构造出奇数全为 1 的数 \(a\)，判断 x&a==a 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  int base = 0xAA;
  int half = (base << 8) + base;
  int whole = (half << 16) + half;
  x = x & whole;
  return !(x + (~whole + 1));
}

negate

取相反数。

1
2
3
4
5
6
7
8
9
10
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 1;
}

isAsciiDigit

判断 x 是否满足给定范围，根据加减后的符号位，构造两个布尔量，相与即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
  int con1 = !((x + (~0x30 + 1)) >> 31 & 1);
  int con2 = (x + (~0x3a + 1)) >> 31 & 1;
  return con1 & con2;
}

conditional

实现三目运算符。首先用！将输入转换为零一值 cond，用 cond 为 x，y 构造全 0 或全 1 的 mask。以下代码为例，x=0 时，cond=1，mask=0，结果为 z；x!=0 时，cond=0，mask=0xffffffff，结果为 y。满足三目运算符的性质。

1
2
3
4
5
6
7
8
9
10
11
12
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  int cond = !x;
  int mask = ~0 + cond;
  return (mask & y) | (~mask & z);
}

isLessOrEqual

判断 x<=y 是否成立。需要考虑加法溢出的问题。解决方法是同号的情况下才相减判断大小，异号时根据符号直接判断大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 
 * 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 signx = x >> 31 & 1;
  int signy = y >> 31 & 1;
  int isSignDiff = signx ^ signy;
  return (isSignDiff & !signy) | (!isSignDiff & !((y + (~x + 1)) >> 31));
}

logicalNeg

实现非操作，可以将任意值转为 01 值。核心思想是唯一地把 0 映射到 1，其余均映射到 0。先去除 x 的符号位，使得 \(x\ge 0\)，如果 \(x-1==-1\)，那么 \(x=0\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  int sign = (x >> 31) & 1;
  int notOverflow;
  // remove sign bit
  x = x & ~(sign << 31);
  notOverflow = ((~0 + x) >> 31) & 1;
  return ~sign & notOverflow;
}

howManyBits

重磅！返回补码下表征 x 所需的最少位数。这是个非常复杂的问题，从最大允许 90 次操作就可以看出来。事实上，稍加思考后，就可以知道这个题的关键是找到与符号位不同的最高位，答案 + 1（编码符号位）即是答案，例如：

  • 0 的符号位为 0，1 的最高位为 0（不存在），答案为 1
  • -1 的符号位为 1，0 的最高位为 0（不存在），答案为 1
  • 0x80000000 的符号位为 1，0 的最高位是 31，答案为 32

首先，为了避免正负数的问题，可以通过右移 + 异或，转换为正数处理。然后如果可以使用分支或者循环，可以逐位判断，找到最高位的 1。但是不允许的情况下，该怎么办呢？

一种直觉的思路是把循环展开，每次移动一位：先判断当前数是否为 0，不为 0 则计数器 + 1，然后右移 1 位。重复 31 次。代码形如：

1
2
3
cnt+=!!x;
x>>=1;
// 重复31次

这样需要至少 4*31 次操作，超出了 90 的限制，显然不是高效的解法。

细想一下，需要返回的结果实际上是一个 5 位数，从 00000 到 11111（31），最后加上符号位即可。因此，相较于低效地在原始的 32 位数字上遍历，可以逐位地判断结果的每 1 位是否为 1。从高到低地判断，以最高位 16 为例，流程如下：

  1. 判断 x>>15 是否为 0
  2. 若是，将结果第 5 位置 1，x>>=16
  3. 若否，将结果第 5 位置 0

在不允许分支的情况下，如何区分两种情况？答案是前面做过的三目运算符，x=(x>>15)==0?x:x>>16，即可完成。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  // 32 = 100000
  // 31 = 011111
  int ans = 0;
  int cond, mask;
  int ALL_ONE = ~0;
  // convert negative to non-negative, -1 -> 0
  x ^= x >> 31;
  // printf("after converting: %x \n", x);
  cond = !(x >> 15);
  ans |= !cond << 4;
  mask = ALL_ONE + cond;
  // x = x >> 15==0?x:x>>16;
  x = (~mask & x) | (mask & (x >> 16));
  cond = !(x >> 7);
  ans |= !cond << 3;
  mask = ALL_ONE + cond;
  x = (~mask & x) | (mask & (x >> 8));
  // x = x >> 7==0?x:x>>8;
  cond = !(x >> 3);
  ans |= !cond << 2;
  mask = ALL_ONE + cond;
  // x = x >> 3==0?x:x>>4;
  x = (~mask & x) | (mask & (x >> 4));
  cond = !(x >> 1);
  ans |= !cond << 1;
  mask = ALL_ONE + cond;
  // x = x >> 1==0?x:x>>2;
  x = (~mask & x) | (mask & (x >> 2));
  // last one
  // printf("last one: %x,%x\n", x, ans);
  ans |= x;
  return ans + 1;
}

浮点数

floatScale2

将浮点数 * 2。不难，分析得到各个位的取值后，分别判断规格数、非规格数、特殊值三种情况即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//float
/* 
 * floatScale2 - 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 floatScale2(unsigned uf) {
  unsigned sign = uf >> 31;
  int mMask = (1 << 23) - 1;
  unsigned m = uf & mMask;
  unsigned frac = (uf >> 23) & 0xff;
  if (frac == 0xff)
  {
    return uf;
  }
  if (frac == 0)
  {
    m <<= 1;
  }
  else
  {
    frac += 1;
  }
  return (sign << 31) + (frac << 23) + m;
}

floatFloat2Int

将浮点数转为 int，同样不难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  unsigned sign = uf >> 31;
  int mMask = (1 << 23) - 1;
  unsigned m = uf & mMask;
  unsigned frac = (uf >> 23) & 0xff;
  int exp = frac - 127;
  if (frac == 0xff || exp >= 31)
  {
    return 1 << 31;
  }
  if (exp < 0)
  {
    return 0;
  }
  m += 1 << 23;
  if (exp <= 23)
  {
    m >>= 23 - exp;
  }
  else
  {
    m <<= exp - 23;
  }
  if (sign)
  {
    m = ~m + 1;
  }
  return m;
}

floatPower2

实现求 2 的幂的功能。重点在于判断特殊情况，下溢为 0，上溢为无穷，规格数还是非规格数等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
  unsigned frac, m;
  if (x < -149)
  {
    return 0;
  }
  if (x > 127)
  {
    return 0xff << 23;
  }
  if (x < -126)
  {
    frac = 0;
    m = 1 << (149 + x);
  }
  else
  {
    frac = x + 127;
    m = 0;
  }
  return (frac << 23) + m;
}

结果

使用./driver.pl 对正确性和性能进行评估。拿到了全部的正确性和性能分数，受时间限制没有对每个函数内的操作数细扣优化，感觉有些地方还是有优化空间的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Correctness Results     Perf Results
Points  Rating  Errors  Points  Ops     Puzzle
1       1       0       2       7       bitXor
1       1       0       2       1       tmin
1       1       0       2       9       isTmax
2       2       0       2       9       allOddBits
2       2       0       2       2       negate
3       3       0       2       12      isAsciiDigit
3       3       0       2       7       conditional
3       3       0       2       15      isLessOrEqual
4       4       0       2       11      logicalNeg
4       4       0       2       49      howManyBits
4       4       0       2       14      floatScale2
4       4       0       2       21      floatFloat2Int
4       4       0       2       11      floatPower

Score = 62/62 [36/36 Corr + 26/26 Perf] (168 total operators)