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

   Prepare for bytecode.

   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[512], branch,
   f[257], NodeCount,
   FileSize, size, i, j, bit, byte;

FILE *infile, *outfile;


void AssignID(int sp0/*-3*/, int sp1/*-2*/)
{
   int sp2/*+1*/, sp3/*+2*/;

   sp2 = LeftPtr[sp0];
   sp3 = RightPtr[sp0];
   NextPtr[sp0] = sp1;
   if( y[sp0] - INTERNAL_NODE )
   {
      Dictionary[y[sp0]] = sp0;
   }
   else
   {
      x[sp0] = NodeCount++;
      AssignID(sp2, sp0);
      AssignID(sp3, sp0);

      Tree[x[sp0]] =
         (y[sp2] - INTERNAL_NODE)
            ?  0 - y[sp2]
            :  x[sp2];
      Tree[256 + x[sp0]] =
         (y[sp3] - INTERNAL_NODE)
            ?  0 - y[sp3]
            :  x[sp3];
   }
}

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 sp0/*-2*/)
{
   if( NextPtr[sp0] + 1 )
   {
      WriteBits(NextPtr[sp0]);
      byte |= (RightPtr[NextPtr[sp0]] - sp0 ? 0 : 1) << bit++;
      if( 7 < bit )
      {
         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);
   while( size < 579 &&
         (buffer[size] = fgetc(infile)) - EOF )
   {
      size++;
   }
   if( size )
   {
      NodeCount = buffer[FileSize = i = 0];
      Heap = (HeapPoolIndex = (NodeCount + 3) >> 2)
           + (NodeCount << 1);
      if( Heap + 4 < size )
      {
         while( i < NodeCount )
         {
            j = 0;
            while( j < 4 )
            {
               f[i + j] = ((buffer[(i >> 2) + 1] >> (j << 1)) & 3);
               j++;
            }
            i += 4;
         }

         j = HeapPoolIndex + 1;
         i = 0;
         while( i < NodeCount )
         {
            c = 0;
            while( c < 2 )
            {
               a = (c << 8) + i;
               b = buffer[j++];
               if( (f[i] & (c + 1)) )
               {
                  Tree[a] = 0 - b;
               }
               else
               {
                  Tree[a] = b;
                  if( Tree[a] < (i + 1) ||
                      NodeCount < Tree[a] + 1 )
                  {
                     goto breaklabel;
                  }
               }
               c++;
            }
            i++;
         }
         breaklabel:
         if( i - NodeCount )
         {
         }
         else
         {
            FileSize = i = 0;
            while( i < 32 )
            {
               FileSize |= buffer[j++] << i;
               i += 8;
            }
         }
      }
      if( 0 < FileSize )
      {
         fseek(infile, Heap + 5, SEEK_SET);
         byte = i = j = 0;
         bit = 8;
         while( i < FileSize )
         {
            if( 7 < bit )
            {
               byte = fgetc(infile);
               bit = 0;
            }

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

         while( (i = fgetc(infile)) - EOF )
         {
            f[i] += 1;
            FileSize++;
         }

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

         while( i < 256 )
         {
            if( f[i] )
            {
               HeapPush();
            }
            i++;
         }
         if( NextPtr[Heap] == -1 )
         {
            i = 0;
            while( 0 < f[i] )
            {
               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);

         i = NodeCount;
         while( i < 256 )
         {
            Tree[i] = Tree[256 + i] = UNUSED_NODE;
            i++;
         }

         fputc(NodeCount, outfile);
         i = 0;
         while( i < NodeCount )
         {
            byte = j = 0;
            while( j < 4 )
            {
               c = 1 << (j << 1);
               if( Tree[i + j] < 1 )
               {
                  byte |= c;
               }
               if( Tree[i + j + 256] < 1 )
               {
                  byte |= c << 1;
               }
               j++;
            }
            fputc(byte, outfile);
            i += 4;
         }

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

         i = 0;
         while( i < 4 )
         {
            fputc((FileSize >> (i << 3)) & 255, outfile);
            i++;
         }

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

         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;
}