Patent Ruling Against Microsoft Hinges on Meaning of Custom XML

By Jeff Cogswell  |  Posted 2009-08-14

Patent Ruling Against Microsoft Hinges on Meaning of Custom XML

A Federal judge in Texas handed down a ruling Aug. 11 barring Microsoft from continuing to sell and support its Microsoft Word software on the grounds that it violates a patent owned by a company called i4i. But the ruling has some odd things in it that have already caused a good bit of debate on blog and news sites. Here's one part of the ruling:

Microsoft Corporation is hereby permanently enjoined from ... selling, offering to sell ... any Infringing and Future Word Products that have the capability of opening a .XML, .DOCX, or .DOCM file ("an XML file") containing custom XML.

The odd wording here is "custom XML," which appears several times in the ruling. Based on the comments in response to eWEEK's articles on the ruling, as well as comments I've seen elsewhere, a great deal of people think the problem was that Microsoft uses XML as its format. But that isn't the case. The ruling focuses on the use of custom XML. The ruling is not about the fact that Word uses XML. If it did, there would be a worldwide disaster, considering how prevalent XML is.

But what exactly is custom XML? To start with, let's look at the claims of the patent itself and try to make a connection. The patent, which was written back in 1994, covers a new way of providing formatting in a word processing program. To understand the claims of the patent, it's important to note the distinction between what the inventors call content and what are called metacodes (which are ultimately formatting codes).

Deciphering the Lawsuit Claims

Consider the following sentence, which has some parts bold, some parts italics, and some parts normal text:

The quick brown fox jumped over the lazy dogs.

The content is the sentence itself without any formatting. Here's the content, which has no formatting:

The quick brown fox jumped over the lazy dogs.

When formatting is included, the word processing program can use different means to store the formatting information. The patent notes that a common way of storing such formatting is by placing the formatting right inside the sentence. For example, one might store it as HTML like this:

 The <b>quick</b> brown fox jumped <i>over</i> the lazy dogs.

The formatting code <b> means "turn on bold" while </b> means "turn off bold." Similarly with <i> and </i> for italics. This text with the formatting codes could be stored in a file and then read character-by-character from left to right by a word processing program. The software would display it on a screen, not with the formatting codes, but instead with the formatting actually applied:

 The quick brown fox jumped over the lazy dogs.

So what is claimed in the patent? The patent is long and makes 20 claims and provides some step-by-step algorithms for processing such text and for processing the formatting codes (or metacodes). Ultimately the algorithms create a data structure called a metacode map, which contains information about where in the text formatting is applied. The end result is two separate data structures: the metacode map with formatting information, and the plain text with no formatting. The program uses both data structures to display the fully formatted text on the screen.

