Editing GIF (section)

== Unisys and LZW patent enforcement ==<!-- This section is linked from PNG -->
In 1977 and 1978, [[Jacob Ziv]] and [[Abraham Lempel]] published a pair of papers on a new class of lossless data-compression algorithms, now collectively referred to as [[LZ77 and LZ78]]. In 1983, [[Terry Welch]] developed a fast variant of LZ78 which was named [[Lempel–Ziv–Welch]] (LZW).<ref name="PNG">{{cite web
 |url=http://www.libpng.org/pub/png/pnghist.html
 |title=History of the Portable Network Graphics (PNG) Format
 |author=Greg Roelofs
 |access-date=23 March 2012
 |archive-date=7 March 2012
 |archive-url=https://web.archive.org/web/20120307042624/http://www.libpng.org/pub/png/pnghist.html
 |url-status=live
 }}</ref><ref name="KYZ">{{cite web
 |url=http://www.kyzer.me.uk/essays/giflzw/
 |title=Sad day... GIF patent dead at 20
 |author=Stuart Caie
 |access-date=23 March 2012
 |archive-date=10 February 2012
 |archive-url=https://web.archive.org/web/20120210060008/http://www.kyzer.me.uk/essays/giflzw/
 |url-status=live
 }}</ref>

Welch filed a patent application for the LZW method in June 1983. The resulting patent, US4558302,<ref>{{Cite patent|country=US|number=4558302|inventor-last=Welch|inventor-first=Terry A.|assign=[[Sperry Corp.]]|pubdate=1985-12-10|inventor1-link=Terry_Welch}}</ref> granted in December 1985, was assigned to [[Sperry Corporation]] who subsequently merged with [[Burroughs Corporation]] in 1986 and formed [[Unisys]].<ref name="PNG" /> Further patents were obtained in the United Kingdom, France, Germany, Italy, Japan and Canada.

In addition to the above patents, Welch's 1983 patent also includes citations to several other patents that influenced it, including:
* two 1980 Japanese patents from [[NEC]]'s Jun Kanatsu,<ref>{{cite patent
| country	= JP
| number	= S5719857A
| status	= patent
| title		= Data compression storage device
| pubdate	= 1982-02-02
| fdate		= 1980-07-09
| inventor1-last	= Kanatsu
| inventor1-first	= Jiyun
| assign1	= [[Nippon Electric Corporation|Nippon Electric Corp.]]
}}</ref><ref>{{cite patent
| country	= JP
| number	= S57101937A
| status	= patent
| title		= Data storage device
| pubdate	= 1986-20-24
| fdate		= 1980-12-16
| inventor1-last	= Kanatsu
| inventor1-first	= Jiyun
| assign1	= [[Nippon Electric Corporation|Nippon Electric Corp.]]
}}</ref>
* {{US patent|4021782}} (1974) from John S. Hoerning,
* {{US patent|4366551}} (1977) from Klaus E. Holtz, and
* a 1981 German patent from Karl Eckhart Heinz.<ref>{{cite patent
| country	= DE
| number	= 3118676
| status	= patent
| title		= Verfahren zur Kompression redundanter Folgen serieller Datenelemente [Method for compressing redundant sequences of serial data elements]
| pubdate	= 1982-12-02
| fdate		= 1981-05-12
| inventor1-last	= Eckhart
| inventor1-first	= Heinz Karl
}}</ref><ref>{{US patent|4558302}}</ref>

