[FFmpeg-devel] (i)(m)dct help for g.722.1

[Michael Niedermayer]

Hi

On Thu, May 17, 2007 at 12:48:09PM +0200, Benjamin Larsson wrote:
> Michael Niedermayer wrote:
> > Hi
> > 
> >>
> >> Questions to the math gurus:
> >> What's the best alternative FFT algorithm in terms of speed and accuracy 
> >> that supports arbitraty sizes?
> >> Is there a way to use the current code with some additional math 
> >> (convolution, re-sampling) and produce accurate results?
> > 
> > IIRC the only thing needed to do a 320 point FFT is that you write a
> > 5 point FFT (the naive O(n^2) algo will do) and combine that with the
> > existing 64 point FFT with the correct twiddle factors
> > 
> > [...]
> 
> Here is a 5 point fft generated by spiral. Look at kiss fft how to
> integrate both stages.

maybe this spiral thing could be tried to optimize our normal fft too?

[...]
> /* [ 10, 10 ] */
> void  DFT_5(double  *Y, double  *X) {

missing ff_ prefix


>     double t962, t963, t964, t965, t966, t967, t968, t969, t970, t971, t972, t
> 973, t974, t975, t976, t977;
>     t962 = (X[2] + X[8]);
>     t963 = (X[3] + X[9]);
>     t964 = (X[2] - X[8]);
>     t965 = (X[3] - X[9]);
>     t966 = (X[6] + X[4]);
>     t967 = (X[7] + X[5]);
>     t968 = (X[6] - X[4]);
>     t969 = (X[7] - X[5]);
>     t970 = ((X[0] + (0.3090169943749474*t962)) - (0.80901699437494745*t966));
>     t971 = ((X[1] + (0.3090169943749474*t963)) - (0.80901699437494745*t967));
>     t972 = ((X[0] - (0.80901699437494745*t962)) + (0.3090169943749474*t966));
>     t973 = ((X[1] - (0.80901699437494745*t963)) + (0.3090169943749474*t967));

_ALL_ () are superflous above

A25= 0.3090169943749474+0.25;
u0= A25*(t962 - t966);
u1= A25*(t963 - t967);
u2= X[0] - 0.25*(t962 + t966);
u3= X[1] - 0.25*(t963 + t967);

t970 = u2 + u0;
t971 = u3 + u1;
t972 = u2 - u0;
t973 = u3 - u1;

the above needs 4 multiply and 10 additions while the suggested code
needs 8 multiply and 8 additions
assuming  i didnt make a misstake of course, also my code may or may
not be faster depending on the cpu ...


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

There will always be a question for which you do not know the correct awnser.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070517/a0cc7ec6/attachment.pgp>