Re: Data compression (in Ada)

[John Howard <jhoward@sky.net>]

On 29 Jun 1996, Tore Joergensen wrote:

> Mike Roske (mroske@mailgw.sanders.lockheed.com) wrote:
> : I am looking for an Ada 83 implementation of a file
> : compression/decompression algorithm (a la Zip).  It doesn't have to be
> : compatible with Zip.
>
> : I have a need to take a file, compress it, and store it on an embedded
> : file system (part of the load process).  At run-time I will be
> : uncompressing the file into RAM in order to access the data.  There 
> : isn't enough EEPROM to store the uncompressed file, but I have enough
> : RAM once I get started.

> Try to find some information on LZW compression. This is the compression
[snip]

LZW is a good general-purpose compression method though there are times 
when LZW compression actually expands the size instead of reducing it.
More serious is the fact that the Lempel-Ziv Welch (LZW) algorithm is
patented.  Don't use it unless you are willing to pay royalties.  UniSys
(or whatever they changed the name to) acquired the LZW patent.  The LZW 
patent has only recently been enforced with lawsuits.  Terry Welch is the 
culprit who published the algorithm for all the world to appreciate.  The
trouble is the owner did not enforce licensing until several years after 
LZW was made popular via the efforts of CompuServe.

That stealthy move has caused alot of problems already.  GIF is based on 
LZW and GIF is becoming popular due to Web browsers.  TIFF v5 and v6
defines LZW as part of their standard compression algorithms.  TIFF v6
recognizes LZW as patented and recommends its use be dropped.  The LZW 
stealth move is the main reason TIFF v6.0 was largely abandoned (JPEG as 
hastily defined to replace LZW for v6.0 was defective which basically left 
only RLE as a viable option supported by TIFF).  The new Adobe Public 
Document Format (PDF) also defines LZW as part of its standard.  The 
problem is that Adobe has licensed the use of LZW with its owner.  So even 
though PDF is a standard released to the public it can't be duplicated by 
software developers who don't license LZW with its owner.  PDF is 
copyrighted by Adobe but Adobe is not obligated to make PDF open.  That 
allows possible future stealth moves by Adobe or a successor (as happened 
from UniSys by acquiring the LZW patent).  PDF is a good strategic move 
for Adobe but PDF should be replaced with something truly open.  Certainly 
no public standard called "open" should rely upon patented algorithms 
requiring royalties.  [In May, I became interested in implementing Adobe 
PDF in Ada but I found LZW unavoidably defined by the standard.  Fool us 
once -- shame on you.  Fool us twice -- shame on us.  I have decided to
wait for a new TIFF standard and see what develops with alternative public
document formats that are truly open.]

The viable solution is to abandon LZW and instead use Lempel-Ziv Huffman
(LZH) or Run-Length Encoding (RLE) or Apple's PackBits for either 
compressing text files or black/white images.  PCX and fax formats are 
variations of RLE.  Go to www.adobe.com for information on RLE and 
PackBits.  LZH is found as Pascal source code on a Simtel mirror or in the 
SourceWare Archive Group (SWAG) sources.  There are variations of public
and royalty-free JPEG algorithms which are designed for compressing color
images.  Arithmetic compression is another neat algorithm which would 
often be desirable to use but cannot become popular to implement until its 
patent expires.

-- John Howard <jhoward@sky.net>