[FFmpeg-devel] [PATCH] RDFT for Bink and QDM2
Michael Niedermayer
michaelni
Sat Jan 24 10:36:47 CET 2009
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
[...]
--
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
When the tyrant has disposed of foreign enemies by conquest or treaty, and
there is nothing more to fear from them, then he is always stirring up
some war or other, in order that the people may require a leader. -- Plato
-------------- 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/20090124/9747eacb/attachment.pgp>
More information about the ffmpeg-devel
mailing list