간단한 무손실 압축 run-length encoding 예제 소스

데이터 압축은 보통 (데이터) 손실 압축과 무손실 압축으로 구분할 수 있다. 일반적인 이미지 압축인 jpeg은 손실 압축에 속하고, 파일 압축에 사용하는 zip같은 경우는 무손실 압축에 속한다.

무손실 압축중에 가장 간단한 것이 run-length encoding(RLE)이다.

run-length encoding은 아래 예와 같이 중복된 데이터를 없애 데이터를 압축한다.

원본 : 0 0 0 1 1 0 0 0 0 0 1 1 1 1    (data size:14)

 RLE : 0 3 1 2 0 5 1 4                    (data size:8)

원본에서 순서대로 0은 3개, 1은 2개, 0은 5개 1은 4개로 표시하는 방식이다. 

하지만, 이런 방식때문에 경우에 따라선 데이터 양이 늘어나는 단점이 있다.

중복되 데이터가 없는 겨우 아래의 예처럼 RLE 한 데이터 양이 원본보다 크게 되는 경우가 있다.

원본 : 1 0 1 0 1                            (data size : 5)

 RLE : 1 1 0 1 1 1 0 1 1 1                (data size : 10)

이런 단점이 있어도 특정 경우에 예를 들어 메모리가 적고, RTOS 구동중인 프로세서에 GUI를 구현해야 할 때 요긴하게 사용할 수 있다.

RLE의 encoder/decoder의 소스는 아래와 같다.

[소스 코드]

int runlength_encode(unsigned short *src, int src_len, unsigned short *dst, int dst_size)

{

int i = 0;

int dst_i = 0;

unsigned short code = 0;

int code_count = 0;

int max_count = 65535-1;

if (!src || !dst) return -1;

i = 0;

while (i < src_len)

{

code = 0;

code_count = 0;

for (; i < src_len; i++)

{

if (code_count == 0)

{

code = src[i];

}

else if (code != src[i])

{

break;

}

code_count++;

if (code_count >= max_count)

break;

}

if (code_count && dst_i < dst_size)

{

dst[dst_i++] = code;

dst[dst_i++] = code_count;

}

}

return dst_i;

}

int runlength_decode(unsigned short *src, int src_len, unsigned short *dst, int dst_size)

{

int i = 0;

int dst_i = 0;

if (!src || !dst) return -1;

while (i < src_len-1)

{

int j = 0;

unsigned short code = src[i++];

int code_count = src[i++];

for (j = 0; j < code_count && dst_i < dst_size; j++)

{

dst[dst_i++] = code;

}

}

return dst_i;

}

[테스트 코드]

코드에서는 아래의 이미지를 사용하여 테스트 했다.

void test_runlength()

{

unsigned short *encode_data = NULL;

int encode_data_size = 0;

unsigned short *decode_data = NULL;

int decode_data_size = 0;

encode_data = (unsigned short*)malloc(sizeof(unsigned short) * 48 * 48);

decode_data = (unsigned short*)malloc(sizeof(unsigned short) * 48 * 48);

if (!encode_data || !decode_data)

{

safe_free(encode_data);

safe_free(decode_data);

return;

}

memset(encode_data, 0, sizeof(unsigned short) * 48 * 48);

memset(decode_data, 0, sizeof(unsigned short) * 48 * 48);

encode_data_size = runlength_encode(&icon_joystick[2], 48 * 48, encode_data, 48 * 48);

decode_data_size = runlength_decode(encode_data, encode_data_size, decode_data, 48 * 48);

_trace(TEXT("\r\n image size %d\r\n"), 48 * 48);

for (int i = 0; i < 48 * 48; i++)

{

_trace(TEXT("0x%04x, "), icon_joystick[2+i]);

}

_trace(TEXT("\r\n encode size %d\r\n"), encode_data_size);

for (int i = 0; i < encode_data_size; i++)

{

_trace(TEXT("0x%04x, "), encode_data[i]);

}

_trace(TEXT("\r\n decode size %d\r\n"), decode_data_size);

for (int i = 0; i < decode_data_size; i++)

{

_trace(TEXT("0x%04x, "), decode_data[i]);

}

safe_free(encode_data);

safe_free(decode_data);

}

실행 결과 2304 bytes의 원본 이미지가 RLE 이후 616bytes로 줄어들었다.