Development History Of a File Compression Utility by Richard Greenlaw 251 Colony Ct. Gahanna, Ohio 43230 May 18, 1981 Revised August 29, 1981 Introduction: The file compression system consists of two programs, SQ and USQ, meaning squeeze and unsqueeze. They are written in the C language for the BDS C compiler. The executable files are SQ.COM and USQ.COM, which are self-sufficient to run under the CP/M operating system and consist of 8080 machine code. SQ.COM is compiled from files SQ.C, SQDIO.C, TR1.C, TR2.C, IO.C, SQ.H, DIO.H and SQCOM.H. USQ.COM is compiled from files USQ.C, USQDIO.C, UTR.C, USQ.H and (again) DIO.H and SQCOM.H. Both COM files also include standard library functions and the BDS-C run-time package. SQDIO.C and USQDIO.H provide i/o redirection and pipe simulation and are just the BDS dio package renamed to produce distinct CRL files corresponding to the different addresses of external variables with which they are compiled. The SQ program builds a squeezed file by applying two transformations: First, byte values which are repeated consecutively three or more times are reduced to the value, the token DLE (delimiter), and a count. The penalty is that occurrances of DLE are encoded as DLE, zero. Second, the Huffman algorithm encodes each resulting byte value or endfile as a bit string having length inversely proportional to its frequency of occurrance. This is a complex process requiring reading the input file twice. The squeezed file contains various information to allow the USQ program to decode it and recreate the original file exactly. The environment: The programs should be nearly portable. The CP/M system actually used is single user 2MHz 8080 without interrupts. The BDS C compiler supports a subset of C. It does not support register variables, long integers or floats. That leads to complexity in collecting and processing the frequencies of occurance of the various byte values being encoded. Outline of SQ The interesting work begins in function squeeze in file SQ.C. In the first pass, init_huff in file TR2.C reads the input through the first encoder, getcnr, in file TR1.C, collects the frequency distribution and builds the decoding and encoding structures. Then wrt_head in file TR2.C writes control information and the decoding structure to the output file. In the second pass, encoded bytes consisting of bits and pieces of bit strings are generated by function gethuff in file TR2.C and are simply written to the output by squeeze. Development History of SQ There have been seven operational pre-release versions of SQ. The motive for change in each case was primarily increased execution speed, although the conveniences of operating on lists of files, automatic name generation for squeezed files, and output drive specifiers were also added in the later versions. Early versions called the following chain of functions to get a byte of encoded data: gethuff, getbit, get_cnr, getc_crc and getc. It wrote through putce and putc. That's a lot of function calling. In addittion, gethuff and getbit were passed pointers to functions to identify get_cnr. Actually, those versions used a dummy function for get_cnr, the repeated value encoder, although the actual code was present. This was to simplify debugging and because USQ did not yet have the inverse of that translation. The benchmark for comparisons was not consistent because files were lost at two points. In effect, the current SQ.COM squeezed itself! It typically acheived 6-7% compression on a machine code file of 8K to 10K bytes. Of course machine code is not a practical case, but it is a rugged workout. Text files are compressed 33% to 46% depending on the richness and distribution of the alphabet. V0, for which listings have not survived, took 5:10 (five minutes, 10 seconds) to squeeze itself! This was improved to 4:23 by the optimizer option of the compiler, which simply generates in-line code rather than subroutine calls for all local and external variable accesses. It was further improved to 4:18 (and restored to its original length) by the -e compiler option which specifies the origin of the external variable area to allow direct addressing. (The BDS linker resolves only function names - externals are actually like FORTRAN COMMON and are normally accessed relative to a pointer kept in RAM!). Subsequent improvements came mostly from recoding the key routine. Copies of gethuff and its partner getbit are attached for versions V1 through V6 and the complete listings (20 pages) for V6 are included. In V0 through V2, gethuff forms an output byte by calling getbit eight times and packing the bits. This is the obvious method because the Huffman translation produces variable length bit strings, not a byte for a byte. V1 introduced the variable codebyte to the getbit function. It was rotated each time a bit was removed, so that subsequent calls had to shift it only one bit position. This involved considerable change. Timing is uncertain now. V2 continued to improve the getbit function by customizing the three basic cases and providing seperate returns from each to avoid unnecessary work. The changes of V1 and V2 reduced run time to 1:41, a whopping 61% reduction! V3 incooperated getbit into gethuff. This wasn't difficult because getbit was called only once by gethuff. It ran in 1:27 (on a slightly smaller file), another 14% reduction. V4 removed the pointers to functions mentioned earlier and substituted direct calls. However, at this point the real translation for repeated values was enabled. The net result was a slight loss of ground to 1:30, but more productive work. V0 through V4 worked from Huffman code bit strings of indefinite length accessed through an array of pointers. Each string was byte alligned (unlike the final encoded data). V5 was a complete redesign of the storage and retreival of the array of code strings. I had finally succeeded in proving* that the maximum length code string would fit in the same space as the sum of all frequency counts, so scaling in init_huff was made more rigorous to fit them into unsigned integers (16 bits). * The proof was proven wrong in practice at least for the first implementation of the algorithm. Sq 1.5 (8/29/81) tries harder to generate codes no longer than it can handle (16 bits) and if it fails at this it fudges the counts and tries again. This redesign paved the way for a relatively simple method of processing the code strings several bits at a time, rather than singly in an eight pass loop to form an output byte. At this this point the fancy file name processing, etc., were added, increasing the size of SQ.COM from 7680 bytes to 10,112 bytes, an increase of 32% in the work performed by the "benchmark". V5 ran in 1:40, which scales to 1:16, a reduction of 16%. In a second variant, changing the variable cbitsrem to a char from an integer saved another 5%. V6 restructures the gethuff of V5, replacing the while loop with a custom (goto) loop with the exit condition tested only in a special case. The two basic cases also do only the work necessary to their cases. Also, squeeze in SQ.C calls putc directly and does its own check for write failure, saving one layer of function calls. It ran in 1:29 (scales to 1:08), a reduction of 6% from the second variant of V5. The overall performance improvement ratio, scaled for the one major change in the benchmark workload (but not taking credit for the enabling of the repeated character encoding) was about 4.5 : 1, or a reduction of 78%. The true improvement was probably a factor of 5.