Ch2.1 Information Storage

Park Choong Ho·2021년 8월 25일
0

2.1 Information Storage

메모리에 있는 개별 비트에 접근하는 대신, 대부분 컴퓨터는 8 비트 단위 블록인 바이트를 가장 작은 메모리 단위로 사용합니다. Machine-level 프로그램은 virtual memory라 부르는 메모리를 그저 큰 바이트 배열로 해석합니다. 메모리의 모든 바이트들은 유일한 숫자로 판별될 수 있고 이 유일한 숫자를 주소라 합니다. 이 주소들의 집합을 virtual address space 라합니다. 이름에서 유추할 수 있듯이, 가상 메모리 공간은 machine-level 프로그램에 제공되는 단지 개념적인 이미지입니다. 실제 동작은 DRAM, 플래시 메모리, 디스크 저장소, 특정 하드웨어, 우리고 운영체제간 결합을 통해 프로그램에 자신만이 가지는 것 같은 독자적 바이트 배열을 제공하는 것입니다. 더 자세한 것은 9장에서 살펴보겠습니다.

추후 단원에서, 컴파일러와 런타임 시스템이 이 메모리 공간을 어떻게 더 관리 가능한 단위로 나누는지 살펴볼 것입니다. 메모리 단위에는 여러 program object들 (program data, instructions, 그리고 control information) 이 저장됩니다. 프로그램에 저장된 여러 다른 부분들을 관리하고 공간을 할당하기 위해 여러 매커니즘들이 활용됩니다. 관리는 모두 가상 주소 공간안에서 이루어집니다. 예를 들어, C 포인터 값은 이것이 정수를 저장하든, 구조체를 저장하든, 다른 program object를 저장하든 해당 블록 첫번째 바이트 가상 주소를 가리킵니다. 또한, C 컴파일러는 각 포인터를 type 정보와 결합합니다. 이로 인해 가리키는 값 타입에 따라, 포인터가 가리키는 위치값에 다르게 접근하는 여러 machine-level 코드를 만들 수 있습니다. 컴파일러는 타입 정보를 유지하지만, 실제 machine-level 프로그램은 데이터 타입에 대한 정보를 가지고 있지 않습니다. 각 program object를 바이트 블록으로 해석하고 프로그램 자신 또한 바이트의 연속이라 생각합니다.

2.1.1 Hexadecimal Notation

하나의 바이트는 8 비트로 이루어져 있습니다. 00000000(2)부터 11111111(2)까지 값을 가집니다. 10진 수 정수로 보면, 0부터 255까지입니다. 이 두 표현법은 모두 비트 패턴을 표현하는데 있어 불편합니다. 이진법은 너무 장황하며 십진법은 비트 패턴으로 옮기는데 있어 애로 사항이 있습니다. 따라서 16 진법에 기초한 hexadecimal을 사용해 비트 패턴을 표현합니다. Hexadecimal은 0부터 9 그리고 알파벳 'A'부터 'F'까지 16개의 숫자로 표현합니다. 16진법으로 바이트 하나를 00(16)부터 FF(16)까지 표현할 수 있습니다.

C에서, 0x 또는 0X로 시작하는 수는 16진법으로 해석합니다. 알파벳은 대문자, 소문자 모두 가능합니다. 예를 들어, 0xFa1D37b 0xFA1D37B 0xfa1d37b 모두 맞는 표현입니다. 여기서는 C 표현 방식을 사용하겠습니다.

Machine-level 프로그램 작성시 일반적인 일 중 하나는 10진법, 2진법, 16진법으로 표현된 숫자들을 서로 다른 진법으로 바꿔주는 것입니다. 2진법과 16진법 사이 변환은 이해하기 쉬운데, 그 이유는 한번에 수행할 수 있기 때문입니다. 아래 표를 보면 각각에 대응하는 표현을 확인하실 수 있습니다.

Hex digit01234567
Decimal value01234567
Binary value00000001001000110100010101100111
Hex digit89ABCDEF
Decimal value89101112131415
Binary value10001001101010111100110111101111

어떤 값 x가 2의 제곱승이면 x = 2^n으로 나타낼 수 있습니다. n이 음이 아닌 정수라고 할때, 해당 수는 맨 앞이 1이고 그 뒤가 0 n개로 구성된 2진법 수 입니다. 이를 바탕으로, x를 16진법으로 표현할 수 있습니다. 16진법에서 0은 4개의 이진법 0으로 나타냅니다. 따라서, n이 i + 4j (0 <= i <= 3)이라 했을때, 우리는 x를 맨앞에 숫자 1 (i=0), 2 (i=1), 4(i=2), 8(i=3)이 따르고 그 뒤에 16진법 0들이 따라오는 형태로 표현할 수 있습니다. 예를 들어, x = 2^11이라 했을 때 11 = 3 + 4 * 2이므로 0x800입니다.

