[TIL/크래프톤 정글] DAY 27

배재준·2025년 4월 5일

8기 TIL krafton jungle week04 컴퓨터 시스템

크래프톤 정글 - TIL

목록 보기

20/93

2025.04.05

TIL(TODAY I LEARN)

WEEK04 :
동적 프로그래밍, 그리디 알고리즘
CSAPP 3장. 프로그램의 기계 수준 표현 (특히 3.4, 3.7, 3.8)
3.4 ~ 3.5 까지 공부
목표는 3.6 까지 였는데 생각보다 내용이 엄청많다.. 부랴 부랴 하는중!

3.4 정보 접근하기

x86-64 중앙처리장치(CPU)는 64-비트 값을 저장하는 16개의 범용(general-purpose) 레지스터를 포함한다. 이 레지스터들은 정수 데이터와 포인터를 저장한다.
레지스터들의 이름은 %r로 시작하고 뒤에는 다른 이름들을 가지고 있다.

%rax, %rbp, %rsp, %r8~%r15 이런 식

명령어는 16개 레지스터의 낮은 정렬에 있는 바이트에 저장되어 있는 다른 사이즈의 데이터에 대해 연산한다. 바이트 수준 연산은 최하위 비트에 접근한다. (16-비트 연산은 최하위 2바이트, 32비트는 4비트, 64-비트는 모든 레지스터에 접근한다.)
- %rax ← 전체
- %eax = 하위 32비트
- %ax = 하위 16비트
- %al = 하위 8비트
다른 레지스터들은 프로그램에서 다른 역할을 제공한다. 가장 유일한 것은 스택 포인터(stack pointer)로 %rsp이며, 런타임 스택에서 마지막 위치를 가리키는 데 사용된다. 어떤 명령어는 이 레지스터를 읽거나 쓸 때가 있다. 다른 15개의 레지스터들은 그들의 사용에서 유연함을 가진다.
표준 프로그래밍 기준은 어떻게 레지스터가 스택을 관리하는 지, 함수 매개변수를 어떻게 넘기는 지, 함수로부터 값을 반환하는지, 지역과 임시 데이터를 저장하는 지에 대해 결정한다.

정리

CPU에는 16개의 64비트 레지스터가 있고, 그 일부만 쓸 수도 있음.

%rsp는 스택의 꼭대기를 가리키며, 레지스터 사용은 프로그래밍 규약에 따라 정해져 있음.

3.4.1 오퍼랜드 식별자 (operand Specifiers)

용어	뜻
피연산자(Operand)	명령어가 연산할 "값" 또는 "주소"
소스(Source)	값을 가져오는 곳
목적지(Destination)	결과를 저장하는 곳

Immediate (즉시 값)

그냥 숫자 상수
예: $5, $0x10 (앞에 $ 붙임)
명령어 안에 바로 박혀 있는 값

Register (레지스터)

CPU 안의 저장소 (예: %rax, %rbx)
그냥 레지스터 이름으로 사용

Memory (메모리 참조)

메모리에 저장된 값을 접근할 때
괄호 안에 주소 계산 공식이 들어감: Imm(rb, ri, s)
표기 방식: offset(%base, %index, scale)

주소 = 기준 주소 + 인덱스 * 크기

3.4.2 데이터 이동 인스트럭션

데이터를 "다른 위치로 복사"한다는 건, 메모리 접근 또는 레지스터 조작이 필요하다는 뜻 → 무거운 명령어

메모리 ↔ 메모리, 메모리 ↔ 레지스터 간 복사

CPU 입장에서 시간이 오래 걸리고
전력 소모도 크고,
파이프라인 지연도 발생할 수 있어서 "무겁다"고 표현

MOV 계열 명령어는 “데이터 이동만 수행”하는 명령어 그룹

소스 → 목적지 복사

연산 X, 조건 X, 단순히 "값을 복사"만 함

값을 한 위치에서 다른 위치로 복사하는 것은 두 가지 명령어를 요구

소스 값을 레지스터에 로드(load)하는 것

목적지에 레지스터 값을 쓰는(write) 것

