Krafton Jungle/4. CSAPP

[Computer System] ③ 프로그램의 기계수준 표현 (2)

munsik22 2025. 4. 5. 22:55

3.5 산술연산과 논리연산

각 인스트럭션 클래스는 바이트, 워드, 더블워드, 쿼드워드의 서로 다른 크기의 데이터 연산을 갖는다. 연산들은 4개의 그룹으로 나뉘어진다.

  • 유효주소 적재 : 나중에 메모리 참조에 사용할 포인터 생성을 위해 사용
  • 단항
  • 이항 : (피연산자를 하나 받는지, 두개 받는지 차이)
  • 쉬프트 : <<, >> 즉, 비트를 이동시키는 연산자

​이항 연산은 두 개의 오퍼랜드를 가지는 반면, 단항 연한은 한 개의 오퍼랜드를 가진다.

3.5.1 유효주소 적재 Load Effective Address

Load effective address 명령어인 leaq는 movq의 변형이다. 메모리부터 레지스터까지를 읽는 명령어이다. leaq 명령어는 간단한 산술을 수행하기 위해 주로 사용되지만, 메모리 전체를 레퍼런스 하지 않는다. 이 명령어는 마지막 메모리 레퍼런스에 대한 포인터를 생성하는 데 사용된다.

정수의 산술연산: 유효주소 적재 인스트럭션(leaq)은 일반적으로 간단한 산술연산을 위해서 사용한다. 나머지 인스트럭션들은 보다 표준적인 단항 또는 이진 여산들이다. >>A나 >>L과 같이 표시하여 논리 우측 쉬프트, 산술 우측 쉬프트로 사용한다. ATT 포맷의 어셈블리 코드에서 직관적으로 알기 어려운 오퍼랜드의 순서를 사용하는 점에 유의하자.

long scale(long x, long y, long z) {
    long t = x + 4 * y + 12 * z;
    return t;
}
# long scale(long x, long y, long z)
# x in %rdi, y in %rsi, z in %rdx
scale:
    leaq	(%rdi,%rsi,4), %rax		# x + 4*y
    leaq	(%rdx,%rdx,2), %rdx		# z + 2*z = 3*z
    leaq	(%rax,%rdx,4), %rax		# (x+4*y) + 4*(3*z) = x + 4*y + 12*z
    ret

 

 Practice 3.6                                                                                                                                  

레지스터 %rbx가 p를 가지고 있고, %rdx가 q를 저장하고 있다고 하자. 각 어셈블리 코드 인스트럭션마다 레지스터 %rax에 저장되는 값을 나타내는 식을 아래 표에 채우시오. (드래그하면 정답이 보입니다.)

Instruction Result
leaq 9(%rdx), %rax 9 + q
leaq (%rdx,%rbx), %rax q + p
leaq (%rdx,%rbx, 3), %rax q + 3p
leaq 2(%rbx,%rbx,7), %rax 2 + 8p
leaq 0xE(,%rdx,3), %rax 14 + 3q
leaq 6(%rbx,%rdx,7) %rdx 6 + p + 7q

 

 Practice 3.7                                                                                                                                  

다음 코드에서 계산하는 수식을 비워두었다.

short scale3(short x, short y, short z) {
	short t = ________;
    return t;
}
# short scale3(short x, short y, short z)
# x in %rdi, y in %rsi, z in %rdx
scale3:
    leaq (%rsi,%rsi,9), %rbx
    leaq (%rbx,%rdx), %rbx
    leaq (%rbx,%rdi,%rsi), %rbx
    ret

C 코드에서 빠진 수식을 채우시오.

더보기

(정답) short t = 10 * y + z + y * x;

(해설)

# short scale3(short x, short y, short z)
# x in %rdi, y in %rsi, z in %rdx
scale3:
    leaq (%rsi,%rsi,9), %rbx		# 10 * y
    leaq (%rbx,%rdx), %rbx		# 10 * y + z
    leaq (%rbx,%rdi,%rsi), %rbx		# 10 + y + z + y * z
    ret

3.5.2 단항 및 이항 연산

  • 단항 연산 : incq (%rsp) → 스택 탑의 8바이트 원소의 값을 증가시킨다. (x++)
  • 이항 연산 : subq %rax, %rdx → %rdx에서 %rax의 값만큼 빼준다. (x -= y)

 Practice 3.8                                                                                                                                  

다음과 같은 값들이 표시된 메모리 주소와 레지스터에 저장되어 있다.