Practice Problem 2.1

A. 0x25B9D2를 이진법으로
B. 이진법 1010111001001001을 16진법으로
C. 0xA8B3D를 이진법으로
D. 이진법 1100100010110110010110을 16진법으로

Practice Problem 2.2

n2^n(decimal)2^n (hexadecimal)
5320x20
23______
__32,768__
_____0x2000
12_____
_64__
__0x100

빈칸을 채우시오.

Practice Problem 2.3

Practice Problem 2.4

2.1.2 Data Sizes

모든 컴퓨터들을 word size를 가지고 있습니다. word size는 pointer data의 명목상 크기를 나타냅니다. 가상주소가 이 word 단위로 인코딩되기에, 워드 크기에 의해 결정되는 가장 중요한 시스템 요소는 가상 주소 최대 크기입니다. 그 말은 즉, 만약 기계가 w-bit 워드 크기를 가진다 했을때, 가상 주소는 0부터 2^w - 1까지 되고 프로그램은 최대 2^w 바이트만큼 접근할 수 있습니다.

최근 몇년 동안, 컴퓨터는 32-bit 워드에서 64-bit 워드로 진화해 왔습니다. 이러한 변화는 큰 규모의 데이터베이스에서 시작해 그 다음 랩탑, 데스크탑 그리고 최근에는 스마트폰까지 이어졌습니다. 32-bit 워드 크기는 가상 주소 공간을 약 4GB까지 제한합니다. 64-bit까지 scaling up하면 가상 주소 공간을 16 exabytes까지 늘릴 수 있습니다.

또한, 64-bit 기계들은 32-bit 기계를 대상으로 컴파일한 프로그램을 돌릴 수 있습니다. 이를 backward compatibility라 합니다. 예를 들어 prog.c 프로그램을 아래와 같이 컴파일했을 때,

linux> gcc -m32 prog.c

이 프로그램은 32-bit, 64-bit 컴퓨터 모두에서 동작합니다. 반면 아래와 같이

linux> gcc -m64 prog.c

컴파일 했을 경우 64-bit 기계에서만 동작합니다. 따라서 프로그램을 32-bit 프로그램 또는 64-bit 프로그램이라 합니다. 왜냐하면 프로그램은 프로그램이 동작하는 기계 종류 보다는 프로그램이 어떻게 컴파일 됐는가에 기반하기 때문입니다.

컴퓨터와 컴파일러는 integer, floating point, 또 여러 크기를 가진 데이터 인코딩 방법들을 활용해 데이터 포맷을 지원합니다. 예를 들어, 많은 컴퓨터들은 바이트 하나뿐 아니라, 2-, 4-, 8- 바이트 크기 integer를 다루는 인스트럭션들을 가지고 있습니다. 또한 4-, 8- 바이트 크기의 floating-point 수들도 지원합니다.

C 언어는 integer와 floating-point 데이터를 위한 여러 데이터 포맷을 지원합니다. 아래 그림은 여러가지 C 데이터 타입에 할당되는 바이트 크기를 보여줍니다.

C declaarationBytes
SignedUnsigned32-bit64bit
[signed] charunsigned char11
shortunsigned short22
intunsigned44
longunsigned long48
int32_tuint32_t44
int64_tuint64_t88
char*48
float44
double88

몇몇 데이터들의 바이트 크기는 프로그램이 어떻게 컴파일 되어있느냐에 달려있습니다. 32-bit, 64-bit 프로그램 각각의 데이터 바이트 크기를 확인할 수 있습니다. Integer 데이터는 양수, 0, 음수 모드를 나타내는 signed, 양수, 0 만 나타내는 unsigned 두가지가 있습니다. char 데이터는 바이트 1개입니다. 비록 char라는 이름에서 알 수 있듯, text에서 문자 하나를 저장하기 위해 사용되지만 여기에도 integer를 저장할 수 있습니다. 데이터 타입 short, int, long은 여러 크기의 데이터를 나타내기 위함입니다. 64-bit 시스템을 대상으로 컴파일 되었다고 하더라도, int 타입은 여전히 4바이트입니다. long 데이터 타입은 32-bit에서 4바이트이지만 64-bit에서는 8byte입니다.

New to C? Declaring pointers

