FFmpeg
fft_template.c
Go to the documentation of this file.
1 /*
2  * FFT/IFFT transforms
3  * Copyright (c) 2008 Loren Merritt
4  * Copyright (c) 2002 Fabrice Bellard
5  * Partly based on libdjbfft by D. J. Bernstein
6  *
7  * This file is part of FFmpeg.
8  *
9  * FFmpeg is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Lesser General Public
11  * License as published by the Free Software Foundation; either
12  * version 2.1 of the License, or (at your option) any later version.
13  *
14  * FFmpeg is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  * Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public
20  * License along with FFmpeg; if not, write to the Free Software
21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22  */
23 
24 /**
25  * @file
26  * FFT/IFFT transforms.
27  */
28 
29 #include <stdlib.h>
30 #include <string.h>
31 #include "libavutil/mathematics.h"
32 #include "libavutil/thread.h"
33 #include "fft.h"
34 #include "fft-internal.h"
35 
36 #if FFT_FIXED_32
37 #include "fft_table.h"
38 #else /* FFT_FIXED_32 */
39 
40 /* cos(2*pi*x/n) for 0<=x<=n/4, followed by its reverse */
41 #if !CONFIG_HARDCODED_TABLES
42 COSTABLE(16);
43 COSTABLE(32);
44 COSTABLE(64);
45 COSTABLE(128);
46 COSTABLE(256);
47 COSTABLE(512);
48 COSTABLE(1024);
49 COSTABLE(2048);
50 COSTABLE(4096);
51 COSTABLE(8192);
52 COSTABLE(16384);
53 COSTABLE(32768);
54 COSTABLE(65536);
55 COSTABLE(131072);
56 
57 static av_cold void init_ff_cos_tabs(int index)
58 {
59  int i;
60  int m = 1<<index;
61  double freq = 2*M_PI/m;
62  FFTSample *tab = FFT_NAME(ff_cos_tabs)[index];
63  for(i=0; i<=m/4; i++)
64  tab[i] = FIX15(cos(i*freq));
65  for(i=1; i<m/4; i++)
66  tab[m/2-i] = tab[i];
67 }
68 
69 typedef struct CosTabsInitOnce {
70  void (*func)(void);
73 
74 #define INIT_FF_COS_TABS_FUNC(index, size) \
75 static av_cold void init_ff_cos_tabs_ ## size (void)\
76 { \
77  init_ff_cos_tabs(index); \
78 }
79 
86 INIT_FF_COS_TABS_FUNC(10, 1024)
87 INIT_FF_COS_TABS_FUNC(11, 2048)
88 INIT_FF_COS_TABS_FUNC(12, 4096)
89 INIT_FF_COS_TABS_FUNC(13, 8192)
90 INIT_FF_COS_TABS_FUNC(14, 16384)
91 INIT_FF_COS_TABS_FUNC(15, 32768)
92 INIT_FF_COS_TABS_FUNC(16, 65536)
93 INIT_FF_COS_TABS_FUNC(17, 131072)
94 
96  { NULL },
97  { NULL },
98  { NULL },
99  { NULL },
100  { init_ff_cos_tabs_16, AV_ONCE_INIT },
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 },
114 };
115 
116 #endif
117 COSTABLE_CONST FFTSample * const FFT_NAME(ff_cos_tabs)[] = {
118  NULL, NULL, NULL, NULL,
119  FFT_NAME(ff_cos_16),
120  FFT_NAME(ff_cos_32),
121  FFT_NAME(ff_cos_64),
122  FFT_NAME(ff_cos_128),
123  FFT_NAME(ff_cos_256),
124  FFT_NAME(ff_cos_512),
125  FFT_NAME(ff_cos_1024),
126  FFT_NAME(ff_cos_2048),
127  FFT_NAME(ff_cos_4096),
128  FFT_NAME(ff_cos_8192),
129  FFT_NAME(ff_cos_16384),
130  FFT_NAME(ff_cos_32768),
131  FFT_NAME(ff_cos_65536),
132  FFT_NAME(ff_cos_131072),
133 };
134 
135 #endif /* FFT_FIXED_32 */
136 
137 static void fft_permute_c(FFTContext *s, FFTComplex *z);
138 static void fft_calc_c(FFTContext *s, FFTComplex *z);
139 
140 static int split_radix_permutation(int i, int n, int inverse)
141 {
142  int m;
143  if(n <= 2) return i&1;
144  m = n >> 1;
145  if(!(i&m)) return split_radix_permutation(i, m, inverse)*2;
146  m >>= 1;
147  if(inverse == !(i&m)) return split_radix_permutation(i, m, inverse)*4 + 1;
148  else return split_radix_permutation(i, m, inverse)*4 - 1;
149 }
150 
152 {
153 #if (!CONFIG_HARDCODED_TABLES) && (!FFT_FIXED_32)
155 #endif
156 }
157 
158 static const int avx_tab[] = {
159  0, 4, 1, 5, 8, 12, 9, 13, 2, 6, 3, 7, 10, 14, 11, 15
160 };
161 
162 static int is_second_half_of_fft32(int i, int n)
163 {
164  if (n <= 32)
165  return i >= 16;
166  else if (i < n/2)
167  return is_second_half_of_fft32(i, n/2);
168  else if (i < 3*n/4)
169  return is_second_half_of_fft32(i - n/2, n/4);
170  else
171  return is_second_half_of_fft32(i - 3*n/4, n/4);
172 }
173 
175 {
176  int i;
177  int n = 1 << s->nbits;
178 
179  for (i = 0; i < n; i += 16) {
180  int k;
181  if (is_second_half_of_fft32(i, n)) {
182  for (k = 0; k < 16; k++)
183  s->revtab[-split_radix_permutation(i + k, n, s->inverse) & (n - 1)] =
184  i + avx_tab[k];
185 
186  } else {
187  for (k = 0; k < 16; k++) {
188  int j = i + k;
189  j = (j & ~7) | ((j >> 1) & 3) | ((j << 2) & 4);
190  s->revtab[-split_radix_permutation(i + k, n, s->inverse) & (n - 1)] = j;
191  }
192  }
193  }
194 }
195 
196 av_cold int ff_fft_init(FFTContext *s, int nbits, int inverse)
197 {
198  int i, j, n;
199 
200  s->revtab = NULL;
201  s->revtab32 = NULL;
202 
203  if (nbits < 2 || nbits > 17)
204  goto fail;
205  s->nbits = nbits;
206  n = 1 << nbits;
207 
208  if (nbits <= 16) {
209  s->revtab = av_malloc(n * sizeof(uint16_t));
210  if (!s->revtab)
211  goto fail;
212  } else {
213  s->revtab32 = av_malloc(n * sizeof(uint32_t));
214  if (!s->revtab32)
215  goto fail;
216  }
217  s->tmp_buf = av_malloc(n * sizeof(FFTComplex));
218  if (!s->tmp_buf)
219  goto fail;
220  s->inverse = inverse;
222 
224  s->fft_calc = fft_calc_c;
225 #if CONFIG_MDCT
229 #endif
230 
231 #if FFT_FIXED_32
232  ff_fft_lut_init();
233 #else /* FFT_FIXED_32 */
234 #if FFT_FLOAT
235  if (ARCH_AARCH64) ff_fft_init_aarch64(s);
236  if (ARCH_ARM) ff_fft_init_arm(s);
237  if (ARCH_PPC) ff_fft_init_ppc(s);
238  if (ARCH_X86) ff_fft_init_x86(s);
239  if (HAVE_MIPSFPU) ff_fft_init_mips(s);
240 #endif
241  for(j=4; j<=nbits; j++) {
243  }
244 #endif /* FFT_FIXED_32 */
245 
246 
247  if (ARCH_X86 && FFT_FLOAT && s->fft_permutation == FF_FFT_PERM_AVX) {
248  fft_perm_avx(s);
249  } else {
250 #define PROCESS_FFT_PERM_SWAP_LSBS(num) do {\
251  for(i = 0; i < n; i++) {\
252  int k;\
253  j = i;\
254  j = (j & ~3) | ((j >> 1) & 1) | ((j << 1) & 2);\
255  k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\
256  s->revtab##num[k] = j;\
257  } \
258 } while(0);
259 
260 #define PROCESS_FFT_PERM_DEFAULT(num) do {\
261  for(i = 0; i < n; i++) {\
262  int k;\
263  j = i;\
264  k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\
265  s->revtab##num[k] = j;\
266  } \
267 } while(0);
268 
269 #define SPLIT_RADIX_PERMUTATION(num) do { \
270  if (s->fft_permutation == FF_FFT_PERM_SWAP_LSBS) {\
271  PROCESS_FFT_PERM_SWAP_LSBS(num) \
272  } else {\
273  PROCESS_FFT_PERM_DEFAULT(num) \
274  }\
275 } while(0);
276 
277  if (s->revtab)
279  if (s->revtab32)
281 
282 #undef PROCESS_FFT_PERM_DEFAULT
283 #undef PROCESS_FFT_PERM_SWAP_LSBS
284 #undef SPLIT_RADIX_PERMUTATION
285  }
286 
287  return 0;
288  fail:
289  av_freep(&s->revtab);
290  av_freep(&s->revtab32);
291  av_freep(&s->tmp_buf);
292  return -1;
293 }
294 
296 {
297  int j, np;
298  const uint16_t *revtab = s->revtab;
299  const uint32_t *revtab32 = s->revtab32;
300  np = 1 << s->nbits;
301  /* TODO: handle split-radix permute in a more optimal way, probably in-place */
302  if (revtab) {
303  for(j=0;j<np;j++) s->tmp_buf[revtab[j]] = z[j];
304  } else
305  for(j=0;j<np;j++) s->tmp_buf[revtab32[j]] = z[j];
306 
307  memcpy(z, s->tmp_buf, np * sizeof(FFTComplex));
308 }
309 
311 {
312  av_freep(&s->revtab);
313  av_freep(&s->revtab32);
314  av_freep(&s->tmp_buf);
315 }
316 
317 #if FFT_FIXED_32
318 
319 static void fft_calc_c(FFTContext *s, FFTComplex *z) {
320 
321  int nbits, i, n, num_transforms, offset, step;
322  int n4, n2, n34;
323  unsigned tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8;
324  FFTComplex *tmpz;
325  const int fft_size = (1 << s->nbits);
326  int64_t accu;
327 
328  num_transforms = (0x2aab >> (16 - s->nbits)) | 1;
329 
330  for (n=0; n<num_transforms; n++){
331  offset = ff_fft_offsets_lut[n] << 2;
332  tmpz = z + offset;
333 
334  tmp1 = tmpz[0].re + (unsigned)tmpz[1].re;
335  tmp5 = tmpz[2].re + (unsigned)tmpz[3].re;
336  tmp2 = tmpz[0].im + (unsigned)tmpz[1].im;
337  tmp6 = tmpz[2].im + (unsigned)tmpz[3].im;
338  tmp3 = tmpz[0].re - (unsigned)tmpz[1].re;
339  tmp8 = tmpz[2].im - (unsigned)tmpz[3].im;
340  tmp4 = tmpz[0].im - (unsigned)tmpz[1].im;
341  tmp7 = tmpz[2].re - (unsigned)tmpz[3].re;
342 
343  tmpz[0].re = tmp1 + tmp5;
344  tmpz[2].re = tmp1 - tmp5;
345  tmpz[0].im = tmp2 + tmp6;
346  tmpz[2].im = tmp2 - tmp6;
347  tmpz[1].re = tmp3 + tmp8;
348  tmpz[3].re = tmp3 - tmp8;
349  tmpz[1].im = tmp4 - tmp7;
350  tmpz[3].im = tmp4 + tmp7;
351  }
352 
353  if (fft_size < 8)
354  return;
355 
356  num_transforms = (num_transforms >> 1) | 1;
357 
358  for (n=0; n<num_transforms; n++){
359  offset = ff_fft_offsets_lut[n] << 3;
360  tmpz = z + offset;
361 
362  tmp1 = tmpz[4].re + (unsigned)tmpz[5].re;
363  tmp3 = tmpz[6].re + (unsigned)tmpz[7].re;
364  tmp2 = tmpz[4].im + (unsigned)tmpz[5].im;
365  tmp4 = tmpz[6].im + (unsigned)tmpz[7].im;
366  tmp5 = tmp1 + tmp3;
367  tmp7 = tmp1 - tmp3;
368  tmp6 = tmp2 + tmp4;
369  tmp8 = tmp2 - tmp4;
370 
371  tmp1 = tmpz[4].re - (unsigned)tmpz[5].re;
372  tmp2 = tmpz[4].im - (unsigned)tmpz[5].im;
373  tmp3 = tmpz[6].re - (unsigned)tmpz[7].re;
374  tmp4 = tmpz[6].im - (unsigned)tmpz[7].im;
375 
376  tmpz[4].re = tmpz[0].re - tmp5;
377  tmpz[0].re = tmpz[0].re + tmp5;
378  tmpz[4].im = tmpz[0].im - tmp6;
379  tmpz[0].im = tmpz[0].im + tmp6;
380  tmpz[6].re = tmpz[2].re - tmp8;
381  tmpz[2].re = tmpz[2].re + tmp8;
382  tmpz[6].im = tmpz[2].im + tmp7;
383  tmpz[2].im = tmpz[2].im - tmp7;
384 
385  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp1 + tmp2);
386  tmp5 = (int32_t)((accu + 0x40000000) >> 31);
387  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp3 - tmp4);
388  tmp7 = (int32_t)((accu + 0x40000000) >> 31);
389  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp2 - tmp1);
390  tmp6 = (int32_t)((accu + 0x40000000) >> 31);
391  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp3 + tmp4);
392  tmp8 = (int32_t)((accu + 0x40000000) >> 31);
393  tmp1 = tmp5 + tmp7;
394  tmp3 = tmp5 - tmp7;
395  tmp2 = tmp6 + tmp8;
396  tmp4 = tmp6 - tmp8;
397 
398  tmpz[5].re = tmpz[1].re - tmp1;
399  tmpz[1].re = tmpz[1].re + tmp1;
400  tmpz[5].im = tmpz[1].im - tmp2;
401  tmpz[1].im = tmpz[1].im + tmp2;
402  tmpz[7].re = tmpz[3].re - tmp4;
403  tmpz[3].re = tmpz[3].re + tmp4;
404  tmpz[7].im = tmpz[3].im + tmp3;
405  tmpz[3].im = tmpz[3].im - tmp3;
406  }
407 
408  step = 1 << ((MAX_LOG2_NFFT-4) - 4);
409  n4 = 4;
410 
411  for (nbits=4; nbits<=s->nbits; nbits++){
412  n2 = 2*n4;
413  n34 = 3*n4;
414  num_transforms = (num_transforms >> 1) | 1;
415 
416  for (n=0; n<num_transforms; n++){
417  const FFTSample *w_re_ptr = ff_w_tab_sr + step;
418  const FFTSample *w_im_ptr = ff_w_tab_sr + MAX_FFT_SIZE/(4*16) - step;
419  offset = ff_fft_offsets_lut[n] << nbits;
420  tmpz = z + offset;
421 
422  tmp5 = tmpz[ n2].re + (unsigned)tmpz[n34].re;
423  tmp1 = tmpz[ n2].re - (unsigned)tmpz[n34].re;
424  tmp6 = tmpz[ n2].im + (unsigned)tmpz[n34].im;
425  tmp2 = tmpz[ n2].im - (unsigned)tmpz[n34].im;
426 
427  tmpz[ n2].re = tmpz[ 0].re - tmp5;
428  tmpz[ 0].re = tmpz[ 0].re + tmp5;
429  tmpz[ n2].im = tmpz[ 0].im - tmp6;
430  tmpz[ 0].im = tmpz[ 0].im + tmp6;
431  tmpz[n34].re = tmpz[n4].re - tmp2;
432  tmpz[ n4].re = tmpz[n4].re + tmp2;
433  tmpz[n34].im = tmpz[n4].im + tmp1;
434  tmpz[ n4].im = tmpz[n4].im - tmp1;
435 
436  for (i=1; i<n4; i++){
437  FFTSample w_re = w_re_ptr[0];
438  FFTSample w_im = w_im_ptr[0];
439  accu = (int64_t)w_re*tmpz[ n2+i].re;
440  accu += (int64_t)w_im*tmpz[ n2+i].im;
441  tmp1 = (int32_t)((accu + 0x40000000) >> 31);
442  accu = (int64_t)w_re*tmpz[ n2+i].im;
443  accu -= (int64_t)w_im*tmpz[ n2+i].re;
444  tmp2 = (int32_t)((accu + 0x40000000) >> 31);
445  accu = (int64_t)w_re*tmpz[n34+i].re;
446  accu -= (int64_t)w_im*tmpz[n34+i].im;
447  tmp3 = (int32_t)((accu + 0x40000000) >> 31);
448  accu = (int64_t)w_re*tmpz[n34+i].im;
449  accu += (int64_t)w_im*tmpz[n34+i].re;
450  tmp4 = (int32_t)((accu + 0x40000000) >> 31);
451 
452  tmp5 = tmp1 + tmp3;
453  tmp1 = tmp1 - tmp3;
454  tmp6 = tmp2 + tmp4;
455  tmp2 = tmp2 - tmp4;
456 
457  tmpz[ n2+i].re = tmpz[ i].re - tmp5;
458  tmpz[ i].re = tmpz[ i].re + tmp5;
459  tmpz[ n2+i].im = tmpz[ i].im - tmp6;
460  tmpz[ i].im = tmpz[ i].im + tmp6;
461  tmpz[n34+i].re = tmpz[n4+i].re - tmp2;
462  tmpz[ n4+i].re = tmpz[n4+i].re + tmp2;
463  tmpz[n34+i].im = tmpz[n4+i].im + tmp1;
464  tmpz[ n4+i].im = tmpz[n4+i].im - tmp1;
465 
466  w_re_ptr += step;
467  w_im_ptr -= step;
468  }
469  }
470  step >>= 1;
471  n4 <<= 1;
472  }
473 }
474 
475 #else /* FFT_FIXED_32 */
476 
477 #define BUTTERFLIES(a0,a1,a2,a3) {\
478  BF(t3, t5, t5, t1);\
479  BF(a2.re, a0.re, a0.re, t5);\
480  BF(a3.im, a1.im, a1.im, t3);\
481  BF(t4, t6, t2, t6);\
482  BF(a3.re, a1.re, a1.re, t4);\
483  BF(a2.im, a0.im, a0.im, t6);\
484 }
485 
486 // force loading all the inputs before storing any.
487 // this is slightly slower for small data, but avoids store->load aliasing
488 // for addresses separated by large powers of 2.
489 #define BUTTERFLIES_BIG(a0,a1,a2,a3) {\
490  FFTSample r0=a0.re, i0=a0.im, r1=a1.re, i1=a1.im;\
491  BF(t3, t5, t5, t1);\
492  BF(a2.re, a0.re, r0, t5);\
493  BF(a3.im, a1.im, i1, t3);\
494  BF(t4, t6, t2, t6);\
495  BF(a3.re, a1.re, r1, t4);\
496  BF(a2.im, a0.im, i0, t6);\
497 }
498 
499 #define TRANSFORM(a0,a1,a2,a3,wre,wim) {\
500  CMUL(t1, t2, a2.re, a2.im, wre, -wim);\
501  CMUL(t5, t6, a3.re, a3.im, wre, wim);\
502  BUTTERFLIES(a0,a1,a2,a3)\
503 }
504 
505 #define TRANSFORM_ZERO(a0,a1,a2,a3) {\
506  t1 = a2.re;\
507  t2 = a2.im;\
508  t5 = a3.re;\
509  t6 = a3.im;\
510  BUTTERFLIES(a0,a1,a2,a3)\
511 }
512 
513 /* z[0...8n-1], w[1...2n-1] */
514 #define PASS(name)\
515 static void name(FFTComplex *z, const FFTSample *wre, unsigned int n)\
516 {\
517  FFTDouble t1, t2, t3, t4, t5, t6;\
518  int o1 = 2*n;\
519  int o2 = 4*n;\
520  int o3 = 6*n;\
521  const FFTSample *wim = wre+o1;\
522  n--;\
523 \
524  TRANSFORM_ZERO(z[0],z[o1],z[o2],z[o3]);\
525  TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\
526  do {\
527  z += 2;\
528  wre += 2;\
529  wim -= 2;\
530  TRANSFORM(z[0],z[o1],z[o2],z[o3],wre[0],wim[0]);\
531  TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\
532  } while(--n);\
533 }
534 
535 PASS(pass)
536 #if !CONFIG_SMALL
537 #undef BUTTERFLIES
538 #define BUTTERFLIES BUTTERFLIES_BIG
539 PASS(pass_big)
540 #endif
541 
542 #define DECL_FFT(n,n2,n4)\
543 static void fft##n(FFTComplex *z)\
544 {\
545  fft##n2(z);\
546  fft##n4(z+n4*2);\
547  fft##n4(z+n4*3);\
548  pass(z,FFT_NAME(ff_cos_##n),n4/2);\
549 }
550 
551 static void fft4(FFTComplex *z)
552 {
553  FFTDouble t1, t2, t3, t4, t5, t6, t7, t8;
554 
555  BF(t3, t1, z[0].re, z[1].re);
556  BF(t8, t6, z[3].re, z[2].re);
557  BF(z[2].re, z[0].re, t1, t6);
558  BF(t4, t2, z[0].im, z[1].im);
559  BF(t7, t5, z[2].im, z[3].im);
560  BF(z[3].im, z[1].im, t4, t8);
561  BF(z[3].re, z[1].re, t3, t7);
562  BF(z[2].im, z[0].im, t2, t5);
563 }
564 
565 static void fft8(FFTComplex *z)
566 {
567  FFTDouble t1, t2, t3, t4, t5, t6;
568 
569  fft4(z);
570 
571  BF(t1, z[5].re, z[4].re, -z[5].re);
572  BF(t2, z[5].im, z[4].im, -z[5].im);
573  BF(t5, z[7].re, z[6].re, -z[7].re);
574  BF(t6, z[7].im, z[6].im, -z[7].im);
575 
576  BUTTERFLIES(z[0],z[2],z[4],z[6]);
577  TRANSFORM(z[1],z[3],z[5],z[7],sqrthalf,sqrthalf);
578 }
579 
580 #if !CONFIG_SMALL
581 static void fft16(FFTComplex *z)
582 {
583  FFTDouble t1, t2, t3, t4, t5, t6;
584  FFTSample cos_16_1 = FFT_NAME(ff_cos_16)[1];
585  FFTSample cos_16_3 = FFT_NAME(ff_cos_16)[3];
586 
587  fft8(z);
588  fft4(z+8);
589  fft4(z+12);
590 
591  TRANSFORM_ZERO(z[0],z[4],z[8],z[12]);
592  TRANSFORM(z[2],z[6],z[10],z[14],sqrthalf,sqrthalf);
593  TRANSFORM(z[1],z[5],z[9],z[13],cos_16_1,cos_16_3);
594  TRANSFORM(z[3],z[7],z[11],z[15],cos_16_3,cos_16_1);
595 }
596 #else
597 DECL_FFT(16,8,4)
598 #endif
599 DECL_FFT(32,16,8)
600 DECL_FFT(64,32,16)
601 DECL_FFT(128,64,32)
602 DECL_FFT(256,128,64)
603 DECL_FFT(512,256,128)
604 #if !CONFIG_SMALL
605 #define pass pass_big
606 #endif
607 DECL_FFT(1024,512,256)
608 DECL_FFT(2048,1024,512)
609 DECL_FFT(4096,2048,1024)
610 DECL_FFT(8192,4096,2048)
611 DECL_FFT(16384,8192,4096)
612 DECL_FFT(32768,16384,8192)
613 DECL_FFT(65536,32768,16384)
614 DECL_FFT(131072,65536,32768)
615 
616 static void (* const fft_dispatch[])(FFTComplex*) = {
617  fft4, fft8, fft16, fft32, fft64, fft128, fft256, fft512, fft1024,
618  fft2048, fft4096, fft8192, fft16384, fft32768, fft65536, fft131072
619 };
620 
621 static void fft_calc_c(FFTContext *s, FFTComplex *z)
622 {
623  fft_dispatch[s->nbits-2](z);
624 }
625 #endif /* FFT_FIXED_32 */
static void fft_permute_c(FFTContext *s, FFTComplex *z)
Definition: fft_template.c:295
#define NULL
Definition: coverity.c:32
#define MAX_FFT_SIZE
Definition: fft_table.h:60
#define BUTTERFLIES(a0, a1, a2, a3)
Definition: fft_template.c:538
float FFTDouble
Definition: fft.h:44
static CosTabsInitOnce cos_tabs_init_once[]
Definition: fft_template.c:95
void ff_fft_lut_init(void)
float re
Definition: fft.c:82
#define M_SQRT1_2
Definition: mathematics.h:58
static const int avx_tab[]
Definition: fft_template.c:158
#define SPLIT_RADIX_PERMUTATION(num)
FFTSample re
Definition: avfft.h:38
#define t8
Definition: regdef.h:53
static int split_radix_permutation(int i, int n, int inverse)
Definition: fft_template.c:140
#define MAX_LOG2_NFFT
Specifies maximum allowed fft size.
Definition: fft_table.h:59
#define t7
Definition: regdef.h:35
#define av_cold
Definition: attributes.h:88
#define av_malloc(s)
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf offset
COSTABLE(16)
av_cold void ff_fft_init_arm(FFTContext *s)
Definition: fft_init_arm.c:38
void ff_fft_init_ppc(FFTContext *s)
Definition: fft_init.c:151
const int32_t ff_w_tab_sr[MAX_FFT_SIZE/(4 *16)]
#define DECL_FFT(n, n2, n4)
Definition: fft_template.c:542
#define AVOnce
Definition: thread.h:172
#define INIT_FF_COS_TABS_FUNC(index, size)
Definition: fft_template.c:74
static void(*const fft_dispatch[])(FFTComplex *)
Definition: fft_template.c:616
void(* fft_permute)(struct FFTContext *s, FFTComplex *z)
Do the permutation needed BEFORE calling fft_calc().
Definition: fft.h:96
#define t1
Definition: regdef.h:29
void(* mdct_calc)(struct FFTContext *s, FFTSample *output, const FFTSample *input)
Definition: fft.h:104
void(* imdct_calc)(struct FFTContext *s, FFTSample *output, const FFTSample *input)
Definition: fft.h:102
#define t3
Definition: regdef.h:31
float FFTSample
Definition: avfft.h:35
#define fail()
Definition: checkasm.h:133
static av_cold void fft_perm_avx(FFTContext *s)
Definition: fft_template.c:174
#define pass
Definition: fft_template.c:605
#define Q31(x)
Definition: aac_defines.h:98
Definition: fft.h:83
av_cold int ff_fft_init(FFTContext *s, int nbits, int inverse)
Set up a complex FFT.
Definition: fft_template.c:196
uint32_t * revtab32
Definition: fft.h:107
typedef void(APIENTRY *FF_PFNGLACTIVETEXTUREPROC)(GLenum texture)
#define PASS(name)
Definition: fft_template.c:514
int nbits
Definition: fft.h:84
int inverse
Definition: fft.h:85
int32_t
#define s(width, name)
Definition: cbs_vp9.c:257
enum fft_permutation_type fft_permutation
Definition: fft.h:105
#define ff_imdct_half_c
Definition: fft-internal.h:60
#define ff_imdct_calc_c
Definition: fft-internal.h:59
void(* func)(void)
Definition: fft_template.c:70
static int is_second_half_of_fft32(int i, int n)
Definition: fft_template.c:162
#define AV_ONCE_INIT
Definition: thread.h:173
int index
Definition: gxfenc.c:89
float im
Definition: fft.c:82
#define FFT_FLOAT
Definition: aac_defines.h:82
uint16_t ff_fft_offsets_lut[21845]
#define t5
Definition: regdef.h:33
static av_cold void init_ff_cos_tabs(int index)
Definition: fft_template.c:57
void(* imdct_half)(struct FFTContext *s, FFTSample *output, const FFTSample *input)
Definition: fft.h:103
#define TRANSFORM(a0, a1, a2, a3, wre, wim)
Definition: fft_template.c:499
#define TRANSFORM_ZERO(a0, a1, a2, a3)
Definition: fft_template.c:505
static void fft4(FFTComplex *z)
Definition: fft_template.c:551
int
av_cold void ff_fft_end(FFTContext *s)
Definition: fft_template.c:310
FFTSample im
Definition: avfft.h:38
#define t6
Definition: regdef.h:34
#define COSTABLE_CONST
Definition: fft.h:113
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().
Definition: fft.h:101
#define t4
Definition: regdef.h:32
void ff_fft_init_mips(FFTContext *s)
FFT transform.
Definition: fft_mips.c:501
#define BF(a, b, c, s)
#define ff_mdct_calc_c
Definition: fft-internal.h:61
static int ff_thread_once(char *control, void(*routine)(void))
Definition: thread.h:175
static void fft8(FFTComplex *z)
Definition: fft_template.c:565
COSTABLE_CONST FFTSample *const FFT_NAME(ff_cos_tabs)[]
static const struct twinvq_data tab
#define av_freep(p)
uint16_t * revtab
Definition: fft.h:86
#define M_PI
Definition: mathematics.h:52
static uint32_t inverse(uint32_t v)
find multiplicative inverse modulo 2 ^ 32
Definition: asfcrypt.c:35
av_cold void ff_init_ff_cos_tabs(int index)
Initialize the cosine table in ff_cos_tabs[index].
Definition: fft_template.c:151
static void fft_calc_c(FFTContext *s, FFTComplex *z)
Definition: fft_template.c:621
static void fft16(FFTComplex *z)
Definition: fft_template.c:581
#define t2
Definition: regdef.h:30
int i
Definition: input.c:407
definitions and tables for FFT
trying all byte sequences megabyte in length and selecting the best looking sequence will yield cases to try But a word about which is also called distortion Distortion can be quantified by almost any quality measurement one chooses the sum of squared differences is used but more complex methods that consider psychovisual effects can be used as well It makes no difference in this discussion First step
void ff_fft_init_x86(FFTContext *s)
Definition: fft_init.c:27
FFTComplex * tmp_buf
Definition: fft.h:87