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

   Inline functions.

   10/12/01
                                                                           */

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

#define INTERNAL_NODE   256
#define UNUSED_NODE     300

typedef struct _node
{
   int x, y;
   struct _node *left, *right, *next;
} Node;

Node *Dictionary[256], HeapPool[512], *Heap, *a, *b, *c, **cursor;
unsigned char buffer[1024];

int HeapPoolIndex,
   Left[256], Right[256], f[257], NodeCount,
   FileSize, size, i, j, bit, byte, *branch;

FILE *infile, *outfile;

/**************************************************************** AssignID */
static void AssignID(Node *node, Node *parent)
{
   node->next = parent;
   if( node->y != INTERNAL_NODE )
   {
      Dictionary[node->y] = node;
      return;
   }
   node->x = NodeCount++;
   AssignID(node->left, node);
   AssignID(node->right, node);

   Left[node->x] = (node->left->y == INTERNAL_NODE)
                 ? node->left->x : -node->left->y;
   Right[node->x] = (node->right->y == INTERNAL_NODE)
                  ? node->right->x : -node->right->y;

} /* AssignID() */

/**************************************************************** HeapPush */
static void HeapPush(void)
{
   c = &HeapPool[HeapPoolIndex++];

   c->x = f[i];
   c->y = i;
   c->left = a;
   c->right = b;

   for(cursor = &Heap;
       *cursor != NULL && (*cursor)->x < c->x;
       cursor = &((*cursor)->next));
   c->next = *cursor;
   *cursor = c;

} /* HeapPush() */

/*************************************************************** WriteBits */
static void WriteBits(Node *node)
{
   if( node->next != NULL )
   {
      WriteBits(node->next);
      byte |= (node->next->right == 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);
   size = fread(buffer, 1, 579, infile);
   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++)
      {
         if( (f[i] & 1) != 0 )
         {
            Left[i] = -buffer[j++];
         }
         else
         {
            Left[i] = buffer[j++];
            if( Left[i] >= NodeCount || Left[i] <= i )
               break;
         }
         if( (f[i] & 2) != 0 )
         {
            Right[i] = -buffer[j++];
         }
         else
         {
            Right[i] = buffer[j++];
            if( Right[i] >= NodeCount || Right[i] <= i )
               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 ? Left : Right;
         if( branch[j] <= 0 )
         {
            fputc(-branch[j], outfile);
            j = 0;
            i++;
         }
         else
         {
            j = branch[j];
         }
         bit++;
      }
      printf("Decoded %s -> %s\n", argv[1], argv[2]);
   }
   else
   {
      /* CreateTree() */
      for(i = 0; i < 256; f[i++] = 0);

      FileSize = 0;
      fseek(infile, 0, SEEK_SET);
      while( (size = fread(buffer, 1, 1024, infile)) != 0 )
      {
         for(i = 0; i < size; f[buffer[i++]]++);
         FileSize += size;
      }

      HeapPoolIndex = 0;
      Heap = a = b = NULL;

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

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

         /* HeapPop() */
         b = Heap->next;
         Heap = Heap->next->next;

         f[i] = a->x + b->x;
         HeapPush();
      } while( Heap != NULL && Heap->next != NULL );

      NodeCount = 0;
      AssignID(Heap, NULL);

      for(i = NodeCount; i < 256; i++)
         Left[i] = Right[i] = UNUSED_NODE;

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

      for(i = 0; i < NodeCount; i++)
      {
         fputc(abs(Left[i]), outfile);
         fputc(abs(Right[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() */