Zj_W1nd's BLOG

CSAPP Labs——Data Lab

CSAPP Lab
2024/06/05

介绍：

https://hansimov.gitbook.io/csapp/labs/data-lab
通过这个实验我们将真正理解计算机中数据的存储方式——包括那些令人头疼的浮点数（真的能理解）。

这个实验的核心目标是在限定的运算符和运算符数目内完成许多函数（称为“谜题”）。官方提供了用于检测函数是否合规和打分的程序，满分相当于完成目标。并且提供了几个小工具。程序会用数万条测试数据对函数进行测试（包括大量的边界条件），因此必须保证函数是绝对有效的。

最关键的要求如下：
整数问题:

  1. 程序只能是顺序逻辑，不允许任何的条件分支、循环、跳转等。调用函数当然也不行。

  2. 不允许定义任何其他的宏、函数。

  3. 不允许使用任何规定外的运算符（如逻辑与&&等）和除int以外的数据类型

  4. 不允许使用任何大于0xFF的常量

对于浮点数问题，我们额外允许使用unsigned数据类型和分支结构（条件判断、循环等），同时也允许任何unsigned和int类型的常量使用，对于运算符也不再有限制，但仍然仅限整型的运算（不允许任何浮点运算）。

知道了规则，我们可以看看问题了。

内容：

整数部分：

bitXor：按位异或

bitXor - x^y using only ~ and &
Example: bitXor(4, 5) = 1
Legal ops: ~ &
Max ops: 14
使用逻辑运算将异或化为最简与非式即可。

1
2
3
int bitXor(int x, int y) {
  return ~(~(x&~y)&~(~x&y));
}

tmin: 给出最小的二进制补码整数

tmin - return minimum two’s complement integer
Legal ops: ! ~ & ^ | + << >>
Max ops: 4
Rating: 1

返回是32位有符号数，绝对值取最大然后取补结果是0x80000000。由于不允许使用长度超过0xFF的常量，使用移位运算实现：

1
2
3
int tmin(void) {
  return 1<<31;//0x80000000
}

isTmax：是最大整数吗？

isTmax - returns 1 if x is the maximum, two’s complement number,
and 0 otherwise
Legal ops: ! ~ & ^ | +
Max ops: 10
Rating: 1

最大的整数显然是0111 1111 … 1111，我们要将输入和这个数匹配。但没有移位运算也没有三目运算符。注意到它允许加法运算，是不是我们可以利用溢出？

这里出了很多问题。中间一个想法是!(~x+x+1)，即这个数加自己的相反数（取补）不是0.但是这会有一个问题，就是它的相反数0x80000000也符合这个条件。

而使用“+1是自己取反”这个性质的话，还会匹配-1（0xffffffff).因此想办法排除掉特殊情况-1，使用!!(~x)这一项可以在x是-1的时候取0，在x不是-1的时候取1，解决。

1
2
3
int isTmax(int x) {
  return !((x+1)^(~x))&(!!(~x));
}

allOddBits: 0-31，奇数位全1？

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
Max ops: 12
Rating: 2

这里结合AI的答案有一个偷鸡（也不算，因为规则已经很严了）：允许+和移位运算，那么我们可以用小于0xFF的常量拼凑成一个mask。这里就用0xAA(1010 1010)拼32位，结果直接和mask与然后判断即可。

1
2
3
4
int allOddBits(int x) {
  int mask = 0xAA + (0xAA << 8) + (0xAA << 16) + (0xAA << 24); // Create a mask with all odd-numbered bits set to 1
  return !((x & mask) ^ mask); // Check if all odd-numbered bits in x are set to 1
}

negate：相反数

negate - return -x
Example: negate(1) = -1.
Legal ops: ! ~ & ^ | + << >>
Max ops: 5
Rating: 2

补码的运算方式，取反加一即可。

1
2
3
int negate(int x) {
  return ~x + 1;//取反+1
}

isAsciiDigit: 是ascii字符0-9吗？

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

判断是否是0x30-0x39。这里我们不能直接比较，不过可以作差看符号位。那么由于要包含相等情况，需要上界增加1下界减少1——0x3a和0x2f

1
2
3
4
5
6
int isAsciiDigit(int x) {
// x-0x30
  int lower_than_0x39 = (x + (~0x3a + 1)) >> 31;//x-0x39<0主笔了写成0x29和0x40了
  int greater_than_0x30 = (0x2f + (~x + 1)) >> 31;//0x29-x<0
  return (lower_than_0x39 & 0x1) & (greater_than_0x30 & 0x1);//x-0x39<=0 && 0x30-x<=0
}

conditional：三目运算符

conditional - same as x ? y : z
Example: conditional(2,4,5) = 4
Legal ops: ! ~ & ^ | + << >>
Max ops: 16
Rating: 3

从源头出发。给出的运算符能实现数值->逻辑值转化的（非数值运算式转化）只有一个符号!，因此我们要在这个符号上下功夫。x是0输出z非0输出y，程序还不允许判断，那么我们考虑一个会随着x变化的mask。那这个把“非0”一大类映射到一个数的操作就是由!完成。

