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

   lclint +posixlib encode.c common.c

   09/12/01
                                                                           */

#ifdef _WIN32
   #include<io.h>
#else
   #include<unistd.h>
#endif
#include<assert.h>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"common.h"

/* Performance tuning variables */
#define MIN_SUBSTRING_LENGTH  5
#define MIN_PATCH_INDEX       6
#define MIN_GAIN_PER_PATCH    6


static void Encode(FILE *infile, FILE *outfile);
static void EncodeDebug(FILE *infile, FILE *outfile);
static int  FindPreviousSubstring(FILE *infile, /*@out@*/int *length);
static int  TrailingBytesMatched(int index, int negoffset, FILE *infile);
static void WriteLiteral(int length, FILE *outfile);
static int  WriteLiteralDebug(int length, FILE *outfile);
static void WriteSubstring(int length, int negoffset, FILE *outfile);
static int  WriteSubstringDebug(int length, int negoffset, FILE *outfile);

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

   /* Set input/output */
   infile = stdin;
   outfile = stdout;
   if( argc > 1 && argv[1][0] != '-' )
   {
      if( (infile = fopen(argv[1], "rb")) == NULL )
         return printf("Can not open %s\n", argv[1]);
   }
   if( argc > 2 )
   {
      if( (outfile = fopen(argv[2], "wb+")) == NULL )
      {
         (void)fclose(infile);
         return printf("Can not create %s\n", argv[2]);
      }
   }

   /* Initialize ring buffer */
   memset(RingBuffer, 0, BUFFER_SIZE);
   iChecksum = ProcOffset = InputOffset = 0;
   FileSize = 0x7fffffff;

   /* Compress stream */
   if( isatty(fileno(outfile)) != 0 )
   {
      (void)puts("Output is a tty");
      argc = 4;
   }
   if( argc > 3 )
   {
      (void)puts("Using debug encoder");
      EncodeDebug(infile, outfile);
   }
   else
   {
      Encode(infile, outfile);
   }

   /* End */
   (void)fclose(infile);
   (void)fclose(outfile);
   return 0;

} /* main() */


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

   runlength = 0;
   while( GetByte(ProcOffset, infile) != INPUT_EOF )
   {
      if( (dupoffset = FindPreviousSubstring(infile, &duplength)) != 0 )
      {
         /* Found matched substring, check minimum length */
         if( duplength >= MIN_SUBSTRING_LENGTH )
         {
            if( runlength > 0 )
               WriteLiteral(runlength, outfile);
            WriteSubstring(duplength, dupoffset, outfile);
            ProcOffset += duplength;
            runlength = 0;
            continue;
         }
      }

      /* No qualifying substring, keep literal byte in buffer */
      ProcOffset++;
      runlength++;

      if( runlength >= HALF_BUFFER_SIZE )
      {
         /* Flush literal block */
         WriteLiteral(runlength, outfile);
         runlength = 0;
      }
   }

   /* Flush literal block */
   if( runlength > 0 )
      WriteLiteral(runlength, outfile);

   /* Write checksum */
   (void)fputc(iChecksum, outfile);

} /* Encode() */

/************************************************************* EncodeDebug */
static void EncodeDebug(FILE *infile, FILE *outfile)
{
   int runlength, duplength, dupoffset, cmpsize;
   DWORD byte;

   runlength = cmpsize = 0;
   while( (byte = GetByte(ProcOffset, infile)) != INPUT_EOF )
   {
      if( isprint((int)byte) )
      {
         fprintf(outfile, "%08x: %02x '%c'\n",
            (DWORD)ProcOffset, byte, (char)byte);
      }
      else
      {
         fprintf(outfile, "%08x: %02x\n", (DWORD)ProcOffset, byte);
      }

      if( (dupoffset = FindPreviousSubstring(infile, &duplength)) != 0 )
      {
         /* Found matched substring, check minimum length */
         if( duplength >= MIN_SUBSTRING_LENGTH )
         {
            if( runlength > 0 )
               cmpsize += WriteLiteralDebug(runlength, outfile);
            cmpsize += WriteSubstringDebug(duplength, dupoffset, outfile);
            ProcOffset += duplength;
            runlength = 0;
            continue;
         }
      }

      /* No qualifying substring, keep literal byte in buffer */
      ProcOffset++;
      runlength++;

      if( runlength >= HALF_BUFFER_SIZE )
      {
         /* Flush literal block */
         cmpsize += WriteLiteralDebug(runlength, outfile);
         runlength = 0;
      }
   }

   /* Flush literal block */
   if( runlength > 0 )
      cmpsize += WriteLiteralDebug(runlength, outfile);

   fprintf(outfile,
      "Checksum = %d\n"
      "Original size = %d bytes\n"
      "Compressed size = %d bytes\n",
      iChecksum, FileSize, cmpsize);

} /* EncodeDebug() */

