[CS 문제 풀이] 어셈블리 코드 분석 및 C 코드 동작 해석

3.59

The following code computes the 128-bit product of two 64-bit signed values x and y and stores the result in memory:

다음 코드는 두 개의 64비트 부호를 지닌 값 x와 y의 128비트곱을 계산하고 그 결과를 메모리에 저장한다.

computes : 계산하다

bit product : 비트곱

signed : 부호를 지닌

 

typedef __int128 int128_t;
// typedef : 기존 자료형에 새로운 별칭을 부여할 때 사용되는 키워드
// __int128 : 128비트 길이의 정수를 저장할 수있는 확장 자료형
// int128_t : 자료형에 부여된 새로운 별칭

void store_prod(int128_t *dest, int64_t x, int64_t y) {
// int128_t *dest : 메모리 주소
// int64_t x : 64비트 길이의 정수형 x
// int64_t y : 64비트 길이의 정수형 y

   *dest=x* (int128_t) y;
    // (int128_t) : y를 128비트 정수로 형 변환(이러면 x도 자동으로 128비트로 변환한다.)
}

 

Gcc generates the following assembly code implementing the computation:

Gcc는 해당 연산 과정을 구현한 다음 어셈블리 코드를 생성한다.

generates : 생성하다

implementing : 구현하는

computation : 연산 과정(계산)

 

store_prod:		// 함수의 시작위치를 표시하는 이름
movq %rdx, %rax		// %rdx값을 %rax에 저장한다
cqto			// 64비트를 128비트로 변환한다
movq %rsi, %rcx		// %rsi값을 %rcs에 저장한다
sarq $63, %rcx 		// %rcx레지스터의 값을 오른쪽으로 63비트 이동시킨다
imulq %rax, %rcx	// %rcx에 들어 있던 값을 %rax의 값과 곱하고 그 결과를 %rcx에 저장한다
imulq %rsi, %rdx	// %rdx에 들어 있던 값을 %rsi의 값과 곱하고 그 결과를 %rdx에 저장한다
addq %rdx, %rcx		// %rcx에 들어있던 값을 %rdx의 값과 합하고 그 결과를 %rcs에 저장한다
mulq %rsi		// %rax에 들어있는 값과 %rsi의 값을 곱해서 그 결과를 %rdx:%rax에 저장한다
addq %rcx, %rdx		// %rdx에 들어있는 값을 %rcs의 값과 합하고 그 결과를 %rdx에 저장한다
movq %rax, (%rdi)	// %rax의 값을 %rdi가 가리키고 있는 메모리 주소에 저장한다
movq %rdx, 8(%rdi)	// %rdx의 값을 %rid가 가리키고 있는 주소에서 8바이트 떨어진 메모리 주소에 저장한다
ret			// 함수가 끝났음을 알리고, 위 함수를 호출한 곳으로 돌아간다(= return)

 

This code uses three multiplications for the multiprecision arithmetic required to implement 128-bit arithmetic on a 64-bit machine.

이 코드는 64비트 기계에서 128비트 산술을 구현하는데 필요한 다중 정밀도 산술을 위해 세개의 곱셈을 사용한다.

multiplications : 곱셈

multiprecision : 다중 정밀도

arithmetic : 산술

 

Describe the algorithm used to compute the product, and annotate the assembly code to show how it realizes your algorithm.

곱셈을 계산하는데 사용된 알고리즘을 설명하고, 너의 알고리즘을 어떻게 이해하는지 보여주기 위해 어셈블리 코드에 주석을 달아라.

Describe : 말로 설명하다

annotate : 주석을 달다

realizes : 이해하다

 

Hint: When extending arguments of x and y to 128 bits, they can be rewritten as x = 2⁶⁴ ·x_h + x_l and y = 2⁶⁴ · y_h + y_l, where x_h, x_l, y_h, and y_l are 64- bit values.

