CSAPP bomb lab4

Phase_4

phase_4汇编代码：

000000000040100c <phase_4>:
  40100c:	48 83 ec 18          sub    $0x18,%rsp				#rsp-=0x18						
  401010:	48 8d 4c 24 0c       lea    0xc(%rsp),%rcx			#rcx=rsp+0xc
  401015:	48 8d 54 24 08       lea    0x8(%rsp),%rdx			#rdx=rsp+0x8
  40101a:	be cf 25 40 00       mov    $0x4025cf,%esi			#rsi=0x4025cf
  40101f:	b8 00 00 00 00       mov    $0x0,%eax				#eax=0
  401024:	e8 c7 fb ff ff       callq  400bf0 <[email protected]>
  #查(gdb)x/1s 0x4025cf得"%d %d",所以sscanf两个int型整数，第1个数据x存于0x8(%rsp),第2个数据y存于0xc(%rsp)
  401029:	83 f8 02             cmp    $0x2,%eax							
  40102c:	75 07                jne    401035 <phase_4+0x29>	#if (rax!=2)->bomb()
  40102e:	83 7c 24 08 0e       cmpl   $0xe,0x8(%rsp)			#else
  401033:	76 05                jbe    40103a <phase_4+0x2e>	#if (0=<x<=0xe)->{40103a}
  401035:	e8 00 04 00 00       callq  40143a <explode_bomb>	#else bomb()
  40103a:	ba 0e 00 00 00       mov    $0xe,%edx				#edx=0xe
  40103f:	be 00 00 00 00       mov    $0x0,%esi				#esi=0
  401044:	8b 7c 24 08          mov    0x8(%rsp),%edi			#edi=x
  401048:	e8 81 ff ff ff       callq  400fce <func4>			
  40104d:	85 c0                test   %eax,%eax				
  40104f:	75 07                jne    401058 <phase_4+0x4c>	#if(返回值!=0)->bomb()
  401051:	83 7c 24 0c 00       cmpl   $0x0,0xc(%rsp)			#else
  401056:	74 05                je     40105d <phase_4+0x51>	#if (y!=0)->bomb()
  401058:	e8 dd 03 00 00       callq  40143a <explode_bomb>	#else
  40105d:	48 83 c4 18          add    $0x18,%rsp				#->成功

Phase_4思路：

调用ssacnf(input,"%d %d",&x,&y),必须成功输入到&x和&y中，必须使得 x>=0 && x<=0xe,然后置参数1:edi=x ,参数2:esi=0,参数3:edx=0xe 调用func4函数。必须保证返回值为0且y的值为0才成功。所以y的值确定为0，x的值在0～0xe之间，确切可行解需进入func4()分析。

编写成C代码为：

void func4(char *input)
{
	int y;
	int x;
	if (sscanf(input,"%d %d",&x,&y)!=2)
		bomb();
	if (x<0 || x>0xe)
		bomb();
	int result=func4(x,0,0xe,&y);
	if (y!=0 || result!=0)
		bomb();
	return;
} 

---

现在，就剩下进入func4函数中进行分析：

0000000000400fce <func4>:
// func4(a=x,b=0,c=0xe)
// a,b,c分别存于rdi,rsi,rdx
  400fce:	48 83 ec 08          sub    $0x8,%rsp				#rsp-=8		
  400fd2:	89 d0                mov    %edx,%eax				#rax=0xe
  400fd4:	29 f0                sub    %esi,%eax				#rax-=b
  400fd6:	89 c1                mov    %eax,%ecx				###rcx=rax
  400fd8:	c1 e9 1f             shr    $0x1f,%ecx				
  400fdb:	01 c8                add    %ecx,%eax				#rax+=rax>>0x1f
  400fdd:	d1 f8                sar    %eax					#rax= rax/2
  400fdf:	8d 0c 30             lea    (%rax,%rsi,1),%ecx		#rcx=rax+rsi
  400fe2:	39 f9                cmp    %edi,%ecx				
  400fe4:	7e 0c                jle    400ff2 <func4+0x24>		#if(rcx<=rdi)->{400ff2}
  400fe6:	8d 51 ff             lea    -0x1(%rcx),%edx			#rax=rcx-1
  400fe9:	e8 e0 ff ff ff       callq  400fce <func4>			#callq <func4>
  400fee:	01 c0                add    %eax,%eax
  400ff0:	eb 15                jmp    401007 <func4+0x39>	
  400ff2:	b8 00 00 00 00       mov    $0x0,%eax				#rax=0
  400ff7:	39 f9                cmp    %edi,%ecx
  400ff9:	7d 0c                jge    401007 <func4+0x39>		#if(rcx>=rdi)->{401007}
  400ffb:	8d 71 01             lea    0x1(%rcx),%esi			#else rsi=rcx+1
  400ffe:	e8 cb ff ff ff       callq  400fce <func4>			#callq <func4>
  401003:	8d 44 00 01          lea    0x1(%rax,%rax,1),%eax	#rax=2*rax+1
  401007:	48 83 c4 08          add    $0x8,%rsp				#rsp+=8
  40100b:	c3                   retq 							#return rax 

分析其逻辑，将func4汇编代码的逻辑转化为C代码：

int func4(a,b,c)
{
	int mid=c-b;
	mid=(mid>>31+mid)/2+b;
	if (mid<a)
		return 2*func4(a+mid+1,c)+1;
	else if (mid>a)
		return 2*func4(a,b,mid-1);
	else
		return 0;
}
// 一开始传入的参数为func4(x,0,14)
// 首次传入进入func4的mid值为7，因而若x=7，可以直接return 0
// 其他答案难以直观看出，可编代码试验，在此不做赘述

因而，得到其中一个解：“7 0” .