어떤 타입 T에 더해서
T p;
은 T 타입을 가리키는 포인터 변수를 나타냅니다.
예를 들어,
char
p;
라 선언하면, 이는 char 타입을 포인터 변수입니다.

다른 컴파일러 설정과 전형적인 크기에 따른 변동성을 피하기 위해, ISO C99는 컴파일러와 컴퓨터 설정에 관계없이 고정된 데이터 크기를 가진 데이터 타입 클래스를 소개하고 있습니다. int32_t, int64_t가 앞서 말한 그것들이며 각각 정확히 4, 8바이트씩 차지합니다. 고정된 크기의 integer 타입을 사용하는 것은 데이터 표현을 프로그래머가 데이터 표현을 제어하는 가장 좋은 방법입니다.

대부분 데이터 타입들은 unsigned가 접두어로 붙거나 고정된 데이터 타입을 위한 특정한 unsigned 선언을 하지 않는 이상, signed 값들을 인코딩합니다. char 타입은 이 규칙에서 벗어납니다. 비록 대부분 컴파일러와 컴퓨터들이 char를 signed 데이터 취급하지만, C 기준은 이를 보장하지 않습니다. 대신에, 꺽쇠 괄호([])에서 알 수 있듯이, 프로그래머는 signed char 선언을 해주어 1 바이트 signed 값임을 보장해 주어야 합니다. 하지만 많은 context상에서 char 데이터 타입이 signed인지 unsigned인지는 프로그램에서 크게 민감한 내용은 아닙니다. C언어는 키워드를 정렬하고 선택적 키워드를 포함하거나 생략하는 다양한 방법을 허용합니다. 예를 들어,

unsigned long
unsigned long int
long unsigned
long unsigned int

모두 같은 의미를 가지고 있습니다.

위 그림은 포인터가 프로그램 word size만큼 사용함을 보여줍니다. (type char *이 그 예시입니다.) 대부분 기계들은 2개의 다른 floating-point 포맷을 지원합니다. 하나는 single precision이며 C에서 float으로 선언됩니다. 다른 하나는 double precision으로 C에서 double로 선언됩니다. float은 4 바이트, double은 8바이트입니다.

프로그래머는 자신의 프로그램이 여러 다른 컴퓨터와 컴파일러에서 돌아갈 수 있게끔 노력해야 합니다. 이러한 이식성중 하나는 프로그램이 다른 데이터 크기에 무감각해지게끔 만드는 것입니다. C 기준은 다른 데이터 타입들에 대한 lower bound 숫자 범위는 있지만 upper bound는 없습니다.(fixed-size 타입은 예외입니다.) 1980년부터 2010년까지 32-bit 컴퓨터와 프로그램이 득세하던 시절에는, 많은 프로그램들이 32-bit 프로그램 할당을 기준으로 작성되어 왔습니다. 64-bit 컴퓨터로 넘어가면서, 많은 숨겨진 워드 크기 의존성들이 새로운 컴퓨터에 이식되는 프로그램들의 버그가 되었습니다. 예를 들어, 많은 프로그래머들이 역사적으로 int타입으로 선언된 객체를 포인터를 저장하는데 사용할 수 있게 가정했습니다. 32-bit 프로그램에서는 동작하지만, 64-bit 컴퓨터에서는 문제를 야기합니다.

2.1.3 Addressing and Byte Ordering

여러 바이트를 포괄하는 프로그램 객체에 대해, 2가지 convention을 기억합시다. 하나는 그 객체의 주소가 무엇인지고 다른 하나는 해당 바이트들을 메모리상에 어떻게 나열할 것인지입니다. 거의 모든 시스템에서 다중 바이트 객체는 바이트의 연속으로 저장되어 있고 해당 바이트들 중 가장 작은 주소 값을 주소로 가집니다. 예를들어, int 타입 변수 x가 0x100주소를 가진다고 해봅시다. 이 말은 즉, &x값이 0x100이 된다는 의미입니다.(&는 해당 변수의 주소를 가리킵니다. 그리고 32-bit 기준으로 생각해봅시다.) x의 4 바이트는 0x100, 0x101, 0x102, 0x103에 저장될 것입니다.