movl만의 특별한 규칙
- 레지스터를 목적지로 갖는 경우 → 레지스터 상위 4바이트 0으로 설정됨
MOVZ / MOVS
- 작은 크기 → 큰 크기로 올릴 때 사용

`movz` = Zero Extension

→ 빈 부분을 0으로 채움 (양수 취급)

movzbq %al, %rax

8비트 → 64비트, 상위는 0으로 채움

`movs` = Sign Extension

→ 빈 부분을 부호(양/음수) 에 따라 채움

movsbq %al, %rax

8비트 → 64비트, 상위는 부호 따라 채움

MOV 명령어는 단순 복사를 위한 핵심 명령어지만,

크기, 부호 확장, immediate 제한 등 예외가 많고 섬세한 규칙이 다수

movl은 레지스터 상위 0으로 채움

movq는 64비트 즉시 값 제한됨

movabsq는 큰 숫자도 OK

movz, movs는 크기 확장

3.4.3 데이터 이동 예제

C언어에서 "포인터"라고 부르는 것이 어셈블리어에서는 단순히 주소임.
1. 포인터를 역참조하는 것은 포인터를 레지스터에 복사하고, 이 레지스터를 메모리 참조에 사용하는 과정으로 이루어짐.
x 같은 지역변수들은 메모리에 저장되기보다는 종종 레지스터에 저장된다.
1. 레지스터의 접근은 메모리보다 속도가 훨씬 더 빠르다.

3.4.4 스택 데이터의 저장과 추출(push, pop)

1. 스택(Stack)은 메모리의 특정 영역을 차지한다

운영체제는 스택을 위한 메모리 공간을 따로 잡아준다.
스택은 로컬 변수, 함수 호출 정보, 레지스터 백업 등을 저장할 때 사용.

2. 스택은 "위에서 아래로" 쌓인다 (감소 방향)

스택은 메모리 주소상 높은 주소 → 낮은 주소 방향으로 자라남.
즉, 새 값을 푸시(push)하면 → 주소가 작아짐.

3. 스택 포인터 `%rsp`는 현재 스택의 top 주소를 가리킨다

%rsp는 항상 스택의 최상단(top) 을 가리킴
스택에 뭘 넣든 꺼내든, 기준점은 항상 %rsp

4. push (스택에 저장)

pushq %rax

내부 동작:

%rsp를 8만큼 줄임 (%rsp = %rsp - 8)
줄어든 주소에 %rax 값을 저장

→ 왜 8?

→ x86-64는 64비트(=8바이트) 환경이기 때문!

5. pop (스택에서 꺼내기)

popq %rax

내부 동작:

%rsp가 가리키는 주소의 값을 %rax에 저장
%rsp를 8만큼 증가시킴 (%rsp = %rsp + 8)

✔️ 메모리 자체는 변하지 않음

→ 다만 %rsp가 옮겨가면서 더 이상 "스택의 top"이 아닌 상태가 되는 것!

6. 꺼낸 값은 어디 갔냐?

→ 메모리에 여전히 남아 있다!

다만, %rsp가 다른 위치를 가리키기 때문에 "스택에서 제거된 것처럼" 보일 뿐

다음에 push를 하면 그 주소에 새 값이 덮어써질 수 있음

3.5 산술연산과 논리연산

연산자 종류

연산자들은 4가지 그룹으로 나뉨:

그룹	예시	특징
Load effective address	`leaq`	산술 연산에 자주 사용됨
Unary (1개의 피연산자)	`inc`, `dec`, `neg`, `not`
Binary (2개의 피연산자)	`add`, `sub`, `imul`, `xor`, `or`, `and`
Shift 연산	`shl`, `shr`, `sar`, `sal`	비트 단위 이동

3.5.1 유효주소 적재(Load Effective Address)

leaq 명령어
- 원래는 "주소를 계산해서 레지스터에 저장"하는 명령어
- 실제로는 산술 계산에도 많이 쓰임.

leaq 7(%rdx,%rdx,4), %rax

⇒ %rdx + (4 * %rdx) + 7로 산술 계산이 가능

3.5.2 단항 및 이항 연산

