[Ffmpeg-devel] [RFC] fixed point mdct transform

[Rich Felker]

On Fri, Nov 25, 2005 at 02:39:50PM +0100, Michael Niedermayer wrote:
> Hi
> 
> On Fri, Nov 25, 2005 at 01:10:04PM +0100, Benjamin Larsson wrote:
> > I did a fixed point mdct and was hoping to use it in ffmpeg for some of
> > the audio codecs. The code is located here:
> > 
> > http://tranquillity.campus.luth.se/~banan/fpmdct/
> > 
> > The problem with this implementation is that it needs lots of fractional
> > bits to get good precision. In _kiss_fft_guts.h the FRACBITS define lets
> > you change the amount of fractional bits to use. The minimum amount of
> > bits for the random test table seams to be 12. Less then 12 gives more
> > then 1 bit difference compared to the reference calculation in some
> > cases (I consider that to much). The amount of fractional bits also
> > cause >32bit overflow when multiplying. My aim is to only use 32 bits to
> > aid embedded use, but I'm not sure how to do that. So does anyone have
> > any wise comments to share in this matter ? I guess the core problem is
> > how to do a fast precise fft transform with integer arithmetics without
> > using more then 32bits.
> 
> ahh, you want everything at the same time, iam almost certain thats not
> possible, heres what i _think_
> 1. on many modern CPUs with fast FPU a floating point FFT will be faster 
> and more precisse then a fixed point FFT
> 2. if you limit yourself to C style 32bit multiplies then you will have
> to accept either low precission or slow and messy code
> 3. many CPUs have a fast 32x32->64 bit or 32x32->high32 bit multiply
> instruction

imo definitely go with option 3. something like this:
int a,b; ((long long)a * b) is only a 32bit multiply, which results in
a 64bit result. any sane cpu has 64bit results for 32x32 multiply,
via one of the two means michael mentioned.

> so there are really at least 4 cases we should ideally support
> 1. float based FFT
> 2. less accurate but fast C style 32bit fixedpoint FFT (x*y)>>shift
> 3. accurate and fast 32x32->high32 style fixedpoint FFT (x*(int64_t)y)>>32
> 4. 64bit FFT (x*y)>>shift style

not clear what the difference between 3 and 4 is, but either sounds
ok.

rich