iyeaaa

SEQ 방식의 명령 수행

기존의 SEQ는 한 클럭 주기당 하나의 명령어만을 수행합니다.

(a)의 하드웨어에서 하나의 명령어를 수행한다면

Combinational logic에서 300ps(s/조)가 소요되고

clock에 의해 register에 값을 쓰는데에 20ps가 소요되어 결과적으로 320ps가 소요됩니다.

(a)의 하드웨어로 I1, I2, I3를 수행한다면

I1 I2 I3, 3개의 명령어를 수행하므로 320 * 3 = 960ps가 소요됩니다.

SEQ 성능 측정

성능측정을 위한 두 가지 개념이 있습니다.

Latency of SEQ

하나의 명령어가 수행되는 시간으로 Latency(지연시간)을 표현합니다.

즉, 위 SEQ의 Latency는 320ps입니다.

Throughput of SEQ

1초당 수행되는 명령어의 개수로 Throughtput(처리량)을 표현합니다.

위의 SEQ는 320ps당 1개의 Instruction이 수행되므로, 1s당 31억 2천만개의 Instruction이 처리됩니다.

너무 길기때문에, 십억개의 Instructions 묶음으로 나타내기로 약속한 GIPS를 통해 처리량을 표현하면, 3.12 GIPS가 됩니다.

즉, 위 SEQ의 Throghput은 3.12 GIPS 입니다.

왜 Pipelining?

SEQ의 작업 순서가 변경되지 않으면서, 여러개의 명령어를 동시에 수행할 수 있다면 더 빠른속도를 산출할 수 있을겁니다.

하나의 Instruction은 여러개의 Stage(Fetch, Decode, Execute, Memory, Writeback, PC update)로 나눌 수 있는데,

Instruction을 적절한 개수로 나눠 여러개의 명령어의 완료순서를 바꾸지 않고 동시에 수행할 수 있습니다.

위 처럼 하드웨어를 구성했다고 합시다.

A에서 계산하고, 클럭이 rise되어 첫번째 레지스터에 작성되고

B에서 계산하고, 클럭이 rise되어 두번째 레지스터에 작성되고

C에서 계산하고, 클럭이 rise되어 세번째 레지스터에 작성되고

를 반복합니다.

Pipeline으로 각 구간이 위와같이 수행된다고 합시다.

예를들어, A에서 Fetch를 완료한 후 Decode단계에서 B가 Fetch를 진행하는 방식으로 동시에 여러개의 명령어를 수행하는겁니다.

각 구간마다 넘버링하여 하드웨어 상태를 살펴보면 다음과 같습니다.

Pipelining 성능 측정

SEQ의 처리량, 지연시간과 측정 방식이 완전히 동일합니다.

다만 처리량을 구하는 방법에서 약간 생각할 부분이 있습니다.

Latency of Pipelining

하나의 명령어의 수행이 완료되려면 stage A, B, C를 거쳐야합니다.

한 clock의 cycle당 하나의 stage를 완료하므로, clock의 cycle인 120ps에 3을 곱하면 360ps입니다.

즉, 위 Pipelining의 Latency는 360ps 입니다.

Throughput of Pipelining

위는 단지 3개의 명령어만 수행하지만, 처리량은 1초동안 명령어가 반복적으로 수행한다고 가정해서 구하므로,

명령어 I1 I2 I3 I1 I2 I3 I1... 를 반복적으로 수행해야한다고 가정하겠습니다.

1초에 수행되는 명령어의 개수를 구해야하는데

1초에 굉장히 많은 명령어가 수행되므로 양 Side 부분은 무시하고 값을 구해도 실제로 수행되는 명령어 수와 크게 다르지 않을겁니다.

즉 처리량 계산을 위해 side 부분을 제거해서 0ps부터 600ps 까지의 부분만 보았을 때 위와 같은 형태로 명령어들이 수행됩니다.

이제 처리량 계산을 위해 다음을 생각해봅시다.

N개의 부분으로 나뉘어진 하드웨어는 N개의 stage를 동시에 수행할겁니다. (예시에서 N = 3)

또한, 한개의 명령어를 수행하려면 stage A, B, C를 거쳐야하고 한 주기동안에도 stage A, B, C가 모두 수행되고 있습니다.

즉 Clock의 한 주기동안 stage A, B, C가 모두 수행되므로 한개의 Instruction이 수행된다고 생각하면,

1초를 한 주기단위로 나눈 개수(위에서는 1s / 120ps)는 1초동안 수행되는 Instruction 수와 동일합니다.

실제로는 한 주기 동안 I1의 stage 한개, I2의 stage 한개, I3의 stage 한개가 수행되지만

결과적으로 1초에 수행되는 명령어수와 거의 동일하다는 얘기입니다.

위의 사실들을 바탕으로 계산해보면,

한개의 Instruction이 120ps 동안 실행된다고 생각했을 때

1 Instruction : 120ps = 8333333333.33 Instruction : 1s 의 비율을 가집니다.

1초에 약 83.333억개를 수행하므로, 이를 10억단위로 묶는 GIPS로 나타내면 약 8.33333 GIPS가 됩니다.

즉, 위 Pipelining의 Throughput은 약 8.33 GIPS입니다.

SEQ vs Pipelining 성능비교

Latency : Pipelining의 지연시간이 SEQ의 지연시간보다 약 1.12(360 / 320)배 더 깁니다.

Throughput : Pipelining의 처리량이 SEQ의 지연시간보다 약 2.67(8.33 / 3.12)배 더 깁니다.

Pipelining이 SEQ에 비해 1.12배라는 약간의 명령어 처리시간이 늘어났지만 2.67배라는 처리량을 얻었으므로

더 좋은 성능을 얻었다고 정리할 수 있습니다.

Unsigned

부호가 없는 양수인 2진수를 10진수로 바꾸는 공식은 다음과 같습니다.

충분히 이해할만합니다.

Signed

부호가 존재하는 2진수에 대해서는 다음 공식을 적용해야합니다.

적당한 증명

왜 이런공식이 나오는지 생각해보자면

아래 w가 3인 binary수를 unsigned와 signed를 매칭시켰습니다.

Unsigned

000 에서 100이 될 때 앞자리에 1이 생기면서 4가 더해집니다.

001 에서 101이 될 때 앞자리에 1이 생기면서 4가 더해집니다.

즉, 어찌보면 당연하지만 앞자리는 4를 단지 더해주는 역할을 합니다.

Signed

000 에서 100이 될 때 앞자리에 1이 생기면서 -4가 더해집니다.
001 에서 101이 될 때 앞자리에 1이 생기면서 -4가 더해집니다.

즉, 앞자리는 4를 빼주는 역할을 합니다.

때문에 위의 공식에서 맨 앞자리에 마이너스를 곱해서 더합니다.

Unsigned와 Signed의 관계성

위 공식을 이용해서 B2U에서 B2T를 빼보면, 저 수식이 생길겁니다.

만약, 맨 앞자리 비트가 1이라고 가정하면

다시말해서, Unsigned에서는 양수이고 Signed에서는 음수인 숫자로 한정했을 때,

B2U - B2T = 2^w가 됩니다.

이 관계성은 Signed 타입의 숫자에서 Unsigned 타입의 숫자로 변환하거나 그 반대로 변환할 때 유용합니다.

<__isoc_sscanf, read_six_numbers 분석 결론>

Phase_2에서 read_six_numbers에 대해 분석해 얻은 결론을 떠올리면 다음과 같습니다.

1. %rsi에서 전달한 문자열을 통해 __isoc99_sscanf에서 어떤 형식으로 입력을 받을지 결정할 수 있습니다. 지금 경우에는 "%d %d %d %d %d %d" 가 전달되었으므로 6개의 정수를 읽는다고 판단할 수 있습니다.
2. 입력한 문자열이 __isoc99_sscanf 를 진행하면서 %rdi에서 전달되어 sscanf 함수를 통해 정수 배열형태로 %rsp에 저장됩니다.
3. read_six_numbers에서 정수 배열 개수가 5개 이하라면 폭탄을 터뜨립니다.
4. read_six_numbers는 반환값으로 입력한 정수의 개수를 반환한다. 더 자세히 말하면 read_six_numbers는가 %rax에 저장하지 않으므로,  __isoc99_sscanf 함수가 %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는 입력한 여섯개의 정수 배열을 가리키는 포인터입니다. 이를 %r13에도 저장합니다.

