The GIF Controversy: A Software Developer's Perspective
Last revision June 20, 2004. Original text published January 27, 1995. © 1995-2003 Michael C. Battilana. Web shortcut to this page: lzw.info. This page also has a PURL for cataloging and bibliographical purposes. Parts are quoted with permission from CompuServe Information Service. Parts are excerpted from the PNG specification.
This article was written with great care. It may reflect personal opinions of the author, which are not necessarily shared by the publishers, who cannot assume any responsibility for mistakes or misprints. Nothing in this article should be regarded as legal counsel. If you require legal or other expert assistance, you should consult a professional advisor. Many of the designations used by manufacturers and sellers to distinguish their products are trademarks. The author of this article has made every attempt to supply trademark information about manufacturers and their products. GIF and Graphics Interchange Format are service marks of CompuServe Inc. PostScript is a registered trademark of Adobe Systems Inc. TIFF is a trademark of Aldus Corp.
Between 1987 and 1994, GIF (Graphics Interchange Format) peacefully became the most popular file format for archiving and exchanging computer images. At the end of December 1994, CompuServe Inc. and Unisys Corporation announced to the public that developers would have to pay a license fee in order to continue to use technology patented by Unisys in certain categories of software supporting the GIF format. These first statements caused immediate reactions and some confusion. As a longer term consequence, it appears likely that GIF will be replaced and extended by new file formats, but not so before the expiration of the patents which caused so much debate (at midnight US Eastern Standard Time on June 19, 2003 for the US patent, and midnight local time on June 18 and 19, 2004 for the European and Japanese counterparts, respectively).
This is a very interesting case, which could teach more than one lesson on the theory and practice of software and the laws. There are many entities involved. Fingers have been pointed at lawmakers, Unisys, CompuServe and developers. In theory, it may have been possible for any or all of these parts to prevent the matter from creating so much anxiety in the first place. Yet we are all here, debating on this issue. This article intends to provide a collection of information from the history of the controversy to the most recent events, as they were perceived by a software developer.
CompuServe released GIF as a free and open specification in 1987. GIF soon became a world standard, and also played an important role in the internet community. It was well supported by CompuServe's Information Service, but many developers wrote (or acquired under license) software supporting GIF without even needing to know that a company named CompuServe existed. GIF was relatively simple, and very well documented in books, articles and text files.
GIF images are compressed to reduce the file size. The technique used to compress the image data is called LZW (after Lempel-Ziv-Welch) and was first described by Terry A. Welch in the June 1984 issue of IEEE's Computer magazine. Unisys holds a patent on the procedure described in the article, but the article describing the algorithm had no mention of this. The LZW procedure was simple and very well described, and it soon became a very popular technique for data compression (just as GIF would become a standard in its own field). It appears that neither CompuServe, nor the CompuServe Associate who designed GIF, nor the computer world in general were aware of the patent. GIF is not alone in the use of LZW. The TIFF file specification also includes LZW-compression among its compression methods, and so do dozens of very popular file archiving programs (such as Compress).
While having the right to pursue legal action or seek damages against infringing LZW developers and publishers, Unisys has so far been very accommodating and fair. It is likely that the success of LZW and its thousands of implementations, especially among small developers, caught Unisys unprepared. Otherwise, it would be difficult to understand how Unisys could first allow a very large number of small and big developers to use LZW for years, and then, after the establishment of various standards based on LZW, change its attitude.
The original CompuServe/Unisys licensing agreement text which had upset so many developers was immediately followed by clarifications from both CompuServe and Unisys. Given that the online community tends to be suspicious about anything that is big, has a legal department or owns software patents, Unisys had to face a particularly delicate challenge. But it probably wasn't easier for CompuServe, who had to explain the patent issue to its own developers, some of whom felt "betrayed". The outside world would learn about this issue from the press in the following days.
Even Time Magazine reported about this matter, although like most of the newspapers it concentrated on GIF more than on TIFF, LZW, Unisys or software patents. In the meantime, a group of leaders of the online graphics community began working on a patent-free future of GIF. These efforts would later converge into the PNG specification. The full texts of official statements from CompuServe and Unisys are also included at the end of this article [edited out of this version].
Among the first reactions, some bulletin board systems had all GIF files deleted from their hard disks (or converted into JPEG format). Common remarks included:
These reactions may require some clarification.
Unisys, and not CompuServe, has been "trying to impose" a royalty. The problem is not specific to GIF, but includes TIFF and archiving software.
GIF files are not covered by the patent. There is no risk in distributing GIF files or in using the GIF name. According to a CompuServe spokesperson, "Recent discussions of GIF taxes and fees are totally without merit. For people who view GIF images, who keep GIF images on servers, or who are creating GIF images for distribution, the recent licensing discussions have no effect on their activities."
Only the software employing the LZW algorithm for writing GIF files is "at risk". The Unisys patent includes claims which specifically cover the decompression of LZW-compressed material, so it may also affect simple GIF readers. Several patent attorneys consulted on this matter have concluded that decompression-only programs do not infringe upon the Unisys patent. Unisys however does not appear to share this opinion.
A format such as JPEG cannot be used as a substitute for GIF. Unlike GIF (and PNG), JPEG was designed as a "lossy" format. This means that it slightly changes an image as it is compressed. This is unacceptable for many applications. Also, while JPEG excels in compressing real world true color images, it offers no support for palette-based images (support for these has been added as part of the JPEG 2000 standard). Additionally, some JPEG-related technology itself has been the object of patent claims (e.g. US patent 4,698,672).
The CompuServe licensing agreement was intended as a voluntary service to the few dozen developers creating software for use primarily in conjunction with the CompuServe Information Service (CIS). This includes applications such as CompuServe "navigators", but does not apply to general purpose GIF readers/writers (which are not intended for use primarily in conjunction with CIS).
On January 27, 1995, Unisys announced new licensing policies regarding "The Welch Patent". These include a .45% royalty on the total unit selling price of GIF/LZW products (minimum $0.10, maximum $10.00 per unit) and a .65% royalty on GIF/TIFF/LZW products (minimum $0.20, maximum $25.00). For further information and a copy of the written agreement it is possible to call Unisys at +1 215 986-4411, or email lzw_info(at)unisys.com.
Any organization using LZW should look at whether they have an infringement on Unisys' patent. CompuServe is not involved in any of these discussions - they are between Unisys and outside developers.
Normally, procedures such as LZW are published in magazines so that they can be shared by the community of software developers. LZW itself is a refinement of other algorithms published in the years before (Ziv-Lempel and others). Software is usually protected by copyright law, but in recent years (since 1981 in the USA) in several countries it has become possible to patent software. Initially, only software used to control hardware could be patented. This interpretation was soon extended to include all types of software (except for "pure mathematical algorithms"). While software patents have become an opportunity for many, they remain a controversial danger for others. Any programmer or publisher might be trapped at any time by a patent infringement claim that could not be foreseen or avoided.
Publication of an algorithm in a magazine does not automatically exclude a patent application. In many countries, including the USA, it is possible to apply for a patent and still publish the paper without mention of the application. In the USA (but not in many other countries), the patent application may even be filed within 12 months of the publication. Under such regulations, the only algorithms that might be used freely and without risk would be those published prior to 1981 (e.g. Donald Knuth's "The Art of Computer Programming").
Today, even designing a graphics file format can become a programmer's nightmare. One very active member of the internet community (and author of the GZIP compressor) has collected information on more than 350 patents on lossless data compression and 100 on lossy image compression. Lempel, Ziv, Cohn and Eastman patented their original LZ78 algorithm (US patent 4,464,650). The LZW algorithm which is now attracting so much attention is patented by both IBM (4,814,746) and Unisys (US patent 4,558,302, European patent 0,129,439 - Japanese and other patents pending), while British Telecom (BT) holds a similar patent. The IBM patent application was filed three weeks before that of Unisys, but the US patent office apparently failed to recognize that they covered the same algorithm. (The IBM patent is more general, but its claim 7 is said to be exactly LZW.)
The LZW patent, as well as its international counterparts, and similar patents filed by others, are expected to remain valid for at least 20 years from the original filing date of June 20, 1983, i.e. until midnight US Eastern Standard Time on June 19, 2003 for US patent 4,558,302. The European counterpart EP0129439 (covering at least Germany, the UK, France and Italy, as long as yearly fees are paid) was filed on June 18, 1984, and the Japanese counterpart JP7249996 was filed on June 20, 1984. Although the international counterparts mention June 20, 1983 as the priority date (which is relevant for determining novelty) the validity of these patents is 20 years from their filing date.
10 Years of LZW
While the original article on LZW was published in 1984, the LZW patent issue first surfaced in the press in 1989, when the BTLZ algorithm (a procedure similar to LZW developed and patented by British Telecom) was to be approved for data compression into the V.42bis modem standard. Unisys said on at least one occasion that it first began to learn of the widespread use of LZW in connection with the development of this standard. The first licensing arrangements put into place included those with modem manufacturers ($ 20,000 for each one-time license) and with Adobe PostScript developers ($ 10,000).
An article on "LZW Data Compression" was published in the October 1989 issue of Dr. Dobb's Journal (see the Bibliography section for more details). A reader replied in the December issue explaining that the algorithm was patented. The author of the article added that he was unaware of any patent on the algorithm. More readers wrote, and in the March 1990 issue the editor-in-chief dedicated his Editorial to this topic, which in his words "sparked a forest of fires". The same issue also contained an official statement by Unisys Corporation, which confirmed that LZW was patented, mentioned the modem industry, and indicated how developers could contact Unisys.
In the October 2, 1989 issue of PC Week, "Spencer the Katt" wrote:
In about the same period, an article in InfoWorld mentioned the fact that modem manufacturers were facing the possibility of having to pay royalties to Unisys and to other patent holders for the right to use LZW.
Page 132 ("LZWEncode Filter") of the PostScript Language Reference Manual, Second Edition, published in December 1990, contains the address of the Welch Licensing Department at Unisys Corporation.
In the March 1991 issue of Byte, Steve Apiki ("Lossless Data Compression") explained that LZW is used in GIF, and that "The [LZW] algorithm itself is patented by Sperry [now Unisys]."
At this point, at least the readers of some publications were potentially aware of the LZW patent. But still, there were few links to GIF. Unisys apparently didn't know about GIF, nor did most GIF developers know that GIF contained LZW technology. And those who may have known, not necessarily knew about the patent.
This issue was also discussed among a small group of the better informed members of the CompuServe PICS Forum (now GRAPHSUP). The general feeling at that time was that "Unisys only intends to get royalties from hardware vendors," and there was some consensus on the idea that Unisys "wouldn't do anything about pure software implementations".
Until the end of 1994, discussions on CompuServe's Information Service showed no clear mention of the requirement to get a license from Unisys for using LZW in GIF applications. During 1988 at least one developer stopped working on GIF tools because of considerations regarding the LZW patent, and reportedly "made CompuServe aware of it". This apparently was limited to private verbal conversations, and information on this behalf could be found neither in the press nor in CIS. Other developers are reported to have directly informed the Unisys licensing department about the use of LZW in GIF between 1988 and the end of 1989, but it is not known that Unisys ever acknowledged these actions in writing. At about the same time, at least one CIS member, working for Unisys, reportedly informed Unisys management, "clearly pointing the use of LZW in GIF".
In 1996, attention was drawn to one of CompuServe's public file libraries, which still contained an archive named "UNIGF2.ARC", uploaded on July 13, 1988, titled "Decoder -- Sperry, Unisys", and described as a "Sperry PC high-res GIF display" program. The uploader however immediately clarified that all references to Unisys contained in the article were meant to indicate a particular configuration of computer and graphics board, and not the patent.
Among the developers who contacted Unisys between the end of 1990 and the beginning of 1991, there was at least one GIF developer. He recently described his experience:
In those days, the standard license fee for PC-based software products was $1 per copy sold (or a 1% royalty), after a $100 advance payment. Apparently, Unisys still didn't know that GIF was based on LZW. In January 1995, Unisys stated:
Two years before the Unisys statement, at the end of 1992, an Italian software house contacted Unisys because it was interested in a license for the possible use of LZW in its PostScript Level 2 drivers. That correspondence also mentioned GIF and TIFF as using LZW, and anticipated some of the controversies which would follow 25 months later. Unisys replied: "... You raise a number of interesting issues which require consideration..."
While disclosing the full contents of this correspondence would probably not serve anyone's interest, the text of two letters sent to Unisys in 1992 is included at the end of this article [edited out of this version], because the author feels that this 1992 perspective could complement the article with a few interesting ideas. The letters have not been edited, so some details (such as the reference to ZIP) may be incomplete with respect to current knowledge.
Unisys offered that software house a $ .25 per unit royalty (1% of the net income) as an alternative to the PostScript one-time license, but did not answer the question raised: "If we implemented a software GIF or TIFF image file loader and saver (both formats are based on the LZW algorithm), would we need a license from Unisys Corp., as far as U.S. Patent 4,558,302 is concerned?". According to public statements, Unisys did however contact CompuServe the following month.
December 29, 1994 - The Days After
Between 1993 and 1994, the majority of developers still didn't know that GIF employed a patented algorithm, although both Unisys and CompuServe were aware of this (as the developers would learn in December 1994). Different opinions have been expressed on this. Some developers feel that reaching an agreement behind the scenes was the least destructive thing that could be done. Other (at times passionate) opinions picked up on electronic media are similar to these three:
Unisys replied in part with reassuring clarifications to the general public, explaining that if the software was developed prior to 1995, or if it is public domain or freeware, the developer need not to worry:
However, these statements were followed by far more restrictive interpretations, both in early 1995 and in the summer of 1996. It soon became clear that Unisys could be demanding royalties for everything "manufactured" after 1994. One developer contacted Unisys and reported:
While the Unisys licensing policies announced on January 27, 1995 (and later narrowed to more restrictive but clearer definitions) enabled many software publishers to again ship their products after a month-long pause, other developers preferred to abandon GIF already in 1995, waiting for a patent-free evolution of GIF. Comments included:
Some of the most active developers decided to collaborate on the design of a patent-free evolution of GIF (and TIFF's LZW compression mode). A method was quickly found to create uncompressed GIF files without using LZW code, while remaining compatible with existing GIF loaders. Also, a variety of different procedures and data structures (such as Shannon-Fano and AVL trees) have been used to compress data in ways similar, if not always equivalent, to LZW. But a diversity in procedures and data structures alone apparently does not escape the patent. As one expert said, "If the output data is [compressed] GIF, the compressor infringes the Unisys patent regardless of the algorithm."
On January 16, 1995, CompuServe declared its intention to coordinate the development of GIF24, a freely usable successor to GIF capable of 24-bit lossless compression. Several developers invested a lot of time and energies to solve the Unisys patent problem, and rapidly worked out different modifications to the GIF specification. One of the better known efforts was the project for a "GEF" graphics-exchange format. GEF and GIF24 converged into PNG (official abbreviation of "Portable Network Graphics", unofficially "Png is Not Gif").
The open architecture of PNG preserves the simplicity that made GIF so popular, and adds features such as true color. Test results indicate that PNG is capable of (losslessly) compressing true color images better than any other widely used image format. It is also more effective than GIF in storing palette-based images. More information on PNG is included in the Reference and Bibliography sections.
At the end, it appears that if so many efforts converge into a new, improved standard, we still have to give part of the credit to the LZW patent...
Possibly in part as a reaction to commercial developers splitting GIF code from their commercial applications and making available the GIF code through free distribution channels, Unisys later clarified that commercial developers in general would be subject to the minimum royalty ($0.10) even on software distributed for free. According to statements reportedly made by Unisys to individual developers, unlicensed freeware GIF software would be allowed only if it came from charitable institutions. Shareware organizations would have to both set a 30-day expiration limit in the (unregistered) program, and also disable the GIF component until the software is registered. Other types of unlicensed "freeware" distribution of GIF and other LZW-based software, regardless of the medium (books, internet, CD-ROM collections, etc.) would not be allowed.
At the end of summer 1996, the references to certain types of freely distributable programs which until then were officially allowed to be distributed without a license had disappeared from the Unisys web site:
The Press Releases archive on the Unisys web site was updated, and the original 1995 item titled "1-10-95 UNISYS CLARIFIES POLICY REGARDING LZW PATENT USE IN ON-LINE SERVICE OFFERINGS" was changed to point to a new public statement, which included:
In September 1996, the new approach was described by some developers:
While the World Wide Web Consortium (W3C) officially endorsed the PNG specification as a "W3C Recommendation" and the major graphics packages now support PNG, as of 1998 most internet browsers still could not directly handle PNG. The popularity of GIF even received an unexpected boost when Microsoft, Netscape and others added support for GIF animations to their browsers. As a result, GIF became more difficult to replace with PNG, since PNG was not designed to support animation. The developers of PNG are currently completing a meta-PNG specification providing superior animation features, called MNG. It appears however increasingly likely that before both PNG and MNG will be supported by a majority of web browsers the LZW patent will have expired. At the same time the JPEG 2000 specification, also designed to be "patent free", is combining technologies such as wavelet compression with support for image types which previously required the use of different file formats such as PNG, MNG, TIFF, JPEG and GIF.
In the second half of 1999 Unisys changed the wording on a LZW information page at its web site, and made available new server licensing options. These changes inspired a new wave of popular interest in the GIF/LZW issue. The substance of the matter however has not changed much since 1995: Unisys is not asking for any licenses in relation to GIF data files, but only for software implementing the LZW algorithm. Most commercial applications that create GIF files already have a GIF/LZW license from Unisys, so users and webmasters creating GIF files with these programs do not need to worry about getting a separate license. As for the renewed proposal to "burn all GIFs" and replace them with a format such as PNG, that is not yet completely possible, because PNG does not support animation, which is widely used with GIF.
As of June 20, 2004, the GIF/LZW-related patents mentioned in this text have expired.
(Any comments or experience you would like to share are always very appreciated. The email address can be found here.)
The following sections have been edited out:
Adobe Systems Incorporated
Association of Shareware Professionals Forum
Battilana, Michael C.
Bell, Timothy C., Cleary, John G. and Witten, Ian H.
Boutell, Thomas (Editor)
Cloanto Italia srl
CompuServe Graphics Developers Forum (GO GRAPHDEV)
CompuServe Graphics Support Forum (GO GRAPHSUP)
Knuth, Donald E.
Landy, Gene K.
Miles, J. B.
Nelson, Mark R.
Nelson, Mark R.
PNG (Portable Network Graphics)
"Spencer the Katt"
US Patent 4,558,302
Vaughan-Nichols, Steven J.
Welch, Terry A.
Ziv, Jacob and Lempel, Abraham
Ziv, Jacob and Lempel, Abraham
More articles on the GIF issue:
Special thanks to Dave, David, Diana, Frank, Jason, Jean-loup, Jon, Kevin, Larry, Pierce, Richard, Tim, Tom and many others for their precious help.