[FFmpeg-devel] [PATCH] WMA Voice decoder

Michael Niedermayer michaelni
Fri Jan 22 18:09:28 CET 2010


On Fri, Jan 22, 2010 at 10:48:23AM -0500, Ronald S. Bultje wrote:
> Hi,
> 
> 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.)

One way that works:
            switch(y){
            case  6: z2= (x*16665          )>> 1; break;
            case 11: z2=  x*4545                ; break;
            case 16: z2= (x*49995          )>> 4; break;
            case 21: z2= (x*312044983      )>>17; break;
            case 26: z2= (x*2016290659     )>>20; break;
            case 31: z2= (x*211385311      )>>17; break;
            case 36: z2= (x*5555           )>> 2; break;
            case 41: z2= (x*2557246689     )>>21; break;
            case 46: z2= (x*569821273+2842 )>>19; break;

(should be implemeneted with a LUT instead of switch of course.
 and probably fixed shift)
The last addition can be avoided in exchange for a larger constant of
4558570185 (this has 5 prime factors so part of it could be
multiplied into x first to avoid the >32bit multiply)
id suspect it also might be possible to premultiply x always by
some small trivial constant like 3 or 5 to end up with constants
that all fit in 32bit and need no addition

And there are surely many other ways to do this as well

but now i need to go and buy some food before the shops close :)

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Incandescent light bulbs waste a lot of energy as heat so the EU forbids them.
Their replacement, compact fluorescent lamps, much more expensive, dont fit in
many old lamps, flicker, contain toxic mercury, produce a fraction of the light
that is claimed and in a unnatural spectrum rendering colors different than
in natural light. Ah and we now need to turn the heaters up more in winter to
compensate the lower wasted heat. Who wins? Not the environment, thats for sure
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20100122/f7551739/attachment.pgp>



More information about the ffmpeg-devel mailing list