<+31> : %rsi에도 이를 저장하지만, 테스트 결과 %rsi에 저장된 값을 read_six_numbers가 리턴되었을 때에는 이미 소멸됨을 확인했습니다.

<+34> : %r12에도 저장합니다.

<+42> : %r14d에 0을 저장합니다.

<+48> : <+87>로 점프합니다.

<+87 ~ 100> 

: %r13, %rbp가 가리키는 숫자가 1 이상 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> : %rbp에도 포인터를 넘겨줍니다.

<+90> : 입력한 첫번째 정수를 %eax에 복사합니다.

<+94> : %eax에서 1을 뺍니다.

<+97 ~ 100> : 5와 비교해서 5보다 크거나 0보다 작으면 <+50>으로 점프합니다. <+50>은 폭탄이므로 입력하는 첫번째 정수는 1 이상 6이하여야 합니다.

   0x0000555555401542 <+50>:	callq  0x555555401a90 <explode_bomb>

<+102 ~ 115>

: %r14d는 Outer Loop의 현재 인덱스(%r13과, %rbp가 가리키는 인덱스와 같음)

   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> : %r14d에 1을 더합니다.

<+106> : %r14d를 6과 비교합니다.

<+110> : 6과 같으면 <+117>로 점프합니다. 여기서는 점프하지 않고 넘어갑니다.

<+112> : %r14d의 값을 %ebx에 복사합니다.

<+115> : <+65>로 점프합니다.

<+65 ~ 76>

: %rbp가 가리키는 숫자(Outer Loop의 현재 원소)와 %eax(Inner Loop의 현재 원소)가 다른지 검사.

   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> : %rax에 %ebx값을 복사합니다.

<+68> : %eax에 %rsp에서 현재 저장된 인덱스만큼 이동한 원소의 값을 저장합니다.

<+71> : %eax와 %rbp가 가리키는 값을 비교합니다.

<+74> : <+76>에서 폭탄이 터지므로 %eax와 %rbp가 가리키는 값은 달라야합니다.

<+57 ~ 71>

: %ebx는 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> : %ebx에 1을 더합니다.

<+60 ~ 63> : %ebx에 6이 되었다면 <+83>로 점프합니다.

<+65 ~ 71>을 수행한 후 %ebx가 6이 되기 전까지 반복합니다.

<중간결론1>

2중 Loop 구조입니다.

<+87 ~ 115> 는 Outer Loop입니다. 여기서는 %rbp, %r13을 1부터 6까지 순회합니다.(<+83>에서 오른쪽으로 한칸씩 옮겨감) 그리고 그 인덱스를 %r14d가 소유합니다.

Outer Loop를 순회하면서 각 원소마다 Inner Loop인 <+57 ~ 71>을 순회합니다.

여기서는 Outer Loop의 숫자와 Inner Loop의 숫자가 같으면 폭탄이 터지도록 합니다.

모든 검사가 끝나면 <+110>에서 현재 인덱스가 6인지 검사해서 순회가 끝났으므로 <+117>로 이동해 다음 과정들을 순회하게 됩니다.

즉, 모든 숫자는 1 이상 6 이하여야하고, 그리고 그 숫자들은 모두 달라야합니다.

마지막 순간에는 다음과 같은 형태가 될겁니다.

조건들을 만족했으니 <+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> : %rcx가 배열의 마지막 원소의 끝 주소를 가지게 합니다. (맨 마지막의 다음 숫자는 0입니다)

<+122 ~ 127> : %eax와 %edx에 7을 복사합니다.

<+129 ~ 133> : %r12가 가리키는 값을 a라고 할 때 7-a를 가지도록합니다.

<+141 ~ 144> : 만약 원소의 끝 주소에 도달하지 않았다면 <+117 ~ 144>를 반복합니다.

결론적으로, 입력한 배열의 숫자를 모두 7에서 뺀 값으로 저장하게합니다.

<+146 ~ 151> : 순회를 마치고, <+146>으로 진입한 후에 %esi에 0을 저장하고 <+179>로 점프합니다.

현재 상황은 밑과 같습니다.

<+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는 R[%rsi]번째 숫자가 됩니다. 지금은 0번째 인덱스 숫자인 6을 저장합니다.

<+182> : %eax에 1을 저장합니다.

<+187> : 우선은 %rdx가 0x555555604230 주소값이 저장된다고 까지만 생각하고 넘어가겠습니다.

<+194 ~ 197> : R[%ecx]와 1을 비교해서 1 초과라면 <+153>로 넘어가고, 1 이면 <+164>로 넘어갑니다.

<+153 ~ 162>

: %rdx가 node 배열의 인덱스 (R[%ecx] - 1)의 값이 가리키는 대상을 가지게 된다.

   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> : %rdx의 참조를 8바이트 씩 이동해서 복사하므로 보기편하도록 8바이트 배열 관점에서 관찰했습니다. 그리고 %rdx를 배열에서 한칸 옮긴 값의 참조를 저장합니다. 또한 앞으로 저 배열을 node 배열이라고 하겠습니다.

node 배열에서 한번 이동 : M[0x555555604230 + 0x8] 이 저장된다. 즉 0x555555604240가 저장된다.

0x555555604240 <node2>:	0x0000000200000206	0x0000555555604250

또한, 지금 서로의 주소값을 지니고 있는데 잘 관찰해보면 node배열은 다음과 같은 구조를 가집니다.

&node a는 노드 a의 주소값입니다.

<+157> : %eax에 1을 더합니다.

<+160 ~ 162> : %ecx는 R[%rsi]번째 숫자입니다. 이를 %eax와 비교해서 같을때까지 <+153 ~ 162>를 반복합니다.

%rsi는 0으로 고정입니다. 즉 %ecx는 0번째 숫자입니다.

또한 %eax가 1부터 %ecx가 될때까지 반복하므로, %ecx번 반복한다고 생각할 수 있고.

한번 더 나아가서, %rdx를 node 배열에서 %ecx번 이동를 반복하게 합니다.

예를들어, node1에서 5번 이동하면 %rdx는 node6 주소를 값으로 가집니다.

마지막의 상태는 다음과 같습니다.

<+164 ~ 177>

: 8바이트 단위로 옮겨서 배열이 저장되는 위치에서 0x20 떨어진곳에  %rdx가 가리키는값 저장.

   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> : 우리가 입력한 배열이 저장되는 위치에서 0x20 떨어진곳에 8바이트 단위로 옮겨서 %rdx가 node 배열에 가리키는 값을 저장합니다.

<+169 ~ 177> : %rsi가 6이 되었다면 <+201>로 점프하고, 아니라면 <+179>에서 진행합니다.

<중간결론2>

이번에도 2중 Loop 구조입니다.

<+179 ~ 197>가 Outer Loop, <+153 ~ 177> 가 Inner Loop 입니다.

R[%ecx]가 1이면 %rdx가 가리키는 위치를 옮길 필요가 없기때문에 <+153 ~ 162>를 진행하지 않는것 뿐이고,

결론적으로 %rdx가 가리키는 index (R[%ecx] - 1) 값을 우리가 저장한 배열 오른쪽에 저장해놓는겁니다.

R[%rsi] 가 가리키는 인덱스가 현재 진행하는 Outer Loop의 index입니다.

%ecx는 R[%rsi]번째 숫자만큼 이동해서 가지는 값을 0x20 + R[%rsp]부터 8바이트씩 옮겨 복사합니다.

즉, 1 2 3 4 5 6을 입력한 우리의 경우 배열에는 6 5 4 3 2 1( = 7-6, 7-5, 7-4, 7-3, 7-2, 7-1)이 저장되었고

그 오른쪽 주소에 %rdx가 가리키는 node배열의 node 6, node 5, node 4, node 3, node 2, node 1 의 값들이 차례대로 저장되는겁니다.

사진을 보면 다음과 같게 됩니다.

(배열의 주소는 보기 편하도록 한것이지, 실제 주소가 아닙니다)

즉, R[%rsi]가 6이 되어 Outer Loop까지 종료되었을때,

<+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>

결론적으로 보면 기존에 오른쪽같이 연결되어있던 노드들을

