Daily Archives:October 1st, 2006

LZW: Don’t it feel good when a patent dies?

LZW stands for Lempel-Ziv Welch, and is the name of a very elegant compression algorithm suitable for a variety of applications, but it is best known for being the foundation of the GIF image format created by CompuServe.

GIF images were in very wide use in the early days of the web; it was a good way to compress images such as logos that need to have sharp edges. (This is as compared to photo-type pictures, which need a lot more colours, but still look good if you sacrifice some sharpness – that’s roughly how JPEG works.) However, for all their elegance, efficiency, and former widespread use, images with a .gif suffix are rather seldom seen today? Why?

Both GIF and LZW received a lot of bad press over the last decade after the emergence of some relevant software patents owned by Unisys and IBM. In the second half of the 90s, Unisys started threatening to prosecute websites and application vendors that used the GIF format, which resulted in a lot of bad publicity for them and the gradual transition of most of the world’s websites to the new, open, PNG format which has taken its place today. Purveyors of closed, proprietary standards beware!

A company called Forgent tried to pull the same trick in 2002, claiming a patent on JPEG images. The patent was declared invalid in 2006, but not before Forgent had collected $90M in licensing fees, according to Wikipedia. I wonder if they had to give any of that back? The sad thing is that such legal action can often be rather profitable, even if you lose in the end.

Three years ago I pointed out the rather distressing effect on SCO’s share price when it started claiming ownership of parts of Linux in early ’03. The claims have been rebutted one after another as SCO failed to produce any convincing evidence, and the share price has now fallen back to where it was when the whole thing started.

SCO share price

I enjoyed the latest developments in SCO’s attempt to sue IBM for $5bn, as reported by Dow Jones Newswire:

Wells ruled in June that SCO had “willfully failed to comply” with court orders to show IBM which of millions of lines of computer code in Linux were supposedly misappropriated.

SCO argued that was IBM’s job, a stance Wells likened to a security guard who accuses a shopper of stealing merchandise and demanding the shopper show proof of the theft.

The case remains scheduled for a February 2007 trial, but the ruling by Wells gutted SCO’s case.

So SCO managed to keep alive for a while on the back of this, but everybody now thinks of them primarily as a litigation company, not as a software company, and no techie worth his salt would ever want to work there now, which must spell doom in the long term.

But, anyway, back to LZW. The GIF format is nearly dead, and long live PNG, which has quite a few technical advantages in addition to giving its users freedom from litigation. Unisys’s actions not only damaged their brand, but spurred the rapid development of a superior replacement over which they had no control. And now, at long last, the patents have finally all expired – hurrah! – which means that, GIFs or no GIFs, the LZW algorithm can be restored to its rightful place as a rather useful implement in the Computer Science toolbox.

Thanks to E-Scribe news for the reminder.

© Copyright Quentin Stafford-Fraser