1
2
3
4
5
// 利用逻辑！符号对X输入进行转化（相当于就是一次判断）
int conditional(int x, int y, int z) {
  int mask_genius = ~(!x)+1;//x=0时0xffffffff,x!=0时0x00000000，编译会报警告，不管
  return (~mask_genius & y) | (mask_genius & z);
}

isLessOrEqual: x小于等于y？

isLessOrEqual - if x <= y then return 1, else return 0
Example: isLessOrEqual(4,5) = 1.
Legal ops: ! ~ & ^ | + << >>
Max ops: 24
Rating: 3

这里会测一大堆边界条件和溢出的东西…
我们的思想还是作差，但是作差这个运算会在很多地方溢出导致结果不对，因此考虑检测溢出——先判断符号是否相同。总之就是作差，符号相同作差小于（符号位）+ 相等判断 + 符号不同看x是不是负数。

1
2
3
4
5
6
7
8
int isLessOrEqual(int x, int y) {//天天测b溢出，要判断符号
  int x_sign = x >> 31;//x符号位
  int check_same_sign = (x_sign) ^ (y>>31);//符号位相同为0不同为-1（0xffffffff）
  int x_minus_y = x + ~y + 1;//x-y
  int sign= x_minus_y >> 31;//x-y<=0
  int tmp= !(x^y);//x和y一样为1不一样为0
  return (sign & !check_same_sign) | tmp | (x_sign & check_same_sign & 0x1);//一样，符号位相同作差x<y，符号位不同x<0
}

logicalNeg: 实现逻辑非‘!’

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

核心：看是不是0.那么要考虑0(0x00000000)的特性。首先考虑到是相反数的符号位和自己相同，但很不幸测试挂了——0x80000000也满足这个条件（取反加一是自己）。那这里不改变思路的情况下就要想办法排除掉0x80000000，，它和0的区别就是符号位是1.那在符号位做文章的话，就只返回自己和相反数符号位都是0的情况：

1
2
3
4
5
6
7
8
int logicalNeg(int x) { //判断是否自己的相反数和自己符号位相同
// 但是0x80000000的相反数是0x80000000不行
  int x_neg = ~x + 1;//取反加1 
  int tmp=(x>>31)^((x_neg)>>31)&0x1;
  int tmp2=(x>>31)|((x_neg)>>31)&0x1;//不能用异或，要保证两个符号位为0排除0x80000000
  //tmp=0且tmp2=0就返回1,否则返回0(大部分数tmp是1tmp2也是1，0是双0，0x80000000tmp是0而tmp2是1)
  return  ~tmp & ~tmp2 & 0x1;
}

*howManyBits：一个数最少要几位二进制补码表示

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 我草90个操作数
Rating: 4

很遗憾，这个问题自己没做出来，是copy的互联网的方案。开始没懂是什么意思，分析例子，直观来说，正数就是它们最高位1的位置加一位符号位，负数转成正数考虑。但是很难懂的是-1和1同样都是用一位1来表示。先贴代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 天才
int howManyBits(int x) {
	int temp = x ^ (x << 1);
	int bit_16,bit_8,bit_4,bit_2,bit_1;
	bit_16 = !!(temp >> 16) << 4;
	temp = temp >> bit_16;
	bit_8 = !!(temp >> 8) << 3;
	temp = temp >> bit_8;
	bit_4 = !!(temp >> 4) << 2;
	temp = temp >> bit_4;
	bit_2 = !!(temp >> 2) << 1;
	temp = temp >> bit_2;
	bit_1 = !!(temp >> 1);
	return 1 + bit_1 + bit_2 + bit_4 + bit_8 + bit_16;
}

特别鸣谢Github Copilot
首先第一行：

1
int temp = x ^ (x << 1);

这段代码应当用这个视角看待：x的每一位和它右边的位异或，当且仅当这一位和它右边的位不同才为1（即一位为1一位为0）。有这样一个直观认知：对于一个绝对值小的正数其高位应该都是0.对于一个绝对值小的负数其高位应该都是1。

第一行代码属于是这个算法的神之手：相邻位两两异或，迅速就能保存最高有效位——我们并不关心低位那些数据位什么样。

1
2
bit_16 = !!(temp >> 16) << 4;
temp = temp >> bit_16;

这里是看tmp的高16位有没有1，有1的话bit_16置位为10000并将tmp右移16位,否则为0。这里是将结果拆分成2进制的幂的形式，结果最大为32(100000),最高有效位的位置最大是(11111)，因此我们按权重拆分成五项，依次检查确定x的最高有效位的位置如何用2的幂表示，最高有效位越高，16-8-4-2-1的判定就越向前推进。

1
return 1 + bit_1 + bit_2 + bit_4 + bit_8 + bit_16;

最后加1，位下标变位数。
这个算法就是天才中的天才。劲

浮点数部分

IEEE 754单精度浮点数介绍