위에서 0x20(%rsp)에 저장되어 있는 순서대로 재배치하는 코드입니다.

여기서부터는 6 3 1 2 5 4 을 입력했다고 가정하고 진행해보겠습니다.

6 3 1 2 5 4을 입력한 숫자들은 1 4 6 5 2 3 으로 변환되고, 0x20(%rsp)에 node1, node4, node6, node5, node2, node3의 주소가 배치되게 됩니다.

그리고 <+201  ~ 206> 을 진행하고 나면, 노드사이 관계가 오른쪽과 같이 변경됩니다.

변경이 완료되면 <+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는 %rbx의 다음 노드 주소를 가집니다. 현재 %rbx는 첫번째 노드 주소이므로, %rax는 두번째 노드 주소입니다.

즉 R[%rbx]는 &node1, R[%rax]는 &node4 입니다.

<+279> : %eax는 두번째 노드인데, 그 앞의 8바이트만 가져오므로 v4를 저장합니다.

<+281 ~ 283> : 두번째 노드의 값인 v4와 첫번째 노드 값인 v1을 비교합니다. 그리고 v1 >= v4를 만족해야합니다. 그리고 <+266>으로 점프합니다, 아니라면 폭탄이 터집니다.

<+266> : %rbx를 다음 노드로 옮깁니다.

<+270 ~ 273> : %ebp를 1 감소합니다. 만약 %ebp가 0보다 작다면 <+292>로 이동합니다.

이를 반복하는데, 결국 %ebp가 5에서 1까지 반복하므로 총 5번 반복합니다. 그리고 %rbx를 다음 노드로 옮기면서 %eax는 %rbx의 다음 노드가 됩니다. 또한 그때마다 앞에놓인 노드의 v값이 뒤에놓인 노드의 v값보다 크거나 같아야합니다.

즉 v값을 기준으로 내림차순을 만족해야합니다.

<결론>

각 노드의 v값을 나열해보면 다음과 같습니다.

(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

노드가 큰 순서대로 나열하면

1 → 4 → 6 → 5 →2 →3

입니다.

그리고 이 노드들은 7에서 입력한 숫자를 뺀 값이므로,

6 3 1 2 5 4

로 변환됩니다.

즉 답은 다음과 같습니다.

6 3 1 2 5 4

phase_5

Dump of assembler code for function phase_5:
=> 0x00005555554014ca <+0>:	push   %rbx
   0x00005555554014cb <+1>:	mov    %rdi,%rbx
   0x00005555554014ce <+4>:	callq  0x55555540176f <string_length>
   0x00005555554014d3 <+9>:	cmp    $0x6,%eax
   0x00005555554014d6 <+12>:	jne    0x555555401509 <phase_5+63>
   0x00005555554014d8 <+14>:	mov    %rbx,%rax
   0x00005555554014db <+17>:	lea    0x6(%rbx),%rdi
   0x00005555554014df <+21>:	mov    $0x0,%ecx
   0x00005555554014e4 <+26>:	lea    0x1675(%rip),%rsi        # 0x555555402b60 <array.3417>
   0x00005555554014eb <+33>:	movzbl (%rax),%edx
   0x00005555554014ee <+36>:	and    $0xf,%edx
   0x00005555554014f1 <+39>:	add    (%rsi,%rdx,4),%ecx
   0x00005555554014f4 <+42>:	add    $0x1,%rax
   0x00005555554014f8 <+46>:	cmp    %rdi,%rax
   0x00005555554014fb <+49>:	jne    0x5555554014eb <phase_5+33>
   0x00005555554014fd <+51>:	cmp    $0x3a,%ecx
   0x0000555555401500 <+54>:	je     0x555555401507 <phase_5+61>
   0x0000555555401502 <+56>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401507 <+61>:	pop    %rbx
   0x0000555555401508 <+62>:	retq
   0x0000555555401509 <+63>:	callq  0x555555401a90 <explode_bomb>
   0x000055555540150e <+68>:	jmp    0x5555554014d8 <phase_5+14>

<+1 ~ 12>

   0x00005555554014cb <+1>:	mov    %rdi,%rbx
   0x00005555554014ce <+4>:	callq  0x55555540176f <string_length>
   0x00005555554014d3 <+9>:	cmp    $0x6,%eax
   0x00005555554014d6 <+12>:	jne    0x555555401509 <phase_5+63>

<+1> : 전에 분석했듯이 우리가 입력한 것들은 한줄의 문자열로 %rdi에 저장됩니다. 그리고 이를 %rbx에도 저장합니다.

<+4> : string_length도 phase_1에서 분석했었듯이 레지스터 %rdi와 %rdx로 이루어져 그 간격을 %rax에 저장해서 반환하는 함수입니다.

<+9> : 그 반환값을 6과 비교합니다.

<+12> : 반환값, 즉 문자열의 길이가 6이 아니라면 <+63>으로 점프해서 폭탄이 터지므로, 입력하는 문자열의 길이는 6이어야합니다.

   0x0000555555401509 <+63>:	callq  0x555555401a90 <explode_bomb>

<+14 ~ 36>

   0x00005555554014d8 <+14>:	mov    %rbx,%rax
   0x00005555554014db <+17>:	lea    0x6(%rbx),%rdi
   0x00005555554014df <+21>:	mov    $0x0,%ecx
   0x00005555554014e4 <+26>:	lea    0x1675(%rip),%rsi        # 0x555555402b60 <array.3417>
   0x00005555554014eb <+33>:	movzbl (%rax),%edx
   0x00005555554014ee <+36>:	and    $0xf,%edx

<+14> : %rax에 %rbx가 가지고 있는 포인터를 복사합니다.

<+17> : %rdi에 0x6(%rbx), 즉 6번째 문자를 저장합니다.

<+21> : %ecx에 0을 저장합니다.

<+26> : 배열을 저장하는것으로 추측됩니다.

<+33> : (%rax)는 문자열의 첫번째 문자입니다. 이를 %edx에 저장합니다.

<+36> : 첫번째 문자를 15와 &연산합니다. 영어 문자가 대소문자든 숫자문자든 아무상관없이 정수 1부터 26까지 순서대로 대응되도록 해줍니다.

<+39 ~ 68>

   0x00005555554014f1 <+39>:	add    (%rsi,%rdx,4),%ecx
   0x00005555554014f4 <+42>:	add    $0x1,%rax
   0x00005555554014f8 <+46>:	cmp    %rdi,%rax
   0x00005555554014fb <+49>:	jne    0x5555554014eb <phase_5+33>
   0x00005555554014fd <+51>:	cmp    $0x3a,%ecx
   0x0000555555401500 <+54>:	je     0x555555401507 <phase_5+61>
   0x0000555555401502 <+56>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401507 <+61>:	pop    %rbx
   0x0000555555401508 <+62>:	retq
   0x0000555555401509 <+63>:	callq  0x555555401a90 <explode_bomb>
   0x000055555540150e <+68>:	jmp    0x5555554014d8 <phase_5+14>

<+39> : %rsi에 정보를 알기 힘든 배열을 저장했었습니다. 그리고 이 <+39>의 operand에서 %rsi의 배열을 4바이트를 단위로 접근함을 알 수 있습니다. 즉 %rsi는 4바이트 int형 정수배열이 저장되었다는 관점으로 볼 수 있습니다.

(gdb) x/30dw $rsi
0x555555402b60 <array.3417>:	2	10	6	1
0x555555402b70 <array.3417+16>:	12	16	9	3
0x555555402b80 <array.3417+32>:	4	7	14	5
0x555555402b90 <array.3417+48>:	11	8	15	13
0x555555402ba0:	2032168787	1948284271	1802398056	1970239776
0x555555402bb0:	1851876128	1869902624	1752440944	1868701797
0x555555402bc0:	1998611053	543716457	1819440227	539779885
0x555555402bd0:	2032168804	4158831

때문에, 4바이트 단위로 끊어서 메모리에 저장된 값을 출력하면 다음과 같습니다.

30개를 출력해보았더니, 16개까지는 인위적으로 값을 집어넣은듯한 값이 있고 그 이후로는 쓰레기 값이 있기때문에 우선 사용할것같은 16개까지만 적었습니다. 

그리고 이 배열의 입력한 첫번째 문자에서 15와 &연산한 값만큼 한칸씩 이동해서 나온 element를 %ecx에 저장합니다.

저는 "abcdef"를 입력했다고 가정했기 때문에, 첫번째 element인 2를 저장합니다.

<+42> : %rax에 1을 더합니다.

<+46> :  %rax와 %rdi를 비교합니다.

<+49> : %rax와 %rdi가 다르면 <+33>으로 점프합니다.

<+51> : %rax와 %rdi가 같으면 58과 %ecx를 비교합니다.

<+54> : 58이면 <+61>로 점프해서 문제가 해결됩니다.

<결론>

상황을 관찰해보면,

%rax는 배열을 첫번째 요소에서 마지막 요소까지 순회합니다.

순회하면서, 각 입력한 문자가 위의 정수 배열의 인덱스 역할을 하며 인덱스가 가리키는 정수를 %ecx에 누적합니다.

그리고 마지막 요소의 순회까지 끝나면 R[%ecx]가 58이 되어야 합니다.

즉, 우리가 입력해야하는 문자열은 각 문자가 1부터 9로 대응되며 그 합이 58이 되는 문자열이고 답은 너무나도 많습니다.

몇가지 예시만 들어보면,

우선 58을 위의 배열에 있는 숫자 중에서 6개 숫자의 합으로 분리해야하므로,

10 + 10 + 10 + 16 + 9 + 3 으로 분리할 수 있습니다.

각 숫자의 인덱스는 1 1 1 5 6 7 이고, 1 1 1 5 6 7로 대응되는 문자들은 아래를 포함하여 너무나 많은 조합이 가능합니다.

aaaefg, 111567, AAAEFG, a1156G

세 가지 함수를 분석하겠습니다.

phase_4

func4

__isoc99_sscanf

__isoc99_sscanf

phase2에서 __isoc99_sscanf 함수에 알아낸 사실들을 정리하면 다음과 같습니다.

1. 입력한 정수가 %rdi에서 저장된 문자열에서 배열형태로 변환됩니다.
2. 첫번째 원소를 가리키는 포인터가 %rsp에 저장됩니다.
3. 입력한 정수의 개수를 %rax에 반환합니다.

따라서 50 100 을 입력했다면 오른쪽의 상황을 가집니다.

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>

__isoc99_sscanf 함수의 인자로 %rsi에 "%d %d"를 담아 전달합니다.

(gdb) x/s 0x555555402ded
0x555555402ded:	"%d %d"

<+35>

1. "%d %d"를 전달해서 함수를 호출했으므로 두 개의 정수를 입력해야한다고 판단할 수 있습니다.

2. %rsp에 정수배열의 포인터가 저장됩니다.

3. %rax에 입력한 정수의 개수가 저장됩니다.

<+40 ~ 43>

   0x000055555540147d <+40>:	cmp    $0x2,%eax
   0x0000555555401480 <+43>:	jne    0x555555401488 <phase_4+51>

   0x0000555555401488 <+51>:	callq  0x555555401a90 <explode_bomb>

<+40> : 입력한 정수의 개수를 2와 비교합니다.

<+43> : 입력한 정수의 개수가 2가 아니라면 <+51>로 점프하고 폭탄이 터지므로, 입력해야하는 정수의 개수는 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)는 오른쪽 그림과 같이 입력한 첫번째 정수입니다. 첫번째 정수와 14를 비교합니다.