객체를 표현하는 바이트를 나열하기 위한 2가지 방식이 있습니다. w-bit integer가 bit를 [x(w-1), x(w-2), ......., x(1), x(0)]을 가지고 있고 x(w-1)이 가장 영향력있는 비트이고 x(0)이 가장 영향력 없는 비트라고 해봅시다. w가 8의 배수임을 가정하고 이 비트들이 바이트로 그룹화 되어 있다고 한다면, [x(w-1), x(w-2), ......., x(w-8)]을 가지고 있는 바이트가 가장 영향력 있는 바이트고 가장 영향력 없는 바이트가 [x(7), x(6), ..... x(0)] 비트를 가지게 될 것입니다. 다른 바이트들은 중간에 있는 비트들을 가지게 될 것입니다. 몇몇 컴퓨터들은 가장 영향력 없는 바이트부터 저장하는 반면에, 다른 컴퓨터들은 가장 영향력 있는 바이트부터 저장합니다. 전자(가장 영향력 없는 바이트가 먼저오는 경우)를 little endian이라하고 후자(가장 영향력 있는 바이트가 먼저오는 경우)를 big endian이라 합니다.

int 타입을 가지는 x 변수가 주소값 0x100을 가지고 값을 0x1234567을 가진다고 해봅시다. 바이트의 순서는 컴퓨터의 종류에 따라 달라집니다.

0x1234567에서 high-order 바이트가 0x01이고 low-order 바이트가 0x67입니다.

대부분 Intel 호환 컴퓨터들은 little-endian 모드로 동작합니다. 반면에, IBM, Oracle 컴퓨터들은 big-endian모드로 동작합니다. "대부분"이란 단어에 주목하시면 됩니다. 이 convetion은 정확히 회사에 따라 구분되어지지 않습니다. IBM과 Oracle 컴퓨터 중에서도 Intel 호환 프로세서를 사용하는 컴퓨터들은 little-endian입니다. 최근의 많은 마이크로프로세서 칩들은 bi-endian인데 이말은 little, big 모두에서 동작한다는 뜻입니다. 하지만 실제 사용에서, 바이트 정렬 순서는 특정 운영체제가 선택되면 고정됩니다. 예를 들어, ARM 마이크로 프로세서들(핸드폰에서 많이 사용되는)은 little, big에서 모두 동작하는 하드웨어를 가지고 있습니다. 하지만 이 칩들이 주로 사용되는 운영체제들은 - 안드로이드(구글), IOS(애플) - 오직 little-endian에서만 동작합니다.

어떤 방식이 더 적합한지 궁금하실 겁니다. 한쪽을 선택할 기술적인 이유는 없습니다. 한쪽을 선택하고 지속적으로 그것을 유지하는 한, 선택은 가변적일 수 있습니다.

프로그래머에서 컴퓨터가 사용하는 바이트 정렬은 눈에 보이지 않습니다.(바이트 정렬이 다른 컴퓨터에서 컴파일한 결과는 동일합니다.) 그런데, 바이트 정렬이 문제가 될때가 있습니다. 하나는 네트워크를 통해 다른 컴퓨터간에 binary data를 주고 받는 경우입니다. 일반적인 문데는 little-endian 컴퓨터에서 데이터를 big-endian으로 보낸 경우입니다.(반대의 경우도 마찬가지입니다.) 이렇게 될경우 워드안에 바이트들이 전송받는 프로그램에서 뒤집어진채로 들어오기 때문입니다. 이러한 문제점을 피하기 위해, 네트워킹 프로그램에서 활용되는 코드는 바이트 정렬에 따른 미리 짜여진 convention을 따르게끔 되어 있습니다. 이렇게 하면 데이터를 전송하는 컴퓨터가 내부 표현을 네트워크 기준에 맞게 변화하고 반면에 전송받는 기계는 네트워크 기준을 내부 표현에 맞게 변형시키는 것입니다. 이러한 예시는 11장에서 살펴보겠습니다.

두번째 경우는 바이트 정렬이 integer 데이터를 표현하는 바이트 집합을 해석할 때 중요한 경우입니다. machine-level 프로그램을 살펴볼 때 종종 나타납니다. 예를 들어, Intel x86-64 프로세서에 맞는 machine-level 코드 텍스트 표현을 주는 파일에 이러한 코드 라인이 있다고 가정해봅시다.

4004d3: 01 05 43 0b 20 00 add %eax, 0x200b43(%rip)

