PNG was written in nine weeks by angry people
PNG is almost always told as a technical improvement on GIF: more than 256 colors, per-channel alpha transparency, noticeably better compression. All of that is true, and all of it is the consequence rather than the cause. The format was designed in a little over two months, starting on January 4, 1995, by an informal group that came together on Usenet, for a reason with nothing technical about it: six days earlier, writing software able to produce GIF files had become a royalty-bearing act. The format was seven years old, and nobody, at CompuServe or anywhere else, had checked who owned the compression algorithm sitting at the center of the specification.
A published algorithm, a filed patent
The story starts with two papers by Jacob Ziv and Abraham Lempel in the IEEE Transactions on Information Theory: "A universal algorithm for sequential data compression," vol. 23, no. 3, May 1977, pp. 337 to 343, then "Compression of individual sequences via variable-rate coding," vol. 24, no. 5, September 1978, pp. 530 to 536. Both families, LZ77 and LZ78, are public.
Terry A. Welch, an engineer at Sperry Corporation, draws a fast variant of LZ78 out of them. He files patent application US 06/505,638 on June 20, 1983. The following year he describes his method in a widely circulated magazine: "A Technique for High-Performance Data Compression," Computer, vol. 17, no. 6, June 1984, pp. 8 to 19. Patent US 4,558,302, "High speed data compression and decompression apparatus and method," is granted on December 10, 1985 in the name of Sperry Corp. Sperry then merges with Burroughs to form Unisys.
A neighboring method is the subject of a second patent, filed by two IBM researchers, Victor S. Miller and Mark N. Wegman: US 4,814,746, "Data compression method," granted on March 21, 1989 and tied back to an original application of June 1, 1983, nineteen days before Welch's. Two titles over one family of ideas: getting around one was no guarantee of escaping the other.
Meanwhile, on June 15, 1987, CompuServe publishes the Graphics Interchange Format specification. The document carries a sentence every developer of the day reads as permission: "While this document is copyrighted, the information contained within is made available for use in computer software without royalties, or licensing restrictions." Tim Oren, CompuServe's vice president for Future Technology, would later explain the reasoning: "The LZW algorithm was incorporated from an open publication, and without knowledge that Unisys was pursuing a patent." The algorithm had been found in a journal, which has never meant free of rights.
December 29, 1994
Unisys puts CompuServe on notice in January 1993. The two companies negotiate for a year and a half and sign an agreement dated June 21, 1994, cited as clause 10.1 of the contract that follows. According to the Unisys public statement, CompuServe pays it 1 percent of the average selling price of its software, "approximately 11 cents for each copy sold and connected to its information service," and has six months to put the agreement into effect, a deadline extended by one month at its own request.
CompuServe dates its announcement to developers December 29, 1994, between Christmas and New Year (some accounts hold to the 28th). The terms offered to them are not the ones CompuServe obtained: 1 dollar to sign up, then, per registered copy, the greater of 1.5 percent of the selling price and 0.15 dollar, paid to CompuServe. Registration before January 31, 1995, in exchange for which Unisys waives any royalty claim on past use.
The detail that lights the fuse is not the price, it is the scope. Clause 11.2 defines the "Field of Use" as software "used by subscribers to the CompuServe Information Service to access the CompuServe Information Service." Clause 1.5 forbids the developer from delivering the product to any customer who does not undertake to use it primarily to reach CompuServe. Clause 10.7 forbids disclosing the terms of the contract. The contract finally requires a legal notice on the product or in its documentation, in which the patent holder's name is misspelled: "LZW compression and decompression methods are licensed under Unysis Corporation's U.S. Patent 4,558,302 and equivalent foreign patents." In the text that circulated, the typo comes back eight times, against three correct spellings.
The League for Programming Freedom sums the situation up in one sentence: "It turns out that the license being offered today is only for Compuserve users." A developer writing a GIF encoder for the web rather than for CompuServe has nothing to sign. He has no license either.
Nine weeks on a mailing list
On January 4, 1995, Thomas Boutell posts to comp.graphics, comp.compression and comp.infosystems.www.providers a draft format he calls PBF, for Portable Bitmap Format. A three-byte signature, chunk numbers rather than names, 8 bits of maximum depth, no compression method settled.
What follows reads like standards work run through a compressor. That same day: delta filtering proposed by Scott Elliott and Mark Adler, deflate compression by Tom Lane and the Info-ZIP team, 24-bit support. On January 6, Oliver Fromme proposes the name PNG. On January 7, draft 2, internal CRCs, and Greg Roelofs publishes a test result: simply swapping GIF's LZW for deflate improves compression by 10 percent. On January 8, a gamma chunk from Paul Haeberli, 48- and 64-bit support from Jonathan Shekter. On January 10, Jeremy Wohl sets up the first mailing list.
CompuServe announces an in-house project on January 16, GIF24. Draft 5, on January 23, adopts the name PNG. Adam Costello proposes his Adam7 interlacing scheme on February 2. On February 7, CompuServe comes around and presents PNG as the designated successor to GIF, in place of its own GIF24. Draft 9 ships on March 7, 1995 and the specification is frozen, a little over two months after the first message: the later drafts bring nothing but clarifications. The reference libraries follow on May 1, 1995, zlib 0.9 from Jean-loup Gailly and Mark Adler, pnglib 0.6 from Guy Eric Schalnat.
Standardization takes longer than the design. Version 0.92 as a W3C Working Draft on December 8, 1995, W3C recommendation on October 1, 1996, image/png media type registered by IANA on October 14, 1996, publication as informational RFC 2083, dated March 1997. The RFC abstract does not hide the motive: "PNG provides a patent-free replacement for GIF". The same document notes, in its introduction, that the name is pronounced "ping".
Unisys rewrites its own press releases
The Unisys release of January 1995 contained an exemption: "Unisys does not require licensing, or fees to be paid, for non-commercial, non-profit GIF-based applications," explicitly extended to Internet offerings "including 'Freeware'". By the end of the summer of 1996, those passages had vanished from the Unisys site, replaced by a text that justifies the change: "As a result of both this extensive licensing and changes in the use and marketing of GIF and other LZW-based products, Unisys has had to adjust its licensing policies to reflect these changes and the needs of existing and future licensees."
In 1999 the company offers the operators of sites whose images were produced with unlicensed software a flat license at 5,000 dollars, and its stated position leaves no exemption at all: "In all cases, a written license agreement or statement signed by an authorized Unisys representative is required from Unisys for all use, sale or distribution of any software (including so-called "freeware") and/or hardware providing LZW conversion capability." Slashdot runs the headline "Unisys Not Suing (most) Webmasters for Using GIFs" on August 31, 1999, where Mark Starr, General Patent and Technology Counsel at Unisys, lays down the rule: "if the GIFs on your Web site were created with software that is licensed by Unisys, you are fine."
The pushback takes a physical form. On Friday, November 5, 1999, the League for Programming Freedom organizes Burn All GIFs Day. Developers gather outside the Unisys offices in California, the watchword being to burn paper printouts of GIF files, and the trade press describes the operation the same day; the photographs of actual flames the organizers later passed around come from a Canadian gathering instead. Mark Starr would sum the affair up in The Industry Standard of April 25, 2000: "They want everything to be free and let's all be friends. But fortunately, this is not the American way."
The American patent expires on June 20, 2003. The European counterparts fall on June 18, 2004, the Japanese one on June 20, 2004, the Canadian one on July 7, 2004. The IBM patent runs longer: USPTO data relayed by Google Patents puts its expiry at March 21, 2006.
Why GIF outlived its own patent
PNG won the still image and lost the rest, for a reason written into its own specification. Section 12.3 of RFC 2083: "PNG also does not support multiple images in one file. This restriction is a reflection of the reality that many applications do not need and will not support multiple images per file." The choice is deliberate, section 8.4 sending any eventual multi-image format off to a separate specification, with a different signature.
That is precisely the moment browsers start animating GIFs. The capability had lain dormant in the GIF89a specification since 1989; Netscape Navigator 2.0, whose first beta ships in September 1995, is the first to loop those images, and the others follow. The format that was supposed to die gains a use its replacement had ruled out on principle, and that use earns it a second life on the web of the late 1990s. The promised multi-image format, MNG, only reaches version 1.0 in January 2001 and is picked up by no more than a handful of applications; APNG, its successor, written at Mozilla in 2004 and rejected by the PNG group in 2007, is not read by Chrome until 2017.
The result is a double survival. PNG became the default format for everything that does not move, and GIF carried on with its career on the one patch of ground RFC 2083 had left it. When the patent expired in 2003, the legal cause dropped out of the story and only the effect remained: a technically superior format, and nobody remembers it was written in nine weeks by people who were furious.