|
October 01, 1992
URL:http://www.drdobbs.com/a-simple-data-compression-technique/184402606
/*
* 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 */
/* DECOMPRS.C - Ross Data Compression (RDC)
* decompress function
*
* Written by Ed Ross, 1/92
*
* decompress inbuff_len bytes of inbuff into outbuff.
return length of outbuff. */
#include <string.h>
typedef unsigned char uchar; /* 8 bits, unsigned */
typedef unsigned int uint; /* 16 bits, unsigned */
int rdc_decompress(uchar *inbuff, uint inbuff_len,
uchar *outbuff)
{
uint ctrl_bits;
uint ctrl_mask = 0;
uchar *inbuff_idx = inbuff;
uchar *outbuff_idx = outbuff;
uchar *inbuff_end = inbuff + inbuff_len;
uint cmd;
uint cnt;
uint ofs;
uint len;
/* process each item in inbuff */
while (inbuff_idx < inbuff_end)
{
/* get new load of control bits if needed */
if ((ctrl_mask >>= 1) == 0)
{
ctrl_bits = * (uint *) inbuff_idx;
inbuff_idx += 2;
ctrl_mask = 0x8000;
}
/* just copy this char if control bit is zero */
if ((ctrl_bits & ctrl_mask) == 0)
{
*outbuff_idx++ == *inbuff_idx++;
continue;
}
/* undo the compression code */
cmd = (*inbuff_idx >> 4) & 00F;
cnt = *inbuff_idx++ & 00F;
switch (cmd)
{
case 0: /* short rle */
cnt += 3;
memset(outbuff_idx, *inbuff_idx++, cnt);
outbuff_idx += cnt;
break;
case 1: /* long /rle */
cnt += (*inbuff_idx++ << 4);
cnt += 19;
memset(outbuff_idx, *inbuff_idx++, cnt);
outbuff_idx += cnt;
break;
case 2: /* long pattern */
ofs = cnt + 3;
ofs += (*inbuff_idx++ << 4);
cnt = *inbuff_idx++;
cnt += 16;
memcpy(outbuff_idx, outbuff_idx - ofs, cnt);
outbuff_idx += cnt;
break;
default: /* short pattern */
ofs = cnt + 3;
ofs += (*inbuff_idx++ << 4);
memcpy(outbuff_idx, outbuff_idx - ofs, cmd);
outbuff_idx += cmd;
break;
}
}
/* return length of decompressed buffer */
return outbuff_idx - outbuff;
}
/* End of File */
/* TESTRDC.C - Ross Data Compression (RDC)
* test driver program
*
* Written by Ed Ross, 1/92
*
* This program will compress or decompress a file
* using RDC data compression. */
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#define HASH_LEN 4096 /* # hash table entries */
#define BUFF_LEN 16384 /* size of disk io buffer */
typedef unsigned char uchar; /* 8 bits, unsigned */
typedef unsigned int uint; /* 16 bits, unsigned */
uchar *hash_tbl[HASH_LEN]; /* hash table */
uchar inbuff[BUFF_LEN]; /* io buffers */
uchar outbuff[BUFF_LEN];
FILE *infile, *outfile; /* FILE access */
char usage[] =
"\nUsage: TESTRDC <c | d> <infile> <outfile>\n"
" c = compress infile to outfile\n"
" d = decompress infile to outfile\n";
/* compression function prototypes */
int rdc_compress(uchar *inbuff, uint inbuff_len,
uchar *outbuff,
uchar *hash_tbl[], uint hash_len);
int rdc_decompress(uchar *inbuff, uint inbuff_len,
uchar *outbuff);
/*--- post error message and exit ---*/
void err_exit(char *fmt, ...)
{
va_list v;
va_start(v, fmt);
vfprintf(stderr, fmt, v);
va_end(v);
exit(1);
}
/*--- compress infile to outfile ---*/
void do_compress(void)
{
int bytes_read;
int compress_len;
/* read infile BUFF_LEN bytes at a time */
while ((bytes_read =
fread(inbuff, 1, BUFF_LEN, infile)) > 0)
{
/* compress this load of bytes */
compress_len = rdc_compress(inbuff, bytes_read,
outbuff, hash_tbl, HASH_LEN);
/* write length of compressed buffer */
if (fwrite(&compress_len, sizeof(int),
1, outfile) != 1)
err_exit("Error writing block length.\n");
/*check for negative length indicating the
buffer could not be compressed */
if (compress_len < 0)
compress_len = 0 - compress_len;
/* write the buffer */
if (fwrite(outbuff, compress_len, 1, outfile) != 1)
err_exit("Error writing compressed data.\n");
/* we're done if less than full buffer was read */
if (bytes_read != BUFF_LEN)
break;
}
/* add trailer to indicate end of file */
compress_len = 0;
if (fwrite(&compress_len, sizeof(int),
1, outfile) != 1)
err_exit("Error writing trailer.\n");
}
/*--- decompress infile to outfile ---*/
void do_decompress(void)
{
int block_len;
int decomp_len;
/* read infile BUFF_LEN bytes at a time */
for (;;)
{
if (fread(&block_len, sizeof(int), 1, infile) != 1)
err_exit("Can't read block length.\n");
/* check for end-of-file flag */
if (block_len == 0)
return;
if (block_len < 0) /* copy uncompressed chars */
{
decomp_len = 0 - block_len;
if (fread(outbuff, decomp_len, 1, infile) != 1)
err_exit("Can't read uncompressed block.\n");
}
else /* decompress this buffer */
{
if (fread(inbuff, block_len, 1, infile) != 1)
err_exit("Can't read compressed block.\n");
decomp_len = rdc_decompress(inbuff, block_len,
outbuff);
}
/* and write this buffer outfile */
if (fwrite(outbuff, decomp_len, 1, outfile) != 1)
err_exit("Error writing uncompressed data.\n");
}
}
/*--- main ---*/
void main(int argc, char *argv[])
{
/* check command line */
if (argc != 4)
err_exit(usage);
/* open the files */
if ((infile = fopen(argv[2], "rb")) == NULL)
err_exit("Can't open %s for input.\n", argv[2]);
if ((outfile : fopen(argv[3], "wb")) == NULL)
err_exit("Can't open %s for output.\n", argv[3]);
/* dispatch to requested function */
switch (argv[1] [0])
{
case 'c':
case 'C':
do_compress();
break;
case 'd':
case 'D':
do_decompress();
break;
default:
err_exit(usage);
}
/* and close the files */
if (fclose(infile))
err_exit("Error closing input file.\n");
if (fclose(outfile))
err_exit("Error closing output file.\n");
}
/* End of File */
Ed Ross is a consultant with 15 years programming experience. He has implemented a wide range of applications on mainframes, minis, and IBM PC's. Ed is the principle owner of Application Software which specializes in custom software solutions for the needs of medium and small businesses. He can be contacted at 51-01 39th Ave., Apt. M-12; Sunnyside, NY 11104; (718) 639-9727.
This article presents a data compression technique that I call RDC (for Ross Data Compression). The C implementation of RDC is faster than an assembler implementation of 13-bit LZW and provides a comparable compression ratio. RDC requires only one variable-size hash table of memory overhead and is implemented in just two C functions. RDC is ideal for situations where data compression would enhance your application and you don't want to spend the time or space for elaborate compression methods.
RDC performs all operations on two memory buffers. The compressor scans an input buffer for patterns, replaces the patterns with a two- or three-byte compression code and writes the code to an output buffer. The decompressor reads compressed data from an input buffer, expands the codes to the original pattern, and writes the expanded data to the output buffer.
RDC compresses patterns of consecutive occurrences of a single character using run-length encoding (RLE). These patterns are represented by a code that says "repeat this character this many times". A two-byte code, called a short RLE code, can represent from three to 18 occurrences of a character. A three-byte code, called a long RLE code, can represent from 19 to 4114 occurrences of a character. RLE is a simple and efficient method of compressing repeated byte sequences.
RDC uses a sliding dictionary to compress patterns of characters that occur earlier in the input buffer. The sliding dictionary is a window into the previous 4098 bytes of the input buffer. A character pattern which occurs in the dictionary is represented by a code that says "copy this many characters starting at this offset in the dictionary". A short (two-byte) pattern code can represent a pattern of three to 15 characters. A long (three-byte) pattern code can represent a pattern of 16 to 271 characters.
Characters which are not part of any pattern are simply copied to the output buffer. A one-bit control code tags each item in the output buffer and allows the decompressor to take appropriate action.
Listing 1 shows the compression function. Each pass through the main loop adds one item to the output buffer, either a compression code or a character copied from the input buffer. To do this, the program first reserves a spot for the control bit for this item. A control bit of 1 indicates a compression code and a 0 indicates a copied character. The value is not yet known but a spot must be reserved so the bit can be set when the item type is determined. The control bits are added to a control word until the word is filled.
When the control word is full, the compressor writes it to a previously reserved location and reserves a new location for the next time the control word is filled. RDC insures that the compressed data will not require more space than the original data. Since it is possible, but not likely, to encounter a sequence of characters that RDC can not compress, the program checks to see if the end of the output buffer is near. If it is near, the program copies the input buffer to the output buffer and returns a negative size to the caller indicating that RDC was unable to compress the data.
Next RDC looks for patterns. Repeated characters are the easiest to find and most efficient to compress, so it looks for these first. It simply counts the number of subsequent characters that match the character being scanned without moving past the end of the input buffer or counting more characters than RDC can handle. If three or more matches are found, RDC writes an RLE code to the output buffer and the scanning process starts again.
If it finds no repeating characters, the program looks to see if this sequence of characters appears in the sliding dictionary. RDC uses a hash table to access a list of pointers into the dictionary. The hash key is constructed from the first three characters of the search pattern. The hash table entry points to the location in the dictionary where the pattern was last seen. If the pointer points to a location within 4098 characters of the current position, the program looks to see how many characters in the dictionary match the characters being scanned. If it finds three or more characters, RDC writes a pattern code to the output buffer and the scanning process resumes.
Note that the hash table is updated with the location of each three-character sequence as it is scanned. The hash table always contains the most recent occurrence of each pattern. I've chosen a simple hashing algorithm which uses no multiplies or divides and is optimized for a 4096 entry hash table. If you like to tinker with algorithms this is the place! Be aware that the hash key will be computed for each character that is not part of an RLE sequence. A fancy approach using slower machine instructions can dramatically slow the compression rate.
To prevent wild pointers the hash table should contain null pointers at the start of the program. An unusual characteristic of the hashing algorithm shown here is that the number of entries in the hash table should be a power of two! This allows the final hash key to be obtained with an and instruction instead of the usual mod operation. The maximum number of hash table entries this algorithm will use is 4096.
If the program does not find an RLE sequence or a dictionary pattern, then it copies the input character to the output buffer and the search continues with the next input character.
Listing 2 contains the decompressor. The decompressor has an easy job because the compressor does most of the work. The decompressor uses the control bits to identify each item as a compression code or an uncompressed character. It expands compression codes and writes them to the output buffer. The decompressor copies uncompressed characters to the output buffer. The process continues until all items in the input buffer have been processed.
The first byte of each compression code contains two four-bit fields. The high-order field identifies the type of code. The remaining parts of the code vary depending on the code type. Table 1 gives the format of each compression code.
The RLE codes contain the character to be repeated and the number of times to repeat it. The repeat count field is four bits in the short code and 12 bits in the long code. The count fields are adjusted to achieve the maximum range for each code. The shortest sequence we can compress is three characters so the decompressor adds three to the short repeat count to achieve a range from three to 18 characters. Likewise, a long RLE code will have no less that 18 characters so the decompressor adds 19 to the long count to achieve a range of 19 to 4114 characters.
The pattern codes contain the number of characters in the pattern and the offset of the pattern from the current location in the buffer. The offset for short and long codes is a 12-bit value and is adjusted to yield an offset of three to 4098 characters.
The character count field of the short pattern code also serves to identify the compression code type. The values 0, 1, and 2 are used to identify the short RLE, long RLE and long pattern code respectively. Values 3 to 15 are the pattern length for the short pattern code.
The character count field of the long pattern code is eight bits and is adjusted to give a range of 16 to 271 characters in a long pattern.
I have included a simple driver program, Listing 3, that you can use to test the RDC routines. The command TESTRDC C <FILE 1> <FILE 2> will compress FILE 1 and produce FILE 2. The command TESTRDC D <FILE 1> <FILE 2> will decompress FILE 1 and produce FILE 2. The driver will write any existing output files so be careful of the file names you choose.
Table 2 lists the performance of RDC compared to the well-known PKARC program used on MS-DOS machines. PKARC is written in assembler language and is one of the fastest LZW implementations available. The table shows the results of compressing and decompressing two files. The binary file is a large .exe file and the text file is a software reference manual. The file size is shown in bytes. Compression and decompression times are in seconds. These tests were performed in a RAM disk to remove disk I/O time from the comparisons.
RDC seems to compress binary files better than PKARC, while PKARC does better with text files. When compressing a variety of files of different types and sizes the total compression rates are about even.
I have used RDC to add data compression to a custom backup program I wrote for one of my clients. The time spent compressing the data is minimal and the client saves several floppy disks each time they do backup.
With RDC in your toolbox you can add data compression to your applications with a minimum of code and data overhead.
Code Type Byte 1 Byte 2 Byte 3 --------------------------------------------------------- Short RLE 0 | Count Character (not used) Long RLE 1 | Low Count High Count Character Long Pattern 2 | Low Offset High Offset Count Short Pattern 3-15 | Low Offset High Offset (not used)
File Type File Size RDC RDC RDC PKARC PKARC PKARC
Comp. Comp. Dec. Comp. Comp. Dec.
Time Size Time Time Size Time
-----------------------------------------------------------------
Binary 272,640 2.91 165,875 1.32 3.57 175,511 2.14
Text 96,768 1.04 47,973 0.55 1.26 39,778 0.82
Total 369,408 3.95 213,848 1.87 4.83 215,289 2.96
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.