이 코드 라인은 disassembler에 의해서 생성됩니다.(disassembler는 executable 프로그램에서 표현되는 인스트럭션 집합을 결정하는 도구입니다. 3장에서 다시 확인할 것 입니다.) For now, we simply note that this line states that the hexadecimal byte sequence 01 05 43 0b 20 00 is the byte-level representation of an instruction that adds a word of data to the value stored at an address computed by adding 0x200b43 to the current value of the program counter, the address of the next instruction to be executed. 앞서 있는 0을 떼어내면, 우리는 0x200b43이라는 숫자값을 가지게 될 것입니다. 이렇게 little-endian 컴퓨터에서 생성된 machine-level 프로그램 표현을 읽으면, 바이트들이 뒤집어진채로 보이게 됩니다. 바이트 집합을 작성하는 자연스러운 방법은 가장 낮은 순서 바이트를 왼쪽에 쓰고 가장 높은 것을 오른쪽에 쓰는 것입니다. 하지만 이는 숫자를 일반적으로 가장 영향력이 큰 자리수를 왼쪽에 쓰고 가장 낮은 것을 오른쪽에 쓰는 방법과는 차이가 있습니다.

3번째는 바이트 정렬을 눈으로 확인할 수 있을때입니다. 대표적으로 보통의 타입시스템을 우회하는 프로그램을 작성할 떄입니다. C 언어에서는, castunion을 사용해 오브젝트가 처음에 생성된 데이터 타입과 다른 타입으로 참조되는 것을 가능하게 했을때 일어납니다. 이러한 코딩 트릭은 프로그램 개발시에는 지양되는데, system-level 프로그램밍시에는 꽤나 유용하며 필요한 경우도 종종 있습니다.

아래 그림은 casting을 사용해 접근하고 다른 프로그램 오브젝트 바이트를 출력하는 C 코드입니다. unsigned char 타입 오브젝트를 가리키는 포인터 byte_pointer 데이터 타입을 정의할 때 typedef를 사용했습니다. 이러한 바이트 포인터는 각 바이트가 양의 정수로 생각되어지는 바이트 집합을 참조합니다. 첫번째 루틴인 show-bytes는 바이트 포인터에 의해 나타나는 바이트 집합의 주소와 바이트 숫자가 주어집니다. 바이트 숫자는 size_t라는 데이터 타입을 가지면서 특정되어 집니다. size_t데이터 타입은 데이터 구조의 크기를 표현하는데 선호되는 타입입니다. 이렇게 하면 16진법으로 개별 바이트를 출력합니다. C formatting 지시자인 %.2x는 정수를 최소 2자리수까지 16진법으로 표현하라는 것을 나타냅니다.

show_int, show_float, show_pointer 프로시저들은 show_bytes 프로시저를 활용해 어떻게 C 프로그램 객체(int, float, void ) 바이트를 출력하는지 보여주고 있습니다. 단순히 show_bytes에 포인터 &x를 x인자로 넘겨 포인터를 (unsigned char)로 casting한 부분을 살펴보시기 바랍니다. 이 casting은 컴파일러에게 이 프로그램은 해당 포인터를 원래 데이터 타입 객체로 볼것이 아닌 단순한 바이트 연속으로 해석하라는 것입니다. 이 포인터는 오브젝트가 차지하는 가장 낮은 바이트 주소 입니다.

이 프로시저들은 C의 sizeof연산자를 활용해 오브젝트가 사용하는 바이트 크기를 나타냅니다. 일반적으로, sizeof(T) expression은 type T의 오브젝트를 저장하는데 필요한 바이트 크기를 반환합니다. 고정된 크기보다 sizeof를 사용하는 것은 다른 컴퓨터 타입에 호환되는 코드를 작성하기 위한 한 단계입니다.

위 코드를 몇개의 다른 컴퓨터들에서 돌리면 아래와 같은 결과들이 나옵니다. 해당 리스트는 어떤 컴퓨터들에서 돌렸는지에 대한 리스트입니다.

  • Linux 32: Intel IA32 processor running Linux
  • Windows: Intel IA32 processor running WIndows
  • Sun: Sun Microsystems SPARC processor running Solaris (These machines are now produced by Oracle)
  • Linux 63: Intel x86-64 processor running Linux

인자 값인 12,345는 16진법으로 0x00003039로 표현합니다. int 데이터에 대해 byte 정렬을 제외하고는 모두 동일한 값을 얻었습니다. 특히, 가장 덜 중요한 바이트 값인 0x39가 Linux 32, Windows, Linux 64에서 가장 먼저 나타난 것을 확인할 수 있습니다. 이렇게 보이는 컴퓨터들은 모두 little-endian 컴퓨터입니다. Sun은 그에 반해 big-endian 입니다. 유사하게 float 데이터도 바이트 정렬을 제외하고 같은 값을 가집니다. 그에 반해, 포인터 값은 완전히 다릅니다. 다른 기계와 운영체제 설정들은 저장부분 할당에 대해 다른 convention을 따릅니다. 한가지 기억할 특징은 Linux 32, Windows, Sun 컴퓨터는 4 바이트 주소를, Linux 64는 8 바이트 주소를 사용한다는 것입니다.

