#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define    VERBOSE     

short           father[512];
unsigned short  code[256], heap_length;
unsigned long   compress_charcount, file_size, heap[257];
unsigned char   code_length[256];
long            frequency_count[512];
short           decomp_tree[512];

FILE            *ifile, *ofile;

void            build_decomp_tree (), decompress_image ();
void            decompress(char f1[],char f2[]),compress(char f1[],char f2[]);

unsigned short  generate_code_table ();
void            build_code_tree (), build_initial_heap ();
void            compress_image (), compression_report ();
void            get_frequency_count ();

void main ()
{
	char ch,file[2][12];
	cout<<endl;
	cout<<endl;
	cout<<"                  實驗八   ~哈夫曼編碼~              "<<endl;
	cout<<endl;
	cout<<"  *1. 壓縮文件       *2. 解壓文件      *3.退出"<<endl;
	cout<<endl;
	cout<<"***請選擇要執(zhí)行的操作***:";
	cin>>ch;
	while(ch)
	{
		switch(ch)
		{
		case '1':   
			printf ("\nHUFF1:  Huffman Code Compression Program.");
			printf ("\n        14-Aug-90  Bill Demas.  Version 1.0\n\n");
			printf("  壓縮文件名:");
			scanf("%s",&file[0]);
			printf("  生成文件名:");
			scanf("%s",&file[1]);
			compress(file[0],file[1]);
			ch='0';
			break;
		case '2':
			printf ("\nDHUFF:  Huffman Code Decompression Program.");
			printf ("\n        14-Aug-90  Bill Demas.  Version 1.0\n\n");
			printf("  解壓文件名:");
			scanf("%s",&file[0]);
			printf("  生成文件名:");
			scanf("%s",&file[1]);
			decompress(file[0],file[1]);
			ch='0';
			break;
		case '3':
			exit(0);
			break;
		default:
			cout<<"***請選擇要執(zhí)行的操作***:";
			cin>>ch;
		}
	}
}

void compress(char *f1,char *f2)
{ 
	if ((ifile = fopen (f1, "rb")) != NULL)
	{
		fseek (ifile, 0L, 2);
		file_size = (unsigned long) ftell (ifile);
         #ifdef VERBOSE
            printf ("(1) Getting Frequency Counts.\n");
         #endif
         fseek (ifile, 0L, 0);
         get_frequency_count ();
         #ifdef VERBOSE
            printf ("(2) Building Initial Heap.\n");
         #endif
         build_initial_heap ();

         #ifdef VERBOSE
            printf ("(3) Building the Code Tree.\n");
         #endif
         build_code_tree ();
         #ifdef VERBOSE
            printf ("(4) Generating the Code Table.\n");
         #endif
		 if (!generate_code_table ())
			 printf ("ERROR!  Code Value Out of Range. Cannot Compress.\n");
		 else
		 {
            #ifdef VERBOSE
			 printf ("(5) Compressing & Creating the Output File.\n");
            #endif
			 if ((ofile = fopen (f2, "wb")) != NULL)
			 {
				 fwrite (&file_size, sizeof (file_size), 1, ofile);
				 fwrite (code, 2, 256, ofile);
				 fwrite (code_length, 1, 256, ofile);

				 fseek (ifile, 0L, 0);
				 compress_image ();
				 fclose (ofile);
			 }
			 else
				 printf("\nERROR: Couldn't create output file \n");
            #ifdef VERBOSE
               compression_report ();
            #endif
			}
			fclose (ifile);
   }
   else
	   printf ("\nERROR:   -- File not found!\n");
}
void decompress(char *f1,char *f2)  //解壓
{ 
	if ((ifile = fopen (f1, "rb")) != NULL)
	{
	   fread (&file_size, sizeof (file_size), 1, ifile);
	   fread (code, 2, 256, ifile);
	   fread (code_length, 1, 256, ifile);
       #ifdef VERBOSE 
	        printf ("(1) Building the tree.\n");
       #endif     
	        build_decomp_tree ();
       #ifdef VERBOSE    
	        printf ("(2) Decompressing & Creating the Output File.\n");
       #endif
	   if ((ofile = fopen (f2, "wb")) != NULL)
	   {
		   decompress_image();
		   fclose (ofile);
	   }
	   else
		   printf ("\nERROR:  Couldn't create output file \n");
	   fclose (ifile);
   }
   else
	   printf ("\nERROR:   -- File not found!\n");
}//decompress

void  build_decomp_tree ()
{
   register unsigned short  loop1;
   register unsigned short  current_index;
   unsigned short  loop;
   unsigned short  current_node = 1;

   decomp_tree[1] = 1;

   for (loop = 0; loop < 256; loop++)
   {
      if (code_length[loop])
      {
	 current_index = 1;
	 for (loop1 = code_length[loop] - 1; loop1 > 0; loop1--)
	 {
	    current_index = (decomp_tree[current_index] << 1) +
			    ((code[loop] >> loop1) & 1);
	    if (!(decomp_tree[current_index]))
	       decomp_tree[current_index] = ++current_node;
	 }
	 decomp_tree[(decomp_tree[current_index] << 1) +
	   (code[loop] & 1)] = -loop;
      }
   }
}

