Hey, I’m back.
This time we will solve phase 4.
Different from before, we need to handle two functions in this phase.
This is the code of phase 4:
000000000040100c <phase_4>: 40100c: 48 83 ec 18 sub $0x18,%rsp 401010: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx 401015: 48 8d 54 24 08 lea 0x8(%rsp),%rdx 40101a: be cf 25 40 00 mov $0x4025cf,%esi 40101f: b8 00 00 00 00 mov $0x0,%eax 401024: e8 c7 fb ff ff callq 400bf0 <__isoc99_sscanf@plt> 401029: 83 f8 02 cmp $0x2,%eax 40102c: 75 07 jne 401035 <phase_4+0x29> 40102e: 83 7c 24 08 0e cmpl $0xe,0x8(%rsp) 401033: 76 05 jbe 40103a <phase_4+0x2e> 401035: e8 00 04 00 00 callq 40143a <explode_bomb> 40103a: ba 0e 00 00 00 mov $0xe,%edx 40103f: be 00 00 00 00 mov $0x0,%esi 401044: 8b 7c 24 08 mov 0x8(%rsp),%edi 401048: e8 81 ff ff ff callq 400fce <func4> 40104d: 85 c0 test %eax,%eax 40104f: 75 07 jne 401058 <phase_4+0x4c> 401051: 83 7c 24 0c 00 cmpl $0x0,0xc(%rsp) 401056: 74 05 je 40105d <phase_4+0x51> 401058: e8 dd 03 00 00 callq 40143a <explode_bomb> 40105d: 48 83 c4 18 add $0x18,%rsp 401061: c3 retq
We can find that it calls a special function “func4”.
func4:
0000000000400fce <func4>: 400fce: 48 83 ec 08 sub $0x8,%rsp 400fd2: 89 d0 mov %edx,%eax 400fd4: 29 f0 sub %esi,%eax 400fd6: 89 c1 mov %eax,%ecx 400fd8: c1 e9 1f shr $0x1f,%ecx 400fdb: 01 c8 add %ecx,%eax 400fdd: d1 f8 sar %eax 400fdf: 8d 0c 30 lea (%rax,%rsi,1),%ecx 400fe2: 39 f9 cmp %edi,%ecx 400fe4: 7e 0c jle 400ff2 <func4+0x24> 400fe6: 8d 51 ff lea -0x1(%rcx),%edx 400fe9: e8 e0 ff ff ff callq 400fce <func4> 400fee: 01 c0 add %eax,%eax 400ff0: eb 15 jmp 401007 <func4+0x39> 400ff2: b8 00 00 00 00 mov $0x0,%eax 400ff7: 39 f9 cmp %edi,%ecx 400ff9: 7d 0c jge 401007 <func4+0x39> 400ffb: 8d 71 01 lea 0x1(%rcx),%esi 400ffe: e8 cb ff ff ff callq 400fce <func4> 401003: 8d 44 00 01 lea 0x1(%rax,%rax,1),%eax 401007: 48 83 c4 08 add $0x8,%rsp 40100b: c3 retq
Back to phase 4. At 40101a, we can find that an address was stored in esi and passed to Scanf. We print the content of the address 0x4025cf. It is “%d %d”. So we need to put two integer numbers first. And if we do not do this, it will explode.
The numbers we put into it will be saved in stacks. The first one is 0x8(%rsp) and it must be less or equal to 14, then the next one is 0xc(%rsp). We can also know that the addresses of these numbers are stored in %rcx and %rdx.
Then it will prepare to call func4. Before it wants to do that, it set %edx=15, %esi=0, and %edi = the first number we input. Then it calls func4. After that, when func4 returns to phase 4, test whether %eax(return value from fun4) is 0. Obviously, it must be 0. From 401051 to 401058, it also tests whether the 2nd we input is 0. And the answer is yes again.
OK, we know what phase 4 wants to do. It’s time to explore the operation of func4.
func4 does a lot about ax, di, si, dx, and cx, so we simplify it first.
// write fun4() in c style directly
int fun4(rdi,rsi,rdx)
{
eax=edx;
eax=eax-esi;
ecx=eax;
ecx>>31;
eax=eax+ecx;
eax>>1;
ecx=rax+rsi;
....
}
Then we can substitute some of them and simplify it.
int fun4(rdi,rsi,rdx)
{
//eax=edx;
eax=edx-esi;
ecx=edx-esi;
ecx>>31;
//eax=eax+ecx;
//eax>>1;
eax=(edx-esi+(edx-esi)>>31)>>1
ecx=rax+rsi;
...
}
Then we talk about the structure of the rest part.
// In fact, we still write it into c style directly
if(ecx<=edi)
{
goto 400ff2;
}
edx=rcx-1;
fun4();
eax>>1;
goto 401007;//return;
400ff2:
eax=0;
if(ecx>=edi)
{
goto 401007;//return;
}
esi=1+rcx;
fun4();
eax=rax*2+1;
return;
401007:
return;
It seems like only three blocks of code. The first one goes until goto 401007, the second is from 400ff2 to 401007, and the last part is “return”;
Then we substitute the second into the first. After that, they come like these:
int fun4(rdi,rsi,rdx)
{
eax=edx-esi;
ecx=edx-esi;
ecx>>31;
eax=(edx-esi+(edx-esi)>>31)>>1
ecx=rax+rsi;
if(ecx<=edi)
{
goto 400ff2;
eax=0;
if(ecx>=edi)
{
goto 401007;//return;
}
esi=1+rcx;
fun4();
eax=rax*2+1;
return;
}
else{
edx=rcx-1;
fun4();
eax>>1;
goto 401007;//return;
}
return;
}
We can figure out how the function runs now. It’s time to write it into the executable c function.
//di is x,si is y,dx is z,cx is num,ax is ret
int fun4(int x,int y,int z)
{
int ret=z-y;
int num=(z-y)>>31;
ret=(z-y-(z-y)>>31)>>1;
num=ret+y;
if(num<=x)
{
ret=0;
if(num==x)
return ret;
y=num+1;
ret=fun4(x,y,z);
ret=ret*2+1;
return ret;
}
else
{
z=num-1;
ret=fun4();
ret>>=2;
return ret;
}
}
Ah ha, it looks too long. Simplify it again!
//di is x,si is y,dx is z,cx is num,ax is ret
int fun4(int x,int y,int z)
{
int ret=z-y;
int num=(z-y)>>31;
ret=(ret-num)/2;
num=ret+y;
if(num<=x)
{
if(num==x)
return 0;
return (fun4(x,num+1,z)*2+1);
}
else
{
return fun4(x,y,num-1)*2;
}
}
Then…
int fun4(int x,int y,int z)
{
int num=(z-y)/2+y;//because (z-y)>>31 is 0, it is also equal to num=(y+z)/2，不会证明自己学数论
if(num<=x)
{
if(num>=x)
return 0;
return (fun4(x,num+1,z)*2+1);
}
else
{
return fun4(x,y,num-1)*2;
}
}
At the beginning, y is 0 and z is 14. We want this function returns 0 at the end. It is obvious that if x==(z-y)/2+y, it will return 0 within the first loop.
So one of the answers is 7 0;
Finished? We are not satisfied with it! There must be more solutions!
We can compare the outer if. The first block of “IF” will return 0 or something plus 1. The else block returns something multiple 2. We expect the function gives us a 0. So when num<=x, num must equal x, otherwise there will be at least 1 in the return value. Then we can find the “*2” in return value is meaningless because we want it 0.
这里英语不会说，英语太烂了，笑死，直接汉语吧。然后再回到第一个注释，我们可以简写成int num=(y+z)/2。这时啥？这是中间值阿。说白了就是一直在中间值查找，要是相等直接返回0，皆大欢喜。要是x比中间值大，直接寄，所以说我们上来肯定要小于等于7。要是x比中间值小，那就上一个中间值处以二再-1，所以他是这个规律：14，7，3，1，0。
这样就真的够了？错了。老外的教材很多时候可不是为了凑体而凑题，应该是一个完整的情景。我们仔细观察一下，当x比中间值小的时候，他是除以2一直走下去一直到0.这也算是一种二分查找，找到的是除以二然后往下取整的数。如果大于呢？给个15看看
这不就是二分查找吗哥哥。
然后他的返回值也很有意思，就是这个数字比中间值小，他就乘以2，比他大，那就加1.
所以是个没啥用的二分查找。
这次鸽的有点久，不过放假就快了，加油，Range！
In the end, let us try our answer!
We got that one! Cheers! 😀
The key of phase 1: Border relations with Canada have never been better.
The key of phase 2: 1 2 4 8 16 32
The key of phase 3: 0 207
The key of phase 4: 0 0, 1 0, 3 0, 7 0
//后记：发现这个题实际上手下留情了，没有pop和push这种需要保存的操作
Views: 99