Leading items

Another patent battle for Android

In 2011, an auction was held for some 6,000 patents held by Nortel Networks. A consortium named Rockstar — formed by Microsoft, Apple, Sony, EMC, Blackberry (then Research In Motion), and Ericsson — competed in the bidding against Google. Rockstar won the bidding for a staggering $4.5 billion, roughly $750,000 per patent. Google, and its Chief Legal Officer David Drummond, were concerned at the time about those patents being used against Android — something that has now come to pass.

Google chose not to get involved with Rockstar, despite being invited to join the consortium. Drummond explained that the company refused to join because it suspected that the acquisition terms would not have included extending patent licenses to Android and Android manufacturers.

Drummond turned out to be right about what the Nortel patents would be used for. Two weeks ago, Rockstar filed eight lawsuits in the plaintiff-friendly Eastern District of Texas; one against Google, and seven against the major Android OEMs — Samsung, HTC, Huawei, LG, Asus, Pantech, and ZTE — for infringing patents from Nortel.

Although there are eight lawsuits in total, there are effectively only two different legal battlegrounds here. Google faces claims of infringing seven patents that cover an "associative search engine" invention. Six of those are "continuing patents": that is, they are patents that follow on one or more earlier patents in the "series", as improvements to the original invention. The original patent was 6,098,065 (filed in 1997), and the six continuing patents (filed from 1999 to 2007) are: 7,236,969, 7,469,245, 7,672,970, 7,895,178, 7,895,183, and 7,933,883.

These patents are largely very similar, and all claim "an advertisement machine which provides advertisements to a user searching for desired information within a data network". The "base invention" claimed describes an online search engine that provides results by correlating the search string with relevant entries in a database of results, using profile information from the searcher to help provide better results for that user. The continuing patents extend upon this "base", until we get to the last patent, number 7,933,883, which adds: a secondary database of advertisements, which the search string is matched against to provide targeted advertisements; multiple systems for profiling users of the search engine; and using the searcher's profile in combination with their search string to provide targeted advertisements to the searcher along with their search results.

So Rockstar is claiming that Google's AdWords, one of Google's main sources of income, is infringing seven of Rockstar's patents. That's a bold attack: Rockstar has fired missiles at the heart of Google's revenue stream. Given the gravity of the claims, a countersuit from Google against the consortium organizers as a reprisal seems likely.

The lawsuits against the Android OEMs all claim that a different set of patents are infringed by at least some of their respective Android devices. The specific patents claimed are:

• Patent 5,838,551: Filed in 1996, the invention simplifies circuit board design by eliminating the need to connect electromagnetic interference (EMI) shields to boards via solder traces by using instead an electrical connection to a "rigid planar dielectric substrate", such as "a printed circuit board or a ceramic substrate". [Not asserted against Pantech or ZTE.]

• Patent 6,037,937: Filed in 1997, covers an overlay of a "control tool" over content shown on a screen to provide for improved user navigation through a graphical user interface; this is an improvement over the use of hardware buttons or additional devices to conduct the navigation.

• Patent 6,128,298: Filed in 1997: a device that provides internet access to "nodes of private networks"; the device "presents a single IP address to the internet and uses a plurality of IP ports to solve the problem of IP address conservation". This invention could read on network address translation (NAT), like that used in mobile wireless Internet hotspots.

• Patent 6,333,973: Filed in 1997: the invention details an "Integrated message center" which "consolidate[s] [notification] messages of different types for viewing and manipulation by a user". Could be read against Android's notification shade, which centralizes the display of different notifications. [Not asserted against Pantech]

• Patent 6,463,131: Filed in 2000: "a system and method" which allows users to distinguish between different notifications by customizing how they are received. For example, different ring tones could be used to signal different callers, or to distinguish a text from a call. This patent could read on Android notifications.

• Patent 6,765,591: Filed in 1999: a graphical user interface for "managing a virtual private network" (VPN).

• Patent 6,937,572: Filed in 2000: tracing Voice over IP calls, providing one or more different types of trace information, including: IP address, the type of device making the call, and a call-back number.

All of these lawsuits claim willful infringement by the defendants. If proven, that leads to treble damages — a tripling of the final damage award after damages for all other patent infringement claims are calculated. In Rockstar's written claim against Google, it refers to Google's failed efforts to buy the Nortel patents as evidence that Google knew it was infringing these patents and was trying to buy itself a license. This argument is analogous to claiming that people who buy house insurance know that their house is going to burn down.

As Rockstar is a non-practicing patent-holding entity (i.e. a patent troll) — it does not actually make any products — Rockstar is probably more interested in extracting money out of Google and the Android OEMs than in getting an injunction, although claims for injunctions as remedies are included in the lawsuits. The lawsuits against the OEMs are only the latest in a series of efforts over the last few years to use patents against Android device manufacturers for a variety of reasons, from raising the costs of offering products based on open source software to simply extracting money from a booming industry.

