Sad day... GIF patent dead at 20

I just heard some sad news on talk radio - GIF patent US4,558,302 was found expired in its patent office filing cabinet this morning. There weren't any more details. I'm sure everyone in the internet community will miss it - even if you didn't enjoy the litigation, there's no denying its contribution to bandwidth conservation. Truly a compression icon.

On Friday, 20th June 2003, the death knell sounded for US patent number 4,558,302. Having benefitted the Unisys Corporation for twenty years, the contents of the patent are entered into the Public Domain and may be used absolutely freely by anyone.

Officially titled "High speed data compression and decompression apparatus and method", it is more commonly known as the LZW patent or "Unisys's GIF tax". Unlike most patents, the LZW patent has been the subject of much controversy during its lifetime. This is because thousands of software developers, with millions of users, were unintentionally infringing on the patent and the patent holder neglected to tell them for seven years.

History

A time line of the GIF/LZW patent saga runs like so:

  • May 1977: [LZ77] published. The paper uses maths notation heavily and is unreadable to most people, but generally the technique works by looking entire repeated "strings" of data, and replacing the repeats with a much shorter pointer back to the original. Many compression algorithms build on this technique and most archivers (e.g. ZIP, ZOO, ARC, gzip, LhA, CAB, Arj, RAR, StuffIt) include it in their compression methods. It works by maintaining a sliding window over the data to be compressed, and continually searches for repeats within that window as it works forward through the uncompressed data. This is not the same as LZ78 or LZW, but many people confuse it as such.
  • September 1978: [LZ78] published. This technique is markedly different to LZ77; it maintains a dictionary of strings rather than a sliding window. Unlike LZ77, this technique is unpopular. An implementation of the algorithm at Sperry Research Center was patented by the inventors, including Lempel and Ziv: patent US4,464,650. However, the derivative of LZ78 called LZW is popular, for reasons that will soon be clear.
  • 20th June 1983: LZW patent filed. Terry Welch, working for the Sperry Research Center, invents a derivative of LZ78 with much simplified, faster dictionary handling. He calls it LZW, after the names of the inventors, Lempel-Ziv-Welch.
  • June 1984: Terry Welch's article A Technique for High-Performance Data Compression appears in IEEE Computer magazine. It is this article more than anything else that has made LZW a popular data compression algorithm. The article is very well written, far more readily understandable than the math-laden monstrosities of [LZ77] and [LZ78]. The article includes a justification for data compression, an overview of common methods, and a detailed explanation and run-through of the LZW algorithm. At no point does the article mention LZW's pending patent application! It does state that Sperry's LZW implementation is "proprietary", however it also gives all the details and pseudo-code required for the reader to implement their own LZW compressor and decompressor. A magazine reader might easily make the mistake of thinking the algorithm was freely usable.
  • 5th July 1984: UNIX compress version 1.2 is released by Spencer Thomas, after the LZW article was published but before LZW was patented. Like many IEEE Computer readers, Spencer decided to implement the LZW algorithm he read in the magazine, completely unaware that there was a patent pending on the technique. compress later replaced pack as the de-facto UNIX compression tool, usually used in conjunction with tar or shar archives. It remained the standard UNIX compressor until gzip replaced it. compress is still included in proprietary Unices to this day.
  • 10th December 1985: The US Patent Office grants US patent number 4,558,302, the Sperry Corporation's infamous LZW patent.
  • 11th August 1986: The US Patent Office accidentally grants another LZW patent, this time to IBM, due to patent examiners not realising that the Sperry and IBM applications claimed for exclusive 17 year rights on the same algorithm. For their part, IBM has not made use of the patent publicly, probably out of fear of having it invalidated and revoked by Sperry.
  • September 1986: The Sperry Corporation (owners of the Sperry Research Center) and the Burroughs Corporation merge to form Unisys.
  • 15th June 1987: Bob Berry and the graphics development team at CompuServe release a new graphics file format called GIF (Graphics Interchange Format). It can handle anything from 2 to 256 colours and the graphics data is compressed with LZW. Just like Spencer Thomas, CompuServe engineers had read the LZW algorithm in a magazine and had wrongly assumed that it wasn't patented. Unisys does nothing to correct this wrong assumption.
  • 1988: Unisys does nothing about GIF. The GIF format becomes more popular.
  • 1989: Unisys does nothing about GIF, but they do arrange LZW licensing for various hardware manufacturers -- for example, V.42bis modem manufacturers, as the V.42bis standard calls for BTLZ compression, which infringes on some of the LZW patent's claims despite not being exactly LZW. Also, PostScript printer manufacturers are licensed, due to them implementing the LZWEncode feature of the PostScript language. Raymond Gardner tries to bring up the LZW patent issue in public after Mark Nelson writes a tutorial on LZW compression in Dr Dobb's Journal, and the LZW patent becomes generally known, but nobody seems to have linked LZW to GIF yet. The GIF format, naturally, becomes more popular.
  • 1990: Unisys says nothing. The GIF format becomes popular. Adobe pay to license LZW in their Postscript language, but not for their GIF saver in Photoshop.
  • 1991: Unisys says nothing. The GIF format becomes more popular. Aldus (now owned by Adobe) pays to license LZW in their TIFF file format.
  • 1992: Unisys says nothing. The GIF format becomes more popular.
  • 1993: Unisys says nothing. The GIF format becomes more popular.
  • 1994: Unisys says ... no, wait, on 24th December 1994, Unisys and CompuServe jointly announce that any developers writing software that creates or reads the GIF file format will all have to license the LZW patent from Unisys! After returning from their Christmas festivities, developers and users alike go ballistic on electronic bulletin boards around the world. It's a GIF tax! Burn all GIFs!
