이전 글에서 PCX 스타일의 플래그를 사용하는 RLE 인코딩 방식을 살펴보았다. 이번 회에는 일반 BIN 파일에 대한 RLE 인코딩 방식에 대해 알아보자. BIN(Binary) 파일이란 ASCII 코드 만으로 되어있는 텍스트 파일에 비해 1byte에 0~255 어느 값이라도 사용될 수 있는 파일 형태이다.
ASCII 파일의 유래는 텍스트를 표현할 수 있는 디바이스( 모니터, 프린터, 터미널 등의 주변 기기)에
어째든 한글이 사용되는 파일의 경우 데이터 코드적 의미의 “텍스트 파일”은 없다. 파일의 확장자가 txt, html, xml 등 한글 또는 이진(binary) 값이 사용되었을 가능성이 있는 경우 모든 파일의 데이터는 바이너리로 취급해야 한다.
바이너리 파일, 혹은 일반 파일의 특징은 모든 가능한 데이터 심볼이 존재할 수 있다는 점이다. 엄밀한 의미에서, 데이터 압축에 있어서 “텍스트 파일”과 “바이너리 파일”의 차이점은 ‘0’ 값이 있고 없고의 차이이다. ‘0’ 은 보통 ‘Null’ 값으로 인지되고, 프로그램에서 텍스트 파일을 읽어드릴 때에 파일의 끝(EOF)으로 인식하는 경우가 많아 ‘0’ 값을 사용하는 텍스트 파일은 없거나, 있어도 깨진 파일 취급을 받게 된다.
데이터 내에 ‘0’ 값의 유무를 따지는 이유는 모든 데이터 압축의 인코딩은 소스 데이터 심볼을 디코딩이 필요한 인코딩 심볼 코드로 변경해야 하는데, 인코딩 데이터 용량의 최소화를 위해 하나의 bit, 하나의 심볼도 매우 중요해질 때가 있기 때문이다. 이 부분에 대해서는 글 후반에 기술해 보겠다. 우선 가장 보편적으로 사용할 수 있는 바이너리 파일 RLE 코드 생성 방법을 보자.
Run Length Encoding의 심볼과 코드 (BIN 방식)
Flag 방식과는 다르게 ESC(Escape) Sequnce를 사용한다. Escape Sequence란 일반적인 데이터의 흐름(stream)에서 벗어나 터미널이나 주변 디바이스를 제어하는 컨트롤 문자에서 그 뜻을 기원한다. 문서 작성 시 Enter 키를 치면 한 줄이 추가 되고 문서 앞으로 프롬프트가 이동하는 것과 같은 역할이다.
PCX와 같이 플래그를 쓰는 방식에 비해 인코딩이 매우 간단하다. 플래그를 쓰는 인코딩의 경우는 플래그에 지정된 코드를 통해서 한정된 정보 공간을 여러 용도로 사용하기 때문으로 정보의 다양성을 추구하는 대신 모든 코드에 플래그가 지정되어 데이터에 또 다른 잉여가 발생하는 원인이 된다. Esape Sequence는 일반적인 데이터 흐름에서 특정한 상황이 되었을 때에 추가되는 심볼이다. 위의 경우는 같은 심볼이 2개 중복 되면 2번째 중복된 심볼이 Escape Sequence를 발동 시켜 다음에 오는 코드의 수만큼 이전 심볼을 출력에 추가하라는 의미로 사용되었다.
단, 위의 예시의 뒷 부분의 ‘D’ 심볼이 2개가 반복되는 경우는 두 번째 ‘D’ 코드가 Escape Sequence로 해석되며 ‘0’ 개의 문자를 추가하라는 코드로 해석된다. 즉, 위의 RLE 방식에서는 소스 데이터에 2개만 반복되는 심볼들이 많이 존재하게 되면 ‘0’ 코드 값이 불필요하게 추가되는 인코딩 잉여가 발생하게 된다. 또, 위의 RLE 방식에서 심볼의 크기는 2bit 이상이어야 길이 값으로 의미가 있게 된다.
Note
최대 반복 카운트 = (2 ^ 심볼의 bit – 1) 심볼이 8bit: 1byte 인 경우 최대 255개의 반복된 길이를 하나의 시퀀스로 처리할 수 있다.Run Length Encoding C 소스 샘플
아래 간단한 로직의 C 소스가 있다. 위에 설명한 데로 동일 심볼이 2개 반복되면 Escape Sequence를 코딩 하여 출력한다.
unsigned int c_rle( uchar * ibuf, uchar * obuf, unsigned int bsize )
{
uchar * ip = ibuf, * ep = ip + bsize; // 소스 데이터 시작과 끝 포인터
uchar * op = obuf; // 출력 버퍼 시작 포인터
uchar c; // 현재 심볼
int iter = 0; // 중복 카운터
while( ip < ep )
{
c = *op++ = *ip++; // 입력 심볼을 출력 후 포인터 진행
if( *ip == c ) // 다음 심볼이 중복이라면
{
*op++ = c; ip++; // 심볼을 출력하고 포인터 진행
// 최대 255개까지 중복 탐색
for( iter = 0; *(ip + iter) == c && iter < 255 && (ip + iter) < ep; iter++ );
ip += iter; // 반복된 만큼 input 포인터를 앞으로
*op++ = iter; // 반복된 수를 값으로
}
}
return op - obuf; // 출력량을 리턴
}
디코딩은 것은 위의 인코딩 로직의 반대로 진행하면 된다.
uint d_rle( uchar * ibuf, uchar * obuf, uint bsize )
{
uchar * ip = ibuf; // 인코딩 버퍼의 시작 포인터
uchar * ep = ip + bsize; // 인코딩 버퍼의 끝 포인터
uchar * op = obuf; // 출력 버퍼의 시작 포인터
int last = -1; // 이전 심볼
uchar c; // 입력된 코드
while( ip < ep )
{
c = *op++ = *ip++; // 입력 심볼을 출력 버퍼로
if( c == last ) // 심볼이 이전과 같다면 다음이 카운트
{
int count = *ip++;
for( uchar i = 0; i < count; i++ ) *op++ = last;
}
last = c; // 현재 심볼을 이전 심볼로 이전
}
return op - obuf; // 디코딩된 출력 사이즈
}
Escape 심볼을 사용하는 RLE
위의 RLE 로직 이외에 특정 Escape 심볼들을 정해서 사용할 수도 있다. 만일 소스 데이터를 구성하는 심볼들의 사용 빈도를 RLE 이 전에 파악할 수 있다면( BWT의 경우 등 ) 가능한 데이터 심볼들 중에 전혀 사용되지 않았거나, 최소로 사용된 특정 심볼을 Escape 심볼로 정하여 좀 더 다양한 RLE 제어 컨트롤을 할 수 가 있다.
텍스트 파일의 경우 0x0, 0xff(255) 등과 같은 심볼은 거의 사용되지 않는다. 이럴 경우 1byte RLE 코드를 작성할 수 있다. 위 소스의 샘플 로직은 2개가 연속된 심볼의 경우 ‘0’ 값을 항상 추가로 코딩 해줘야만 한다. 매우 희귀한 경우이긴 하지만 원본 소스보다 더 커지는 경우도 생각할 수 있어 압축 대상 데이터의 특성에 대하여 충분히 파악한 상태에만 RLE 로직을 데이터 압축에 사용할 수 있다.
데이터 분석이 이루어지지 않았을 때에 미리 약속한 Escape symbol을 넣을 수도 있다. 예를 들어 xFE, xFD 와 같이 바이너리 파일에 잘 사용되지 않는 문자 2개가 반복될 때에 Escape symbol로 인식하게 하는 방식이다.
BMP – Cross-platform 비트맵 이미지
BMP는 Microsoft 사에서 만든 비트맵 이미지 포맷으로 Windows OS 전반에서 매우 중요한 이미지 포맷으로 사용하고 있다. BMP(Bitmap)는 압축 이미지 포맷이 아니라 DIB(Device Indepandant Bitmap)를 그 목적으로 하는 RAW 혹은 Raster Graphics 포맷이다. 다양한 영상 출력기들에 이미지 색상 정보, 알파 값, 크기, 원본 출처 등등의 메타 데이터를 포함하여 각 디바이스에서 어떻게 이미지를 표현할 지를 스스로 결정하여 표현하도록 한다.
초기 PC 시절 Apple, IBM, Sparc 등의 퍼스널 컴퓨터 영역과 그 주변 기기들은 모두 독자적인 그래픽 장치들을 가지고 있었고 ANSI 표준이 없었던 시절에 고안된 여러 DIB 중 Microsoft가 제안한 방식으로 내부적으로 데이터를 RLE 방식의 인코딩을 사용한다.
BMP 포맷에 RLE 혹은 RLE 밖에 사용하지 않은 것은 모든 디바이스에 호환될 수 있고, 모든 주변 기기에 장착된 MPU가 처리할 수 있을 정도로 알고리즘이 간단하기 때문이다. 4096 bytes 크기의 가용 메모리밖에 없는 디스플레이 장치를 상상해보자.
BMP에서는 x00 x00 배열을 Escape Sequence로 사용한다. x00, x00 두 심볼이 출현했을 때에 상위 2bits 의 값을 보고, 하위 bits에 담겨있는 값과 다음에 오는 코드의 의미를 해석한다.
| 00 | EOL( End Of Line ) |
| 01 | EOF( End Of File ) |
| 10 | 이미지 내 출력 픽셀 위치 변경 |
| 11 | RLE 반복 심볼 카운터 |
BMP는 RLE 방식의 인코딩을 하며 JPEG로 압축했을 때에 300K 수준의 이미지를 2M 크기로 보관하기도 하는 압축률에 있어서는 RLE 알고리즘이 큰 의미가 없지만 포맷 호환성은 극대화 하면서 무의미한 단 색 이미지의 데이터를 그대로 보관하는 최악의 경우는 피한 이미지 저장 방식이다. 또한, 간단한 이미지 압축 방식으로 해서 CPU의 자원을 사용을 최소화한 이미지 압축 포맷으로 OS 부팅 시의 로고 화면이나 빠른 윈도우 배경화면 변환 등에 유용하다.
Run Length Encoding 결론
RLE의 용도는 컴퓨팅 파워가 미약하거나, CPU 사용을 최소화 하며 이미지 크기에서 최악의 경우를 피하려고 하는 경우 이거나, 소스 데이터가 RLE에 매우 적합할 때에 간단하게 구현할 수 있는 압축 알고리즘이다.
이상 압축 알고리즘 중 가장 간단한 형태인 RLE에 대해 알아보았다. PCX 방식은 1980 ~ 1990년대 초반까지… XT PC에서 286 초기 시절까지 우리가 흔하게 만났던, 우리에게는 그 시절에 꼭 필요했고 대단히 유용한 이미지 압축 방식이었다. 현재에도 데이터 압축에 있어서 매우 중요한 알고리즘으로 새로운 데이터 처리 과정을 고안할 때에 가장 먼저 적용 가능성을 고려해 보는 기본 중의 기본 알고리즘이라 하겠다.
2400 MNP 모뎀이라는 용어를 기억하시는가? 다음은 모뎀과 팩스에 관련된 압축 이야기를 해보겠다.
이전 글 : Run Length Encoding( PCX )
