huf.cpp

作业

#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define FALSE 0                         
#define TRUE  1

struct chardata {
    short charnum;
    unsigned long total;
    short seq_length;
    long bit_sequence;
    double frequency;
    chardata *up,*left,*right;
};

struct decode_table_element {
    unsigned char letter;
    char spare;
    short left;
    short right;
};

chardata *huftable[256];
chardata *root=NULL;
decode_table_element *decode_table;
short array_max_index=0;
unsigned long  total;
long real_bits_total = 0L;
FILE *infile,*outfile;
char *infile_name,*outfile_name;

int compare(const void*, const void*);  
int dumptable();
int create_tree();
int gen_bit_sequences(chardata *);
int create_decode_table();                
int compress();                           
int find_lowest_freqs();                 
int only_one_up_ptr_left();                 
unsigned long asctobin(char *bit_seq);
short output_bits(long bit_seq, short seq_len);
short find_match(int c);                        
void assign_index(chardata *node);
void fill_array(chardata *node);
//------------------------------------------------------------------------------
int main(int argc,char **argv)
{
    if(argc!=3)
    {
        printf("%s","input wrong! lzhuf file1 file2");
        getch();
        return 1;
    }
    infile_name=argv[1];
    outfile_name=argv[2];
    short c;
    for (c=0; c < 256; c++)
    {
	    if ((huftable[c] = new chardata)== NULL)
	    {
	        printf("Unable to allocate space for %dth huftable node.",c);
	        getch();
	        return 1;
	    }
	    huftable[c]->charnum   = c;
	    huftable[c]->total     = 0L;
	    huftable[c]->frequency = 0;
	    huftable[c]->up        = NULL;
	    huftable[c]->left      = NULL;
	    huftable[c]->right     = NULL;
    }
    if ((infile=fopen(infile_name, "rb")) == NULL)
    {
	    printf("Unable to open %s.\n", infile_name);
	    getch();
	    return 1;
    }
    while (!feof(infile))
    {
	    c = fgetc(infile);
	    if(feof(infile)) continue;
	    ++total;
	    ++huftable[c]->total;
    }
    fclose(infile);

    qsort((void *)huftable, (size_t)256, (size_t)sizeof(chardata *),compare);
    dumptable();

    if (create_tree() != TRUE) return 1;

    gen_bit_sequences(root);

    if (create_decode_table() != TRUE)
    {
	    puts("Unable to allocate space for decode table, exiting.");
	    getch();
	    return 1;
    }
    printf("Decode table built, contains %d elements.\n",array_max_index + 1);

    if (compress() != 0) return 1;
    puts("Done.");
    delete []decode_table;
    delete []huftable[256];
    getch();
}
//------------------------------------------------------------------------------
chardata *ptr1,*ptr2;

int  create_tree()
{
     double maxfreq = 0 ;
     chardata *new_node = NULL;
     while (maxfreq < 0.99999)
     {
          find_lowest_freqs();
          if ((new_node =new chardata)== NULL)
          {
               puts(" malloc() failed in create_tree().");
               return FALSE;
          }
          new_node->up    = NULL;
          new_node->left  = ptr2;
          new_node->right = ptr1;
          new_node->charnum = -1;
          ptr1->up = new_node;
          ptr2->up = new_node;
          new_node->frequency = ptr1->frequency + ptr2->frequency;
          maxfreq = new_node->frequency;
          printf("Newly created freq == %f\n", maxfreq);
     }
     root = new_node;
     if (!only_one_up_ptr_left())
     {
     	puts("Lose! more than one up ptr left.");
        return FALSE;
     }
     return TRUE;
}
//------------------------------------------------------------------------------
int only_one_up_ptr_left()
{
    short bottom=255;
    chardata *tptr;
    chardata *first_null_up_ptr=NULL;
    tptr=huftable[bottom];
    while (bottom != -1)
    {
          while (tptr->up != NULL)
             tptr = tptr->up;
          if(first_null_up_ptr == NULL)
             first_null_up_ptr = tptr;
          else
	     if (first_null_up_ptr != tptr)
             return FALSE;
          --bottom;
    }
    return TRUE;
}
//------------------------------------------------------------------------------
int find_lowest_freqs()
{
    chardata *tptr;
    chardata *minptr;
    chardata *second_minptr;
    chardata dummy;
    short bottom = 255;
    dummy.frequency = 2.0;
    minptr=&dummy;
    while(bottom != -1)
    {
	   tptr = huftable[bottom];
	   if (tptr->total == 0L)
	   {
              --bottom;
	      continue;
	   }
           while(tptr->up != NULL)
              tptr = tptr->up;
	   if(tptr->frequency < minptr->frequency)
	      minptr = tptr;
   	   --bottom;
    }
    bottom = 255;
    second_minptr=&dummy;
    while(bottom != -1)
    {
	   tptr = huftable[bottom];
	   if (tptr->total == 0L)
	   {
	      --bottom;
	      continue;
	   }
           while (tptr->up != NULL)
	       tptr = tptr->up;
	   if((tptr->frequency < second_minptr->frequency)&& (tptr != minptr))                           /* and curr <> min1     */
	          second_minptr = tptr;
           --bottom;
    }
    ptr1 = minptr;
    ptr2 = second_minptr;
return 0;
}
//------------------------------------------------------------------------------
int dumptable()
{
    short i;
    if (total==0) return 1;
    for (i=0; i< 256; i++)
    huftable[i]->frequency = (double(huftable[i]->total))/(double)total;
    return 0;
}
//------------------------------------------------------------------------------
int compare(const void *arg1, const void *arg2)
{
    long result=((chardata *)arg1)->total-((chardata *)arg2)->total;
    if (result > 0L) return -1;
    if (result < 0L) return +1;
    return 0;
}
//------------------------------------------------------------------------------
short seq_len=0;

