[Mesa-dev] S2TC - yet another attempt to solve the "S3TC issue"

[Rudolf Polzer]

On Tue, Aug 09, 2011 at 03:25:05AM -0700, Jose Fonseca wrote:
> ----- Original Message -----
> > I was trying to help the Linux communtiy, but apparently I failed.
> > 
> > Looks like all this work I did was for nothing. Nothing is
> > appreciated, all is
> > "Not Invented Here".
> >
> > How else should I have brought this up? I still don't understand WHY
> > this is an
> > issue. Is US patent law really that retarded? I still can't believe
> > this, as to
> > me that would mean that Apache would have needed a patent license in
> > order to
> > transport GIF files back then (or at least, to assign the content
> > type
> > "image/gif" in the default config).
> 
> I don't have time for a longer reply now, but I do think your S2TC work is
> interesting, and that you've successfully contoured the patent claims, at
> least for the decompression, as I didn't look at the compression bits.

The compression bits are even simpler. Decompression is a BIT dodgy, due to the
(i^j)&1 decision which, but could be "fixed" by always using 0 or 1 there,
reducing quality a bit, but being "safer".

As for compression: the compressed format is basically "each 4x4 block is a
2-color optimum palette image". Similar schemes have existed way before S3TC
(e.g. in some video codecs used by DOS games - see ffmpeg for implementations
of these), and even way before Apple's RPZA, which I still see as obvious prior
art that should render any S3TC related patents invalid (which is apparently
exactly what Apple now is trying to achieve in court). Whether my specific
algorithms for choosing the 2 colors, or for finding the nearest color of the
two for each pixel, violate any patents, I cannot say, but these two things are
quite interchangable. Too bad the standard color reduction algorithm "Median
cut" does not work well if the target is just two colors, as it would have been
a VERY safe choice.

Still, this apparently isn't useful for anything.

> But, there was never anything you could have done to improve the situation
> for GPU S3TC decompression.  It's not just a US patent system vs the rest.
> It's complex, but it's all in the archives, as it has all been discussed
> before.

Still makes absolutely no sense to me, but if it's that insane, it is (see my
Apache/GIF example, which is THE VERY SAME THING).

However, I still am wondering - what if the data fed to the GPU is not S3TC
compressed at all? Do we still need the patent license if we e.g. feed a block
of null bytes to it, jzst because that circuit is a S3TC decoder? Hopefully
not, as this would be EVEN more insane.

If the "null byte" example is legal, however, then likely, feeding S2TC
compressed textures is fine as well, as the methods described in the S3TC
patents are not used by them. So one idea to support precompressed textures
would be converting S3TC to S2TC the following way, for the DXT1 case:

- if the block is a "DXT1-alpha" block:
  - map 10 to either 00 or 01 at random (or using (i^j)&1 dithering)
  - keep all other bit values as is
- if the block is a "DXT1-without-alpha" block:
  - possibly, to make the block types indistinguishable, swap c0 and c1, and
    XOR each pixel data byte by 0101010
  - map 10 and 11 to either 00 or 01 (at random, with (i^j)&1 dithering, or 10
    to 00, 11 to 01)
  - keep all other bit values as is
  - when going the "move interpolated values to borders" way, this would be
    doable by an AND of each byte by 01010101)

a lazy low-quality implementation of this could be like this:

// extract colors to c0 and c1
// extract pixel data to an uint32_t pixels
if(c0 <= c1)
{
	// DXT1-alpha block

	// either:
	// map any 10 to 00:
	// 00 -> 00
	// 01 -> 01
	// 10 -> 00
	// 11 -> 11
	//pixels = pixels & ~((~pixels & 0x55555555) << 1);

	// or:
	// map any 10 to 01:
	// 00 -> 00
	// 01 -> 01
	// 10 -> 01
	// 11 -> 11
	//pixels = (pixels & ~((~pixels & 0x55555555) << 1)) | ((pixels & 0xAAAAAAAA) >> 1);

	// or:
	// dither between the two methods (the "i&j" method)
	pixels = (pixels & ~((~pixels & 0x55555555) << 1)) | ((pixels & 0x88228822) >> 1);
}
else
{
	// DXT1-noalpha block

	// optionally, to make sure the decoder always "sees" the c0 <= c1 case:
	swap(&c0, &c1);
	pixels = ~pixels;
	// actually: pixels ^ 0x55555555, but the difference to this gets ANDed away in the next step

	pixels = pixels & 0x55555555;

	// or, we could do the same dithering method as above for possibly better display (not sure):
	// 00 -> 00
	// 01 -> 01
	// 10 -> 00 or 01
	// 11 -> 00 or 01
	pixels = (pixels & ((~pixels & 0xAAAAAAAA) >> 1)) | ((pixels & 0x88228822) >> 1);
}

For DXT5, further processing would be needed for handling the alpha channel, or
maybe not, depending on interpretation of the S3TC patents. If "color" in there
is not interpreted to also include scalar values, then DXT5's alpha part is
fine as is - if not, converting DXT5's alpha to S2TC alpha would be necessary
too. In case the DXT5 alpha encoding is commonly seen as NOT infringing the
S3TC patents, which personally I am unsure about, then the S2TC tools could be
changed to encode "full" DXT5 alpha (and S2TC code doing that is provided in
the s2tc+alpha branch of my repository).

This would obviously lose quality, but not any more than what the S2TC
decompressor does when fed with S3TC data. But, even if this is _legally_
sound, it might be a bad idea to have a non-conforming implementation of
GL_EXT_texture_compression_s3tc which this would be - especially, as a game
that includes both S3TC and RGB encoded textures may, due to this quality loss,
rather want to prefer RGB over S3TC.

If the input is compressed using S2TC, though, no further quality loss would
occur at this stage, as the operation described above would be the identity.

> How should you brought this? You should have assumed that we have our reasons
> -- after all we've been living under the frustration of these patents,
> walking on a mine field, for a decade --, instead of assuming we have NIH
> syndrome.

So I should never try to do anything new, as likely someone else may have
already done it and rejected it.

Good to know.

Best regards,

Rudolf Polzer