1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/sourcepawn/compiler/scpack.c Sat Nov 04 18:00:27 2006 +0000
1.3 @@ -0,0 +1,450 @@
1.4 +/* compress.c -- Byte Pair Encoding compression */
1.5 +/* Copyright 1996 Philip Gage */
1.6 +
1.7 +/* This program appeared in the September 1997 issue of
1.8 + * C/C++ Users Journal. The original source code may still
1.9 + * be found at the web site of the magazine (www.cuj.com).
1.10 + *
1.11 + * It has been modified by me (Thiadmer Riemersma) to
1.12 + * compress only a section of the input file and to store
1.13 + * the compressed output along with the input as "C" strings.
1.14 + *
1.15 + * Compiling instructions:
1.16 + * Borland C++ 16-bit (large memory model is required):
1.17 + * bcc -ml scpack.c
1.18 + *
1.19 + * Watcom C/C++ 32-bit:
1.20 + * wcl386 scpack.c
1.21 + *
1.22 + * GNU C (Linux), 32-bit:
1.23 + * gcc scpack.c -o scpack
1.24 + */
1.25 +
1.26 +#include <assert.h>
1.27 +#include <limits.h>
1.28 +#include <stdio.h>
1.29 +#include <stdlib.h>
1.30 +#include <string.h>
1.31 +
1.32 +#if UINT_MAX > 0xFFFFU
1.33 + #define MAXSIZE 1024*1024L
1.34 +#else
1.35 + #define MAXSIZE UINT_MAX /* Input file buffer size */
1.36 +#endif
1.37 +#define HASHSIZE 8192 /* Hash table size, power of 2 */
1.38 +#define THRESHOLD 3 /* Increase for speed, min 3 */
1.39 +
1.40 +#define START_TOKEN "#ifdef SCPACK" /* start reading the buffer here */
1.41 +#define NAME_TOKEN "#define SCPACK_TABLE"
1.42 +#define SEP_TOKEN "#define SCPACK_SEPARATOR"
1.43 +#define TERM_TOKEN "#define SCPACK_TERMINATOR"
1.44 +#define TEMPFILE "~SCPACK.TMP"
1.45 +static char tablename[32+1] = "scpack_table";
1.46 +static char separator[16]=",";
1.47 +static char terminator[16]="";
1.48 +
1.49 +int compress(unsigned char *buffer, unsigned buffersize, unsigned char pairtable[128][2])
1.50 +{
1.51 + unsigned char *left, *right, *count;
1.52 + unsigned char a, b, bestcount;
1.53 + unsigned i, j, index, bestindex, code=128;
1.54 +
1.55 + /* Dynamically allocate buffers and check for errors */
1.56 + left = (unsigned char *)malloc(HASHSIZE);
1.57 + right = (unsigned char *)malloc(HASHSIZE);
1.58 + count = (unsigned char *)malloc(HASHSIZE);
1.59 + if (left==NULL || right==NULL || count==NULL) {
1.60 + printf("Error allocating memory\n");
1.61 + exit(1);
1.62 + }
1.63 +
1.64 + /* Check for errors */
1.65 + for (i=0; i<buffersize; i++)
1.66 + if (buffer[i] > 127) {
1.67 + printf("This program works only on text files (7-bit ASCII)\n");
1.68 + exit(1);
1.69 + }
1.70 +
1.71 + memset(pairtable, 0, 128*2*sizeof(char));
1.72 +
1.73 + do { /* Replace frequent pairs with bytes 128..255 */
1.74 +
1.75 + /* Enter counts of all byte pairs into hash table */
1.76 + memset(count,0,HASHSIZE);
1.77 + for (i=0; i<buffersize-1; i++) {
1.78 + a = buffer[i];
1.79 + b = buffer[i+1];
1.80 + /* ignore any pair with a '\0' */
1.81 + if (a == 0 || b == 0)
1.82 + continue;
1.83 + index = (a ^ (b << 6)) & (HASHSIZE-1);
1.84 + while ((left[index] != a || right[index] != b) &&
1.85 + count[index] != 0)
1.86 + index = (index + 1) & (HASHSIZE-1);
1.87 + left[index] = a;
1.88 + right[index] = b;
1.89 + if (count[index] < 255)
1.90 + count[index] += (unsigned char)1;
1.91 + }
1.92 +
1.93 + /* Search hash table for most frequent pair */
1.94 + bestcount = THRESHOLD - 1;
1.95 + for (i=0; i<HASHSIZE; i++) {
1.96 + if (count[i] > bestcount) {
1.97 + bestcount = count[i];
1.98 + bestindex = i;
1.99 + }
1.100 + }
1.101 +
1.102 + /* Compress if enough occurrences of pair */
1.103 + if (bestcount >= THRESHOLD) {
1.104 +
1.105 + /* Add pair to table using code as index */
1.106 + a = pairtable[code-128][0] = left[bestindex];
1.107 + b = pairtable[code-128][1] = right[bestindex];
1.108 +
1.109 + /* Replace all pair occurrences with unused byte */
1.110 + for (i=0, j=0; i<buffersize; i++, j++)
1.111 + if (a == buffer[i] && b == buffer[i+1]) {
1.112 + buffer[j] = (unsigned char)code;
1.113 + ++i;
1.114 + }
1.115 + else
1.116 + buffer[j] = buffer[i];
1.117 + buffersize = j;
1.118 + }
1.119 + else
1.120 + break;
1.121 + } while (++code < 255);
1.122 +
1.123 + /* done */
1.124 + free(left); free(right); free(count);
1.125 + return buffersize; /* return adjusted buffersize */
1.126 +}
1.127 +
1.128 +static int strmatch(char *str, char *token, int *indent)
1.129 +{
1.130 + int i = 0;
1.131 +
1.132 + /* skip whitespace */
1.133 + while (*str==' ' || *str=='\t') {
1.134 + str++;
1.135 + i++;
1.136 + } /* while */
1.137 + if (strncmp(str,token,strlen(token))!=0)
1.138 + return 0;
1.139 + if (indent != NULL)
1.140 + *indent = i;
1.141 + return 1;
1.142 +}
1.143 +
1.144 +static void check_if(char *str,int linenr)
1.145 +{
1.146 + if (strmatch(str,"#if",NULL)) {
1.147 + printf("Error: \"#if...\" preprocessor statement should not be in SCPACK section "
1.148 + "(line %d)\n", linenr);
1.149 + exit(1);
1.150 + } /* if */
1.151 +}
1.152 +
1.153 +static int check_tablename(char *str)
1.154 +{
1.155 + int i;
1.156 +
1.157 + if (strmatch(str,NAME_TOKEN,NULL)) {
1.158 + str += strlen(NAME_TOKEN);
1.159 + while (*str==' ' || *str=='\t')
1.160 + str++;
1.161 + for (i=0; i<(sizeof tablename - 1) && *str!='\0' && strchr(" \t\n",*str)==NULL; i++, str++)
1.162 + tablename[i] = *str;
1.163 + tablename[i] = '\0';
1.164 + return 1;
1.165 + } /* if */
1.166 + return 0;
1.167 +}
1.168 +
1.169 +static int check_separator(char *str)
1.170 +{
1.171 + int i;
1.172 +
1.173 + if (strmatch(str,SEP_TOKEN,NULL)) {
1.174 + str += strlen(SEP_TOKEN);
1.175 + while (*str==' ' || *str=='\t')
1.176 + str++;
1.177 + for (i=0; i<(sizeof separator - 1) && *str!='\0' && strchr(" \t\n",*str)==NULL; i++, str++)
1.178 + separator[i] = *str;
1.179 + separator[i] = '\0';
1.180 + return 1;
1.181 + } /* if */
1.182 +
1.183 + if (strmatch(str,TERM_TOKEN,NULL)) {
1.184 + str += strlen(TERM_TOKEN);
1.185 + while (*str==' ' || *str=='\t')
1.186 + str++;
1.187 + for (i=0; i<(sizeof terminator - 1) && *str!='\0' && strchr(" \t\n",*str)==NULL; i++, str++)
1.188 + terminator[i] = *str;
1.189 + terminator[i] = '\0';
1.190 + return 1;
1.191 + } /* if */
1.192 +
1.193 + return 0;
1.194 +}
1.195 +
1.196 +/* readbuffer
1.197 + * Reads in the input file and stores all strings in the
1.198 + * section between "#ifdef SCPACK" and "#else" in a buffer.
1.199 + * Only text that is between double quotes is added to the
1.200 + * buffer; the \" escape code is handled. Multiple strings
1.201 + * on one line are handled.
1.202 + */
1.203 +unsigned readbuffer(FILE *input, unsigned char *buffer)
1.204 +{
1.205 + char str[256];
1.206 + unsigned buffersize;
1.207 + int i,linenr;
1.208 +
1.209 + linenr=0;
1.210 + buffersize=0;
1.211 +
1.212 + rewind(input);
1.213 + while (!feof(input)) {
1.214 + while (fgets(str,sizeof str,input)!=NULL) {
1.215 + linenr++;
1.216 + check_tablename(str);
1.217 + check_separator(str);
1.218 + if (strmatch(str,START_TOKEN,NULL))
1.219 + break;
1.220 + } /* while */
1.221 + if (!strmatch(str,START_TOKEN,NULL))
1.222 + return buffersize; /* no (more) section found, quit */
1.223 +
1.224 + while (fgets(str,sizeof str,input)!=NULL) {
1.225 + linenr++;
1.226 + check_if(str,linenr);
1.227 + if (check_tablename(str))
1.228 + printf("Error: table name definition should not be in SCPACK section (line %d)\n", linenr);
1.229 + check_separator(str);
1.230 + if (strmatch(str,"#else",NULL))
1.231 + break; /* done */
1.232 + /* add to the buffer only what is between double quotes */
1.233 + i=0;
1.234 + do {
1.235 + while (str[i]!='\0' && str[i]!='"')
1.236 + i++;
1.237 + if (str[i]=='"') {
1.238 + /* we are in a string */
1.239 + i++;
1.240 + while (str[i]!='\0' && str[i]!='"') {
1.241 + /* handle escape sequences */
1.242 + if (str[i]=='\\') {
1.243 + i++;
1.244 + switch (str[i]) {
1.245 + case 'a': /* alarm */
1.246 + buffer[buffersize++]='\a';
1.247 + i++;
1.248 + break;
1.249 + case 'b': /* backspace */
1.250 + buffer[buffersize++]='\b';
1.251 + i++;
1.252 + break;
1.253 + case 'f': /* form feed */
1.254 + buffer[buffersize++]='\f';
1.255 + i++;
1.256 + break;
1.257 + case 'n': /* newline */
1.258 + buffer[buffersize++]='\n';
1.259 + i++;
1.260 + break;
1.261 + case 'r': /* carriage return */
1.262 + buffer[buffersize++]='\n';
1.263 + i++;
1.264 + break;
1.265 + case 't': /* tab */
1.266 + buffer[buffersize++]='\t';
1.267 + i++;
1.268 + break;
1.269 + case '\'':
1.270 + buffer[buffersize++]='\'';
1.271 + i++;
1.272 + break;
1.273 + case '"':
1.274 + buffer[buffersize++]='"';
1.275 + i++;
1.276 + break;
1.277 + default:
1.278 + // ??? octal character code escapes and hexadecimal escapes
1.279 + // not supported
1.280 + printf("Unknown escape sequence '\\%c' on line %d\n",
1.281 + str[i], linenr);
1.282 + } /* switch */
1.283 + } else {
1.284 + buffer[buffersize++]=str[i++];
1.285 + } /* if */
1.286 + } /* while */
1.287 + if (str[i]=='"') {
1.288 + buffer[buffersize++]='\0'; /* terminate each string */
1.289 + i++;
1.290 + } else {
1.291 + printf("Error: unterminated string on line %d\n",linenr);
1.292 + } /* if */
1.293 + } /* if */
1.294 + } while (str[i]!='\0');
1.295 + } /* while - in SCPACK section */
1.296 + /* put in another '\0' to terminate the section */
1.297 + buffer[buffersize++]='\0';
1.298 + } /* while - !feof(input) */
1.299 + return buffersize;
1.300 +}
1.301 +
1.302 +static void write_pairtable(FILE *output, unsigned char pairtable[128][2], char *tablename)
1.303 +{
1.304 + int i;
1.305 +
1.306 + /* dump the pair table */
1.307 + fprintf(output, "/*-*SCPACK start of pair table, do not change or remove this line */\n");
1.308 + fprintf(output, "unsigned char %s[][2] = {", tablename);
1.309 + for (i=0; i<128 && pairtable[i][0]!=0 && pairtable[i][1]!=0; i++) {
1.310 + if ((i % 16)==0)
1.311 + fprintf(output, "\n ");
1.312 + else
1.313 + fprintf(output, " ");
1.314 + fprintf(output, "{%d,%d}", pairtable[i][0], pairtable[i][1]);
1.315 + /* check if something follows this pair */
1.316 + if (i+1<128 && pairtable[i+1][0]!=0 && pairtable[i+1][1]!=0)
1.317 + fprintf(output, ",");
1.318 + } /* for */
1.319 + fprintf(output, "\n};\n");
1.320 + fprintf(output, "/*-*SCPACK end of pair table, do not change or remove this line */\n");
1.321 +}
1.322 +
1.323 +void writefile(FILE *input, FILE *output, unsigned char *buffer, unsigned buffersize, unsigned char pairtable[128][2])
1.324 +{
1.325 + char str[256];
1.326 + int insection, indent, needseparator;
1.327 + unsigned char *bufptr;
1.328 +
1.329 + bufptr = buffer;
1.330 + insection = 0;
1.331 +
1.332 + rewind(input);
1.333 + while (!feof(input)) {
1.334 + while (fgets(str,sizeof str,input)!=NULL) {
1.335 + fprintf(output,"%s",str);
1.336 + if (check_tablename(str)) {
1.337 + write_pairtable(output, pairtable, tablename);
1.338 + /* strip an existing pair table from the file */
1.339 + if (fgets(str,sizeof str,input)!=NULL) {
1.340 + if (strmatch(str,"/*-*SCPACK",NULL)) {
1.341 + while (fgets(str,sizeof str,input)!=NULL)
1.342 + if (strmatch(str,"/*-*SCPACK",NULL))
1.343 + break;
1.344 + } else {
1.345 + fprintf(output,"%s",str);
1.346 + } /* if */
1.347 + } /* if */
1.348 + } /* if */
1.349 + if (strmatch(str,START_TOKEN,NULL))
1.350 + insection = 1;
1.351 + if (insection && strmatch(str,"#else",NULL))
1.352 + break;
1.353 + } /* while */
1.354 + if (!strmatch(str,"#else",&indent))
1.355 + return; /* no (more) section found, quit */
1.356 + insection=0;
1.357 +
1.358 + /* dump the buffer as strings, separated with commas */
1.359 + needseparator = 0;
1.360 + while (*bufptr != '\0') {
1.361 + assert((unsigned)(bufptr-buffer) < buffersize);
1.362 + if (needseparator)
1.363 + fprintf(output, "%s\n",separator);
1.364 + fprintf(output, "%*c\"",indent+2,' ');
1.365 + /* loop over string */
1.366 + while (*bufptr != '\0') {
1.367 + if (*bufptr<' ' || *bufptr >= 128 || *bufptr == '"' || *bufptr == '\\')
1.368 + fprintf(output, "\\%03o", *bufptr);
1.369 + else
1.370 + fprintf(output, "%c", *bufptr);
1.371 + bufptr++;
1.372 + } /* while */
1.373 + fprintf(output, "\"");
1.374 + needseparator = 1;
1.375 + bufptr++; /* skip '\0' */
1.376 + } /* while */
1.377 + fprintf(output, "%s\n",terminator);
1.378 + bufptr++;
1.379 +
1.380 + /* skip the input file until the #endif section */
1.381 + while (fgets(str,sizeof str,input)!=NULL) {
1.382 + if (strmatch(str,"#endif",NULL)) {
1.383 + fprintf(output,"%s",str);
1.384 + break; /* done */
1.385 + } /* if */
1.386 + } /* while */
1.387 + } /* while - !feof(input) */
1.388 +}
1.389 +
1.390 +static void usage(void)
1.391 +{
1.392 + printf("Usage: scpack <filename> [output file]\n");
1.393 + exit(1);
1.394 +}
1.395 +
1.396 +int main(int argc, char **argv)
1.397 +{
1.398 + FILE *in, *out;
1.399 + unsigned char *buffer;
1.400 + unsigned buffersize, orgbuffersize;
1.401 + unsigned char pairtable[128][2];
1.402 +
1.403 + if (argc < 2 || argc > 3)
1.404 + usage();
1.405 + if ((in=fopen(argv[1],"rt"))==NULL) {
1.406 + printf("SCPACK: error opening input %s\n",argv[1]);
1.407 + usage();
1.408 + } /* if */
1.409 + if (argc == 2) {
1.410 + if ((out=fopen(TEMPFILE,"wt"))==NULL) {
1.411 + printf("SCPACK: error opening temporary file %s\n",TEMPFILE);
1.412 + usage();
1.413 + } /* if */
1.414 + } else {
1.415 + if ((out=fopen(argv[2],"wt"))==NULL) {
1.416 + printf("SCPACK: error opening output file %s\n",argv[2]);
1.417 + usage();
1.418 + } /* if */
1.419 + } /* if */
1.420 +
1.421 + buffer = (unsigned char *)malloc(MAXSIZE);
1.422 + if (buffer == NULL) {
1.423 + printf("SCPACK: error allocating memory\n");
1.424 + return 1;
1.425 + } /* if */
1.426 + /* 1. read the buffer
1.427 + * 2. compress the buffer
1.428 + * 3. copy the file, insert the compressed buffer
1.429 + */
1.430 + buffersize = readbuffer(in, buffer);
1.431 + orgbuffersize = buffersize;
1.432 + if (buffersize > 0) {
1.433 + buffersize = compress(buffer, buffersize, pairtable);
1.434 + writefile(in, out, buffer, buffersize, pairtable);
1.435 + printf("SCPACK: compression ratio: %ld%% (%d -> %d)\n",
1.436 + 100L-(100L*buffersize)/orgbuffersize, orgbuffersize, buffersize);
1.437 + } else {
1.438 + printf("SCPACK: no SCPACK section found, nothing to do\n");
1.439 + } /* if */
1.440 + fclose(out);
1.441 + fclose(in);
1.442 + /* let the new file replace the old file */
1.443 + if (buffersize == 0) {
1.444 + if (argc == 2)
1.445 + remove(TEMPFILE);
1.446 + else
1.447 + remove(argv[2]);
1.448 + } else if (argc == 2) {
1.449 + remove(argv[1]);
1.450 + rename(TEMPFILE,argv[1]);
1.451 + } /* if */
1.452 + return 0;
1.453 +}