단항 연산
- 하나의 오퍼랜드가 소스와 목적지로 동시에 사용
- C의 ++,-- 와 비슷
이항 연산
- 두번째 오퍼랜드가 소스이면서 목적지로 사용됨
- C의 x -= y 와 비슷
- %rdx = %rdx - %rax (소스 먼저, 목적지 나중)
- 목적지는 레지스터나 메모리
- 둘 다 메모리는 안 됨 (한쪽은 반드시 레지스터/상수 값)

3.5.3 시프트 연산

명령어	의미	채우는 방식
`shl` / `sal`	왼쪽 시프트	오른쪽에 0 채움 (동일한 동작)
`shr`	오른쪽 논리 시프트	왼쪽에 0 채움
`sar`	오른쪽 산술 시프트	왼쪽에 부호 비트 복사

shl/sar/shr $<count>, <dest> # 상수값(count)만큼 (dest)를 시프트 shl/sar/shr %cl, <dest> # %cl (8비트 레지스터) 사용

최대 시프트 횟수는

salb (8비트): %cl의 하위 3비트 → 최대 7
salw (16비트): 하위 4비트 → 최대 15
sall (32비트): 하위 5비트 → 최대 31
salq (64비트): 하위 6비트 → 최대 63

시프트 횟수는 데이터 크기에 따라 제한됨

3.5.4 토의

대부분의 인스트럭션들은 비부호형과 2의 보수 산술연산에 사용될 수 있다.

== 어셈블리 명령어 자체는 부호 여부를 따지지 않고 단순히 비트 계산만 한다는 뜻

우측 시프트 연산만 부호형, 비부호형 데이터를 구분함.
컴퓨터는 비트 단위 계산만을 할 뿐

3.5.5 특수 산술연산

128비트 곱셈: mulq / imulq

64비트 × 64비트 = 최대 128비트 결과 필요
그래서 x86-64는 %rax × S → 결과는 %rdx:%rax 조합에 저장

명령어	의미	부호 여부
`mulq S`	%rax × S → 128비트 저장	unsigned
`imulq S`	%rax × S → 128비트 저장	signed

반드시 %rax가 첫 번째 곱셈 피연산자여야 함

128비트 나눗셈: divq / idivq

128비트 수 ÷ 64비트 수 = 몫과 나머지
입력: %rdx:%rax = 128비트 숫자(레지스터 두개 이어붙임)
결과:
- 몫: %rax
- 나머지: %rdx

명령어	설명	부호
`idivq S`	signed 나눗셈	부호 확장 필요 (`cqto`)
`divq S`	unsigned 나눗셈	%rdx를 0으로 초기화 필요

개념	설명
128비트 곱셈	`mulq`(unsigned), `imulq`(signed), 결과는 `%rdx:%rax`
128비트 나눗셈	`divq`(unsigned), `idivq`(signed), 입력도 `%rdx:%rax`
부호 확장	`cqto` (signed), `xor %rdx,%rdx` (unsigned 초기화)

~3.5 윤성원의 컴퓨터 시스템 특강

레지스터
레지스터 이름 의미
rax 함수 반환값 저장
rdi,rds,rdx,rcx … 함수 인자(파라미터) 저장
rsp stack top
rbp stack base(데이터의 바닥)
메모리 주소 지정 방법들
- ex) movq $10
  - $10 : 즉시 주소 시정 : 바이트로 상수 바로 씀
- movq 주소
  - 주소 : 직접 주소 지정 : 바로 주소 써놨다.
- 간접 주소 지정 4가지 + 1가지
  - 레지스터 직접 주소 지정
    - ex) movq %rax, %rbx : 레지스터 안에 값 바로
  - 레지스터 간접 주소 지정
    - movq %rax, (%rbx) : 레지스터 안에 주소의 값으로
  - 베이스 레지스터 간접 주소 지정
    - movq offset(%bp) , %rax : offset 만큼 이동해서 갖고와
  - 인덱스 레지스터 간접 주소 지정
    - movq ARRAY(%bp) , %rax : 어셈블리 배열의 첫 시작 부분을 인덱스로
  - 베이스 인덱스 간접 주소 지정
    - movq ARRAY(%bp, offset) , %rax : 배열의 offset 부분부터 갖고 오겠다.

