/* decode.c - Don Yang (uguu.org)
   Huffman decoder

   decode <infile> <outfile>

   02/01/03
                                                                           */
/*@ -compmempass -dependenttrans -nullret -observertrans -usedef @*/

#include<assert.h>
#include<errno.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define BUFSIZE      2048


typedef struct _node
{
   int leaf;
   struct _node *left, *right;
} Node;

typedef struct
{
   FILE *file;
   int byte, bitindex;
} BitPool;

static int DecodeFile(BitPool *i, FILE *outfile, int filesize);
static int DecodeCompressedFile(BitPool *i, FILE *outfile,
                                Node *tree, int filesize);
static int DecodeUniformFile(FILE *outfile, Node *tree, int filesize);
static int LoadTree(BitPool *i, /*@out@*/Node **tree);
static /*@observer@*/Node *NewNode(int leaf);
static int ReadBit(BitPool *i);

/******************************************************************** main */
int main(int argc, char **argv)
{
   FILE *infile, *outfile;
   int filesize, status;
   BitPool i;

   if( argc < 3 )
      return printf("%s <infile> <outfile>\n", *argv);
   if( (infile = fopen(argv[1], "rb")) == NULL )
   {
      printf("Can not open %s, error %d\n", argv[1], errno);
      return 1;
   }
   if( fseek(infile, 0, SEEK_SET) != 0 )
   {
      printf("seek error %d\n", errno);
      (void)fclose(infile);
      return 1;
   }
   if( (outfile = fopen(argv[2], "wb+")) == NULL )
   {
      printf("Can not create %s, error %d\n", argv[2], errno);
      (void)fclose(infile);
      return 1;
   }

   if( fread(&filesize, sizeof(int), 1, infile) == 1 )
   {
      i.file = infile;
      i.byte = 0;
      i.bitindex = 8;
      if( (status = DecodeFile(&i, outfile, filesize)) != 0 )
      {
         if( status == 1 )    printf("read error %d\n", errno);
         if( status == 2 )    printf("write error %d\n", errno);
      }
   }
   else
   {
      (void)puts("empty output file created");
   }

   (void)fclose(infile);
   (void)fclose(outfile);
   return 0;

} /* main() */


/************************************************************** DecodeFile */
static int DecodeFile(BitPool *i, FILE *outfile, int filesize)
{
   Node *tree;
   int status;

   if( (status = LoadTree(i, &tree)) != 0 )
      return status;

   assert(tree != NULL);
   return (tree->leaf != -1)
      ?  DecodeUniformFile(outfile, tree, filesize)
      :  DecodeCompressedFile(i, outfile, tree, filesize);

} /* DecodeFile() */

/**************************************************** DecodeCompressedFile */
static int DecodeCompressedFile(BitPool *i, FILE *outfile,
                                Node *tree, int filesize)
{
   Node *cursor;
   int bit, byteswritten;

   cursor = tree;
   assert(tree->leaf == -1);
   for(byteswritten = 0; byteswritten < filesize; byteswritten++)
   {
      cursor = tree;
      while( (bit = ReadBit(i)) != EOF )
      {
         cursor = (bit == 0) ? cursor->left : cursor->right;
         if( cursor->leaf != -1 )
         {
            if( fputc(cursor->leaf, outfile) == EOF )
               return 2;
            break;
         }
      }
      if( bit == EOF )
         return 1;
   }
   return 0;

} /* DecodeCompressedFile() */

/******************************************************* DecodeUniformFile */
static int DecodeUniformFile(FILE *outfile, Node *tree, int filesize)
{
   unsigned char block[BUFSIZE];
   size_t blocksize;

   assert(0 <= tree->leaf && tree->leaf <= 255);
   memset(block, tree->leaf, BUFSIZE);
   for(blocksize = BUFSIZE; filesize > 0; filesize -= blocksize)
   {
      if( filesize < BUFSIZE )
         blocksize = (size_t)filesize;
      if( fwrite(block, blocksize, 1, outfile) != 1 )
         return 2;
   }
   return 0;

} /* DecodeUniformFile() */

/**************************************************************** LoadTree */
static int LoadTree(BitPool *i, Node **tree)
{
   Node *stack[256], **p;
   unsigned int byte, bitindex;
   int bit, stacksize;

   stacksize = 0;
   p = &stack[0];
   *tree = NULL;
   for(;;)
   {
      if( (bit = ReadBit(i)) == EOF )
         return 1;

      if( bit == 0 )
      {
         /* Internal node */
         stack[stacksize] = *p = NewNode(-1);
         p = &(stack[stacksize++]->left);
      }
      else
      {
         /* Leaf */
         for(bitindex = byte = 0; bitindex < 8; bitindex++)
         {
            if( (bit = ReadBit(i)) == EOF )
               return 1;
            byte |= (unsigned int)bit << bitindex;
         }
         *p = NewNode((int)byte);
         if( stacksize == 0 )
            break;

         for(;
             stacksize > 0 && stack[stacksize - 1]->right != NULL;
             stacksize--);
         if( stacksize == 0 )
            break;
         p = &(stack[stacksize - 1]->right);
      }
   }

   *tree = stack[0];
   return 0;

} /* LoadTree() */

/***************************************************************** NewNode */
static Node *NewNode(int leaf)
{
   static int PoolSize = 0;
   static Node Pool[511];

   Pool[PoolSize].leaf = leaf;
   Pool[PoolSize].left = Pool[PoolSize].right = NULL;
   return &Pool[PoolSize++];

} /* NewNode() */

/***************************************************************** ReadBit */
static int ReadBit(BitPool *i)
{
   int c;

   if( i->bitindex > 7 )
   {
      if( (c = fgetc(i->file)) == EOF )
      {
         i->bitindex = -1;
      }
      else
      {
         i->byte = c;
         i->bitindex = 0;
      }
   }
   if( i->bitindex < 0 )
      return EOF;
   return (i->byte & (1 << (unsigned int)(i->bitindex++))) == 0 ? 0 : 1;

} /* ReadBit() */