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

   Reorder code.

   10/14/01
                                                                           */

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

#define INTERNAL_NODE   256
#define UNUSED_NODE     256

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;


void AssignID(int node, int parent)
{
   NextPtr[node] = parent;
   if( y[node] - INTERNAL_NODE )
   {
      Dictionary[y[node]] = node;
   }
   else
   {
      x[node] = NodeCount++;
      AssignID(LeftPtr[node], node);
      AssignID(RightPtr[node], node);

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

void HeapPush(void)
{
   c = HeapPoolIndex++;

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

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

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

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, size = 0, SEEK_SET);
   for(; size < 579 &&
         (buffer[size] = fgetc(infile)) - EOF; size++);
   if( size )
   {
      NodeCount = buffer[FileSize = i = 0];
      if( (NodeCount << 1) + ((NodeCount + 3) >> 2) + 4 < size )
      {
         for(; i < NodeCount; i += 4)
         {
            for(j = 0; j < 4; j++)
               f[i + j] = ((buffer[(i >> 2) + 1] >> (j << 1)) & 3);
         }

         j = ((NodeCount + 3) >> 2) + 1;
         for(i = 0; i < NodeCount; i++)
         {
            for(c = 0; c < 2; c++)
            {
               if( (f[i] & (c + 1)) )
               {
                  Tree[c][i] = -buffer[j++];
               }
               else
               {
                  Tree[c][i] = buffer[j++];
                  if( NodeCount <= Tree[c][i] || 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( 0 < FileSize )
      {
         fseek(infile, (NodeCount << 1) + ((NodeCount + 3) >> 2) + 5, SEEK_SET);
         byte = i = j = 0;
         bit = 8;
         while( i < FileSize )
         {
            if( 7 < bit )
            {
               byte = fgetc(infile);
               bit = 0;
            }

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

         for(; (i = fgetc(infile)) - EOF; FileSize++)
            f[i]++;

         Heap = (HeapPoolIndex = a = b = i = 0) - 1;

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

         i = INTERNAL_NODE;
         while( NextPtr[Heap] + 1 )
         {
            Heap = NextPtr[b = NextPtr[a = Heap]];

            f[i] = x[a] + x[b];
            HeapPush();
         }

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

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

         fputc(NodeCount, outfile);
         for(i = 0; i < NodeCount; i += 4)
         {
            for(byte = j = 0; j < 4; j++)
            {
               if( Tree[0][i + j] < 1 )  byte |= 1 << (j << 1);
               if( Tree[1][i + j] < 1 )  byte |= 2 << (j << 1);
            }
            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 << 3)) & 255, outfile);

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

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

         printf("Encoded %s -> %s\n", argv[1], argv[2]);
      }
   }
   else
   {
      puts("Empty file");
   }

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