void  decompress_image ()
{
   register unsigned short  cindex = 1;
   register char            curchar;
   register short           bitshift;

   unsigned long  charcount = 0L;


   while (charcount < file_size)
   {
      curchar = (char) getc (ifile);

      for (bitshift = 7; bitshift >= 0; --bitshift)
      {
	 cindex = (cindex << 1) + ((curchar >> bitshift) & 1);

	 if (decomp_tree[cindex] <= 0)
	 {
	    putc ((int) (-decomp_tree[cindex]), ofile);

	    if ((++charcount) == file_size)
               bitshift = 0;
            else
               cindex = 1;
	 }
	 else
	    cindex = decomp_tree[cindex];
      }
   }
}

//壓縮
void reheap (unsigned short heap_entry)
{
   register unsigned short  index;
   register unsigned short  flag = 1;

   unsigned long   heap_value;


   heap_value = heap[heap_entry];

   while ((heap_entry <= (heap_length >> 1)) && (flag))
   {
      index = heap_entry << 1;

      if (index < heap_length)
         if (frequency_count[heap[index]] >= frequency_count[heap[index+1]])
            index++;

      if (frequency_count[heap_value] < frequency_count[heap[index]])
	 flag--;
      else
      {
         heap[heap_entry] = heap[index];
         heap_entry       = index;
      }
   }

   heap[heap_entry] = heap_value;
}

void compress_image ()
{
   register unsigned int    thebyte = 0;
   register short           loop1;
   register unsigned short  current_code;
   register unsigned long   loop;

   unsigned short  current_length, dvalue;
   unsigned long   curbyte = 0;
   short           curbit = 7;


   for (loop = 0L; loop < file_size; loop++)
   {
      dvalue         = (unsigned short) getc (ifile);
      current_code   = code[dvalue];
      current_length = (unsigned short) code_length[dvalue];

      for (loop1 = current_length-1; loop1 >= 0; --loop1)
      {
         if ((current_code >> loop1) & 1)
            thebyte |= (char) (1 << curbit);

         if (--curbit < 0)
         {
            putc (thebyte, ofile);
            thebyte = 0;
            curbyte++;
            curbit = 7;
         }
      }
   }
   putc (thebyte, ofile);
   compress_charcount = ++curbyte;
}

void  compression_report ()
{
   float           savings;
   unsigned short  header_charcount;
   unsigned long   output_characters;


   header_charcount   = 768 + sizeof (file_size);
   output_characters  = (unsigned long) header_charcount +
			compress_charcount;

   printf ("\nRaw characters          : %ld\n", file_size);
   printf ("Header characters       : %d\n", header_charcount);
   printf ("Compressed characters   : %ld\n", compress_charcount);
   printf ("Total output characters : %ld\n", output_characters);

   savings = 100 - ((float) output_characters / (float) file_size) * 100;
   printf ("\nPercentage savings      : %3.2f%%\n", savings);
}

unsigned short  generate_code_table ()
{
   register unsigned short  loop;
   register unsigned short  current_length;
   register unsigned short  current_bit;

   unsigned short  bitcode;
   short           parent;


   for (loop = 0; loop < 256; loop++)
      if (frequency_count[loop])
      {
         current_length = bitcode = 0;
         current_bit = 1;
         parent = father[loop];

         while (parent)
         {
            if (parent < 0)
            {
               bitcode += current_bit;
               parent = -parent;
            }
            parent = father[parent];
            current_bit <<= 1;
            current_length++;
         }

         code[loop] = bitcode;

         if (current_length > 16)
            return (0);
         else
            code_length[loop] = (unsigned char) current_length;
      }
      else
         code[loop] = code_length[loop] = 0;

   return (1);
}

void build_code_tree ()
{
   register unsigned short  findex;
   register unsigned long   heap_value;

   while (heap_length != 1)
   {
      heap_value = heap[1];
      heap[1]    = heap[heap_length--];

      reheap (1);
      findex = heap_length + 255;

      frequency_count[findex] = frequency_count[heap[1]] +
                                frequency_count[heap_value];
      father[heap_value] =  findex;
      father[heap[1]]    = -findex;
      heap[1]            =  findex;

      reheap (1);
   }

   father[256] = 0;
}

void build_initial_heap ()
{
   register unsigned short  loop;
   heap_length=0;

   for (loop=0; loop<256;loop++)
      if (frequency_count[loop])
         heap[++heap_length] = (unsigned long) loop;

   for (loop=heap_length;loop>0;loop--)
      reheap(loop);
}

void get_frequency_count ()
{
   register unsigned long  loop;


   for (loop = 0; loop < file_size; loop++)
      frequency_count[getc (ifile)]++;
}