The GIF Controversy: A Software Developer's Perspective January 27, 1995 - Text revision 2 - March 31, 1995 by Michael Console Battilana Copyright (c) 1995 Cloanto Italia srl, All rights reserved Parts are quoted with permission from CompuServe Information Service Parts are excerpted from the PNG specification Permission granted for non-profit electronic distribution Suggested file name: "giflzw1.txt" Keywords: GIF PNG LZW WELCH COMPRESSION UNISYS PATENT HISTORY TEXT Free by mailing before April 30, 1995 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., an H&R Block Company. PostScript is a registered trademark of Adobe Systems Inc. TIFF is a trademark of Aldus Corp. Abstract During the past eight years, 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 the new PNG (Portable Network Graphics) format. Introduction 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 accomodating 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 (scan this text for #1). The full texts of official statements from CompuServe and Unisys are also included at the end of this article (scan this text for #2). 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: "PROTEST OF NEW COMPUSERVE-UNISYS GIF USAGE TAX !!" "They [CompuServe] seem to think that GIF is the greatest thing since free online magazines." "The announcement by CompuServe and Unisys that users of the GIF image format must register by January 10 and pay a royalty or face lawsuits for their past usage, is the online communications community's equivalent of the sneak attack at Pearl Harbor." 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. 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 send E-mail to . 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. Software Patents 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 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 (4,558,302), while British Telecom 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.) 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 - scan this text for #4). 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 a columnist wrote: "Alas, there's no consolation for developers of archiving programs that rely on the LZW data-compression algorithm. While cruising the bulletin boards last week, Spencer learned that Unisys has a patent on the algorithm, upon which a slew of data-compression programs are based. Watch out." 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. 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: "Finding the right person was the most difficult part of licensing LZW, but hopefully it's easier today (perhaps only 5 phone calls would be needed!)... When talking to Unisys back then, my recollection is that we had to basically tell the people at Unisys, 'Believe me, you DO own a patent on LZW; who do we talk to about LICENSING?' When we finally reached the licensing/legal department, THEY knew they had a patent, and spelled out the terms. I recall the person we were dealing with saying something like, 'They [Unisys] laugh when I make all these $1 deals, but we have to charge something to protect the patent.'" 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 ago, Unisys learned that the LZW method was incorporated in the GIF specification and immediately began negotiations with CompuServe in January of 1993. We reached agreement with CompuServe on licensing the technology in June 1994..." Two years before the Unisys statement, at the end of 1992, Cloanto, 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 (scan this text for #3), 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 Cloanto 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 by Cloanto: "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: "Consider this. CompuServe admits to knowing about patent problems with the GIF file format as early as January of 1993. ... We added GIF support to Fastgraph months after CompuServe admits knowledge of the patent problem... We relied on the information that was supplied to us by CompuServe. If CompuServe had told us the truth when they knew it, we never would have added GIF support..." "If I chose to put GIF encode/decode functions in my software development toolkits, my main threat of legal liability would not come from Unisys, but rather from one of my customers being sued by Unisys, who would turn around and sue me for selling them some code that contained patented algorithms." "I still don't have a clue what my situation is if I want to sell source and object code that imports and exports GIF images. I am not in the end-user app business, but my customers are, and they certainly will have to have an LZW license, but what about me? I've talked with Unisys by voice and E-mail, and the voice discussion was entirely unsatisfactory as I posted when it happened - basically the Unisys guy said anyone who sells code for $100-$300 a pop was a total _____ for selling it that cheap. The E-mail discussions I've had said 'OK - we hear you - we'll get back to you.' Never happened." 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: "... Unisys does not intend to pursue previous inadvertent infringement by versions of GIF-based software products marketed prior to 1995... Unisys does not require licensing, or fees to be paid, for non-commercial, non-profit GIF-based applications, including those for use on the online services... Commercial developers... are expected to secure a licensing agreement with Unisys for software products introduced beginning in 1995, or enhancements of products that were introduced prior to 1995." However, these statements were followed by far more restrictive interpretations. It soon became clear that Unisys could be demanding royalties for everything "manufactured" after 1994. One developer contacted Unisys and reported: "I called the Unisys lawyer you referred me to and he confirmed this position. Even a book or CD containing *pre 1995* freeware is subject to royalties if the disk is put together in 1995... Royalties must be collected *again* for each update release." While the new Unisys licensing policies (announced on January 27, 1995) enabled many software publishers to again ship their products after a month-long pause, other developers preferred to wait, hoping for a patent-free evolution of GIF. Comments included: "What if I sign up and then they announce a new GIF specification which does not use LZW?" "Labeling and user notification requirements in the agreement are ridiculous. I understand their desire to 'spread the word' about their patent, but they're telling me that I have to provide far more info on their ownership of the patent than they require in the docs/packaging of modem manufacturers and other users of LZW. Fair is fair. A blurb in the online help and docs should be sufficient; a 'non-defeatable' splash screen at startup is going too far." "Unisys is attempting to control how we (and other shareware authors) do business, and to make us billboards for their LZW patent... By making me tell my users how many security backups they can make, etc., they're telling me how to run my business and how to interface with my customers." "Imagine the nightmare of having to pay royalties to 10 patent holders, each of whom tells you how to run your business..." "Unisys has given us a chance to work together to change the system - rather than waiting to be sued one by one for this patent or that. We can win the fight against software patents, if we speak loud and clear against them." 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 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 equivalent, to LZW. But this diversity apparently does not escape the patent. As one expert said, "If the output data is 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... The author of this text can be contacted at . Any comments, or experience you would like to share, would be very appreciated. Reference [search key: #1] If the excerpts from the PNG specification are not included here in order to keep the file size reasonable ("lossy compression"), please check for another file accompanying this text (suggested file name: "giflzw2.txt"), or send E-mail to before April 30, 1995. The latest hypertext version of the full document is available on the World Wide Web: ----------------------------------------------------------------------- Excerpts from the PNG (Portable Network Graphics) Specification, Ninth Draft - Revision date: 7 March, 1995 [The text is not included here] ----------------------------------------------------------------------- [search key: #2] If the official texts from CompuServe and Unisys are not included here in order to keep the file size reasonable, please check for another file accompanying this text (suggested file name: "giflzw2.txt"), or send E-mail to before April 30, 1995. ----------------------------------------------------------------------- AGREEMENT FOR USE OF GRAPHICS INTERCHANGE FORMAT(SM) [The text of the Graphics Interchange Format (GIF) Developer Agreement, released by CompuServe on December 29, 1994 is not included here. It became obsolete when Unisys announced its new licensing policies regarding "The Welch Patent" on January 27, 1995.] ----------------------------------------------------------------------- ----------------------------------------------------------------------- %: 174559 S19/GIF/LZW Discussion [GRAPHSUP] 04-Jan-95 17:07:50 Sb: #GIF/LZW Clarification Fm: Larry Wood 76703,704 To: All [The text is not included here] ----------------------------------------------------------------------- ----------------------------------------------------------------------- #: 181065 S3/Hot News and Rumor 07-Jan-95 19:12:19 Sb: #Unisys GIF Clarification Fm: Steve Ahlstrom/SYSOP 76703,2006 To: All [The text is not included here] ----------------------------------------------------------------------- ----------------------------------------------------------------------- From: rmarks@ecdcsvr.tredydev.unisys.com (Richard Marks) Date: Fri, 6 Jan 1995 22:09:14 GMT Unisys LZW Patent FREQUENTLY ASKED QUESTIONS January 6, 1995 [The text is not included here] ----------------------------------------------------------------------- [search key: #3] If the texts of the two letters are not included here in order to keep the file size reasonable, please check for another file accompanying this text (suggested file name: "giflzw2.txt"), or send E-mail to before April 30, 1995. ----------------------------------------------------------------------- From Cloanto/Unisys - November 6, 1992 [The text is not included here] ----------------------------------------------------------------------- ----------------------------------------------------------------------- From Cloanto/Unisys - November 12, 1992 [The text is not included here] ----------------------------------------------------------------------- Bibliography [search key: #4] [Author Unknown - Information Appreciated] "Spencer the Katt" PC Week, October 2, 1989 Adobe Systems Incorporated "LZWEncode Filter" PostScript Language Reference Manual, Second Edition Addison-Wesley Publishing Company ISBN 0-201-18127-4 Apiki, Steve "Lossless Data Compression" Byte, March 1991, pages 309-314, 386-387 Association of Shareware Professionals Forum CompuServe GO ASPFORUM Bell, Timothy C., Cleary, John G. and Witten, Ian H. "Adaptive Dictionary Encoders" Text Compression Prentice Hall ISBN 0-13-911991-4 Boutell, Thomas (Editor) PNG (Portable Network Graphics) Specification Ninth Draft - Revision date: 7 March, 1995 Hypertext version available on the World Wide Web: Clay, Betty "Texas Tales" ICPUG Newsletter, January/February 1995, pages 18-23 Cloanto Italia srl Supplement to Personal Paint Manual Version 6.1/1995, January 27, 1995 CompuServe Graphics Developers Forum (GO GRAPHDEV) CompuServe Graphics Support Forum (GO GRAPHSUP) Console Battilana, Michele "LZW Data Compression without Hashing" University of Udine Exam Project, July 9, 1987 Elmer-Dewitt, Philip "Will Gates Get the Net?" Time, January 30, 1995, Page 47 Erickson, Jonathan "Patent Letter Suits" (Editorial) Dr. Dobb's Journal, March 1990, page 6 Erickson, Jonathan "The Green, Green Cash of Gnomes" (Editorial) Dr. Dobb's Journal, April 1995, page 6 Gardner, Ray "LZW Patent Issues" (Letter) Dr. Dobb's Journal, December 1989, page 8 Internet comp.graphics Newsgroups Internet comp.sys.graphics Newsgroup Knuth, Donald E. The Art of Computer Programming Volume 3 / Sorting and Searching Addison-Wesley Publishing Company ISBN 0-201-03803-X Landy, Gene K. The Software Developer's and Marketer's Legal Companion Addison-Wesley Publishing Company ISBN 0-201-62276-9 Miles, J. B. "Patent Issues May Stall Approval of New V.42bis Modem Standard" InfoWorld, approximately fall of 1989, pages 43-44 [Author, Article Title and Exact Date Unknown - Information Appreciated] [InfoWorld Article on LZW and Modem Implementations - Is this it?] Nelson, Mark R. "LZW Data Compression" Dr. Dobb's Journal, October 1989, pages 29-36, 86-87 Nelson, Mark R. "LZW Patent Issues" (Reply to Letter) Dr. Dobb's Journal, December 1989, pages 8-12 PNG (Portable Network Graphics) Information and support material available from: Internet comp.graphics Newsgroups Internet comp.sys.graphics Newsgroup CompuServe Graphics Support Forum (GO GRAPHSUP) Via FTP from The PNG specification is also available on the World Wide Web: Unisys Corporation "Patented Algorithms" (Letter) Dr. Dobb's Journal, March 1990, page 8 Vaughan-Nichols, Steven J. "Saving Space", "Squeeze, Squash, and Crush" and "Legal Seagull" Byte, March 1990, pages 237-243 Welch, Terry A. "A technique for high-performance data compression" IEEE Computer, June 1984, pages 8-19 Ziv, Jacob and Lempel, Abraham "A universal algorithm for sequential data compression" IEEE Transactions on Information Theory, May 1977, pages 337-343 Ziv, Jacob and Lempel, Abraham "Compression of individual sequences via variable-rate coding" IEEE Transactions on Information Theory, September 1978, pages 530-536 Special thanks to Dave, David, Diana, Frank, Jason, Jean-loup, Jon, Kevin, Larry, Pierce, Richard, Tim, Tom and many others for their precious help.