phase_6的代码很长,不过很有结构,按功能划分首先来看第一段:
00000000004010f4 <phase_6>: 4010f4: 41 56 push %r14 4010f6: 41 55 push %r13 4010f8: 41 54 push %r12 4010fa: 55 push %rbp 4010fb: 53 push %rbx 4010fc: 48 83 ec 50 sub $0x50,%rsp 401100: 49 89 e5 mov %rsp,%r13 401103: 48 89 e6 mov %rsp,%rsi 401106: e8 51 03 00 00 callq 40145c <read_six_numbers> 40110b: 49 89 e6 mov %rsp,%r14 40110e: 41 bc 00 00 00 00 mov $0x0,%r12d 401114: 4c 89 ed mov %r13,%rbp # the start of the outer while loop 401117: 41 8b 45 00 mov 0x0(%r13),%eax 40111b: 83 e8 01 sub $0x1,%eax 40111e: 83 f8 05 cmp $0x5,%eax 401121: 76 05 jbe 401128 <phase_6+0x34> # looping every number, every number is within [1,6] (integer) 401123: e8 12 03 00 00 callq 40143a <explode_bomb> 401128: 41 83 c4 01 add $0x1,%r12d 40112c: 41 83 fc 06 cmp $0x6,%r12d 401130: 74 21 je 401153 <phase_6+0x5f> # the exit of the outer while loop 401132: 44 89 e3 mov %r12d,%ebx 401135: 48 63 c3 movslq %ebx,%rax # the start of the inner for loop 401138: 8b 04 84 mov (%rsp,%rax,4),%eax 40113b: 39 45 00 cmp %eax,0x0(%rbp) 40113e: 75 05 jne 401145 <phase_6+0x51> # none of num1 ~ num6 can be the same 401140: e8 f5 02 00 00 callq 40143a <explode_bomb> 401145: 83 c3 01 add $0x1,%ebx 401148: 83 fb 05 cmp $0x5,%ebx 40114b: 7e e8 jle 401135 <phase_6+0x41> # the end of the inner for loop 40114d: 49 83 c5 04 add $0x4,%r13 401151: eb c1 jmp 401114 <phase_6+0x20> # the end of the outer while looppush是为保护原来的值,最后会pop回去。重要的在401100开始,将rsp的值赋给r13和rsi后调用read_six_numbers,这个函数在phase_2中我们遇到过,作用是将我们输入的6个数字存储在从rsi所存储地址开始的连续24个字节中,这里由于rsi已经被赋予了rsp的值,我们输入的6个数字被存储在rsp标记的连续24个字节中
接着是一个准备:rsp的值赋给r14,r12等于0
这个准备后是401114,我们会在后面看到这是一个while循环的开始,r13的值被赋给rbp,r13所指值被赋给eax,接着eax减去1,然后与5比较,在401121我们看到它必须小于等于5,否则触雷;接着r12加一,然后与6比较,如果不是6,就将r12赋给ebx,再将其赋给eax(这是内部for循环的开始),
接着关键的一步是,rsp+4*rax所指的值被赋给了eax,eax将会与rbp所指向的值比较,在40113e看见必须不相等,否则触雷,如果成功跳过,将ebx加上一后,ebx与5比较,直到ebx大于5,都要跳回401135(for循环的开始)
这两个循环嵌套做了什么呢?首先看外部的while,它将r13所指向的值减一与5比较,r13已经被赋予rsp的值,它指向的是num1,我们输入的第一个数,考虑到比较法是jbe,这个数必须是在[1,6]上的整数。r12被加上1,这个值是用来判断有多少个输入数已经被减一和5比较过了,它在值为6时标记退出,这时所有数都被比较过。
既然r12标记了现在比较的是哪一个数,r12被赋给ebx和rax,rax存储它的值后,rsp+4*rax就是它的下一个数,40113e表明这两个数不能相等,其后ebx而40114b的跳跃表明rax又加上1,rsp+4*rax就是下下个数,依旧不能与一开始的数相等... 这样一圈下来,比如r12是1的话,num1就不能与num2,num3...num6中任何一个相等
而在40114b满足后,r13被加上4,然后跳回while loop的开始,这时一切都一样,只是r13指向num2了,同样的套路进行下去,直到r13指向num6才结束
现在可以回答:这两个循环检查了我们输入的6个整数,它们全都要在[1,6]上,并且两两不相等
接下来看看第二段:
401153: 48 8d 74 24 18 lea 0x18(%rsp),%rsi 401158: 4c 89 f0 mov %r14,%rax 40115b: b9 07 00 00 00 mov $0x7,%ecx 401160: 89 ca mov %ecx,%edx # the start of a while loop 401162: 2b 10 sub (%rax),%edx 401164: 89 10 mov %edx,(%rax) # num1=7-num1, num2=7-num2, ... ,num6=7-num6 401166: 48 83 c0 04 add $0x4,%rax 40116a: 48 39 f0 cmp %rsi,%rax 40116d: 75 f1 jne 401160 <phase_6+0x6c> # the exit of a while loop, looped for 6 timesrsi标记了rsp+24,结束地址,rax存储r14,这时r14还存着rsp的值,然后ecx被赋成7,7被赋给edx,然后用edx减去eax处的值,把这个值存在eax处,接着eax+4,回到赋值给edx的地方,直到eax遇到rsi。这个循环的作用是把每个我们输入的num变成7-num
然后:
40116f: be 00 00 00 00 mov $0x0,%esi 401174: eb 21 jmp 401197 <phase_6+0xa3> 401176: 48 8b 52 08 mov 0x8(%rdx),%rdx # start of the loop 40117a: 83 c0 01 add $0x1,%eax 40117d: 39 c8 cmp %ecx,%eax 40117f: 75 f5 jne 401176 <phase_6+0x82> 401181: eb 05 jmp 401188 <phase_6+0x94> 401183: ba d0 32 60 00 mov $0x6032d0,%edx 401188: 48 89 54 74 20 mov %rdx,0x20(%rsp,%rsi,2) # make rsi+32+x store the location of the nodes according to numi order 40118d: 48 83 c6 04 add $0x4,%rsi 401191: 48 83 fe 18 cmp $0x18,%rsi 401195: 74 14 je 4011ab <phase_6+0xb7> #exit 401197: 8b 0c 34 mov (%rsp,%rsi,1),%ecx 40119a: 83 f9 01 cmp $0x1,%ecx 40119d: 7e e4 jle 401183 <phase_6+0x8f> 40119f: b8 01 00 00 00 mov $0x1,%eax 4011a4: ba d0 32 60 00 mov $0x6032d0,%edx 4011a9: eb cb jmp 401176 <phase_6+0x82>这一部分的循环不像for和while loop那样有结构,最好画一张图。rsi被赋成0后跳转401197,ecx被赋成rsp+rax所指向的值,然后与1比较,
如果小于等于1则跳到401183:edx赋成0x6032d0,rdx被赋给rsp+2*rsi+32所指向的为止,然后rsi加上4,与24比较,如果相等则跳出这个循环,否则将ecx被赋值成rsp+rsi所指向的值,继续与1比较的过程
不妨假设我们输入的第一个数就是6,所以从401174跳到401197,
ecx到这里变成了1,这样满足40119d的跳跃条件,跳到401183,edx赋成6032d0,然后把rdx存到rsp+32的位置(这时rsi是0),然后rsi加上4
6032d0那里存着什么呢? 用x/a命令看,那里存着一个数 0x0000014c,并且看起来是一个node1(终端显示)
这个node是什么结构的呢?401176处,rdx被赋值成rdx+8所指向的东西,看看0x6032d8,那里存着0x6032e0(node2的地址)
这样就能猜出来,node是一个结构体,含有两个量,第一个是整型数,第二个则是一个指针指向下一个node,这其实就是一个链表:
0x6032d0 <node1>: 0x10000014c 0x6032e0 <node2>
0x6032e0 <node2>: 0x2000000a8 0x6032f0 <node3>
0x6032f0 <node3>: 0x30000039c 0x603300 <node4>
0x603300 <node4>: 0x4000002b3 0x603310 <node5>
0x603310 <node5>: 0x5000001dd 0x603320 <node6>
0x603320 <node6>: 0x6000001bb 0x0 (注意每个整型数的第一个数字只代表这是第几个node,不是整型数的值的一部分)
那么上面的循环体在做什么?稍微观察可以看到,它的退出条件只有rsi==24,而rsi从0开始每次增加4,总共要处理6次
每次处理中,edx都首先被赋予0x6032d0,如果ecx本身就是1,就省去了40117a到40117f累加eax的过程,因为这时num就是1,指向第一个节点,那么就将rsp+32赋予这个节点的地址
如果eax不是1,就要经过那个累加直到eax==ecx,然后将rsp+32+2*rsi这个地址上存储某个节点的地址
那个节点是哪个呢?从401176可以看出,rdx在每次累加eax后都会变成下一个节点的地址(从第一个开始),那么最后它就变成了num的数值标记的那个节点
所以,这个循环的作用就是,按num1~num6的数值所标顺序在rsp+32到rsp+72这一段地址上存储6个节点的地址
例如,如果我输入1 2 3 4 5 6,在这里变成6 5 4 3 2 1, 节点的存储顺序就是node6 node5 node4 node3 node2 node1
接下来又是一个循环
4011ab: 48 8b 5c 24 20 mov 0x20(%rsp),%rbx 4011b0: 48 8d 44 24 28 lea 0x28(%rsp),%rax 4011b5: 48 8d 74 24 50 lea 0x50(%rsp),%rsi 4011ba: 48 89 d9 mov %rbx,%rcx 4011bd: 48 8b 10 mov (%rax),%rdx #starting a loop 4011c0: 48 89 51 08 mov %rdx,0x8(%rcx) # retail the linked list (set every node's tail pointer to the new next node) 4011c4: 48 83 c0 08 add $0x8,%rax 4011c8: 48 39 f0 cmp %rsi,%rax 4011cb: 74 05 je 4011d2 <phase_6+0xde> #exit the loop 4011cd: 48 89 d1 mov %rdx,%rcx 4011d0: eb eb jmp 4011bd <phase_6+0xc9>
rsi被赋成rsp+80,不难看出这标记着链表结尾
rbx从rsp+32开始,rax从rsp+40开始,rcx从rsp+32开始
每次循环都将rdx赋成rax所指向的值,然后将rcx+8所指的地址存成rdx,然后rax加8,直到rax等于rsi退出
这个循环的作用很简单,在4011c0处可以看出,这个循环让新排好的node序列中每个node的指针域指向新链表中的下一个node(因为我们可能打乱了原先链表的顺序,需要重连)
4011d2: 48 c7 42 08 00 00 00 movq $0x0,0x8(%rdx) 4011d9: 00 4011da: bd 05 00 00 00 mov $0x5,%ebp 4011df: 48 8b 43 08 mov 0x8(%rbx),%rax # the start of a for loop 4011e3: 8b 00 mov (%rax),%eax 4011e5: 39 03 cmp %eax,(%rbx) 4011e7: 7d 05 jge 4011ee <phase_6+0xfa> 4011e9: e8 4c 02 00 00 callq 40143a <explode_bomb> 4011ee: 48 8b 5b 08 mov 0x8(%rbx),%rbx 4011f2: 83 ed 01 sub $0x1,%ebp 4011f5: 75 e8 jne 4011df <phase_6+0xeb> # the end of a for loop 4011f7: 48 83 c4 50 add $0x50,%rsp 4011fb: 5b pop %rbx 4011fc: 5d pop %rbp 4011fd: 41 5c pop %r12 4011ff: 41 5d pop %r13 401201: 41 5e pop %r14 401203: c3 retq最后一段代码一开始将rdx+8的地方存上0,这也是在完成上个循环的工作:最后一个节点的指针域为NULL
4011da将ebp赋成5,然后循环开始:
rax赋成rbx+8所指的值,也就是下一个节点的地址(rbx在上一个循环中等于rsp+32,第一个节点的地址)
然后rax等于其自身所指的值,也就是节点所存整型数的数值
比较rbx的节点整型值和rax,在4011e7可以看出,前一个节点的整型数值必须更大,否则触雷
然后rbx加上12变成下一个节点的地址,ebp减去1,回到循环开头
这个循环告诉我们,新的链表中每个节点的值都要大于下一个的。
回到0x6032d0开始的那一片链表,比较一下那些数的大小不难发现满足条件的重排链表是: node3 node4 node5 node6 node1 node2
考虑到num变成了7-num,我们一开始的输入就应该是:4 3 2 1 6 5
这样就通过了phase 6