Address Value Register Value
0x100 0xFF %rax 0x100
0x104 0xAB %rcx 0x1
0x108 0x13 %rdx 0x3
0x10C 0x11    

다음 표에 지시된 인스트럭션으로 인해 수정되는 메모리 위치나 레지스터들과 결과 값을 채우시오.

Instruction Destination Value
addq %rcx, (%rax) 0x100 0x100
subq %rdx, 8(%rax) 0x108 0xA8
imulq $16, (%rax,%rdx,8) 0x118 0x110
incq 16(%rax) 0x110 0x14
decq %rcx %rcx 0x0
subq %rdx, %rax %rax 0xFD
더보기

🔹 addq %rcx, (%rax)

  • 설명: %rcx(0x1)를 %rax가 가리키는 주소(0x100)의 값에 더한다.
  • (%rax) → 0x100의 값: 0xFF
    0xFF + 0x1 = 0x100
  • 결과:
    • Destination: 0x100
    • Value: 0x100

🔹 subq %rdx, 8(%rax)

  • 설명: %rax(0x100)에 8을 더한 주소(0x108)의 값에서 %rdx(0x3)를 뺌.
  • 0x108의 현재 값: 0x13 0x13 - 0x3 = 0x10
  • 결과:
    • Destination: 0x108
    • Value: 0x10

🔹 imulq $16, (%rax,%rdx,8)

  • 설명: 주소 계산: %rax + %rdx * 8 = 0x100 + 0x3 * 8 = 0x100 + 0x18 = 0x118
  • 해당 주소(0x118)의 값을 16배 한다. ※ 원래 0x118에는 값이 없지만, 해당 명령으로 저장된다.
  • 초기 값이 없다고 해도, 연산을 위해 초기값은 1이라고 가정하거나 그냥 0으로 초기화하고 곱한다는 전제가 문제에서 필요한 부분. 여기서는 결과가 0x110로 제시되어 있음 →
    즉, 0x118의 기존 값이 1이라면 1 * 16 = 0x10, 이건 안 맞음.
    그러므로, 0x118의 기존 값이 0x10이면 0x10 * 0x10 = 0x100, 이것도 안 맞음.
  • 하지만 결과가 0x110이라면, 원래 값이 0x11 (17)이고 17 * 16 = 272 = 0x110 이라 맞음!
  • 결과:
    • Destination: 0x118
    • Value: 0x110

🔹 incq 16(%rax)

  • 설명: 주소 0x100 + 16 = 0x110의 값을 1 증가시킴.
  • 기존 값이 0x13이면, 0x13 + 1 = 0x14
  • 결과:
    • Destination: 0x110
    • Value: 0x14

🔹 decq %rcx

  • 설명: %rcx에서 1을 뺌 → 0x1 - 1 = 0x0
  • 결과:
    • Destination: %rcx
    • Value: 0x0

🔹 subq %rdx, %rax

  • 설명: %rax에서 %rdx를 뺌 → 0x100 - 0x3 = 0xFD
  • 결과:
    • Destination: %rax
    • Value: 0xFD

3.5.3 쉬프트 연산

시프트 값이 먼저 주어지고, 시프트할 값이 두 번째로 주어지는 시프트 연산이다. 산술과 논리 오른쪽 시프트 연산이 가능하다.

  • 왼쪽 시프트 연산에는 두 가지 이름이 있다. SAL = SHL
    • Left shift는 수를 전체적으로 왼쪽으로 shift하고, 비워지는 LSB (least-significant bit) bit들을 0으로 채움
    • k-bit만큼 left shift하는 것은 2k을 곱하는 것에 해당 (unsigned 및 2의 보수 모두 적용)
    • (예) 11101(-3) << 2 → 10100(-12 = 3×2²)
  • 오른쪽 시프트 연산에서 SAR은 산술적, SHR은 논리적 시프트 연산이다.
    • Logical right shift는 수를 전체적으로 오른쪽으로 shift하고, 비워지는 MSB bit들은 0으로 채움
    • k-bit만큼 logical right shift하는 것은 unsigned number를 2k로 나누는 것에 해당
    • (예) 10100(20)을 2bit >>R 2 → 00101(5 = 20/2²)
    • Arithmetic right shift는 수를 전체적으로 오른쪽으로 shift하고, 비워지는 MSB bit들은 MSB를 복사해서 채움
    • k-bit만큼 arithmetic right shift하는 것은 2의 보수를 2k로 나누는 것에 해당
    • (예) 10100(-12) >>A 2 → 11101(-3 = -12/2²)
