Listing 1 COMPRS.C
/* * 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 & 00F); *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; } /* End of File */