A Simple Data-Compression Technique
Ed Ross
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.
Introduction
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.
Overview
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.
Compression Function
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.
Hash Table
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.
Decompression Function
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 Compression Codes
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.
Driver Program
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.
Summary
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.