<+49> : unsigned비교이므로 첫번째 정수가 0 미만, 14 초과라면 <+51>로 이동합니다.

<+51> : 폭탄이 터집니다. 즉 첫번째 정수는 0 이상 14 이하를 만족해야합니다.

<+56> : %edx에 14를 저장합니다.

<+61> : %esi에 0을 저장합니다.

<+66> : %edi에 첫번째 정수를 저장합니다.

<+69> : 바로 func4를 호출하는것으로 보아 %edx, %esi, %edi가 함수의 인자로 작동한다고 추측할 수 있습니다.

<+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> : func4가 리턴된 후의 R[%eax]는 여전히 2(입력한 정수 개수는 항상 두개여야 함이 보장되었다)거나 func4의 리턴값 둘 중 하나일겁니다. 그 값을 7과 비교합니다.

<+77> : 만약 R[%eax]가 7이 아니면 <+86>으로 이동해서 폭탄이 터지므로, func4는 리턴값이 존재하는 함수임을 알 수 있습니다.

그리고 그 func4의 리턴값은 7이 나오도록 인자를 전달해야합니다.

<+79> : 0x4(%rsp)는 입력한 두 번째 숫자입니다. 두번째 숫자와 7을 비교합니다.

<+84> : 두번째 숫자가 7과 같은지 비교합니다.

<+86> : 두번째 숫자가 7이 아니면 폭탄이 터지므로, 두번째 숫자는 7 이어야합니다.

<이후> : 일반적인 함수를 마치려는 코드입니다.

func4를 분석하기 전에 우리가 문제를 해결하기위해 필요한 조건들을 정리해보겠습니다.

1. 입력한 첫번째 숫자는 0 이상 14 이하를 만족해야한다.
2. 입력한 두번째 숫자는 7 이어야 한다.
3. %edx, %esi, %edi가 인자로 전달되며 그 값들은 다음과 같습니다. R[%edx] = 14, R[%esi] = 0, R[%edi] = 입력한 첫번째 정수
4. 리턴값이 7이 되도록 인자를 전달해야하는데, R[%edx]와 R[%esi]는 14와 0으로 정해져있습니다. 즉 R[%edi]를 리턴값이 7이 되도록 전달해야합니다. 다시말하면 첫번째 정수를 리턴값이 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>

입력한 첫번째 정수를 a(0 <= a <= 14)라고 가정하면,

전달되는 인자는 R[%edx] = 14, R[%esi] = 0, R[%edi] = a 입니다. 

우리는 a값을 통해서 리턴값이 7이 되도록 해야합니다.

<+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> : %ebx에 31번 오른쪽으로 shift합니다. 이는 %ebx의 부호를 추출한다고 이해할 수 있습니다.

<+10> : %ebx에 %eax를 더합니다.

<+12> : %ebx를 부호를 고려한 채 오른쪽으로 한번 shift합니다. 이는 %ebx를 2로 나눈것과 같습니다.

<+14> : %ebx에 %edi에 더합니다.

여기까지 계산한 식을 정리하면 오른쪽과 같습니다.

<+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> : R[%ebx]와 R[%edi]를 비교합니다.

<+18> : 만약 %ebx가 더 크면 <+28>로 점프합니다.

<+20> : 다시 비교합니다.

<+22> : 만약 %ebx가 더 작으면 <+40>으로 점프합니다.

<+24> : 크지도 않고 작지도 않으니, R[%ebx] == R[%edi] 입니다.  그러면 %ebx를 %eax에 넣어 return합니다.

<+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> :  R[%edx] = R[%rbx] - 1 을 진행합니다.
• <+31> : 코드의 처음으로 돌아가서 재귀호출합니다.

R[%ebx] > R[%edi]

• <+40> : R[%esi] = R[%rbx] + 1 을 진행합니다.
• <+34> : 코드의 처음으로 돌아가서 재귀호출합니다.

func4 결론

코드를 잘 보시면 이분탐색을 진행하는 코드임을 알 수 있습니다.

검색 범위는 0부터 14까지인데, %esi는 최소값을 담당하고 %edx를 담당합니다.

검색 대상은 우리가 입력한 첫번째 숫자인 %edi입니다.

그리고 %edx와 %esi의 중간 인덱스를 %ebx에 저장해서 그 값을 Target인 %edi와 비교해서 분기합니다.결론적으로 리턴값은 검색을 성공했을 때의 %ebx 입니다.

리턴값이 7이어야한다는건, 검색을 성공했을 때의 인덱스가 7이어야한다는겁니다.

또한 검색을 성공했다는건 R[%ebx] == R[%edi] 임을 의미하므로, 검색 대상인 첫번째 숫자가 7이어야함을 의미합니다.

인덱스와 그 값이 완전히 똑같은 배열에서 왜 이분탐색을 돌리는지는 의문이지만,

결론적으로 첫번째 숫자가 7, 두번째 숫자가 7이어야하므로 답은 다음과 같습니다.

7 7

main

