Spec / code mismatch for color index out of bounds

[GoogleCodeExporter]

The libwebp code's ExpandColorMap function pads out the color map with 
transparent black (0x00000000) so that the length of the color map is either 2, 
4, 16 or 256. Inside the COLOR_INDEX_INVERSE macro, there is no bounds 
checking, so that even if the color_table_size was only 200 (which rounds up to 
256), libwebp seems to accept an index of 220 to map to transparent black.

None of this is described in the specification, and it's not obvious to me 
whether this is a bug in the spec or a bug in the code.

Original issue reported on code.google.com by nigel...@golang.org on 9 Jun 2014 at 11:42

[GoogleCodeExporter]

it's actually a speed-up technique to avoid having to check the bounds for 
every pixels (see COLOR_INDEX_INVERSE macro in dsp/lossless.c:1177).

The specs just specifies "argb = color_table[GREEN(argb)];", leaving the 
out-of-bound handling undefined and up to the decoder.

This paragraph could indeed use some precision for out-of-bound handling.

Original comment by pascal.m...@gmail.com on 11 Jun 2014 at 2:12

[GoogleCodeExporter]

We can nail it down to the spec that these values are translucent black.

Original comment by jyrki.al...@gmail.com on 11 Jun 2014 at 3:03

[GoogleCodeExporter]

that would force ffmpeg to change their code which is currently correct:
http://www.ffmpeg.org/doxygen/2.1/webp_8c_source.html#l01042

This is a case where libwebp is walking the thin line between being fast and 
being the reference-implementation.
We could also add a check for out-of-bound, protected by a compile-flag (like: 
#ifdef REFERENCE_IMPLEMENTATION).

Original comment by pascal.m...@gmail.com on 12 Jun 2014 at 6:19

[GoogleCodeExporter]

In my opinion, having the code match the spec, and having a consistent 
definition of what is a valid and an invalid VP8L image, is the most important 
thing. If being fast is important, and if the bounds check inside the inverse 
color index transform really makes a significant performance impact (which I'd 
be surprised if it did), then change the spec and tell the ffmpeg developers. 
But I repeat that my biggest concern is eliminating undefined behavior.

For example, the Go JPEG library tries to match the official JPEG spec, but has 
had to include changes that are off-spec because one or more implementations 
incorrectly read and wrote invalid JPEGs, and so now Go's cleanroom code has to 
re-implement the bugs of other (unofficial) implementations:
https://codereview.appspot.com/6526043/diff/5002/src/pkg/image/jpeg/reader.go?co
ntext=10&column_width=120

Original comment by nigel...@golang.org on 12 Jun 2014 at 6:36

[GoogleCodeExporter]

If a correctly predicted branch costs 3 cycles, we are saving 3 cycles per 
pixel with the current implementation. On a 2 GHz processor and a 1024x1024 
pixel image this maps to 1.6 ms savings on decode time. On top of this, there 
are some (possibly minor) additional savings for not polluting the branch 
predictors by an unnecessary branch.

Since it is an insignificant corner case of the spec, it is better to define 
the lookup to be large enough so that we can avoid the branches, and get it 
filled with zeros.

Please change the spec, not the code.

Original comment by jyrki.al...@gmail.com on 12 Jun 2014 at 10:18

[GoogleCodeExporter]

as much as i don't like to change the spec if code-modification is possible, i 
think Jyrki has a point here:
the attached file is 9% slower to decode (palette size=100) with bound-checking.

Patch for adding bound-checking instead of expand-colormap is here: 
https://gerrit.chromium.org/gerrit/70605

So, yes, i think we should amend the spec and send a patch to ffmpeg.

Original comment by pascal.m...@gmail.com on 23 Jun 2014 at 4:26

Attachments:

• bryce_100colors.webp

[GoogleCodeExporter]

attached, a WebP test file that explicitly uses out-of-bound index in the 
palette to code translucent black pixels.
It will decode 'ok' with libwebp (because we pad the color palette), but not 
with current ffmpeg (which reports an "invalid palette index 113").

Also attached a patch for ffmpeg that i indent to send upstream once the spec 
is amended.

Original comment by pascal.m...@gmail.com on 16 Sep 2014 at 3:03

Attachments:

• bad_palette_index.webp
• 0001-libavcodec-webp-treat-out-of-bound-palette-index-as-.patch

[GoogleCodeExporter]

doc updated, as per https://gerrit.chromium.org/gerrit/#/c/71605/

Will send the patch to ffmpeg dev.

Original comment by pascal.m...@gmail.com on 18 Sep 2014 at 6:33

• Changed state: Done