[FFmpeg-devel] [PATCH] WMA Voice decoder

Ronald S. Bultje rsbultje
Sat Jan 30 23:04:57 CET 2010

Hi,

On Fri, Jan 22, 2010 at 11:15 AM, Uoti Urpala <uoti.urpala at pp1.inet.fi> wrote:
> On Fri, 2010-01-22 at 10:48 -0500, Ronald S. Bultje wrote:
>> On Fri, Jan 22, 2010 at 10:39 AM, Michael Niedermayer <michaelni at gmx.at> wrote:
>> > On Thu, Jan 21, 2010 at 01:01:16PM -0500, Ronald S. Bultje wrote:
>> >> On Wed, Jan 20, 2010 at 7:53 PM, Michael Niedermayer <michaelni at gmx.at> wrote:
>> >> >> + ? ?int z = (uint16_t) (x * 49995 / y);
>> >> >
>> >> > I wonder if the 9 possible values for y could with a table ?9 entries
>> >> > and multiply + >> be used to simplify this
>> >>
>> >> So x%9=[0,8], so y is then 6, 11, 16, 21, ..., 46. Since 49995 uses 16
>> >> bits and x itself is 16 bits also, we'd either have to guarantee that
>> >> x*49995/y == x*(49995/y), which I think is not possible I think, or
>> >> use 64 bits. Couldn't I just use FASTDIV here also? I suppose a more
>> >> optimal solution would be:
>> >
>> > i mean you should try by brute force or if prefered another form of
>> > proof if this can be done by some multiply / add / shift
>>
>> I think it's not possible, we want a nondiv version of x*49995/y for
>> x>=0 && x <=0xFFFE and y being [6,46]. Since we can't proove that the
>> division can be done first, we need to multiply first, i.e. the range
>> is 0xFFFE * 49995 = 3.2 billion, unless we can simplify it. However,
>> 41 is already a prime number which 49995 is not divisible by, so I
>> don't think this is possible. So the input range of the division (for
>> a FASTDIV-style div) = up to 3.2 billion.
>>
>> dsputil.c says:
>> /* a*inverse[b]>>32 == a/b for all 0<=a<=16909558 && 2<=b<=256
>> ?* for a>16909558, is an overestimate by less than 1 part in 1<<24 */
>>
>> So it's only guaranteed to be valid up to 16 million, i.e. my range is too big.
>>
>> (I wonder if this proof is valid, I think it is but I'm not a math PhD.)
>
> x*49995 / 41 = x*(1219*41 + 16) / 41 = 1219*x + x * 16 / 41
> In the last form x*16 is at most 1048544.

OK, I used UMULH() along with this to create a table. Now all
divisions except the modulo at the end (I cannot prevent that) are
gone.

New patch coming.

Ronald