lzw壓縮算法的c語言實現[轉載]2007-04-10 16:091 程序由五個模塊組成。

(1)   lzw.h       定義了一些基本的數據結構，常量，還有變量的初始化等。

#ifndef __LZW_H__
#define __LZW_H__
//------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <memory.h>
//------------------------------------------------------------------------------
#define LZW_BASE     0x102//   The code base
#define CODE_LEN        12    //   Max code length
#define TABLE_LEN       4099 // It must be prime number and bigger than 2^CODE_LEN=4096. 
        // Such as 5051 is also ok.
#define BUFFERSIZE      1024
//------------------------------------------------------------------------------
typedef struct
{
     HANDLE       h_sour;   // Source file handle.
     HANDLE       h_dest;   // Destination file handle.
    
     HANDLE       h_suffix; // Suffix table handle.
     HANDLE       h_prefix; // Prefix table handle.
     HANDLE       h_code;   // Code table handle.
    
     LPWORD       lp_prefix; // Prefix table head pointer.
     LPBYTE       lp_suffix; // Suffix table head pointer.
     LPWORD       lp_code; // Code table head pointer.

     WORD         code;
     WORD         prefix;
     BYTE         suffix;

     BYTE         cur_code_len; // Current code length.[ used in Dynamic-Code-Length mode ]

}LZW_DATA,*PLZW_DATA;


typedef struct
{
     WORD         top;
     WORD         index;

     LPBYTE       lp_buffer;
     HANDLE       h_buffer;
    
     BYTE         by_left;
     DWORD        dw_buffer;

     BOOL         end_flag;

}BUFFER_DATA,*PBUFFER_DATA;


typedef struct                   //Stack used in decode
{
WORD         index;
HANDLE       h_stack;
LPBYTE       lp_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_DATA     buffer )
{
     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_DATA    buffer )
{
     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_DATA     lzw,     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_DATA     lzw)
{  
     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 <stdio.h>
#include <stdlib.h>
#include <windows.h>
//------------------------------------------------------------------------------
HANDLE   file_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 buffer
{
     DWORD 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 file
{
   
     DWORD ret;
     if(buffer->end_flag) // The flag mark the end of decode
{
   if( buffer->by_left )
   {
    buffer->lp_buffer[ buffer->index++ ] = (BYTE)( buffer->dw_buffer >> 32-buffer->by_left )<<(8-buffer->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 <stdio.h>
#include <stdlib.h>
#include <windows.h>
//------------------------------------------------------------------------------
#define    DIV        TABLE_LEN
#define    HASHSTEP   13          // 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 = prefix<<8 | suffix;
     result = tmp % DIV;
     return result;
}
//------------------------------------------------------------------------------
WORD re_hash_index( WORD hash ) // If hash conflict occured we must recalculate
{                                // hash index .
     WORD result;
     result = hash + HASHSTEP;
     result = result % DIV;
     return result;
}
//------------------------------------------------------------------------------
BOOL in_table( PLZW_DATA lzw ) // To find whether current code is already in table.
{
     BOOL result;
     WORD hash;

     hash = get_hash_index( lzw );
     if( lzw->lp_code[ hash ] == 0xFFFF )
     {
         result = FALSE;    
     }
     else
     {
         if( lzw->lp_prefix[ hash ] == lzw->prefix &&
             lzw->lp_suffix[ hash ] == lzw->suffix )
         {
             result = TRUE;
         }
         else
         {
             result = 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 ];
     }
     else
     {
         while( 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;
     }
     else
     {
         while( 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 <stdio.h>
#include <stdlib.h>
#include <windows.h>

//------------------------------------------------------------------------------
VOID output_code( DWORD code ,PBUFFER_DATA out, PLZW_DATA lzw)
{