<+148> : main함수에서 read_line의 반환값이 %rdi에 저장되는 것으로보아, 입력한 문자열이 %rdi에 저장됨을 추론할 수 있습니다.

   0x0000555555401214 <+138>:	callq  0x555555400f00 <puts@plt>
   0x0000555555401219 <+143>:	callq  0x555555401b0d <read_line>
   0x000055555540121e <+148>:	mov    %rax,%rdi
   0x0000555555401221 <+151>:	callq  0x55555540136d <phase_3>

테스트 결과 일치함을 확인할 수 있었습니다.

(gdb) x/s $rdi
0x555555604760 <input_strings+160>:	"50 100"

__isoc99_sscanf 분석

phase2에서 __isoc99_sscanf 함수에 대해 이미 알아낸 사실들이 많습니다.

1. 입력한 정수가 %rdi에서 저장된 문자열에서 배열형태로 변환됩니다.
2. 첫번째 원소를 가리키는 포인터가 %rsp에 저장됩니다.
3. 입력한 정수의 개수를 %rax에 반환합니다.

따라서 50 100을 입력했을 때 오른쪽의 상황을 가집니다.

Phase_3

Dump of assembler code for function phase_3:
   0x000055555540136d <+0>:	sub    $0x18,%rsp
   0x0000555555401371 <+4>:	mov    %fs:0x28,%rax
   0x000055555540137a <+13>:	mov    %rax,0x8(%rsp)
   0x000055555540137f <+18>:	xor    %eax,%eax
   0x0000555555401381 <+20>:	lea    0x4(%rsp),%rcx
   0x0000555555401386 <+25>:	mov    %rsp,%rdx
   0x0000555555401389 <+28>:	lea    0x1a5d(%rip),%rsi        # 0x555555402ded
   0x0000555555401390 <+35>:	callq  0x555555400fc0 <__isoc99_sscanf@plt>
   0x0000555555401395 <+40>:	cmp    $0x1,%eax
   0x0000555555401398 <+43>:	jle    0x5555554013b3 <phase_3+70>
   0x000055555540139a <+45>:	cmpl   $0x7,(%rsp)
   0x000055555540139e <+49>:	ja     0x5555554013eb <phase_3+126>
   0x00005555554013a0 <+51>:	mov    (%rsp),%eax
   0x00005555554013a3 <+54>:	lea    0x1796(%rip),%rdx        # 0x555555402b40
   0x00005555554013aa <+61>:	movslq (%rdx,%rax,4),%rax
   0x00005555554013ae <+65>:	add    %rdx,%rax
   0x00005555554013b1 <+68>:	jmpq   *%rax
   0x00005555554013b3 <+70>:	callq  0x555555401a90 <explode_bomb>
   0x00005555554013b8 <+75>:	jmp    0x55555540139a <phase_3+45>
   0x00005555554013ba <+77>:	mov    $0x8c,%eax
   0x00005555554013bf <+82>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c1 <+84>:	mov    $0x3be,%eax
   0x00005555554013c6 <+89>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c8 <+91>:	mov    $0x79,%eax
   0x00005555554013cd <+96>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013cf <+98>:	mov    $0x2c9,%eax
   0x00005555554013d4 <+103>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013d6 <+105>:	mov    $0x379,%eax
   0x00005555554013db <+110>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013dd <+112>:	mov    $0x347,%eax
   0x00005555554013e2 <+117>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013e4 <+119>:	mov    $0x39a,%eax
   0x00005555554013e9 <+124>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013eb <+126>:	callq  0x555555401a90 <explode_bomb>
   0x00005555554013f0 <+131>:	mov    $0x0,%eax
   0x00005555554013f5 <+136>:	jmp    0x5555554013fc <phase_3+143>
   0x00005555554013f7 <+138>:	mov    $0x123,%eax
   0x00005555554013fc <+143>:	cmp    %eax,0x4(%rsp)
   0x0000555555401400 <+147>:	je     0x555555401407 <phase_3+154>
   0x0000555555401402 <+149>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401407 <+154>:	mov    0x8(%rsp),%rax
   0x000055555540140c <+159>:	xor    %fs:0x28,%rax
   0x0000555555401415 <+168>:	jne    0x55555540141c <phase_3+175>
   0x0000555555401417 <+170>:	add    $0x18,%rsp
   0x000055555540141b <+174>:	retq
   0x000055555540141c <+175>:	callq  0x555555400f20 <__stack_chk_fail@plt>

<+40 ~ 49>

   0x0000555555401395 <+40>:	cmp    $0x1,%eax
   0x0000555555401398 <+43>:	jle    0x5555554013b3 <phase_3+70>
   0x000055555540139a <+45>:	cmpl   $0x7,(%rsp)
   0x000055555540139e <+49>:	ja     0x5555554013eb <phase_3+126>

   0x00005555554013b3 <+70>:	callq  0x555555401a90 <explode_bomb>

   0x00005555554013eb <+126>:	callq  0x555555401a90 <explode_bomb>

<+40> : 현재 R[%eax]는 입력한 숫자의 개수입니다. 입력한 숫자의 개수를 1과 비교합니다.

<+43> : 만약 1 이하라면 <+70>으로 점프합니다. <+70>은 폭탄이므로, 입력하는 숫자의 개수는 2개 이상이어야 합니다. (50을 입력했다고 가정했으므로 폭탄이 터집니다.)

<+45> : (%rsp)는 입력한 첫번째 숫자입니다. 첫번째 숫자와 7을 비교합니다.

<+49> : 7보다 크거나 0보다 작으면(ja는 unsigned 연산이므로) <+126>으로 점프합니다. 폭탄이므로 첫번째 숫자는 0이상, 7이하 여야합니다.

여기서부터는 0 291을 입력했다고 가정합니다.

<+51 ~ 68>

   0x00005555554013a0 <+51>:	mov    (%rsp),%eax
   0x00005555554013a3 <+54>:	lea    0x1796(%rip),%rdx        # 0x555555402b40
   0x00005555554013aa <+61>:	movslq (%rdx,%rax,4),%rax
   0x00005555554013ae <+65>:	add    %rdx,%rax
   0x00005555554013b1 <+68>:	jmpq   *%rax

<+51> : %eax에 입력한 첫번째 숫자를 저장합니다.

<+54> : <+54> 코드를 진행할 때의 R[%rip]는 <+61>의 주소, 0x00005555554013aa입니다. (%rip, PC는 다음 실행할 명령어의 주소를 가리킨다.)

즉, R[%rdx] = 0x1796 + 0x00005555554013aa = 0x555555402b40 가 됩니다.

<+61> : %rax는 입력한 첫번째 숫자를 의미하는데, 0이상 7이하의 숫자를 가지는 숫자에 4를 곱해서 %rdx에 더한값이 가리키는 주소의 값을 %rax에 저장합니다. R[%rdx] + 4 * R[%rax]의 참조 값은 gdb test로 알아낼 수 있었습니다.

   0x00005555554013ba <+77>: mov    $0x8c,%eax
   0x00005555554013bf <+82>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c1 <+84>: mov    $0x3be,%eax
   0x00005555554013c6 <+89>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013c8 <+91>: mov    $0x79,%eax
   0x00005555554013cd <+96>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013cf <+98>: mov    $0x2c9,%eax
   0x00005555554013d4 <+103>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013d6 <+105>: mov    $0x379,%eax
   0x00005555554013db <+110>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013dd <+112>: mov    $0x347,%eax
   0x00005555554013e2 <+117>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013e4 <+119>: mov    $0x39a,%eax
   0x00005555554013e9 <+124>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013eb <+126>: callq  0x555555401a90 <explode_bomb>
   0x00005555554013f0 <+131>: mov    $0x0,%eax
   0x00005555554013f5 <+136>: jmp    0x5555554013fc <phase_3+143>
   0x00005555554013f7 <+138>: mov    $0x123,%eax

첫번째 숫자에 따라 점프해서 %eax에 값을 저장하고 있습니다.

각 숫자별로 정리하면 다음과 같습니다.

   0x00005555554013fc <+143>:	cmp    %eax,0x4(%rsp)
   0x0000555555401400 <+147>:	je     0x555555401407 <phase_3+154>
   0x0000555555401402 <+149>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401407 <+154>:	mov    0x8(%rsp),%rax
   0x000055555540140c <+159>:	xor    %fs:0x28,%rax
   0x0000555555401415 <+168>:	jne    0x55555540141c <phase_3+175>
   0x0000555555401417 <+170>:	add    $0x18,%rsp
   0x000055555540141b <+174>:	retq

