간단한 무손실 압축 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로 줄어들었다.
댓글
댓글 쓰기