floating-point와 integer 데이터가 같은 숫자 값인 12,345를 인코딩하고 있지만 둘이 다른 바이트 패턴: 0x00003039가 integer, 0x4640E400가 floating-point인 것을 확인할 수 있습니다. 일반적으로 이 두가지 포맷은 다른 인코딩 스킴을 사용합니다. 만약 이 16진법 패턴들을 바이너리 폼형태로 바꾸고 이들을 적절히 이동시키면, 연속된 13개의 비트가 일치함을 확인할 수 있습니다. 아래 그림에서 *로 표시했습니다.

이것은 우연의 일치가 아닙니다. floating-point 포맷을 공부할 때 이 예시로 돌아오도록 하겠습니다.

Practice Problem 2.5

Practice Probelm 2.6

2.1.4 Representing Strings

C에서 문자열은 null문자(0값을 가집니다.)로 종료되는 문자 배열로 인코딩됩니다. 각 문자는 몇가지 기준 인코딩으로 표현됩니다. 그 중 가장 보편적인 것이 ASCII 문자 코드입니다. 따라서, 만약 show_bytes 루틴을 "12345"와 6(마지막 종료문자 포함) 인자들과 함께 동작하면 31 32 33 34 35 00라는 결과를 얻게됩니다. ASCII 십진수 자리수 x의 ASCII 코드가 0x3x인것과 동료되는 바이트가 0x00임을 확인할 수 있습니다. ASCII를 사용하는 어떤 시스템에서든 바이트 정렬과 워드크기에 상관없이 같은 결과를 확인할 수 있습니다. 결과적으로, 텍스트 데이터는 바이너리 데이터보다 플랫폼에 더 비의존적입니다.

Practice Problem 2.7

2.1.5 Representing COde

아래와 같은 C 함수가 있다고 해봅시다.

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

각 컴퓨터마다 생성된 기계 코드를 살펴보겠습니다.

Linux 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 c3

여기서 인스트럭션 값들이 다른 것을 확인할 수 있습니다. 다른 컴퓨터 타입들은 다르고 상호 호환되지 않는 인스트럭션들과 인코딩들을 가지고 있습니다. 심지어 같은 프로세서라 할지라도 다른 운영체제에서 동작하는 거라면 인코딩 convention이 다릅니다. 따라서 상호 호환되지 않습니다. 바이너리 코드는 컴퓨터와 운영체제간의 다른 조합일 경우 거의 호환되지 않습니다.

컴퓨터시스템의 근본적인 개념은 프로그램은 컴퓨터 시각에서 단순히 바이트의 연속이라는 것입니다. 컴퓨터는 원 소스 코드 프로그램에 대한 어떤 정보도 가지고 있지 않습니다.(디버깅을 돕기위한 몇몇 보조 테이블 제외) 이러한 것을 3장 machine-level 프로그래밍에서 더 자세히 살펴보도록 하겠습니다.

2.1.6 Introduction to Boolean Algebra

바이너리 값들은 컴퓨터가 정보들을 인코딩하고 저장하고 조작하는 방식에 있어 핵심적인 역할을 하기에, 0, 1을 연구함으로써 수학적 지식의 정수가 진화해 왔습니다. 이러한 연구는 George Boole 의 연구와 함께 1850즈음 시작되었고 이것이 Boolean algebra입니다. Boole는 논리 값인 TRUEFALSE를 바이너리 값인 1과 0으로 인코딩 함으로써 논리적인 추론의 기초적인 원리를 찝어낸 algebra를 공식화할 수 있었습니다.

가장 간단한 Boolean algebra는 집합 {0, 1}에서 정의됩니다.

위 그림을 보시면 boolean algebra의 몇몇 연산을 정의하고 있습니다. 이 연산들을 나타내는 기호들은 향후 얘기할 C bit-level 연산들에서 사용되는 기호들과 일치합니다. Boolean 연산 ~는 논리 연산자 NOT(기호로는 )과 상응합니다. 그 말은 ⌝P가 P가 true가 아닐때 true가 된다는 의미입니다. 이와 동일하게 ~p는 p가 0일 때 1이됩니다. Boolean 연산 &논리 연산 AND(기호로는 /\)와 동일합니다. P/\Q는 P와 Q가 모두 true일 때 true가 됩니다. 이와 동일하게 p & q는 p와 q 모두 1일 때 1이됩니다. Boolean 연산 |논리 연산 OR(기호로는 V)와 상응합니다. PVQ는 P 또는 Q 둘중 하나만 true여도 true입니다. p | q는 p 또는 q가 1이면 1입니다. Boolean 연산 ^는 논리 연산자 EXCLUSIVE-OR(기호로는 )와 상응합니다. P ⊕ Q는 P 또는 Q가 true일 때 true 입니다. (V와는 다른 점을 유의하시기 바랍니다. P와 Q가 모두 true이면 false입니다.) p ^ q는 p = 1이고 q = 0 이거나 p = 0이고 q = 1일때 1이됩니다.

