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

   Decompress from stdin to stdout.
   Assume 32bit int.

   This is a O(N) algorithm, meaning decompression is fast no matter what
   size the input is.  Unlike the encoder, this one is more like O(3 * N) or
   something like that, so it's fast ^_^;;

   Using results from encode.c (decompressing encoded boot image):

      ./decode < image > bzImage.test
         0.400u 0.010s 0:00.43 95.3% 0+0k 0+0io 240pf+0w

      unrar e image.rar
         0.200u 0.040s 0:00.48 50.0% 0+0k 0+0io 410pf+0w

      gunzip -c image > bzImage.test
         0.080u 0.020s 0:00.10 100.0% 0+0k 0+0io 93pf+0w

   Decompressing logs:

      ./decode < test2.txt > test.txt.test
         0.020u 0.000s 0:00.02 100.0% 0+0k 0+0io 95pf+0w

      unrar e test.rar
         0.030u 0.000s 0:00.04s 75.0% 0+0k 0+0io 170pf+0w

      gunzip -c test2.txt > test.txt.test
         0.000u 0.000s 0:00.00 0.0% 0+0k 0+0io 94pf+0w

   For original data sources, see encode.c.

   06/01/00
                                                                           */
#include<stdio.h>

/* Constants */
#define HISTORY_SIZE    0x7fff
#define BUFFER_SIZE     ((HISTORY_SIZE + 1) * 2)

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

/* Other globals */
static int isize, osize;   /* File sizes */
static int isum, osum;     /* XOR of all bytes */
#ifdef DEBUG
   static FILE *logfile;   /* Debug log */
#endif

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

   isize++;
   isum ^= (data = getchar());
   if( data == EOF )
      isum ^= EOF;
   return data;

} /* input() */

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

} /* output() */

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

   #ifdef DEBUG
      logfile = fopen("decode.log", "wt+");
   #endif

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

   /* Decompress stdin */
   for(i = input(); i != EOF; i = input())
   {
      if( (j = input()) == EOF )
      {
         isize--;
         #ifdef DEBUG
            fprintf(logfile, "Checksum = %d\n", i);
         #endif
         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);

         #ifdef DEBUG
            fprintf(logfile, "Pattern:%d (%d)\n", length, source);
         #endif

         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 */
         #ifdef DEBUG
            fprintf(logfile, "Run:%d\n", length);
         #endif

         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;
   fprintf(stderr, "decompressed %d/%d\n", osize, isize);
   #ifdef DEBUG
      fprintf(logfile, "%d/%d = %f\n",
         osize, isize, ((float)osize) / (float)isize);
      fclose(logfile);
   #endif

   return 0;

} /* main() */