<+143> : 0x4(%rsp) 는 우리가 입력한 두번째 숫자를 의미합니다. 두번째 숫자와 R[%eax]를 비교하고 있습니다.

<+147> : 만약 위에서 정리한 R[%eax]와 두번째 숫자가 같다면 <+154>로 점프합니다.

<+149> : 만약 두번째 숫자가 R[%eax]와 다르다면, 폭탄이 터지게 되므로 두번째 숫자와 R[%eax]가 같아야함이 밝혀졌습니다.

즉 답은 다음과 같습니다.

두 가지 함수를 분석하려고 합니다.

phase_2

read_six_numbers

__isoc99_sscanf@plt

역순으로 분석해보겠습니다.

__isoc99_sscanf@plt

C언어에서 sscanf는 문자열에서 다른 변수로 입력을 받아들이는 역할을 하는 함수이고, 여기서도 비슷할거라 추측합니다.

read_six_numbers

Dump of assembler code for function read_six_numbers:
   0x0000555555401acc <+0>:	sub    $0x8,%rsp
   0x0000555555401ad0 <+4>:	mov    %rsi,%rdx
   0x0000555555401ad3 <+7>:	lea    0x4(%rsi),%rcx
   0x0000555555401ad7 <+11>:	lea    0x14(%rsi),%rax
   0x0000555555401adb <+15>:	push   %rax
   0x0000555555401adc <+16>:	lea    0x10(%rsi),%rax
   0x0000555555401ae0 <+20>:	push   %rax
   0x0000555555401ae1 <+21>:	lea    0xc(%rsi),%r9
   0x0000555555401ae5 <+25>:	lea    0x8(%rsi),%r8
   0x0000555555401ae9 <+29>:	lea    0x12f1(%rip),%rsi        # 0x555555402de1
   0x0000555555401af0 <+36>:	mov    $0x0,%eax
   0x0000555555401af5 <+41>:	callq  0x555555400fc0 <__isoc99_sscanf@plt>
   0x0000555555401afa <+46>:	add    $0x10,%rsp
   0x0000555555401afe <+50>:	cmp    $0x5,%eax
   0x0000555555401b01 <+53>:	jle    0x555555401b08 <read_six_numbers+60>
   0x0000555555401b03 <+55>:	add    $0x8,%rsp
   0x0000555555401b07 <+59>:	retq
   0x0000555555401b08 <+60>:	callq  0x555555401a90 <explode_bomb>

<+29>

%rsi는 인자로 자주 쓰이는 레지스터입니다.

이 레지스터에 어떤 값이 전달되는지 관찰해보았습니다.

(gdb) x/s 0x555555402de1
0x555555402de1:	"%d %d %d %d %d %d"

"%d %d %d %d %d %d" 였습니다. 즉, sscanf에서 문자열에서 6개의 정수로 이루어진 정수 띄어쓰기 단위로 읽어들인다고 생각할 수 있습니다.

<+50 ~ 53>

포인트만 관찰해보면, 에서 %eax의 값이 5보다 작거나 같으면 폭탄으로 점프하기 때문에 6개 이상의 숫자를 입력해야합니다. 즉 read_six_number 함수에서 %eax를 통해 값의 개수를 반환한다고 추론할 수 있습니다.

<main>

   0x00005555554011f6 <+108>:	callq  0x555555400f00 <puts@plt>
   0x00005555554011fb <+113>:	callq  0x555555401b0d <read_line>
   0x0000555555401200 <+118>:	mov    %rax,%rdi
   0x0000555555401203 <+121>:	callq  0x555555401304 <phase_2>
   0x0000555555401208 <+126>:	callq  0x555555401c51 <phase_defused>

<+113> : read_line 함수를 호출합니다. 한 줄 입력받는 함수라고 추론할 수 있습니다.

<+118> : %rdi 에게 값을 넘기는것을 보아 %rdi에 입력받은 문자열이 저장된다고 추론해볼 수 있습니다.

테스트를 진행해보니, 예상이 맞았습니다.

<__isoc_sscanf> <read_six_numbers>

지금까지의 분석을 통해

테스트로 얻은 결론은 이렇습니다.

1. %rsi에서 전달한 문자열을 통해 __isoc99_sscanf에서 어떤 형식으로 입력을 받을지 결정할 수 있습니다. 지금 경우에는 "%d %d %d %d %d %d" 가 전달되었으므로 6개의 정수를 읽는다고 판단할 수 있습니다.
2. 입력한 문자열이 __isoc99_sscanf 를 진행하면서 %rdi에서 전달되어 sscanf 함수를 통해 %rsp에 정수 배열형태로 저장됩니다.
3. read_six_numbers에서 정수 배열 개수가 5개 이하라면 폭탄을 터뜨립니다.
4. read_six_numbers는 반환값으로 입력한 정수의 개수를 반환한다. 더 자세히 말하면 read_six_numbers는가 %rax에 저장하지 않으므로,  __isoc99_sscanf 함수가 %rax에 입력한 정수의 개수를 반환합니다.

phase_2

Dump of assembler code for function phase_2:
=> 0x0000555555401304 <+0>:	push   %rbp
   0x0000555555401305 <+1>:	push   %rbx
   0x0000555555401306 <+2>:	sub    $0x28,%rsp
   0x000055555540130a <+6>:	mov    %fs:0x28,%rax
   0x0000555555401313 <+15>:	mov    %rax,0x18(%rsp)
   0x0000555555401318 <+20>:	xor    %eax,%eax
   0x000055555540131a <+22>:	mov    %rsp,%rsi
   0x000055555540131d <+25>:	callq  0x555555401acc <read_six_numbers>
   0x0000555555401322 <+30>:	cmpl   $0x1,(%rsp)
   0x0000555555401326 <+34>:	jne    0x555555401331 <phase_2+45>
   0x0000555555401328 <+36>:	mov    %rsp,%rbx
   0x000055555540132b <+39>:	lea    0x14(%rbx),%rbp
   0x000055555540132f <+43>:	jmp    0x555555401341 <phase_2+61>
   0x0000555555401331 <+45>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401336 <+50>:	jmp    0x555555401328 <phase_2+36>
   0x0000555555401338 <+52>:	add    $0x4,%rbx
   0x000055555540133c <+56>:	cmp    %rbp,%rbx
   0x000055555540133f <+59>:	je     0x555555401351 <phase_2+77>
   0x0000555555401341 <+61>:	mov    (%rbx),%eax
   0x0000555555401343 <+63>:	add    %eax,%eax
   0x0000555555401345 <+65>:	cmp    %eax,0x4(%rbx)
   0x0000555555401348 <+68>:	je     0x555555401338 <phase_2+52>
   0x000055555540134a <+70>:	callq  0x555555401a90 <explode_bomb>
   0x000055555540134f <+75>:	jmp    0x555555401338 <phase_2+52>
   0x0000555555401351 <+77>:	mov    0x18(%rsp),%rax
   0x0000555555401356 <+82>:	xor    %fs:0x28,%rax
   0x000055555540135f <+91>:	jne    0x555555401368 <phase_2+100>
   0x0000555555401361 <+93>:	add    $0x28,%rsp
   0x0000555555401365 <+97>:	pop    %rbx
   0x0000555555401366 <+98>:	pop    %rbp
   0x0000555555401367 <+99>:	retq
   0x0000555555401368 <+100>:	callq  0x555555400f20 <__stack_chk_fail@plt>

위에서 read_six_number에서 분석한 결과에 따르면,

현재 우리가 입력한 값은 오른쪽과 같은 구조를 가지게 됩니다.

(주소값은 예시)

<+30 ~ 34>

(%rsp)는 우리가 입력한 첫번째 숫자입니다.

<+30> 에서 1과 비교 후 <+34>에서 첫번째 숫자가 1이 아니라면 <+45>로 넘어가게 됩니다.

   0x0000555555401322 <+30>:	cmpl   $0x1,(%rsp)
   0x0000555555401326 <+34>:	jne    0x555555401331 <phase_2+45>