先讲下浮点数怎么存储的。对于IEEE 754标准下的单精度浮点数，其一共占32位，分符号、阶码、尾数（1-8-23）三部分，是以符号位-尾数乘2的阶码次幂得到。阶码是以真实值加127存储的（为了丢弃符号位存储负数）。同时为了省空间，尾数会省去最高位的1。如图所示（来自网络）：ieee_754_float.jpg
存储前会对小数进行规格化，也就是科学计数法。会将尾数设置为1.xxxx的形式然后省去最高位1.知道了这些就可以进行操作了

floatScale2: 实现给定浮点数*2

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

乘以2，显然由于浮点数的表示方法，我们只操作阶码就行，一般来说阶码加1即可。这里参考网络上的代码时，给出了一个如果非规格化浮点数（阶码全0）的分支情况，要将尾数左移一位（不确定是否真的有用但加上了），由于IEEE省略最高位1的策略，尾数最高位无论是0是1都不影响结果。
根据要求，对于无穷大（在标准下表示阶码全1），返回原值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
unsigned floatScale2(unsigned uf) {
  int sign = uf & (1<<31);//符号位取出来不动
  int exp = (uf & 0x7f800000) >> 23;//阶码
  int frac=uf&0x007fffff;//尾数
  if(exp==0)//如果阶码是0
  {
    frac=frac<<1;//尾数左移一位
    // 此时尾数的最高位必定是1否则会被规格化
    // 不影响，考虑0.5左移一位，这时候尾数全是0但根据标准其实是1
  }
  else if(exp==0xff)//如果阶码是全1
  {
    return uf;//返回原数
  }
  else //一般情况
  {
    exp=exp+1;//阶码+1
  }
  return sign|exp<<23|frac;//返回结果
}

后面我们都用类似的分块思想操作浮点数。

float2Int：小数取整 (int)f

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

思路是取出阶码然后按阶码移位尾数进行还原。如果是小数或0直接返回0，根据要求溢出返回0x80000000。要把尾数移位到对应位的话要对阶码做判断，看比23大还是比23小。最后还原符号。

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
int floatFloat2Int(unsigned uf) {
  int sign = uf & (1<<31);//符号位
  int exp = (uf & 0x7f800000) >> 23;//阶码(+127),运算顺序问题
  int frac=uf&0x007fffff;//尾数
  exp = exp-127;//阶码真值
  // if 解禁
  //printf("%x\n",exp);
  if(exp<0) 
    return 0;//小数或0直接返回0就行
  else if(exp>31){
    return 0x80000000u;//溢出返回0x80000000u
  }
  else{
    frac=frac|0x00800000;//尾数把1补上
    if(exp>23)
      frac=frac<<(exp-23);//阶码大于23，尾数左移至对应位
    else
      frac=frac>>(23-exp);//阶码小于23，尾数右移至对应位
  }
  //这时候frac应该能表示整数部分的绝对值了，最后确定符号
  if(sign>>31)
    return ~frac+1;//负数
  else
    return frac;//正数
}

floatPower2：2的x次方，以浮点输出。

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

二的整数次幂无论如何乘，规格化后位数永远是0，直接操作阶码就行了。根据要求加两个溢出分支检测，直接返回即可：

1
2
3
4
5
6
7
unsigned floatPower2(int x) {
  if(x+127<0)//下界超过了阶码能表示的范围
    return 0;//返回0
  if(x+127>255)//阶码大于255, 0xff
    return 0x7f800000;//返回+INF
  return (x+127)<<23;//浮点数的2^x，尾数为0（隐藏1），阶码x+127
}

总结

这个Lab有些脑筋急转弯的感觉，有的算法——尤其是那个判断最小位数的——简洁而高效。想起我刚上大一时接触的无tmp交换（a=a^b b=b^a a=a^b)位运算确实是门艺术。
data_lab_success.png

CATALOG
  1. 1. 介绍：
  2. 2. 内容：
    1. 2.1. 整数部分：
      1. 2.1.1. bitXor：按位异或
      2. 2.1.2. tmin: 给出最小的二进制补码整数
      3. 2.1.3. isTmax：是最大整数吗？
      4. 2.1.4. allOddBits: 0-31，奇数位全1？
      5. 2.1.5. negate：相反数
      6. 2.1.6. isAsciiDigit: 是ascii字符0-9吗？
      7. 2.1.7. conditional：三目运算符
      8. 2.1.8. isLessOrEqual: x小于等于y？
      9. 2.1.9. logicalNeg: 实现逻辑非‘!’
      10. 2.1.10. *howManyBits：一个数最少要几位二进制补码表示
    2. 2.2. 浮点数部分
      1. 2.2.1. IEEE 754单精度浮点数介绍
      2. 2.2.2. floatScale2: 实现给定浮点数*2
      3. 2.2.3. float2Int：小数取整 (int)f
      4. 2.2.4. floatPower2：2的x次方，以浮点输出。
  3. 3. 总结
Total : 63
2025
2024
2023
算法 Android 逆向 pwn wp heap linux CSAPP Lab chop Develop Windows CVE go rust protobuf kernel Rust llvm FSOP vm Others shellcode 前端 ROP web hvv IDA 编译 awdp awd
pwn linux CSAPP Reverse Develop pwn others Web