LZW is Free! (Almost) [LWN.net]

[This article was contributed by Joe 'Zonker' Brockmeier]

The LZW patent is nearing its expiration date. Appropriately enough, patent 4,558,302 expires next Friday, June 20 -- plan your parties accordingly. At least if you're in the U.S. -- the patent will continue to be valid for a little longer in several other countries.

Unisys sat on the patent for nine years before it attempted to start collecting royalties on software that made use of LZW to create images in the Graphics Interchange Format (GIF), and for the use of GIFs on websites. Unisys really started putting the pressure on in 1999, however, asking web site operators to fork over a fee of $5,000 just to use GIFs on a publically-accessible website or an Intranet site. You could also get a license to cover both a "Billboard" site and an Intranet for the low, low fee of $7,500.

Pressure is a relative term. Unisys was never successful in garnering the licensing fees from the majority of sites that use GIFs, nor did they conduct an RIAA-style search for sites using GIFs to send threatening letters to. And, compared to Amazon's "one-click" patent, the LZW patent looks almost reasonable.

Nevertheless, the Unisys money-grab inspired a deep loathing in quite a few Webmasters and other users who had already been using GIFs or the LZW algorithm for quite some time, and who resented the sudden demand for royalties. Thus the Burn All GIFs day was born. Thanks to their GIF efforts, Unisys has the dubious honor of being one of the first companies to awaken the Free and Open Source software communities to the danger of software patents.

Don Marti, webmaster for the Burn All GIFs site, said it's yet to be seen how successful the Burn All GIFs project has been.

The real success of Burn All GIFs day will be measured by how well webmasters can stay away from patent minefields in the future. When you use a patent-encumbered format, you're setting yourself up to have the patent holder hold you up in the future.

The W3C's decision to declare itself a patent-shenanigans-free zone is a positive development, and other information technology standards bodies should also drop the idea of "UFO" (Uniform Fee Only) patent policies, which impose prohibitive transaction costs on free software and small companies.

Marti also noted that the W3C's royalty-free policy is a step forward for Free and Open Source software developers.

Of course, it's not all about GIFs. The LZW algorithm is also found in a number of other graphics formats and in programs that compress data. GIFs are merely the most widely-recognized use of LZW. For example, LZW is used in the Unix "compress" utility, which led to the creation of the widely-used gzip as a replacement.

It's unlikely that the Free and Open Source community will rush back to using the LZW algorithm, now that it has been effectively replaced. But even as it re-enters the public domain, the LZW tale serves as a cautionary tale of the dangers of software patents. It won't be the last.

(Log in to post comments)

LZW is Free! (Almost)

Posted Jun 12, 2003 14:43 UTC (Thu) by virtex (subscriber, #3019) [Link]

Unisys sat on the patent for nine years before it attempted to start collecting royalties on software that made use of LZW to create images in the Graphics Interchange Format (GIF)

The only way Unisys could have ever expected to receive royalties from GIFs is by waiting. GIFs flourished because they were free. Unisys waited for GIFs to become popular and for people to become dependent on them before demanding royalties. If those royalties had been expected from the beginning, GIF would have been a complete failure.

LZW and gzip

Posted Jun 16, 2003 20:31 UTC (Mon) by roelofs (subscriber, #2599) [Link]

For example, LZW is used in the Unix "compress" utility, which led to the creation of the widely-used gzip as a replacement.

"Led to" principally in the sense that any inferior technology leads to the creation of better technologies. gzip ultimately owes its development to PKWARE in the sense that they replaced LZW ("shrinking") with some Shannon-Fano thing ("implosion") in PKZIP 1.1 and then with an LZ77 derivative ("deflation") sometime around March 1991, IIRC (whenever PKZIP 1.93a came out). PKZIP's documentation of the format in appnote.txt opened the door for Info-ZIP's free implementations of inflate() and deflate(), and those in turn became the basis for gzip (and later zlib).

Whether the LZW patent had anything to do with PKWARE's switch, I don't know. But I do know that they had at least four compression methods in use by that time, not counting whatever was used in PKARC/PKPAK, and all of this happened long before Unisys started asserting its patent. That said, Jean-loup was paying attention to patents by then, but they were mostly those related to deflation, such as one by Fiala and Green[e].

Btw, in response to another poster, Unisys was the merger of Sperry-Rand and Burroughs, as I recall ("the power of 2" or something). The Sperry half brought the LZW patent.

Greg Roelofs