1、lzw壓縮算法的c語(yǔ)言實(shí)現(xiàn)1 程序由五個(gè)模塊組成。(1)lzw.h定義了一些基本的數(shù)據(jù)結(jié)構(gòu)，常量，還有變量的初始化等。#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

2、 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

3、 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,*PBUF

4、FER_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_DAT

5、A 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=

6、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;/

7、-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(

8、 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_suff

9、ix );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|

10、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_DAT

11、A 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;re

12、turn (WORD)ret;/-#endif(3) hash.h定義了壓縮時(shí)所用的碼表操作函數(shù)，為了快速查找使用了hash算法，還有處理hash沖突的函數(shù)#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 = lz

13、w-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 =

14、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

15、-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

16、 != 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壓縮程序主函數(shù)#ifndef _ENCODE_H_#define _ENCODE_H_/-#include #include #include /-VOID output_code( DWORD code ,PBUFFER_DATA out, PLZW_DATA lzw)out-dw_buff

17、er |= 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

18、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

19、-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

20、_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_r

21、un = 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解壓函數(shù)主函數(shù)#ifndef _DECODE_H_#define _DECODE_H_/-#include #in

22、clude #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-l

23、p_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

24、-lp_suffix lzw-code = lzw-suffix;lzw-code+;if( lzw-code = (WORD)1cur_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 |= (DWO

25、RD)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 =

26、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-

27、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(