We have yet to hear a public statement from the defendants about the Rockstar lawsuit. But we can expect Google and at least some of the OEMs to defend themselves. It is possible that some of the OEMs will settle with Rockstar. However, long and drawn out court battles fighting back against Rockstar, including demands that the patents be reexamined as potentially invalid due to obviousness and/or a lack of novelty in light of prior art, are to be expected. There is also a strong possibility of a countersuit from Google against the most powerful of Rockstar's organizers: Microsoft and Apple.

Patent litigation in the smartphone and mobile device space have been heating up for years, with some dramatic results, like that seen in Apple v. Samsung. But these lawsuits — simultaneously attacking every major Android OEM while also firing directly at Google's main profit stream — are the most audacious seen so far.

Comments (26 posted)

Prototyping with Pencil (the other one)

Earlier this year I was reminded of one of the peculiar joys of free software: the fact that (trademarks aside) anyone can name a project anything they like, even if that project name is already in use. Specifically, when comparing the various parallel forks of the Pencil cell-animation application in June, there were numerous false-positive search engine hits caused by Pencil, the entirely unrelated open source application for making graphical user interface mock-ups. The mock-up tool recently made a new release, so a fresh look at it seems in order.

This "Pencil" is a visual prototyping system. Users can draw simple interface elements onto mock-up screens like one might do with a generic drawing application such as Inkscape, but Pencil goes a few steps further. First, the application ships with several loadable collections of UI elements taken from existing operating systems and platforms. These "stencil" collections (as they are called) include GTK+, Android, iOS, and an assortment of web application frameworks, plus several generic options. Second, Pencil supports linking multiple mock-ups through clickable UI elements, so it is possible to create simple interactive mock-ups rather than mere static images. Finally, the application can export its mock-ups to some interesting output formats, such as linked web pages (again, helpful when creating interactive prototypes).

Version 2.0.5 was released in late September, following on from 2.0.3 in June. Both introduced new features, after a considerable gap since the previous update in 2012. Pencil is based on Mozilla's XUL runtime, and it can be downloaded as a standalone application or installed as a Firefox extension. Linux builds of the standalone version are provided as Ubuntu and Fedora packages as well as a tarball. The Firefox extension is provided only on the project's downloads page—and is not available through Mozilla's official Add-ons site—which prompts Firefox to display a big scary warning about installing software from unknown sources when one tries to install it.

It is not easy to say which installation option is better; Pencil is a heavyweight among add-ons and I consistently found it to run slower than the standalone version (and to slow down web browsing). On the other hand, the installable packages will conflict with the "Pencil" animation application, since both want to install /usr/bin/pencil. It seems like a little package polishing should enable peaceful coexistence, but thus far neither project seems interested in renaming its own binary.

When launched, the Pencil interface sports a large drawing canvas and a collapsible tree-view palette showing all of the installed UI element stencils. Adding elements to the drawing is a simple drag-and-drop; most elements are an image with optional text fields overlaid on top. That means nothing (other than common sense) prevents the user from mixing iOS, GTK, Windows, and web elements on a single drawing. The text fields are editable with a double click, so that the user can apply appropriate labels and text-entry content.

At this level of editing, creating a mock-up is trivial—or, perhaps, the mechanics of creating the mock-up are trivial, while proper UI design remains the real challenge. But what makes Pencil more useful than a collection of clip-art images is how it bakes in features to automatically guide the user in the right direction, and how it hides its more complex functionality while still making it available when needed.

For example, all UI elements have handles at the four corners of their bounding box, plus at the horizontal and vertical midpoints. Whenever an element is being dragged, as its midpoint nears the midpoint of something beneath it, a guide line appears and the user can snap the element to the guide to automatically center it. Nothing looks worse than a UI where things are slightly misaligned, after all. The same feature is available to snap elements to the top, bottom, or sides of other elements. And the snap function is smart enough to align items to the "active" area of the element underneath. This means that elements will snap to alignment with the screen of the "phone" mock-ups, rather than to the outside edge of the device.

For comparison, while Inkscape offers a slew of alignment and spacing tools, Pencil makes it difficult to not line things up correctly. Similarly, Pencil elements can be resized without distortion by grabbing one of the handles and dragging. In Inkscape dragging a handle scales the entire object (including changing the width of the lines), leaving it distorted. Pencil only scales the empty space inside the element, leaving its lines un-mangled. There are ways around that problem in Inkscape, but Pencil builds the feature into the structure of the UI elements itself.