<+45>로 넘어가면 폭탄이 터지므로 첫번째 숫자는 1이어야 합니다.

0x0000555555401331 <+45>:	callq  0x555555401a90 <explode_bomb>

<+30 ~ 34>

여기서부터는 입력한 첫번째 숫자가 1임을 보장된 상태로 코드를 진행합니다.

<+36>:	mov    %rsp,%rbx
<+39>:	lea    0x14(%rbx),%rbp
<+43>:  jmp    0x555555401341 <phase_2+61>

<+36>에서 %rbx도 첫번째 숫자를 가리키는 포인터를 가지도록합니다.

<+39>에서 0x14를 더한 주소값을 %rbp에 저장하므로,

%rbp는 우리가 입력한 6번째 숫자를 가리키게 됩니다.

<+43>에서 <+61>로 점프합니다.

<+61 ~ 68>

<+61>:	mov    (%rbx),%eax
<+63>:	add    %eax,%eax
<+65>:	cmp    %eax,0x4(%rbx)
<+68>:	je     0x555555401338 <phase_2+52>
<+70>:	callq  0x555555401a90 <explode_bomb>

<+61> : %rax에 첫번째 숫자를 복사합니다.

<+63> : %rax의 값에 2를 곱합니다.

<+65> : 0x4(%rbx)는 %rbx가 가리키는 숫자의 다음 숫자를 의미합니다. 즉, 두번째 숫자와 비교합니다.

<+68> : 두번째 숫자와 첫번째 숫자에 2를 곱한값이 같다면 <+52>로 되돌아갑니다. 다르다면 <+70>에서 폭탄이 터집니다.

<+52 ~ 61>

   0x0000555555401338 <+52>:	add    $0x4,%rbx
   0x000055555540133c <+56>:	cmp    %rbp,%rbx
   0x000055555540133f <+59>:	je     0x555555401351 <phase_2+77>
   0x0000555555401341 <+61>:	mov    (%rbx),%eax

<+52> : %rbx가 0x04를 더해서 다음 원소를 가리키도록 합니다.

<+56> : 마지막 원소를 가리키는 포인터와 두번째 원소를 가리키는 포인터를 비교합니다.

<+59> : 만약 마지막 원소와 주소값이 같다면 <+77>로 점프합니다.

<+61> : 아니라면 <+61>부터 %rbx가 %rbp와 같을 때까지, 즉 %rax에는 다시 %rbx에 2를 곱한값이 저장되어야하고, %rbx가 다음 원소를 가리킴이 마지막 원소에 도달할 때까지 반복합니다.

<+77 ~ 99>

   0x0000555555401351 <+77>:	mov    0x18(%rsp),%rax
   0x0000555555401356 <+82>:	xor    %fs:0x28,%rax
   0x000055555540135f <+91>:	jne    0x555555401368 <phase_2+100>
   0x0000555555401361 <+93>:	add    $0x28,%rsp
   0x0000555555401365 <+97>:	pop    %rbx
   0x0000555555401366 <+98>:	pop    %rbp
   0x0000555555401367 <+99>:	retq

여기까지 도달했다면, 입력해야하는 숫자가 다음과 같은 공식을 만족해야합니다.

a[i+1] = a[i] * 2 : 0 <= i <= 5, a[i] = 1

스택에서 phase_2를 pop합니다.

즉 답은 다음과 같습니다.

1 2 4 8 16 32

세 가지 함수를 분석하려고 합니다.

phase_1

strings_no_equal

string_length

string_length

Dump of assembler code for function string_length:
   0x000000000000176f <+0>:	cmpb   $0x0,(%rdi)
   0x0000000000001772 <+3>:	je     0x1786 <string_length+23>
   0x0000000000001774 <+5>:	mov    %rdi,%rdx
   0x0000000000001777 <+8>:	add    $0x1,%rdx
   0x000000000000177b <+12>:	mov    %edx,%eax
   0x000000000000177d <+14>:	sub    %edi,%eax
   0x000000000000177f <+16>:	cmpb   $0x0,(%rdx)
   0x0000000000001782 <+19>:	jne    0x1777 <string_length+8>
   0x0000000000001784 <+21>:	repz retq
   0x0000000000001786 <+23>:	mov    $0x0,%eax
   0x000000000000178b <+28>:	retq

string_length는 문자열 길이를 반환하는 함수라고 과감히 예상할 수 있습니다.

그리고 바로 %rdi를 사용하는것으로 보아, %rdi에 문자열이 전달되었다고 생각할 수 있습니다.

전달될 때는 첫 element의 주소가 저장됩니다.

<+0 ~ 3> 

(%rdi) - 0x0을 계산하고 결과값이 0과 같으면 23번 줄로 점프합니다.

다시말하면, (%rdi)는 현재 배열에서 첫번째 value고 이 value가 '\0'임을 체크합니다.

만약 '\0'이면 <+23>으로 점프해서 eax에 0을 저장하고 리턴하고, 아니라면 다음으로 진행합니다.

   0x000000000000176f <+0>:	cmpb   $0x0,(%rdi)
   0x0000000000001772 <+3>:	je     0x1786 <string_length+23>

   0x0000000000001786 <+23>:	mov    $0x0,%eax
   0x000000000000178b <+28>:	retq

<+5 ~ 14>

%rdx에 %rdi값을 저장했습니다. 즉 %rdx도 첫번째 원소를 가리키는 포인터값을 지니게 됩니다.

그 후 1을 더하므로 다음 원소를 가리키게 되고, %eax가 %rdx의 포인터값의 일부를 가지도록 합니다.

그 후 %eax에서 %edi를 빼므로 %rdx와 %rdi의 인덱스 차이를 가지게 됩니다.

   0x0000000000001774 <+5>:	mov    %rdi,%rdx
   0x0000000000001777 <+8>:	add    $0x1,%rdx
   0x000000000000177b <+12>:	mov    %edx,%eax
   0x000000000000177d <+14>:	sub    %edi,%eax

<+16 ~ 19>

%rdx가 가리키는 주소값의 내용, 즉 두번째 원소가 null인지 비교합니다. (아까 했던 과정임)

'\0'이 아니라면 <+8>로 점프합니다.

   0x000000000000177f <+16>:	cmpb   $0x0,(%rdx)
   0x0000000000001782 <+19>:	jne    0x1777 <string_length+8>

결론

여기서부터 %rdx를 1더하고

%eax는 %rdx에서 %rdi의 간격차를 계산한 값을 가지게 되는데

이를 %rdx가 '\0'이 될때까지 반복하므로 %eax가 결국에는 %rdi에 전달받은 문자열이 길이를 가지게 됨을 알 수 있습니다.

string_no_equal

Dump of assembler code for function strings_not_equal:
   0x000000000000178c <+0>:	push   %r12
   0x000000000000178e <+2>:	push   %rbp
   0x000000000000178f <+3>:	push   %rbx
   0x0000000000001790 <+4>:	mov    %rdi,%rbx
   0x0000000000001793 <+7>:	mov    %rsi,%rbp
   0x0000000000001796 <+10>:	callq  0x176f <string_length>
   0x000000000000179b <+15>:	mov    %eax,%r12d
   0x000000000000179e <+18>:	mov    %rbp,%rdi
   0x00000000000017a1 <+21>:	callq  0x176f <string_length>
   0x00000000000017a6 <+26>:	mov    $0x1,%edx
   0x00000000000017ab <+31>:	cmp    %eax,%r12d
   0x00000000000017ae <+34>:	je     0x17b7 <strings_not_equal+43>
   0x00000000000017b0 <+36>:	mov    %edx,%eax
   0x00000000000017b2 <+38>:	pop    %rbx
   0x00000000000017b3 <+39>:	pop    %rbp
   0x00000000000017b4 <+40>:	pop    %r12
   0x00000000000017b6 <+42>:	retq
   0x00000000000017b7 <+43>:	movzbl (%rbx),%eax
   0x00000000000017ba <+46>:	test   %al,%al
   0x00000000000017bc <+48>:	je     0x17e5 <strings_not_equal+89>
   0x00000000000017be <+50>:	cmp    0x0(%rbp),%al
   0x00000000000017c1 <+53>:	jne    0x17ec <strings_not_equal+96>
   0x00000000000017c3 <+55>:	add    $0x1,%rbx
   0x00000000000017c7 <+59>:	add    $0x1,%rbp
   0x00000000000017cb <+63>:	movzbl (%rbx),%eax
   0x00000000000017ce <+66>:	test   %al,%al
   0x00000000000017d0 <+68>:	je     0x17de <strings_not_equal+82>
   0x00000000000017d2 <+70>:	cmp    %al,0x0(%rbp)
   0x00000000000017d5 <+73>:	je     0x17c3 <strings_not_equal+55>
   0x00000000000017d7 <+75>:	mov    $0x1,%edx
   0x00000000000017dc <+80>:	jmp    0x17b0 <strings_not_equal+36>
   0x00000000000017de <+82>:	mov    $0x0,%edx
   0x00000000000017e3 <+87>:	jmp    0x17b0 <strings_not_equal+36>
   0x00000000000017e5 <+89>:	mov    $0x0,%edx
   0x00000000000017ea <+94>:	jmp    0x17b0 <strings_not_equal+36>
   0x00000000000017ec <+96>:	mov    $0x1,%edx
   0x00000000000017f1 <+101>:	jmp    0x17b0 <strings_not_equal+36>

