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

   Preprocess 3: remove macros / comments.

   09/15/01
                                                                           */

#include<stdio.h>

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

typedef unsigned char BYTE;

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

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

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

static BYTE HuffmanBuffer[0x3ffe];

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

static void AddByteOffset(int byte, int offset);
static void Decode(FILE *infile, FILE *outfile);
static void Encode(FILE *infile, FILE *outfile);
static int  FindDuplicateSubstring(FILE *infile, int *length);
static void FindInit(void);
static int  GetByte(int absoffset, FILE *infile);
static int  GetWord(FILE *infile);
static void HuffmanDecode(int length, FILE *infile);
static int  HuffmanEncode(int length);
static void InitEntry(int index, int *string, int length);
static void InitTable(void);
static void InitTableEntries(int index, int *string);
static void PutByte(int data, FILE *outfile);
static void PutWord(int data, FILE *outfile);
static void ReadLiteral(int tag, FILE *infile, FILE *outfile);
static void ReadSubstring(int tag, FILE *infile, FILE *outfile);
static void WriteLiteral(int length, FILE *outfile);
static void WriteSubstring(int length, int negoffset, FILE *outfile);

int main(int argc, char **argv)
{
   FILE *infile, *outfile;
   int i;

   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' )
   {
      Encode(infile, outfile);
   }
   else
   {
      Decode(infile, outfile);
   }

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

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

static void Decode(FILE *infile, FILE *outfile)
{
   int tag;

   while( (tag = GetWord(infile)) != -1 )
   {
      if( (tag & 0x8000) == 0 )
         ReadLiteral(tag, infile, outfile);
      else
         ReadSubstring(tag, infile, outfile);
   }

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

static void Encode(FILE *infile, FILE *outfile)
{
   int runlength, duplength, dupoffset;

   FindInit();

   InitTable();

   runlength = 0;
   while( GetByte(ProcOffset, infile) != -1 )
   {
      dupoffset = FindDuplicateSubstring(infile, &duplength);
      if( duplength >= 5 )
      {
         if( runlength > 0 )
            WriteLiteral(runlength, outfile);
         WriteSubstring(duplength, dupoffset, outfile);
         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);
}

static int FindDuplicateSubstring(FILE *infile, int *length)
{
   int maxoffset, maxlen, index;
   int offset, len, i;

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

   *length = maxlen;
   return ProcOffset - maxoffset;
}

static void FindInit(void)
{
   int i, offset, index;

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

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

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

static void HuffmanDecode(int length, FILE *infile)
{
   int bit, byte, i, x, *branch;

   bit = 8;
   for(i = x = byte = 0; i < length;)
   {
      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++;
   }
}

static int HuffmanEncode(int length)
{
   int bit, byte, c, i, j, x, enclength;

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

      if( (c & 0x80) != 0 )
         return 0;

      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 )
               return 0;
            bit = byte = 0;
         }
      }
   }

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

   return (x >= length) ? 0 : x;
}

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

static void InitTable(void)
{
   int string[16];

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

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

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

static void ReadLiteral(int tag, FILE *infile, FILE *outfile)
{
   int length, i, byte;

   length = tag & 0x3fff;
   if( (tag & 0x4000) == 0 )
   {
      for(i = 0; i < length; i++)
      {
         byte = GetByte(ProcOffset, infile);
         ProcOffset++;
         PutByte(byte, outfile);
      }
   }
   else
   {
      HuffmanDecode(length, infile);
      for(i = 0; i < length; i++)
         PutByte(RingBuffer[(ProcOffset + i) & 32767], outfile);
      LimitOffset = ProcOffset += length;
   }
}

static void ReadSubstring(int tag, FILE *infile, FILE *outfile)
{
   int length, negoffset, i;

   if( (tag & 0x4000) == 0 )  length = fgetc(infile);
   else                       length = GetWord(infile);
   negoffset = tag & 0x3fff;

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

static void WriteLiteral(int length, FILE *outfile)
{
   int hlength, i;

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

static void WriteSubstring(int length, int negoffset, FILE *outfile)
{
   int i;

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

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