Category : Printer + Display Graphics
Archive   : TIFGIF.ZIP
Filename : COMPRESS.C

/*----------------------------------------------------------------------*/
/* Copyright (c) 1987 */
/* by CompuServe Inc., Columbus, Ohio. All Rights Reserved */
/* COMPRESS.C can be copied and distributed freely for any */
/* non-commercial purposes. COMPRESS.C can only be incorporated */
/* into commercial software with the permission of CompuServe Inc. */
/*----------------------------------------------------------------------*/

/*
* ABSTRACT:
* The compression algorithm builds a string translation table that maps
* substrings from the input string into fixed-length codes. These codes
* are used by the expansion algorithm to rebuild the compressor's table
* and reconstruct the original data stream. In it's simplest form, the
* algorithm can be stated as:
*
* "if k is in the table, then is in the table"
*
* is a code which represents a string in the table. When a new
* character k is read in, the table is searched for k. If this
* combination is found, is set to the code for that combination
* and the next character is read in. Otherwise, this combination is
* added to the table, the code is written to the output stream and
* is set to k.
*
* The expansion algorithm builds an identical table by parsing each
* received code into a prefix string and suffix character. The suffix
* character is pushed onto the stack and the prefix string translated
* again until it is a single character. This completes the expansion.
* The expanded code is then output by popping the stack and a new entry
* is made in the table.
*
* The algorithm used here has one additional feature. The output codes
* are variable length. They start at a specified number of bits. Once
* the number of codes exceeds the current code size, the number of bits
* in the code is incremented. When the table is completely full, a
* clear code is transmitted for the expander and the table is reset.
* This program uses a maximum code size of 12 bits for a total of 4096
* codes.
*
* The expander realizes that the code size is changing when it's table
* size reaches the maximum for the current code size. At this point,
* the code size in increased. Remember that the expander's table is
* identical to the compressor's table at any point in the original data
* stream.
*
* The compressed data stream is structured as follows:
* first byte denoting the minimum code size
* one or more counted byte strings. The first byte contains the
* length of the string. A null string denotes "end of data"
*
* This format permits a compressed data stream to be embedded within a
* non-compressed context.
*
* AUTHOR: Steve Wilhite
*
* REVISION HISTORY:
*
*/

#include
#include /* MSC 4.0 */

#include "compress.h"

#define GetMem _fmalloc
#define FreeMem _ffree

#define far_null_ptr 0L
#define null_ptr 0
#define largest_code 4095
#define table_size 5003

/* Declare prototypes */

static void init_table( short min_code_size );

static void flush( short n );

static void write_code( short code );

jmp_buf recover;

struct code_entry
{
short prior_code;
short code_id;
unsigned char added_char;
};

static short code_size;
static short clear_code;
static short eof_code;
static short min_code;
static short bit_offset;
static short byte_offset, bits_left;
static short max_code;
static short free_code;
static short prefix_code;
static short suffix_char;
static short hx, d;

static unsigned char code_buffer[256+3];
static struct code_entry far *code_table;
static short (*get_byte)(void);
static short (*put_byte)(unsigned char);

static void init_table( short min_code_size )
{
short i;

code_size = min_code_size + 1;
clear_code = 1 << min_code_size;
eof_code = clear_code + 1;
free_code = clear_code + 2;
max_code = 1 << code_size;

for (i = 0; i < table_size; i++)
code_table[i].code_id = 0;
}

/*$page*/

static void flush( short n )
{
short i, status;

status = (*put_byte)((unsigned char)(n));

if (status != 0)
longjmp(recover, status);

for (i = 0; i < n; i++)
{
status = (*put_byte)(code_buffer[i]);

if (status != 0)
longjmp(recover, status);
}
}


static void write_code( short code )
{
long temp;

byte_offset = bit_offset >> 3;
bits_left = bit_offset & 7;

if (byte_offset >= 254)
{
flush(byte_offset);
code_buffer[0] = code_buffer[byte_offset];
bit_offset = bits_left;
byte_offset = 0;
}

if (bits_left > 0)
{
temp = ((long) code << bits_left) | code_buffer[byte_offset];
code_buffer[byte_offset] = (unsigned char)(temp);
code_buffer[byte_offset + 1] = (unsigned char)(temp >> 8);
code_buffer[byte_offset + 2] = (unsigned char)(temp >> 16);
}
else
{
code_buffer[byte_offset] = (unsigned char)(code);
code_buffer[byte_offset + 1] = (unsigned char)(code >> 8);
}

bit_offset += code_size;
}

/*$page*/

short Compress_Data( short min_code_size,
short (*get_byte_routine)(void),
short (*put_byte_routine)(unsigned char) )
/*
* Function:
* Compress a stream of data bytes using the LZW algorithm.
*
* Inputs:
* min_code_size
* the field size of an input value. Should be in the range from
* 1 to 9.
*
* get_byte_routine
* address of the caller's "get_byte" routine:
*
* status = get_byte();
*
* where "status" is
* 0 .. 255 the byte just read
* -1 logical end-of-file
* < -3 error codes
*
* put_byte_routine
* address the the caller's "put_byte" routine:
*
* status = put_byte(value)
*
* where
* value the byte to write
* status 0 = OK, else < -3 means some error code
*
* Returns:
* 0 normal completion
* -1 (not used)
* -2 insufficient dynamic memory
* -3 bad "min_code_size"
* < -3 error status from either the get_byte or put_byte routine
*/
{
short status;

get_byte = get_byte_routine;
put_byte = put_byte_routine;

if (min_code_size < 2 || min_code_size > 9)
if (min_code_size == 1)
min_code_size = 2;
else
return -3;

code_table = (struct code_entry far *)
GetMem(sizeof(struct code_entry)*table_size);

if (code_table == null_ptr)
return -2;

status = setjmp(recover);

if (status != 0)
{
FreeMem((char *) code_table);
return status;
}

(*put_byte)((unsigned char)(min_code_size)); /* record minimum code size */
bit_offset = 0;
init_table(min_code_size);
write_code(clear_code);
suffix_char = (*get_byte)();

if (suffix_char >= 0)
{
prefix_code = suffix_char;

while ((suffix_char = (*get_byte)()) >= 0)
{
hx = (prefix_code ^ suffix_char << 5) % table_size;
d = 1;

for (;;)
{
if (code_table[hx].code_id == 0)
{
write_code(prefix_code);

d = free_code;

if (free_code <= largest_code)
{
code_table[hx].prior_code = prefix_code;
code_table[hx].added_char = (unsigned char)(suffix_char);
code_table[hx].code_id = free_code;
free_code++;
}

if (d == max_code)
if (code_size < 12)
{
code_size++;
max_code <<= 1;
}
else
{
write_code(clear_code);
init_table(min_code_size);
}

prefix_code = suffix_char;
break;
}

if (code_table[hx].prior_code == prefix_code &&
code_table[hx].added_char == (unsigned char)(suffix_char))
{
prefix_code = code_table[hx].code_id;
break;
}

hx += d;
d += 2;
if (hx >= table_size)
hx -= table_size;
}
}

if (suffix_char != -1)
longjmp(recover, suffix_char);

write_code(prefix_code);
}
else if (suffix_char != -1)
longjmp(recover, suffix_char);

write_code(eof_code);

/* Make sure the code buffer is flushed */

if (bit_offset > 0)
flush((bit_offset + 7)/8);

flush(0); /* end-of-data */

FreeMem((char *) code_table);
return 0;
}