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

   Preprocess 4: remove prototypes / inline functions.

   09/15/01
                                                                           */

#include<stdio.h>

#define SetBinary(stream)     /*tmode(fileno(stream), O_BINAR*/

typedef unsigned char BYTE;

BYTE RingBuffer[0x8000];
int ProcOffset, LimitOffset;
int FileSize, iChecksum, oChecksum;

int Left[127] =
{
      1,   2,   3,-116,-108,   6,   7,   8, -68, -62,
     -2,  12, -20,  14, -26,  16, -70,  18,  19,  20,
     21, -84,  23,-107,  25, -64,  27,  28, -69,  30,
   -113, -75,-125, -61,  35,  36, -46,  38,  39,  40,
     41,  42,  43,  44,  45,  46,  47, -25, -12, -48,
     51,  52,  53, -57,  55,  56,  57,  58,  59, -81,
   -127,-126,-106, -77, -91,  66,  67, -14,  69, -29,
     71,-114,-117,-121,  75, -51,-111,  78,  79,  80,
   -115,-100, -97,  84,-105,  86,  87,  88, -52, -85,
    -76, -35, -37, -33,  95,  96, -45,  98, -78, 100,
    -60, -65, 103,-122, 105, 106, -31,  -1, 109,  -7,
    111,-118, -82,-119, -34, 116, -92, 118, 119, -18,
    121, -27,   0, 124, -96, -58,  -4
};
int Right[127] =
{
     77,  37,  17,   4,   5,-112,  15, -50,   9,  10,
     11,  13, -28, -19, -30, -83, -56,  34,  26,  22,
    -41,-120, -40,  24, -54, -53, -95,  33,  29,  32,
     31,  -3,-123, -59, -10,-109, -98,  70,-101,  49,
   -102, -39, -36, -79, -88,  48,  -5, -74,  -9,  50,
     54, -73, -47, -66, -49,  63,  62, -93,  61,  60,
    -11, -13, -89,  64,  65,  68, -24, -21, -90, -22,
     76,  72,  73,  74, -42, -80,  -8, -32,  83,  82,
     81, -99,-110,  94,  85,-104,-103,  90,  89, -72,
     91,  92,  93, -38, 122, 110,  97, 101,  99, -71,
    -86, 102, 107, 104, -16, -63, -23, 108,-124, -17,
    113, 112, -67, 114, 115, 117, -43, -87, 120, -94,
     -6, -15, 123, -44, 125, 126, -55
};

struct
{
   BYTE bit[16];
   int length;
} Table[128];

BYTE HuffmanBuffer[0x3ffe];

int FirstIndex[256], LastIndex[256];
int NextIndex[0x3ffe + 1];
int ByteOffset[0x3ffe + 1];


void AddByteOffset(int byte, int offset)
{
   int chain, index;

   for(chain = 0; chain < 256; chain++)
   {
      if( FirstIndex[chain] == 0 )
         continue;
      if( (offset - ByteOffset[FirstIndex[chain]]) >=
            (0x3ffe - 1) )
         break;
   }

   index = FirstIndex[chain];
   FirstIndex[chain] = NextIndex[FirstIndex[chain]];
   if( FirstIndex[chain] == 0 )
      LastIndex[chain] = 0;

   if( LastIndex[byte] == 0 )
   {
      FirstIndex[byte] = LastIndex[byte] = index;
   }
   else
   {
      NextIndex[LastIndex[byte]] = index;
      LastIndex[byte] = index;
   }
   ByteOffset[index] = offset;
   NextIndex[index] = 0;
}

void InitEntry(int index, int *string, int length)
{
   int i;

   Table[index].length = length;
   for(i = 0; i < length; i++)
      Table[index].bit[i] = (BYTE)(string[i] - 1);
}

void InitTableEntries(int index, int *string)
{
   size_t x;
   int i;

   for(x = 0; string[x] != 0; x++);
   string[x] = 1;
   string[x + 1] = 0;
   if( (i = Left[index]) <= 0 )  InitEntry(-i, string, x + 1);
   else                          InitTableEntries(i, string);

   string[x] = 2;
   if( (i = Right[index]) <= 0 ) InitEntry(-i, string, x + 1);
   else                          InitTableEntries(i, string);

   string[x] = 0;
}

int GetByte(int absoffset, FILE *infile)
{
   int byte;

   while( absoffset >= LimitOffset )
   {
      if( (byte = fgetc(infile)) == EOF )
      {
         FileSize = LimitOffset++;
         return -1;
      }
      iChecksum ^= byte;
      RingBuffer[(LimitOffset++) & 32767] = (BYTE)byte;
   }
   if( absoffset >= FileSize )
      return -1;

   return RingBuffer[absoffset & 32767];
}

int GetWord(FILE *infile)
{
   int byte1, byte2;

   if( (byte1 = fgetc(infile)) == EOF )
      return -1;
   if( (byte2 = fgetc(infile)) == EOF )
   {
      iChecksum = byte1;
      return -1;
   }

   return (byte2 << 8) | byte1;
}

void PutByte(int byte, FILE *outfile)
{
   oChecksum ^= byte;
   fputc(byte, outfile);
}

void PutWord(int word, FILE *outfile)
{
   oChecksum ^= word & 0xff;
   oChecksum ^= word >> 8;
   fputc(word & 0xff, outfile);
   fputc(word >> 8, outfile);
}