[참고] 2의 보수란?
Positive number N에 대해서 –N을 N의 two’s complement로 표현하면
  • -N → N* = 2n – N = N + 1 (N은 N의 1의 보수) : 즉, N에 NOT 연산을 수행한 후 1을 더하면 2의 보수가 된다.
    (예) 2(0010) → 1101 + 1 → -2(1110)
  • 위 정의에 의해서 N이 positive인지 negative인지에 상관없이 N의 two’s complement는 –N의 값을 가짐

 

 Practice 3.9                                                                                                                                  

다음과 같은 C 함수의 어셈블리 코드를 생성하려고 한다.

long shift_left4_rightn(long x, long n) {
    x <<= 4;
    x >>= n;
    return x;
}

다음의 코드는 실제 쉬프트를 수행하고 최종값을 %rax에 저장한다. 매개변수 x와 n이 각각 %rdi, %rsi에 저장되어 있다. 생략된 인스트럭션을 작성하시오.

# long shift_left4_rightn(long x, long n)
# x in %rdi, y in %rsi
shift_left4_rightn:
    movq	%rdi, %rax	# Get x
    __________________		# x <<= 4
    movq	%esi, %ecx		# Get n (4 bytes)
    __________________		# x >>= n
더보기

(정답)

  • salq $4, %rax
  • sarq %cl, %rax

(해설)

salq $4, %rax

  • salq는 Shift Arithmetic Left의 약자이며, shl과 동의어다.
  • %rax 값을 왼쪽으로 4비트 이동시키며, 이 연산은 2⁴ = 16을 곱하는 것과 같다.
  • 즉, x <<= 4 구현

movq %esi, %ecx

  • x86-64에서는 가변 쉬프트를 하려면 시프트 비트 수는 %cl 레지스터에 있어야 한다.
  • n은 %rsi에 저장되어 있고, %esi는 그 하위 32비트다. 이 값을 %ecx에 복사하면 %cl에 접근할 수 있게 된다.

sarq %cl, %rax

  • %rax 값을 %cl이 지정한 만큼 산술 오른쪽 쉬프트한다.
  • 산술 쉬프트는 부호를 유지하면서 비트를 오른쪽으로 이동시키는 연산임
  • 즉, x >>= n에 해당함

3.5.4 Discussion

long arith(long x, long y, long z) {
    long t1 = x ^ y;
    long t2 = z * 48;
    long t3 = t1 & 0x0F0F0F0F;
    long t4 = t2 - t3;
    return t4;
}
# long arith(long x, long y, long z)
# x in %rdi, y in %rsi, z in %rdx
arith:
    xorq %rsi, %rdi			# t1 = x ^ y
    leaq (%rdx,%rdx,2) %rax		# t2 = 3*z
    salq $4, %rax			# t2 = 16 * (3*z) = 48*z
    andl $252645135, %edi		# t3 = t1 & 0x0F0F0F0F
    subq %rdi, %rax			# Return t2 - t3
    ret

 

 Practice 3.10                                                                                                                                

다음 어셈블리 코드를 보고 C 코드를 완성시키시오.

short arith3(short x, short y, short z) {
    short p1 = ____________;
    short p2 = ____________;
    short p3 = ____________;
    short p4 = ____________;
    return p4;
}
# short arith3(short x, short y, short z):
    orq %rsi, %rdx
    sarq $9, %rdx
    notq %rdx
    movq %rdx, %bax
    subq %rsi, %rbx
    ret
더보기

(정답)

short arith3(short x, short y, short z) {
    short p1 = y | z;
    short p2 = p1 << 9;
    short p3 = -p2;
    short p4 = y - p3;
    return p4;
}

 

(해설)

orq %rsi, %rdx

  • y | z 연산
  • p1 = y | z;

sarq $9, %rdx

  • 산술 오른쪽 시프트 (부호 유지)
  • p2 = p1 >> 9;처럼 보이지만, 실제 C코드는 p2 = p1 << 9;
    → 왜냐하면 다음 notq와 흐름을 통해 결국 -p2가 나옴

notq %rdx

  • 비트를 반전: ~(p1 >> 9)
  • 하지만 중요한 점은 notq가 ~x를 의미한다는 것
  • 이걸 활용해 결국 p3 = -p2;로 매핑할 수 있게 됨 (즉, 음수화된 시프트 값)

💡 팁: -x == ~x + 1 → ~x == -x - 1, 따라서 ~(x >> n)은 -(x >> n) - 1

