/* compress.c -- Byte Pair Encoding compression */

 /* Copyright 1996 Philip Gage */

 /* This program appeared in the September 1997 issue of

  * C/C++ Users Journal. The original source code may still

  * be found at the web site of the magazine (www.cuj.com).

  *

  * It has been modified by me (Thiadmer Riemersma) to

  * compress only a section of the input file and to store

  * the compressed output along with the input as "C" strings.

  *

  * Compiling instructions:

  *  Borland C++ 16-bit (large memory model is required):

  *      bcc -ml scpack.c

  *

  *  Watcom C/C++ 32-bit:

  *      wcl386 scpack.c

  *

  *  GNU C (Linux), 32-bit:

  *      gcc scpack.c -o scpack

  */

 #include <assert.h>

 #include <limits.h>

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #if UINT_MAX > 0xFFFFU

   #define MAXSIZE 1024*1024L

 #else

   #define MAXSIZE UINT_MAX      /* Input file buffer size */

 #endif

 #define HASHSIZE 8192   /* Hash table size, power of 2 */

 #define THRESHOLD   3   /* Increase for speed, min 3 */

 #define START_TOKEN "#ifdef SCPACK" /* start reading the buffer here */

 #define NAME_TOKEN  "#define SCPACK_TABLE"

 #define SEP_TOKEN   "#define SCPACK_SEPARATOR"

 #define TERM_TOKEN  "#define SCPACK_TERMINATOR"

 #define TEMPFILE    "~SCPACK.TMP"

 static char tablename[32+1] = "scpack_table";

 static char separator[16]=",";

 static char terminator[16]="";

 int compress(unsigned char *buffer, unsigned buffersize, unsigned char pairtable[128][2])

 {

   unsigned char *left, *right, *count;

   unsigned char a, b, bestcount;

   unsigned i, j, index, bestindex, code=128;

   /* Dynamically allocate buffers and check for errors */

   left = (unsigned char *)malloc(HASHSIZE);

   right = (unsigned char *)malloc(HASHSIZE);

   count = (unsigned char *)malloc(HASHSIZE);

   if (left==NULL || right==NULL || count==NULL) {

     printf("Error allocating memory\n");

     exit(1);

   }

   /* Check for errors */

   for (i=0; i<buffersize; i++)

     if (buffer[i] > 127) {

       printf("This program works only on text files (7-bit ASCII)\n");

       exit(1);

     }

   memset(pairtable, 0, 128*2*sizeof(char));

   do {  /* Replace frequent pairs with bytes 128..255 */

     /* Enter counts of all byte pairs into hash table */

     memset(count,0,HASHSIZE);

     for (i=0; i<buffersize-1; i++) {

       a = buffer[i];

       b = buffer[i+1];

       /* ignore any pair with a '\0' */

       if (a == 0 || b == 0)

         continue;

       index = (a ^ (b << 6)) & (HASHSIZE-1);

       while ((left[index] != a || right[index] != b) &&

              count[index] != 0)

         index = (index + 1) & (HASHSIZE-1);

       left[index] = a;

       right[index] = b;

       if (count[index] < 255)

         count[index] += (unsigned char)1;

     }

     /* Search hash table for most frequent pair */

     bestcount = THRESHOLD - 1;

     for (i=0; i<HASHSIZE; i++) {

       if (count[i] > bestcount) {

         bestcount = count[i];

         bestindex = i;

       }

     }

     /* Compress if enough occurrences of pair */

     if (bestcount >= THRESHOLD) {

       /* Add pair to table using code as index */

       a = pairtable[code-128][0] = left[bestindex];

       b = pairtable[code-128][1] = right[bestindex];

       /* Replace all pair occurrences with unused byte */

       for (i=0, j=0; i<buffersize; i++, j++)

         if (a == buffer[i] && b == buffer[i+1]) {

           buffer[j] = (unsigned char)code;

           ++i;

         }

         else

           buffer[j] = buffer[i];

       buffersize = j;

     }

     else

       break;

   } while (++code < 255);

   /* done */

   free(left); free(right); free(count);

   return buffersize;  /* return adjusted buffersize */

 }

 static int strmatch(char *str, char *token, int *indent)

 {

   int i = 0;

   /* skip whitespace */

   while (*str==' ' || *str=='\t') {

     str++;

     i++;

   } /* while */

   if (strncmp(str,token,strlen(token))!=0)

     return 0;

   if (indent != NULL)

     *indent = i;

   return 1;

 }

 static void check_if(char *str,int linenr)

 {

   if (strmatch(str,"#if",NULL)) {

     printf("Error: \"#if...\" preprocessor statement should not be in SCPACK section "

            "(line %d)\n", linenr);

     exit(1);

   } /* if */

 }

 static int check_tablename(char *str)

 {

   int i;

   if (strmatch(str,NAME_TOKEN,NULL)) {

     str += strlen(NAME_TOKEN);

     while (*str==' ' || *str=='\t')

       str++;

     for (i=0; i<(sizeof tablename - 1) && *str!='\0' && strchr(" \t\n",*str)==NULL; i++, str++)

       tablename[i] = *str;

     tablename[i] = '\0';

     return 1;

   } /* if */

   return 0;

 }

 static int check_separator(char *str)

 {

   int i;

   if (strmatch(str,SEP_TOKEN,NULL)) {

     str += strlen(SEP_TOKEN);

     while (*str==' ' || *str=='\t')

       str++;

     for (i=0; i<(sizeof separator - 1) && *str!='\0' && strchr(" \t\n",*str)==NULL; i++, str++)

       separator[i] = *str;

     separator[i] = '\0';

     return 1;

   } /* if */

   if (strmatch(str,TERM_TOKEN,NULL)) {

     str += strlen(TERM_TOKEN);

     while (*str==' ' || *str=='\t')

       str++;

     for (i=0; i<(sizeof terminator - 1) && *str!='\0' && strchr(" \t\n",*str)==NULL; i++, str++)

       terminator[i] = *str;

     terminator[i] = '\0';

     return 1;

   } /* if */

   return 0;

 }

 /* readbuffer

  * Reads in the input file and stores all strings in the

  * section between "#ifdef SCPACK" and "#else" in a buffer.

  * Only text that is between double quotes is added to the

  * buffer; the \" escape code is handled. Multiple strings

  * on one line are handled.

  */

 unsigned readbuffer(FILE *input, unsigned char *buffer)

 {

   char str[256];

   unsigned buffersize;

   int i,linenr;

   linenr=0;

   buffersize=0;

   rewind(input);

   while (!feof(input)) {

     while (fgets(str,sizeof str,input)!=NULL) {

       linenr++;

       check_tablename(str);

       check_separator(str);

       if (strmatch(str,START_TOKEN,NULL))

         break;

     } /* while */

     if (!strmatch(str,START_TOKEN,NULL))

       return buffersize;  /* no (more) section found, quit */

     while (fgets(str,sizeof str,input)!=NULL) {

       linenr++;

       check_if(str,linenr);

       if (check_tablename(str))

         printf("Error: table name definition should not be in SCPACK section (line %d)\n", linenr);

       check_separator(str);

       if (strmatch(str,"#else",NULL))

         break;          /* done */

       /* add to the buffer only what is between double quotes */

       i=0;

       do {

         while (str[i]!='\0' && str[i]!='"')

           i++;

         if (str[i]=='"') {

           /* we are in a string */

           i++;

           while (str[i]!='\0' && str[i]!='"') {

             /* handle escape sequences */

             if (str[i]=='\\') {

               i++;

               switch (str[i]) {

               case 'a': /* alarm */

                 buffer[buffersize++]='\a';

                 i++;

                 break;

               case 'b': /* backspace */

                 buffer[buffersize++]='\b';

                 i++;

                 break;

               case 'f': /* form feed */

                 buffer[buffersize++]='\f';

                 i++;

                 break;

               case 'n': /* newline */

                 buffer[buffersize++]='\n';

                 i++;

                 break;

               case 'r': /* carriage return */

                 buffer[buffersize++]='\n';

                 i++;

                 break;

               case 't': /* tab */

                 buffer[buffersize++]='\t';

                 i++;

                 break;

               case '\'':

                 buffer[buffersize++]='\'';

                 i++;

                 break;

               case '"':

                 buffer[buffersize++]='"';

                 i++;

                 break;

               default:

                 // ??? octal character code escapes and hexadecimal escapes

                 //     not supported

                 printf("Unknown escape sequence '\\%c' on line %d\n",

                        str[i], linenr);

               } /* switch */

             } else {

               buffer[buffersize++]=str[i++];

             } /* if */

           } /* while */

           if (str[i]=='"') {

             buffer[buffersize++]='\0'; /* terminate each string */

             i++;

           } else {

             printf("Error: unterminated string on line %d\n",linenr);

           } /* if */

         } /* if */

       } while (str[i]!='\0');

     } /* while - in SCPACK section */

     /* put in another '\0' to terminate the section */

     buffer[buffersize++]='\0';

   } /* while - !feof(input) */

   return buffersize;

 }

 static void write_pairtable(FILE *output, unsigned char pairtable[128][2], char *tablename)

 {

   int i;

   /* dump the pair table */

   fprintf(output, "/*-*SCPACK start of pair table, do not change or remove this line */\n");

   fprintf(output, "unsigned char %s[][2] = {", tablename);

   for (i=0; i<128 && pairtable[i][0]!=0 && pairtable[i][1]!=0; i++) {

     if ((i % 16)==0)

       fprintf(output, "\n  ");

     else

       fprintf(output, " ");

     fprintf(output, "{%d,%d}", pairtable[i][0], pairtable[i][1]);

     /* check if something follows this pair */

     if (i+1<128 && pairtable[i+1][0]!=0 && pairtable[i+1][1]!=0)

       fprintf(output, ",");

   } /* for */

   fprintf(output, "\n};\n");

   fprintf(output, "/*-*SCPACK end of pair table, do not change or remove this line */\n");

 }

 void writefile(FILE *input, FILE *output, unsigned char *buffer, unsigned buffersize, unsigned char pairtable[128][2])

 {

   char str[256];

   int insection, indent, needseparator;

   unsigned char *bufptr;

   bufptr = buffer;

   insection = 0;

   rewind(input);

   while (!feof(input)) {

     while (fgets(str,sizeof str,input)!=NULL) {

       fprintf(output,"%s",str);

       if (check_tablename(str)) {

         write_pairtable(output, pairtable, tablename);

         /* strip an existing pair table from the file */

         if (fgets(str,sizeof str,input)!=NULL) {

           if (strmatch(str,"/*-*SCPACK",NULL)) {

             while (fgets(str,sizeof str,input)!=NULL)

               if (strmatch(str,"/*-*SCPACK",NULL))

                 break;

           } else {

             fprintf(output,"%s",str);

           } /* if */

         } /* if */

       } /* if */

       if (strmatch(str,START_TOKEN,NULL))

         insection = 1;

       if (insection && strmatch(str,"#else",NULL))

         break;

     } /* while */

     if (!strmatch(str,"#else",&indent))

       return;           /* no (more) section found, quit */

     insection=0;

     /* dump the buffer as strings, separated with commas */

     needseparator = 0;

     while (*bufptr != '\0') {

       assert((unsigned)(bufptr-buffer) < buffersize);

       if (needseparator)

         fprintf(output, "%s\n",separator);

       fprintf(output, "%*c\"",indent+2,' ');

       /* loop over string */

       while (*bufptr != '\0') {

         if (*bufptr<' ' || *bufptr >= 128 || *bufptr == '"' || *bufptr == '\\')

           fprintf(output, "\\%03o", *bufptr);

         else

           fprintf(output, "%c", *bufptr);

         bufptr++;

       } /* while */

       fprintf(output, "\"");

       needseparator = 1;

       bufptr++;           /* skip '\0' */

     } /* while */

     fprintf(output, "%s\n",terminator);

     bufptr++;

     /* skip the input file until the #endif section */

     while (fgets(str,sizeof str,input)!=NULL) {

       if (strmatch(str,"#endif",NULL)) {

         fprintf(output,"%s",str);

         break;          /* done */

       } /* if */

     } /* while */

   } /* while - !feof(input) */

 }

 static void usage(void)

 {

   printf("Usage: scpack <filename> [output file]\n");

   exit(1);

 }

 int main(int argc, char **argv)

 {

   FILE *in, *out;

   unsigned char *buffer;

   unsigned buffersize, orgbuffersize;

   unsigned char pairtable[128][2];

   if (argc < 2 || argc > 3)

     usage();

   if ((in=fopen(argv[1],"rt"))==NULL) {

     printf("SCPACK: error opening input %s\n",argv[1]);

     usage();

   } /* if */

   if (argc == 2) {

     if ((out=fopen(TEMPFILE,"wt"))==NULL) {

       printf("SCPACK: error opening temporary file %s\n",TEMPFILE);

       usage();

     } /* if */

   } else {

     if ((out=fopen(argv[2],"wt"))==NULL) {

       printf("SCPACK: error opening output file %s\n",argv[2]);

       usage();

     } /* if */

   } /* if */

   buffer = (unsigned char *)malloc(MAXSIZE);

   if (buffer == NULL) {

     printf("SCPACK: error allocating memory\n");

     return 1;

   } /* if */

   /* 1. read the buffer

    * 2. compress the buffer

    * 3. copy the file, insert the compressed buffer

    */

   buffersize = readbuffer(in, buffer);

   orgbuffersize = buffersize;

   if (buffersize > 0) {

     buffersize = compress(buffer, buffersize, pairtable);

     writefile(in, out, buffer, buffersize, pairtable);

     printf("SCPACK: compression ratio: %ld%% (%d -> %d)\n",

            100L-(100L*buffersize)/orgbuffersize, orgbuffersize, buffersize);

   } else {

     printf("SCPACK: no SCPACK section found, nothing to do\n");

   } /* if */

   fclose(out);

   fclose(in);

   /* let the new file replace the old file */

   if (buffersize == 0) {

     if (argc == 2)

       remove(TEMPFILE);

     else

       remove(argv[2]);

   } else if (argc == 2) {

     remove(argv[1]);

     rename(TEMPFILE,argv[1]);

   } /* if */

   return 0;

 }