void WriteLiteral(int length, FILE *outfile)
{
   int bit, byte, c, i, j, x;

   for(i = x = bit = byte = 0; i < length && x < length; i++)
   {
      c = RingBuffer[(ProcOffset - length + i) & 32767];

      if( (c & 0x80) != 0 )
      {
         x = length;
      }
      else
      {
         for(j = 0; j < Table[c].length; j++)
         {
            byte |= ((unsigned)Table[c].bit[j]) << (bit++);
            if( bit > 7 )
            {
               HuffmanBuffer[x++] = (BYTE)byte;
               if( x >= length )
                  break;
               bit = byte = 0;
            }
         }
      }
   }

   if( bit > 0 )
      HuffmanBuffer[x++] = (BYTE)byte;

   if( x < length )
   {
      PutWord(0x4000 | length, outfile);
      for(i = 0; i < x; PutByte(HuffmanBuffer[i++], outfile));
   }
   else
   {
      PutWord(length, outfile);
      for(i = 0; i < length; i++)
         PutByte(RingBuffer[(ProcOffset - length + i) & 32767],
            outfile);
   }
}

int main(int argc, char **argv)
{
   FILE *infile, *outfile;
   int runlength, duplength, dupoffset, i, x;

   int maxoffset, maxlen, index;
   int offset, len;

   int string[16];

   int bit, byte, *branch;

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

   for(i = 0; i < 0x8000; RingBuffer[i++] = 0);
   iChecksum = oChecksum = ProcOffset = LimitOffset = 0;
   FileSize = 0x7fffffff;

   if( argv[1][0] != 'x' )
   {
      for(i = 0; i < 256; FirstIndex[i++] = 0);
      for(i = 0; i < 256; LastIndex[i++] = 0);

      FirstIndex[0] = index = 1;
      offset = -0x3ffe + 1;
      for(i = 0; i < 0x3ffe - 1; i++)
      {
         ByteOffset[index] = offset;
         NextIndex[index] = index + 1;
         index++;
         offset++;
      }
      NextIndex[index - 1] = 0;
      LastIndex[0] = index - 1;

      string[0] = 0;
      InitTableEntries(0, string);

      runlength = 0;
      while( GetByte(ProcOffset, infile) != -1 )
      {
         maxoffset = maxlen = 0;

         for(index = FirstIndex[RingBuffer[ProcOffset & 32767]];
             index != 0;
             index = NextIndex[index])
         {
            offset = ByteOffset[index];
            len = ProcOffset - offset;

            if( len < maxlen )
               break;

            for(i = 1; i < len; i++)
            {
               if( GetByte(ProcOffset+i, infile) != GetByte(offset+i, infile) )
                  break;
            }
            if( i > maxlen )
            {
               maxoffset = offset;
               maxlen = i;
            }
         }

         duplength = maxlen;
         dupoffset = ProcOffset - maxoffset;

         if( duplength >= 5 )
         {
            if( runlength > 0 )
               WriteLiteral(runlength, outfile);

            if( duplength < 256 )
            {
               PutWord(0x8000 | dupoffset, outfile);
               PutByte(duplength, outfile);
            }
            else
            {
               PutWord(0xc000 | dupoffset, outfile);
               PutWord(duplength, outfile);
            }

            for(i = 0; i < duplength; i++)
            {
               AddByteOffset(RingBuffer[(ProcOffset + i) & 32767],
                  ProcOffset + i);
            }

            ProcOffset += duplength;
            runlength = 0;
            continue;
         }

         AddByteOffset(RingBuffer[ProcOffset & 32767], ProcOffset);
         ProcOffset++;
         runlength++;

         if( runlength >= 0x3ffe )
         {
            WriteLiteral(runlength, outfile);
            runlength = 0;
         }
      }

      if( runlength > 0 )
         WriteLiteral(runlength, outfile);

      fputc(iChecksum, outfile);
   }
   else
   {
      while( (i = GetWord(infile)) != -1 )
      {
         if( (i & 0x8000) == 0 )
         {
            len = i & 0x3fff;
            if( (i & 0x4000) == 0 )
            {
               for(i = 0; i < len; i++)
               {
                  PutByte(GetByte(ProcOffset, infile), outfile);
                  ProcOffset++;
               }
            }
            else
            {
               bit = 8;
               for(i = x = byte = 0; i < len;)
               {
                  if( bit > 7 )
                  {
                     if( (byte = fgetc(infile)) == EOF )
                        break;
                     bit = 0;
                  }
                  branch = ((byte & (1 << bit)) == 0) ? Left : Right;
                  if( branch[x] <= 0 )
                  {
                     RingBuffer[(ProcOffset + i) & 32767] = (BYTE)(-branch[x]);
                     i++;
                     x = 0;
                  }
                  else
                  {
                     x = branch[x];
                  }
                  bit++;
               }

               for(i = 0; i < len; i++)
                  PutByte(RingBuffer[(ProcOffset + i) & 32767], outfile);
               LimitOffset = ProcOffset += len;
            }
         }
         else
         {
            if( (i & 0x4000) == 0 )  len = fgetc(infile);
            else                     len = GetWord(infile);
            offset = i & 0x3fff;

            for(i = 0; i < len; i++)
            {
               PutByte(RingBuffer[ProcOffset & 32767] =
                       RingBuffer[(ProcOffset - offset) & 32767], outfile);
               ProcOffset++;
            }
            LimitOffset = ProcOffset;
         }
      }

      if( iChecksum != oChecksum )
         fputs("Checksum failed\n", stderr);
   }

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