At the same time, each element has a number of editable properties that can be changed from the right-click menu. Changing text labels is the most common operation, so that is the double-click behavior, but the rest can be altered if necessary. These properties include basics like color and font settings, but they include more complex options, too. For instance, UI elements can be grouped together, and each element in the group can have a different "sizing policy" that controls what happens when the entire group is resized. That lets users create things like relative-width web page designs, where some fields (like menus) stay the same size when the page is resized, but others (like text blocks) expand to fill the available space.

Although most UI elements are image-based, some offer more involved features and generally provide advanced functionality. The "Placeholder Text" stencil offers lorem ipsum text blocks (and its properties include adjustable margins), scrollbar elements can be scrolled up or down, and so on. It is a bit of work to build an interactive prototype, since each variation of the UI (button unpressed, button pressed, etc.) needs to be created as a separate canvas image, but Pencil saves some duplication of effort by letting the user make a copy of the current canvas rather than starting from scratch.

Pencil is certainly not free from problems. Sometimes when dragging an element from the element palette, the element disappears when the cursor reaches the canvas. There also does not appear to be a list view of elements on the canvas, so if one is hidden by another, it is impossible to select it. Probably the biggest practical limitation is the freshness of the stencil sets, however. The GTK+ collection, for example, is clearly a GTK2-era design, and there does not seem to be any urgency to update it. There seems to be no Qt collection at all, nor (ironically) a Firefox/Thunderbird collection. Admittedly, the collection that is the most fun to use is the "Sketchy" set that looks like genuine drawn-on-the-back-of-a-napkin mock-ups, but updates to the collections for Linux and web platforms that make them as current as the Android and iOS offerings would be nice.

Most of the professional UI and UX designers in the free software world seem to have gotten comfortable creating mock-ups in Gimp, Inkscape, and even Blender, so retraining on a different application may not sound appealing. Novices, however, will probably find Pencil easier to learn than a general-purpose drawing application. But it is possible that Pencil offers something worthwhile to interaction designers, too, and they may not be aware of it—after all, there are plenty of other Pencils available to choose from.

Comments (4 posted)

Progress on smaller and more colorful fonts

Concurrent with the central program of the 2013 ATypI conference in Amsterdam were various side meetings and workshops—not to mention the informal hallway discussions that are common to all technology conferences. In this case, the different side tracks resulted in some forward motion on some specifications that are likely to affect font development and software support for several years to come. The biggest is probably the Web Open Font Format version 2 (WOFF2), a proposed revision to the format used to deliver compressed font files over the web. WOFF 1.0 is still quite new, but Google is keen to update the format with support for a newly-released compression algorithm. At the same time, both of the two competing proposals for encoding color into fonts also moved forward, suggesting that the contest is far from over.

WOFF2

WOFF1 reached World Wide Web Consortium (W3C) "recommended" status in December 2012, but work was underway for a successor as early as March 2012. The format is intended to lossless-ly compress a font file for HTTP transmission. "Lossless" in this case means that the WOFF file retains the same glyphs as the input TrueType or OpenType font; the standard allows the WOFF creator to subset the characters included and remove unwanted tables (e.g., tables for character mappings, metrics, kerning, tracking, etc.). The file format is not simply a gzipped TTF, however: each data table in the font is compressed separately, so that applications only need to decompress the parts they need.

The first version of WOFF uses zlib's compress2() as the compression algorithm, which is a no-nonsense choice—after all, implementations are widely available and the algorithm is unencumbered with patents, which makes the W3C happy. But Google, purveyor of the largest web font–delivery service, was interested in improving on the compression in two respects: further reducing the size of the files and making decompression faster.

Reducing file size is an obvious improvement for any compression system, but the optimize-for-decompression model used for serving up the files might mean making different trade-offs than one would in a general-purpose algorithm. The font files only need to be compressed once, but need to be decompressed by every client—in browsers, the lag between loading page text and the application of the web font to that text is a common enough irritant that it has become known as FOUT ("flash of unstyled text"). Plus, optimizing decompression at the cost of more complex compression could help reduce the load on less powerful mobile devices.

Google's initial attempt to improve on WOFF1's compression used the LZMA entropy coder, but that algorithm proved aggravating on a number of fronts. First, its only documentation (much less specification) is sample code. Second, its lead developer was uninterested in working to incorporate LZMA into WOFF or other standards—a task that could involve time on his part for tasks like a rigorous security review. Third, although LZMA achieved smaller file sizes than zlib, it fell short on the goal of speeding up decompression.

The team at Google, led by Raph Levien and David Kuettel, reached out to other offices within the company and found a viable alternative. Jyrki Alakuijala and Zoltan Szabadka (who had previously worked on WebP compression) were already working on a variant of the Flate algorithm called Zopfli. They were able to further adapt their work into a new algorithm optimized for WOFF2. Called Brotli, the algorithm results in file sizes comparable to LZMA's (though a bit larger), but drastically faster decompression. Levien cited data rates of 120 to 300 MB/s decompression on the Google Fonts collection, compared to 20-30 MB/s for LZMA. The average file size is 29% smaller than WOFF1.

