[CSAPP] 2.1 정보의 저장(Ch. 2 정보의 표현과 처리)

2.1 정보의 저장

• 기계수준의 프로그램은 메모리를 '가상메모리(virtual memory)'로 부르는 거대한 바이트의 배열로 취급.
• 메모리의 각 바이트는 주소로 식별할 수 있고, 모든 가능한 주소의 집합을 '가상 주소공간(virtual address space)'이라 부름(이는 기계수준 프로그램에게 제공되는 개념적인 이미지).

---

2.1.1 16진수 표시

• C에서 0x나 0X로 시작하는 숫자 상수는 16진수로 해석. 'A'에서 'F'까지 대소문자 모두, 혼용 여부에 상관없이 16진수 자릿수로 해석(ex. 0xFA1D37B == 0xfa1d37b == 0xFa1D37b)

Hex digit	0	1	2	3	4	5	6	7
Decimal value	0	1	2	3	4	5	6	7
Binary value	0000	0001	0010	0011	0100	0101	0110	0111
Hex digit	8	9	A	B	C	D	E	F
Decimal value	8	9	10	11	12	13	14	15
Binary value	1000	1001	1010	1011	1100	1101	1110	1111

• $x = 2^n$이면($n$은 음수가 아닌 정수) 쉽게 16진수로 변환할 수 있다. $n$을 $i + 4j$, $0 \leq i \leq 3$로 표시할 수 있으면, $x$는 앞에 16진수 $1(i = 0)$, $2(i = 1)$, $4(i = 2)$, $8(i = 3)$을 쓰고 그 뒤에 $j$개의 0을 쓰면 된다. (ex. $x = 2048= 2^11$이면, $n = 11 = 3 + 4 \cdot 2$로 16진수 0x800이 된다.)
• 나머지 변환은 다들 생각하는 대로 하면..

---

2.1.2 데이터의 크기

• 모든 컴퓨터는 '워드 크기(word size)'를 규격으로 가짐.
• 하나의 가상 주소가 한 개의 워드로 인코딩되므로 포인터의 정규 크기를 의미하게 된다.
• 따라서 워드 크기에 따라 '가상 주소 공간'의 최대 크기가 결정된다.
• ex) $\omega$비트 워드 크기의 컴퓨터는 $0$에서 $2^\omega - 1$의 가상주소 범위를 가지고, 프로그램은 $2^\omega$바이트에 접근할 수 있게 됨
• 32비트 워드 크기는 가상 주소공간의 크기를 $4 \times 10^9$바이트를 조금 넘는, 4GB로 표시되는 크기로 한정.
• 64비트 워드 크기는 16엑사바이트(Exabyte), $1.84 \times 10^{19}$바이트의 가상 주소공간으로 한정.
• 비트에 따라서 일반적으로 데이터 타입들에 할당되는 바이트 수는 조금씩 다른 경우가 많다.
• 다음 표는 C에서 숫자 데이터 타입들의 크기

C declaration		Bytes
Signed	Unsigned	32-bit	64-bit
[signed] char	unsigned char	1	1
short	unsigned short	2	2
int	unsigned	4	4
long	unsigned long	4	8
int32_t	uint32_t	4	4
int64_t	uint64_t	8	8
char *		4	8
float		4	4
double		8	8

---

2.1.3 주소지정과 바이트 순서

• 여러 바이트에 프로그램 객체(program objects)를 저장할 때 '객체의 주소를 무엇으로 할지', '메모리에 바이트를 어떻게 정렬할지' 두 가지를 정해야 한다.
• 일반적으로 멀티 바이트 객체는 '연속된 바이트'에 저장하고 객체 주소는 저장된 '가장 앞 메모리의 주소'로 한다.

어떤 객체를 표현하는 바이트를 정렬하는 데에는 'Big endian'방식과 'Little endian'방식이 존재한다.

$\omega$-비트 정수가 $[x_{\omega - 1}, x_{\omega - 2}, \cdots , x_1, x_0 ]$를 갖는다고 하자.

그러면 $x_{\omega - 1}$은 '가장 중요한 비트(most significant bit)'라 하고 $x_0$은 가장 덜 중요한 비트라 한다.

$\omega$가 8의 배수이면 비트들을 바이트로 나눌 수 있고, 가장 중요한 바이트는 $[x_{\omega - 1}, x_{\omega - 2}, \cdots , x_{\omega - 8} ]$을 비트들로 가지고, 가장 덜 중요한 바이트는 $[x_7, x_6, \cdots , x_0]$을 비트들로 갖는다.