힌트: x와 y의 인자를 128비트로 확장할 때, x는 x = 2⁶⁴ ·x_h+ x_l로, y는 y = 2⁶⁴· y_h+ y_l로 다시 표현할 수 있다. 여기서 x_h, x_l, y_h, y_l는 모두 64비트 값이다.

arguments : 인자

 

Similarly, the 128-bit product can be written as p = 2⁶⁴ . p_h + p_l, where p_h and p_l are 64-bit values.

마찬가지로, 128비트 곱셈 결과 p는 p = 2⁶⁴·p_h + p_l 로 표현할 수 있으며, 여기서 p_h와 p_l은 각각 64비트 값이다.

 

Show how the code computes the values of p_h and p_l in terms of x_h, x_l, y_hh, and y_l.

x_h, x_l, y_h, y_l을 조건으로 하여 코드가 p_h와 p_l의 값을 어떻게 계산하는지 보여라.

terms : 조건

 

---

3.60

Consider the following assembly code:

다음 어셈블리 코드를 고려하자.

Consider : 고려하다. 주시하다.

 

// long loop(long x, int n)
// x in %rdi, n in %esi
// x값은 %rdi에 저장하고, n값은 %esi에 저장한다
// (%rdi == x), (%esi == n)
loop:			// 루프(함수 이름) 시작
	movl %esi, %ecx		// (%esi == n)값을 %ecx에 저장한다
	movl $1, %edx		// (%1 == 1)값을 %edx에 저장한다
	movl $0, %eax		// (%0 == 0)값을 %eax에 저장한다
	jmp .L2			// 조건 검사 부분으로 점프한다
.L3:			// 루프 본문 시작
	movq %rdi, %r8		// (%rdi == x)에 들어있는 값을 %r8에 저장한다
	andq %rdx, %r8		// (%r8 == %rdi == x)와 %rdx를 AND 연산한다
	orq %r8, %rax		// %rax와 %r8를 OR 연산한다
	salq %cl, %rdx		// %rdx를 %cl비트만큼 왼쪽으로 이동시킨다
.L2:			// 루프 조건 검사 시작
	testq %rdx, %rdx	// %rdx와 %rdx를 AND 연산하고, 그 결과가 0인지 아닌지 확인한다
	jne .L3			// 루프 본문으로 점프한다
	rep; ret		// 함수가 끝났음을 알리고, 위 함수를 호출한 곳으로 돌아간다(= return)

 

The preceding code was generated by compiling C code that had the following overall form:

이전 코드는 다음과 같은 전체적인 형태를 가진 C 코드를 컴파일해서 생성됐다.

overall : 전반적으로

long long(long x, long n)
{
    long result = (0);
    long mask;
    for(mask = (-); mask (-); mask = (mask << ?))
    {
    	result |= -;  
        // 기존 result에 -의 비트를 OR연산한다
        // 예시 : result = 1, - = 5라고할 때,
        // result의 비트는 0001, -의 비트는 0101이다.
        // 각 비트를 OR연산하면, 0101이므로 결과는 5가 된다.
    }
    return result;
}

// %eax는 함수 반환값을 저장하는 레지스터 -> %eax에 0을 저장하니까 result = 0;
// %rdi는 함수의 첫 번째 파라미터 값을 저장하는 레지스터
// %esi는 함수의 두 번째 파라미터 값을 저장하는 레지스터
// ...아니 %esi랑 %rsi가 같은 레지스터라고 한다. ㅋㅋ어이가 없네. 뭐이리 복잡해.
// 루프 본문 시작 시, %rdi에 들어 있는 x의 값을 %r8에 저장한다.
//

// long loop(long x, int n)
// x in %rdi, n in %esi
// x값은 %rdi에 저장하고, n값은 %esi에 저장한다
// (%rdi == x), (%esi == n)
loop:			// 루프(함수 이름) 시작
	movl %esi, %ecx		// (%esi == n)값을 %ecx에 저장한다
	movl $1, %edx		// (%1 == 1)값을 %edx에 저장한다
	movl $0, %eax		// (%0 == 0)값을 %eax에 저장한다
	jmp .L2			// 조건 검사 부분으로 점프한다
