39 static void av_cold fft_lut_init(
void)
48 #if !CONFIG_HARDCODED_TABLES 68 double freq = 2*
M_PI/m;
71 tab[i] =
FIX15(cos(i*freq));
81 #define INIT_FF_COS_TABS_FUNC(index, size) \ 82 static av_cold void init_ff_cos_tabs_ ## size (void)\ 84 init_ff_cos_tabs(index); \ 108 { init_ff_cos_tabs_32, AV_ONCE_INIT },
109 { init_ff_cos_tabs_64, AV_ONCE_INIT },
110 { init_ff_cos_tabs_128, AV_ONCE_INIT },
111 { init_ff_cos_tabs_256, AV_ONCE_INIT },
112 { init_ff_cos_tabs_512, AV_ONCE_INIT },
113 { init_ff_cos_tabs_1024, AV_ONCE_INIT },
114 { init_ff_cos_tabs_2048, AV_ONCE_INIT },
115 { init_ff_cos_tabs_4096, AV_ONCE_INIT },
116 { init_ff_cos_tabs_8192, AV_ONCE_INIT },
117 { init_ff_cos_tabs_16384, AV_ONCE_INIT },
118 { init_ff_cos_tabs_32768, AV_ONCE_INIT },
119 { init_ff_cos_tabs_65536, AV_ONCE_INIT },
120 { init_ff_cos_tabs_131072, AV_ONCE_INIT },
150 if(n <= 2)
return i&1;
160 #if (!CONFIG_HARDCODED_TABLES) && (!FFT_FIXED_32) 166 0, 4, 1, 5, 8, 12, 9, 13, 2, 6, 3, 7, 10, 14, 11, 15
184 int n = 1 << s->
nbits;
186 for (i = 0; i < n; i += 16) {
189 for (k = 0; k < 16; k++)
194 for (k = 0; k < 16; k++) {
196 j = (j & ~7) | ((j >> 1) & 3) | ((j << 2) & 4);
210 if (nbits < 2 || nbits > 17)
255 for(j=4; j<=nbits; j++) {
264 #define PROCESS_FFT_PERM_SWAP_LSBS(num) do {\ 265 for(i = 0; i < n; i++) {\ 268 j = (j & ~3) | ((j >> 1) & 1) | ((j << 1) & 2);\ 269 k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\ 270 s->revtab##num[k] = j;\ 274 #define PROCESS_FFT_PERM_DEFAULT(num) do {\ 275 for(i = 0; i < n; i++) {\ 278 k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\ 279 s->revtab##num[k] = j;\ 283 #define SPLIT_RADIX_PERMUTATION(num) do { \ 284 if (s->fft_permutation == FF_FFT_PERM_SWAP_LSBS) {\ 285 PROCESS_FFT_PERM_SWAP_LSBS(num) \ 287 PROCESS_FFT_PERM_DEFAULT(num) \ 296 #undef PROCESS_FFT_PERM_DEFAULT 297 #undef PROCESS_FFT_PERM_SWAP_LSBS 298 #undef SPLIT_RADIX_PERMUTATION 312 const uint16_t *revtab = s->
revtab;
313 const uint32_t *revtab32 = s->
revtab32;
317 for(j=0;j<np;j++) s->
tmp_buf[revtab[j]] = z[j];
319 for(j=0;j<np;j++) s->
tmp_buf[revtab32[j]] = z[j];
335 int nbits,
i, n, num_transforms,
offset, step;
337 unsigned tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8;
339 const int fft_size = (1 << s->
nbits);
342 num_transforms = (0x2aab >> (16 - s->
nbits)) | 1;
344 for (n=0; n<num_transforms; n++){
348 tmp1 = tmpz[0].
re + (unsigned)tmpz[1].
re;
349 tmp5 = tmpz[2].
re + (unsigned)tmpz[3].
re;
350 tmp2 = tmpz[0].
im + (unsigned)tmpz[1].
im;
351 tmp6 = tmpz[2].
im + (unsigned)tmpz[3].
im;
352 tmp3 = tmpz[0].
re - (unsigned)tmpz[1].
re;
353 tmp8 = tmpz[2].
im - (unsigned)tmpz[3].
im;
354 tmp4 = tmpz[0].
im - (unsigned)tmpz[1].
im;
355 tmp7 = tmpz[2].
re - (unsigned)tmpz[3].
re;
357 tmpz[0].
re = tmp1 + tmp5;
358 tmpz[2].
re = tmp1 - tmp5;
359 tmpz[0].
im = tmp2 + tmp6;
360 tmpz[2].
im = tmp2 - tmp6;
361 tmpz[1].
re = tmp3 + tmp8;
362 tmpz[3].
re = tmp3 - tmp8;
363 tmpz[1].
im = tmp4 - tmp7;
364 tmpz[3].
im = tmp4 + tmp7;
370 num_transforms = (num_transforms >> 1) | 1;
372 for (n=0; n<num_transforms; n++){
376 tmp1 = tmpz[4].
re + (unsigned)tmpz[5].
re;
377 tmp3 = tmpz[6].
re + (unsigned)tmpz[7].
re;
378 tmp2 = tmpz[4].
im + (unsigned)tmpz[5].
im;
379 tmp4 = tmpz[6].
im + (unsigned)tmpz[7].
im;
385 tmp1 = tmpz[4].
re - (unsigned)tmpz[5].
re;
386 tmp2 = tmpz[4].
im - (unsigned)tmpz[5].
im;
387 tmp3 = tmpz[6].
re - (unsigned)tmpz[7].
re;
388 tmp4 = tmpz[6].
im - (unsigned)tmpz[7].
im;
390 tmpz[4].
re = tmpz[0].
re - tmp5;
391 tmpz[0].
re = tmpz[0].
re + tmp5;
392 tmpz[4].
im = tmpz[0].
im - tmp6;
393 tmpz[0].
im = tmpz[0].
im + tmp6;
394 tmpz[6].
re = tmpz[2].
re - tmp8;
395 tmpz[2].
re = tmpz[2].
re + tmp8;
396 tmpz[6].
im = tmpz[2].
im + tmp7;
397 tmpz[2].
im = tmpz[2].
im - tmp7;
400 tmp5 = (
int32_t)((accu + 0x40000000) >> 31);
402 tmp7 = (
int32_t)((accu + 0x40000000) >> 31);
404 tmp6 = (
int32_t)((accu + 0x40000000) >> 31);
406 tmp8 = (
int32_t)((accu + 0x40000000) >> 31);
412 tmpz[5].
re = tmpz[1].
re - tmp1;
413 tmpz[1].
re = tmpz[1].
re + tmp1;
414 tmpz[5].
im = tmpz[1].
im - tmp2;
415 tmpz[1].
im = tmpz[1].
im + tmp2;
416 tmpz[7].
re = tmpz[3].
re - tmp4;
417 tmpz[3].
re = tmpz[3].
re + tmp4;
418 tmpz[7].
im = tmpz[3].
im + tmp3;
419 tmpz[3].
im = tmpz[3].
im - tmp3;
425 for (nbits=4; nbits<=s->
nbits; nbits++){
428 num_transforms = (num_transforms >> 1) | 1;
430 for (n=0; n<num_transforms; n++){
436 tmp5 = tmpz[ n2].
re + (unsigned)tmpz[n34].
re;
437 tmp1 = tmpz[ n2].
re - (unsigned)tmpz[n34].
re;
438 tmp6 = tmpz[ n2].
im + (unsigned)tmpz[n34].
im;
439 tmp2 = tmpz[ n2].
im - (unsigned)tmpz[n34].
im;
441 tmpz[ n2].
re = tmpz[ 0].
re - tmp5;
442 tmpz[ 0].
re = tmpz[ 0].
re + tmp5;
443 tmpz[ n2].
im = tmpz[ 0].
im - tmp6;
444 tmpz[ 0].
im = tmpz[ 0].
im + tmp6;
445 tmpz[n34].
re = tmpz[n4].
re - tmp2;
446 tmpz[ n4].
re = tmpz[n4].
re + tmp2;
447 tmpz[n34].
im = tmpz[n4].
im + tmp1;
448 tmpz[ n4].
im = tmpz[n4].
im - tmp1;
450 for (i=1; i<n4; i++){
453 accu = (int64_t)w_re*tmpz[ n2+i].
re;
454 accu += (int64_t)w_im*tmpz[ n2+i].
im;
455 tmp1 = (
int32_t)((accu + 0x40000000) >> 31);
456 accu = (int64_t)w_re*tmpz[ n2+i].
im;
457 accu -= (int64_t)w_im*tmpz[ n2+i].
re;
458 tmp2 = (
int32_t)((accu + 0x40000000) >> 31);
459 accu = (int64_t)w_re*tmpz[n34+i].
re;
460 accu -= (int64_t)w_im*tmpz[n34+i].
im;
461 tmp3 = (
int32_t)((accu + 0x40000000) >> 31);
462 accu = (int64_t)w_re*tmpz[n34+i].
im;
463 accu += (int64_t)w_im*tmpz[n34+i].
re;
464 tmp4 = (
int32_t)((accu + 0x40000000) >> 31);
471 tmpz[ n2+
i].
re = tmpz[
i].
re - tmp5;
472 tmpz[
i].
re = tmpz[
i].
re + tmp5;
473 tmpz[ n2+
i].
im = tmpz[
i].
im - tmp6;
474 tmpz[
i].
im = tmpz[
i].
im + tmp6;
475 tmpz[n34+
i].
re = tmpz[n4+
i].
re - tmp2;
476 tmpz[ n4+
i].
re = tmpz[n4+
i].
re + tmp2;
477 tmpz[n34+
i].
im = tmpz[n4+
i].
im + tmp1;
478 tmpz[ n4+
i].
im = tmpz[n4+
i].
im - tmp1;
491 #define BUTTERFLIES(a0,a1,a2,a3) {\ 493 BF(a2.re, a0.re, a0.re, t5);\ 494 BF(a3.im, a1.im, a1.im, t3);\ 496 BF(a3.re, a1.re, a1.re, t4);\ 497 BF(a2.im, a0.im, a0.im, t6);\ 503 #define BUTTERFLIES_BIG(a0,a1,a2,a3) {\ 504 FFTSample r0=a0.re, i0=a0.im, r1=a1.re, i1=a1.im;\ 506 BF(a2.re, a0.re, r0, t5);\ 507 BF(a3.im, a1.im, i1, t3);\ 509 BF(a3.re, a1.re, r1, t4);\ 510 BF(a2.im, a0.im, i0, t6);\ 513 #define TRANSFORM(a0,a1,a2,a3,wre,wim) {\ 514 CMUL(t1, t2, a2.re, a2.im, wre, -wim);\ 515 CMUL(t5, t6, a3.re, a3.im, wre, wim);\ 516 BUTTERFLIES(a0,a1,a2,a3)\ 519 #define TRANSFORM_ZERO(a0,a1,a2,a3) {\ 524 BUTTERFLIES(a0,a1,a2,a3)\ 529 static void name(FFTComplex *z, const FFTSample *wre, unsigned int n)\ 531 FFTDouble t1, t2, t3, t4, t5, t6;\ 535 const FFTSample *wim = wre+o1;\ 538 TRANSFORM_ZERO(z[0],z[o1],z[o2],z[o3]);\ 539 TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\ 544 TRANSFORM(z[0],z[o1],z[o2],z[o3],wre[0],wim[0]);\ 545 TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\ 552 #define BUTTERFLIES BUTTERFLIES_BIG 556 #define DECL_FFT(n,n2,n4)\ 557 static void fft##n(FFTComplex *z)\ 562 pass(z,FFT_NAME(ff_cos_##n),n4/2);\ 569 BF(t3, t1, z[0].
re, z[1].re);
570 BF(t8, t6, z[3].re, z[2].re);
571 BF(z[2].re, z[0].re, t1, t6);
572 BF(t4, t2, z[0].
im, z[1].im);
573 BF(t7, t5, z[2].im, z[3].im);
574 BF(z[3].im, z[1].im, t4, t8);
575 BF(z[3].re, z[1].re, t3, t7);
576 BF(z[2].im, z[0].im, t2, t5);
585 BF(t1, z[5].
re, z[4].re, -z[5].re);
586 BF(t2, z[5].
im, z[4].im, -z[5].im);
587 BF(t5, z[7].re, z[6].re, -z[7].re);
588 BF(t6, z[7].im, z[6].im, -z[7].im);
607 TRANSFORM(z[1],z[5],z[9],z[13],cos_16_1,cos_16_3);
608 TRANSFORM(z[3],z[7],z[11],z[15],cos_16_3,cos_16_1);
619 #define pass pass_big 631 fft4,
fft8,
fft16, fft32, fft64, fft128, fft256, fft512, fft1024,
632 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[]
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.
void ff_fft_lut_init(uint16_t *table, int off, int size, int *index)
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)