/*************************************************** FindPreviousSubstring */
static int FindPreviousSubstring(FILE *infile, int *length)
{
   int maxindex, maxlen;
   int negoffset, i;

   maxlen = maxindex = 0;

   /* Try each position (using very slow brute force search) */
   for(negoffset = 0; negoffset < HALF_BUFFER_SIZE; negoffset++)
   {
      /* Compare substring bytes up to current position */
      for(i = 0; i < negoffset; i++)
      {
         assert(ProcOffset + i - negoffset < ProcOffset);
         if( GetByte(ProcOffset + i - negoffset, infile) !=
             GetByte(ProcOffset + i, infile) )
         {
            if( i < MIN_PATCH_INDEX )
               break;
            if( TrailingBytesMatched(i + 1, negoffset, infile)
                  < MIN_GAIN_PER_PATCH )
               break;
         }
      }

      if( i > maxlen )
      {
         maxindex = negoffset;
         maxlen = i;
      }
   }

   *length = maxlen;
   return maxindex;

} /* FindPreviousSubstring() */

/**************************************************** TrailingBytesMatched */
static int  TrailingBytesMatched(int index, int negoffset, FILE *infile)
{
   int i, length;

   length = 0;
   for(i = index; i < negoffset && length < MIN_GAIN_PER_PATCH; i++)
   {
      if( GetByte(ProcOffset + i - negoffset, infile) !=
          GetByte(ProcOffset + i, infile) )
         return length;
      length++;
   }

   return length;

} /* TrailingBytesMatched() */

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

   assert(length <= HALF_BUFFER_SIZE);
   PutWord((WORD)length, outfile);

   for(i = 0; i < length; i++)
      PutByte(RingBuffer[(ProcOffset - length + i) & BUFFER_MASK], outfile);

} /* WriteLiteral() */

/******************************************************* WriteLiteralDebug */
static int WriteLiteralDebug(int length, FILE *outfile)
{
   int i;

   (void)fputs("literal:", outfile);
   for(i = 0; i < length && i < 16; i++)
   {
      fprintf(outfile, " %02x",
         (DWORD)RingBuffer[(ProcOffset - length + i) & BUFFER_MASK]);
   }
   if( length > 16 )
      (void)fputs(" ...", outfile);
   fprintf(outfile, " (%d bytes)\n", length);

   return 2 + length;

} /* WriteLiteralDebug() */

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

   /* Write substring reference */
   if( length < 256 )
   {
      PutWord((WORD)(0x8000 | negoffset), outfile);
      PutByte((BYTE)length, outfile);
   }
   else
   {
      PutWord((WORD)(0xc000 | negoffset), outfile);
      PutWord((WORD)length, outfile);
   }

   /* Write patching bytes */
   for(i = 0; i < length; i++)
   {
      if( RingBuffer[(ProcOffset + i - negoffset) & BUFFER_MASK] !=
          RingBuffer[(ProcOffset + i) & BUFFER_MASK] )
      {
         PutWord((WORD)(0x4000 | (length - i)), outfile);
         PutByte(RingBuffer[(ProcOffset + i) & BUFFER_MASK], outfile);
      }
   }

} /* WriteSubstring() */

/***************************************************** WriteSubstringDebug */
static int WriteSubstringDebug(int length, int negoffset, FILE *outfile)
{
   int i, p;

   fprintf(outfile, "substring: matched %08x, %d bytes\n          ",
      (DWORD)(ProcOffset - negoffset), length);
   for(i = 0; i < length && i < 16; i++)
   {
      fprintf(outfile, " %02x",
         (DWORD)RingBuffer[(ProcOffset - negoffset + i) & BUFFER_MASK]);
   }
   if( length > 16 )
      (void)fputs(" ...", outfile);
   (void)fputc('\n', outfile);

   for(i = p = 0; i < length; i++)
   {
      if( RingBuffer[(ProcOffset - negoffset + i) & BUFFER_MASK] !=
         RingBuffer[(ProcOffset + i) & BUFFER_MASK] )
      {
         fprintf(outfile, "patch %08x: %02x\n",
            (DWORD)(ProcOffset + i),
            (DWORD)RingBuffer[(ProcOffset + i) & BUFFER_MASK]);
         p++;
      }
   }

   return ((length < 256) ? 3 : 4) + 3 * p;

} /* WriteSubstringDebug() */