0. 손실, 비손실 압축
손실 압축과 비손실 압축이라는 단어를 한번쯤을 들어보았을 것이다. 손실 압축은 말 그대로 원본의 데이터를 압축한 후 이 압축을 풀었을 때의 데이터가 원본 데이터와는 100% 동일하지 않은 압축을 말한다. 그림이나 동영상, 음성 데이터 등은 원본과 100% 같지 않아도 데이터를 사용하는 것이 가능하므로 약간의 손실을 갖지만 높은 압축율을 갖는 손실 압축을 주로 사용하게 된다. 그에 반해 TEXT 데이터나 GBA에서 사용되는 폰트 데이터 등 약간의 손실로도 원본 데이터를 알아보는데 지장이 생긴다면 압축을 하지 않으니만 못할 것이다. 따라서 이 경우에는 압축율이 다소 낮지만 원본의 데이터가 100% 복원되는 비손실 압축이 주로 사용된다. 손실 압축과 비손실 압축의 구분은 본 강좌에서 그다지 큰 영향을 갖지는 않으나 앞으로 소개할 알고리즘이 비손실 알고리즘이라는 사실은 기본적으로 알아두시길.
1. RLE(Run Length Encoding)란?
만약 33 33 33 33 33 33 33 이라는 데이터가 존재한다면 어떻게 압축을 하면 될까?
대부분의 사람들이 33이 7개 연속으로 존재한다고 저장하면 되지 않겠는가 하는 생각을 할 것이다.
이런 기본적인 concept으로부터 시작하는 압축 알고리즘이 RLE방식이다.
RLE방식은 한 문자(한 byte)가 몇 번 반복되는지를 저장하는 방식이다. 따라서 RLE방식은 같은 문자가 여러번 반복되는 데이터에 대해 효율적인 압축방법이 되리란 것을 쉽게 예상할 수 있을 것이다. 텍스트의 경우 여러번 반복되는 데이터가 존재하기 힘드므로 텍스트를 RLE로 압축할 경우 효율이 낮고 오히려 압축데이터의 크기가 더 커지는 경우가 허다하다. 게임을 시작할 때의 로고를 생각해보자. 대부분 검은 바탕이나 단색바탕에 로고 자체도 매우 단순하여 타일전체가 단색인 경우가 많다. 따라서 이런 그림의 경우에 RLE방식으로 압축하는 게 효율적일때가 많다.
2. 어떻게 압축하면 될까?
0x33이라는 문자가 7번 반복된다는 사실을 어떻게 저장하면 될까.
반복되는 문자 뒤에 반복회수를 적어준다면 33 07 형태가 되는데 이 방법에는 약간의 문제가 있다.
만약 01 02 03 04 형태의 데이터가 존재한다면 01 01 02 01 03 01 04 01 로 저장해야 되는데 이 경우 데이터가 2배로 늘어나게 되므로 "압축"의 의미와는 다소 거리가 멀게 된다.
그렇다면 반복되는 문자가 존재할 때만 "반복이 시작된다"의 의미를 갖는 문자가 나타나게 한다면 0x01 0x02 0x03 0x04는 그대로 01 02 03 04 로 저장하면 될 것이다. 편의상 이 문자를 < 로 표현하도록 하겠다. 주의할 점은 반복이 시작됨을 알리는 구분자(separator)가 '<'가 아닐수도 있다는 점이다.
구분자는 알고리즘을 구현하는 사람 맘대로 결정하는 것이 가능하다.
그럼 이 구분자 < 로 RLE방식으로 압축해 보도록 하자. 주어진 데이터는 다음과 같다.
33 33 33 33 33 33 33 11 11 11 22 33 22
33이 7번 반복되고 11 이 3번, 22 33 22 는 반복되는 문자가 없다는 것을 알 수 있다.
그러면 이를 압축할 경우
< 33 07 < 11 03 22 33 22
의 형태로 압축이 되는 것이다. 33의 경우 7개의 바이트가 단지 3바이트만으로 표현되므로 50% 이상 압축되었다. 그러나 11의 경우 3바이트를 압축하여 3바이트가 되었으므로 압축하지 않는 것과 그 크기가 같으므로 압축의 의미를 갖지 못하게 된다. 따라서 이 방식으로 압축할 경우 4바이트 이상 반복되는 문자가 출현할 경우 압축을 시도하면 될 것이다.
그런데 이 방식으로 저장할 경우 구분자와 같은 문자가 출현할 경우 압축 데이터가 판별하기 모호해지게 된다. 구분자로 < 를 사용하는데 데이터 중 < 라는 데이터가 존재할 경우 위의 방식을 그대로 적용하면
< < 33 33 =>(압축)=> < < 33 33
과 같이 저장되게 된다. 그렇다면 이를 역으로 압축을 해제할 경우 제대로 압축이 해제 될리가 없다.
구분자 < 가 출현했으니 그 다음 바이트 < 가 33번 반복된다는 의미를 갖는다고도 볼 수 있으므로 원래의 데이터와는 달라져버린다. 따라서 구분자로 사용되는 문자가 출현할 경우에는 별도의 압축 방법을 생각해야 한다.
이 경우 구분자가 문자로 출현할 경우 구분자를 한번 더 써주는 방식을 택하면 된다.
위의 데이터를 압축한다면
< < < < 33 33
이 되는데 < 뒤에 <가 존재할 경우 <를 그대로 저장하는 것이므로 이 방식으로 압축을 해제할 경우
< < 33 33
으로 원하는 결과를 얻을 수 있게 된다. 이 방법은 위에서와 마찬가지로 구분자가 두배의 용량이 된다는 단점이 있으므로 전체 데이터에서 출현 빈도수가 낮은 문자를 구분자로 사용하면 가능한한 효율을 높일 수 있게 된다.
여기서 설명한 방식은 RLE방식의 한가지 방법일 뿐이다. 압축알고리즘이 워낙 간단한데가 구현이 간단해 수많은 압축형식이 있을 수 있다. 따라서 앞의 설명은 RLE가 뭐다 라는 정도의 설명이라고만 생각해도 충분하다.
3. GBA에서의 구현방식
GBA에서는 압축데이터 앞에 4 바이트의 헤더가 존재한다. 이 4 byte를 뒤에서부터 읽어들인다.
왜 뒤에서부터 읽는가에 대한 내용은 빅 엔디언, 리틀 엔디언의 차이이므로 관심이 있는 사람은 이에 대해 찾아보면 금방 이해할 수 있을 것이다. 어쨌든 이 4 byte의 정보가 압축 데이터에 대한 내용을 담고 있다.
30 00 0e 00 .. .. .. .. ..
이라면 4byte를 뒤에서부터 읽을 경우 00 0e 00 30 이 된다. 이 때 맨 뒤의 바이트는 압축방법에 대한 정보를 담고 있고 앞의 세 바이트는 압축을 풀었을 때의 크기를 담고 있다.
맨 뒤의 바이트가 30 인 것은 이 데이터가 RLE방식으로 압축되었다는 것을 의미하고 앞의 세 바이트 00 0e 00은 압축을 해제했을 때의 데이터의 크기가 0e 00 즉 0xe00 byte가 된다는 것을 의미한다.
그 뒤의 데이터는 역시 위에서 설명한 RLE방식으로 압축되어 있으나 GBA에서 사용하는 방식은 약간 다르다. GBA에서는 Flag_byte(앞에서의 구분자 역할) 1 byte 뒤에 Data_byte N byte가 뒤따르는 방식을 사용한다. 이 설명만으로는 정확한 압축 방법을 알기 힘들테니 우선 Flag_byte에 어떤 정보가 담겨 있는지 알아보자.
Flag_byte는 1 byte이므로 8 bit 인데 MSB는 압축이 되었는가에 대한 정보를 갖고 있고 MSB를 제외한 bit들은 반복횟수를 의미한다.
Flag_byte : _ _ _ _ _ _ _ _
^
1이면 압축데이터, 0이면 압축되지 않은 데이터
가 된다. 따라서 압축이 되었는지의 여부는 ( flag_byte & 0x80 ) 으로 알 수 있고 반복 횟수는 ( flag_byte & 0x7f ) 로 알 수 있다.
우선은 Flag_byte를 읽어 압축이 되었는가, 반복 횟수는 몇번인가 를 알 수 있을 것이다.
압축이 되었을 경우, 즉 Flag_byte가 1일 경우 Flag_byte에 뒤따르는 1 byte의 문자가 반복되게 되는데 이 반복회수는 ( flag_byte & 0x7f ) + 3 이 된다. 즉 80 33 이라면 Flag_byte가 80으로 1000 0000이므로 압축이 되었고 그 뒤의 33이 0+3번, 즉 3번 반복된다는 의미를 갖게 되는 것이다. 따라서 80 33은 압축을 풀면 33 33 33 이 된다.
압축이 되지 않는 부분에 대해서는 이 반복 횟수의 의미가 다르다. MSB가 0일 경우 그 뒤의 데이터들이 압축이 되지 않았다는 뜻인데 그 압축되지 않은 데이터의 개수가 ( flag_byte & 0x7f ) + 1 개라는 뜻이다. 따라서 04 01 02 03 04 05 를 압축을 해제하려면 우선 04를 읽어 압축되지 않은 데이터가 5개라는 내용이므로 01 02 03 04 05 가 된다.
실제로 나리키리2 의 남코 오프닝 부분에 대한 데이터를 이용하여 압축을 해제하는 전체적인 과정을 보도록 하자.
30 00 0E 00 85 00 81 88 81 11 00 14 80 11 00 14
^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
80 11 00 14 80 11 00 14 80 11 85 00 81 88 91 11
^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
85 00 81 88 91 11 85 00 07 88 88 A8 00 11 11 21
^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^
C7 80 11 00 51 89 11 8D 00 00 0A 80 00 00 B5 80
^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^
....
압축된 데이터의 앞부분 0x40 byte만을 뽑아내어 구분자와 데이터를 group화 한 것이다.
밑줄쳐진 부분은 한 덩어리로 맨 앞이 flag_byte, 그 뒤가 모두 data_byte라고 생각하면 된다.
앞에서의 설명과 같이 00 0E 00 30이므로 RLE로 0xE00만큼의 데이터가 압축되었음을 알 수 있다.
85 00 은 0x00이 8번 반복되었음을 의미하고 81 88은 0x88이 4번 반복됨을 의미한다.
역시 마찬가지로 81 11은 0x11이 4번 반복되는 것이고 00 14의 경우 압축되지 않은 데이터가 1개 존재하는 것이므로 14가 1개가 존재함을 알 수 있다. 위의 압축을 풀면 다음과 같다.
00 00 00 00 00 00 00 00 88 88 88 88 11 11 11 11
^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^ ^^^^^^^^^^^
14 11 11 11 14 11 11 11 14 11 11 11 14 11 11 11
^^ ^^^^^^^^ ^^ ^^^^^^^^ ^^ ^^^^^^^^ ^^ ^^^^^^^^
00 00 00 00 00 00 00 00 88 88 88 88 11 11 11 11
^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^ ^^^^^^^^^^^
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
....
역시 압축할 때 한덩어리가 되는 부분을 group지어 놓았다. 다소 보기 난해한 면은 있으나 쓸 줄 아는 것이라곤 그림판 뿐인데다가 미적 센스는 빵점이니 텍스트가 오히려 나을것이다 -_-;;;
혹시나 저 텍스트를 이쁘게 그려주실 분 계시면 연락바란다 =_=-b
4. 코드를 보여달라고?
코드는 직접 짜보는 것이 좋다는 것이 지론이긴 하지만 직접 적용하는 과정을 보여주는 것이 더 낫지 않을까 하여 압축을 푸는 부분에 대한 코드만 간략히 소개하도록 한다. 다시 압축하는 코드는 압축 방법을 곰곰히 잘 생각해보면 금방 짤 수 있을 것이다.
C 코드와 압축 데이터가 저장된 file과 압축을 해제했을 때의 데이터가 저장된 file을 링크하니 압축하는 코드를 만들게 된다면 두 파일들의 내용으로 제대로 동작하는지 확인하면 될 것이다.
다운로드
int RLUnComp(FILE *src, FILE *dst)
{
long header=0; // 헤더를 저장한다.
long len; // 압축을 해제했을 때의 데이터 크기
long count=0; // 압축을 얼마나 해제했는가
int i;
int flag_byte; // flag_byte
int data_byte; // data_byte
for(i=0;i<4;i++) {
header|=((fgetc(src))<<(8*i)); // 뒤에서부터 4바이트를 읽는다
}
if((header&0xff)!=0x30) {
printf("This is not an RLE data\n");
return -1;
}
printf("This is compressed with RLE\n");
len=header>>8; // 뒤의 한 바이트는 잘라낸다
while(count<len) {
flag_byte=fgetc(src); // flag_byte를 읽고
if(flag_byte&0x80) { // 압축 데이터라면
data_byte=fgetc(src); // data_byte를 읽어
for(i=0;i<(flag_byte&0x7f)+3;i++) {
fputc(data_byte,dst);
count++; // (flag_byte&0x7f)+3 만큼 반복한다.
}
}
else { // 압축되지 않은 데이터라면
for(i=0;i<(flag_byte&0x7f)+1;i++) {
data_byte=fgetc(src);
fputc(data_byte,dst); // (flag_byte&0x7f)+1 만큼의
count++; // data_byte를 그대로 출력한다.
}
}
}
return 0;
}
@. 다음 강좌는 LZ77이 되겠습니다.. 만 아직 데이터를 완벽히 분석한게 아니라 며칠 시간이 걸릴지도 모르겠습니다. RLE는 워낙에 간단해서 분석이 쉬웠는데 LZ77은 아직 알 수 없는 데이터들이 존재하는군요 -.-;;;;
@2. 당근 채찍 아무거나 좋습니다. 리플로 반응을 좀 보여주세요 ioi
출처 : http://hansicgu.hemosu.com
