《深入理解计算机系统/CSAPP》 Data Lab1

我使用的是阿里云的机器，64位Centos7，错误提示仅供参考。

其他的98说了，太难了。

编辑bits.c文件

/* 
 * CS:APP Data Lab 
 * 
 * <Please put your name and userid here>
 * 
 * bits.c - Source file with your solutions to the Lab.
 *          This is the file you will hand in to your instructor.
 *
 * WARNING: Do not include the <stdio.h> header; it confuses the dlc
 * compiler. You can still use printf for debugging without including
 * <stdio.h>, although you might get a compiler warning. In general,
 * it's not good practice to ignore compiler warnings, but in this
 * case it's OK.  
 */

#if 0
/*
 * Instructions to Students:
 *
 * STEP 1: Read the following instructions carefully.
 */

You will provide your solution to the Data Lab by
editing the collection of functions in this source file.

INTEGER CODING RULES:
 
  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code 
  must conform to the following style:
 
  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
    
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.

 
  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting if the shift amount
     is less than 0 or greater than 31.


EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }

  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }

FLOATING POINT CODING RULES

For the problems that require you to implement floating-point operations,
the coding rules are less strict.  You are allowed to use looping and
conditional control.  You are allowed to use both ints and unsigneds.
You can use arbitrary integer and unsigned constants. You can use any arithmetic,
logical, or comparison operations on int or unsigned data.

You are expressly forbidden to:
  1. Define or use any macros.
  2. Define any additional functions in this file.
  3. Call any functions.
  4. Use any form of casting.
  5. Use any data type other than int or unsigned.  This means that you
     cannot use arrays, structs, or unions.
  6. Use any floating point data types, operations, or constants.


NOTES:
  1. Use the dlc (data lab checker) compiler (described in the handout) to 
     check the legality of your solutions.
  2. Each function has a maximum number of operations (integer, logical,
     or comparison) that you are allowed to use for your implementation
     of the function.  The max operator count is checked by dlc.
     Note that assignment ('=') is not counted; you may use as many of
     these as you want without penalty.
  3. Use the btest test harness to check your functions for correctness.
  4. Use the BDD checker to formally verify your functions
  5. The maximum number of ops for each function is given in the
     header comment for each function. If there are any inconsistencies 
     between the maximum ops in the writeup and in this file, consider
     this file the authoritative source.

/*
 * STEP 2: Modify the following functions according the coding rules.
 * 
 *   IMPORTANT. TO AVOID GRADING SURPRISES:
 *   1. Use the dlc compiler to check that your solutions conform
 *      to the coding rules.
 *   2. Use the BDD checker to formally verify that your solutions produce 
 *      the correct answers.
 */


#endif
//1
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 *   Explain：离散数学?!
 */
int bitXor(int x, int y) {
  return ~((~(x&~y))&(~(~x&y)));
}
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 *   Explain：整形四字节，三十二字，返回10000000000000000000...(b)即可
 */
int tmin(void) {
  return 1<<31;

}
//2
/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 *   Explain：最大值 0x7fffffff 会出现溢出(利用有符号加判断无符号)
 */