• 가장 중요한 바이트부터 저장하는 관습을 'Big endian' / 가장 덜 중요한 바이트부터 저장하는 관습을 'Little endian'이라 한다.

int형 변수 x가 주소 0x100에 있고, 16진수값 0x01234567을 갖는다고 가정하면,

Big endian의 경우 0x100에 01, 0x101에 23, 0x102에 45, 0x103에 67을 저장.

Little endian은 0x100에 67, 0x101에 45, 0x102에 23, 0x103에 01을 저장.

바이트 순서를 볼 수 있는 첫번째 경우는 네트워크를 통해 이진 데이터가 다른 컴퓨터로 옮겨질 때.

이를 막기 위해 네트워크 응용프로그램으로 작성된 코드는 송신 컴퓨터가 내부 표시를 네트워크 표준으로 변경하고, 수신 컴퓨터가 네트워크 표준을 내부 표시방식으로 변환하는 방식을 따른다(11장에서 살펴볼 것)

두번째 경우는 정수 데이터를 표시하는 바이트를 볼때.

이는 기계수준 프로그램을 볼 때 종종 신경써야 한다.

세번째 경우는 프로그램이 정상적 타입 체계를 회피하도록 작성되었을 때.

C에서는 '캐스트(cast)'나 '유니온(union)'을 사용하는 경우 객체가 만들어졌을 때와 다른 타입의 데이터로 볼 수 있게 된다.(show-bytes.c 참고)

---

2.1.4 스트링의 표시

C에서 스트링은 널 문자로 종료하는 문자열로 인코딩됨.

show_bytes("12345", 6)을 실행하면 31 32 33 34 34 00을 출력.

cf) 십진수 숫자 x에 해당하는 아스키 코드가 0x3x이다.

아스키를 문자코드로 사용하는 모든 컴퓨터에서 바이트 순서나 워드 크기와 무관하게 똑같이 얻을 수 있으므로 텍스트 데이터가 이진 데이터보다 플랫폼에 독립적이라 할 수 있다.

cf) 'a'에서 'z'까지의 문자는 아스키 코드로 0x61에서 0x7A 사이의 값을 갖는다.

---

2.1.5 코드의 표현

int sum(int x, int y) {
    return x + y;
   }

위 코드를 다음 각각의 컴퓨터에서 컴파일하면 다음과 같은 바이트 표시의 기계어 코드를 생성.

Linuex 32 55 89 e5 8b 45 0c 03 45 08 c9 c3

Windows 55 89 e5 8b 45 0c 03 45 08 5d c3

Sun 81 c3 e0 08 90 02 00 09

Linux 64 55 48 89 e5 89 7d fc 89 75 f8 03 45 fc c9 ce

서로 다른 컴퓨터 타입은 다르고 호환되지 않는 인스트럭션과 인코딩을 사용한다.

동일한 프로세서여도 운영체제가 다른 경우 코딩 관습에 차이가 있고 바이너리 호환성을 갖지 못함.

- 이진 코드는 컴퓨터와 운영체제들 사이에서 호환성 갖는 경우가 드묾.

---

2.1.6 Bool 대수

[Boolean algebra]

• ~ : NOT(￢) (if p = 0, then ~p = 1)
• & : AND(∧) (if p = 1 and q = 1, then p&q = 1)
• | : OR(∨) (if p = 1 or q = 1, then p|q = 1)
• ^ : EXCLUSIVE-OR( = XOR)(⊕) (if (p = 1 or q = 1) and (not both equal to 1), then p^q = 1)

[비트 연산]

비트 벡터 $a$와 $b$. $a = [a_{\omega - 1}, a_{\omega - 2}, \cdots, a_0]$, $b = [b_{\omega - 1}, b_{\omega - 2}, \cdots, b_0]$.

$a\&b$는 길이가 $\omega$인 비트 벡터로 $i$번째 원소는 $0 \leq i \leq \omega$인 $i$에 대해 $a_i \& b_i$로 정의할 수 있음.

ex) $\omega = 4$, $a = [0110], b = [1100]$인 경우,

• $a\&b =  0100  \& 1100 = 0100$
• $a|b = 0100 | 1100 = 1100$
• $a \hat{} b = 0100 \hat{} 1100 = 1010 $
• $ \sim b = \sim1100 = 0011$

cf) $ \&$연산은 $|$연산에 대해 분배법칙이 성립하며, 그 역도 성립

    $a\&(b|c) = (a\&b) |(a \&c)$

    $a|(b\&c) = (a | b) \& (a|c)$

 

비트 벡터를 통해 유한집합을 나타낼 수 있다.

