[Nouveau] [Mesa3d-dev] Status of s3tc patent in respect to open-source drivers and workarounds

[Corbin Simpson]

On Sun, Mar 28, 2010 at 4:47 AM, SpliFF <spliff at warriorhut.org> wrote:
> Hi radeonhd, nouveau, mesa3d developers,
>
> Firstly, thank you all very much for all the important work you do.
>
> I've been working as a part-time developer on the "Spring RTS" project
> (open-source game engine) which runs on linux (and other os). Some time
> ago I tried the engine on the open-source ATI radeonhd driver, which I
> understand to be partly based on mesa 3d, and all textures were white. I
> originally assumed it was an engine bug but after some investigation
> tracked it down to s3tc texture (de)compression not being integrated in
> the open driver for legal reasons. It seems the same issue applies to
> Mesa3d and Nouveau - that is s3tc being patented and the patent owner
> refusing to comment or provide cover for open-source projects
> implementing the techniques discussed in US Patent 5956431
> (http://v3.espacenet.com/publicationDetails/claims?DB=&locale=&FT=D&date=19990921&CC=US&NR=5956431A&KC=A&tree=true)
>
> I recently took inspiration from an article/talk presented by Andrew
> Trigell regarding patents where he claims developers often overestimate
> the scope of patents
> (http://news.swpat.org/2010/03/transcript-tridgell-patents/) because
> they fixate on the title and summary instead of the actual claims.
>
> The key point he was making is that in order to infringe a patent you
> apparently have to infringe on ALL ELEMENTS of a PRIMARY claim. If you
> don't do something in the primary claim then by definition you aren't
> doing the things in secondary claims that reference it (ie, where the
> claim reads "... in claim X ..."). In short if you workaround the
> primary claims you probably aren't infringing. Wikipeadia, with some
> jurisdictional hand-waving, appears to agree: "If all of the claim's
> elements are found in the technology, the claim is said to "read on" the
> technology; if a single element from the claim is missing from the
> technology, the claim does not literally read on the technology and the
> technology does not infringe the patent with respect to that claim."
>
> So I took a look at the 4 primary claims that apply to DECODING s3tc
> textures. All other claims either rely on these claims or involve
> encoding, which Mesa 3D / Xorg drivers should not need to do. Finding a
> workaround for these primary claims is necessary to avoid infringement
> for an s3tc decoder. I'll break these into seperate elements because a
> workaround (non-infringement) for ANY element is a workaround for the
> ENTIRE claim itself. The elements are seperated by semicolons and I've
> added line-breaks to make them clearer).
>
> To avoid confusion I've removed the preamble from each claim, they don't
> count as elements of the claim.
>
> In short, if anyone on these lists can see a way to decompress an s3tc
> image without doing just 1 of the items from EACH of the following 4
> claims then a legal s3tc decoder should be possible.
>
> ================
> 5.
> an encoded image decomposer,
> coupled to receive encoded image data file having at least one
> compressed image block,
> for breaking the encoded image data file into individual compressed
> image blocks,
> each compressed image block having at least one associated codeword,
> each codeword generated through selecting a block type for an original
> image block comprising the compressed image block,
> computing an analog curve for the block type,
> selecting a partition along the analog curve for the computed analog curve,
> and computing the set of codewords for the partition;
>
> at least one block decoder,
> coupled to the encoded image decomposer,
> for decompressing the compressed image blocks;
>
> and an image composer,
> coupled to each block decoder,
> for ordering the decompressed image blocks in an output file.
>
> ==================
> 16.
> receiving the encoded image data;
>
> decomposing the encoded image into the modified header and the
> individual encoded image blocks;
>
> reading the modified header to generate an output header;
>
> decoding each individual encoded image block to generate a decoded image
> block,
> including receiving each individual encoded image block, including a
> plurality of codewords,
> and a bitmap of at least one pixel,
> the plurality of codewords derived through selecting a block type for an
> original image block of the encoded image block,
> computing an analog curve for the block type,
> selecting a partition along the analog curve for the computed analog curve,
> and computing the plurality of codewords for the partition;
>
> and composing the output header and the individual decoded image blocks
> to generate an output file of the original image.
>
> ==================
> 21.
> a block address computation module, coupled to receive each codeword
> from the header information, for computing an address of an encoded
> image block having the identified pixel;
>
> a block fetching module, coupled to receive the encoded image block
> portion and the computed address, for fetching the encoded image block
> having the identified pixel;
>
> and a block decoder, coupled to receive the fetched encoded image block,
> for decoding the image block to generate a quantized color associated
> with the identified pixel.
>
> ==================
> 22.
> computing an address for an encoded image block having the identified
> pixel,
> the address computed from the at least one codeword for the encoded
> image block;
>
> fetching the encoded image block using the computed address;
>
> computing quantized color levels for the fetched encoded image block;
>
> and selecting a color of the identified pixel from the quantized color
> levels to output.
>
> ===================
>
>
> One thing that stands out to me are that none of the primary claims seem
> to describe the technical format itself (ie, no algorithms, keywords,
> block sizes, byte-alignment, etc..) This means the claims at issue seem
> to be *methods* of data handling, (and not particularly inventive ones
> in my opinion). That suggests to me that with a little thought it should
> be possible to generate the same results via a method that doesn't
> infringe one of the 4 specific claims listed above. To clarify, despite
> all the technical mumbling in the abstract the claimed invention does
> not appear to be a "format" as such, but a method of pulling "blocks"
> and a "header" out of an undefined format and generating "color pixels".
> Even the abstract claims all the presented examples of keywords, values
> and structure for s3tc are not the actual invention being claimed.
> Another important point is that some of the wording in the claims may
> not mean what it appears to mean (ie, the generally accepted
> definition), the full patent may redefine some common software terms in
> the wrapper.
>
> Some possible avenues of investigation, straight off the top of my head are:
>
> * Determine the patents' definition of a "unit" and/or "module", and use
> something else (ie, a monolithic function)
> * Determine the patents' definition of a "block", and use something
> else. (characters, a bytestream, ...)
> * Determine the patents' definition of "compose / decompose", and do
> something else.
> * Do we need to "compose a header" as a seperate stage (use a footer,
> temporary vars, registers)
> * Does the curve have to be "analog"? What about a lookup table with
> discreet points that approximate a curve?
> * Can the algorithms work on groups of blocks or sub-blocks instead of
> "individual blocks".
>
> More for DRI projects than Mesa, but I'll ask anyway:
> * Do we need to decode anything; could an X11 driver force-feed the raw
> bytes to hardware instead?
>
> Claim 22 seems like a pretty important step and possibly a hard one to
> workaround but it also appears to be claiming the invention of using a
> key lookup to fetch values with some vague notion of quantising them. Is
> it just me or are they claiming to have invented indexed color?
>
> PS. If some of the points above seem pedantic that's deliberate. My
> understanding is that patent claims are actually intended or required to
> be NARROW in scope as broad claims are usually rejected. That means a
> workaround that doesn't do PRECISELY the things in each claim above is,
> by definition, a new invention. I'm hoping an invention that members of
> this community are capable of finding before someone else patents it.
>
> I've CC'ed the EFF on this because I'd like to see it become a part of
> their patent-busting efforts. Fear of this patent is blocking an
> extremely important component of 3D gaming under linux (the use of DDS
> textures under an open-source driver). Not that I'm a fan of DDS, just
> that it's the format of choice for commercial and non-commercial games
> until hardware supports something better, and even then still a
> requirement for running many classic games under WINE +
> radeonhd/mesa3d/nouveau. It seems absurd that I can buy a product with a
> patent license granted (NVIDIA/ATI card) but then be denied the
> protection of that license because I don't use part of the product (the
> official driver). I really hope that as a community we can either invent
> around this patent or bust it (at least in US / EU where it is most
> problematic) without losing hardware support or requiring the
> reformatting/conversion of digital assets.\

Since neither you nor Andrew are lawyers, I would kindly ask that you
refrain from attempting to provide legal advice. :3

The scant legal advice that *has* been obtained suggests that the
current course of action, wherein S3TC is not advertised without the
aid of an external library or a configuration option force-enabling
it, is the best course of action. I for one would prefer to have
firsthand legal advice before making any changes, although I am not a
lawyer and cannot provide legal advice.

At any rate, since Spring is open-source, I would heavily advise the
Spring team to remember that OpenGL extensions that are not part of a
core version are not guaranteed to be available, and in this case,
there is a trivial workaround for when the extension is not present,
so you guys could (and should!) include an uncompressed texture path
and ship uncompressed textures.

~ C.

-- 
When the facts change, I change my mind. What do you do, sir? ~ Keynes

Corbin Simpson
<MostAwesomeDude at gmail.com>