int isTmax(int x) {
  return !((x^(~(x+1)))|(!(~x)));
}
/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1 
 * (判断二进制数奇数位是否全为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
 *   Explain：0x5555 5555二进制只有数奇数位是1，判断x==0x55555555即可
 *   But：但是演示的数为0xAAAAAAAA？？？
 */
int allOddBits(int x) {
  int mask = 0xAA | 0xAA << 8;
  mask = mask | mask << 16;
  x = x & mask;
  return !(mask^x);
}
/* 
 * negate - return -x 
 * (负数，反码？)
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 *   Explain：-x=~x+1
 *   But: 没有考虑0x7fffffff
 */
int negate(int x) {
  return ~x+1;
}
//3
/* 
 * 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
 *   Explain：保障x在[0x30,0x39]
 */
int isAsciiDigit(int x) {
  int min = 0x30;
  int max = 0x39;
  return (!((x+(~min+1))>>31)) & (!((max+(~x+1))>>31));
}
/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 *   Explain：三元操作， 将x装换成 0/1 ,然后再拓展到32字
 */
int conditional(int x, int y, int z) {
  x = (!x<<31)>>31;
  return (~x&y)|(x&z);
}
/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 *   Explain：符号位 x>>31;
 *            x,y 同号时 判断p = y-x
 *            x,y异号时 判断正数返回
 */
int isLessOrEqual(int x, int y) {
  int a = x>>31;
  int b = y>>31;
  int c = a+b;
  int p = !((~x+1+y)>>31);
  
  return (c&(a&1))|((~c)&p);
}
//4
/* 
 * 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 
 *   Explain：!x=~x+1
 */
int logicalNeg(int x) {
  return ~(x|(~x+1))>>31&1;
}
/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 * (判断x需要多少为补码表示)
 *  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
 *  Explain：...
 */
int howManyBits(int x) {
  int n = 0;
  x ^= (x<<1);
  n += ((!!(x&((~0)<<(n+16)))) << 4);
  n += ((!!(x&((~0)<<(n+8)))) << 3);
  n += ((!!(x&((~0)<<(n+4)))) << 2);
  n += ((!!(x&((~0)<<(n+2)))) << 1);
  n += (!!(x&((~0)<<(n+1))));
  return n+1;
}
//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
 *   Explain：...
 */
unsigned floatScale2(unsigned uf) {
  int exp_ = (uf&0x7f800000)>>23;
  int s_ = uf&0x80000000;
  if(exp_ == 0) return (uf<<1)|s_;
  if(exp_ == 255) return uf;
  ++exp_;
  if(exp_ == 255) return 0x7f800000|s_;
  return (uf&0x807fffff)|(exp_<<23);
}
/* (浮点转有符号整型)
 * 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
 *   Explain：...
 */
int floatFloat2Int(unsigned uf) {
  int s_ = uf>>31;
  int exp_ = ((uf&0x7f800000)>>23)-127;
  int frac_ = (uf&0x007fffff)|0x00800000; 
  if(!(uf&0x7fffffff)) return 0;
  
  if(exp_ > 31) return 0x80000000;
  if(exp_ < 0) return 0;
  
  if(exp_ > 23) frac_ <<= (exp_-23);
  else frac_ >>= (23-exp_);

  if(!((frac_>>31)^s_)) return frac_;
  else if(frac_>>31) return 0x80000000;
  else return ~frac_+1;
}
/* (浮点数按位异或)
 * 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
 *   Explain：...
 */       
unsigned floatPower2(int x) {
  if(x<-127) return 0;
  if(x>128) return 0x7f800000;
  x += 127;
  x = x << 23;
  return x;
}

实验结果

使用dlc检查函数实现代码是否符合实验要求的编码规则

首先./dlc bits.c直接检测是否有错误
```
    ./dlc bits.c
```
后用-e选项调用dlc，观察操作符数
```
    ./dlc -e bits.c
```

坑

由于权限问题，找不到指令需要使用命令chmod 777 dlc修改dlc文件权限

使用 btest 检查函数实现代码的功能正确性

首先使用make编译生成btest可执行程序
然后调用 ./btest 命令检查 bits.c中所有函数的功能正确性

坑

使用make时保证复制的Makefile在当前文件夹下。

如果出现错误

      fatal error: gnu/stubs-32.h: No such file or directory
       # include <gnu/stubs-32.h>
                                 ^
      compilation terminated.
      In file included from /usr/include/features.h:399:0,
                       from /usr/include/limits.h:26,
                       from /usr/lib/gcc/x86_64-redhat-linux/4.8.5/include/limits.h:168,
                       from /usr/lib/gcc/x86_64-redhat-linux/4.8.5/include/syslimits.h:7,
                       from /usr/lib/gcc/x86_64-redhat-linux/4.8.5/include/limits.h:34,
                       from tests.c:3:
      /usr/include/gnu/stubs.h:7:27: fatal error: gnu/stubs-32.h: No such file or directory
       # include <gnu/stubs-32.h>
                                 ^
      compilation terminated.
      make: *** [btest] Error 1

是因为64位操作系统缺少32位运行库造成的，解决方案：

    sudo yum install glibc-devel.i686

一个题目floatPower2验证出现死循环始终无法通过，没在找到解决方案，不过btest.c中的#define TIMEOUT_LIMIT 10改成了#define TIMEOUT_LIMIT 10，“曲线救国”