41 #if !CONFIG_HARDCODED_TABLES 61 double freq = 2*
M_PI/m;
64 tab[i] =
FIX15(cos(i*freq));
74 #define INIT_FF_COS_TABS_FUNC(index, size) \ 75 static av_cold void init_ff_cos_tabs_ ## size (void)\ 77 init_ff_cos_tabs(index); \ 101 { init_ff_cos_tabs_32, AV_ONCE_INIT },
102 { init_ff_cos_tabs_64, AV_ONCE_INIT },
103 { init_ff_cos_tabs_128, AV_ONCE_INIT },
104 { init_ff_cos_tabs_256, AV_ONCE_INIT },
105 { init_ff_cos_tabs_512, AV_ONCE_INIT },
106 { init_ff_cos_tabs_1024, AV_ONCE_INIT },
107 { init_ff_cos_tabs_2048, AV_ONCE_INIT },
108 { init_ff_cos_tabs_4096, AV_ONCE_INIT },
109 { init_ff_cos_tabs_8192, AV_ONCE_INIT },
110 { init_ff_cos_tabs_16384, AV_ONCE_INIT },
111 { init_ff_cos_tabs_32768, AV_ONCE_INIT },
112 { init_ff_cos_tabs_65536, AV_ONCE_INIT },
113 { init_ff_cos_tabs_131072, AV_ONCE_INIT },
143 if(n <= 2)
return i&1;
153 #if (!CONFIG_HARDCODED_TABLES) && (!FFT_FIXED_32) 159 0, 4, 1, 5, 8, 12, 9, 13, 2, 6, 3, 7, 10, 14, 11, 15
177 int n = 1 << s->
nbits;
179 for (i = 0; i < n; i += 16) {
182 for (k = 0; k < 16; k++)
187 for (k = 0; k < 16; k++) {
189 j = (j & ~7) | ((j >> 1) & 3) | ((j << 2) & 4);
203 if (nbits < 2 || nbits > 17)
245 for(j=4; j<=nbits; j++) {
254 #define PROCESS_FFT_PERM_SWAP_LSBS(num) do {\ 255 for(i = 0; i < n; i++) {\ 258 j = (j & ~3) | ((j >> 1) & 1) | ((j << 1) & 2);\ 259 k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\ 260 s->revtab##num[k] = j;\ 264 #define PROCESS_FFT_PERM_DEFAULT(num) do {\ 265 for(i = 0; i < n; i++) {\ 268 k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\ 269 s->revtab##num[k] = j;\ 273 #define SPLIT_RADIX_PERMUTATION(num) do { \ 274 if (s->fft_permutation == FF_FFT_PERM_SWAP_LSBS) {\ 275 PROCESS_FFT_PERM_SWAP_LSBS(num) \ 277 PROCESS_FFT_PERM_DEFAULT(num) \ 286 #undef PROCESS_FFT_PERM_DEFAULT 287 #undef PROCESS_FFT_PERM_SWAP_LSBS 288 #undef SPLIT_RADIX_PERMUTATION 302 const uint16_t *revtab = s->
revtab;
303 const uint32_t *revtab32 = s->
revtab32;
307 for(j=0;j<np;j++) s->
tmp_buf[revtab[j]] = z[j];
309 for(j=0;j<np;j++) s->
tmp_buf[revtab32[j]] = z[j];
325 int nbits,
i, n, num_transforms,
offset, step;
327 unsigned tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8;
329 const int fft_size = (1 << s->
nbits);
332 num_transforms = (0x2aab >> (16 - s->
nbits)) | 1;
334 for (n=0; n<num_transforms; n++){
338 tmp1 = tmpz[0].
re + (unsigned)tmpz[1].
re;
339 tmp5 = tmpz[2].
re + (unsigned)tmpz[3].
re;
340 tmp2 = tmpz[0].
im + (unsigned)tmpz[1].
im;
341 tmp6 = tmpz[2].
im + (unsigned)tmpz[3].
im;
342 tmp3 = tmpz[0].
re - (unsigned)tmpz[1].
re;
343 tmp8 = tmpz[2].
im - (unsigned)tmpz[3].
im;
344 tmp4 = tmpz[0].
im - (unsigned)tmpz[1].
im;
345 tmp7 = tmpz[2].
re - (unsigned)tmpz[3].
re;
347 tmpz[0].
re = tmp1 + tmp5;
348 tmpz[2].
re = tmp1 - tmp5;
349 tmpz[0].
im = tmp2 + tmp6;
350 tmpz[2].
im = tmp2 - tmp6;
351 tmpz[1].
re = tmp3 + tmp8;
352 tmpz[3].
re = tmp3 - tmp8;
353 tmpz[1].
im = tmp4 - tmp7;
354 tmpz[3].
im = tmp4 + tmp7;
360 num_transforms = (num_transforms >> 1) | 1;
362 for (n=0; n<num_transforms; n++){
366 tmp1 = tmpz[4].
re + (unsigned)tmpz[5].
re;
367 tmp3 = tmpz[6].
re + (unsigned)tmpz[7].
re;
368 tmp2 = tmpz[4].
im + (unsigned)tmpz[5].
im;
369 tmp4 = tmpz[6].
im + (unsigned)tmpz[7].
im;
375 tmp1 = tmpz[4].
re - (unsigned)tmpz[5].
re;
376 tmp2 = tmpz[4].
im - (unsigned)tmpz[5].
im;
377 tmp3 = tmpz[6].
re - (unsigned)tmpz[7].
re;
378 tmp4 = tmpz[6].
im - (unsigned)tmpz[7].
im;
380 tmpz[4].
re = tmpz[0].
re - tmp5;
381 tmpz[0].
re = tmpz[0].
re + tmp5;
382 tmpz[4].
im = tmpz[0].
im - tmp6;
383 tmpz[0].
im = tmpz[0].
im + tmp6;
384 tmpz[6].
re = tmpz[2].
re - tmp8;
385 tmpz[2].
re = tmpz[2].
re + tmp8;
386 tmpz[6].
im = tmpz[2].
im + tmp7;
387 tmpz[2].
im = tmpz[2].
im - tmp7;
390 tmp5 = (
int32_t)((accu + 0x40000000) >> 31);
392 tmp7 = (
int32_t)((accu + 0x40000000) >> 31);
394 tmp6 = (
int32_t)((accu + 0x40000000) >> 31);
396 tmp8 = (
int32_t)((accu + 0x40000000) >> 31);
402 tmpz[5].
re = tmpz[1].
re - tmp1;
403 tmpz[1].
re = tmpz[1].
re + tmp1;
404 tmpz[5].
im = tmpz[1].
im - tmp2;
405 tmpz[1].
im = tmpz[1].
im + tmp2;
406 tmpz[7].
re = tmpz[3].
re - tmp4;
407 tmpz[3].
re = tmpz[3].
re + tmp4;
408 tmpz[7].
im = tmpz[3].
im + tmp3;
409 tmpz[3].
im = tmpz[3].
im - tmp3;
415 for (nbits=4; nbits<=s->
nbits; nbits++){
418 num_transforms = (num_transforms >> 1) | 1;
420 for (n=0; n<num_transforms; n++){
426 tmp5 = tmpz[ n2].
re + (unsigned)tmpz[n34].
re;
427 tmp1 = tmpz[ n2].
re - (unsigned)tmpz[n34].
re;
428 tmp6 = tmpz[ n2].
im + (unsigned)tmpz[n34].
im;
429 tmp2 = tmpz[ n2].
im - (unsigned)tmpz[n34].
im;
431 tmpz[ n2].
re = tmpz[ 0].
re - tmp5;
432 tmpz[ 0].
re = tmpz[ 0].
re + tmp5;
433 tmpz[ n2].
im = tmpz[ 0].
im - tmp6;
434 tmpz[ 0].
im = tmpz[ 0].
im + tmp6;
435 tmpz[n34].
re = tmpz[n4].
re - tmp2;
436 tmpz[ n4].
re = tmpz[n4].
re + tmp2;
437 tmpz[n34].
im = tmpz[n4].
im + tmp1;
438 tmpz[ n4].
im = tmpz[n4].
im - tmp1;
440 for (i=1; i<n4; i++){
443 accu = (int64_t)w_re*tmpz[ n2+i].
re;
444 accu += (int64_t)w_im*tmpz[ n2+i].
im;
445 tmp1 = (
int32_t)((accu + 0x40000000) >> 31);
446 accu = (int64_t)w_re*tmpz[ n2+i].
im;
447 accu -= (int64_t)w_im*tmpz[ n2+i].
re;
448 tmp2 = (
int32_t)((accu + 0x40000000) >> 31);
449 accu = (int64_t)w_re*tmpz[n34+i].
re;
450 accu -= (int64_t)w_im*tmpz[n34+i].
im;
451 tmp3 = (
int32_t)((accu + 0x40000000) >> 31);
452 accu = (int64_t)w_re*tmpz[n34+i].
im;
453 accu += (int64_t)w_im*tmpz[n34+i].
re;
454 tmp4 = (
int32_t)((accu + 0x40000000) >> 31);
461 tmpz[ n2+
i].
re = tmpz[
i].
re - tmp5;
462 tmpz[
i].
re = tmpz[
i].
re + tmp5;
463 tmpz[ n2+
i].
im = tmpz[
i].
im - tmp6;
464 tmpz[
i].
im = tmpz[
i].
im + tmp6;
465 tmpz[n34+
i].
re = tmpz[n4+
i].
re - tmp2;
466 tmpz[ n4+
i].
re = tmpz[n4+
i].
re + tmp2;
467 tmpz[n34+
i].
im = tmpz[n4+
i].
im + tmp1;
468 tmpz[ n4+
i].
im = tmpz[n4+
i].
im - tmp1;
481 #define BUTTERFLIES(a0,a1,a2,a3) {\ 483 BF(a2.re, a0.re, a0.re, t5);\ 484 BF(a3.im, a1.im, a1.im, t3);\ 486 BF(a3.re, a1.re, a1.re, t4);\ 487 BF(a2.im, a0.im, a0.im, t6);\ 493 #define BUTTERFLIES_BIG(a0,a1,a2,a3) {\ 494 FFTSample r0=a0.re, i0=a0.im, r1=a1.re, i1=a1.im;\ 496 BF(a2.re, a0.re, r0, t5);\ 497 BF(a3.im, a1.im, i1, t3);\ 499 BF(a3.re, a1.re, r1, t4);\ 500 BF(a2.im, a0.im, i0, t6);\ 503 #define TRANSFORM(a0,a1,a2,a3,wre,wim) {\ 504 CMUL(t1, t2, a2.re, a2.im, wre, -wim);\ 505 CMUL(t5, t6, a3.re, a3.im, wre, wim);\ 506 BUTTERFLIES(a0,a1,a2,a3)\ 509 #define TRANSFORM_ZERO(a0,a1,a2,a3) {\ 514 BUTTERFLIES(a0,a1,a2,a3)\ 519 static void name(FFTComplex *z, const FFTSample *wre, unsigned int n)\ 521 FFTDouble t1, t2, t3, t4, t5, t6;\ 525 const FFTSample *wim = wre+o1;\ 528 TRANSFORM_ZERO(z[0],z[o1],z[o2],z[o3]);\ 529 TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\ 534 TRANSFORM(z[0],z[o1],z[o2],z[o3],wre[0],wim[0]);\ 535 TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\ 542 #define BUTTERFLIES BUTTERFLIES_BIG 546 #define DECL_FFT(n,n2,n4)\ 547 static void fft##n(FFTComplex *z)\ 552 pass(z,FFT_NAME(ff_cos_##n),n4/2);\ 559 BF(t3, t1, z[0].
re, z[1].re);
560 BF(t8, t6, z[3].re, z[2].re);
561 BF(z[2].re, z[0].re, t1, t6);
562 BF(t4, t2, z[0].
im, z[1].im);
563 BF(t7, t5, z[2].im, z[3].im);
564 BF(z[3].im, z[1].im, t4, t8);
565 BF(z[3].re, z[1].re, t3, t7);
566 BF(z[2].im, z[0].im, t2, t5);
575 BF(t1, z[5].
re, z[4].re, -z[5].re);
576 BF(t2, z[5].
im, z[4].im, -z[5].im);
577 BF(t5, z[7].re, z[6].re, -z[7].re);
578 BF(t6, z[7].im, z[6].im, -z[7].im);
597 TRANSFORM(z[1],z[5],z[9],z[13],cos_16_1,cos_16_3);
598 TRANSFORM(z[3],z[7],z[11],z[15],cos_16_3,cos_16_1);
609 #define pass pass_big 621 fft4,
fft8,
fft16, fft32, fft64, fft128, fft256, fft512, fft1024,
622 fft2048, fft4096, fft8192, fft16384, fft32768, fft65536, fft131072
static void fft_permute_c(FFTContext *s, FFTComplex *z)
#define BUTTERFLIES(a0, a1, a2, a3)
static CosTabsInitOnce cos_tabs_init_once[]
void ff_fft_lut_init(void)
static const int avx_tab[]
#define SPLIT_RADIX_PERMUTATION(num)
static int split_radix_permutation(int i, int n, int inverse)
#define MAX_LOG2_NFFT
Specifies maximum allowed fft size.
av_cold void ff_fft_init_arm(FFTContext *s)
void ff_fft_init_ppc(FFTContext *s)
const int32_t ff_w_tab_sr[MAX_FFT_SIZE/(4 *16)]
#define DECL_FFT(n, n2, n4)
#define INIT_FF_COS_TABS_FUNC(index, size)
static void(*const fft_dispatch[])(FFTComplex *)
#define i(width, name, range_min, range_max)
void(* fft_permute)(struct FFTContext *s, FFTComplex *z)
Do the permutation needed BEFORE calling fft_calc().
void(* mdct_calcw)(struct FFTContext *s, FFTDouble *output, const FFTSample *input)
void(* mdct_calc)(struct FFTContext *s, FFTSample *output, const FFTSample *input)
void(* imdct_calc)(struct FFTContext *s, FFTSample *output, const FFTSample *input)
static const uint8_t offset[127][2]
av_cold void ff_fft_fixed_init_arm(FFTContext *s)
static av_cold void fft_perm_avx(FFTContext *s)
av_cold int ff_fft_init(FFTContext *s, int nbits, int inverse)
Set up a complex FFT.
enum fft_permutation_type fft_permutation
static int is_second_half_of_fft32(int i, int n)
typedef void(RENAME(mix_any_func_type))
uint16_t ff_fft_offsets_lut[21845]
static av_cold void init_ff_cos_tabs(int index)
void(* imdct_half)(struct FFTContext *s, FFTSample *output, const FFTSample *input)
#define TRANSFORM(a0, a1, a2, a3, wre, wim)
#define TRANSFORM_ZERO(a0, a1, a2, a3)
static void fft4(FFTComplex *z)
av_cold void ff_fft_end(FFTContext *s)
void ff_mdct_calcw_c(FFTContext *s, FFTDouble *output, const FFTSample *input)
av_cold void ff_fft_init_aarch64(FFTContext *s)
void(* fft_calc)(struct FFTContext *s, FFTComplex *z)
Do a complex FFT with the parameters defined in ff_fft_init().
void ff_fft_init_mips(FFTContext *s)
FFT transform.
static int ff_thread_once(char *control, void(*routine)(void))
static void fft8(FFTComplex *z)
COSTABLE_CONST FFTSample *const FFT_NAME(ff_cos_tabs)[]
static const struct twinvq_data tab
static uint32_t inverse(uint32_t v)
find multiplicative inverse modulo 2 ^ 32
av_cold void ff_init_ff_cos_tabs(int index)
Initialize the cosine table in ff_cos_tabs[index].
static void fft_calc_c(FFTContext *s, FFTComplex *z)
static void fft16(FFTComplex *z)
definitions and tables for FFT
void ff_fft_init_x86(FFTContext *s)