/* c6.c - Don Yang (uguu.org)

   Unify data types.

   10/14/01
                                                                           */

#include<stdio.h>
#include<stdlib.h>

#define INTERNAL_NODE   256
#define UNUSED_NODE     300

int
   x[512], y[512], LeftPtr[512], RightPtr[512], NextPtr[512],
   buffer[579],
   Dictionary[256], Heap, a, b, c,
   HeapPoolIndex, Tree[2][256], branch,
   f[257], NodeCount,
   FileSize, size, i, j, bit, byte;

FILE *infile, *outfile;

/**************************************************************** AssignID */
static void AssignID(int node, int parent)
{
   NextPtr[node] = parent;
   if( y[node] != INTERNAL_NODE )
   {
      Dictionary[y[node]] = node;
      return;
   }
   x[node] = NodeCount++;
   AssignID(LeftPtr[node], node);
   AssignID(RightPtr[node], node);

   Tree[0][x[node]] =
      (y[LeftPtr[node]] == INTERNAL_NODE)
         ?  x[LeftPtr[node]]
         :  -y[LeftPtr[node]];
   Tree[1][x[node]] =
      (y[RightPtr[node]] == INTERNAL_NODE)
         ?  x[RightPtr[node]]
         :  -y[RightPtr[node]];

} /* AssignID() */

/**************************************************************** HeapPush */
static void HeapPush(void)
{
   c = HeapPoolIndex++;

   x[c] = f[i];
   y[c] = i;
   LeftPtr[c] = a;
   RightPtr[c] = b;

   if( Heap < 0 || x[Heap] > x[c] )
   {
      NextPtr[c] = Heap;
      Heap = c;
   }
   else
   {
      a = Heap;
      b = NextPtr[a];
      while( b != -1 && x[b] < x[c] )
      {
         a = b;
         b = NextPtr[b];
      }
      NextPtr[a] = c;
      NextPtr[c] = b;
   }

} /* HeapPush() */

/*************************************************************** WriteBits */
static void WriteBits(int node)
{
   if( NextPtr[node] != -1 )
   {
      WriteBits(NextPtr[node]);
      byte |= (RightPtr[NextPtr[node]] == node ? 1 : 0) << bit++;
      if( bit > 7 )
      {
         fputc(byte, outfile);
         bit = byte = 0;
      }
   }

} /* WriteBits() */

/******************************************************************** main */
int main(int argc, char **argv)
{
   if( argc < 3 )
      return printf("%s <infile> <outfile>\n", *argv);

   if( (infile = fopen(argv[1], "rb")) == NULL )
      return printf("Can not open %s\n", argv[1]);
   if( (outfile = fopen(argv[2], "wb+")) == NULL )
   {
      fclose(infile);
      return printf("Can not create %s\n", argv[2]);
   }

   fseek(infile, 0, SEEK_SET);
   for(size = 0; size < 579; size++)
   {
      if( (buffer[size] = fgetc(infile)) == EOF )
         break;
   }
   if( size == 0 )
   {
      fclose(infile);
      fclose(outfile);
      return puts("Empty file");
   }

   /* LoadHeader() */
   NodeCount = buffer[0];
   FileSize = 0;
   if( NodeCount * 2 + ((NodeCount + 3) / 4) + 5 <= size )
   {
      /* LoadTree() */
      for(i = 0; i < NodeCount; i += 4)
      {
         for(j = 0; j < 4; j++)
            f[i + j] = ((buffer[i / 4 + 1] >> (j * 2)) & 3);
      }

      j = (NodeCount + 3) / 4 + 1;
      for(i = 0; i < NodeCount; i++)
      {
         for(c = 0; c < 2; c++)
         {
            if( (f[i] & (c + 1)) != 0 )
            {
               Tree[c][i] = -buffer[j++];
            }
            else
            {
               Tree[c][i] = buffer[j++];
               if( Tree[c][i] >= NodeCount || Tree[c][i] <= i )
                  break;
            }
         }
         if( c < 2 )
            break;
      }
      if( i == NodeCount )
         FileSize = (buffer[j] | (buffer[j + 1] << 8) |
                    (buffer[j + 2] << 16) | (buffer[j + 3] << 24));
   }
   if( FileSize > 0 )
   {
      /* DecodeFile() */
      fseek(infile, NodeCount * 2 + (NodeCount + 3) / 4 + 5, SEEK_SET);
      byte = j = 0;
      bit = 8;
      for(i = 0; i < FileSize;)
      {
         if( bit > 7 )
         {
            byte = fgetc(infile);
            bit = 0;
         }

         branch = (byte & (1 << bit)) == 0 ? 0 : 1;
         if( Tree[branch][j] <= 0 )
         {
            fputc(-Tree[branch][j], outfile);
            j = 0;
            i++;
         }
         else
         {
            j = Tree[branch][j];
         }
         bit++;
      }
      printf("Decoded %s -> %s\n", argv[1], argv[2]);
   }
   else
   {
      /* CreateTree() */
      for(i = 0; i < 256; f[i++] = 0);

      fseek(infile, 0, SEEK_SET);
      for(FileSize = 0; (i = fgetc(infile)) != EOF; FileSize++)
         f[i]++;

      HeapPoolIndex = 0;
      Heap = -1;
      a = b = 0;

      for(i = 0; i < 256; i++)
      {
         if( f[i] != 0 )
            HeapPush();
      }
      if( NextPtr[Heap] == -1 )
      {
         for(i = 0; f[i] > 0; i++);
         HeapPush();
      }

      i = INTERNAL_NODE;
      do
      {
         /* HeapPop() */
         a = Heap;

         /* HeapPop() */
         b = NextPtr[Heap];
         Heap = NextPtr[NextPtr[Heap]];

         f[i] = x[a] + x[b];
         HeapPush();
      } while( NextPtr[Heap] != -1 );

      NodeCount = 0;
      AssignID(Heap, -1);

      for(i = NodeCount; i < 256; i++)
         Tree[0][i] = Tree[1][i] = UNUSED_NODE;

      /* WriteHeader() */
      fputc(NodeCount, outfile);
      for(i = 0; i < NodeCount; i += 4)
      {
         byte = 0;
         for(j = 0; j < 4; j++)
         {
            if( Tree[0][i + j] <= 0 )  byte |= 1 << (j * 2);
            if( Tree[1][i + j] <= 0 )  byte |= 2 << (j * 2);
         }
         fputc(byte, outfile);
      }

      for(i = 0; i < NodeCount; i++)
      {
         fputc(abs(Tree[0][i]), outfile);
         fputc(abs(Tree[1][i]), outfile);
      }

      for(i = 0; i < 4; i++)
         fputc((FileSize >> (i * 8)) & 255, outfile);

      /* EncodeFile() */
      bit = byte = 0;
      fseek(infile, 0, SEEK_SET);
      for(i = 0; i < FileSize; i++)
      {
         j = fgetc(infile);
         WriteBits(Dictionary[j]);
      }

      if( bit > 0 )
         fputc(byte, outfile);

      printf("Encoded %s -> %s\n", argv[1], argv[2]);
   }

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

} /* main() */