Home > Zib library에서 사용하는 알고리즘 > Lempel-Ziv 알고리즘 > 예제 소스 보기

Lempel-Ziv 예제 프로그램

////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

#include <string.h>

#define HASH_SIZE 256

#define QUEUE_SIZE 256

#define QUEUE_POS(x) ((x + QUEUE_SIZE) % QUEUE_SIZE )

#define QUEUE_EMPTY ( front == rear )

#define QUEUE_FULL ( ( ( rear + 1 ) % QUEUE_SIZE ) == front )

#define MIN_COMPRESS 3

#define ESCAPE_CHAR (unsigned char)0xCC

typedef struct _tagHashList

{

int pos;

struct _tagHashList *next;

}HashList;

HashList hashList[HASH_SIZE];

char queue[QUEUE_SIZE];

int front;

int rear;

int pattern;

int current;

void InitQueue();

int CheckQueue( int _length );

int LempelZivCompress( char *_data, int _dataSize,

char *_compressData, int *_compressSize );

int LempelZivDeCompress( char *_compressData, int _compressSize,

char *_data, int *_dataSize );

int PushQueue( char _data );

int PopQueue();

int compress( char *_data, int _length, int _patter );

void InitHashList();

void InitQueue()

{

front = rear = 0;

}

void InitHashList()

{

int i;

for ( i = 0; i < HASH_SIZE; i++ )

{

hashList[i].next = 0;

}

}

int PushQueue( char _data )

{

queue[rear++] = _data;

rear = rear % QUEUE_SIZE;

return _data;

}

int PopQueue()

{

char pop = queue[front++];

front = front % QUEUE_SIZE;

return pop;

}

int CheckQueue( int _length )

{

HashList *tempList;

int tempPos;

int i;

current = QUEUE_POS( rear - _length );

tempList = hashList[ queue[current] ].next;

while( tempList != NULL )

{

tempPos = tempList->pos;

for ( i = 1; i < _length; i++ )

{

if ( queue[ QUEUE_POS( current + i) ] !=

queue[ QUEUE_POS(tempPos + i) ] )

break;

}

if ( i == _length )

return tempPos;

tempList = tempList->next;

}

return -1;

}

int AddHashList( char _data, int _pos )

{

HashList *newList;

newList = new HashList;

if ( newList == NULL )

return 0;

newList->pos = _pos;

newList->next = hashList[(unsigned char)_data].next;

hashList[(unsigned char)_data].next = newList;

return 1;

}

int DelHashList( char _data, int _pos )

{

HashList *tempList, *saveList;

tempList = hashList[(unsigned char)_data].next;

saveList = &hashList[(unsigned char)_data];

while( tempList != NULL )

{

if ( tempList->pos == _pos )

{

break;

}

saveList = tempList;

tempList = tempList->next;

}

if ( tempList )

{

saveList->next = tempList->next;

delete tempList;

return 1;

}

return 0;

}

int main( int argc, char *argv[] )

{

char buffer[4096];

char compbuffer[4096];

int size;

memset( buffer, 'a', 256 );

buffer[256] = 'b';

buffer[257] = ESCAPE_CHAR;

buffer[258] = 'c';

buffer[259] = 0;

printf("orig: %s\n", buffer );

LempelZivCompress( buffer, 259, compbuffer, &size );

memset( buffer, 0, 4096 );

LempelZivDeCompress( compbuffer, size, buffer, &size );

buffer[ size ] = 0;

printf("decomp: %s\n", buffer );

return 1;

}

int compress( char *_data, int _current, int _length, int _pattern )

{

int ret = 0;

if ( _length > MIN_COMPRESS )

{

*_data++ = ESCAPE_CHAR;

*_data++ = _current - _pattern;

*_data++ = _length;

ret = 3;

}

else

{

int i;

for ( i = 0; i < _length; i++ )

{

if ( queue[ _pattern + i ] == (char)ESCAPE_CHAR )

{

*_data++ = ESCAPE_CHAR;

*_data++ = 0x00;

ret += 2;

}

else{ *_data++ = queue[ _pattern + i ]; ret++; }

}

}

return ret;

}

int LempelZivCompress

(

char *_data,

int _dataSize,

char *_compressData,

int *_compressSize

)

{

int i;

int pattern, matchlength;

pattern = matchlength = 0;

char *writeData = _compressData;

PushQueue( _data[0] );

int ret;

i = 0;

while( i < _dataSize )

{

if ( QUEUE_FULL )

{

if ( pattern == front )

{

ret = compress( writeData, current,

matchlength, pattern );

writeData += ret;

matchlength = 0;

}

DelHashList( queue[front], front );

PopQueue();

}

if ( matchlength == 0 )

{

current = QUEUE_POS( rear - 1 );

ret = CheckQueue( matchlength + 1 );

if ( ret == -1 )

{

AddHashList( queue[current], QUEUE_POS(rear-1) );

ret = compress( writeData, current, 1, current );

writeData += ret;

matchlength = 0;

}

else

{

matchlength++;

pattern = ret;

}

PushQueue( _data[++i] );

}

else

{

ret = CheckQueue( matchlength + 1 );

if ( ret == -1 )

{

ret = compress( writeData, current,

matchlength, pattern );

writeData += ret;

matchlength = 0;

}

else

{

matchlength++;

PushQueue( _data[++i] );

pattern = ret;

}

}

}

compress( writeData, current, matchlength, pattern );

*_compressSize = writeData - _compressData;

return *_compressSize;

}

int LempelZivDeCompress

(

char *_compressData,

int _compressSize,

char *_data,

int *_dataSize

)

{

int i;

int length;

int pos;

char *writeData = _data;

InitQueue();

for ( i = 0; i < _compressSize; i++ )

{

if ( _compressData[i] != (char)ESCAPE_CHAR )

{

PushQueue( _compressData[i] );

if ( QUEUE_FULL )

{

*writeData++ = (char)PopQueue();

}

}

else

{

pos = _compressData[++i];

if ( pos == (char)0x00 )

{

PushQueue( ESCAPE_CHAR );

if ( QUEUE_FULL )

{

*writeData++ = (char)PopQueue();

}

}

else

{

length = (unsigned char)_compressData[++i];

pos = QUEUE_POS( rear - pos );

for ( int t = 0; t < length; t++ )

{

PushQueue( queue[pos + t] );

if ( QUEUE_FULL )

{

*writeData++ = (char)PopQueue();

}

}

}

}

}

while( !(QUEUE_EMPTY) )

{

*writeData++ = (char)PopQueue();

}

*_dataSize = writeData - _data;

return *_dataSize;

}

////////////////////////////////////////////////////////////////////////////////////////////////////////////