string_no_eqaul, 문자열 두 개 받아서 서로 다른지 비교하는 기능을 가졌을 것으로 보입니다.

<+4 ~ 7>

인자 전달로 자주쓰이는 %rdi, %rsi를 %rbx, %rbp로 전달했습니다.

이는 callee-saved register인 레지스터에 저장해서 caller-saved register인 %rdi, %rsi가 string_no_eqaul 함수에서 변하지 않도록 하기위함을 알 수 있습니다.

이제 %rbx, %rbp가 각각 문자열의 첫 원소를 가리키는 포인터를 가집니다.

<+10 ~ 31>

위의 분석해서 알 수 있듯이 string_length 함수는 %rdi를 인자로 전달받는 함수입니다.

즉, 위 문자열에서 "abcdefg" 문자열이 전달되고 %eax에 7이 반환되고 이를 %r12d에 저장합니다.

그리고 <+18> 에서 %rbp의 값을 %rdi에 전달합니다. 이는 아래 문자열을 string_length의 인자로 전달하기 위함임을 알 수 있습니다.

함수리 리턴되면 %eax에 7이 전달될겁니다.

<+26>

%edx 에 1을 저장하고 있습니다.( 어떤 역할인지는 밑에서 설명합니다 )

<+31 ~ 34>

%r12d과 %eax 둘이 같은지 비교합니다.

다시말하면, 첫번째 문자열의 길이와 두번째 문자열의 길이를 비교합니다.

- 만약 같다면 <+43>으로 점프합니다.

- 만약 다르면, 두 문자열이 서로 다름이 판정되었으므로 점프하지 않고 <+36 ~ 42>에서 %edx를 %eax에 저장해 반환함으로써 결과적으로 1을 반환합니다.

-> 즉 %edx는 문자열이 다른지 같은지를 알려주는 반환값의 역할을 하는 레지스터입니다.

<+43 ~ 48>

여기부터는 두 문자열의 길이가 같음을 보장한 후 진행하게됩니다. (다른경우 이미 리턴됐으므로)

(%rbx)는 첫번째 문자열에서 가리키고 있는 값입니다. 이 경우에는 a입니다. 그리고 a를 %eax에 저장합니다.

그리고 저장한 %eax는 1바이트 값이므로 %al이 '\0'인지 아닌지 체크합니다.

- '\0' 인경우 : 만약 '\0'이라면 두 문자열이 모두 비었음을 의미하고, 길이가 같으므로 두 문자열이 같습니다. 후에 <+89>로 이동해서 %edx를 0으로 만들어 <+36>으로 이동해 0을 반환하게 됩니다.

- '\0' 이 아닌경우 : 두 문자열이 모두 빈 문자열이 아님을 알 수 있습니다. 이제부터는 각 문자를 순서대로 하나씩 비교해봐야합니다.

우선 <+50 ~ 53>에서 첫번째 원소를 비교합니다.

   0x00000000000017be <+50>:	cmp    0x0(%rbp),%al
   0x00000000000017c1 <+53>:	jne    0x17ec <strings_not_equal+96>

%al은 첫번째 문자열의 첫번째값을 지니고, 0x0(%rbp)는 두번째 문자열의 첫번째 값을 가집니다.

<53>에서 두 문자열이 다르면 <+96> 으로 이동해서

   0x00000000000017ec <+96>:	mov    $0x1,%edx
   0x00000000000017f1 <+101>:	jmp    0x17b0 <strings_not_equal+36>

%edx에 1(두 문자열이 다름)을 저장하고 <+36>으로 점프해서 1을 반환합니다.

<+55 ~ 73>

%rbx, %rbp에 각각 1을 더해서 다음 원소를 가리키도록합니다.

다시 %eax에는 첫번째 문자열에서 %rbx가 가리키는 값을 가지도록하므로,

앞으로 나오는 %al은 첫번째 문자열의 원소입니다. (%al은 %eax의 일부입니다)

그리고 오른쪽의 상태를 가집니다.

이제 <+66>에서 %al이 '\0'인지 아닌지 체크합니다

'\0'인경우 : 두 문자열이 길이가 같지만, 가리키는 첫번째 문자열의 원소가 '\0'이므로 가리키는 두번째 문자열의 원소 또한 '\0'입니다. 즉 두 문자열이 같습니다. 때문에 <+82>로 넘어가서 0을 리턴합니다.

'\0'이 아닌경우 : 가리키는 두 원소가 같은지 체크해야합니다. 만약 다르다면 두 문자열이 다르므로 <+75>로 가서 1을 리턴합니다.

   0x00000000000017d7 <+75>:	mov    $0x1,%edx
   0x00000000000017dc <+80>:	jmp    0x17b0 <strings_not_equal+36>

만약 같다면 <+55>로 돌아가서 <+55 ~ 73> 과정을 반복해서 문자열의 같은지 여부를 %rax에 리턴하게 됩니다.

<+55>:	add    $0x1,%rbx
<+59>:	add    $0x1,%rbp
<+63>:	movzbl (%rbx),%eax
<+66>:	test   %al,%al
<+68>:	je     0x17de <strings_not_equal+82>
<+70>:	cmp    %al,0x0(%rbp)
<+73>:	je     0x17c3 <strings_not_equal+55>

두 문자열이 같은경우에 마지막 순간은 아래와 같은 상태가 됩니다.

phase_1

Dump of assembler code for function phase_1:
=> 0x00005555554012e4 <+0>:	sub    $0x8,%rsp
   0x00005555554012e8 <+4>:	lea    0x17e1(%rip),%rsi        # 0x555555402ad0
   0x00005555554012ef <+11>:	callq  0x55555540178c <strings_not_equal>
   0x00005555554012f4 <+16>:	test   %eax,%eax
   0x00005555554012f6 <+18>:	jne    0x5555554012fd <phase_1+25>
   0x00005555554012f8 <+20>:	add    $0x8,%rsp
   0x00005555554012fc <+24>:	retq
   0x00005555554012fd <+25>:	callq  0x555555401a90 <explode_bomb>
   0x0000555555401302 <+30>:	jmp    0x5555554012f8 <phase_1+20>

위에서 관찰했듯이 strings_not_eqaul 함수는 %rdi, %rsi를 매개변수로 가집니다.

<+4 ~ 18>

<+4>를 보면 0x17e1(%rip)를 %rsi에 저장하고 있습니다.

<+11>에서 strings_not_eqaul을 호출해서 %eax에 두 문자열이 같은지 다른지를 판별한 값이 들어갑니다.

<+16 ~ 18>에서 %eax가 1이면 <+25>로 가서 폭탄이 터지므로 두 문자열이 같도록해서 <+24>에서 정상적으로 phase_1이 리턴되도록 해야합니다.

즉, strings_not_eqaul의 %rdi, %rsi 중 하나는 입력한 값이고, 하나는 답이므로 <+11>전까지 진행해서 값을 꺼내보면 됩니다.

abcd를 입력해서 값을 꺼내보면,

%rdi에 입력한 값이 들어갔으므로, %rsi에 답이 있다고 추론할 수 있습니다.

즉, 답은 다음과 같습니다.

When I get angry, Mr. Bigglesworth gets upset.