home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_10_10
/
1010114a
< prev
next >
Wrap
Text File
|
1992-08-13
|
4KB
|
180 lines
/*
* Listing 1
*
* COMPRS.C - Ross Data Compression (RDC)
* compress function
*
* Written by Ed Ross, 1/92
*
* compress inbuff_len bytes of inbuff into outbuff
* using hash_len entries in hash_tbl.
*
* return length of outbuff, or "0 - inbuff_len"
* if inbuff could not be compressed.
*
*/
#include <string.h>
typedef unsigned char uchar; /* 8 bits, unsigned */
typedef unsigned int uint; /* 16 bits, unsigned */
int rdc_compress(uchar *inbuff, uint inbuff_len,
uchar *outbuff,
uchar *hash_tbl[], uint hash_len)
{
uchar *in_idx = inbuff;
uchar *inbuff_end = inbuff + inbuff_len;
uchar *anchor;
uchar *pat_idx;
uint cnt;
uint gap;
uint c;
uint hash;
uint *ctrl_idx = (uint *) outbuff;
uint ctrl_bits;
uint ctrl_cnt = 0;
uchar *out_idx = outbuff + sizeof(uint);
uchar *outbuff_end = outbuff + (inbuff_len - 48);
/* skip the compression for a small buffer */
if (inbuff_len <= 18)
{
memcpy(outbuff, inbuff, inbuff_len);
return 0 - inbuff_len;
}
/* adjust # hash entries so hash algorithm can
use 'and' instead of 'mod' */
hash_len--;
/* scan thru inbuff */
while (in_idx < inbuff_end)
{
/* make room for the control bits
and check for outbuff overflow */
if (ctrl_cnt++ == 16)
{
*ctrl_idx = ctrl_bits;
ctrl_cnt = 1;
ctrl_idx = (uint *) out_idx;
out_idx += 2;
if (out_idx > outbuff_end)
{
memcpy(outbuff, inbuff, inbuff_len);
return 0 - inbuff_len;
}
}
/* look for rle */
anchor = in_idx;
c = *in_idx++;
while (in_idx < inbuff_end
&& *in_idx == c
&& (in_idx - anchor) < 4114)
in_idx++;
/* store compression code if character is
repeated more than 2 times */
if ((cnt = in_idx - anchor) > 2)
{
if (cnt <= 18) /* short rle */
{
*out_idx++ = cnt - 3;
*out_idx++ = c;
}
else /* long rle */
{
cnt -= 19;
*out_idx++ = 16 + (cnt & 0x0F);
*out_idx++ = cnt >> 4;
*out_idx++ = c;
}
ctrl_bits = (ctrl_bits << 1) | 1;
continue;
}
/* look for pattern if 2 or more characters
remain in the input buffer */
in_idx = anchor;
if ((inbuff_end - in_idx) > 2)
{
/* locate offset of possible pattern
in sliding dictionary */
hash = ((((in_idx[0] & 15) << 8) | in_idx[1]) ^
((in_idx[0] >> 4) | (in_idx[2] << 4)))
& hash_len;
pat_idx = hash_tbl[hash];
hash_tbl[hash] = in_idx;
/* compare characters if we're within 4098 bytes */
if ((gap = in_idx - pat_idx) <= 4098)
{
while (in_idx < inbuff_end
&& pat_idx < anchor && *pat_idx == *in_idx
&& (in_idx - anchor) < 271)
{
in_idx++;
pat_idx++;
}
/* store pattern if it is more than 2 characters */
if ((cnt = in_idx - anchor) > 2)
{
gap -= 3;
if (cnt <= 15) /* short pattern */
{
*out_idx++ = (cnt << 4) + (gap & 0x0F);
*out_idx++ = gap >> 4;
}
else /* long pattern */
{
*out_idx++ = 32 + (gap & 0x0F);
*out_idx++ = gap >> 4;
*out_idx++ = cnt - 16;
}
ctrl_bits = (ctrl_bits << 1) | 1;
continue;
}
}
}
/* can't compress this character
so copy it to outbuff */
*out_idx++ = c;
in_idx = ++anchor;
ctrl_bits <<= 1;
}
/* save last load of control bits */
ctrl_bits <<= (16 - ctrl_cnt);
*ctrl_idx = ctrl_bits;
/* and return size of compressed buffer */
return out_idx - outbuff;
}