compact
This program is similar to the well known compress program but runs faster, compresses large files better, and has a superior worst case expansion of incompressable data. The program supports multi-volume data sets, and can run as multiple concurrent tasks to overlap compute and I/O activities. These characteristics make it particularly useful when doing periodic system backups, especially with streaming tape drives.
The magic number for big-endian compacted files is C5A3; little endian files use the byte-swapped A3C5. The recommended suffix for compacted files is (.W).
This program may be used for research into data compression techniques only. Be sure to read WARNING section for further discussion.
In the options below, upper case letters refer to the expanded input or output stream, while opposite lower case letters refer to the compressed stream. All numbers may be suffixed by b (512 byte blocks), k (kilobytes), or m (megabytes).
The 16-bit input code size halves the number of operations required by the 8-bit compress algorithm, but uses more memory, and takes longer to fill the string table. The larger input code size also improves the worst-case expansion of incompressible data, since (with default 17-bit output) the worst-case expansion is only 1/16 or about 6%.
Because the program compresses 16-bit codes, it is susceptable to big-endian/little-endian byte ordering incompatibilities. In practice this is handled automatically when reading the compressed file, because the magic number is seen as byte-swapped; the program knows to byte-swap both input and output streams when reading the data back in.
On systems available to the author, with compressed file sizes of 1 megabyte or larger, compact runs 2.5 to 3 times faster than compress while producing an output file typically 10% smaller. These characteristics are largely insensitive to the maximum output code size. On highly compressible data, larger output code width further improves compression perhaps 10%; however with incompressable input data (eg *.Z files) compression deteriorates by about the same amount.
An output code width of 17 bits requires about a megabyte of memory. Each additional output bit about doubles this requirement. Hence output code sizes of 20 bits or more are impractical on most systems, but values up to 26 bits or so could theoretically be used.
On systems without previously compressed files, compact generally compresses anything (including program binaries) by 50% or better. With 35% compressed files (the author's system disk) data compression is still 42%; this compares to 31% feeding the same input stream to compress.
With the -t and -T the program uses multiple processes, pipes, and System V shared memory to overlap compute and I/O activities. When both options are selected, one child does input directly to shared memory, while another child does output directly from shared memory, and the parent does data compression from shared memory to shared memory without device I/O delays.
To achieve maximum performance on a system with adequate real memory, it is usually good to specify both input and output buffering. Buffering on the expanded side is useful to smooth out the inherent bursty performance of the filesystem; 100K to a megabyte or so works well here. Buffering on the compressed side should be sufficient to hold all data produced while the streaming tape stops, reverses and restarts; generally this takes 1-3 seconds.
At the time of this writing, peak performance is limited on most systems by the host processor. If input-output buffering is well tuned, processor utilization of 98% or better is common. The compression algorithm itself compresses 20-30 KB/second per processor VAX MIP available. However some system time is required to do I/O, so uniprocessor systems cannot achieve this speed in practice.
As an example, a particular SparcStation 1 (12 VAX MIPS) with a fast SCSI disk, 35% compressed files and a cartridge tape drive can do a 273 Megabyte tar backup to 159 MB of tape in 36 minutes using about 3 megabytes of working storage, 50% user and 13% system time. The remaining processor power is absorbed by the tar program to bring total system processor utilization to 99%. This runs the tape drive at 74% of rated speed. A similar uncompressed backup running the drive at full speed would take 46 minutes, except that the data wouldn't fit on the tape. The specific shell command used is:
tar cf - /home | compact -T400 -B4k -t6 -b100k >/dev/rct0
This program may be used only for research into data compression, as a case study in program optimization, or as an example of System V interprocess communication.
The author originally intended the program for practical day-to-day usage. However, in final preparation for program release, it was learned the program probably infringes one or more widely licensed patents in data compression. There is no choice but to release the program for research purposes only.
Compact was derived exclusively from the compress program and from the paper quoted in the references. It appears the author duplicated much of the research leading to V.42bis, and the discussion given there is useful in understanding this program. There remain significant differences the author has not analyzed in detail. Careful study of those differences might yield something new.
A Technique for High Performance Data Compression, Terry A. Welch, computer, vol. 17, no. 6 (June 1984), pp. 8-19.
The program attempts to always read full input records. If for example a 10KB read returns only 4KB, the program tries again with 6KB. If less than 6KB is received, it will try again with the remaining buffer space. Some tape drivers may consider this antisocial behavior.
The program won't run on machines with 16 bit integers and 64K addressing. Intel 80286 users, eat your hearts out.
An alarmingly large number of systems seem unable to do floppy or tape I/O to shared memory, presumably because the DMA lock-down mechanism is confused by shared pages. On these systems, the x or X options must be used to prevent device hangs or system crashes.