레지스터 이름	의미
rax	함수 반환값 저장
rdi,rds,rdx,rcx …	함수 인자(파라미터) 저장
rsp	stack top
rbp	stack base(데이터의 바닥)

백준 잔디는 매일 심어야 한다. CSAPP을 하니까 문제가 풀고싶더라.

11047 - 동전0 - 실버4

문제 링크 - https://www.acmicpc.net/problem/11047

내 코드

   import sys
   
   input = sys.stdin.readline
   
   n,k = map(int,input().split())
   A = []
   for _ in range(n):
       A.append(int(input().strip()))
       
   
   cnt = 0
   for i in A[::-1]:
       if k == 0:
           break
       if k < i:
           continue
       else:
           cnt += k // i
           k = k % i
   print(cnt)

문제 분류

그리디 알고리즘

CSAPP 3장을 일주일 만에 다 읽고 이해하라는건 너무 빡세다. 오늘도 내일도 화이팅

배재준

^_^

이전 포스트

[TIL/크래프톤 정글] DAY 26

다음 포스트

[TIL/크래프톤 정글] DAY 27

크래프톤 정글 - TIL

TIL(TODAY I LEARN)

3.4 정보 접근하기

3.4.1 오퍼랜드 식별자 (operand Specifiers)

3.4.2 데이터 이동 인스트럭션

`movz` = Zero Extension

8비트 → 64비트, 상위는 0으로 채움

`movs` = Sign Extension

8비트 → 64비트, 상위는 부호 따라 채움

3.4.3 데이터 이동 예제

3.4.4 스택 데이터의 저장과 추출(push, pop)

1. 스택(Stack)은 메모리의 특정 영역을 차지한다

2. 스택은 "위에서 아래로" 쌓인다 (감소 방향)

3. 스택 포인터 `%rsp`는 현재 스택의 top 주소를 가리킨다

4. push (스택에 저장)

5. pop (스택에서 꺼내기)

6. 꺼낸 값은 어디 갔냐?

3.5 산술연산과 논리연산

연산자 종류

3.5.1 유효주소 적재(Load Effective Address)

3.5.2 단항 및 이항 연산

3.5.3 시프트 연산

최대 시프트 횟수는

3.5.4 토의

3.5.5 특수 산술연산

~3.5 윤성원의 컴퓨터 시스템 특강

11047 - 동전0 - 실버4

문제 링크 - https://www.acmicpc.net/problem/11047

내 코드

문제 분류

[TIL/크래프톤 정글] DAY 26

[TIL/크래프톤 정글] DAY 28

0개의 댓글

[TIL/크래프톤 정글] DAY 27

크래프톤 정글 - TIL

TIL(TODAY I LEARN)

3.4 정보 접근하기

3.4.1 오퍼랜드 식별자 (operand Specifiers)

3.4.2 데이터 이동 인스트럭션

movz = Zero Extension

8비트 → 64비트, 상위는 0으로 채움

movs = Sign Extension

8비트 → 64비트, 상위는 부호 따라 채움

3.4.3 데이터 이동 예제

3.4.4 스택 데이터의 저장과 추출(push, pop)

1. 스택(Stack)은 메모리의 특정 영역을 차지한다

2. 스택은 "위에서 아래로" 쌓인다 (감소 방향)

3. 스택 포인터 %rsp는 현재 스택의 top 주소를 가리킨다

4. push (스택에 저장)

5. pop (스택에서 꺼내기)

6. 꺼낸 값은 어디 갔냐?

3.5 산술연산과 논리연산

연산자 종류

3.5.1 유효주소 적재(Load Effective Address)

3.5.2 단항 및 이항 연산

3.5.3 시프트 연산

최대 시프트 횟수는

3.5.4 토의

3.5.5 특수 산술연산

~3.5 윤성원의 컴퓨터 시스템 특강

11047 - 동전0 - 실버4

문제 링크 - https://www.acmicpc.net/problem/11047

내 코드

문제 분류

[TIL/크래프톤 정글] DAY 26

[TIL/크래프톤 정글] DAY 28

0개의 댓글

`movz` = Zero Extension

`movs` = Sign Extension

3. 스택 포인터 `%rsp`는 현재 스택의 top 주소를 가리킨다