In June 1984, an article by Welch was published in the [[IEEE]] magazine which publicly described the LZW technique for the first time.<ref name="cloanto">{{cite web|url=https://mike.pub/19950127-gif-lzw|title=The GIF Controversy: A Software Developer's Perspective|date=27 January 1995 |access-date=26 May 2015|archive-date=23 August 2016|archive-url=https://web.archive.org/web/20160823024419/https://mike.pub/19950127-gif-lzw|url-status=live}}</ref> LZW became a popular data compression technique and, when the patent was granted, Unisys entered into licensing agreements with over a hundred companies.<ref name="PNG" /><ref name="LPF">{{cite web|url=https://www.thefreelibrary.com/UNISYS+CLARIFIES+POLICY+REGARDING+PATENT+USE+IN+ON-LINE+SERVICE+...-a016000999 |title=Unisys Clarifies Policy Regarding Patent Use in On-Line Service Offerings |archive-url=https://web.archive.org/web/20070207110047/http://lpf.ai.mit.edu/Patents/Gif/unisys.html|archive-date=7 February 2007}} – archived by [[League for Programming Freedom]]</ref>

The popularity of LZW led [[CompuServe]] to choose it as the compression technique for their version of GIF, developed in 1987. At the time, CompuServe was not aware of the patent.<ref name="PNG" /> Unisys became aware that the version of GIF used the LZW compression technique and entered into licensing negotiations with CompuServe in January 1993. The subsequent agreement was announced on 24 December 1994.<ref name="KYZ" /> Unisys stated that they expected all major commercial on-line information services companies employing the LZW patent to license the technology from Unisys at a reasonable rate, but that they would not require licensing, or fees to be paid, for non-commercial, non-profit GIF-based applications, including those for use on the on-line services.<ref name="LPF" />

Following this announcement, there was widespread condemnation of CompuServe and Unisys, and many software developers threatened to stop using GIF. The [[Portable Network Graphics|PNG format]] (see below) was developed in 1995 as an intended replacement.<ref name="PNG" /><ref name="KYZ" /><ref name="cloanto" /> However, obtaining support from the makers of Web browsers and other software for the PNG format proved difficult and it was not possible to replace GIF, although PNG has gradually increased in popularity.<ref name="PNG" /> Therefore, GIF variations without LZW compression were developed. For instance the libungif library, based on [[Eric S. Raymond]]'s giflib, allows creation of GIFs that followed the data format but avoided the compression features, thus avoiding use of the Unisys LZW patent.<ref>{{cite web|url=https://directory.fsf.org/wiki/Libungif|title=Libungif|access-date=26 May 2015|archive-date=13 April 2015|archive-url=https://web.archive.org/web/20150413095700/http://directory.fsf.org/wiki/Libungif|url-status=live}}</ref> A 2001 ''[[Dr. Dobb's Journal|Dr. Dobb's]]'' article described a way to achieve LZW-compatible encoding without infringing on its patents.<ref>{{cite web |url=http://www.drdobbs.com/architecture-and-design/replacing-a-dictionary-with-a-square-roo/184404817 |title=Replacing a Dictionary with a Square Root |work=[[Dr. Dobb's Journal]] |first=Tom |last=Cargill |date=2001-10-01 |access-date=2017-01-20 |archive-date=28 June 2017 |archive-url=https://web.archive.org/web/20170628173622/http://www.drdobbs.com/architecture-and-design/replacing-a-dictionary-with-a-square-roo/184404817 |url-status=live }}</ref>

In August 1999, Unisys changed the details of their licensing practice, announcing the option for owners of certain non-commercial and private websites to obtain licenses on payment of a one-time license fee of $5000 or $7500.<ref name="Unisys">{{cite web|url=http://www.unisys.com/about__unisys/lzw/lzw__license__english.htm |title=LZW Software and Patent Information |access-date=2007-01-31 |url-status=dead |archive-url=https://web.archive.org/web/20090608194513/http://www.unisys.com/about__unisys/lzw/lzw__license__english.htm |archive-date=8 June 2009 }} – clarification of 2 September 1999</ref> Such licenses were not required for website owners or other GIF users who had used licensed software to generate GIFs. Nevertheless, Unisys was subjected to thousands of online attacks and abusive emails from users believing that they were going to be charged $5000 or sued for using GIFs on their websites.<ref name="slashdot">[https://slashdot.org/story/99/08/31/0143246/unisys-not-suing-most-webmasters-for-using-gifs Unisys Not Suing (most) Webmasters for Using GIFs] {{Webarchive|url=https://web.archive.org/web/20170510024223/https://slashdot.org/story/99/08/31/0143246/unisys-not-suing-most-webmasters-for-using-gifs |date=10 May 2017 }} – [[Slashdot]] investigation into the controversy</ref> Despite giving free licenses to hundreds of non-profit organizations, schools and governments, Unisys was completely unable to generate any good publicity and continued to be condemned by individuals and organizations such as the [[League for Programming Freedom]] who started the "Burn All GIFs" campaign in 1999.<ref>{{cite web|archive-url=https://web.archive.org/web/19991013083423/http://burnallgifs.org/ |archive-date=1999-10-13 |url=http://burnallgifs.org/ |title=Burn All GIFs Day}}</ref><ref name="burn">[http://burnallgifs.org/archives/ Burn All GIFs] {{Webarchive|url=https://web.archive.org/web/20070203044403/http://burnallgifs.org/archives/ |date=3 February 2007 }} – A project of the League for Programming Freedom (latest version)</ref>

The United States LZW patent expired on 20 June 2003.<ref name="Unisys2"/> The counterpart patents in the United Kingdom, France, Germany and Italy expired on 18 June 2004, the Japanese patents expired on 20 June 2004, and the Canadian patent expired on 7 July 2004.<ref name="Unisys2">{{cite web|url=http://www.unisys.com/about__unisys/lzw |title=License Information on GIF and Other LZW-based Technologies |access-date=2005-04-26 |url-status=dead |archive-url=https://web.archive.org/web/20090602212118/http://www.unisys.com/about__unisys/lzw |archive-date=2 June 2009 }}</ref> Consequently, while Unisys has further patents and patent applications relating to improvements to the LZW technique,<ref name="Unisys2" /> LZW itself (and consequently GIF) have been free to use since July 2004.<ref>{{cite web |url=https://www.gnu.org/philosophy/gif.html |title=Why There Are No GIF Files on GNU Web Pages |publisher=Free Software Foundation |access-date=19 May 2012 |archive-date=19 May 2012 |archive-url=https://web.archive.org/web/20120519232602/http://www.gnu.org/philosophy/gif.html |url-status=live }}</ref>