비트 레벨에서 연산이 필요한 프로그램들: 시스템 프로그램(컴파일러와 운영체제), 암호화, 그래픽, 빠른 연산과 효율적인 공간 사용이 필요한 프로그램들
이 장에 소개되는 테크닉들은 메모리에 데이터가 저장되는 방식에 종속적이며 기계와 컴파일러에 매우 종속적이다. 따라서 이러한 방법에 의존하는 것은 프로그램의 portability를 감소시킬 가능성이 높다. 절대적으로 필요한 상황이 아니면 피하는 것이 좋으며, 사용할 때는 꼭 documentation을 해야 한다.
20.1 Bitwise Operators
6개의 bitwise operators가 존재함
Bitwise Shift Operators
integer의 binary representation의 비트들을 왼쪽 또는 오른쪽으로 shift한다.
<< 와 >> 연산의 피연산자는 char를 포함한 모든 정수형 타입이다. integer promotion은 양쪽 피연산자에 대해 모두 이루어지며, 결과의 타입은 promotion 후의 left 연산자 type과 같다.
i << j의 값은 i 내의 bit들이 왼쪽으로 j자리만큼 shift되었을 때의 값이다. i의 왼쪽 끝으로 밀려서 사라지는 숫자만큼 오른쪽에 0 bit가 들어온다. i >> j의 값은 i가 오른쪽으로 j자리만큼 shift된 값이다. 만약 i가 unsigned type이거나 i가 음수가 아닌 수이면, 필요한 만큼 왼쪽 자리에 0이 추가된다. i가 음수인 경우, 결과는 implementation-defined. 어떤 implementation들은 왼쪽 끝에 0을 더하고, 1들을 더해서 sign bit를 보존하는 것들도 있다.
C99 표준 6.5.7 중
If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.
portalbility를 위해, shift 연산을 unsigned number에만 사용하는 것이 좋다.
unsigned short i, j;
i = 13; /* i is now 13 (binary 0000000000001101) */
j = i << 2; /* i is now 52 (binary 0000000000110100) */
j = i >> 2; /* i is now 3 (binary 0000000000000011) */
두 연산자 모두 피연산자의 값을 수정하지는 않는다. 변수의 값을 수정할 때는 compound assignment operators(<<=, >>=)를 사용한다.
Bitwise Complement, And, Exclusive Or, and Inclusive Or
나머지 4개의 bitwise 연산자들
~연산자는 unary(단항)이다. integer promotion은 그 피연산자에 적용된다.
다른 연산자들은 binary(이항)이다.
~, &, ^, | 연산자들은 피연산자들의 모든 bit에 대해 Boolean 연산을 수행한다.
~: 피연산자의 complement를 생산. 0이 1로, 1이 0으로 대체된다.
&: 두 피연산자의 대응되는 모든 비트에 대해 Boolean and 연산 수행
^: 두 피연산자의 대응되는 모든 비트에 대해 Boolean or 연산 수행 (두 비트가 모두 1이면 0 생산)
|: 두 피연산자의 대응되는 모든 비트에 대해 Boolean or 연산 수행 (두 비트가 모두 1이면 1 생산)
unsigned short i, j, k;
i = 21; /* i is now 21 (binary 0000000000010101) */
j = 56; /* j is now 56 (binary 0000000000111000) */
k = ~i; /* k is now 65514 (binary 1111111111101010) */
k = i & j; /* k is now 16 (binary 0000000000010000) */
k = i ^ j; /* k is now 45 (binary 0000000000101101) */
k = i | j; /* k is now 61 (binary 0000000000111101) */
~i의 값은 unsigned short의 값이 16비트를 차지한다는 가정 하의 값이다.
~연산자는 포터블한 low-level program을 만드는데 도움이 된다. integer에 몇개의 비트가 포함되는지 모르더라도, 모든 비트가 1인 integer를 ~0으로 표현할 수 있다. 비슷하게 마지막 5개의 비트를 제외한 모든 비트가 1인 integer는 ~0x1f로 표현할 수 있다.
4개의 연산자들 간 우선순위는 ~, &, ^, | 순이다.
&, ^, | 에 대한 compound assignment operators: =&, =^, =|
Using the Bitwise Operators to Access Bits
low-level programming을 할 때, 종종 정보를 하나의 비트, 또는 비트의 모음에 저장하게 된다. 예를 들어 그래픽 프로그램에서는 두개 또는 그 이상의 픽셀을 고작 1바이트 공간에 저장하기도 한다. bitwise 연산자들을 사용해서 몇개의 bit들에 저장되어 있는 데이터를 추출하거나 수정할 수 있다.
i가 16비트 unsigned short 변수라고 가정하자. i의 가장 왼쪽(most significant) 비트의 번호를 15로 붙이고 가장 오른쪽(least significant) 비트의 번호를 0으로 붙이자.
LSB 0 numbering : https://en.wikipedia.org/wiki/Bit_numbering
Setting a bit. i의 4번 비트를 set하려면 i의 값과 상수 0x0010(4번 자리에 1을 담은 "mask")와 비트 or 연산을 수행한다.
i = 0x0000; /* i is now 0000000000000000 */
i |= 0x0010; /* i is now 0000000000010000 */
i |= 1 << j; /* sets bit j */
Clearing bit. i의 4번 비트를 clear하려면 4번 자리가 0, 나머지 모든 비트는 1인 마스크를 사용한다.
i = 0x00ff; /* i is now 0000000011111111 */
i &= ~0x0010; /* i is now 0000000011101111 */
i &= ~(1 << j); /* clears bit j */
Testing a bit. 다음 if문은 i의 4번 비트가 set되었는지 테스트한다.
if (i & 0x0010) ... /* tests bit 4 */
if (i & 1 << j) ... /* tests bit j */
더 쉽게 비트들을 다루기 위해서 비트에 이름을 붙일 수 있다. 0, 1, 2번 비트가 각각 파랑색, 녹색, 빨강색에 대응한다고 가정하면,
#define BLUE 1
#define GEEEN 2
#define RED 4
i |= BLUE; /* sets BLUE bit */
i &= ~BLUE; /* clears BLUE bit */
if (i & BLUE) ... /* tests BLUE bit */
i |= BLUE | GREEN; /* sets BLUE and GREEN bits */
i &= ~(BLUE | GREEN); /* clears BLUE and GREEN bits */
if (i & (BLUE | GREEN)) ... /* tests BLUE and GREEN bits */
Using the Bitwise Operators to Access Bit-Fields
여러 개의 연속된 비트들(a bit-field)을 다루는 방법이다.
Modifying a bit-field. a bit-field를 수정하려면 bitwise and(bit-field를 clear하기 위해)를 사용하고, 그 뒤에 bitwise or(bit-field에 새 비트들을 저장하기 위해)를 사용한다. 다음 문장은 변수 i의 4-6번 비트에 binary 값 101을 저장한다.
i = i & ~0x0070 | 0x0050; /* stores 101 in bits 4-6 */
& 연산자는 i의 4-6번 비트를 clear한다. | 연산자는 6번, 4번 비트를 set한다. 이것을 조금 더 일반화하기 위해, j는 i의 4-6번째 비트에 담길 값을 저장하고 있다고 가정하자. bitwise or 연산 수행 전에 j를 shift해야 한다.
i = (i & ~0x0070) | (j << 4); /* stores j in bits 4-6 */
i = i & ~0x0070 | j << 4; /* | operator has lower precedence than & and << */
Retrieving a bit-field. bit-field가 오른쪽 끝에 있으면, 그 값을 얻는 것은 쉽다. 다음 문장은 변수 i의 0-2번째 비트를 얻는다.
j = i & 0x0007; /* retrieves bits 0-2 */
bit-field가 i의 오른쪽 끝에 있지 않은 경우, 우선 bit-field가 오른쪽 끝에 자리잡도록 shift한 뒤에 위와 동일한 방법을 쓰면 된다. 다음 문장은 i의 4-6번째 비트를 얻는다.
j = (i >> 4) & 0x0007; /* retrieves bits 4-6 */
xor.c
/* Performs XOR encrpytion */
#include <ctype.h>
#include <stdio.h>
#define KEY '&'
int main(void)
{
int orig_char, new_char;
while ((orig_char = getchar()) != EOF) {
new_char = orig_char ^ KEY;
if (isprint(orig_char) && isprint(new_char))
putchar(new_char);
else
putchar(orig_char);
}
return 0;
}
20.2 Bit-Fields in Structures
앞서 살펴본 bit-fields를 다루는 방법들은 까다롭고 헷갈리기 쉽다. 그 대안으로 C에서는 멤버들이 bit-field의 길이를 나타내는 구조체를 선언하는 것을 제공한다.
예를 들어 MS-DOS에서 파일이 생성되거나 수정되는 시점의 날짜를 어떻게 저장하는지 알아보자. days, months, years가 작은 숫자이므로, 보통의 정수형 변수에 이것들을 저장하는 것은 공간을 낭비한다. 그 대신 DOS에서는 날짜를 위해 단 16비트만 할당한다. 날짜를 위해 5비트, 달을 위해 4비트, 연도를 위해 7비트.
bit-field를 이용해, 다음과 같이 위 그림과 같은 구조체를 정의한다.
struct file_date {
unsigned int day: 5;
unsigned int month: 4;
unsigned int year: 7;
};
각각의 멤버 뒤에 있는 숫자는 그 멤버의 비트 길이를 나타낸다. 모든 멤버가 같은 타입을 가지므로, 다음과 같이 선언을 줄일 수 있다.
struct file_date {
unsigned int day: 5, month: 4, year: 7;
};
bit-field의 타입이 될수 있는 것은 int, unsigned int, signed int 밖에 없다. int를 사용하는 것은 모호하다. 어떤 컴파일러는 필드의 가장 높은 순서의 비트를 sign 비트로 간주하고, 다른 컴파일러는 그렇지 않다. portability를 위해서 모든 bit-field를 unsigned int 또는 signed int로 선언하는 것이 좋다.
(C99) C99에서는 bit-field의 형식이 _Bool이 될 수 있다. C99 컴파일러는 추가로 다른 형식을 허용할 수도 있다.
다음과 같이 bit-field를 구조체의 다른 멤버와 같이 사용할 수 있다.
struct file_date fd;
fd.day = 28;
fd.month = 12;
fd.year = 8; /* represents 1988 */
다른 평범한 구조체의 멤버와 같이 bit-field를 사용하면 된다.
year 멤버는 1980년을 기준으로 저장된다(마이크로소프트에 따르면 세계가 시작된 해)
bitwise 연산을 사용해도 같은 결과를 얻을 수 있고, bitwise 연산자를 쓰는 것이 약간 더 빠르다. 하지만 보통은 몇 마이크로초를 절약하는 것 보다 읽기 쉬운 프로그램을 작성하는 것이 낫다.
bit-field가 다른 구조체 멤버에 비해 가지고 있는 제한이 하나 있는데 bit-field는 일반적인 의미의 주소를 가지고 있지 않기 때문에, bit-field에 주소 연산자(&)를 사용할 수 없다. 따라서 scanf 같은 함수는 bit-field에 직접 데이터를 저장하지 못한다.
scanf("%d", &fd.day); /*** WRONG ***/
물론 scanf를 통해 다른 평범한 변수에 값을 저장하고 fd.day에 할당하는 것은 괜찮다.
How Bit-Fields Are Stored
C 표준에서는 bit-field를 어떻게 저장할 지에 대해 컴파일러에게 상당한 자유를 허용한다.
컴파일러가 bit-field를 다루는 규칙은 "storage units"의 개념에 따라 달라진다. storage unit의 크기는 implementation-defined이며, 통상적인 값은 8 bits, 16 bits, 32 bits이다. 구조체 선언을 처리할 때, 컴파일러는 다음 bit-field를 위한 공간이 없을 때까지 bit-field들을 하나씩 storage unit에 채우며, 각 필드 사이에는 공간을 남기지 않는다. 다음 필드를 위한 공간이 없게 되면, 어떤 컴파일러는 다음 storage unit으로 넘어가고, 또 어떤 컴파일러는 bit-field를 storage unit들 여러개에 걸쳐서 저장한다. (implementation-defined) bit-field가 저장되는 순서(왼쪽->오른쪽 또는 오른쪽->왼쪽)도 implementation-defined이다.
위에서 사용한 예시인 file_date는 storage unit이 16비트라고 가정한다(8비트인 경우도 컴파일러가 month 필드를 두개의 storage unit에 걸쳐 저장한다면 괜찮다). 또 비트 필드가 오른쪽에서부터 왼쪽으로 할당된다고 가정한다.
bit-field의 이름을 생략해도 된다. 이름 없는 비트 필드는 다른 비트 필드들이 제대로 자리를 잡도록 해주는 역할을 할 수 있다. DOS 파일에서 시간은 다음과 같이 저장된다.
struct file_time {
unsigned int seconds: 5;
unsigned int minutes: 6;
unsigned int hours: 5;
};
(0-59를 저장하는 데 단 5비트만 쓰이는 이유는 DOS에서 초를 2로 나누어서 0부터 29까지의 값으로 저장하기 때문이다.)
만약 seconds field에 관심이 없다면, 그 이름을 비워놓으면 된다.
struct file_time {
unsigned int : 5; /* not used */
unsigned int minutes: 6;
unsigned int hours: 5;
};
나머지 비트 필드들은 seconds 필드가 여전히 존재하는것과 동일하게 정렬된다.
이름 없는 비트 필드의 길이를 0으로 지정할 수도 있다. 이것은 컴파일러에게 다음 비트 필드를 storage unit이 시작되는 곳에 저장하라고 보내는 신호이다.
struct s {
unsigned int a: 4;
unsigned int : 0; /* 0-length bit-field */
unsigned int b: 8;
만약 storage unit의 크기가 8비트인 경우, 컴파일러는 a 멤버를 위해 4비트를 할당하고, 다음 storage unit까지 4비트를 넘기고, b 멤버를 위해 8비트를 할당한다. storage unit의 크기가 16비트인 경우, a를 위해 4비트를 할당하고, 12비트를 넘기고, b를 위해 8비트를 할당한다.
20.3 Other Low-Level Techniques
Defining Machine-Dependent Types
char type은 정의에 의해 1바이트를 점유하기 때문에, character 형식을 byte로 다루기도 한다. 문자 형태가 되지 않아도 되는 데이터를 char 형식으로 저장하는 것이다. 이럴 때는 BYTE type을 정의하는 것도 좋다.
typedef unsigned char BYTE;
machine에 따라, 추가적인 타입을 정의하고 싶을 수 있다. x86 아키텍쳐에서는 16비트 words를 광범위하게 사용하므로, 해당 플랫폼에서는 다음 정의가 유용할 것이다.
typedef unsigned short WORD;
이 BYTE와 WORD 타입은 이후의 예제에서 사용된다.
Using Unions to Provide Multiple Views of Data
C에서 공용체는 때때로 원래 의미와는 완전히 다른 목적 - 메모리 블록을 둘 또는 이상의 측면에서 보는 것 - 으로 사용된다.
위에서 썼던 file_date 구조체를 보면, 이 구조체는 2바이트에 해당한다. 따라서 모든 2바이트 값을 file_date 구조체로 볼 수 있다. 특히 unsigned short 값을 file_date 구조체로 볼 수 있을 것이다(short integer의 크기가 16비트라는 가정 하에). 다음 공용체는 short integer를 파일의 날짜로, 또는 그 역으로 변환하기 쉽게 해 준다.
union int_date {
unsigned short i;
struct file_date fd;
};
이 공용체를 통해, 2바이트로 저장된 값을 extract해서 month, day, year 필드를 얻을 수 있다. 역으로, 날짜를 file_date 구조체로 만들어서 2바이트로 저장할 수 있다.
아래 함수는 unsigned short 인자를 전달받아 그것을 파일의 날짜 형태로 출력한다.
void print_date(unsigned short n)
{
union int_date u;
u.i = n;
printf("%d/%d/%d\n", u.fd.month, u.fd.day, u.fd.year + 1980);
}
공용체를 이용해 데이터를 여러 측면에서 보는 것은 register(종종 작은 unit으로 나눠짐)를 다룰 때 특히 유용하다. 예를 들어 x86 프로세서는 AX, BX, CX, DX라는 16비트 레지스터를 가지고 있다. 각각의 레지스터는 두개의 8비트 레지스터로 취급 가능하다. 예를 들어 AX는 두개의 레지스터 AH와 AL로 나눠진다(H and L stand for "high" and "low").
AX, BX, CX, DX 레지스터를 표현하는 변수를 만들려면: 16비트, 8비트 레지스터 모두에 접근할 수 있어야 하고, 레지스터들의 관계도 성립해야 한다(AX를 수정하면 AH와 AL 모두에게 영향을 미치고, AH나 AL을 수정하면 AX도 수정됨). 아래의 공용체는 두개의 멤버를 가지고 있다. 한 멤버는 16비트 레지스터에 대응하는 구조체이고, 다른 멤버는 8비트 레지스터에 대응하는 멤버를 갖는 구조체이다.
union {
struct {
WORD ax, bx, cx, dx;
} word;
struct {
BYTE al, ah, bl, bh, cl, ch, dl, dh;
} byte;
} regs;
word 구조체의 멤버는 byte 구조체의 멤버와 겹쳐진다. ax는 al, ah와 같은 메모리를 점유한다. regs 공용체는 다음과 같이 사용될 수 있다.
regs.byte.ah = 0x12;
regs.byte.al = 0x34;
printf("AX: %hx\n", regs.word.ax); /* AX: 1234 */
byte 구조체에서 AL 레지스터가 "low" half이고 AH 레지스터가 "high" half인데도 al이 ah보다 먼저 온다는 점을 유의하자. 1바이트를 넘는 데이터 아이템이 저장될 때, 그것을 메모리에 저장하는 논리적 방법은 두 가지가 있다. 가장 왼쪽에 있는 바이트에 먼저 저장하는 "자연스러운" 순서대로 하는 방법이 있고, 가장 왼쪽에 있는 바이트에 가장 나중에 저장하는 반대 순서대로 하는 방법이 있다. 전자는 big-endian이라고 불리고, 후자는 little-endian이라고 불린다. 이 순서는 C가 아닌 프로그램을 실행하는 CPU에 의해 결정된다. 그런데 x86 프로세서들은 데이터가 little-endian으로 저장된다고 가정한다. 따라서 regs.word.ax의 첫번째 바이트가 low byte가 된다.
Using Pointers as Address
11.1에서 포인터는 메모리 주소의 어떤 종류이고, 그 자세한 사항을 알 필요는 없다고 했었지만 low-level 프로그래밍을 하게 되면 디테일이 중요하다. 주소는 종종 integer(또는 long integer)와 같은 비트 갯수를 갖고 있다. 특정 주소를 나타내는 포인터를 만드는 것은 쉽다: integer를 포인터로 cast하면 된다. 예를 들어 다음과 같이 주소 1000(hex)를 포인터 변수에 저장할 수 있다.
BYTE *p;
p = (BYTE *) 0x1000; /* p contains address 0x1000 */
Viewing Memory Locations
이 프로그램은 메모리 세그먼트를 보여준다. 대부분의 CPU는 프로그램을 "protected mode"로 실행하기 때문에 프로그램에서는 해당 프로그램에 속해 있는 부분의 메모리에만 접근할 수 있다. 이것은 한 프로그램이 다른 프로그램에 속하거나, 운영체제에 속한 메모리에 접근하거나 수정하려는 것을 방지한다. 따라서 이 프로그램으로는 프로그램 자체에 할당된 메모리 영역에만 접근이 가능하다. 이 지역을 벗어나면 프로그램이 깨진다.
viewmemory.c는 우선 자체의 main 함수의 주소와, 한 변수의 주소를 출력한다. 이를 통해 사용자는 어떤 메모리 영역을 탐색할 수 있는지를 짐작할 수 있다.
여기서는 int 값이 32비트로 저장되고, 주소 값도 32비트로 저장된다고 가정한다. 주소는 관습적으로 16진수 형태로 출력된다.
viewmemory.c
/* Allows the user to view regions of computer memory */
#include <stdio.h>
#include <ctype.h>
typedef unsigned char BYTE;
int main(void)
{
unsigned int addr;
int i, n;
BYTE *ptr;
printf("Address of main function: %x\n", (unsigned int) main);
printf("Address of addr variable: %x\n", (unsigned int) &addr);
printf("\nEnter a (hex) address: ");
scanf("%x", &addr);
printf("Enter number of bytes to view: ");
scanf("%d", &n);
printf("\n");
printf(" Address Bytes Characters\n");
printf(" ------- ------------------------------- ----------\n");
ptr = (BYTE *) addr;
for (; n > 0; n -= 10) {
printf("%8X ", (unsigned int) ptr);
for (i = 0; i < 10 && i < n; i++)
printf("%.2X ", *(ptr + i));
for (; i < 10; i++)
printf(" ");
printf(" ");
for (i = 0; i < 10 && i < n; i++) {
BYTE ch = *(ptr + i);
if (!isprint(ch))
ch = '.';
printf("%c", ch);
}
printf("\n");
ptr += 10;
}
return 0;
}
%X conversion specifier는 %x과 유사하며, 16진수 A, B, C, D, E, F를 대문자로 표시한다.
리눅스에서는 main 함수의 앞쪽 영역을 표시했을 때, ELF라는 글자를 볼 수 있다. 나는 해볼수 없어서 생략.
addr 변수의 주소를 입력했을 때에는, 입력한 addr 변수의 값을 그대로 관찰할 수 있다.
addr의 주소인 0022FE38에 들어간 값은 38 FE 22 00이다. 이것을 거꾸로 하면 00 22 FE 38로 입력된 값이 된다. 순서가 거꾸로 된 이유는 앞서 살펴본 대로 x86 프로세서에서 리틀 인디언 방식으로 데이터를 오른쪽 바이트부터 저장하기 때문이다.
The volatile Type Qualifier
어떤 컴퓨터에서는 특정 메모리 영역은 "volatile"하다. 그 영역에 저장된 데이터는 프로그램이 실행되는 중에 바뀔 수 있다. 프로그램 자체적으로 그곳에 새로운 값을 저장하지 않을 때에도 바뀔 수 있다. 예를 들어 어떤 메모리 영역은 입력 장치에서 직접 전달되는 데이터를 저장할 수 있다.
volitle type qualifer를 사용해서 프로그램에서 사용되는 데이터 중 volatile 데이터가 있는지를 알려줄 수 있다. volatile은 보통 volatile한 메모리 영역을 가리키는 포인터 변수를 선언할 때 나타난다.
volatile BYTE *p; /* p will point to a volatile byte */
왜 volatile이 필요할까? p를 사용자가 가장 마지막으로 입력한 문자를 담는 메모리를 가리킨다고 가정하자. 이 영역은 volatile하다. 사용자가 키보드에서 문자를 입력할 때마다 그 값이 바뀌기 때문이다. 다음 반복문을 사용해서 키보드로 입력받은 문자들을 얻고 버퍼 배열에 저장할 수 있다.
while (buffer not full) {
wait for input;
buffer[i] = *p;
if (buffer[i++] == '\n')
break;
}
수준 높은 컴파일러는 이 반복문에서 p와 *p의 값을 변경시키지 않는다는 것을 인식해서, *p을 값을 단 한번만 얻게 해서 프로그램을 최적화하려고 할 수도 있다.
store *p in a register;
while (buffer not full) {
wait for input;
buffer[i] = value stored in register;
if (buffer[i++] == '\n')
break;
}
이 최적화된 프로그램에서는 우리의 의도와는 달리 버퍼에 동일한 문자만 계속 채워질 것이다. p가 volatile 데이터를 가리킨다고 선언함으로써 컴파일러에게 *p의 값을 그것이 필요할 때 마다 매번 메모리 영역에서 얻어와야 한다는 것을 알려주게 된다.