In association with heise online

10 April 2012, 11:10

What one line of code can teach us

by Glyn Moody

Glyn Moody looks at an example of how a patent on one line of code can inhibit innovation for a generation and how that lesson should not be forgotten when the government is asking what an open standard is.

Light Blue Touchpaper is a blog written by researchers in the Security Group at the University of Cambridge Computer Laboratory (don't miss the explanation of the blog's rather witty name). It's normally full of deep stuff about computer security and vulnerabilities, and is well worth reading for that reason.

But Markus Kuhn recently posted an excellent but rather different piece there about software patents:

I have been waiting for this day for 17 years! Today, United States Patent 5,404,140 titled “Coding system” owned by Mitsubishi expires, 22 years after it was filed in Japan.

Why the excitement? Well, 17 years ago, I wrote JBIG-KIT, a free and open-source implementation of JBIG1, the image compression algorithm used in all modern fax machines. My software is about 4000 lines of code long (in C), and only one single “if” statement in it is covered by the above patent:

if (s->a < lsz) { s->c += s->a; s->a = lsz; }

And sadly, there was no way to implement a JBIG1 encoder or decoder without using this patented line of code (in some form) while remaining compatible with all other JBIG1 implementations out there.

What's rather remarkable is that this single line of code raises several important issues for open source.

The first, as you might guess, is how something so trivial was granted a patent in the first place. As Kuhn explains:

JBIG1 uses an arithmetic coder that estimates the probability that the next pixel to be encoded is either black or white (taking into account 10 previously transmitted neighbour pixels). Arguably in the interest of saving a bit of RAM in hardware implementations, the standard does not use the simple arithmetic expression that estimates these pixel probabilities based on counts of how often a pixel has been black or white before in that context: p(next pixel is white) = (#white pixel so far + 1) / (#pixels so far + 1). Instead, it defines a finite-state machine that comes up with a cruder estimate, using just 7 bits to define 113 states, rather than actually counting pixels with 32-bit registers. IBM had a patent on that finite-state machine, which is really hardly more than an obfuscated counter. Then a Mitsubishi employee noticed that the crude IBM approximation sometimes ended up assigning to the “less probable pixel colour” a probability larger than 0.5, making it actually more probable. So they suggested the above if-statement to swap the probability estimates of the two colours in those rare cases, leading to a tiny improvement in coding efficiency.

So we have the IBM patent on the technique of using the past as an indication of the future – in this case, the past being the previous pixels in the fax image. Now, last time I looked such inductive approaches formed the basis of most of science, so it seems pretty extraordinary that it was deemed worthy of a patent, even if – or perhaps especially if – it's dressed up with a bit of maths.

Next, we have Mitsubishi's patent, which is actually just an observation about IBM's patent. It represents zero creativity whatsoever – it's effectively just fixing a bug in what Kuhn rightly calls the original "crude IBM approximation".

All-in-all, then, the IBM and Mitsubishi patents represent all that is worst in the US patent system: trivial, obvious and based on pure mathematical knowledge. But as Kuhn observes, the standards community at the time managed to turn what would otherwise have been just a minor annoyance into a full-blown disaster:

The standardization of file formats and computer protocols turned in the late 1980s into a very nasty game: every participant is now mainly interested in squeezing as many of their patented ideas into the resulting standard as possible. The JBIG1 standard is a good example of a technology that could have been made much simpler and a bit more efficient if the authors hadn’t had to justify to their employers the time spent on developing the standard with the prospect that users of the standard would have to pay licence fees.

It's basically a sick and twisted system that ends up doing the opposite of what it claims. Instead of promoting progress, it holds it back. As Kuhn points out, he – or anyone – could have come up with a better solution than JBIG1, improving the basic standard for fax machines. But once Mitsubishi's patent was enshrined in that standard, nobody could do a thing, because it would have broken interoperability. That may be a bug for users, but for the computer companies, it's a feature:

About 25 years ago, large IT research organizations discovered standards as a gold mine, a vehicle to force users to buy patent licenses, not because the technology is any good, but because it is required for compatibility. This is achieved by writing the standards very carefully such that there is no way to come up with a compatible implementation that does not require a patent license, an art that has been greatly perfected since.

Sadly, this is not purely of historical interest. There is currently a huge battle for the soul of the British government under way that is all about standards and patents. The outcome of that tussle will have big implications for open source.

Next: What this means for open standards now

Print Version | Permalink:
  • Twitter
  • Facebook
  • submit to slashdot
  • StumbleUpon
  • submit to reddit

  • July's Community Calendar

The H Open

The H Security

The H Developer

The H Internet Toolkit