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

   Preprocess 6: optimize.

   09/15/01
                                                                           */

#include<stdio.h>

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

typedef unsigned char BYTE;

BYTE RingBuffer[1<<15],
     GenericBuffer[1<<14],
     BitTable[128][16];

int Left[] =
{
      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
},
    Right[] =
{
     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
},
    LengthTable[128],
    ProcOffset, LimitOffset,
    FileSize, iChecksum, oChecksum,

    FirstIndex[256], LastIndex[256],
    NextIndex[1<<14],
    ByteOffset[1<<14],

    i, x, bit, byte, runlength,
    duplength, dupoffset, maxoffset, maxlen, offset, len, *branch, index;

FILE *infile, *outfile;

void AddByteOffset()
{
   byte = RingBuffer[ProcOffset & 32767];
   for(maxlen = 0; maxlen < 256; maxlen++)
      if( FirstIndex[maxlen] )
         if( (ProcOffset - ByteOffset[FirstIndex[maxlen]]) > 16380 )
            break;

   if( !(FirstIndex[maxlen] = NextIndex[maxoffset = FirstIndex[maxlen]]) )
      LastIndex[maxlen] = 0;

   ByteOffset[
      LastIndex[byte] =
         LastIndex[byte]
            ? (NextIndex[LastIndex[byte]] = maxoffset)
            : (FirstIndex[byte] = maxoffset)] = ProcOffset++;
   NextIndex[maxoffset] = 0;
}

void InitEntry()
{
   LengthTable[-byte] = x;
   for(i = 0; i < x; i++)
      BitTable[-byte][i] = GenericBuffer[i];
}

void InitTableEntries(int arg_index)
{
   GenericBuffer[x++] = 0;
   if( (byte = Left[arg_index]) < 1 )  InitEntry();
   else                                InitTableEntries(byte);

   GenericBuffer[x - 1] = 1;
   if( (byte = Right[arg_index]) < 1 ) InitEntry();
   else                                InitTableEntries(byte);

   GenericBuffer[--x] = 0;
}

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

   return arg_absoffset < FileSize ? RingBuffer[arg_absoffset & 32767] : -1;
}

int GetWord()
{
   if( (bit = fgetc(infile)) == EOF ||
       (byte = fgetc(infile)) == EOF )
   {
      iChecksum = bit;
      return -1;
   }

   return (byte << 8) | bit;
}

void PutByte(int arg_byte)
{
   oChecksum ^= arg_byte;
   fputc(arg_byte, outfile);
}

void PutWord(int arg_word)
{
   oChecksum ^= arg_word & 255;
   oChecksum ^= arg_word >> 8;
   fputc(arg_word & 255, outfile);
   fputc(arg_word >> 8, outfile);
}

void WriteLiteral()
{
   for(i = x = bit = byte = 0; i < runlength && x < runlength; i++)
   {
      maxlen = RingBuffer[(ProcOffset - runlength + i) & 32767];

      if( maxlen & 128 )
         x = runlength;
      else
         for(maxoffset = 0; maxoffset < LengthTable[maxlen]; maxoffset++)
         {
            byte |= ((int)BitTable[maxlen][maxoffset]) << (bit++);
            if( bit > 7 )
            {
               GenericBuffer[x++] = (BYTE)byte;
               bit = byte = 0;
            }
         }
   }

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

   if( x < runlength )
   {
      PutWord(16384 | runlength);
      for(i = 0; i < x; PutByte(GenericBuffer[i++]));
   }
   else
   {
      PutWord(runlength);
      for(i = 0; i < runlength; i++)
         PutByte(RingBuffer[(ProcOffset - runlength + i) & 32767]);
   }

   runlength = 0;
}

int main(int argc, char **argv)
{
   infile = argc > 2 ? fopen(argv[2], "rb") : stdin;
   outfile = argc > 3 ? fopen(argv[3], "wb+") : stdout;
   if( !infile || !outfile )
      return 1;
   SetBinary(infile);
   SetBinary(outfile);

   for(i = iChecksum = oChecksum = ProcOffset = LimitOffset = 0;
       i < 32768; RingBuffer[i++] = 0);
   FileSize = 1<<30;

   if( *argv[1] - 120 )
   {
      for(i = 0; i < 256; i++)
         FirstIndex[i] = LastIndex[i] = 0;

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

      for(InitTableEntries(runlength = 0); GetByte(ProcOffset) + 1;)
      {
         maxoffset = maxlen = 0;

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

            if( len < maxlen )
               break;

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

         duplength = maxlen;
         dupoffset = ProcOffset - maxoffset;

         if( duplength > 4 )
         {
            if( runlength )
               WriteLiteral();

            if( duplength < 256 )
            {
               PutWord(32768 | dupoffset);
               PutByte(duplength);
            }
            else
            {
               PutWord(49152 | dupoffset);
               PutWord(duplength);
            }

            for(i = 0; i < duplength; i++)
               AddByteOffset();
            continue;
         }

         AddByteOffset();
         runlength++;

         if( runlength > 16381 )
            WriteLiteral();
      }

      if( runlength > 0 )
         WriteLiteral();

      fputc(iChecksum, outfile);
   }
   else
   {
      for(; (i = GetWord()) + 1;)
      {
         if( i & 32768 )
         {
            if( i & 16384 )  len = GetWord();
            else             len = fgetc(infile);
            offset = i & 16383;

            for(i = 0; i < len; i++)
            {
               PutByte(RingBuffer[ProcOffset & 32767] =
                       RingBuffer[(ProcOffset - offset) & 32767]);
               ProcOffset++;
            }
            LimitOffset = ProcOffset;
         }
         else
         {
            len = i & 16383;
            if( i & 16384 )
            {
               bit = 8;
               for(i = x = byte = 0; i < len;)
               {
                  if( bit > 7 )
                  {
                     if( (byte = fgetc(infile)) == EOF )
                        break;
                     bit = 0;
                  }
                  branch = (byte & (1 << bit)) ? Right : Left;
                  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]);
               LimitOffset = ProcOffset += len;
            }
            else
            {
               for(i = 0; i < len; i++)
               {
                  PutByte(GetByte(ProcOffset));
                  ProcOffset++;
               }
            }
         }
      }

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

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