//  COMPR.C

//  The author and the source of this code is not known.

#include <string.h>
#include <stdlib.h>

#include "me5.h"

//  #define BITS 12
//  BITS now passed as variable bits, in range 10 through 12.
#define MIN_BITS 10     // formerly 9
#define MAX_BITS 12

//  #define HASHING_SHIFT BITS-8
//  #define MAX_VALUE (1 << BITS) - 1
//  #define MAX_CODE MAX_VALUE - 1
//  these now variables also

#define TABLE_SIZE 5003    /*  The string table size needs to be a   */
                           /*  prime number that is somewhat larger  */
                           /*  than 2^BITS (2^12 = 4096).            */

/*  variables referenced only in this module  */

unsigned int bits, hashing_shift, max_value, max_code;

int *code_value;                    /* This is the code value array          */
unsigned int *prefix_code;          /* This array holds the prefix codes     */
unsigned char *append_character;    /* This array holds the appended chars   */
int inbufidx, outbufidx;            /* indices into input and output buffers */
int bit_count;                      /*  bit_count and bit_buffer must be  */
unsigned long bit_buffer;           /*  zeroed before compression or expansion  */
unsigned char decode_stack[4096];   /* This array holds the decoded string   */

unsigned int me5_compress_block(unsigned int n, unsigned int bits_value);
unsigned int me5_decompress_block(unsigned int n, unsigned int bits_value, int *err_flag);

int compress(unsigned char *inbuf, unsigned char *outbuf, int n, int max_out);
int expand(unsigned char *inbuf, unsigned char *outbuf, int n, int max_out, int *err_flag);
int find_match(unsigned int hash_prefix, unsigned int hash_character);
char *decode_string(unsigned char *buffer, unsigned int code);
unsigned int input_code(unsigned char *inbuf);
void output_code(unsigned int code, unsigned char *outbuf);

//  This is called by allocate_buffers() in ME5.C.
//  Returns true if compression space allocated, false otherwise.
/*--------------------------------*/
int allocate_compression_space(void)
{
code_value = (int *)calloc(TABLE_SIZE, sizeof(int));
if ( code_value == NULL )
    return ( false );

prefix_code = (unsigned int *)calloc(TABLE_SIZE, sizeof(unsigned int));
if ( prefix_code == NULL )
    {
    free(code_value);
    return ( false );
    }

append_character = calloc(TABLE_SIZE,sizeof(unsigned char));
if ( append_character == NULL )
    {
    free(code_value);
    free(prefix_code);
    return ( false );
    }

return ( true );
}

//  This is called by deallocate_buffers() in ME5.C.
/*-----------------------------*/
void free_compression_space(void)
{
memset(code_value,0,TABLE_SIZE*sizeof(int));
memset(prefix_code,0,TABLE_SIZE*sizeof(unsigned int));
memset(append_character,0,TABLE_SIZE*sizeof(unsigned char));
free(code_value);
free(prefix_code);
free(append_character);
}

//  Returns size of block.
/*-------------------------------------------*/
unsigned int me5_compress_block(unsigned int n,
                                unsigned int bits_value)
{
unsigned int new_n;
unsigned int m;

bits = bits_value;

if ( bits < MIN_BITS || bits > MAX_BITS )
    return ( 0 );

hashing_shift = bits - 8;
max_value = (1 << bits) - 1;
max_code = max_value - 1;

me5_expand_block = false;
new_n = compress(buffer,buffer1,n,n);   //  compress block

if ( (int)new_n != -1 )                 //  output does not exceed n bytes
    {                                   //  i.e. compression possible
    me5_expand_block = true;
    n = new_n;

    //  Move first third to end.
    m = n/3;
    memcpy(buffer,buffer1+m,n-m);
    if ( m )
        memcpy(buffer+n-m,buffer1,m);
    }
    //  Expand block during decryption only if it has been compressed.

return ( n );
}

//  This function is called only when me5_expand_block is true.
//  Returns size of decompressed block and
//  returns *err_flag = 0 if no error
//                     -1 if output buffer overflow
//                     -2 if code expansion error
//                     -3 if size of decompressed block is zero
/*---------------------------------------------*/
unsigned int me5_decompress_block(unsigned int n,
                                  unsigned int bits_value,
                                  int *err_flag)
{
unsigned int m;

bits = bits_value;

if ( bits < MIN_BITS || bits > MAX_BITS )
    return ( 0 );

hashing_shift = bits - 8;
max_value = (1 << bits) - 1;
max_code = max_value - 1;

//  Move first third of buffer back to beginning.
m = n/3;
memcpy(buffer1,buffer,n-m);
if ( m )
    memmove(buffer,buffer+n-m,m);
memcpy(buffer+m,buffer1,n-m);

n = expand(buffer,buffer1,n,BUFFSIZE,err_flag);

if ( n == 0 )
    *err_flag = -3;

//  if ( !*err_flag )
    memcpy(buffer,buffer1,n);

return ( n );
}

/*  Compress the n bytes at inbuf.
 *  n and max_out should be < 32768.
 *  Returns size of compressed block
 *  or -1 if output would overflow output buffer.
 */
