lzw算法源码c语言.c

LZW压缩算法简介 作者:宋成 描述:一篇关于LZW压缩算法简介的文章

  cur_str.character = -1;
 }
}

void addto_translation_table(tt_entry_t *tt_entries,
 const tt_entry_t &new_string, u32 &string_num)
{
 tt_entries[string_num] = new_string;
 string_num ++;
}

#ifdef _USE_ASM_VER__LZW_DECOMPRESS

extern "C" int WINAPI lzw_decompress(tt_entry_t *tt_entries,
 u8 *in_data_buffer, u32 code_num,
 u8 *out_data_buffer, u32 *out_data_len);

#else

int lzw_decompress(tt_entry_t *tt_entries, u8 *in_data_buffer, u32 code_num,
 u8 *out_data_buffer, u32 *out_data_len)
{
 enum
 {
  STA_STRING = 8,
  STA_CHAR = 9,
 };

 int ret_val = -1;
 u32 cur_pos, byte_offset, old_byte_offset, bit_offset;
 u16 old_code, new_code, old_state;
 tt_entry_t tmp_string;
 translated_string_t cur_string;
 u32 string_num;
 u8 character;

 u32 tmp_var;

 tt_entry_t *tmp_ptr2=NULL;
 int flag;

 if( !tt_entries )
 {
  tmp_ptr2 = new tt_entry_t[MAX_ST_ENTRIES];
  if( !tmp_ptr2 )
  {
   goto err_out;
  }
  tt_entries = tmp_ptr2;
 }

 memset(tt_entries, 0, sizeof(tt_entry_t) * MAX_ST_ENTRIES);

 bit_offset = 0;
 read_data_from_bs((u8 *)&old_code, CODE_LENGTH, in_data_buffer, bit_offset);
 assert( old_code < 256 );
 DBG_PRINT(("byte offset=0, code=%d, string length=1\n", old_code));
 out_data_buffer[0] = (u8)old_code;
 character = (u8)old_code;

 string_num = 0;

 byte_offset=1, old_state = STA_CHAR, old_byte_offset = 0;
 for(cur_pos=1; cur_pos<code_num; cur_pos++)
 {

  DBG_PRINT(("byte offset=%d, ", byte_offset));
  if( byte_offset==1947 )
  {
   byte_offset = byte_offset;
  }

  read_data_from_bs(&new_code, CODE_LENGTH, in_data_buffer, bit_offset);
  tmp_var = byte_offset;

  if( search_translation_table(tt_entries, new_code) < 0 )
  { // not in translation table
   flag = 0;
   translate_code(tt_entries, old_code, cur_string);

   tmp_string.the_string.start_pos = (u16)byte_offset;
   tmp_string.the_string.str_len = ( -1 == cur_string.character ?
    cur_string.the_string.str_len + 1 : 2 );
   old_state = STA_STRING;
  }
  else
  { // in translation table
   flag = 1;
   tmp_string.the_string.start_pos = (u16)old_byte_offset;

   if( STA_CHAR==old_state )
   {
    tmp_string.the_string.str_len = 2;
   }
   else if( STA_STRING==old_state )
   {
    tmp_string.the_string.str_len =
     tt_entries[old_code-256].the_string.str_len + 1;
   }
   else
   {
    assert(0);
   }

   translate_code(tt_entries, new_code, cur_string);
   old_state = -1 != cur_string.character ? STA_CHAR : STA_STRING;
  }

  if( -1 == cur_string.character )
  {
   memcpy(out_data_buffer + byte_offset,
    out_data_buffer + cur_string.the_string.start_pos,
    cur_string.the_string.str_len);
   byte_offset += cur_string.the_string.str_len;
  }
  else
  {
   out_data_buffer[byte_offset] = (u8)cur_string.character;
   byte_offset++;
  }


  if( 0==flag )
  {
   out_data_buffer[byte_offset] = character;
   byte_offset++;
  }


  character = ( -1 == cur_string.character ?
   out_data_buffer[cur_string.the_string.start_pos] :
   (u8) cur_string.character );

  DBG_PRINT(("code=%d, string length=%d\n", new_code,
   0==flag ? tmp_string.the_string.str_len :
    -1==cur_string.character ? cur_string.the_string.str_len : 1
   ));

  addto_translation_table(tt_entries, tmp_string, string_num);

  old_code = new_code;
  old_byte_offset = tmp_var;
 }

 assert( bit_offset == code_num*CODE_LENGTH );
 *out_data_len = byte_offset;

 ret_val = 0;

err_out:

 if( tmp_ptr2 )
 {
  delete []tmp_ptr2;
 }

 return ret_val;
}