$i \in A$이면 언제나 $a_i = 1$인 비트 벡터 $[a_{\omega - 1}, \cdots , a_1, a_0 ]$을 갖는 부분집합 $A \subseteq \{0,1, \cdots , \omega - 1 \}$을 인코딩 가능.

ex) $a = [01101001]$은 집합 $A = \{0, 3,5,6\}$을 인코딩, $b = [01010101] $은 집합 $B = \{0, 2, 4, 6 \}$을 인코딩.

또한 bool연산 |와 &는 합집합과 교집합 연산, ~는 여집합 연산에 대응 가능.

---

2.1.7 C에서의 비트수준 연산

앞서 설명.

C expression	Binary expression	Binary result	Hexadecimal result
~0x41	~[0100 0001]	[1011 1110]	0xBE
~0x00	~[0000 0000]	[1111 1111]	0xFF
0x69 & 0x55	[0110 1001] & [0101 0101]	[0100 0001]	0x41
0x69 | 0x55	[0110 1001] | [0101 0101]	[0111 1101]	0x7D

위 표는 char 자료형에서 수식 계산 예제. 

 

'마스크 연산(masking operation)'을 할 때 비트 연산을 사용

• 0xFF를 통해 한 워드의 가장 덜 중요한 8비트를 지정할 수 있음
• 어떤 워드 x가 있을 때 x&0xFF는 x의 가장 덜 중요한 바이트를 제외하고 모두 0으로 바꿔놓은 워드를 나타낸다.
• x = 0x89ABCDEF이면 x&0xff는 0x000000EF이다.
• ~0은 비트가 모두 1인 마스크를 만든다.
• 가장 중요한 비트쪽으로 마스킹을 하는 경우 워드의 크기에 따라 호환성이 없을 수 있으므로 주의.

---

2.1.8 C에서의 쉬프트 연산

비트 표시 $[x_{\omega - 1} , x_{\omega - 2}, \cdots , x_o ]$을 갖는 피연산자 x에 대해, 식 $x<<k$는 비트 표시 $[x_{\omega - k - 1} , x_{\omega - k - 2} , \cdots , x_o , 0 , \cdots , 0]$을 생성.

x는 좌측으로 k비트 이동하고, 오른쪽에는 k개의 0으로 채워짐.

시프트하는 크기는 0과 $\omega - 1$사이의 값을 가짐.

시프트 연산은 associate from left to right하므로 $x<<j<<k$는 $(x<<j)<<k$와 동일.

 

C언어의 우측 시프트 연산 $x>>k$는 보통 두 종류의 관습을 가짐.

• 논리 우측 시프트(logical) : 왼쪽 끝을 0으로 채워줌 -> $[0, \cdots, 0, x_{\omega - 1} , x_{\omega - 2}, \cdots , x_k ]$
• 산술 우측 시프트(arithmetic) : 왼쪽 끝을 가장 중요한 비트로 채워줌 -> $[x_{\omega - 1} , \cdots , x_{\omega - 1}, x_{\omega - 1} , x_{\omega - 2} , \cdots , x_k ]$. (즉, 가장 중요한 비트가 $k+1$개 존재하게 된다)

다음은 각 8비트 데이터에 시프트 연산을 한 결과를 보여준다.

Operation	Value 1	Value 2
Argument x	[01100011]	[10010101]
x << 4	[00110000]	[01010000]
x >> 4 (logical)	[00000110]	[00001001]
x >> 4 (arithmetic)	[00000110]	[11111001]

C 표준은 부호형 숫자(signed number)의 우측 시프트 연산에 어떤 관습을 사용할지 강제하지 않아서 호환성 문제가 발생할 수 있다.

하지만 보통은 '부호형 데이터'에 대해 '산술 우측 시프트'를 사용한다.

'비부호형 데이터'에 대해서 우측 시프트는 '논리 우측 시프트'여야 한다.

 

자바는 이 둘을 명확히 구분한다. $x>>k$는 산술 우측 시프트, $x>>>k$는 논리 우측 시프트를 의미한다.

 

cf) $k \geq \omega$인 경우에 $k$만큼 시프트하면 보통은 $k \% \omega$만큼 하는 것으로 계산한다.

하지만 C 표준에서 이를 보장하는 것이 아니므로 시프트하는 양은 시프트되는 값의 비트 수보다 작도록 유지해야 한다.

자바에서는 명시적으로 modular 형태로 계산한다.

 

cf) $1 <<2 +3 <<4 = 1 << (2 +3) <<4$로 계산된다. 덧셈, 뺄셈이 시프트 연산자보다 우선순위가 높기 때문에 $(1<<2) +(3<<4)$의 결과를 얻고 싶다면 괄호를 사용하자.