CSAPP-2024-03-2주차-정리
2024년 3월 2주차
Chapter 2 Representing and Manipulating Information
현대 컴퓨터는 이진 신호를 사용해 정보를 저장하고 처리한다. 이진수, 또는 비트는 디지털 혁명의 기반이며, 십진법에 비해 기계 설계에 더 적합하다.
단일 비트는 제한된 정보만을 표현하지만, 비트를 그룹화하고 의미를 부여함으로써 다양한 데이터를 인코딩할 수 있다. 이 장에서는 이진수 시스템, 표준 문자 코드, 음수 및 실수 표현을 포함한 여러 인코딩 방식을 다룬다. 이를 통해 컴퓨터는 숫자, 문자, 실수 등을 효율적으로 표현할 수 있다.
숫자의 컴퓨터 표현에는 부호 없는 인코딩, 2의 보수 인코딩, 부동 소수점 인코딩 등 세 가지 주요 방식이 있다. 이들은 각각 0 이상의 수, 정수, 실수를 표현하는 데 사용된다.
컴퓨터는 제한된 비트 수를 사용해 숫자를 인코딩하기 때문에, 일부 연산 결과는 오버플로우를 경험할 수 있다.
현대 컴퓨터는 예상과 다른 결과를 낼 수 있지만, 일관성은 유지된다. 부동 소수점 산술은 전혀 다른 수학적 성질을 가지며, 연산의 순서에 따라 결과가 달라질 수 있다. 이러한 차이는 정수와 부동 소수점 표현이 값의 범위와 정밀도를 다루는 방식에서 기인한다.
숫자 표현을 연구함으로써, 표현 가능한 값의 범위와 다양한 산술 연산의 성질을 이해할 수 있다. 이러한 이해는 다양한 기계, 운영 체제, 컴파일러 조합에서 프로그램이 올바르게 작동하도록 하는 데 중요하다. 컴퓨터 산술의 미묘함으로 인해 컴퓨터 보안 취약점이 발생했다는 점을 설명한다.
컴퓨터는 수치 값을 인코딩하기 위해 여러 가지 이진 표현을 사용한다. 이 장에서는 이러한 인코딩을 설명하고 숫자 표현에 대해 추론하는 방법을 보여준다. 비트 수준의 숫자 표현을 직접 조작하여 산술 연산을 수행하는 여러 방법을 유도한다.
이 재료의 처리는 일련의 수학적 원칙에 기반을 두고 있다. C++ 프로그래밍 언어는 C에 기반을 두고 있으며, C에 대해 말한 모든 것이 C++에도 적용된다. 반면, Java 언어 정의는 수치 표현과 연산에 대한 새로운 표준 세트를 만들었다.
2.1 Information Storage
컴퓨터는 개별 비트에 접근하기보다는 8비트 블록, 즉 바이트를 메모리의 가장 작은 주소 지정 가능 단위로 사용한다. 기계 수준 프로그램은 메모리를 바이트의 매우 큰 배열인 가상 메모리로 간주한다. 모든 바이트는 고유한 번호, 즉 주소로 식별되며 가능한 모든 주소의 집합을 가상 주소 공간이라고 한다. 가상 주소 공간은 이름에서 알 수 있듯이 기계 수준 프로그램에 제시된 개념적 이미지에 불과하다. 실제 구현은 DRAM, 플래시 메모리, 디스크 저장소, 특수 하드웨어, 운영 체제 소프트웨어의 조합을 사용하여 프로그램에 단일 바이트 배열처럼 보이는 것을 제공한다.
컴파일러와 런타임 시스템이 이 메모리 공간을 더 관리하기 쉬운 단위로 분할하여 다양한 프로그램 객체, 즉 프로그램 데이터, 명령어, 제어 정보를 저장하는 방법에 대해서는 후속 장에서 다룰 것이다. C 컴파일러는 포인터마다 타입 정보를 연결하여 포인터가 지정하는 위치에 저장된 값의 타입에 따라 다른 기계 수준 코드를 생성할 수 있다. C 컴파일러는 이 타입 정보를 유지하지만, 실제로 생성하는 기계 수준 프로그램은 데이터 타입에 대한 정보가 없으며, 프로그램 객체를 바이트 블록으로, 프로그램 자체를 바이트 시퀀스로 단순히 처리한다.
2.1.1 Hexadecimal Notation
이 섹션은 16진수 표기법에 대해 설명하고 있다. 8비트로 이루어진 단일 바이트는 00000000₂에서 11111111₂의 이진 표기법 범위를 가지며, 십진수로는 0₁₀에서 255₁₀까지 표현할 수 있다. 그러나 이진수나 십진수 모두 비트 패턴을 설명하기에는 적합하지 않다. 이진 표기법은 지나치게 장황하고, 십진 표기법으로의 변환은 번거롭다. 이에 반해, 16진수는 0부터 F까지 16가지 가능한 값을 표현할 수 있어 비트 패턴을 기술하는 데 더 편리하다. 16진수 값은 ‘0x’ 또는 ‘0X’로 시작하며, 대문자나 소문자를 사용할 수 있다.
기계 수준 프로그램을 작업하는 과정에서 자주 있는 일은 십진수, 이진수, 16진수 표현 간에 수동으로 변환하는 것이다. 이진수와 16진수 사이의 변환은 각 16진수 자릿수를 차례대로 변환함으로써 직관적으로 수행할 수 있다.
이진수로 확장할 때, 각 16진수 자리수는 해당하는 4비트 이진수로 변환된다.
반대로, 이진수를 16진수로 변환할 때는 4비트씩 그룹화하여 변환하고, 총 비트 수가 4의 배수가 아니면 가장 왼쪽 그룹을 덜 채운다는 것을 주의해야 한다.
2의 거듭제곱 값인 x를 16진수로 쉽게 변환할 수 있는 방법도 제공한다. 이는 x가 2^n 형태일 때, 이진 표현은 1 다음에 n개의 0이 오므로, 16진수에서 0은 4개의 이진 0을 나타낸다는 사실을 이용한다.
2.1.2 Data Sizes
모든 컴퓨터에는 포인터 데이터의 명목상 크기를 나타내는 워드 크기가 있다. 가상 주소가 이러한 워드로 인코딩되므로, 워드 크기에 의해 결정되는 가장 중요한 시스템 매개변수는 가상 주소 공간의 최대 크기다. 즉, w비트 워드 크기를 가진 기계의 경우, 가상 주소는 0부터 2^w - 1의 범위를 가지며, 프로그램은 최대 2^w 바이트에 접근할 수 있다.
최근 몇 년 동안 32비트 워드 크기를 가진 기계에서 64비트 워드 크기를 가진 기계로 널리 전환되고 있다. 32비트 워드 크기는 가상 주소 공간을 4기가바이트(4 GB), 즉 약 4 × 10^9 바이트로 제한한다. 64비트 워드 크기로 확장하면 가상 주소 공간은 16엑사바이트 또는 약 1.84 × 10^19 바이트에 이른다.
2.1.3 Addressing and Byte Ordering
각 컴퓨터는 포인터 데이터의 명목상 크기를 나타내는 워드 크기를 가진다. 가상 주소는 워드로 인코딩되므로 워드 크기에 의해 결정되는 가장 중요한 시스템 매개변수는 가상 주소 공간의 최대 크기다. 즉, w-비트 워드 크기를 가진 기계는 0부터 2^w - 1까지의 가상 주소 범위를 가질 수 있어 최대 2^w 바이트에 접근할 수 있다.
64비트 기계는 대부분 32비트 기계에서 컴파일된 프로그램도 실행할 수 있어 이는 하위 호환성의 한 형태다. 예를 들어, 프로그램이 ‘gcc -m32 prog.c’ 지시어로 컴파일되면 이 프로그램은 32비트 또는 64비트 기계 모두에서 정확하게 실행될 수 있다. 반면에 ‘gcc -m64 prog.c’ 지시어로 컴파일된 프로그램은 64비트 기계에서만 실행될 수 있다. 따라서 프로그램을 “32비트 프로그램” 또는 “64비트 프로그램”으로 참조한다.
컴퓨터와 컴파일러는 정수와 부동 소수점과 같은 다양한 데이터 형식을 지원하며, 이러한 데이터 형식은 다양한 길이로 인코딩된다. C99 ISO 표준은 컴파일러 및 기계 설정에 관계없이 데이터 크기가 고정된 데이터 타입 클래스를 도입했다. 이 중 int32_t와 int64_t는 각각 정확히 4바이트와 8바이트를 가진다. 고정 크기 정수 타입을 사용하는 것이 프로그래머가 데이터 표현을 더 잘 제어할 수 있는 가장 좋은 방법이다.
대부분의 데이터 타입은 signed 값으로 인코딩되지만, unsigned 키워드로 선언되거나 고정 크기 데이터 타입에 대한 구체적인 unsigned 선언을 사용하지 않는 한, 이는 사실이 아니다. 예외는 char 데이터 타입인데, 대부분의 컴파일러와 기계는 이를 signed 데이터로 처리하지만, C 표준은 이를 보장하지 않는다. 대신, 프로그래머는 signed char 선언을 사용해야 한다.
프로그래머는 프로그램을 다양한 기계와 컴파일러에서 이식할 수 있도록 노력해야 한다. 이식성의 한 측면은 다양한 데이터 타입의 정확한 크기에 프로그램을 민감하지 않게 하는 것이다. C 표준은 다양한 데이터 타입의 숫자 범위에 대한 하한을 설정하지만, 고정 크기 타입을 제외하고는 상한이 없다. 1980년부터 2010년까지 주로 32비트 기계와 프로그램이 주를 이루었기 때문에 많은 프로그램이 32비트 프로그램의 할당량을 가정하여 작성되었다. 64비트 기계로의 전환으로 많은 숨겨진 워드 크기 의존성이 새로운 기계로 프로그
램을 이전하면서 버그로 드러났다. 예를 들어, 많은 프로그래머는 int 타입으로 선언된 객체를 포인터를 저장하는 데 사용할 수 있다고 가정했지만, 이는 대부분의 32비트 프로그램에서는 문제가 되지 않지만 64비트 프로그램에서는 문제가 될 수 있다.
프로그램 객체가 여러 바이트를 차지하는 경우, 객체의 주소를 결정하고 메모리 내 바이트를 어떻게 순서지을지에 대한 규칙을 정해야 한다. 거의 모든 기계에서 다바이트 객체는 연속된 바이트 시퀀스로 저장되며, 객체의 주소는 사용된 바이트들 중 가장 작은 주소로 주어진다. 예를 들어, int형 변수 x가 0x100 주소를 가진다고 하면, int형 데이터의 32비트 표현을 가정할 때, x의 4 바이트는 메모리 위치 0x100, 0x101, 0x102, 0x103에 저장된다.
객체를 나타내는 바이트를 순서대로 배열하는 데에는 두 가지 일반적인 관습이 있다. w-비트 정수가 [xw-1,xw-2,…,x1,x0]의 비트 표현을 가지고 있을 때, 가장 중요한 비트는 xw-1이고 가장 덜 중요한 비트는 x0이다. 이 비트들은 w가 8의 배수라고 가정하면 바이트로 그룹화될 수 있으며, 가장 중요한 바이트는 [xw-1,xw-2,…,xw-8]의 비트를 가지고, 가장 덜 중요한 바이트는 [x7,x6,…,x0]의 비트를 가진다. 일부 기계는 가장 덜 중요한 바이트부터 가장 중요한 바이트 순으로 객체를 저장하는 반면, 다른 기계는 가장 중요한 바이트부터 반대 순으로 저장한다. 가장 덜 중요한 바이트가 먼저 오는 관습을 리틀 엔디언(little endian)이라 하고, 가장 중요한 바이트가 먼저 오는 관습을 빅 엔디언(big endian)이라 한다.
대부분의 인텔 호환 기계는 전적으로 리틀 엔디언 모드에서 작동한다. 반면 IBM과 오라클(2010년 선 마이크로시스템즈 인수)의 대부분의 기계는 빅 엔디언 모드에서 작동한다. ARM 마이크로프로세서와 같은 많은 최신 마이크로프로세서 칩은 양방향 엔디언(bi-endian)으로서 리틀 엔디언이나 빅 엔디언 기계로 구성될 수 있다. 그러나 실제로는 특정 운영 체제가 선택되면 바이트 순서는 고정된다.
네트워크를 통해 서로 다른 기계 간에 이진 데이터가 전송될 때 바이트 순서가 문제가 될 수 있다. 네트워크 응용 프로그램을 위한 코드를 작성할 때는 전송 기계가 내부 표현을 네트워크 표준으로 변환하고, 수신 기계가 네트워크 표준을 내부 표현으로 변환하도록 하는 바이트 순서에 대한 확립된 관습을 따라야 한다.
바이트 순서는 기계 수준 프로그램을 검사할 때도 중요하다. 예를 들어, 인텔 x86-64 프로세서의 기계 수준 코드 텍스트 표현 파일에 다음과 같은 줄이 있다고 가정해보자:
4004d3: 01 05 43 0b 20 00 add %eax,0x200b43(%rip)
이 줄은 디스어셈블러에 의해 생성된 것으로, 실행 가능한 프로그램 파일에 의해 표현되는 명령어 시퀀스를 결정하는 도구다. 이를 통해, 리틀 엔디언 기계에서 생성된 기계 수준 프로그램 표현을 읽을 때 바이트가 반대 순서로 나타나는 것이 일반적임을 알 수 있다.
또한 일부 프로그램들은 일반 타입 시스템을 우회하는 경우에도 바이트 순서가 드러난다. C 언어에서는 캐스트나 유니온을 사용하여 생성된 데이터 타입과 다른 데이터 타입으로 객체를 참조할 수 있다. 이러한 코딩 기법은 대부분의 응용 프로그래밍에서는 권장되지 않지만, 시스템 수준 프로그래밍에서는 유용하고 필수적일 수 있다.
결론적으로 바이트 순서는 주로 기계 수준의 데이터 교환과 처리에서 중요해지며, 애플리케이션 프로그래머에게는 대체로 보이지 않는 부분이다. 그러나 포터블하고 효율적인 코드를 작성하기 위해서는 기계와 컴파일러 간의 차이점을 이해하고 고려하는 것이 중요하다.
2.1.4 Representing Strings
C에서 문자열은 널(null) 문자(값이 0)로 종결되는 문자 배열로 인코딩된다. 각 문자는 어떤 표준 인코딩으로 표현되며, 가장 일반적인 인코딩은 ASCII 문자 코드다. 따라서 우리의 show_bytes 루틴을 “12345” 문자열과 종결 문자를 포함하여 6이라는 인자와 함께 실행하면 결과는 31 32 33 34 35 00이다. 십진수 자릿수 x에 대한 ASCII 코드가 0x3x이고, 종결 바이트가 16진수 표현 0x00을 가진다는 것을 알 수 있다. 이 결과는 ASCII를 문자 코드로 사용하는 어떤 시스템에서도, 바이트 순서와 워드 크기 관습에 독립적으로, 동일하게 얻을 수 있다. 이로 인해 텍스트 데이터는 바이너리 데이터보다 플랫폼 독립적이다.
2.1.5 RepresentingCode
C에서 문자열은 null(값이 0인) 문자로 종료되는 문자 배열로 인코딩된다. 각 문자는 표준 인코딩, 가장 흔히 ASCII 문자 코드로 표현된다. 따라서 show_bytes 함수를 “12345”와 6(종료 문자 포함) 인자로 실행하면 결과는 31 32 33 34 35 00이 된다. 이는 십진수 자리 수 x에 대한 ASCII 코드가 0x3x이고, 종료 바이트가 16진수로 0x00을 가진다는 것을 나타낸다. 이 결과는 문자 코드로 ASCII를 사용하는 모든 시스템에서 동일하게 얻을 수 있으며, 바이트 순서나 워드 크기 관례와는 독립적이다. 이로 인해 텍스트 데이터는 바이너리 데이터보다 플랫폼 독립성이 더 크다.
함수 sum의 C 코드는 컴파일될 때 다양한 기계에서 서로 다른 바이트 표현의 기계 코드를 생성한다. 다른 기계 유형은 서로 다른 지침과 인코딩을 사용하며, 심지어 동일한 프로세서가 다른 운영 체제를 실행할 때에도 코딩 관례에서 차이가 있어 이진 호환성이 없다. 바이너리 코드는 일반적으로 다른 기계와 운영 체제 조합 간에 이식성이 거의 없다.
컴퓨터 시스템의 근본적인 개념 중 하나는 프로그램이 기계의 관점에서 단순히 바이트 시퀀스라는 것이다. 기계는 디버깅을 돕기 위해 유지되는 몇몇 보조 테이블을 제외하고는 원래의 소스 프로그램에 대한 정보를 가지고 있지 않다. 기계 수준 프로그래밍을 3장에서 공부할 때 이에 대해 더 명확히 이해할 수 있을 것이다.
2.1.6 Introduction to Boolean Algebra
2.1.6절은 컴퓨터가 정보를 인코딩, 저장, 조작하는 데 있어 중심적인 이진값 0과 1에 관한 풍부한 수학적 지식을 소개한다. 이는 조지 불(1815-1864)의 작업을 시작으로 1850년경에 발전했으며, 불 대수(Boolean algebra)라고 알려져 있다. 불은 참과 거짓 논리 값을 1과 0으로 인코딩함으로써 논리적 추론의 기본 원리를 포착하는 대수를 형식화할 수 있음을 관찰했다.
가장 간단한 불 대수는 두 원소 집합 {0, 1}에 대해 정의된다. 여기서, ~는 논리 연산 not(¬), &는 and(∧), |는 or(∨), ^는 배타적 or(⊕)에 해당한다. 예를 들어, ~P는 P가 참이 아닐 때 참이며, p & q는 p와 q가 모두 1일 때만 1이 된다. p | q는 p 또는 q 중 하나라도 1이면 1이 되고, p ^ q는 p와 q 중 하나만 1일 때 1이 된다.
클로드 섀넌(1916–2001)은 불 대수와 디지털 논리 사이의 연결을 처음으로 만들었다. 그는 1937년 석사 논문에서 불 대수가 전자기계 릴레이 네트워크의 설계 및 분석에 적용될 수 있음을 보여주었다. 컴퓨터 기술이 크게 진보했지만, 불 대수는 여전히 디지털 시스템의 설계와 분석에서 중심적인 역할을 한다.
이 네 가지 불 연산은 고정된 길이 w의 0과 1의 문자열인 비트 벡터에 대해서도 확장될 수 있다. 비트 벡터에 대한 연산은 인수의 해당 요소에 대한 적용에 따라 정의된다. a와 b가 비트 벡터 [aw-1,aw-2,…,a0]와 [bw-1,bw-2,…,b0]를 각각 나타낼 때, a & b는 또한 길이 w의 비트 벡터이며, 0 ≤ i<w에 대해 i번째 요소는 ai & bi 이다. 연산 |, ^, ~도 비슷한 방식으로 비트 벡터에 확장된다.
예를 들어 w = 4이고 인수 a = [0110]과 b = [1100]이 주어졌을 때, 네 연산 a & b, a | b, a ^ b, 그리고 ~b는 다음과 같은 결과를 생성한다. (문장이 완성되지 않았으므로, 결과에 대한 구체적인 설명은 제공되지 않았다.)
2.1.7 Bit-Level Operations in C
2.1.7절은 C 언어가 제공하는 비트 수준 불 연산자에 대해 다룬다. C에서 사용하는 |, &, ~, ^ 기호는 각각 or, and, not, exclusive-or 연산에 해당한다. 이 연산자들은 Figure 2.3에 나열된 모든 ‘정수’ 데이터 타입에 적용 가능하며, char 타입의 데이터를 예로 든 표현식 계산 예제를 제공한다. 예를 들어, ~0x41 표현식의 결과는 이진수 [1011 1110]에 해당하며, 16진수로는 0xBE가 된다. 0x69 & 0x55는 이진수 [0110 1001] & [0101 0101]로 계산되어 [0100 0001]이 되고, 16진수로는 0x41이 된다. 비트 수준 표현의 영향을 평가하는 가장 좋은 방법은 16진수 인수를 이진 표현으로 확장하여 연산을 수행하고 그 결과를 다시 16진수로 변환하는 것이다. 마스킹 연산 같은 비트 수준 연산의 적용은 단어 내에서 특정 비트 집합을 선택하는 데 유용하다.
2.1.8 Logical Operations in C
2.1.8절에서는 C 언어의 논리 연산자 ||, &&, !에 대해 설명한다. 이들은 각각 논리학의 or, and, not 연산에 해당하며, 비 0을 참으로, 0을 거짓으로 간주한다. 반환값은 참 또는 거짓을 나타내는 1 또는 0이다. 하지만 비트 수준 연산과 달리, 논리 연산자는 첫 번째 인수만으로 결과를 결정할 수 있는 경우 두 번째 인수를 평가하지 않는 ‘단락 평가’를 수행한다. 이는 나누기 0과 같은 연산을 방지하고 널 포인터 역참조를 피하는 데 도움이 된다.
2.1.9 Shift Operations in C
이미지에 나타난 2.1.9절에서는 C 언어의 비트 시프트 연산에 대해 다루고 있다. 비트 패턴을 왼쪽이나 오른쪽으로 이동하는 데 사용되는 시프트 연산자는 << 왼쪽 시프트와 >> 오른쪽 시프트 두 가지가 있다.
x << k 연산은 피연산자 x의 비트 패턴을 왼쪽으로 k비트만큼 이동시키며, 가장 중요한 k개의 비트를 삭제하고 오른쪽 끝에 k개의 0을 채워 넣는다. 시프트하는 양 k는 0과 w-1 사이의 값이어야 한다.
오른쪽 시프트 연산인 x >> k에는 논리적 시프트와 산술적 시프트 두 가지 형태가 있다. 논리적 시프트는 왼쪽 끝을 k개의 0으로 채우고, 산술적 시프트는 가장 중요한 비트를 k번 반복하여 채운다.
예시로 제공된 테이블은 8비트 인수 x에 대해 다른 시프트 연산을 적용했을 때의 결과를 보여준다:
x << 4:[01100011]과[10010101]이 각각[00110000],[01010000]으로 왼쪽으로 4비트 시프트된다.x >> 4(논리적) :[01100011]과[10010101]이 각각[00000110],[00001001]로 오른쪽으로 4비트 논리 시프트된다.x >> 4(산술적) :[01100011]은[00000110]으로 변하지만,[10010101]은 최상위 비트가 1이기 때문에[11111001]로 산술 시프트된다.
C 표준은 부호 있는 숫자에 대해 어떤 타입의 오른쪽 시프트가 사용되어야 하는지 명확히 정의하지 않지만, 실제로는 대부분의 컴파일러/기계 조합이 부호 있는 데이터에 대해 산술적 오른쪽 시프트를 사용한다. 반면에 부호 없는 데이터에 대해서는 오른쪽 시프트가 논리적으로 수행되어야 한다.
C와 달리, 자바는 오른쪽 시프트가 수행되어야 하는 방법을 정확하게 정의한다. 자바에서 x >> k는 x를 산술적으로 k 위치만큼 시프트하고, x >>> k는 논리적으로 시프트한다.