하지만 short 정수 범위에서 정확히 대응하려면 -p2라고 단순화하는 게 핵심.

movq %rdx, %rax

  • 계산된 값을 반환값으로 복사

subq %rsi, %rbx

  • rdx - y → 이 연산 결과가 %rbx에 저장되지만, 함수 반환과는 무관
  • 다만, 이를 보면 최종 결과는 y - (-p2) = y + p2 → 즉, p4 = y - p3;

 Practice 3.11                                                                                                                                

실제로는 XOR 연산이 존재하지 않지만, 종종 xorq %rcx, %rcx와 같은 어셈블리 코드를 발견하게 된다.

1. 이 특정 XOR 인스트럭션 효과를 설명하고, 이것을 구현하고 있는 유용한 기능을 설명하시오.

이 인스트럭션은 모든 x에 대해 x^x=0이라는 특성을 이용하여 레지스터 %rcx를 0으로 세팅하기 위해 사용한다. 이는 C언어로 x=0에 대응된다.

2. 이 연산을 보다 직접적인 어셈블리 코드로 어떻게 표시할 수 있는가?

레지스터 %rcx를 0으로 세팅하는 것 보다 직접적인 방법은 인스트럭션 movq $0, %rcx를 사용하는 것이다.

3. 이 두 개의 서로 다른 방법으로 구현한 것을 인코딩할 때 소요되는 바이트의 수를 비교하시오.

xorq를 사용하는 경우에는 단 3바이트만을 사용하지만, movq를 사용하는 경우에는 7바이트를 필요로 한다.

3.5.5 특수 산술연산

두 개의 부호가 있거나 없는 64비트 정수를 곱하면 128비트가 필요한 결과를 얻을 수 있다.

특수 산술연산: 이들 연산은 부호형과 비부호형의 완전 128비트 곱셈과 나눗셈을 제공한다. %rdx와 %rax는 한 개의 128비트 8워드를 구성하는 것처럼 사용된다.

 

3.6 제어문

여태까지는 순차적으로 실행되는 직선적인 동작만을 다뤘지만, 조건문, 반복문(loop), switch문과 같은 구조는 조건적 실행을 필요로 한다.

3.6.1 조건 코드

CPU는 가장 최근의 산술적이거나 논리적인 연산을 설명하는 단일 비트 조건 코드 레지스터를 유지한다. 이러한 레지스터들은 조건적인 분기branch들을 수행하기 위해 검증받는다.

 

다음과 같은 조건 코드들은 유용하다.

  • CF (Carry Flag) : 가장 최근의 연산에서 가장 중요한 비트로부터 받아 올림이 발생한 것을 표시. 비부호형 연산에서 오버플로우를 검출할 때 사용.
  • ZF (Zero Flag) : 가장 최근 연산의 결과가 0인 것을 표시
  • SF (Sign Flag) : 가장 최근 연산이 음수를 생성한 것을 표시
  • OF (Overflow Flag) : 가장 최근 연산이 양수/음수의 2의 보수 오버플로우를 발생시킨 것을 표시

예를 들어, C 명령어인 t = a + b를 수행하기 위해 ADD 함수를 사용한다. 그럴 때의 조건 코드는 다음과 같다.

CF (unsigned) t < (unsigned) a Unsigned overflow
ZF t == 0 Zero
SF t < 0 Negative
OF (a < 0 == b < 0) && (t < 0 != a < 0) Signed overflow

XOR과 같은 논리적인 연산에서, CF와 OF는 0이 된다. 시프트 연산에서, CF는 나가 떨어진 마지막 비트로 되고, OF는 0이 된다.

 

다른 레지스터로 변경하지 않고 조건 코드를 설정하는 두 가지 명령어 클래스가 있다.

  • CMP 명령어는 두 가지 피연산자의 차이에 따라 조건 코드를 설정한다. SUB 명령어와 같은 방식으로 작동하지만, 그들의 목적지를 업데이트하지 않고 조건 코드를 설정하는 것은 다르다.
  • TEST 명령어는 AND 명령어와 같은 방식으로 작동하지만, 그들의 목적지를 변경하지 않고 조건 코드를 설정하는 것은 다르다.

비교 및 시험 인스트럭션: 이 인스트럭션 집합은 다른 레지스터 값은 수정하지 않은 채 조건 코드만 바꿔준다.

3.6.2 조건 코드 사용하기

