We'll analyze three functions.
phase_4
func4
__isoc99_sscanf
__isoc99_sscanf
Summarizing what we found out about the __isoc99_sscanf function in phase2:
- The integers you enter are converted into an array from the string stored in %rdi.
- A pointer to the first element is stored in %rsp.
- The number of integers you entered is returned in %rax.
So if you entered 50 100, you get the situation on the right.
phase_4
Dump of assembler code for function phase_4: => 0x0000555555401455 <+0>: sub $0x18,%rsp 0x0000555555401459 <+4>: mov %fs:0x28,%rax 0x0000555555401462 <+13>: mov %rax,0x8(%rsp) 0x0000555555401467 <+18>: xor %eax,%eax 0x0000555555401469 <+20>: lea 0x4(%rsp),%rcx 0x000055555540146e <+25>: mov %rsp,%rdx 0x0000555555401471 <+28>: lea 0x1975(%rip),%rsi # 0x555555402ded 0x0000555555401478 <+35>: callq 0x555555400fc0 <__isoc99_sscanf@plt> 0x000055555540147d <+40>: cmp $0x2,%eax 0x0000555555401480 <+43>: jne 0x555555401488 <phase_4+51> 0x0000555555401482 <+45>: cmpl $0xe,(%rsp) 0x0000555555401486 <+49>: jbe 0x55555540148d <phase_4+56> 0x0000555555401488 <+51>: callq 0x555555401a90 <explode_bomb> 0x000055555540148d <+56>: mov $0xe,%edx 0x0000555555401492 <+61>: mov $0x0,%esi 0x0000555555401497 <+66>: mov (%rsp),%edi 0x000055555540149a <+69>: callq 0x555555401421 <func4> 0x000055555540149f <+74>: cmp $0x7,%eax 0x00005555554014a2 <+77>: jne 0x5555554014ab <phase_4+86> 0x00005555554014a4 <+79>: cmpl $0x7,0x4(%rsp) 0x00005555554014a9 <+84>: je 0x5555554014b0 <phase_4+91> 0x00005555554014ab <+86>: callq 0x555555401a90 <explode_bomb> 0x00005555554014b0 <+91>: mov 0x8(%rsp),%rax 0x00005555554014b5 <+96>: xor %fs:0x28,%rax 0x00005555554014be <+105>: jne 0x5555554014c5 <phase_4+112> 0x00005555554014c0 <+107>: add $0x18,%rsp 0x00005555554014c4 <+111>: retq 0x00005555554014c5 <+112>: callq 0x555555400f20 <__stack_chk_fail@plt>
<+28>
It puts "%d %d" in %rsi and passes it as an argument to the __isoc99_sscanf function.
(gdb) x/s 0x555555402ded 0x555555402ded: "%d %d"
<+35>
-
Since the function is called with "%d %d", we can tell that we need to enter two integers.
-
A pointer to the integer array is stored in %rsp.
-
The number of integers entered is stored in %rax.
<+40 ~ 43>
0x000055555540147d <+40>: cmp $0x2,%eax 0x0000555555401480 <+43>: jne 0x555555401488 <phase_4+51>
0x0000555555401488 <+51>: callq 0x555555401a90 <explode_bomb>
<+40> : Compares the number of integers entered with 2.
<+43> : If the number of integers entered is not 2, it jumps to <+51> and the bomb explodes, so the number of integers you have to enter is 2.
<+45 ~ 69>
0x0000555555401482 <+45>: cmpl $0xe,(%rsp) 0x0000555555401486 <+49>: jbe 0x55555540148d <phase_4+56> 0x0000555555401488 <+51>: callq 0x555555401a90 <explode_bomb> 0x000055555540148d <+56>: mov $0xe,%edx 0x0000555555401492 <+61>: mov $0x0,%esi 0x0000555555401497 <+66>: mov (%rsp),%edi 0x000055555540149a <+69>: callq 0x555555401421 <func4>
<+45> : (%rsp) is the first integer entered, as shown in the figure on the right. It compares the first integer with 14.
<+49> : Since this is an unsigned comparison, if the first integer is less than 0 or greater than 14, it moves to <+51>.
<+51> : The bomb explodes. In other words, the first integer must be at least 0 and at most 14.
<+56> : Stores 14 in %edx.
<+61> : Stores 0 in %esi.
<+66> : Stores the first integer in %edi.
<+69> : Since func4 is called right away, we can guess that %edx, %esi, and %edi act as the function's arguments.
<+72 ~ 69>
0x000055555540149f <+74>: cmp $0x7,%eax 0x00005555554014a2 <+77>: jne 0x5555554014ab <phase_4+86> 0x00005555554014a4 <+79>: cmpl $0x7,0x4(%rsp) 0x00005555554014a9 <+84>: je 0x5555554014b0 <phase_4+91> 0x00005555554014ab <+86>: callq 0x555555401a90 <explode_bomb> 0x00005555554014b0 <+91>: mov 0x8(%rsp),%rax 0x00005555554014b5 <+96>: xor %fs:0x28,%rax 0x00005555554014be <+105>: jne 0x5555554014c5 <phase_4+112> 0x00005555554014c0 <+107>: add $0x18,%rsp 0x00005555554014c4 <+111>: retq 0x00005555554014c5 <+112>: callq 0x555555400f20 <__stack_chk_fail@plt>
<+74> : After func4 returns, R[%eax] will be either still 2 (it's guaranteed that the number of integers entered is always two) or func4's return value. It compares that value with 7.
<+77> : If R[%eax] is not 7, it moves to <+86> and the bomb explodes, so we can tell that func4 is a function that has a return value.
And we have to pass arguments so that func4's return value comes out as 7.
<+79> : 0x4(%rsp) is the second number entered. It compares the second number with 7.
<+84> : Checks whether the second number equals 7.
<+86> : If the second number is not 7, the bomb explodes, so the second number must be 7.
<After that> : This is ordinary code for finishing a function.
Before analyzing func4, let's sum up the conditions we need to solve the problem.
- The first number entered must be at least 0 and at most 14.
- The second number entered must be 7.
- %edx, %esi, and %edi are passed as arguments, and their values are as follows. R[%edx] = 14, R[%esi] = 0, R[%edi] = the first integer entered
- We have to pass arguments so the return value is 7, but R[%edx] and R[%esi] are fixed at 14 and 0. So we have to pass R[%edi] such that the return value is 7. In other words, we have to enter the first integer so that the return value comes out as 7.
func4
Dump of assembler code for function func4: 0x0000555555401421 <+0>: push %rbx 0x0000555555401422 <+1>: mov %edx,%eax 0x0000555555401424 <+3>: sub %esi,%eax 0x0000555555401426 <+5>: mov %eax,%ebx 0x0000555555401428 <+7>: shr $0x1f,%ebx 0x000055555540142b <+10>: add %eax,%ebx 0x000055555540142d <+12>: sar %ebx 0x000055555540142f <+14>: add %esi,%ebx 0x0000555555401431 <+16>: cmp %edi,%ebx 0x0000555555401433 <+18>: jg 0x55555540143d <func4+28> 0x0000555555401435 <+20>: cmp %edi,%ebx 0x0000555555401437 <+22>: jl 0x555555401449 <func4+40> 0x0000555555401439 <+24>: mov %ebx,%eax 0x000055555540143b <+26>: pop %rbx 0x000055555540143c <+27>: retq 0x000055555540143d <+28>: lea -0x1(%rbx),%edx 0x0000555555401440 <+31>: callq 0x555555401421 <func4> 0x0000555555401445 <+36>: add %eax,%ebx 0x0000555555401447 <+38>: jmp 0x555555401439 <func4+24> 0x0000555555401449 <+40>: lea 0x1(%rbx),%esi 0x000055555540144c <+43>: callq 0x555555401421 <func4> 0x0000555555401451 <+48>: add %eax,%ebx 0x0000555555401453 <+50>: jmp 0x555555401439 <func4+24>
If we let the first integer entered be a (0 <= a <= 14),
the arguments passed are R[%edx] = 14, R[%esi] = 0, R[%edi] = a.
We have to make the return value 7 through the value of a.
<+1 ~ 5>
0x0000555555401422 <+1>: mov %edx,%eax 0x0000555555401424 <+3>: sub %esi,%eax 0x0000555555401426 <+5>: mov %eax,%ebx
<+7 ~ 14>
0x0000555555401428 <+7>: shr $0x1f,%ebx 0x000055555540142b <+10>: add %eax,%ebx 0x000055555540142d <+12>: sar %ebx 0x000055555540142f <+14>: add %esi,%ebx
<+7> : Shifts %ebx right by 31. You can think of this as extracting the sign of %ebx.
<+10> : Adds %eax to %ebx.
<+12> : Shifts %ebx right once while preserving the sign. This is the same as dividing %ebx by 2.
<+14> : Adds %edi to %ebx.
Putting together the expression computed so far gives what's on the right.
<+16 ~ 27>
0x0000555555401431 <+16>: cmp %edi,%ebx 0x0000555555401433 <+18>: jg 0x55555540143d <func4+28> 0x0000555555401435 <+20>: cmp %edi,%ebx 0x0000555555401437 <+22>: jl 0x555555401449 <func4+40> 0x0000555555401439 <+24>: mov %ebx,%eax 0x000055555540143b <+26>: pop %rbx 0x000055555540143c <+27>: retq
<+16> : Compares R[%ebx] and R[%edi].
<+18> : If %ebx is greater, it jumps to <+28>.
<+20> : Compares again.
<+22> : If %ebx is smaller, it jumps to <+40>.
<+24> : It's neither greater nor smaller, so R[%ebx] == R[%edi]. Then it puts %ebx into %eax and returns.
<+28 ~ 50>
0x000055555540143d <+28>: lea -0x1(%rbx),%edx 0x0000555555401440 <+31>: callq 0x555555401421 <func4> 0x0000555555401445 <+36>: add %eax,%ebx 0x0000555555401447 <+38>: jmp 0x555555401439 <func4+24> 0x0000555555401449 <+40>: lea 0x1(%rbx),%esi 0x000055555540144c <+43>: callq 0x555555401421 <func4> 0x0000555555401451 <+48>: add %eax,%ebx 0x0000555555401453 <+50>: jmp 0x555555401439 <func4+24>
R[%ebx] > R[%edi]
- <+28> : Does R[%edx] = R[%rbx] - 1.
- <+31> : Goes back to the start of the code and calls itself recursively.
R[%ebx] > R[%edi]
- <+40> : Does R[%esi] = R[%rbx] + 1.
- <+34> : Goes back to the start of the code and calls itself recursively.
func4 conclusion
If you look at the code closely, you can see that it's code performing a binary search.
The search range is 0 to 14, where %esi handles the minimum, and %edx.
The search target is %edi, the first number we entered.
Then it stores the middle index between %edx and %esi in %ebx, compares that value with the target %edi, and branches.In the end, the return value is %ebx at the moment the search succeeds.
The return value having to be 7 means the index at the moment the search succeeds has to be 7.
Also, the search succeeding means R[%ebx] == R[%edi], so the first number, which is the search target, has to be 7.
It's a mystery why it runs a binary search on an array where the index and the value are exactly the same,
but in the end the first number has to be 7 and the second number has to be 7, so the answer is:
7 7