[FFmpeg-devel] [PATCH] RDFT for Bink and QDM2

[Alex Converse]

2009/1/24 Michael Niedermayer <michaelni at gmx.at>

> On Fri, Jan 23, 2009 at 04:13:10PM -0500, Alex Converse wrote:
> > On Fri, Jan 23, 2009 at 7:25 AM, Michael Niedermayer <michaelni at gmx.at>
> wrote:
> > > On Thu, Jan 22, 2009 at 04:04:09PM -0500, Alex Converse wrote:
> > >> On Thu, Jan 22, 2009 at 1:35 PM, Michael Niedermayer <
> michaelni at gmx.at> wrote:
> > >> > On Thu, Jan 22, 2009 at 01:08:50PM -0500, Alex Converse wrote:
> > >> >> On Thu, Jan 22, 2009 at 12:58 PM, Michael Niedermayer <
> michaelni at gmx.at> wrote:
> > >> >> > On Thu, Jan 22, 2009 at 11:56:24AM -0500, Alex Converse wrote:
> > >> >> >> On Wed, Jan 21, 2009 at 6:14 PM, Michael Niedermayer <
> michaelni at gmx.at> wrote:
> > >> >> >> > On Wed, Jan 21, 2009 at 06:03:36PM -0500, Alex Converse wrote:
> > >> >> >> >> On Wed, Jan 21, 2009 at 5:53 PM, Michael Niedermayer <
> michaelni at gmx.at> wrote:
> > >> >> >> >> > On Wed, Jan 21, 2009 at 04:45:09PM -0500, Alex Converse
> wrote:
> > >> >> >> >> >> On Wed, Jan 21, 2009 at 4:25 PM, Michael Niedermayer <
> michaelni at gmx.at> wrote:
> > >> >> >> >> >> > On Wed, Jan 21, 2009 at 01:12:30PM -0500, Alex Converse
> wrote:
> > >> >> >> >> >> >> On Wed, Jan 21, 2009 at 8:36 AM, Michael Niedermayer <
> michaelni at gmx.at> wrote:
> > >> >> >> >> >> >> >
> > >> >> >> >> >> >> > On Tue, Jan 20, 2009 at 03:19:46PM -0500, Alex
> Converse wrote:
> > >> >> >> >> >> >> > > On Tue, Jan 20, 2009 at 1:50 PM, Michael
> Niedermayer <michaelni at gmx.at> wrote:
> > >> >> >> >> >> >> > > > On Tue, Jan 20, 2009 at 12:24:06PM -0500, Alex
> Converse wrote:
> > >> >> >> >> >> >> > > >> On Tue, Jan 20, 2009 at 11:52 AM, Michael
> Niedermayer <michaelni at gmx.at> wrote:
> > >> >> >> >> >> >> > > >> > On Mon, Jan 19, 2009 at 07:44:38PM -0500, Alex
> Converse wrote:
> > >> >> >> >> >> >> > > > [...]
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >> > [...]
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >> >> +/**
> > >> >> >> >> >> >> > > >> >> + * Sets up a real FFT.
> > >> >> >> >> >> >> > > >> >> + * @param nbits           Log2 of the length
> of the input array
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >> >> + * @param inverse         If TRUE, perform
> the inverse of the transform
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >> > i suggest if 0 perform the forward transform,
> if 1 perform the inverse
> > >> >> >> >> >> >> > > >>
> > >> >> >> >> >> >> > > >> I believe these are equivalent.
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > > > I searched for TRUE in the iso C standard and
> found no match.
> > >> >> >> >> >> >> > > > But lets assume it where defined as 1, this
> doesnt document any
> > >> >> >> >> >> >> > > > other value, is inverse=2 or 0 invalid? the
> forward transform?
> > >> >> >> >> >> >> > > > 99% of the people will guess correct but why
> write something ambigous if
> > >> >> >> >> >> >> > > > it can be written unambigous ...
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > > >>
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >> >> + * @param sign_convention The sign of j of
> the forward FFT.
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >> > i do not understand this, j is a variable that
> has no clear relation to a FFT
> > >> >> >> >> >> >> > > >> >
> > >> >> >> >> >> >> > > >>
> > >> >> >> >> >> >> > > >> j is the unit vector in the vertical direction
> on the complex plane. j
> > >> >> >> >> >> >> > > >> = sqrt(-1).
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > > > wasnt that i, i for imaginary?
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > > >>
> > >> >> >> >> >> >> > > >> The forward DFT can be defined as:
> > >> >> >> >> >> >> > > >> X_k = \sum_{n=0}^{N-1} x_n e^{-{2\pi j \over N}
> nk }
> > >> >> >> >> >> >> > > >>
> > >> >> >> >> >> >> > > >> It also can be defined as
> > >> >> >> >> >> >> > > >> X_k = \sum_{n=0}^{N-1} x_n e^{{2\pi j \over N}
> nk }
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > > > you can, but why would we need it?
> > >> >> >> >> >> >> > > >
> > >> >> >> >> >> >> > >
> > >> >> >> >> >> >> > > Bink uses it. As per the comments, the inverse of
> this transform is
> > >> >> >> >> >> >> > > not simply the transform with the opposite sign
> convention.
> > >> >> >> >> >> >> >
> > >> >> >> >> >> >> > maybe iam too tired but i see just one transform
> > >> >> >> >> >> >> >
> > >> >> >> >> >> >> > X[  k] = sum(n=0..N-1) x[n] e^(-2pi*i*n*k / N)
> > >> >> >> >> >> >> >        | k= N-m
> > >> >> >> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^(-2pi*i*n*(N-m) / N)
> > >> >> >> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^(-2pi*i*n*N / N -
> 2pi*i*n*-m / N)
> > >> >> >> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^(-2pi*i*n + 2pi*i*n*m /
> N)
> > >> >> >> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^( 2pi*i*n*m /
> N)e^(-2pi*i*n)
> > >> >> >> >> >> >> > X[N-m] = sum(n=0..N-1) x[n] e^( 2pi*i*n*m / N)
> > >> >> >> >> >> >>
> > >> >> >> >> >> >> The twiddle has to happen in the frequency domain so we
> have 4 cases:
> > >> >> >> >> >> >
> > >> >> >> >> >> > i have no clue what you talk about, but after a little
> testing i have
> > >> >> >> >> >> > some doubt that your code works at all.
> > >> >> >> >> >> > for example
> > >> >> >> >> >> >
> > >> >> >> >> >> >    ff_rdft_init(&one, 7, 1, 0);
> > >> >> >> >> >> >
> > >> >> >> >> >>
> > >> >> >> >> >> sign_convention takes +/- 1. I'm sorry if that wasn't
> clear.
> > >> >> >> >> >
> > >> >> >> >> > followng shows empirically
> > >> >> >> >> > that the transforms are identical short of trivial changes
> > >> >> >> >> >
> > >> >> >> >> >    ff_rdft_init(&one, bits, 1, -1);
> > >> >> >> >> >    ff_rdft_init(&two, bits, 1,  1);
> > >> >> >> >> >
> > >> >> >> >> >    for(i=0; i<N; i++)
> > >> >> >> >> >        src[i] = dst1[i] = (i + 2*i*i - 7*i*i*i + 123) %
> 1000;
> > >> >> >> >> >
> > >> >> >> >> >    for(i=0; i<N; i++){
> > >> >> >> >> >        dst2[i] = dst1[i];
> > >> >> >> >> >        if((i&1) && i!=1)
> > >> >> >> >> >            dst2[i]*=-1;
> > >> >> >> >> >    }
> > >> >> >> >> >
> > >> >> >> >> >    ff_rdft_calc(&one, dst1);
> > >> >> >> >> >    ff_rdft_calc(&two, dst2);
> > >> >> >> >> >
> > >> >> >> >>
> > >> >> >> >> Yes, it can be done as yet another pre/post processing loop.
> Or it can
> > >> >> >> >> be simply included as part of the transform.
> > >> >> >> >
> > >> >> >> > or the decoder can be fixed so it stores the values with the
> correct signs
> > >> >> >> >
> > >> >> >>
> > >> >> >> There is no such thing as "the correct sign." It's simply a
> matter of
> > >> >> >> convention,
> > >> >> >
> > >> >> > Well, if you define teh RDFT as a real input DFT than there is no
> convention
> > >> >> > that you can change unless you change the DFT as well
> > >> >> >
> > >> >>
> > >> >> We have an option to choose the sign convention for the DFT it is
> > >> >> simply the iDFT. You can think of the RDFT with opposite sign
> > >> >> convention as the RiDFT.
> > >> >
> > >> > RDFT, RiDFT, iRDFT, iRiDFT :)
> > >> >
> > >> >
> > >> > [...]
> > >> >> >
> > >> >> >> and in this case, considering the code we already have,
> > >> >> >> the problem is easier to solve with the positive sign
> convention.
> > >> >> >
> > >> >> > We should surely pick what is simpler, used by more important
> codecs
> > >> >> > and allows more tables to be shared and is closer to established
> conventions
> > >> >> > i dont know which of the 2 that neccessarily is ...
> > >> >> >
> > >> >>
> > >> >> Assuming the forward and inverse RDFT are implemented, adding the
> > >> >> opposite sign convention does not add any new tables.
> > >> >
> > >> > well, at least sign_convention should be replaced by something less
> > >> > error prone, maybe a enum combining it with inverse
> > >> >
> > >>
> > >> How about this?
> > >>
> > >> The enum lead me in the direction of readable vs bit-twiddly for the
> > >> _init function.
> > > [...]
> > >
> > >> + * @param sign_convention sign of the imaginary variable in the
> forward FFT
> > >> + */
> > >> +int ff_rdft_init(RDFTContext *s, int nbits, enum RDFTransformType
> trans);
> > >
> > > sign_convention ?
> > >
> > > except that the patch is probably ok
> > >
> >
> > I had forgotten to update the documentation.
> [...]
>
> > +void ff_rdft_end(RDFTContext *s)
>
> av_cold
>
> besides this it looks ok
>

fixed.

--Alex
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rdft.diff
Type: application/octet-stream
Size: 8424 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20090127/06809474/attachment.obj>