From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,9cecf056761bd1d9 X-Google-Attributes: gid103376,public From: John Howard Subject: Re: Data compression (in Ada) Date: 1996/06/30 Message-ID: #1/1 X-Deja-AN: 162943363 references: <31D41C54.794BDF32@mailgw.sanders.lockheed.com> <4r200g$lh6@usenet.srv.cis.pitt.edu> content-type: TEXT/PLAIN; charset=US-ASCII organization: SkyNET Corporation mime-version: 1.0 newsgroups: comp.lang.ada Date: 1996-06-30T00:00:00+00:00 List-Id: 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