#endif

void PrintStringTable(st_entry_t **string_table, st_entry_t *st_entries)
{
 unsigned int i;
 for(i=0; i<65536; i++)
 {
  if( string_table[i] )
  {
   printf("string chain[%d]\n", i);

   st_entry_t *entry = string_table[i];

   while( entry )
   {
    printf("    start pos=%04d, string length=%04d\n",
     entry->the_string.start_pos, entry->the_string.str_len);
    entry = entry->next;
   }
  }
 }
}

void PrintTranslationTable(tt_entry_t **translation_table, tt_entry_t *tt_entries)
{
 unsigned int i;
 for(i=0; i<MAX_ST_ENTRIES; i++)
 {
  if( translation_table[i] )
  {
   printf("code <%d>: ", 256+i);
   printf("    start pos=%04d, string length=%04d\n",
     translation_table[i]->the_string.start_pos,
     translation_table[i]->the_string.str_len);
  }
 }
}

int Lzwc(char *src_file, char *dest_file)
{
 int ret_val = -1;

 u8 data_buff[MAX_CB_ONECE];
 u8 compressed_data_buff[(MAX_CB_ONECE*CODE_LENGTH)/8];

 int xx=0;

 FILE *fp_src=NULL, *fp_dest=NULL;
 u32 total_bytes_to_compress, bytes_to_compress, number_of_codes;
 int rc;

 fp_src = fopen(src_file, "rb");
 if( !fp_src )
 {
  goto err_out;
 }

 fp_dest = fopen(dest_file, "wb");
 if( !fp_dest )
 {
  goto err_out;
 }

 fseek(fp_src,0, SEEK_END);
 total_bytes_to_compress = ftell(fp_src);
 fseek(fp_src, 0, SEEK_SET);

 do
 {
  lzw_info_t lzwinfo;
  u32 total_bytes_compressed;

  bytes_to_compress = total_bytes_to_compress > MAX_CB_ONECE ?
   MAX_CB_ONECE : total_bytes_to_compress;

  fread(data_buff, 1, bytes_to_compress, fp_src);

  rc = lzw_compress(lzw_string_table, lzw_string_table_entries,
    data_buff, bytes_to_compress, compressed_data_buff, &number_of_codes);

  //printf("%d compression...\n", ++xx);


  if( RCFAILED==rc )
  {
   goto err_out;
  }
  else
  {
   if( RCOK_DATA_UNC==rc )
   {
    lzwinfo.code_num = (u32) number_of_codes;
    total_bytes_compressed = number_of_codes;
    lzwinfo.data_compressed = 0;
   }
   else if( RCOK_DATA_COM==rc  )
   {
    lzwinfo.code_num = (u32) number_of_codes;
    total_bytes_compressed = (CODE_LENGTH * number_of_codes + 7)/8;
    lzwinfo.data_compressed = 1;
   }

   fwrite(&lzwinfo, 1, sizeof(lzw_info_t), fp_dest);
   fwrite(compressed_data_buff, 1, total_bytes_compressed, fp_dest);

   total_bytes_to_compress -= bytes_to_compress;
  }

 } while( total_bytes_to_compress > 0);

 ret_val = 0;

err_out:

 if( fp_src )
 {
  fclose(fp_src);
 }

 if( fp_dest )
 {
  fclose(fp_dest);
 }

 return ret_val;
}

int Lzwd(char *src_file, char *dest_file)
{
 int ret_val = -1;

 u8 data_buff[MAX_CB_ONECE];
 u8 compressed_data_buff[(MAX_CB_ONECE*CODE_LENGTH)/8];

 FILE *fp_src=NULL, *fp_dest=NULL;
 u32 bytes_decompressed, file_size, file_pos;

 fp_src = fopen(src_file, "rb");
 if( !fp_src )
 {
  goto err_out;
 }

 fp_dest = fopen(dest_file, "wb");
 if( !fp_dest )
 {
  goto err_out;
 }

 fseek(fp_src,0, SEEK_END);
 file_size = ftell(fp_src);
 fseek(fp_src, 0, SEEK_SET);

 file_pos = 0;
 while(1)
 {
  lzw_info_t lzwinfo;
  u32 bytes_to_read;

  if( file_pos >= file_size )
  {
   break;
  }
  fread(&lzwinfo, 1, sizeof(lzwinfo), fp_src);
  file_pos += sizeof(long);

  if( file_pos >= file_size )
  {
   break;
  }

  if( lzwinfo.data_compressed )
  {
   bytes_to_read = ((u32)lzwinfo.code_num * CODE_LENGTH + 7) / 8;
  }
  else
  {
   bytes_to_read = (u32)lzwinfo.code_num ;
  }

  fread(compressed_data_buff, 1, bytes_to_read, fp_src);
  file_pos += bytes_to_read;

  if( lzwinfo.data_compressed )
  {
#ifdef _USE_ASM_VER__LZW_DECOMPRESS

   lzw_decompress(lzw_translation_table_entries,
    compressed_data_buff, (u32)lzwinfo.code_num,
    data_buff, &bytes_decompressed);
#else

   lzw_decompress(lzw_translation_table_entries,
    compressed_data_buff, (u32)lzwinfo.code_num,
    data_buff, &bytes_decompressed);
#endif

   //PrintTranslationTable(lzw_translation_table,
   // lzw_translation_table_entries);

  }
  else
  {
   memcpy(data_buff, compressed_data_buff, bytes_to_read);
   bytes_decompressed = bytes_to_read;
  }


  fwrite(data_buff, 1, bytes_decompressed, fp_dest);
 }

 ret_val = 0;

err_out:

 if( fp_src )
 {
  fclose(fp_src);
 }

 if( fp_dest )
 {
  fclose(fp_dest);
 }

 return ret_val;
}

