/* c11a.c (c11.c) - Don Yang (uguu.org)

   Preprocess 1: Combine sources, remove debug output.

   06/02/00
                                                                           */

#include<stdio.h>

/* Constants */
#define HISTORY_SIZE    0x7fff
#define BUFFER_SIZE     ((HISTORY_SIZE + 1) * 2)
#define MINIMUM_MATCH   5
#define BYTES_PER_HASH  1024

/* Ring buffer */
static int buffer[BUFFER_SIZE];  /* 64K * sizeof(int) */
static int bindex;               /* Ring buffer index (current position) */
static int blength;              /* Bytes read ahead */

/* Other globals */
static int run;            /* Number of unmatched bytes */
static int isize, osize;   /* File sizes */
static int isum, osum;     /* XOR of all bytes */

/* Input wrapper */
static int input(void)
{
   int data;

   isize++;
   isum ^= (data = getchar());
   if( data == EOF )
      isum ^= EOF;
   if( isize % BYTES_PER_HASH == 0 )
      fputc('.', stderr);
   return data;

} /* input() */

/* Output wrapper */
static void output(int data)
{
   osize++;
   osum ^= (data &= 0xff);
   putchar(data);

} /* output() */

/* Seek forward in ring buffer */
static void bseek(int offset)
{
   for(; offset; offset--)
   {
      bindex = (bindex + 1) % BUFFER_SIZE;
      if( !(--blength) )
      {
         buffer[bindex] = input();
         blength++;
      }
   }

} /* bseek() */

/* Character reader wrapper */
static int bgetc(int offset)
{
   for(; offset >= blength; blength++)
      buffer[(bindex + blength) % BUFFER_SIZE] = input();

   return buffer[(bindex + offset + BUFFER_SIZE) % BUFFER_SIZE];

} /* bgetc() */

/* Flush unmatched characters */
static void bflush(void)
{
   /* Write header (intel order) */
   output(run);
   output(run >> 8);

   /* Write data */
   for(; run; run--)
      output(bgetc(-run));

} /* bflush() */

/* main */
int main(int argc)
{
   int code, length, source, i, j;

   /* Reset */
   isize = osize = isum = osum = 0;
   for(i = bindex = 0; i < BUFFER_SIZE; buffer[i++] = 0);

   if( argc > 1 )    /* Decode */
   {
      /* Decompress stdin */
      for(i = input(); i != EOF; i = input())
      {
         if( (j = input()) == EOF )
            break;      /* One byte sequence -> first byte is checksum */

         length = i | (j << 8);
         if( length & 0x8000 )
         {
            /* Read from history */
            source = length | 0xffff0000;

            i = input();
            j = input();
            length = i | (j << 8);

            for(i = 0; i < length; i++)
            {
               output(
                  buffer[(bindex + i) % BUFFER_SIZE] =
                  buffer[(bindex + i + source + BUFFER_SIZE) % BUFFER_SIZE]);
            }
            bindex = (bindex + length) % BUFFER_SIZE;
         }
         else
         {
            /* Uncompressed data */
            for(i = 0; i < length; i++)
               output(buffer[(bindex + i) % BUFFER_SIZE] = input());
            bindex = (bindex + length) % BUFFER_SIZE;
         }
      }

      if( osum ^ i )
         fprintf(stderr, "Checksum failed.\n");

      isize ^= osize;
      osize ^= isize;
      isize ^= osize;
   }

   else              /* Encode */
   {
      /* Initialize ring buffer */
      buffer[0] = input();
      blength = 1;

      /* Compress bytes, starting with 0 bytes matched in pattern */
      for(code = bgetc(run = 0); code != EOF; code = bgetc(0))
      {
         /* Match pattern in history */
         i = 0;
         for( source = -MINIMUM_MATCH; source > -HISTORY_SIZE; source--)
         {
            if( bgetc(source) == code )
            {
               /* First character matched, try match more */
               for(length = 1; length < -source; length++)
               {
                  if( bgetc(source + length) != bgetc(length) )
                     break;
               }
               if( length > i )
               {
                  i = length;
                  j = source;
               }
            }
         }

         if( i > MINIMUM_MATCH )
         {
            /* Pattern matched */

            /* Flush unmatched data */
            if( run )
               bflush();

            /* Write matched data (intel order) */
            output(j);
            output(j >> 8);
            output(i);
            output(i >> 8 );

            /* Skip over matched data */
            bseek(i);
         }
         else
         {
            /* Pattern not matched */
            bseek(1);
            run++;
            if( run >= HISTORY_SIZE )
               bflush();
         }
      }

      /* Flush last unmatched pattern */
      if( run )
         bflush();

      /* Write checksum */
      output(isum);
   }

   isize--;
   fprintf(stderr, "\n%d/%d\n", osize, isize);
   return 0;

} /* main() */