<Conclusions from analyzing __isoc_sscanf and read_six_numbers>
If we recall the conclusions we got from analyzing read_six_numbers in Phase_2, they are as follows.
- The string passed in %rsi determines what format __isoc99_sscanf reads the input in. In this case "%d %d %d %d %d %d" is passed, so we can tell it reads 6 integers.
- As __isoc99_sscanf runs, the string we entered is passed in %rdi, and through the sscanf function it is stored at %rsp as an integer array.
- In read_six_numbers, if the integer array has 5 or fewer elements, the bomb explodes.
- read_six_numbers returns the number of integers entered. More precisely, read_six_numbers doesn't store anything in %rax, so it's the __isoc99_sscanf function that returns the number of integers entered in %rax.
Phase_6
Dump of assembler code for function phase_6: 0x0000555555401510 <+0>: push %r14 0x0000555555401512 <+2>: push %r13 0x0000555555401514 <+4>: push %r12 0x0000555555401516 <+6>: push %rbp 0x0000555555401517 <+7>: push %rbx 0x0000555555401518 <+8>: sub $0x60,%rsp 0x000055555540151c <+12>: mov %fs:0x28,%rax 0x0000555555401525 <+21>: mov %rax,0x58(%rsp) 0x000055555540152a <+26>: xor %eax,%eax 0x000055555540152c <+28>: mov %rsp,%r13 0x000055555540152f <+31>: mov %r13,%rsi 0x0000555555401532 <+34>: callq 0x555555401acc <read_six_numbers> 0x0000555555401537 <+39>: mov %r13,%r12 0x000055555540153a <+42>: mov $0x0,%r14d 0x0000555555401540 <+48>: jmp 0x555555401567 <phase_6+87> 0x0000555555401542 <+50>: callq 0x555555401a90 <explode_bomb> 0x0000555555401547 <+55>: jmp 0x555555401576 <phase_6+102> 0x0000555555401549 <+57>: add $0x1,%ebx 0x000055555540154c <+60>: cmp $0x5,%ebx 0x000055555540154f <+63>: jg 0x555555401563 <phase_6+83> 0x0000555555401551 <+65>: movslq %ebx,%rax 0x0000555555401554 <+68>: mov (%rsp,%rax,4),%eax 0x0000555555401557 <+71>: cmp %eax,0x0(%rbp) 0x000055555540155a <+74>: jne 0x555555401549 <phase_6+57> 0x000055555540155c <+76>: callq 0x555555401a90 <explode_bomb> 0x0000555555401561 <+81>: jmp 0x555555401549 <phase_6+57> 0x0000555555401563 <+83>: add $0x4,%r13 0x0000555555401567 <+87>: mov %r13,%rbp 0x000055555540156a <+90>: mov 0x0(%r13),%eax 0x000055555540156e <+94>: sub $0x1,%eax 0x0000555555401571 <+97>: cmp $0x5,%eax 0x0000555555401574 <+100>: ja 0x555555401542 <phase_6+50> 0x0000555555401576 <+102>: add $0x1,%r14d 0x000055555540157a <+106>: cmp $0x6,%r14d 0x000055555540157e <+110>: je 0x555555401585 <phase_6+117> 0x0000555555401580 <+112>: mov %r14d,%ebx 0x0000555555401583 <+115>: jmp 0x555555401551 <phase_6+65> 0x0000555555401585 <+117>: lea 0x18(%r12),%rcx 0x000055555540158a <+122>: mov $0x7,%edx 0x000055555540158f <+127>: mov %edx,%eax 0x0000555555401591 <+129>: sub (%r12),%eax 0x0000555555401595 <+133>: mov %eax,(%r12) 0x0000555555401599 <+137>: add $0x4,%r12 0x000055555540159d <+141>: cmp %r12,%rcx 0x00005555554015a0 <+144>: jne 0x55555540158f <phase_6+127> 0x00005555554015a2 <+146>: mov $0x0,%esi 0x00005555554015a7 <+151>: jmp 0x5555554015c3 <phase_6+179> 0x00005555554015a9 <+153>: mov 0x8(%rdx),%rdx 0x00005555554015ad <+157>: add $0x1,%eax 0x00005555554015b0 <+160>: cmp %ecx,%eax 0x00005555554015b2 <+162>: jne 0x5555554015a9 <phase_6+153> 0x00005555554015b4 <+164>: mov %rdx,0x20(%rsp,%rsi,8) 0x00005555554015b9 <+169>: add $0x1,%rsi 0x00005555554015bd <+173>: cmp $0x6,%rsi 0x00005555554015c1 <+177>: je 0x5555554015d9 <phase_6+201> 0x00005555554015c3 <+179>: mov (%rsp,%rsi,4),%ecx 0x00005555554015c6 <+182>: mov $0x1,%eax 0x00005555554015cb <+187>: lea 0x202c5e(%rip),%rdx # 0x555555604230 <node1> 0x00005555554015d2 <+194>: cmp $0x1,%ecx 0x00005555554015d5 <+197>: jg 0x5555554015a9 <phase_6+153> 0x00005555554015d7 <+199>: jmp 0x5555554015b4 <phase_6+164> 0x00005555554015d9 <+201>: mov 0x20(%rsp),%rbx 0x00005555554015de <+206>: mov 0x28(%rsp),%rax 0x00005555554015e3 <+211>: mov %rax,0x8(%rbx) 0x00005555554015e7 <+215>: mov 0x30(%rsp),%rdx 0x00005555554015ec <+220>: mov %rdx,0x8(%rax) 0x00005555554015f0 <+224>: mov 0x38(%rsp),%rax 0x00005555554015f5 <+229>: mov %rax,0x8(%rdx) 0x00005555554015f9 <+233>: mov 0x40(%rsp),%rdx 0x00005555554015fe <+238>: mov %rdx,0x8(%rax) 0x0000555555401602 <+242>: mov 0x48(%rsp),%rax 0x0000555555401607 <+247>: mov %rax,0x8(%rdx) 0x000055555540160b <+251>: movq $0x0,0x8(%rax) 0x0000555555401613 <+259>: mov $0x5,%ebp 0x0000555555401618 <+264>: jmp 0x555555401623 <phase_6+275> 0x000055555540161a <+266>: mov 0x8(%rbx),%rbx 0x000055555540161e <+270>: sub $0x1,%ebp 0x0000555555401621 <+273>: je 0x555555401634 <phase_6+292> 0x0000555555401623 <+275>: mov 0x8(%rbx),%rax 0x0000555555401627 <+279>: mov (%rax),%eax 0x0000555555401629 <+281>: cmp %eax,(%rbx) 0x000055555540162b <+283>: jge 0x55555540161a <phase_6+266> 0x000055555540162d <+285>: callq 0x555555401a90 <explode_bomb> 0x0000555555401632 <+290>: jmp 0x55555540161a <phase_6+266> 0x0000555555401634 <+292>: mov 0x58(%rsp),%rax 0x0000555555401639 <+297>: xor %fs:0x28,%rax 0x0000555555401642 <+306>: jne 0x555555401651 <phase_6+321> 0x0000555555401644 <+308>: add $0x60,%rsp 0x0000555555401648 <+312>: pop %rbx 0x0000555555401649 <+313>: pop %rbp 0x000055555540164a <+314>: pop %r12 0x000055555540164c <+316>: pop %r13 0x000055555540164e <+318>: pop %r14 0x0000555555401650 <+320>: retq 0x0000555555401651 <+321>: callq 0x555555400f20 <__stack_chk_fail@plt>
<+28 ~ 48>
0x000055555540152c <+28>: mov %rsp,%r13 0x000055555540152f <+31>: mov %r13,%rsi 0x0000555555401532 <+34>: callq 0x555555401acc <read_six_numbers> 0x0000555555401537 <+39>: mov %r13,%r12 0x000055555540153a <+42>: mov $0x0,%r14d 0x0000555555401540 <+48>: jmp 0x555555401567 <phase_6+87>
<+28> : %rsp is a pointer to the array of six integers we entered. This is also stored in %r13.
<+31> : It is stored in %rsi too, but from testing I confirmed that the value stored in %rsi is already gone by the time read_six_numbers returns.
<+34> : It is also stored in %r12.
<+42> : Stores 0 in %r14d.
<+48> : Jumps to <+87>.
<+87 ~ 100>
: Checks whether the number %r13 and %rbp point to is between 1 and 6
0x0000555555401567 <+87>: mov %r13,%rbp 0x000055555540156a <+90>: mov 0x0(%r13),%eax 0x000055555540156e <+94>: sub $0x1,%eax 0x0000555555401571 <+97>: cmp $0x5,%eax 0x0000555555401574 <+100>: ja 0x555555401542 <phase_6+50>
<+87> : Passes the pointer to %rbp as well.
<+90> : Copies the first integer we entered into %eax.
<+94> : Subtracts 1 from %eax.
<+97 ~ 100> : Compares it with 5, and if it's greater than 5 or less than 0, jumps to <+50>. <+50> is the bomb, so the first integer we enter must be between 1 and 6.
0x0000555555401542 <+50>: callq 0x555555401a90 <explode_bomb>
<+102 ~ 115>
: %r14d is the current index of the Outer Loop (same as the index %r13 and %rbp point to)
0x0000555555401576 <+102>: add $0x1,%r14d 0x000055555540157a <+106>: cmp $0x6,%r14d 0x000055555540157e <+110>: je 0x555555401585 <phase_6+117> 0x0000555555401580 <+112>: mov %r14d,%ebx 0x0000555555401583 <+115>: jmp 0x555555401551 <phase_6+65>
<+102> : Adds 1 to %r14d.
<+106> : Compares %r14d with 6.
<+110> : If it equals 6, jumps to <+117>. Here it doesn't jump and moves on.
<+112> : Copies the value of %r14d into %ebx.
<+115> : Jumps to <+65>.
<+65 ~ 76>
:Checks whether the number %rbp points to(the current element of the Outer Loop)and %eax (the current element of the Inner Loop) are different.
0x0000555555401551 <+65>: movslq %ebx,%rax 0x0000555555401554 <+68>: mov (%rsp,%rax,4),%eax 0x0000555555401557 <+71>: cmp %eax,0x0(%rbp) 0x000055555540155a <+74>: jne 0x555555401549 <phase_6+57> 0x000055555540155c <+76>: callq 0x555555401a90 <explode_bomb>
<+65> : Copies the value of %ebx into %rax.
<+68> : Stores in %eax the value of the element reached by moving from %rsp by the currently stored index.
<+71> : Compares %eax with the value %rbp points to.
<+74> : The bomb explodes at <+76>, so %eax and the value %rbp points to must be different.
<+57 ~ 71>
: %ebx is the index of the Inner Loop
0x0000555555401549 <+57>: add $0x1,%ebx 0x000055555540154c <+60>: cmp $0x5,%ebx 0x000055555540154f <+63>: jg 0x555555401563 <phase_6+83> 0x0000555555401551 <+65>: movslq %ebx,%rax 0x0000555555401554 <+68>: mov (%rsp,%rax,4),%eax 0x0000555555401557 <+71>: cmp %eax,0x0(%rbp) 0x000055555540155a <+74>: jne 0x555555401549 <phase_6+57> 0x000055555540155c <+76>: callq 0x555555401a90 <explode_bomb>
<+57> : Adds 1 to %ebx.
<+60 ~ 63> : If %ebx has become 6, jumps to <+83>.
After running <+65 ~ 71>, it repeats until %ebx becomes 6.
<Interim conclusion 1>
It's a nested Loop structure.
<+87 ~ 115> is the Outer Loop. Here %rbp and %r13 go through 1 to 6. (They move one slot to the right at <+83>) And %r14d holds that index.
While going through the Outer Loop, for each element it goes through the Inner Loop, <+57 ~ 71>.
Here, if the Outer Loop's number and the Inner Loop's number are the same, the bomb explodes.
Once all the checks are done, at <+110> it checks whether the current index is 6, and since the loop is finished it moves to <+117> to go through the next steps.
In other words, every number must be between 1 and 6, and the numbers must all be different.
At the very last moment, it will look like this.
The conditions are satisfied, so we should go to <+117>.
<+117 ~ 144, +146 ~ 151>
0x0000555555401585 <+117>: lea 0x18(%r12),%rcx 0x000055555540158a <+122>: mov $0x7,%edx 0x000055555540158f <+127>: mov %edx,%eax 0x0000555555401591 <+129>: sub (%r12),%eax 0x0000555555401595 <+133>: mov %eax,(%r12) 0x0000555555401599 <+137>: add $0x4,%r12 0x000055555540159d <+141>: cmp %r12,%rcx 0x00005555554015a0 <+144>: jne 0x55555540158f <phase_6+127>
<+117> : Makes %rcx hold the end address of the last element of the array. (The number right after the last one is 0)
<+122 ~ 127> : Copies 7 into %eax and %edx.
<+129 ~ 133> : If we call the value %r12 points to a, it makes it hold 7-a.
<+141 ~ 144> : If it hasn't reached the end address of the elements, repeats <+117 ~ 144>.
In the end, it stores every number in the array we entered as 7 minus that number.
<+146 ~ 151> : After finishing the loop and entering <+146>, it stores 0 in %esi and jumps to <+179>.
The current situation is as below.
<+179 ~ 197>
<+179>: mov (%rsp,%rsi,4),%ecx <+182>: mov $0x1,%eax <+187>: lea 0x202c5e(%rip),%rdx # 0x555555604230 <node1> <+194>: cmp $0x1,%ecx <+197>: jg 0x5555554015a9 <phase_6+153> <+199>: jmp 0x5555554015b4 <phase_6+164>
<+179> : %ecx becomes the R[%rsi]-th number. Right now it stores 6, the number at index 0.
<+182> : Stores 1 in %eax.
<+187> : For now, let's just think of it as %rdx getting the address value 0x555555604230 and move on.
<+194 ~ 197> : Compares R[%ecx] with 1, and if it's greater than 1 goes to <+153>, and if it's 1 goes to <+164>.
<+153 ~ 162>
: %rdx comes to hold the target pointed to by the value at index (R[%ecx] - 1) of the node array.
0x00005555554015a9 <+153>: mov 0x8(%rdx),%rdx 0x00005555554015ad <+157>: add $0x1,%eax 0x00005555554015b0 <+160>: cmp %ecx,%eax 0x00005555554015b2 <+162>: jne 0x5555554015a9 <phase_6+153>
(gdb) x/20xg 0x555555604230 0x555555604230 <node1>: 0x00000001000003aa 0x0000555555604240 0x555555604240 <node2>: 0x0000000200000206 0x0000555555604250 0x555555604250 <node3>: 0x0000000300000076 0x0000555555604260 0x555555604260 <node4>: 0x000000040000039c 0x0000555555604270 0x555555604270 <node5>: 0x0000000500000277 0x0000555555604110 0x555555604280 <host_table>: 0x0000555555402e47 0x0000555555402e61 0x555555604290 <host_table+16>: 0x0000555555402e7b 0x0000555555402e94 0x5555556042a0 <host_table+32>: 0x0000555555402eae 0x0000555555402ebc 0x5555556042b0 <host_table+48>: 0x0000555555402ecb 0x0000000000000000 0x5555556042c0 <host_table+64>: 0x0000000000000000 0x0000000000000000
<+153> : It copies by moving %rdx's reference 8 bytes at a time, so to make it easier to see I looked at it as an 8-byte array. And it stores the reference of the value one slot over from %rdx in the array. From now on I'll call that array the node array.
Moving once in the node array : M[0x555555604230 + 0x8] is stored. That is, 0x555555604240 is stored.
0x555555604240 <node2>: 0x0000000200000206 0x0000555555604250
Also, they're holding each other's address values right now, and if you look closely, the node array has the following structure.
&node a is the address value of node a.
<+157> : Adds 1 to %eax.
<+160 ~ 162> : %ecx is the R[%rsi]-th number. It compares this with %eax and repeats <+153 ~ 162> until they're equal.
%rsi is fixed at 0. That is, %ecx is the 0th number.
Also, since %eax repeats from 1 until it becomes %ecx, we can think of it as repeating %ecx times.
Going one step further, it makes %rdx move %ecx times in the node array.
For example, if it moves 5 times from node1, %rdx holds the address of node6 as its value.
The final state is as follows.
<+164 ~ 177>
: Moving in 8-byte units,stores the value %rdx points to at the spot 0x20 away from where the array is stored.
0x00005555554015b4 <+164>: mov %rdx,0x20(%rsp,%rsi,8) 0x00005555554015b9 <+169>: add $0x1,%rsi 0x00005555554015bd <+173>: cmp $0x6,%rsi 0x00005555554015c1 <+177>: je 0x5555554015d9 <phase_6+201>
<+164> : Moving in 8-byte units, it stores the value %rdx points to in the node array at the spot 0x20 away from where the array we entered is stored.
<+169 ~ 177> : If %rsi has become 6, jumps to <+201>, otherwise continues from <+179>.
<Interim conclusion 2>
This is also anested Loop structure.
<+179 ~ 197>is theOuter Loop, <+153 ~ 177>is theInner Loop.
If R[%ecx] is 1, there's no need to move where %rdx points, so it just doesn't run <+153 ~ 162>,
and in the end, it stores the value at index (R[%ecx] - 1) that %rdx points to, to the right of the array we stored.
The index R[%rsi] points to is the index of the Outer Loop currently running.
%ecx copies the value it gets by moving as many times as the R[%rsi]-th number, moving 8 bytes at a time starting from 0x20 + R[%rsp].
So in our case, where we entered 1 2 3 4 5 6, the array holds 6 5 4 3 2 1( = 7-6, 7-5, 7-4, 7-3, 7-2, 7-1),
and at the addresses to its right, the values of node 6, node 5, node 4, node 3, node 2, node 1 of the node array that %rdx points to are stored in order.
In a picture, it looks like this.
(The array addresses are just for readability, not the actual addresses)
So when R[%rsi] becomes 6 and even the Outer Loop finishes,
the code continues from <+201>.
<+201 ~ 206>
0x00005555554015d9 <+201>: mov 0x20(%rsp),%rbx 0x00005555554015de <+206>: mov 0x28(%rsp),%rax 0x00005555554015e3 <+211>: mov %rax,0x8(%rbx) 0x00005555554015e7 <+215>: mov 0x30(%rsp),%rdx 0x00005555554015ec <+220>: mov %rdx,0x8(%rax) 0x00005555554015f0 <+224>: mov 0x38(%rsp),%rax 0x00005555554015f5 <+229>: mov %rax,0x8(%rdx) 0x00005555554015f9 <+233>: mov 0x40(%rsp),%rdx 0x00005555554015fe <+238>: mov %rdx,0x8(%rax) 0x0000555555401602 <+242>: mov 0x48(%rsp),%rax 0x0000555555401607 <+247>: mov %rax,0x8(%rdx) 0x000055555540160b <+251>: movq $0x0,0x8(%rax) 0x0000555555401613 <+259>: mov $0x5,%ebp 0x0000555555401618 <+264>: jmp 0x555555401623 <phase_6+275>
In the end, it's code that takes the nodes that were originally linked like on the right
and rearranges them in the order stored at 0x20(%rsp) above.
From here on, let's assume we entered 6 3 1 2 5 4 and continue.
The numbers 6 3 1 2 5 4 we entered get converted into 1 4 6 5 2 3, and the addresses of node1, node4, node6, node5, node2, node3 are placed at 0x20(%rsp).
And after running <+201 ~ 206>, the relationships between the nodes change as shown on the right.
Once the change is done, it jumps to <+275>.
<+266 ~ 285>
0x000055555540161a <+266>: mov 0x8(%rbx),%rbx 0x000055555540161e <+270>: sub $0x1,%ebp 0x0000555555401621 <+273>: je 0x555555401634 <phase_6+292> 0x0000555555401623 <+275>: mov 0x8(%rbx),%rax 0x0000555555401627 <+279>: mov (%rax),%eax 0x0000555555401629 <+281>: cmp %eax,(%rbx) 0x000055555540162b <+283>: jge 0x55555540161a <phase_6+266> 0x000055555540162d <+285>: callq 0x555555401a90 <explode_bomb>
<+275> : %rax holds the address of the node after %rbx. Right now %rbx is the address of the first node, so %rax is the address of the second node.
That is, R[%rbx] is &node1 and R[%rax] is &node4.
<+279> : %eax is the second node, but it only takes the first 8 bytes, so it stores v4.
<+281 ~ 283> : Compares v4, the value of the second node, with v1, the value of the first node. And v1 >= v4 must hold. Then it jumps to <+266>, otherwise the bomb explodes.
<+266> : Moves %rbx to the next node.
<+270 ~ 273> : Decreases %ebp by 1. If %ebp is less than 0, it moves to <+292>.
This repeats, and since %ebp goes from 5 down to 1, it repeats 5 times in total. And as %rbx moves to the next node, %eax becomes the node after %rbx. Also, each time, the v value of the node in front must be greater than or equal to the v value of the node behind it.
In other words, they must be in descending order by v value.
<Conclusion>
Listing the v value of each node gives the following.
(gdb) x/30dw 0x555555604230 0x555555604230 <node1>: 938 1 1432371776 21845 0x555555604240 <node2>: 518 2 1432371792 21845 0x555555604250 <node3>: 118 3 1432371808 21845 0x555555604260 <node4>: 924 4 1432371824 21845 0x555555604270 <node5>: 631 5 1432371472 21845 (gdb) x/1dw 0x0000555555604110 0x555555604110 <node6>: 891
| node | v |
|---|---|
| 1 | 938 |
| 2 | 518 |
| 3 | 118 |
| 4 | 924 |
| 5 | 631 |
| 6 | 891 |
Listing the nodes from largest
1 → 4 → 6 → 5 →2 →3
is the order.
And since these nodes are 7 minus the numbers we entered,
6 3 1 2 5 4
is what they convert to.
So the answer is as follows.
6 3 1 2 5 4