.L3:			// 루프 본문 시작
	movq %rdi, %r8		// (%rdi == x)에 들어있는 값을 %r8에 저장한다
	andq %rdx, %r8		// (%r8 == %rdi == x)와 %rdx를 AND 연산한다
	orq %r8, %rax		// %rax와 %r8를 OR 연산한다
	salq %cl, %rdx		// %rdx를 %cl비트만큼 왼쪽으로 이동시킨다
.L2:			// 루프 조건 검사 시작
	testq %rdx, %rdx	// %rdx와 %rdx를 AND 연산하고, 그 결과가 0인지 아닌지 확인한다
	jne .L3			// 루프 본문으로 점프한다
	rep; ret		// 함수가 끝났음을 알리고, 위 함수를 호출한 곳으로 돌아간다(= return)
    

A. x, n, result, mask가 각각 어떤 레지스터에 들어 있는가?
> x=%rdi, n=%esi, result=%eax, mask=%
B. result와 mask의 초기값은 무엇인가?
C. mask에 대한 테스트 조건은 무엇인가?
D. mask는 어떻게 업데이트 되는가?
E. result는 어떻게 업데이트 되는가?
F. C코드의 빈 부분을 모두 채워넣어라.

 

Your task is to fill in the missing parts of the C code to get a program equivalent to the generated assembly code.

너의 과제는 생성된 어셈블리 코드와 동일하게 동작하도록 C코드의 빈 부분을 채워넣어라.

get a program: 얻다. 만들어내다. (프로그램을 가져오다X)

 

Recall that the result of the function is returned in register %rax.

함수의 결과는 레지스터 %rax에 반환된다는 것을 상기하라.

Recall : 상기하다. 생각해 내다.

You will find it helpful to examine the assembly code before, during, and after the loop to form a consistent mapping between the registers and the program variables.

너는 루프 전, 중, 후에 어셈블리 코드를 분석하는 것이 레지스터와 프로그램 변수 사이의 일반적인 대응 관계를 형성하는데 도움이 된다는 것을 알게 될 것이다.

examine : 검사하다. 살펴보다. 분석하다.

consistent mapping : 일관된 대응 관계

A. Which registers hold program values x, n, result, and mask?

A. x, n, result, mask가 각각 어떤 레지스터에 들어 있는가?

B. What are the initial values of result and mask?

B. result와 mask의 초기값은 무엇인가?

C. What is the test condition for mask?

C. mask에 대한 테스트 조건은 무엇인가?

D. How does mask get updated?

D. mask는 어떻게 업데이트 되는가?

E. How does result get updated?

E. result는 어떻게 업데이트 되는가?

F. Fill in all the missing parts of the C code.

F. C코드의 빈 부분을 모두 채워넣어라.

---

3.63

This problem will give you a chance to reverse engineer a switch statement from disassembled machine code.

이 문제는 디스어셈블된 기계 코드를 바탕으로 switch문을 역으로 분석해 볼 기회를 너에게 제공한 것이다.

statement : 문장

 

In the following procedure, the body of the switch statement has been omitted:

다음 함수에서는, switch문의 본문이 생략되어 있다.

omitted : 생략된

 

long switch_prob(long x, long n) {
long result = x;
switch(n) {
/* Fill in code here */

}
return result;
}

 

// p1 in %rdi, p2 in %rsi, action in %edx
// p1은 %rdi에 저장
// p2는 %rsi에 저장
// %edx는 action에 저장

.L8: MODE_E
	movl $27, %eax			// 27이란 정수값을 %eax에 복사한다
	ret				// return
.L3: MODE_A
	movq (%rsi), %rax		// %rsi에 저장된 값을 %rax에 복사한다
	movq (%rdi), %rdx		// %rdi에 저장된 값을 %rdx에 복사한다
	movq %rdx, (%rsi)		// %rdx를 %rsi의 내부 값에 복사한다
	ret
