theora dev - Mar 2008 - Bug in reference idct.

Hi

The Theora specification states, in section 7.9.3 ("The 1D Inverse
DCT")
steps 14-16:

14. Assign T[5] the value T[4] - T[5].
15. Truncate T[5] to a 16-bit representation by dropping any higher-order
bits.
16. Assign T[5] the value C4 * (-T[5]) >> 16.

However, the relevant section of code in the reference decoder
(lib/dec/idct.c line 50) is:

t[5]=OC_C4S4*(ogg_int16_t)(t[4]-t[5])>>16;

i.e. T[5] (the result of T[4]-T[5]) is not inverted before being
multiplied by C4.

Lines 106, 150 and 190 in idct.c do the same thing - the spec says the
result of (T[4] - T[5]) should be negated before being multiplied. I
believe this is a bug in the reference implementation.

The experimental "from-scratch" theora-exp has this same bug.


Further, the spec states in the same section, on step 50:

50. Assign X the value T[1] - T[6].

This is impossible as X is defined to be an array. I believe the intent
was to assign R the value of (T[1] - T[6]). The reference decoder states:
   _y[6<<3]=(ogg_int16_t)(t[1]-t[6]);

which would achieve the same result as assigning to R. I believe this is a
bug in the spec.



Chris Brien

Chris Brien wrote:
> Lines 106, 150 and 190 in idct.c do the same thing - the spec says the
> result of (T[4] - T[5]) should be negated before being multiplied. I
> believe this is a bug in the reference implementation.
I'm pretty sure the actual error is in the spec. The current reference
implementation decoder is based on theora-exp, so naturally they will
have the same bugs. However, you will find in
http://svn.xiph.org/trunk/theora-old the original VP3-based decoder,
which uses a completely different iDCT implementation. Using
(t[4]-t[5]), the two match exactly (tested on 65536 random inputs).
Using (t[5]-t[4]), they differ completely.

You will also notice that in the diagram in Figure 7.1, it is output
line 5 that is negated in this butterfly, not 4. Therefore I believe
this is an error in the spec.

I didn't check the output against an exact matrix-mul iDCT
implementation, but even if they did differ, we would need a compelling
reason to change the code now, for compatibility reasons.
> This is impossible as X is defined to be an array. I believe the intent
> was to assign R the value of (T[1] - T[6]). The reference decoder states:
>   _y[6<<3]=(ogg_int16_t)(t[1]-t[6]);
> 
> which would achieve the same result as assigning to R. I believe this is a
> bug in the spec.
Yes, it is.

Both errors have been fixed in svn r14555. Thanks for the report.