int gen_bit_sequences(chardata *node)
{
    static char bit_sequence[32];
    //double frac;
    if (node->left != NULL)
    {
	   bit_sequence[seq_len++]='1';
	   gen_bit_sequences(node->left);
	   seq_len--;
    }
    if (node->right != NULL)
    {
	   bit_sequence[seq_len++]='0';
	   gen_bit_sequences(node->right);
	   seq_len--;
    }
    if (node->right != NULL)
	    return 1;
    bit_sequence[seq_len] = 0;
    node->seq_length = (long)seq_len;
    node->bit_sequence = asctobin(bit_sequence);
    //frac = (double(huftable[node->charnum]->total))/(double)total;
    real_bits_total += (long)seq_len;
    return 0;
}

unsigned long asctobin(char *bit_seq)
{
    register short i;
    register unsigned long binary_value=0;

    for (i = 0; (i < 32) && (bit_seq[i]); i++)
    {
	binary_value <<= 1;
	binary_value |= (bit_seq[i]=='1') ? 1 : 0;
    }

    return binary_value;
}

//------------------------------------------------------------------------------


int  create_decode_table()
{
    assign_index(root);
    decode_table = new decode_table_element[array_max_index+1];
    if(decode_table == NULL)
	    return FALSE;
    fill_array(root);
    return TRUE;
}
//------------------------------------------------------------------------------
void assign_index(chardata *node)
{
    if (node != NULL)
    {
	   node->total = (long)array_max_index++;
       printf("\n%ld",node->total);
	   assign_index(node->left);
       assign_index(node->right);
    }
}
//------------------------------------------------------------------------------

short temp_index = 0;

void fill_array(chardata *node)
{
    if (node != NULL)
    {
	   if (node->left == NULL)
	   {
	       decode_table[temp_index].letter = (unsigned char)node->charnum;
	       decode_table[temp_index].left   = 0;
	       decode_table[temp_index].right  = 0;
	   }
	   else    /* we are at an interior node */
	   {
	      decode_table[temp_index].letter = '@';
	      decode_table[temp_index].left   = (short) node->left->total;
	      decode_table[temp_index].right  = (short) node->right->total;
	   }
       temp_index++;
       fill_array(node->left);
	   fill_array(node->right);
    }
}
//------------------------------------------------------------------------------
int compress(void)
{
     register unsigned long i;
     register short array_index;
     int c;
      
	 char orig_name[_MAX_FNAME+_MAX_EXT],drive[_MAX_DRIVE],dir[_MAX_DIR],filename[_MAX_FNAME],ext[_MAX_EXT];              /* 3 chars, orig ext      */              
     if ((infile=fopen(infile_name, "rb")) == NULL)
     {
	    printf("Unable to open %s\n", infile_name);
	    return 1;
     }
     if ((outfile=fopen(outfile_name, "wb")) == NULL)
     {
	   printf("Unable to open %s\n", outfile_name);
	   return 1;
     }
     _splitpath(infile_name,drive,dir,filename,ext);  
     strcpy(orig_name, filename);
     strcat(orig_name, ext);
     for(i=0; i<13; i++)
        fputc(orig_name[i],outfile);
     if (fwrite((void*)&array_max_index,sizeof(short),1,outfile)< 1)
     {
	    printf("Unable to write to %s -- out of disk space?", outfile_name);
	    fclose(outfile);
	    return 1;
     }
     if (fwrite((void*)&total, sizeof(unsigned long), 1, outfile)< 1)
     {
	   printf("Unable to write to %s -- out of disk space?", outfile_name);
	   fclose(outfile);
	 return 1;
     }
     if (fwrite((void*)decode_table,sizeof(decode_table_element),array_max_index+1,outfile)< array_max_index)
     {
	    printf("Unable to write to %s -- out of disk space?", outfile_name);
	    fclose(outfile);
	    return 1;
    }
    printf("Encoding %ld bytes.\n",total);
    for (i=0; i< total; i++)
    {
	  c = fgetc(infile);
	  if(c==EOF)
	  {
	      printf("\nReached unexpected end of input file at position %ld.\n",i);
	      return 1;
	  }
	  array_index = find_match(c);
	  if (output_bits(huftable[array_index]->bit_sequence,huftable[array_index]->seq_length)!= 0)
	  {
	    printf("Unable to write to %s -- out of disk space?", outfile_name);
	    return 1;
	  }
    }

    output_bits(255,7);

    printf("%ld bytes encoded.\n", i);

    fclose(outfile);
    return 0;
}

/***************************************
 * return array index that corresponds *
 * to a particular character           *
 ***************************************/

short find_match(int c)
{
    register short i=0;

    while (c != huftable[i]->charnum)
	++i;

    return i;
}

/************************************
 * write out a bit sequence to disk *
 ************************************/

short output_bits(long bit_seq, short seq_len)
{
    static unsigned char buffer = 0;
    static unsigned short bits_used   = 0;
    short i;
    bit_seq <<= (32 - seq_len);
    for (i = 0; i < seq_len; i++)
    {
	   buffer <<= 1;
	   buffer|= ((bit_seq & 0x80000000) != 0);
       bit_seq <<= 1;
	   bits_used++;
	   if (bits_used == 8)
	   {
	      if(fputc((int)buffer,outfile)==EOF)
	      {
		     fclose(outfile);
		     return 1;
	      }
	      bits_used = 0;
	      buffer    = 0;
	   }
    }
    return 0;
}
//------------------------------------------------------------------------------