Contents | < Browse | Browse >

===========================================================================
          THE GIF CONTROVERSY: A SOFTWARE DEVELOPER'S PERSPECTIVE
  Michael Console Battilana                                mcb@cloanto.it
===========================================================================

[Yes, we ran an earlier copy of this article when the story first broke. 
However, considering Mr.  Battilana's close relationship to the story,
particularly the emergence of the new PNG graphics format, I feel that if
he has something more to say, it's worth a second look.  -Jason]

    January 27, 1995 - Text revision 2 - March 31, 1995
    by Michael Console Battilana <mcb@cloanto.it>
    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 <gltext1@cloanto.it> before May 31, 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 <lzw_info@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.

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 (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 (4,558,302), 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.)

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 <mcb@cloanto.it>.
    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 <gltext2@cloanto.it> before April 30, 1995.  The latest
hypertext version of the full document is available on the World Wide Web:
<URL:http://sunsite.unc.edu/boutell/png.html>

-----------------------------------------------------------------------
Excerpts from the  PNG (Portable Network Graphics) Specification,
                   Ninth Draft - Revision date: 7 March, 1995

[The text is not included here - Newer PNG specs have been released]

-----------------------------------------------------------------------

[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 <gltext2@cloanto.it> 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.]

-----------------------------------------------------------------------

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:
<URL:http://sunsite.unc.edu/boutell/png.html>

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 <ftp://godzilli.cs.sunysb.edu/pub/ngf>
The PNG specification is also available on the World Wide Web:
   <URL:http://sunsite.unc.edu/boutell/png.html>

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.