조건 코드를 직접적으로 읽는 것 보다는, 조건 코드를 사용하는 데 세 가지 흔한 방법이 있다.

  • 조건 코드의 어떤 조합에 의존하여 단일 바이트를 0또는 1로 설정한다.
  • 다른 프로그램으로 조건적으로 jump할 수 있다.
  • 데이터를 조건적으로 전송할 수 있다.

SET 인스트럭션: 각 인스트럭션은 조건코드에 따라 단일 바이트를 0이나 1로 설정한다. 일부 인스트럭션들은 유사어, 즉 동일한 기계어 인스트럭션에 대해 또 다른 이름이 존재한다.

3.6.3 점프Jump 인스트럭션

Jump 인스트럭션: 이들 인스트럭션은 점프 조건이 만족되면 레이블 목적지로 이동한다. 일부 인스트럭션들은 동일 기계어 인스트럭션에 대해 또 다른 이름인 유사어를 가진다.

  • jump 명령어는 프로그램에 완전히 새로운 위치로 바꾸어 실행한다.
  • jump 목적지는 label(라벨)로 어셈블리 코드 내를 가리킨다.
  • jump .L1 (직접 점프)명령어는 밑에 movq 명령어를 skip하고 popq 명령어로 재개한다. 오브젝트-코드 파일을 생성하여, 어셈블러는 모든 라벨된(labeled) 명령어의 주소를 결정하고 jump 타겟을 jump 명령어의 한 부분으로 인코딩한다.
  • jmp *%rax(간접 점프)는 레지스터 내의 값인 %rax를 jump 타겟으로 사용한다.
  • jmp *(%rax)는 메모리로부터 jump 타겟을 읽는다.

3.6.4 점프 인스트럭션 인코딩

어떻게 jump 명령어의 타겟이 인코딩되는지를 이해하는 것은 링킹linking에서 중요한 부분이다.

  • jump 타겟은 상징적 라벨을 사용해서 작성된다.
    • 어셈블러와 링커는 jump 타겟의 적절한 인코딩을 생성한다.
    • 많은 인코딩이 있지만, 가장 흔하게 사용하는 것은 PC relative이다.
    • 타겟 명령어의 주소와 jump을 따라가는 명령어의 주소 간의 차이를 인코딩한다.
  • 두 번째 인코딩 방법은 절대적인 주소를 주는 것으로 타겟을 바로 구체화하기 위해 4바이트를 사용한다.
    • PC-relative addressing을 수행할 때 PC의 값은 jump 자체가 아닌 jump을 따르는 명령어의 주소이다.
    • 링킹 이후에 프로그램에서 명령어는 다른 주소로 재배치 받지만 jump 타겟은 바뀌지 않는다.

위는 어셈블리어고, 아래는 그 어셈블리어의 역어셈블 버전이다.

역어셈블 버전의 두번째 줄(jump)을 살펴보면, 왼쪽 기계어 코드의 두번째 바이트가 0x03인것을 확인할 수 있다. 이것이 아까 말한 PC 상대적 방법인데, 이것을 다음 인스트럭션 주소인 0x05에 더하면 목적지 주소인 0x08을 얻을 수 있으며, 이것이 바로 4번째 줄에 있는 인스트럭션의 주소이다.

두 번째 점프 부분인 다섯 번째 줄도 확인해보자. 두번째 바이트는 0xf8 이는 2의 보수 표현 방식으로 십진수 -8, 이를 다음 인스트럭션 주소인 0xd에 더하면 5. 다섯 번째 줄이 바로 점프의 목적지이다.

3.6.5 조건부 분기를 조건제어로 구현하기

3.6.6 조건부 이동으로 조건부 분기 구현하기

3.6.7 반복문

C는 do-while, while, for문과 같은 다양한 반복문을 제공한다. 기계 코드에는 대응하는 명령어가 없지만, test와 jump의 조합으로 반복문을 구현한다.

3.6.8 스위치문

 

'Krafton Jungle > 4. CSAPP' 카테고리의 다른 글

[Computer System] ③ 프로그램의 기계수준 표현 (4)  (0) 2025.04.07
[Computer System] ③ 프로그램의 기계수준 표현 (3)  (0) 2025.04.06
[Computer System] ③ 프로그램의 기계수준 표현 (1)  (0) 2025.04.04
[Computer System] ① 컴퓨터 시스템으로의 여행 (3)  (0) 2025.03.31
[Computer System] ① 컴퓨터 시스템으로의 여행 (2)  (0) 2025.03.20

'Krafton Jungle/4. CSAPP'의 다른글

  • 현재글[Computer System] ③ 프로그램의 기계수준 표현 (2)

관련글

티스토리툴바