S3TC patent violation in multiple packages?

[Rudolf Polzer <divVerent@alientrap.org>]

Hi,

the S3TC texture compression scheme is covered by an US patent, as described in
http://lists.freedesktop.org/archives/nouveau/2010-March/005439.html

The following Debian packages in "main" seem to contain S3TC decompression code:

- imagemagick:
  $ convert -list format | grep DDS
        DDS* DDS       r--   Microsoft DirectDraw Surface
  it decodes DXT1, DXT3, DXT5 inside DDS files, which is S3TC.
- ffmpeg (contains dxt1 functions in its source code)
- gimp-dds (obviously, the whole purpose of this plugin is to encode/decode S3TC
  compressed textures)

Shouldn't this be an issue for Debian? Especially in case of ImageMagick, this
can lead to people unknowingly using patent encumbered code e.g. on commercial
web servers. Even if they just use ImageMagick to convert from e.g. BMP to JPG,
wouldn't they then still have to pay license costs for the S3TC decompression
algorithm as it is in ImageMagick, as they use software implementing the
patent?

The other two are maybe a different matter, as one can't use ffmpeg or gimp-dds
at all without violating patent claims anyway, so any user of these maybe can
be assumed to be aware of that (ignoring the fact that one can use and compile
ffmpeg with only purely free codecs like Theora, as face it, nobody does that
anyway, which is also why Debian includes e.g. MPEG-4 support).

Additionally, there is an idea... I think it is possible to do low-quality
decoding of S3TC without actually implementing the patent. All patent claims
that cover decoding talk about an "analog curve", which refers to linear
interpolation between two palette colors in each 4x4 block of the format. I am
wondering if taking just the average of the two palette colors of each 4x4
block, and not considering any palette indexes or interpolation inside, is a
way to evade the patent (at a high quality loss, though). Of course, the
average of the two colors is not guaranteed to be the average of the 4x4 block,
but it seems to come close in experimentation. One issue however may be that
even the act of averaging the two colors MAY be construed as an "analog curve";
however, if you do that, note that each 4x4 block is decompressed to a single
pixel, so the "blocks" are out. Also, obviously no "curve selection module"
would exist in that.

Similarily, for encoding, one could write an encoder that encodes each 4x4
block using an optimum 2-color palette, ignoring the two "interpolated" colors
S3TC allows to use. This would also get rid of the "analog curve", and thus
should evade the patent properly - again at a noticeable quality loss, though.

Best regards,

Rudolf Polzer