Claude Shannon은 처음으로 디지털 논리와 Boolean algebra를 연결지은 사람입니다. 1937년 그의 석사 논문에서, 그는 전기공 연결 네트워크와 분석과 디자인에 Boolean algebra가 적용될 수 있음을 보여주었습니다. 비록 컴퓨터 기술이 그 이후로 엄청나게 발전했지만, Boolean algebra는 여전히 디지털 시스템 디자인과 분석에 있어 중심적인 역할을 하고 있습니다.

지금까지 본 4개의 Boolean 연산을 확장해서 고정된 w 크기의 0과 1로 구성된 문자열인 bit vectors에 적용할 수 있습니다. We define the operations over bit vectors according to their applications to the matching elements of the arguments. a와 b가 bit vector [a(w-1), a(w-2), ...., a(0)]과 [b(w-1), b(w-2), ...., b(0)]을 나타낸다고 해봅시다. We define a & b to also be a bit vector of length w, where the ith element equals ai & bi, for 0 ≤ i < w. The operations |, ^, and ~ are extended to bit vectors in a similar fashion.

예를 들어, w=4이고 a = [0110], b = [1100]인 경우 a & b, a | b, a ^ b, 그리고 ~b의 결과는 아래와 같습니다.

Practice Problem 2.8

Bit vector를 집합으로 표현할 수 있습니다. 예를 들어, a = [01101001] 을 A = {0, 3, 5, 6} (뒤에서부터 a(0)이라고 하고 1인 index값들을 집합에다 기록)으로 인코딩할 수 있습니다. 이러한 인코딩 집합 방식은 Boolean 연산 |&가 집합 union과 intersection과 상응하고 ~연산의 경우 집합 complement(여집합)와 상응합니다. 예시를 해보면 a = [01101001], A = {0, 3, 5, 6} b = [01010101], B = {0, 2, 4, 6}인 경우 a & b는 [01000001], A ∩ B = {0, 6} 이 됩니다.

실제 예시에서 bit vector 집합 인코딩 결과를 많이 보게될 것입니다. 예를 들어, 8장에서 여러 다른 signal들이 프로그램 실행 사이사이에 끼어드는 것을 보게될 것입니다. 여기서 bit-vector mask를 특정함으로써 signal을 기능하게 또는 기능할 수 없게 선택할 수 있습니다. Bit-vector mask는 bit 위치 i에서 1인 경우 signal i가 기능할 수 있고 0인 경우 기능할 수 없음을 나타냅니다. 따라서 mask가 가능한 signal들의 집합을 나타냅니다.

Practice Problem 2.9

2.1.7 Bit-Level Operation in C

C의 유용한 특징중 하나는 bitwise Boolean operation을 지원한다는 것입니다. 사실, 지금까지 사용했던 Boolean operation 기호들은 모두 C에서 사용하는 것들입니다. 이 연산들은 어떤 integral데이터 타입에도 사용가능합니다. 아래 예시는 char 데이터 타입 evaluation 표현 예시들입니다.

위 예시 처럼 bit-level 표현의 결과가 어떨지 정하는 가장 최선의 방법은 16진법을 2진법으로 변환하는 것입니다. 변환 후 2진법상에서 계산 후, 다시 16진법으로 되돌립니다.

Practice Problem 2.10

Practice Problem 2.11

bit-level 연산의 가장 일반적인 활용은 masking 연산을 구현하는 것입니다. 여기서 mask는 word안에서 선택된 비트 집합들을 나타내는 비트 패턴입니다. 예를 들어, mask 0xFF (가장 덜 중요한 8비트)는 워드상 low-order에 있는 바이트를 나타냅니다. Bit-level 연산 x & 0xFF는 x에서 가장 중요하지 않은 바이트 값을 가져올 것입니다. 하지만 나머지 부분은 전부 0이 되겠죠. 예를 들어, x = 0x89ABCDEF 이면 x & 0xFF는 0x000000EF라는 값이 될 것입니다. ~0은 데이터 크기에 상관없이 모든 1에 대한 mask를 가져올 것입니다. 같은 마스크로 데이터 타입이 int가 32 bit일때, 0xFFFFFFFF가 마스크로 사용될 수 있습니다.

