lzw压缩算法的c语言实现

lzw压缩算法的c语言实现1 程序由五个模块组成。(1)lzw.h定义了一些基本的数据结构，常量，还有变量的初始化等。#ifndef _LZW_H_#define _LZW_H_/-#include #include #include #include /-#define LZW_BASE0x102/The code base#define CODE_LEN12/Max code length#define TABLE_LEN4099 / It must be prime number and bigger than 2CODE_LEN=4096. / Such as 5051 is also ok.#define BUFFERSIZE1024/-typedef structHANDLEh_sour;/ Source file handle.HANDLEh_dest;/ Destination file handle.HANDLEh_suffix; / Suffix table handle.HANDLEh_prefix; / Prefix table handle.HANDLEh_code;/ Code table handle.LPWORDlp_prefix; / Prefix table head pointer.LPBYTElp_suffix; / Suffix table head pointer.LPWORDlp_code; / Code table head pointer.WORDcode;WORDprefix;BYTEsuffix;BYTEcur_code_len; / Current code length. used in Dynamic-Code-Length mode LZW_DATA,*PLZW_DATA;typedef structWORDtop;WORDindex;LPBYTElp_buffer;HANDLEh_buffer;BYTEby_left;DWORDdw_buffer;BOOLend_flag;BUFFER_DATA,*PBUFFER_DATA;typedef struct/Stack used in decodeWORDindex;HANDLEh_stack;LPBYTElp_stack;STACK_DATA,*PSTACK_DATA;/-VOID stack_create( PSTACK_DATA stack )stack-h_stack= GlobalAlloc( GHND , TABLE_LEN*sizeof(BYTE) );stack-lp_stack = GlobalLock( stack-h_stack );stack-index = 0;/-VOID stack_destory( PSTACK_DATA stack )GlobalUnlock( stack-h_stack );GlobalFree( stack-h_stack );/-VOID buffer_create( PBUFFER_DATAbuffer )buffer-h_buffer= GlobalAlloc(GHND,BUFFERSIZE*sizeof(BYTE);buffer-lp_buffer= GlobalLock( buffer-h_buffer );buffer-top= 0;buffer-index= 0;buffer-by_left= 0;buffer-dw_buffer= 0;buffer-end_flag= FALSE;/-VOID buffer_destory( PBUFFER_DATAbuffer )GlobalUnlock( buffer-h_buffer );GlobalFree( buffer-h_buffer );/-VOID re_init_lzw( PLZW_DATA lzw )/When code table reached its top it should/be reinitialized.memset( lzw-lp_code, 0xFFFF, TABLE_LEN*sizeof(WORD) );lzw-code= LZW_BASE;lzw-cur_code_len= 9;/-VOID lzw_create(PLZW_DATAlzw,HANDLE h_sour,HANDLE h_dest)WORD i;lzw-h_code= GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD) );lzw-h_prefix= GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD) );lzw-h_suffix= GlobalAlloc( GHND, TABLE_LEN*sizeof(BYTE) );lzw-lp_code= GlobalLock( lzw-h_code);lzw-lp_prefix= GlobalLock( lzw-h_prefix );lzw-lp_suffix= GlobalLock( lzw-h_suffix );lzw-code= LZW_BASE;lzw-cur_code_len= 9;lzw-h_sour= h_sour;lzw-h_dest= h_dest;memset( lzw-lp_code, 0xFFFF, TABLE_LEN*sizeof(WORD) );/-VOID lzw_destory(PLZW_DATAlzw)GlobalUnlock( lzw-h_code);GlobalUnlock( lzw-h_prefix );GlobalUnlock( lzw-h_suffix );GlobalFree( lzw-h_code);GlobalFree( lzw-h_prefix );GlobalFree( lzw-h_suffix );/-#endif(2) fileio.h定义了一些文件操作#ifndef _FILEIO_H_#define _FILEIO_H_/-#include #include #include /-HANDLEfile_handle(CHAR* file_name)HANDLE h_file;h_file = CreateFile(file_name,GENERIC_READ|GENERIC_WRITE,FILE_SHARE_READ|FILE_SHARE_WRITE,NULL,OPEN_ALWAYS,0,NULL);return h_file;/-WORD load_buffer(HANDLE h_sour, PBUFFER_DATA buffer)/ Load file to bufferDWORD ret;ReadFile(h_sour,buffer-lp_buffer,BUFFERSIZE,&ret,NULL);buffer-index = 0;buffer-top = (WORD)ret;return (WORD)ret;/-WORD empty_buffer( PLZW_DATA lzw, PBUFFER_DATA buffer)/ Output buffer to fileDWORD ret;if(buffer-end_flag) / The flag mark the end of decodeif( buffer-by_left )buffer-lp_buffer buffer-index+ = (BYTE)( buffer-dw_buffer 32-buffer-by_left )by_left);WriteFile(lzw-h_dest, buffer-lp_buffer,buffer-index,&ret,NULL);buffer-index = 0;buffer-top = ret;return (WORD)ret;/-#endif(3) hash.h定义了压缩时所用的码表操作函数，为了快速查找使用了hash算法，还有处理hash冲突的函数#ifndef _HASH_H_#define _HASH_H_/-#include #include #include /-#defineDIVTABLE_LEN#defineHASHSTEP13/ It should bigger than 0./-WORD get_hash_index( PLZW_DATA lzw )DWORD tmp;WORD result;DWORD prefix;DWORD suffix;prefix = lzw-prefix;suffix = lzw-suffix;tmp = prefixlp_code hash = 0xFFFF )result = FALSE;elseif( lzw-lp_prefix hash = lzw-prefix &lzw-lp_suffix hash = lzw-suffix )result = TRUE;elseresult = FALSE;while( lzw-lp_code hash != 0xFFFF )if( lzw-lp_prefix hash = lzw-prefix &lzw-lp_suffix hash = lzw-suffix )result = TRUE;break;hash = re_hash_index( hash );return result;/-WORD get_code( PLZW_DATA lzw )WORD hash;WORD code;hash = get_hash_index( lzw );if( lzw-lp_prefix hash = lzw-prefix &lzw-lp_suffix hash = lzw-suffix )code = lzw-lp_code hash ;elsewhile( lzw-lp_prefix hash != lzw-prefix |lzw-lp_suffix hash != lzw-suffix )hash = re_hash_index( hash );code = lzw-lp_code hash ;return code;/-VOID insert_table( PLZW_DATA lzw )WORD hash;hash = get_hash_index( lzw );if( lzw-lp_code hash = 0xFFFF )lzw-lp_prefix hash = lzw-prefix;lzw-lp_suffix hash = lzw-suffix;lzw-lp_code hash = lzw-code;elsewhile( lzw-lp_code hash != 0xFFFF )hash = re_hash_index( hash );lzw-lp_prefix hash = lzw-prefix;lzw-lp_suffix hash = lzw-suffix;lzw-lp_code hash = lzw-code;/-#endif(4) encode.h压缩程序主函数#ifndef _ENCODE_H_#define _ENCODE_H_/-#include #include #include /-VOID output_code( DWORD code ,PBUFFER_DATA out, PLZW_DATA lzw)out-dw_buffer |= code by_left - lzw-cur_code_len );out-by_left += lzw-cur_code_len;while( out-by_left = 8 )if( out-index = BUFFERSIZE )empty_buffer( lzw,out);out-lp_buffer out-index+ = (BYTE)( out-dw_buffer 24 );out-dw_buffer by_left -= 8;/-VOID do_encode( PBUFFER_DATA in, PBUFFER_DATA out, PLZW_DATA lzw)WORD prefix;while( in-index != in-top )if( !in_table(lzw) )/ current code not in code table/ then add it to table and output prefixinsert_table(lzw);prefix = lzw-suffix;output_code( lzw-prefix ,out ,lzw );lzw-code+;if( lzw-code = (WORD)1cur_code_len )/ code reached current code top(1cur_code_len+;if( lzw-cur_code_len = CODE_LEN + 1 )re_init_lzw( lzw );else/ current code already in code table / then output nothingprefix = get_code(lzw);lzw-prefix = prefix;lzw-suffix = in-lp_buffer in-index+ ;/-VOID encode(HANDLE h_sour,HANDLE h_dest)LZW_DATAlzw;BUFFER_DATAin ;BUFFER_DATAout;BOOL first_run = TRUE;lzw_create( &lzw ,h_sour,h_dest );buffer_create( &in );buffer_create( &out );while( load_buffer( h_sour, &in ) )if( first_run )/ File length should be consideredbut here we simply / believe file length bigger than 2 bytes.lzw.prefix = in.lp_buffer in.index+ ;lzw.suffix = in.lp_buffer in.index+ ;first_run = FALSE;do_encode(&in , &out, &lzw);output_code(lzw.prefix, &out , &lzw);output_code(lzw.suffix, &out , &lzw);out.end_flag = TRUE;empty_buffer( &lzw,&out);lzw_destory( &lzw );buffer_destory( &in );buffer_destory( &out );/-#endif(5) decode.h解压函数主函数#ifndef _DECODE_H_#define _DECODE_H_/-#include #include #include /-VOID out_code( WORD code ,PBUFFER_DATA buffer,PLZW_DATA lzw,PSTACK_DATA stack)WORD tmp;if( code lp_stack stack-index+ = code;elsestack-lp_stack stack-index+ = lzw-lp_suffix code ;tmp = lzw-lp_prefix code ;while( tmp 0x100 )stack-lp_stack stack-index+ = lzw-lp_suffix tmp ;tmp = lzw-lp_prefix tmp ;stack-lp_stack stack-index+ = (BYTE)tmp;while( stack-index )if( buffer-index = BUFFERSIZE )empty_buffer(lzw,buffer);buffer-lp_buffer buffer-index+ = stack-lp_stack -stack-index ;/-VOID insert_2_table(PLZW_DATA lzw )lzw-lp_code lzw-code = lzw-code;lzw-lp_prefix lzw-code = lzw-prefix;lzw-lp_suffix lzw-code = lzw-suffix;lzw-code+;if( lzw-code = (WORD)1cur_code_len)-1 )lzw-cur_code_len+;if( lzw-cur_code_len = CODE_LEN+1 )lzw-cur_code_len = 9;if(lzw-code = 1by_left cur_code_len )if( buffer-index = BUFFERSIZE )load_buffer( lzw-h_sour, buffer );next = buffer-lp_buffer buffer-index+ ;buffer-dw_buffer |= (DWORD)next by_left);buffer-by_left+= 8;code = buffer-dw_buffer ( 32 - lzw-cur_code_len );buffer-dw_buffer cur_code_len;buffer-by_left-= lzw-cur_code_len;return code;/-VOID do_decode( PBUFFER_DATA in, PBUFFER_DATA out, PLZW_DATA lzw, PSTACK_DATA stack)WORD code;WORD tmp;while( in-index != in-top)code = get_next_code( in ,lzw );if( code suffix = (BYTE)code;else if( code code)/ code also in table / then output code chaintmp = lzw-lp_prefix code ;while( tmp 0x100 )tmp = lzw-lp_prefix tmp ;lzw-suffix = (BYTE)tmp;else/ code = lzw-code/ code not in table/ add code into table/ and out put code tmp = lzw-prefix;while( tmp 0x100 )tmp = lzw-lp_prefix tmp ;lzw-suffix = (BYTE)tmp;insert_2_table( lzw );out_code(code,out,lzw,stack);lzw-prefix = code;/-VOID decode( HANDLE h_sour, HANDLE h_dest )LZW_DATAlzw;BUFFER_DATAin ;BUFFER_DATAout;STACK_DATAstack;BOOLfirst_run;first_run = TRUE;lzw_create( &lzw ,h_sour,h_dest );buffer_create( &in );buffer_create