DataLab
实验内容
/*
* 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
*/
int bitXor(int x, int y) {
/*
* x ^ y = (~x & y) + (x & ~y)
* De Morgan's Law : x + y = ~(x & y)
*/
int part_one = ~((~x) & y);
int part_two = ~((~y) & x);
return ~(part_one & part_two);
}
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
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
*/
int isTmax(int x) {
/*
* only when x = 0x7fffffff or x = 0xffffffff, x + x + 2 = 0
* !(x + 1) is designed to distinguish between the two
*/
return !((x + x + 2) | (!(x + 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
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
x = (x >> 16) & x;
x = (x >> 8 ) & x;
x = (x >> 4 ) & x;
x = (x >> 2 ) & x;
x = (x >> 1 ) & 1;
return x;
}
/*
* 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) {
/*
* assume x = 0xMN
* part_one check whether M is 3
* part_two check whether N is bigger than 9
*/
int part_one = (x >> 4) ^ 0x3;
int part_two = (x >> 3) & (((x >> 1) & 1) | ((x >> 2) & 1));
return !(part_one | part_two);
}
/*
* 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) {
x = (x << 16) | x;
x = (x << 8 ) | x;
x = (x << 4 ) | x;
x = (x << 2 ) | x;
x = (x << 1 ) | x;
x = x >> 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
*/
int isLessOrEqual(int x, int y) {
int x_sign = x >> 31;
int y_sign = y >> 31;
int y_twos_complement = (~y) + 1;
// if x == y,x_equal_y = 1
int x_equal_y = !(x ^ y);
// when x > 0, y > 0, if x < y, then xpyp is negative
int xpyp = ((~(x_sign | y_sign)) & (x + y_twos_complement)) >> 31;
// if x < 0, y > 0, xnyp always be negative
int xnyp = (x_sign & (~y_sign));
// when x < 0, y < 0, if x < y, then xnyn is negative
int xnyn = ((x_sign & y_sign) & (x + y_twos_complement)) >> 31;
return (x_equal_y + xpyp + xnyp + xnyn) & 1;
}
//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) {
x = (x >> 16) | x;
x = (x >> 8 ) | x;
x = (x >> 4 ) | x;
x = (x >> 2 ) | x;
x = (x >> 1 ) | x;
return (~x) & 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 sign = x >> 31;
int minus_power16 = (~(1 << 16)) + 1; // - 2 ^ 16
int minus_power8 = (~(1 << 8)) + 1; // - 2 ^ 8
int minus_power4 = (~16) + 1; // - 2 ^ 4
int minus_power2 = (~4) + 1; // - 2 ^ 2
int minus_power1 = (~2) + 1; // - 2 ^ 1
int tempX, tempAns;
int ans = 0;
// if x is greater than 0, x stays the same, otherwise we reverse it
x = ((~sign) & x) | (sign & (~x));
tempX = (x + minus_power16) >> 31;
tempAns = ((~tempX) & 16);
ans += tempAns;
x >>= tempAns;
tempX = (x + minus_power8) >> 31;
tempAns = ((~tempX) & 8);
ans += tempAns;
x >>= tempAns;
tempX = (x + minus_power4) >> 31;
tempAns = ((~tempX) & 4);
ans += tempAns;
x >>= tempAns;
tempX = (x + minus_power2) >> 31;
tempAns = ((~tempX) & 2);
ans += tempAns;
x >>= tempAns;
tempX = (x + minus_power1) >> 31;
tempAns = ((~tempX) & 1);
ans += tempAns;
x >>= tempAns;
tempX = (x + (~0)) >> 31;
tempAns = ((~tempX) & 1);
ans += tempAns;
x >>= tempAns;
return 1 + ans;
}
//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 = (1 << 31) & uf;
unsigned exponent = (sign ^ uf) >> 23;
unsigned frac = (sign | (exponent << 23)) ^ uf;
if (exponent == 0xff) return uf;
else if (exponent == 0xfe)
{
return sign | (0xff << 23);
}
else if (exponent == 0)
{
return sign | (frac << 1);
}
else
return sign | ((exponent + 1) << 23) | frac;
}
/*
* 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 & 0x80000000;
int exponent = ((sign ^ uf) >> 23) - 127;
unsigned frac = uf & 0x7ffff;
unsigned ans = 0;
if (exponent > 30) return 0x80000000u;
else if (exponent < 0) return 0;
else if (exponent >= 23)
ans = (frac | 0x800000) << (exponent - 23);
else
ans = (frac | 0x800000) >> (23 - exponent);
if (sign)
ans = (~ans) + 1;
return ans;
}
/*
* 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) {
if (x >= 128) return 0x7f800000;
else if (x >= -126) return (x + 127) << 23;
else if (x >= -150) return 1 << (x + 150);
else return 0;
}
感悟
在看CSAPP之前已经在许多课程中学过关于原码反码补码浮点数位运算等知识了，阅读本书第二章时总觉得自己都懂，没什么新东西了。于是乎直接被家庭作业及LAB教做人
这LAB可真够硬的
确实该保持谦卑：看似这些东西已经学了好几遍，都是草草了解基本概念，几乎没有上手实操过，比如将所学的知识投入应用解决什么实际问题啥的。感谢CSAPP给我这么一个机会，这课程评价如此之高，LAB足够硬核且有趣功不可没
让我沮丧的是有几个函数我没能独自完成，还没拼尽全力就放弃，求助于题解。按作者对CMU学子的要求，这种行为是作弊。我得承认我确实是作弊了，这弄得我很沮丧。当阅读了别人的题解后，我既惊叹于他们的思路与技巧，直呼“还可以这样”，但转念一想其实自己再努把力也未必想不到。但确实没能完全独自完成，后悔不及。
知耻而后勇，以此次作弊为鉴，之后的学习放低姿态，认真按照要求好好弄吧！
BombLab
phase_1
反汇编main函数，找到phase_1()函数入口
(gdb) disassemble main
...
0x0000000000400e32 <+146>: callq 0x40149e <read_line>
0x0000000000400e37 <+151>: mov %rax,%rdi
0x0000000000400e3a <+154>: callq 0x400ee0 <phase_1>
...
phase_1()函数首地址为0x400ee0，接着反汇编phase_1()函数
(gdb) disassemble 0x400ee0
Dump of assembler code for function phase_1:
0x0000000000400ee0 <+0>: sub $0x8,%rsp
0x0000000000400ee4 <+4>: mov $0x402400,%esi
0x0000000000400ee9 <+9>: callq 0x401338 <strings_not_equal>
0x0000000000400eee <+14>: test %eax,%eax
0x0000000000400ef0 <+16>: je 0x400ef7 <phase_1+23>
0x0000000000400ef2 <+18>: callq 0x40143a <explode_bomb>
0x0000000000400ef7 <+23>: add $0x8,%rsp
0x0000000000400efb <+27>: retq
End of assembler dump.
简要分析，phase_1()函数调用首地址为0x401338名为strings_not_equal()的函数，后者通过%rax寄存器返回一个值。若该值为0，炸弹拆除成功；否则炸弹爆炸，于是接着反汇编string_not_euqal()函数
(gdb) disassemble 0x401338
...
0x000000000040133c <+4>: mov %rdi,%rbx
0x000000000040133f <+7>: mov %rsi,%rbp
0x0000000000401342 <+10>: callq 0x40131b <string_length>
0x0000000000401347 <+15>: mov %eax,%r12d
0x000000000040134a <+18>: mov %rbp,%rdi
0x000000000040134d <+21>: callq 0x40131b <string_length>
0x0000000000401352 <+26>: mov $0x1,%edx
0x0000000000401357 <+31>: cmp %eax,%r12d
0x000000000040135a <+34>: jne 0x40139b <strings_not_equal+99>
...
该函数又会调用首地址为0x40131b名为string_length()的函数，并比较二者返回值是否相同，若不同则strings_not_equal()通过%rax返回值1，最终炸弹爆炸，继续反汇编string_length()函数
(gdb) disassemble 0x40131b
Dump of assembler code for function string_length:
0x000000000040131b <+0>: cmpb $0x0,(%rdi)
0x000000000040131e <+3>: je 0x401332 <string_length+23>
0x0000000000401320 <+5>: mov %rdi,%rdx
0x0000000000401323 <+8>: add $0x1,%rdx
0x0000000000401327 <+12>: mov %edx,%eax
0x0000000000401329 <+14>: sub %edi,%eax
0x000000000040132b <+16>: cmpb $0x0,(%rdx)
0x000000000040132e <+19>: jne 0x401323 <string_length+8>
0x0000000000401330 <+21>: repz retq
0x0000000000401332 <+23>: mov $0x0,%eax
0x0000000000401337 <+28>: retq
End of assembler dump.
分析得string_length()函数接收一个参数(存于%rdi中)，%rdi为一字符串首地址，string_length()函数从该首地址起将数据类型为byte的字符值逐个与值0x('\0')比较，最终利用%rax寄存器返回字符串长度，接着回到string_not_equal()函数中
0x000000000040135a <+34>: jne 0x40139b <strings_not_equal+99>
0x000000000040135c <+36>: movzbl (%rbx),%eax
0x000000000040135f <+39>: test %al,%al
0x0000000000401361 <+41>: je 0x401388 <strings_not_equal+80>
0x0000000000401363 <+43>: cmp 0x0(%rbp),%al
0x0000000000401366 <+46>: je 0x401372 <strings_not_equal+58>
0x0000000000401368 <+48>: jmp 0x40138f <strings_not_equal+87>
0x000000000040136a <+50>: cmp 0x0(%rbp),%al
0x000000000040136d <+53>: nopl (%rax)
0x0000000000401370 <+56>: jne 0x401396 <strings_not_equal+94>
0x0000000000401372 <+58>: add $0x1,%rbx
0x0000000000401376 <+62>: add $0x1,%rbp
0x000000000040137a <+66>: movzbl (%rbx),%eax
0x000000000040137d <+69>: test %al,%al
0x000000000040137f <+71>: jne 0x40136a <strings_not_equal+50>
0x0000000000401381 <+73>: mov $0x0,%edx
0x0000000000401386 <+78>: jmp 0x40139b <strings_not_equal+99>
0x0000000000401388 <+80>: mov $0x0,%edx
0x000000000040138d <+85>: jmp 0x40139b <strings_not_equal+99>
0x000000000040138f <+87>: mov $0x1,%edx
0x0000000000401394 <+92>: jmp 0x40139b <strings_not_equal+99>
0x0000000000401396 <+94>: mov $0x1,%edx
0x000000000040139b <+99>: mov %edx,%eax
简要分析得首地址为0x40135a的指令判断两字符串长度是否相同。若长度相同，则逐一比较两串是否逐字符相同。若两串完全相同，则函数返回0；若任意字符不同，函数返回1
分析至此知本题关键在于如何获知模式串内容。观察知当通过string_length()函数计算字符串长度时，待计算字符串的首地址需通过%rdi寄存器传入函数中，而由string_not_equal()中
0x000000000040133c <+4>: mov %rdi,%rbx
0x000000000040133f <+7>: mov %rsi,%rbp
0x0000000000401342 <+10>: callq 0x40131b <string_length>
0x0000000000401347 <+15>: mov %eax,%r12d
0x000000000040134a <+18>: mov %rbp,%rdi
0x000000000040134d <+21>: callq 0x40131b <string_length>
知，两次调用string_length()函数时分别传入了%rdi与%rsi中的值，而又由phase_1()
0x0000000000400ee4 <+4>: mov $0x402400,%esi
0x0000000000400ee9 <+9>: callq 0x401338 <strings_not_equal>
知，%rsi为定值$0x402400，不难得出该定值为模式串首地址
(gdb) x /s 0x402400
0x402400: "Border relations with Canada have never been better."
得答案
phase_2
反汇编main函数，找到phase_2()函数入口
0x0000000000400e56 <+182>: callq 0x400efc <phase_2>
phase_2()函数首地址为0x400efc，接着反汇编phase_2()函数
0x0000000000400efe <+2>: sub $0x28,%rsp
0x0000000000400f02 <+6>: mov %rsp,%rsi
0x0000000000400f05 <+9>: callq 0x40145c <read_six_numbers>
0x0000000000400f0a <+14>: cmpl $0x1,(%rsp)
0x0000000000400f0e <+18>: je 0x400f30 <phase_2+52>
0x0000000000400f10 <+20>: callq 0x40143a <explode_bomb>
该函数在栈上开辟了40个字节大小的空间，设开辟后%rsp值为s0，接着调用首地址为0x40145c名为read_six_numbers()的函数，随后比较确认栈顶四字节大小的数据值是否为1，若不为1则炸弹爆炸，由此确定DWORD PTR 0(%rsp) = 1，接着反汇编read_six_numbers()函数
(gdb) disassemble 0x40145c
Dump of assembler code for function read_six_numbers:
0x000000000040145c <+0>: sub $0x18,%rsp
0x0000000000401460 <+4>: mov %rsi,%rdx
0x0000000000401463 <+7>: lea 0x4(%rsi),%rcx
0x0000000000401467 <+11>: lea 0x14(%rsi),%rax
0x000000000040146b <+15>: mov %rax,0x8(%rsp)
0x0000000000401470 <+20>: lea 0x10(%rsi),%rax
0x0000000000401474 <+24>: mov %rax,(%rsp)
0x0000000000401478 <+28>: lea 0xc(%rsi),%r9
0x000000000040147c <+32>: lea 0x8(%rsi),%r8
0x0000000000401480 <+36>: mov $0x4025c3,%esi
0x0000000000401485 <+41>: mov $0x0,%eax
0x000000000040148a <+46>: callq 0x400bf0 <__isoc99_sscanf@plt>
0x000000000040148f <+51>: cmp $0x5,%eax
0x0000000000401492 <+54>: jg 0x401499 <read_six_numbers+61>
0x0000000000401494 <+56>: callq 0x40143a <explode_bomb>
0x0000000000401499 <+61>: add $0x18,%rsp
0x000000000040149d <+65>: retq
End of assembler dump.
分析得read_six_numbers()接收一个由%rsi传递来的一个参数，其值为s0，即phase_2()函数栈空间开辟后栈顶地址。而read_six_numbers()函数的作用为将用户输入的六个数字按顺序放于栈中(先输入者于栈顶)，再次返回phase_2()函数中
0x0000000000400f15 <+25>: jmp 0x400f30 <phase_2+52>
0x0000000000400f17 <+27>: mov -0x4(%rbx),%eax
0x0000000000400f1a <+30>: add %eax,%eax
0x0000000000400f1c <+32>: cmp %eax,(%rbx)
0x0000000000400f1e <+34>: je 0x400f25 <phase_2+41>
0x0000000000400f20 <+36>: callq 0x40143a <explode_bomb>
0x0000000000400f25 <+41>: add $0x4,%rbx
0x0000000000400f29 <+45>: cmp %rbp,%rbx
0x0000000000400f2c <+48>: jne 0x400f17 <phase_2+27>
0x0000000000400f2e <+50>: jmp 0x400f3c <phase_2+64>
0x0000000000400f30 <+52>: lea 0x4(%rsp),%rbx
0x0000000000400f35 <+57>: lea 0x18(%rsp),%rbp
0x0000000000400f3a <+62>: jmp 0x400f17 <phase_2+27>
自read_six_numbers()函数返回后，phase_2()函数剩余部分为一循环，由
0x0000000000400f17 <+27>: mov -0x4(%rbx),%eax
0x0000000000400f1a <+30>: add %eax,%eax
0x0000000000400f1c <+32>: cmp %eax,(%rbx)
0x0000000000400f1e <+34>: je 0x400f25 <phase_2+41>
0x0000000000400f20 <+36>: callq 0x40143a <explode_bomb>
知，相邻输入的两数字，若后输入者的值不为前者两倍，则炸弹爆炸。而又由DWORD PTR 0(%rsp) = 1知，六个数字分别为1，2，4，8，16，32
phase_3
反汇编phase_3()函数
(gdb) disassemble phase_3
Dump of assembler code for function phase_3:
0x0000000000400f43 <+0>: sub $0x18,%rsp
0x0000000000400f47 <+4>: lea 0xc(%rsp),%rcx
0x0000000000400f4c <+9>: lea 0x8(%rsp),%rdx
0x0000000000400f51 <+14>: mov $0x4025cf,%esi
0x0000000000400f56 <+19>: mov $0x0,%eax
0x0000000000400f5b <+24>: callq 0x400bf0 <__isoc99_sscanf@plt>
知phase_3()函数先将值$0x4025cf存于%esi中，接着调用sscanf()函数读取输入数据，尝试反汇编首地址为0x4025cf的内容
(gdb) x /s 0x4025cf
0x4025cf: "%d %d"
得该谜题应输入两个数字，继续查看phase_3()代码
0x0000000000400f6a <+39>: cmpl $0x7,0x8(%rsp)
0x0000000000400f6f <+44>: ja 0x400fad <phase_3+106>
0x0000000000400f71 <+46>: mov 0x8(%rsp),%eax
0x0000000000400f75 <+50>: jmpq *0x402470(,%rax,8)
0x0000000000400f7c <+57>: mov $0xcf,%eax
0x0000000000400f81 <+62>: jmp 0x400fbe <phase_3+123>
0x0000000000400f83 <+64>: mov $0x2c3,%eax
0x0000000000400f88 <+69>: jmp 0x400fbe <phase_3+123>
0x0000000000400f8a <+71>: mov $0x100,%eax
0x0000000000400f8f <+76>: jmp 0x400fbe <phase_3+123>
0x0000000000400f91 <+78>: mov $0x185,%eax
0x0000000000400f96 <+83>: jmp 0x400fbe <phase_3+123>
0x0000000000400f98 <+85>: mov $0xce,%eax
0x0000000000400f9d <+90>: jmp 0x400fbe <phase_3+123>
0x0000000000400f9f <+92>: mov $0x2aa,%eax
0x0000000000400fa4 <+97>: jmp 0x400fbe <phase_3+123>
0x0000000000400fa6 <+99>: mov $0x147,%eax
0x0000000000400fab <+104>: jmp 0x400fbe <phase_3+123>
0x0000000000400fad <+106>: callq 0x40143a <explode_bomb>
0x0000000000400fb2 <+111>: mov $0x0,%eax
0x0000000000400fb7 <+116>: jmp 0x400fbe <phase_3+123>
0x0000000000400fb9 <+118>: mov $0x137,%eax
0x0000000000400fbe <+123>: cmp 0xc(%rsp),%eax
0x0000000000400fc2 <+127>: je 0x400fc9 <phase_3+134>
0x0000000000400fc4 <+129>: callq 0x40143a <explode_bomb>
由前两行知DWORD PTR 0x8(%rsp)中的值小于等于7，而
0x0000000000400f71 <+46>: mov 0x8(%rsp),%eax
0x0000000000400f75 <+50>: jmpq *0x402470(,%rax,8)
结合后续一系列跳转指令知，这里实现了swtich语句的跳转表功能，以DWORD PTR 0x8(%rsp)中的值为偏移量实现跳转，基地址为0x402470，于是反汇编查看跳转表内容
(gdb) x /8xg 0x402470
0x402470: 0x0000000000400f7c 0x0000000000400fb9
0x402480: 0x0000000000400f83 0x0000000000400f8a
0x402490: 0x0000000000400f91 0x0000000000400f98
0x4024a0: 0x0000000000400f9f 0x0000000000400fa6
当DWORD PTR 0x8(%rsp)值为0时，跳转至0x400f7c，再由后续几条指令知DWORD PTR 0xc(%rsp)的值应为0xcf，于是得本题一组解： [0, 207]，同理得其他七组解分别为[1, 311],[2, 707],[3, 256],[4, 389],[5, 206],[6, 682],[7, 147]
phase_4
反汇编phase_4()
0x0000000000401010 <+4>: lea 0xc(%rsp),%rcx
0x0000000000401015 <+9>: lea 0x8(%rsp),%rdx
0x000000000040101a <+14>: mov $0x4025cf,%esi
0x000000000040101f <+19>: mov $0x0,%eax
0x0000000000401024 <+24>: callq 0x400bf0 <__isoc99_sscanf@plt>
0x0000000000401029 <+29>: cmp $0x2,%eax
0x000000000040102c <+32>: jne 0x401035 <phase_4+41>
同phase_3()，易得该谜题需要两个输入
0x000000000040102e <+34>: cmpl $0xe,0x8(%rsp)
0x0000000000401033 <+39>: jbe 0x40103a <phase_4+46>
0x0000000000401035 <+41>: callq 0x40143a <explode_bomb>
由上述三条指令知DOWRD PTR 0x8(%rsp)中的值小于等于14，即第一个数字应小于15
0x0000000000401051 <+69>: cmpl $0x0,0xc(%rsp)
0x0000000000401056 <+74>: je 0x40105d <phase_4+81>
0x0000000000401058 <+76>: callq 0x40143a <explode_bomb>
同理知第二个数字必为0，接下来反汇编首地址为0x400fce的func4()函数
0x0000000000400fce <+0>: sub $0x8,%rsp
0x0000000000400fd2 <+4>: mov %edx,%eax
0x0000000000400fd4 <+6>: sub %esi,%eax
0x0000000000400fd6 <+8>: mov %eax,%ecx
0x0000000000400fd8 <+10>: shr $0x1f,%ecx
0x0000000000400fdb <+13>: add %ecx,%eax
0x0000000000400fdd <+15>: sar %eax
0x0000000000400fdf <+17>: lea (%rax,%rsi,1),%ecx
0x0000000000400fe2 <+20>: cmp %edi,%ecx
0x0000000000400fe4 <+22>: jle 0x400ff2 <func4+36>
0x0000000000400fe6 <+24>: lea -0x1(%rcx),%edx
0x0000000000400fe9 <+27>: callq 0x400fce <func4>
0x0000000000400fee <+32>: add %eax,%eax
0x0000000000400ff0 <+34>: jmp 0x401007 <func4+57>
0x0000000000400ff2 <+36>: mov $0x0,%eax
0x0000000000400ff7 <+41>: cmp %edi,%ecx
0x0000000000400ff9 <+43>: jge 0x401007 <func4+57>
0x0000000000400ffb <+45>: lea 0x1(%rcx),%esi
0x0000000000400ffe <+48>: callq 0x400fce <func4>
0x0000000000401003 <+53>: lea 0x1(%rax,%rax,1),%eax
0x0000000000401007 <+57>: add $0x8,%rsp
0x000000000040100b <+61>: retq
分析知该函数接收三个参数，分别存于%rdi, %rsi, %rdx中，尝试构造c函数
int func4(int x, int y, int z) {
//x in %rdi, y in %rsi, z in %rdx
//t <-> %rax w <-> %rcx
if (z >= y) {
t = z - y;
w = 0;
t = (z - y) / 2;
w = (z + y) / 2;
if (w <= x) {
t = 0;
if (w == x) return t;
y = (z + y) / 2 + 1;
t = func4(x, y, z);
return 2 * t + 1;
}
else {
z = (z + y) / 2 - 1;
t = func4(x, y, z);
return 2 * t;
}
}
else if (z < y) {
t = z - y;
w = -1;
t = (z - y - 1) / 2;
w = (z + y - 1) / 2;
if (w <= x) {
t = 0;
if (w == x) return t;
y = (z + y + 1) / 2;
t = func4(x, y, z);
return 2 * t + 1;
}
else {
z = (z + y - 1) / 2 - 1;
t = func4(x, y, z);
return 2 * t;
}
}
}
而phase_4()调用本函数时，传入的x, y, z值分别为DWORD PTR 0x8(%rsp), 0, 14.我没有详细探究本函数实现的功能，而是将DWORD PTR 0x8(%rsp)可能的取值(0 ~ 14)全部带入算出结果，由phase_4()函数里
0x000000000040104d <+65>: test %eax,%eax
0x000000000040104f <+67>: jne 0x401058 <phase_4+76>
知，只有在func4()函数返回值为0的情况下炸弹才不会爆炸，因此第一个数可能的取值有0,1,3,7.
即可选的答案有[0, 0], [1, 0], [3, 0], [7, 0]
0x400fdd地址处的 sar %eax指令只含一个操作数，实际上是sar %eax, 1的隐含简写，见 SAR command in X86 assembly with one paramete
phase_5
反汇编phase_5()函数
0x0000000000401063 <+1>: sub $0x20,%rsp
0x0000000000401067 <+5>: mov %rdi,%rbx
0x000000000040106a <+8>: mov %fs:0x28,%rax
0x0000000000401073 <+17>: mov %rax,0x18(%rsp)
0x0000000000401078 <+22>: xor %eax,%eax
0x000000000040107a <+24>: callq 0x40131b <string_length>
0x000000000040107f <+29>: cmp $0x6,%eax
0x0000000000401082 <+32>: je 0x4010d2 <phase_5+112>
0x0000000000401084 <+34>: callq 0x40143a <explode_bomb>
首先可见该函数在栈上申请了32字节空间，接着将fs:0x28地址处的某值放入0x18(%rsp)中，即设置金丝雀值用于栈破坏检测然后调用string_length()函数检查输入字符串字符数目是否为6，非6则炸弹爆炸，由此知应输入字符数目为6.接下来结合
0x0000000000401082 <+32>: je 0x4010d2 <phase_5+112>
0x00000000004010d2 <+112>: mov $0x0,%eax
0x00000000004010d7 <+117>: jmp 0x40108b <phase_5+41>
在确认输入字符串字符数为6后，先将%rax值清零，然后进入一段循环
0x000000000040108b <+41>: movzbl (%rbx,%rax,1),%ecx
0x000000000040108f <+45>: mov %cl,(%rsp)
0x0000000000401092 <+48>: mov (%rsp),%rdx
0x0000000000401096 <+52>: and $0xf,%edx
0x0000000000401099 <+55>: movzbl 0x4024b0(%rdx),%edx
0x00000000004010a0 <+62>: mov %dl,0x10(%rsp,%rax,1)
0x00000000004010a4 <+66>: add $0x1,%rax
0x00000000004010a8 <+70>: cmp $0x6,%rax
0x00000000004010ac <+74>: jne 0x40108b <phase_5+41>
分析知该循环代码依次将我们所输入的六个字符的低四位作为索引，取0x4024b0作为基地址，分六次将索引对应的字符取出存入%rsp + 16 + bias处的栈中，于是我们先反汇编看下0x4024b0地址处存储的信息
(gdb) x /s 0x4024b0
0x4024b0 <array.3449>: "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
由于索引为我们输入字符的低四位，即索引范围为0 ~ 15，对应该字符串的
maduiersnfotvbyl
部分，继续查看phase_5()函数代码
0x00000000004010ae <+76>: movb $0x0,0x16(%rsp)
0x00000000004010b3 <+81>: mov $0x40245e,%esi
0x00000000004010b8 <+86>: lea 0x10(%rsp),%rdi
0x00000000004010bd <+91>: callq 0x401338 <strings_not_equal>
0x00000000004010c2 <+96>: test %eax,%eax
0x00000000004010c4 <+98>: je 0x4010d9 <phase_5+119>
0x00000000004010c6 <+100>: callq 0x40143a <explode_bomb>
string_not_equal在之前的谜题里已见过，易知此段代码作用为将刚才通过索引选出的6个字符与首地址为0x40245e处的字符串进行比较，若不匹配则炸弹爆炸，故查看地址0x40245e处字符串内容
(gdb) x /s 0x40245e
0x40245e: "flyers"
这六个字符分别对应谜题字符串中的[9, 15, 14, 5, 6, 7]位(从0起计数)，而高四位不做限制，故本题答案不唯一，查阅ascii表易得其中两个答案为"9?>567", "IONEFG"，其余答案不一一枚举。phase_5()函数最后几行代码用于检测是否发生栈溢出，在此不做更多介绍
phase_6
反汇编phase_6()函数
0x00000000004010fc <+8>: sub $0x50,%rsp
0x0000000000401100 <+12>: mov %rsp,%r13
0x0000000000401103 <+15>: mov %rsp,%rsi
0x0000000000401106 <+18>: callq 0x40145c <read_six_numbers>
0x000000000040110b <+23>: mov %rsp,%r14
在栈上开辟80字节空间后，将%r13, %rsi, %r14寄存器的值都设为当前栈顶地址。且知本题需输入六个数字
0x000000000040110e <+26>: mov $0x0,%r12d
0x0000000000401114 <+32>: mov %r13,%rbp
0x0000000000401117 <+35>: mov 0x0(%r13),%eax
0x000000000040111b <+39>: sub $0x1,%eax
0x000000000040111e <+42>: cmp $0x5,%eax
0x0000000000401121 <+45>: jbe 0x401128 <phase_6+52>
0x0000000000401123 <+47>: callq 0x40143a <explode_bomb>
0x0000000000401128 <+52>: add $0x1,%r12d
0x000000000040112c <+56>: cmp $0x6,%r12d
0x0000000000401130 <+60>: je 0x401153 <phase_6+95>
0x0000000000401132 <+62>: mov %r12d,%ebx
0x0000000000401135 <+65>: movslq %ebx,%rax
0x0000000000401138 <+68>: mov (%rsp,%rax,4),%eax
0x000000000040113b <+71>: cmp %eax,0x0(%rbp)
0x000000000040113e <+74>: jne 0x401145 <phase_6+81>
0x0000000000401140 <+76>: callq 0x40143a <explode_bomb>
0x0000000000401145 <+81>: add $0x1,%ebx
0x0000000000401148 <+84>: cmp $0x5,%ebx
0x000000000040114b <+87>: jle 0x401135 <phase_6+65>
0x000000000040114d <+89>: add $0x4,%r13
0x0000000000401151 <+93>: jmp 0x401114 <phase_6+32>
分析知本谜题六个输入数字均小于等于6，且六个数字各不相同
0x0000000000401153 <+95>: lea 0x18(%rsp),%rsi
0x0000000000401158 <+100>: mov %r14,%rax
0x000000000040115b <+103>: mov $0x7,%ecx
0x0000000000401160 <+108>: mov %ecx,%edx
0x0000000000401162 <+110>: sub (%rax),%edx
0x0000000000401164 <+112>: mov %edx,(%rax)
0x0000000000401166 <+114>: add $0x4,%rax
0x000000000040116a <+118>: cmp %rsi,%rax
0x000000000040116d <+121>: jne 0x401160 <phase_6+108>
设六个输入按顺序为a[0]至a[5]，上述循环令a[i] = 7 - a[i]
0x000000000040116f <+123>: mov $0x0,%esi
0x0000000000401174 <+128>: jmp 0x401197 <phase_6+163>
0x0000000000401176 <+130>: mov 0x8(%rdx),%rdx
0x000000000040117a <+134>: add $0x1,%eax
0x000000000040117d <+137>: cmp %ecx,%eax
0x000000000040117f <+139>: jne 0x401176 <phase_6+130>
0x0000000000401181 <+141>: jmp 0x401188 <phase_6+148>
0x0000000000401183 <+143>: mov $0x6032d0,%edx
0x0000000000401188 <+148>: mov %rdx,0x20(%rsp,%rsi,2)
0x000000000040118d <+153>: add $0x4,%rsi
0x0000000000401191 <+157>: cmp $0x18,%rsi
0x0000000000401195 <+161>: je 0x4011ab <phase_6+183>
0x0000000000401197 <+163>: mov (%rsp,%rsi,1),%ecx
0x000000000040119a <+166>: cmp $0x1,%ecx
0x000000000040119d <+169>: jle 0x401183 <phase_6+143>
0x000000000040119f <+171>: mov $0x1,%eax
0x00000000004011a4 <+176>: mov $0x6032d0,%edx
0x00000000004011a9 <+181>: jmp 0x401176 <phase_6+130>
分析知有一链表首地址为0x6032d0，该链表一个结点16字节，后8字节用于存放指向下一个结点的指针，于是顺藤摸瓜找出该链表所有结点，设结点按顺序分别为b[0]至b[5]，上述代码作用为将a[i] - 1对应的结点地址放于%rsp + 32为基地址的栈中(e.g. 假设a[0] = 3，则将b[2]放于(%rsp + 32 + 0 * 8)处空间中)
(gdb) x /16xb 0x6032d0
0x6032d0 <node1>: 0x4c 0x01 0x00 0x00 0x01 0x00 0x00 0x00
0x6032d8 <node1+8>: 0xe0 0x32 0x60 0x00 0x00 0x00 0x00 0x00
(gdb) x /16xb 0x6032e0
0x6032e0 <node2>: 0xa8 0x00 0x00 0x00 0x02 0x00 0x00 0x00
0x6032e8 <node2+8>: 0xf0 0x32 0x60 0x00 0x00 0x00 0x00 0x00
(gdb) x /16xb 0x6032f0
0x6032f0 <node3>: 0x9c 0x03 0x00 0x00 0x03 0x00 0x00 0x00
0x6032f8 <node3+8>: 0x00 0x33 0x60 0x00 0x00 0x00 0x00 0x00
(gdb) x /16xb 0x603300
0x603300 <node4>: 0xb3 0x02 0x00 0x00 0x04 0x00 0x00 0x00
0x603308 <node4+8>: 0x10 0x33 0x60 0x00 0x00 0x00 0x00 0x00
(gdb) x /16xb 0x603310
0x603310 <node5>: 0xdd 0x01 0x00 0x00 0x05 0x00 0x00 0x00
0x603318 <node5+8>: 0x20 0x33 0x60 0x00 0x00 0x00 0x00 0x00
(gdb) x /16xb 0x603320
0x603320 <node6>: 0xbb 0x01 0x00 0x00 0x06 0x00 0x00 0x00
0x603328 <node6+8>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00
继续阅读
0x00000000004011ab <+183>: mov 0x20(%rsp),%rbx
0x00000000004011b0 <+188>: lea 0x28(%rsp),%rax
0x00000000004011b5 <+193>: lea 0x50(%rsp),%rsi
0x00000000004011ba <+198>: mov %rbx,%rcx
0x00000000004011bd <+201>: mov (%rax),%rdx
0x00000000004011c0 <+204>: mov %rdx,0x8(%rcx)
0x00000000004011c4 <+208>: add $0x8,%rax
0x00000000004011c8 <+212>: cmp %rsi,%rax
0x00000000004011cb <+215>: je 0x4011d2 <phase_6+222>
0x00000000004011cd <+217>: mov %rdx,%rcx
0x00000000004011d0 <+220>: jmp 0x4011bd <phase_6+201>
上述代码将结点按新的顺序链成链表
0x00000000004011d2 <+222>: movq $0x0,0x8(%rdx)
0x00000000004011da <+230>: mov $0x5,%ebp
0x00000000004011df <+235>: mov 0x8(%rbx),%rax
0x00000000004011e3 <+239>: mov (%rax),%eax
0x00000000004011e5 <+241>: cmp %eax,(%rbx)
0x00000000004011e7 <+243>: jge 0x4011ee <phase_6+250>
0x00000000004011e9 <+245>: callq 0x40143a <explode_bomb>
0x00000000004011ee <+250>: mov 0x8(%rbx),%rbx
0x00000000004011f2 <+254>: sub $0x1,%ebp
0x00000000004011f5 <+257>: jne 0x4011df <phase_6+235>
分析知正确的结点值应从高到低排列，又因比较结点值时使用的是%eax寄存器，故比较的是各结点前四字节的值，即根据我们输入的六个不同数值a[0]至a[5]，分别取a[i] = 7 - a[i]，再用新的a[i]值将原链表结点顺序重排得新链表，保证新链表的结点值为从高至低排列。原各结点值如下表
phase_6
按从大到小排列为 [node3, node4, node5, node6, node1, node2]
a[0]新 - 1 = 3
a[1]新 - 1 = 4
...
a[5]新 - 1 = 2
而
a[i]新 = 7 - a[i]旧
故
a旧 = [4, 3 ,2 ,1 ,6, 5]
即应输入六数分别为[4, 3 ,2 ,1 ,6, 5]
secret_phase
反汇编phase_defused()函数
0x00000000004015c4 <+0>: sub $0x78,%rsp
0x00000000004015c8 <+4>: mov %fs:0x28,%rax
0x00000000004015d1 <+13>: mov %rax,0x68(%rsp)
0x00000000004015d6 <+18>: xor %eax,%eax
0x00000000004015d8 <+20>: cmpl $0x6,0x202181(%rip) # 0x603760 <num_input_strings>
0x00000000004015df <+27>: jne 0x40163f <phase_defused+123>
发现只有六个谜题都破解后才会触发隐藏谜题，继续向下分析
0x00000000004015e1 <+29>: lea 0x10(%rsp),%r8
0x00000000004015e6 <+34>: lea 0xc(%rsp),%rcx
0x00000000004015eb <+39>: lea 0x8(%rsp),%rdx
0x00000000004015f0 <+44>: mov $0x402619,%esi
0x00000000004015f5 <+49>: mov $0x603870,%edi
0x00000000004015fa <+54>: callq 0x400bf0 <__isoc99_sscanf@plt>
0x00000000004015ff <+59>: cmp $0x3,%eax
0x0000000000401602 <+62>: jne 0x401635 <phase_defused+113>
发现函数调用首地址为0x400bf0的sscanf()函数读入数据，查看%0x402619处内容，得
(gdb) x /s 0x402619
0x402619: "%d %d %s"
故知一次读入两个int型数据和一个字符串，分别存入0x8(%rsp), 0xc(%rsp), 0x10(%rsp)中
0x0000000000401604 <+64>: mov $0x402622,%esi
0x0000000000401609 <+69>: lea 0x10(%rsp),%rdi
0x000000000040160e <+74>: callq 0x401338 <strings_not_equal>
0x0000000000401613 <+79>: test %eax,%eax
0x0000000000401615 <+81>: jne 0x401635 <phase_defused+113>
接着phase_defused()调用strings_not_euqal()检测我们输入的字符串与首地址为0x402622处的模式串是否匹配，于是查看该地址处的字符串得正解
(gdb) x /s 0x402622
0x402622: "DrEvil"
需注意，phase_defused()函数并未调用诸如read_line()等函数读取输入，而是直接默认从0x603870地址处读取数据。而前六个谜题每个都调用了一次read_line()函数，再通过
mov %rax, %rdi
指令将输入的数据传给相应函数，于是猜测0x603870为main()函数中某次调用read_line()参数获得用户输入后传给phase_x()函数的地址，检查六次调用read_line()后read_line()传送给phase_x()函数的地址，得六个地址分别为
0x603780
0x6037d0
0x603820
0x603870
0x6038c0
0x603910
知0x603870为第四次read_line()后传递给phase_4()的输入数据的首地址，而第四个谜题需输入两个int型变量，因此只需在第四题的答案后面加上字符串"DrEvil"即可在六个谜题结束后触发隐藏谜题，继续分析
0x0000000000401617 <+83>: mov $0x4024f8,%edi
0x000000000040161c <+88>: callq 0x400b10 <puts@plt>
0x0000000000401621 <+93>: mov $0x402520,%edi
0x0000000000401626 <+98>: callq 0x400b10 <puts@plt>
0x000000000040162b <+103>: mov $0x0,%eax
0x0000000000401630 <+108>: callq 0x401242 <secret_phase>
0x0000000000401635 <+113>: mov $0x402558,%edi
0x000000000040163a <+118>: callq 0x400b10 <puts@plt>
0x000000000040163f <+123>: mov 0x68(%rsp),%rax
0x0000000000401644 <+128>: xor %fs:0x28,%rax
0x000000000040164d <+137>: je 0x401654 <phase_defused+144>
0x000000000040164f <+139>: callq 0x400b30 <__stack_chk_fail@plt>
0x0000000000401654 <+144>: add $0x78,%rsp
0x0000000000401658 <+148>: retq
函数输出两字符串，调用secret_phase()函数，再输出一字符串，检查栈是否溢出，结束。于是接下来分析secret_phase()函数
0x0000000000401242 <+0>: push %rbx
0x0000000000401243 <+1>: callq 0x40149e <read_line>
0x0000000000401248 <+6>: mov $0xa,%edx
0x000000000040124d <+11>: mov $0x0,%esi
0x0000000000401252 <+16>: mov %rax,%rdi
0x0000000000401255 <+19>: callq 0x400bd0 <strtol@plt>
0x000000000040125a <+24>: mov %rax,%rbx
0x000000000040125d <+27>: lea -0x1(%rax),%eax
0x0000000000401260 <+30>: cmp $0x3e8,%eax
0x0000000000401265 <+35>: jbe 0x40126c <secret_phase+42>
0x0000000000401267 <+37>: callq 0x40143a <explode_bomb>
通过调用read_line()函数读入字符串，并调用strtol()函数将其转换为十进制数字，且该数字应小于等于0x3e9，否则炸弹爆炸
0x000000000040126c <+42>: mov %ebx,%esi
0x000000000040126e <+44>: mov $0x6030f0,%edi
0x0000000000401273 <+49>: callq 0x401204 <fun7>
0x0000000000401278 <+54>: cmp $0x2,%eax
0x000000000040127b <+57>: je 0x401282 <secret_phase+64>
0x000000000040127d <+59>: callq 0x40143a <explode_bomb>
0x0000000000401282 <+64>: mov $0x402438,%edi
0x0000000000401287 <+69>: callq 0x400b10 <puts@plt>
0x000000000040128c <+74>: callq 0x4015c4 <phase_defused>
0x0000000000401291 <+79>: pop %rbx
0x0000000000401292 <+80>: retq
函数将地址0x6030f0送入%rdi后，调用首地址为0x401204的fun7()函数，且知该函数必须返回数值2，反汇编fun7()函数进行分析
0x0000000000401204 <+0>: sub $0x8,%rsp
0x0000000000401208 <+4>: test %rdi,%rdi
0x000000000040120b <+7>: je 0x401238 <fun7+52>
0x000000000040120d <+9>: mov (%rdi),%edx
0x000000000040120f <+11>: cmp %esi,%edx
0x0000000000401211 <+13>: jle 0x401220 <fun7+28>
0x0000000000401213 <+15>: mov 0x8(%rdi),%rdi
0x0000000000401217 <+19>: callq 0x401204 <fun7>
0x000000000040121c <+24>: add %eax,%eax
0x000000000040121e <+26>: jmp 0x40123d <fun7+57>
0x0000000000401220 <+28>: mov $0x0,%eax
0x0000000000401225 <+33>: cmp %esi,%edx
0x0000000000401227 <+35>: je 0x40123d <fun7+57>
0x0000000000401229 <+37>: mov 0x10(%rdi),%rdi
0x000000000040122d <+41>: callq 0x401204 <fun7>
0x0000000000401232 <+46>: lea 0x1(%rax,%rax,1),%eax
0x0000000000401236 <+50>: jmp 0x40123d <fun7+57>
0x0000000000401238 <+52>: mov $0xffffffff,%eax
0x000000000040123d <+57>: add $0x8,%rsp
0x0000000000401241 <+61>: retq
尝试将该函数反编译为c代码风格
fun7(x, y)
x in %rdi, y in %rsi, p for %rdx
if (x == 0) return -1;
p = *x;
if (p <= y) {
if (p == y) return 0;
return 2 * fun7(x, y) + 1;
}
x = *(x + 8);
return 2 * fun7(x, y);
初次调用fun7()函数时，x值为0x6030f0, y值为我们输入的一个字符串转换所得数值，结合0x6030f0内存地址的值等，可以推出一个答案y值为22(0x16).在我通过此方法推出一个答案值后，参考他人题解，知0x6030f0为一二叉树根节点地址，该数每个结点含一个值和两个指向左右儿子的指针
(gdb) x /80a 0x6030f0
0x6030f0 <n1>: 0x24 0x603110 <n21>
0x603100 <n1+16>: 0x603130 <n22> 0x0
0x603110 <n21>: 0x8 0x603190 <n31>
0x603120 <n21+16>: 0x603150 <n32> 0x0
0x603130 <n22>: 0x32 0x603170 <n33>
0x603140 <n22+16>: 0x6031b0 <n34> 0x0
0x603150 <n32>: 0x16 0x603270 <n43>
0x603160 <n32+16>: 0x603230 <n44> 0x0
0x603170 <n33>: 0x2d 0x6031d0 <n45>
0x603180 <n33+16>: 0x603290 <n46> 0x0
0x603190 <n31>: 0x6 0x6031f0 <n41>
0x6031a0 <n31+16>: 0x603250 <n42> 0x0
0x6031b0 <n34>: 0x6b 0x603210 <n47>
0x6031c0 <n34+16>: 0x6032b0 <n48> 0x0
由以上信息可构建树为
secret_phase
故可的答案为22(0x16), 20(0x14).
至此，全部谜题破解
fez@LAPTOP-MB5DL415:/mnt/d/repositories/CSAPP/Labs/BombLab$ cat phases.txt
Border relations with Canada have never been better.
1 2 4 8 16 32
0 207
0 0 DrEvil
IONEFG
4 3 2 1 6 5
20
fez@LAPTOP-MB5DL415:/mnt/d/repositories/CSAPP/Labs/BombLab$ ./bomb phases.txt
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
Phase 1 defused. How about the next one?
That's number 2. Keep going!
Halfway there!
So you got that one. Try this one.
Good work! On to the next...
Curses, you've found the secret phase!
But finding it and solving it are quite different...
Wow! You've defused the secret stage!
Congratulations! You've defused the bomb!
2021/7/27
21:16