/*----------------------------------*/
int compress(unsigned char *inbuf,  /*  pointer to input buffer  */
             unsigned char *outbuf, /*  pointer to output buffer  */
             int n,                 /*  number of bytes in input buffer  */
             int max_out)           /*  maximum number of bytes  */
                                    /*  permitted in output buffer  */
{
unsigned int next_code, character, string_code, index, i;

inbufidx = outbufidx = bit_count = 0;
bit_buffer = 0L;
next_code = 256;         /*  next code is the next available string code  */
for ( i=0; i<TABLE_SIZE; i++)       /*  clear out the string table  */
    code_value[i] = -1;             /*  before starting  */

string_code = (unsigned int)inbuf[inbufidx++];   /*  get the first code  */

/*  This is the main loop where it all happens.  This loop runs until all
 *  the input has been exhausted.  Note that it stops adding codes to the
 *  table after all of the possible codes have been defined.
 */
while ( inbufidx != n )
    {
    //  See if the string is in the table.  If it is, get the code value.
    //  If the string is not in the table, try to add it.
    character = (unsigned int)inbuf[inbufidx++];
    index = find_match(string_code,character);
    if ( code_value[index] != -1 )
        string_code = code_value[index];
    else
        {
        if ( next_code <= max_code )
            {
            code_value[index] = next_code++;
            prefix_code[index] = string_code;
            append_character[index] = (unsigned char)character;
            }
        if ( outbufidx == max_out )
            return ( -1 );      /*  output buffer too small  */
        else
            output_code(string_code,outbuf);
        string_code = character;
        //  When a string is found that is not in the table,
        //  output the last string after adding the new one.
        }
    }

if ( outbufidx + 3 > max_out )
    return ( -1 );
else
    {
    output_code(string_code,outbuf);      /*  Output the last code */
    output_code(max_value,outbuf);        /*  Output the end of buffer code */
    output_code(0,outbuf);
    }

return ( outbufidx );
}

/*  Expand the bytes at inbuf (should be < 32768 of them).
 *  Returns the size of the expanded block
 *  and sets *err_flag = 0 if no error
 *                      -1 if output buffer overflow
 *                      -2 if code expansion error
 *
 *  Output buffer overflow should never occur
 *  since block was compressed from block
 *  whose size is <= output buffer size
 */
/*----------------------------*/
int expand(unsigned char *inbuf,
           unsigned char *outbuf,
           int n,   /*  number of bytes in input buffer  */
           int max_out,
           int *err_flag)
{
unsigned int next_code, new_code, old_code;
int character;
unsigned char *string;

*err_flag = 0;
inbufidx = outbufidx = bit_count = 0;
bit_buffer = 0L;
next_code = 256;              /*  this is the next available code to define  */
old_code = input_code(inbuf); /*  read in the first code, initialize the     */
character = old_code;         /*  character variable, and send the first     */
outbuf[outbufidx++] = (unsigned char)old_code;  /*  code to the output file  */

/*  This is the main expansion loop.  It reads in characters from the file
 *  until it sees the special code used to indicate the end of the data.
 */
while ( ( new_code = input_code(inbuf) ) != ( max_value ) )
    {
    /*
     *  this code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
     *  case which generates an undefined code; it handles it by decoding
     *  the last code, adding a single character to the end of the decode string
     */
    if ( new_code >= next_code )
        {
        *decode_stack = (unsigned char)character;
        string = decode_string(decode_stack+1,old_code);
        }
    else    /*  we do a straight decode of the new code  */
        string = decode_string(decode_stack,new_code);

    if ( string == NULL )
        {
        *err_flag = -2;         /*  code expansion error  */
        break;
        }

    /*  now we output the decoded string in reverse order  */
    character = *string;
    while ( string >= decode_stack )
        {
        if ( outbufidx == max_out )
            {
            *err_flag = -1;
            break;
            }
        else
            outbuf[outbufidx++] = *string--;
        }

    if ( *err_flag == -1 )
        break;

    /*  Finally, if possible, add a new code to the string table.  */
    if ( next_code <= max_code )
        {
        prefix_code[next_code] = old_code;
        append_character[next_code] = (unsigned char)character;
        next_code++;
        }
    old_code = new_code;
    }

return ( outbufidx );
}

//  This is the hashing routine.  It tries to find a match for the
//  prefix+char string in the string table.  If it finds it, the index is
//  returned.  If the string is not found, the first available index in
//  the string table is returned instead.
/*-----------------------------------*/
int find_match(unsigned int hash_prefix,
               unsigned int hash_character)
{
int index, offset;

index = ( hash_character << hashing_shift ) ^ hash_prefix;
offset = ( index == 0 ? 1 : TABLE_SIZE - index );

while ( true )
    {
    if ( code_value[index] == -1 )
          return(index);
    if ( prefix_code[index] == hash_prefix )
        {
        if ( append_character[index] == (unsigned char)hash_character )
            return(index);
        }
    index -= offset;
    if (index < 0)
        index += TABLE_SIZE;
    }
}

/*  This routine simply decodes a string from the string table, storing
 *  it in a buffer.  The buffer can then be output in reverse order by
 *  the expansion program.
 */
/*--------------------------------------*/
char *decode_string(unsigned char *buffer,
                    unsigned int code)
{
int i=0;

while ( code > 255 )
    {
    *buffer++ = append_character[code];
    code = prefix_code[code];
    if ( i++ >= 4094 )
        return ( NULL );
    }

*buffer = (unsigned char)code;
return ( buffer );
}

/*-----------------------------------------*/
unsigned int input_code(unsigned char *inbuf)
{
unsigned int code;

while ( bit_count <= 24 )
    {
    bit_buffer |= (unsigned long)inbuf[inbufidx++] << ( 24 - bit_count );
    bit_count += 8;
    }

code = (unsigned int)( bit_buffer >> (32-bits) );
bit_buffer <<= bits;
bit_count -= bits;
return ( code );
}

/*------------------------------*/
void output_code(unsigned int code,
                 unsigned char *outbuf)
{
bit_buffer |= ( ((unsigned long)code) << ( 32 - bits - bit_count ) );
bit_count += bits;
while ( bit_count >= 8 )
    {
    outbuf[outbufidx++] = (unsigned char)( bit_buffer >> 24 );
    bit_buffer <<= 8;
    bit_count -= 8;
    }
}