Google enabled the use of WOFF2 with Brotli as a runtime option for Chrome's "Canary" test builds in July 2013, and presumably has continued to tweak the algorithm based on what it has learned in that process. Keuttel has subsequently posted several updates to the W3C WebFonts Working Group mailing list, reporting the results of tests done on other font libraries. Most recently, on November 6, he noted additional improvements to the average decompression speed that came at the cost of altering the bit-stream format. That change had not yet been released in the open source code as of press time. Google also noted that the Brotli algorithm has not been optimized at all (in comparison to decades of optimization efforts for zlib), so hopefully with additional work there will be additional performance gains.

Improving the compression algorithm is the primary aim of WOFF2, but there are a few incidental improvements thrown in as well. Monotype's earlier MicroType Express (MTX) format proposal introduced some space-saving optimizations, too, like replacing composite glyphs (e.g., accented characters) with references to the original glyphs (e.g., the unaccented character and the accent mark), and transforming the tables in a font in order to take advantage of redundancy (for instance, WOFF1 required every glyph to have a bounding box, but in practice many glyphs' bounding boxes are identical and thus redundant). Google's Brotli-based WOFF2 reuses those ideas from MTX, and adds a few more, such as allowing some or all of the font file's tables to be compressed together, rather than requiring each table to be handled separately.

After the ATypI meeting, the WebFonts Working Group released its Evaluation Report for WOFF2, the first official publication in the publication-heavy process of W3C standardization. File compression fans will be happy to hear that Brotli is moving toward standardization, too; Google's Kenji Baheux posted a preliminary specification for Brotli to the mailing list after ATypI.

Outside of WOFF2 development, the WebFonts Working Group has looked at two other questions, but without resolution. The first was building support into WOFF for TrueType Collection (TTC) files. These are essentially bundles of multiple TTF fonts (such as a regular, bold, and italic) compacted together. Some people feel that delivering TTCs (instead of multiple TTFs compressed into multiple WOFFs) would further improve compression efficiency. The trouble is that in the real world, virtually no one publishes TTCs. Finally, Monotype's Vladimir Levantovsky resurrected a proposal to add "font" as a top-level MIME filetype with the IETF. Doing so might simplify the semantics of further standards work—right now, all fonts are registered underneath the "application" catch-all MIME type, like application/font-woff. As with TTC, however, what seems to be missing is motivation to push for the change. The reality is that what is in use today is good enough.

Colorful language

While TTC support and MIME-type registration languish, there is an abundance of interest in the area of standardization for chromatic fonts (i.e., fonts with color elements). As we discussed in August, there are two competing proposals from different players. Microsoft has been pushing for adding color index tables to the OpenType specification, which for historical reasons is managed by the MPEG body of the ISO. The W3C has a community group that is backing a different solution that adds SVG to OpenType instead. The W3C proposal was developed by Mozilla and Adobe.

Neither group has blinked yet. The W3C camp released its final proposal on October 9, notably with the additional backing of Monotype. On November 1, MPEG published its formal call for proposals for OpenType color support.

One might well ask whether or not the W3C group could simply submit its SVG-based proposal to MPEG. But the specifics of the MPEG call for proposals may make that difficult; among the listed requirements for submissions is "Low implementation complexity," which states that a proposal "shall not introduce significant burden on implementers and shall be easily implemented on various platforms including devices with limited capabilities and constrained memory / CPU resources". That language was certainly not invented to exclude SVG from consideration, but even die-hard SVG fans would probably agree that the format is rarely described as a "low implementation complexity" one.

The most probable outcome is that both proposals will be approved by their respective standards bodies; that is frequently what happens when standards-body proliferation goes unchecked. But the most important lesson may be that Microsoft has learned which standards bodies it can work with and which it cannot. WOFF actually began as an answer to Microsoft's Embedded OpenType (EOT) proposal, a compressed font format that explicitly supported DRM-like restrictions. But the EOT submission to the W3C never garnered outside support, and WOFF beat it handily. Years later when the chromatic font discussions began, it seems, Microsoft decided to skip the W3C and head straight for MPEG.

The W3C's process is not the fastest in the world, but it does have the benefit of requiring consensus between disparate parties. As the Encrypted Media Extensions (EME) debate has shown, the W3C process does not always reflect the will of everyone who uses the web. But it is more resilient against single-vendor solutions. Like a lot of plumbing underneath the web, users may not notice WOFF2 at all (aside from less-frequent FOUT annoyances), but they will notice chromatic fonts. Hopefully the dueling proposals will get cleanly resolved without years of frustrating incompatibility—but the more officially-blessed standards there are, the less likely that could be.

Comments (10 posted)