This is in contrast to the way things were apparently done before the patent; word processors would use metacodes embedded right inside the text (similar to the HTML I showed earlier, but usually using other, earlier, types of codes). The word processor would read in the text character-by-character, turning on and off formatting sequentially as it went along, displaying the text on the screen formatted appropriately (or, in the case of early monitors that couldn't show formatting, displaying codes to denote how parts of the text is formatted).

So far what we're talking about isn't rocket science. But remember, the patent was written back in 1994 (and granted in 1998). This may well have been the first time such technology was seen. The word XML doesn't even appear in the patent, because it didn't exist yet in 1994. Instead, SGML (Standard Generalized Markup Language) is mentioned, which is essentially a precursor to XML.

Now consider Microsoft Word. Prior to Word 2007, the main format for Word documents was a proprietary, secret format that didn't use XML (technically speaking, it was a binary format). With Word 2003 came additional XML capabilities; with Word 2007 came the Open XML format, which stores the documents in a single .zip file that contains several files including images that might be embedded in your document, as well as all your text, which is all XML. Is this in violation of the patent? To try to answer this, I want to now figure out what "custom XML" means.

What is Custom XML?

Consider HTML. It has a well-defined set of tags (such as <i> and <b> and so on). If somebody were to write a software package that allowed for additional tags, then such additional tags could be construed as "custom" tags. XML, however, doesn't have a pre-defined set of tags. You can use any tags you want, and it's up to the software you're using (or creating) to handle the tags appropriately. Some people have argued that as such, all XML is "custom" and therefore the phrase in the judge's ruling-custom XML-is redundant at best, ridiculous at worst.

But there are two more possibilities for what it means. Microsoft's MSDN documentation and the Open XML specification both talk about Custom XML in two separate ways. First, there's an XML tag called customXML whereby you, the tech-savvy user, can embed your own XML in a Word document that goes beyond the XML already used by Word. To do this, you use a part of the Word GUI that you can get to through the Developer tool bar on the ribbon in the XML tab. (I found this article online that describes it pretty well.)

The next possibility is how you can include your own XML files right inside the single .zip file making up an Open XML document. Within the MSDN documentation, this is called Custom XML.

So we have three possibilities-the first being a simple redundancy (or absurdity); the second being the customXML tags for attaching XML codes to your text; and the third being Custom XML for adding XML files into the .zip files.

To help figure out which type the judge meant, I found this document, titled "Memorandum Opinion and Order," signed by the judge. (You can find other documents pertaining to the case here.) The document contains many mentions of "custom XML" (and even includes a footnote about whether or not the term is defined elsewhere, even though the document doesn't actually define the term). The document is filled with mentions of custom XML, such as this:

"Microsoft argues that ... custom XML functionality is simply a small part of ... Word ..."

But there's this gem, which provides the biggest clue:

"adding custom XML elements using the XML structure pane of WORD's graphical user interface"

The part about the XML structure pane in Word pretty much tells the story. It is my opinion that the "custom XML" refers to the second possibility, that of new XML tags that can be manipulated from the XML tab of the Developer tool bar. On that tab is a button called Structure, which opens a pane called XML Structure-just what the Memorandum refers to. This is apparently the "custom XML" that the judge was referring to in the permanent injunction.

What the Trial Decision Says

Now we know what custom XML refers to. But wait: The patent was about separating formatting from text. How is that related to custom XML? Inside the patent are mentions of SGML (again, the precursor to XML), along with samples of how some XML-like code could be processed, resulting in a separation of formatting from text.

The Memorandum document says: "At trial, i4i contended that Microsoft's use of certain WORD 2003 and all of WORD 2007 products for processing XML documents with custom XML elements infringed claims 14, 18, and 20 of the '449 patent."

Here are those three claims, taken right from the patent itself:

14. A method for producing a first map of metacodes and their addresses of use in association with mapped content and stored in distinct map storage means, the method comprising:

providing the mapped content to mapped content storage means;

providing a menu of metacodes; and

compiling a map of the metacodes in the distinct storage means, by locating, detecting and addressing the metacodes; and

providing the document as the content of the document and the metacode map of the document.

18. A method as claimed in claim 14 further comprising comparing the multiplicity of metacodes in the map with a predetermined set of criteria.

20. A method for producing from a document made up of metacodes and content, a map of metacodes and their addresses of use in association with mapped content of the document and stored in distinct map storage means, the method comprising:

(a) reading the content of the document until a metacode is found;

(b) copying the content and storing the copied content in a mapped content storage;

(c) noting in the map the found metacode and its position in the content;

(d) repeating the processing of (a)-(c) until the entire document has been processed; and then

(e) providing the document as the content of the document separately from the metacode map of the document.

So clearly, the judge and jury have ruled that the use of custom XML (that is, using the XML Structure pane to add additional XML into a document) is violating the invention of mapping metacodes with text, and so on. But why that particular aspect? Why just the use of the XML Structure pane, when the entire documents are stored in XML?

Here's the kicker: Reading through the decision, it's almost as if both the jury and judge felt that the XML editor portion of Word was the only place where XML was being used (it's not) and that this is where the alleged metacode data structure was being created (doubtful; if there is one, it would be created elsewhere).

The Grounds for an Appeal

The entire document is stored as XML, regardless of whether there's a feature allowing the users of Word to add further XML into a document. And the entire document must be read in by Word and parsed, possibly resulting in the creation of a metacode data structure. So why did the judge and jury focus on this rather superficial aspect?

Did they even understand that the underlying .docx format is a .zip file with all the text encoded in XML, and that the portion of Word where users can add on their own "custom" XML is pretty irrelevant to separating out the content from the formatting?

Did they understand that there's an underlying file format that looks quite different from the document as rendered on the screen? I can't say, but it does make me question whether the jury and judge truly understood the technology; it's almost as if they misunderstood the "custom XML" feature of Word and its XML Structure pane, and thought that that was somehow related to formatting the text in Word. If that's the case, then the jury was clearly misinformed.

But one interesting aspect in the memorandum is that it describes how there was a good bit of debate between the two sides on whether or not Word creates a data structure internally that effectively performs the same work as the metacode map technique described in the patent. The judge, writing in the memorandum, makes it clear that he feels that if the data structure ultimately performs the same task, then the software is in violation due to what he calls the "doctrine of equivalents."

So, does Word create such a structure? Without looking at the source code, there's no way to know. We could guess; we could say it would make sense to create such a structure, but without looking at the actual source code, we cannot know and are only speculating.

If it does create one, then perhaps Word is in violation of the patent-not just the custom XML aspect of Word, but the entire product. But if not, if there's no such separation between the formatting and the text, then Word probably isn't in violation-even with the custom XML feature being present.

But one thing seems clear to me: The custom XML feature is quite irrelevant to the case. Microsoft says it will appeal. An appeal could either hurt or help the company. On appeal, a court may determine that the custom XML aspect is irrelevant as I've claimed here.

Then they could either claim the entire product is in violation (not just the XML Structure pane, which could be removed from future versions), or they could claim the product is not at all in violation. As such, Microsoft has some huge decisions to make on how to move forward, as its entire Word product could be at risk.

Rocket Fuel