You can get a similar chronology from lzw.info or burnallgifs.org.

Who's to blame?

There are no easy answers to this.

Should the algorithm have been patented? Even though groups like the League for Programming Freedom believe that it should be impossible to patent algorithms, the fact remains that the LZW algorithm was implemented in disk controller hardware. It could just have easily been claimed as part of the hardware and would have had the same level of protection.

Should the algorithm have been publicised by Terry Welch, despite knowing that it was patent pending? Looking back, this is the root cause of the controversy, but at the time it occurred, it would be nothing more than a minor oversight. Terry Welch is not a patent lawyer, he is an engineer, and thus is unlikely to consider the legal gravity of the situation.

Should Unisys be blamed for not publicising the patent? To an extent, yes, but they are under no obligation to do so. They can also pick and choose when to enforce their patent, with no penalties for non-enforcement other than the doctrine of laches. It seems that the reason Unisys did nothing about GIF until 1994 is because Unisys itself did not know about GIF's LZW use until 1994. The world was a lot less "wired" in 1994, a Unisys lawyer couldn't enter "LZW" into the Google search engine and come up with thousands of infringers in a single stroke. Unisys had, in fact, been licensing big LZW infringers that it discovered in its own field of work.

In my opinion, the biggest error committed was the incredible complacency of the BBS and Internet community in allowing the GIF controversy to continue from 1994 to the present day. The dawn of 1995 saw GIF's official successor created -- PNG. Before the year was out, PNG was a well-defined standard, ready to be integrated into graphics viewers and -- most importantly -- the Web Browser.

The Web Browser in 1995 and 1996 was Netscape. Microsoft have played dirty tricks and the Web Browser is now Internet Explorer. Both browsers have an abysmal track record at implementing PNG support. Their excuse is that "webmasters don't use it. We're not sticking our necks out to support a format that nobody uses". Webmasters say "the browsers don't implement it. We're not sticking our necks out to support a format our visitors can't see.". A chicken and egg scenario. Even making PNG a W3C standard hasn't helped its adoption. People are simply too lazy to change, and they don't care for the illegality of unlicensed GIF creators and decoders. The persistent threat of expensive litigation just for having GIF images on your website hasn't diminished GIF's popularity in the slightest. What happened to the rallying cry of "BURN ALL GIFS"? It has been forgotten.

Eight more patents to go

So, Unisys's US patent on LZW has expired. What does this leave?
  • The European patent EP0,129,439 covers four territories: Germany, France, Britain and Italy. It expires on the 18th June 2004.
  • The Canadian patent CA1,223,965 expires on the 6th June 2004.
  • The Japanese patents 2,123,602 and 2,610,084 expire on the 20th June 2004.
  • IBM's LZW patent expires on 11th August 2006. However, IBM are unlikely to use it, knowing full well that it is invalid.

This creates an interesting legal situation where LZW-based software is legal to distribute in the United States, but risks patent infringement claims in or when exported to Europe, Canada and Japan.

Conclusion

I wish Unisys a happy year squeezing the very last drops out of their monopoly. In the meantime, I encourage Microsoft to support PNGs properly and everyone else to make the switch from GIF to PNG.

Further information

References

An earlier version of this article appeared at Kuro5hin.org.

© 2000-2023 Stuart Caie. Email kyzer@kyzer.me.uk

Last updated: Monday, 13 September 2010