Practice Problem 2.12

Practice Problem 2.13

2.1.8 Logical Operations in C

C는 또한 ||, &&, !등의 논리 연산자를 제공합니다. 각각은 OR, AND, NOT 논리 연산에 대응됩니다. 이 연산자들은 bit-level 연산들과 쉽게 혼동할 수 있습니다. 그렇지만, 동작 원리는 꽤 다릅니다. 논리 연산은 0이 아닌 인자들은 TRUE로서 해석하고 0을 FALSE로 해석합니다. 또한 1 또는 0을 반환하며 전자는 TRUE, 후자는 FALSE를 나타냅니다. 밑에는 표현식 평가 예시입니다.

비트 연산은 인수가 0 또는 1로 제한되는 특별한 경우에만 논리적 대응과 일치하는 동작을 가집니다.

논리 연산자 &&, || bit-level 연산 &, | 사이의 중요한 두번째 차이는 논리연산자의 경우 1번째 인자를 평가함으로써 표현식의 결과가 결정될 수 있으면 2번째 인자를 평가하지 않는다는 것입니다. 예를들어, a && 5/a 표현식은 절대 0으로 나누는 것을 하지 않게 되고, p && *p++의 경우 null pointer를 참조하지 않게 됩니다.

Practice Problem 2.14

Practice Problem 2.15

2.1.9 Shift Operations in C

C는 또한 비트 패턴을 왼쪽, 오른쪽으로 옮기는 shift 연산을 제공합니다. 피연산자 x가 bit 패턴 [x(w-1), x(w-2), ..., x(0)]을 가지고 있다고 했을때, 표현식 x << k는 bit 패턴 [x(w-k-1), x(w-k-2), ..., x(0),0, ...0]을 가지는 값을 생성합니다. 이 말은 즉, x가 왼쪽으로 k 비트만큼 움직였다는 의미입니다. 단, 이동하면서 가장 중요한 k 비트들을 버리고 k개의 0을 오른쪽에 채웁니다. 이동하는 횟수는 0 과 w-1사이가 되어야 합니다. Shift 연산은 왼쪽에서 오른쪽으로 진행되기 때문에, x << j << k와 (x << j ) << k는 동일합니다.

오른쪽 shift 연산 또한 존재하며 x >> k라고 작성합니다. 하지만 왼쪽 shift 연산과 미묘한 차이가 있습니다. 일반적으로, 컴퓨터들은 2개 형태의 오른쪽 shift 연산을 지원합니다.

  • Logical: 논리적 오른쪽 shift 연산은 왼쪽 끝을 k개의 0으로 채웁니다. 결과는 [0, ....0, x(w-1), x(w-2), ...., x(k)]가 됩니다.
  • Arithmetic: 수학적 오른쪽 shift 연산은 가장 중요한 bit를 k만큼 반복해서 왼쪽을 채웁니다. 그 결과는 [x(w-1), ...., x(w-1), x(w-1), x(w-2), .... x(k)]입니다. 이 convention은 다소 이상하게 보이지만, 나중에 살펴보게될 signed integer 데이터 연산에 유용합니다.

아래는 shift 연산을 8-bit 인자 x에 적용한 예시입니다.

결과 값들은 오른쪽(left shift) 또는 왼쪽(right shift)을 채우게 됩니다. 하나를 제외하고 모두 0으로 채워넣었습니다. 1로 채워넣은 예시는 [10010101]을 오른쪽으로 arithmetic하게 shift한 경우입니다. 가장 중요한 비트가 1이므로, 1을 채우는 값으로 사용했습니다.

C 표준은 signed 숫자를 가지고 어떤 right shift 연산을 해야하는지 명확히 정의하지 않습니다. 불행하게도 어떤 한 형태를 띠고 있는 코드는 잠재적으로 이식성 문제를 마주하게 될 수 있다는 것을 의미합니다. 하지만, 대부분 컴파일러와 컴퓨터 조합은 arithmetic right shift를 signed 데이터에 사용하고 많은 프로그래머들이 이러한 가정에 기반해 프로그램을 작성합니다. unsigned 데이터의 경우, right shift가 반드시 logical이어야 합니다.

C와 대조적으로, Java는 right shift가 어떻게 동작하는지 명확한 정의를 가지고 있습니다. x >> k는 arithmetic이고 x >>> k는 logical 입니다.

Practice Problem 2.16

profile
백엔드 개발자 디디라고합니다.

0개의 댓글