.L5: MODE_B
	movq (%rdi), %rax		// %rdi에 저장된 값을 %rax에 복사
	addq (%rsi), %rax		// %rsi에 저장된 값을 %rax에 복사
	movq %rax, (%rdi)		// %rax를 %rdi의 내부 값에 복사
	ret				// return
.L6: MODE_C
	movq $59, (%rdi)		// 59란 정수값을 %rdi 내부 값에 복사
	movq (%rsi), %rax		// %rsi에 저장된 값을 %rax에 복사
	ret				// return
.L7: MODE_D
	movq (%rsi), %rax		// %rsi에 저장된 값을 %rax에 복사
	movq %rax, (%rdi)		// %rax의 값을 %rdi 내부 값에 복사
	movl $27, %eax			// 27이란 정수 값을 %eax에 복사
	ret				// return
.L9: default				// default
	movl $12, %eax			// 12란 정수 값을 %eax에 복사
	ret				// return

 

Figure 3.52 Assembly code for Problem 3.62. This code implements the different branches of a switch statement.

그림 3.52는 문제 3.62에 대한 어셈블리 코드이다. 이 코드는 switch문의 다른 branch들을 구현한다.

 

Figure 3.53 shows the disassembled machine code for the procedure.

그림 3.53은 해당 함수의 디스어셈블된 기계 코드를 보여준다.

 

The jump table resides in a different area of memory.

그 점프 테이블은 메모리의 서로 다른 지역에 존재한다.

resides : 존재한다

We can see from the indirect jump on line 5 that the jump table begins at address 0x4006f8.

우리는 그 점프 테이블이 주소 0x4006f8에서 시작되었다는 것을 5번째 줄의 간접 점프로 볼 수 있다.

 

Using the gdb debugger, we can examine the six 8-byte words of memory comprising the jump table with the command x/6gx 0x4006f8. Gdb prints the following:

gdb디버거를 사용하면서, 우리는 명령어 x/6gx 0x4006f8로 점프 테이블을 구성하는 8바이트 메모리 6개로 분석할 수 있다.

Gdb는 다음을 출력한다.

comprising : 구성하다. 포함하다. 의미하다. 이루어지다.

(gdb) x/6gx 0x4006f8

0x4006f8: 0x00000000004005a1 0x00000000004005c3

0x400708: 0x00000000004005a1 0x00000000004005aa

0x400718: 0x00000000004005b2 0x00000000004005bf

 

Fill in the body of the switch statement with C code that will have the same behavior as the machine code.

기계어와 동일한 행동을 하는 C언어로 이루어진 switch문의 본문을 채워라.

 

// long switch_prob(long x, long n)
// x in %rdi, n in %rsi
// x는 %rdi에 저장
// n은 %rsi에 저장

0000000000400590 <switch_prob>:				//switch문 시작
400590: 48 83 ee 3c sub $0x3c,%rsi			//
400594: 48 83 fe 05 cmp $0x5,%rsi			//
400598: 77 29 ja 4005c3 <switch_prob+0x33>		//
40059a: ff 24 f5 f8 06 40 00 jmpq *0x4006f8(,%rsi,8)	//
4005a1: 48 8d 04 fd 00 00 00 lea 0x0(,%rdi,8),%rax	//
4005a8: 00
4005a9: c3 retq
4005aa: 48 89 f8 mov %rdi,%rax
4005ad: 48 c1 f8 03 sar $0x3,%rax
4005b1: c3 retq
4005b2: 48 89 f8 mov %rdi,%rax
4005b5: 48 c1 e0 04 shl $0x4,%rax
4005b9: 48 29 f8 sub %rdi,%rax
4005bc: 48 89 c7 mov %rax,%rdi
4005bf: 48 0f af ff imul %rdi,%rdi
4005c3: 48 8d 47 4b lea 0x4b(%rdi),%rax
4005c7: c3 retq