static N=1;

int Lzwc_test(char *src_file, char *dest_file)
{
 int ret_val = -1;

 u8 data_buff[MAX_CB_ONECE];
 u8 compressed_data_buff[(MAX_CB_ONECE*CODE_LENGTH)/8];

 FILE *fp_src=NULL, *fp_dest=NULL;
 u32 code_num;

 fp_src = fopen(src_file, "rb");
 if( !fp_src )
 {
  goto err_out;
 }

 fp_dest = fopen(dest_file, "wb");
 if( !fp_dest )
 {
  goto err_out;
 }

 do
 {
  lzw_info_t lzwinfo;
  int rc;

  fseek(fp_src, N*MAX_CB_ONECE, SEEK_SET);
  fread(data_buff, 1, MAX_CB_ONECE, fp_src);

  FILE *fp_tmp = fopen("test.tmp", "wb");
  fwrite(data_buff, 1, MAX_CB_ONECE, fp_tmp);
  fclose(fp_tmp);

  rc = lzw_compress(lzw_string_table, lzw_string_table_entries,
    data_buff, MAX_CB_ONECE, compressed_data_buff, &code_num);
  PrintStringTable(lzw_string_table, lzw_string_table_entries);

  if( RCFAILED==rc )
  {
   goto err_out;
  }
  else
  {
   u32 bytes_compressed_to;

   if( RCOK_DATA_UNC==rc )
   {
    lzwinfo.code_num = code_num;
    lzwinfo.data_compressed = 0;
    bytes_compressed_to = code_num;
   }
   else if( RCOK_DATA_COM==rc  )
   {
    lzwinfo.code_num = code_num;
    lzwinfo.data_compressed = 1;
    bytes_compressed_to = (code_num * CODE_LENGTH + 7) / 8;
   }

   fwrite(&lzwinfo, 1, sizeof(lzw_info_t), fp_dest);
   fwrite(compressed_data_buff, 1, bytes_compressed_to, fp_dest);
  }

 } while( 0 );

 ret_val = 0;

err_out:

 if( fp_src )
 {
  fclose(fp_src);
 }

 if( fp_dest )
 {
  fclose(fp_dest);
 }


 return ret_val;

}


int main(int argc, char *argv[])
{
 int ret_val;

 if( 4 != argc )
 {
  printf("Usage: lzw [/c | /d] <source file> <destination file>\n");
  return -1;
 }

 unsigned long t1, t2;
 t1 = GetTickCount();

 if( 'c/' == *(unsigned short *)argv[1] || 'C/' == *(unsigned short *)argv[1] ||
  'c-' == *(unsigned short *)argv[1] || 'C-' == *(unsigned short *)argv[1]
  )
 {
  printf("compressing...");
  ret_val = Lzwc(argv[2], argv[3]);
 }

 if( 'd/' == *(unsigned short *)argv[1] || 'D/' == *(unsigned short *)argv[1] ||
  'd-' == *(unsigned short *)argv[1] || 'D-' == *(unsigned short *)argv[1]
  )
 {
  printf("decompressing...");
  ret_val = Lzwd(argv[2], argv[3]);
 }

 t2 = GetTickCount();

 if( 0==ret_val )
 {
  printf("successfully\n");
  printf("%ld milliseconds elapsed\n", t2-t1);
 }
 else
 {
  printf("failed\n");
 }

 getch();
 return ret_val;
}


/*
void main(int argc, char *argv[])
{
 Lzwc_test(argv[2], argv[3]);

 getch();
}
*/