实验内容下载地址：http://csapp.cs.cmu.edu/3e/labs.html

目录：

1. Data Lab
2. Bomb Lab
3. Attack Lab
4. Buffer Lab (IA32)
5. Architecture Lab
6. Architecture Lab (Y86)
7. Cache Lab
8. Performance Lab
9. Shell Lab
10. Malloc Lab
11. Proxy Lab

描述：

• A “binary bomb” is a program provided to students as an object code file. When run, it prompts the user to type in 6 different strings. If any of these is incorrect, the bomb “explodes,” printing an error message and logging the event on a grading server. Students must “defuse” their own unique bomb by disassembling and reverse engineering the program to determine what the 6 strings should be. The lab teaches students to understand assembly language, and also forces them to learn how to use a debugger. It’s also great fun. A legendary lab among the CMU undergrads.Here’s a Linux/x86-64 binary bomb that you can try out for yourself. The feature that notifies the grading server has been disabled, so feel free to explode this bomb with impunity. If you’re an instructor with a CS:APP account, then you can download the solution.

  实验提供了一个二进制文件bomb，当它运行的时候，他会提示用户输入六个不同的字符串，如果任意一个错误，它就会bomb。学生必须查看他的反汇编代码，然后逆向出6个字符串分别是什么，这个实验教会学生理解汇编语言，也促使他们学习如何使用调试器。

今天开坑写一个系列，记录自己做11个CSAPP配套Lab的过程。

本帖为第一个实验，Data Lab。

实验内容下载地址：http://csapp.cs.cmu.edu/3e/labs.html

目录：

1. Data Lab
2. Bomb Lab
3. Attack Lab
4. Buffer Lab (IA32)
5. Architecture Lab
6. Architecture Lab (Y86)
7. Cache Lab
8. Performance Lab
9. Shell Lab
10. Malloc Lab
11. Proxy Lab

1.实验文件

实验文件解压后 有一个datalab-handout文件夹，里面有很多c文件，我们只需要在 bits.c里面编写程序，然后运行评测程序即可。

2.使用方法

bits.c文件里面有许多空函数，我们的工作就是根据函数的描述把空函数补充完整。
补充完整后，进行编译，使用make命令即可，make编译无错误后，运行btest程序./btest即可进行评测。

只测试单个函数：
./btest -f [函数名]

指定参数
./btest -f [函数名] -1 [参数1] -2 [参数2] -3……

输出调试
可以直接在bits.c文件里面调用printf方法输出调试信息，不需要包含stdio.h头文件。

3.实验内容：

//1
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 * bit异或
 * 要求只用～和&完成异或操作
 * 思路:第一题比较简单，任何逻辑操作都可以用～和&表达，异或也是，
 *      去查一下亦或的等价表达式，用摩根公式简化一下即可
 */
int bitXor(int x, int y) {
  int a = ~(~x &  y);
  int b = ~( x & ~y);
  int c = ~( a &  b);
  return c;
}
/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 * 返回补码表达的最小值
 * 根据补码的知识，补码的最小值就是1000000……000B
 */
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
 * 检验参数x是否是补码最大值
 * 思路，补码最大值是0111……1111  用~(1<<31))得到0111……111 然后和x进行一下亦或操作即可，如果完全一直则得0，取反为1
 */
int isTmax(int x) {
  return !(x^(~(1<<31)));
}
/* 
 * 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 nX = ~x;
  return !( (nX&0xAA) | (nX&(0xAA<<8)) | (nX&(0xAA<<16)) | (nX&(0xAA<<24)));
}
/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
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
 */
int isAsciiDigit(int x) {
  int a = !(!(x>>8));//验证高24位是否全为0(符合要求),
  int b = !(!(0x30^(x&0xF0)));
  int c1 = (0x08&x)>>3; 
  int c2 = (0x04&x)>>2;
  int c3 = (0x02&x)>>1;
  int c = (c1 & c2) | (c1 & c3);//如果是0表示 低四位符合要求
  // printf("x:0x%x a:0x%x b:0x%x c:0x%x c1:0x%x c2:0x%x c3:0x%x\n",x,a,b,c,c1,c2,c3);
  return !(a | b | c);
}
/* 
 * 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 a = ((!(!x))<<31)>>31;
  return (y&a) | (z&~a);
}
/* 
 * 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 x_sign = x>>31&1;
  int y_sign = y>>31&1;
  int a = x_sign & (!y_sign);
  int b = !(x_sign^y_sign);
  int c = b & ((x+~y)>>31 & 1);
  return a | c;
}
//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 
 */
int logicalNeg(int x) {
  int x_sign = (x>>31) & 1;
  int myx = x&(~(1<<31));
  int a = (myx+~0)>>31;
  return (a & ((~x_sign)&1));
}
/* 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) {
  int b16,b8,b4,b2,b1,b0;
  int sign=x>>31;
  x = (sign&~x)|(~sign&x);//如果x为正则不变，否则按位取反（这样好找最高位为1的，原来是最高位为0的，这样也将符号位去掉了）

// 不断缩小范围
  b16 = !!(x>>16)<<4;//高十六位是否有1
  x = x>>b16;//如果有（至少需要16位），则将原数右移16位
  b8 = !!(x>>8)<<3;//剩余位高8位是否有1
  x = x>>b8;//如果有（至少需要16+8=24位），则右移8位
  b4 = !!(x>>4)<<2;//同理
  x = x>>b4;
  b2 = !!(x>>2)<<1;
  x = x>>b2;
  b1 = !!(x>>1);
  x = x>>b1;
  b0 = x;
  return b16+b8+b4+b2+b1+b0+1;//+1表示加上符号位
}