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_FLOAT
37 #include "fft_table.h"
38 #else /* !FFT_FLOAT */
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 
117 {
119 }
120 #endif
121 COSTABLE_CONST FFTSample * const FFT_NAME(ff_cos_tabs)[] = {
122  NULL, NULL, NULL, NULL,
123  FFT_NAME(ff_cos_16),
124  FFT_NAME(ff_cos_32),
125  FFT_NAME(ff_cos_64),
126  FFT_NAME(ff_cos_128),
127  FFT_NAME(ff_cos_256),
128  FFT_NAME(ff_cos_512),
129  FFT_NAME(ff_cos_1024),
130  FFT_NAME(ff_cos_2048),
131  FFT_NAME(ff_cos_4096),
132  FFT_NAME(ff_cos_8192),
133  FFT_NAME(ff_cos_16384),
134  FFT_NAME(ff_cos_32768),
135  FFT_NAME(ff_cos_65536),
136  FFT_NAME(ff_cos_131072),
137 };
138 
139 #endif /* FFT_FLOAT */
140 
141 static void fft_permute_c(FFTContext *s, FFTComplex *z);
142 static void fft_calc_c(FFTContext *s, FFTComplex *z);
143 
144 static int split_radix_permutation(int i, int n, int inverse)
145 {
146  int m;
147  if(n <= 2) return i&1;
148  m = n >> 1;
149  if(!(i&m)) return split_radix_permutation(i, m, inverse)*2;
150  m >>= 1;
151  if(inverse == !(i&m)) return split_radix_permutation(i, m, inverse)*4 + 1;
152  else return split_radix_permutation(i, m, inverse)*4 - 1;
153 }
154 
155 
156 static const int avx_tab[] = {
157  0, 4, 1, 5, 8, 12, 9, 13, 2, 6, 3, 7, 10, 14, 11, 15
158 };
159 
160 static int is_second_half_of_fft32(int i, int n)
161 {
162  if (n <= 32)
163  return i >= 16;
164  else if (i < n/2)
165  return is_second_half_of_fft32(i, n/2);
166  else if (i < 3*n/4)
167  return is_second_half_of_fft32(i - n/2, n/4);
168  else
169  return is_second_half_of_fft32(i - 3*n/4, n/4);
170 }
171 
173 {
174  int i;
175  int n = 1 << s->nbits;
176 
177  for (i = 0; i < n; i += 16) {
178  int k;
179  if (is_second_half_of_fft32(i, n)) {
180  for (k = 0; k < 16; k++)
181  s->revtab[-split_radix_permutation(i + k, n, s->inverse) & (n - 1)] =
182  i + avx_tab[k];
183 
184  } else {
185  for (k = 0; k < 16; k++) {
186  int j = i + k;
187  j = (j & ~7) | ((j >> 1) & 3) | ((j << 2) & 4);
188  s->revtab[-split_radix_permutation(i + k, n, s->inverse) & (n - 1)] = j;
189  }
190  }
191  }
192 }
193 
194 av_cold int ff_fft_init(FFTContext *s, int nbits, int inverse)
195 {
196  int i, j, n;
197 
198  s->revtab = NULL;
199  s->revtab32 = NULL;
200 
201  if (nbits < 2 || nbits > 17)
202  goto fail;
203  s->nbits = nbits;
204  n = 1 << nbits;
205 
206  if (nbits <= 16) {
207  s->revtab = av_malloc(n * sizeof(uint16_t));
208  if (!s->revtab)
209  goto fail;
210  } else {
211  s->revtab32 = av_malloc(n * sizeof(uint32_t));
212  if (!s->revtab32)
213  goto fail;
214  }
215  s->tmp_buf = av_malloc(n * sizeof(FFTComplex));
216  if (!s->tmp_buf)
217  goto fail;
218  s->inverse = inverse;
219  s->fft_permutation = FF_FFT_PERM_DEFAULT;
220 
221  s->fft_permute = fft_permute_c;
222  s->fft_calc = fft_calc_c;
223 #if CONFIG_MDCT
224  s->imdct_calc = ff_imdct_calc_c;
225  s->imdct_half = ff_imdct_half_c;
226  s->mdct_calc = ff_mdct_calc_c;
227 #endif
228 
229 #if FFT_FLOAT
230  if (ARCH_AARCH64) ff_fft_init_aarch64(s);
231  if (ARCH_ARM) ff_fft_init_arm(s);
232  if (ARCH_PPC) ff_fft_init_ppc(s);
233  if (ARCH_X86) ff_fft_init_x86(s);
234  if (HAVE_MIPSFPU) ff_fft_init_mips(s);
235  for(j=4; j<=nbits; j++) {
237  }
238 #else /* FFT_FLOAT */
239  ff_fft_lut_init();
240 #endif
241 
242 
243  if (ARCH_X86 && FFT_FLOAT && s->fft_permutation == FF_FFT_PERM_AVX) {
244  fft_perm_avx(s);
245  } else {
246 #define PROCESS_FFT_PERM_SWAP_LSBS(num) do {\
247  for(i = 0; i < n; i++) {\
248  int k;\
249  j = i;\
250  j = (j & ~3) | ((j >> 1) & 1) | ((j << 1) & 2);\
251  k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\
252  s->revtab##num[k] = j;\
253  } \
254 } while(0);
255 
256 #define PROCESS_FFT_PERM_DEFAULT(num) do {\
257  for(i = 0; i < n; i++) {\
258  int k;\
259  j = i;\
260  k = -split_radix_permutation(i, n, s->inverse) & (n - 1);\
261  s->revtab##num[k] = j;\
262  } \
263 } while(0);
264 
265 #define SPLIT_RADIX_PERMUTATION(num) do { \
266  if (s->fft_permutation == FF_FFT_PERM_SWAP_LSBS) {\
267  PROCESS_FFT_PERM_SWAP_LSBS(num) \
268  } else {\
269  PROCESS_FFT_PERM_DEFAULT(num) \
270  }\
271 } while(0);
272 
273  if (s->revtab)
275  if (s->revtab32)
277 
278 #undef PROCESS_FFT_PERM_DEFAULT
279 #undef PROCESS_FFT_PERM_SWAP_LSBS
280 #undef SPLIT_RADIX_PERMUTATION
281  }
282 
283  return 0;
284  fail:
285  av_freep(&s->revtab);
286  av_freep(&s->revtab32);
287  av_freep(&s->tmp_buf);
288  return -1;
289 }
290 
292 {
293  int j, np;
294  const uint16_t *revtab = s->revtab;
295  const uint32_t *revtab32 = s->revtab32;
296  np = 1 << s->nbits;
297  /* TODO: handle split-radix permute in a more optimal way, probably in-place */
298  if (revtab) {
299  for(j=0;j<np;j++) s->tmp_buf[revtab[j]] = z[j];
300  } else
301  for(j=0;j<np;j++) s->tmp_buf[revtab32[j]] = z[j];
302 
303  memcpy(z, s->tmp_buf, np * sizeof(FFTComplex));
304 }
305 
307 {
308  av_freep(&s->revtab);
309  av_freep(&s->revtab32);
310  av_freep(&s->tmp_buf);
311 }
312 
313 #if !FFT_FLOAT
314 
315 static void fft_calc_c(FFTContext *s, FFTComplex *z) {
316 
317  int nbits, i, n, num_transforms, offset, step;
318  int n4, n2, n34;
319  unsigned tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8;
320  FFTComplex *tmpz;
321  const int fft_size = (1 << s->nbits);
322  int64_t accu;
323 
324  num_transforms = (0x2aab >> (16 - s->nbits)) | 1;
325 
326  for (n=0; n<num_transforms; n++){
327  offset = ff_fft_offsets_lut[n] << 2;
328  tmpz = z + offset;
329 
330  tmp1 = tmpz[0].re + (unsigned)tmpz[1].re;
331  tmp5 = tmpz[2].re + (unsigned)tmpz[3].re;
332  tmp2 = tmpz[0].im + (unsigned)tmpz[1].im;
333  tmp6 = tmpz[2].im + (unsigned)tmpz[3].im;
334  tmp3 = tmpz[0].re - (unsigned)tmpz[1].re;
335  tmp8 = tmpz[2].im - (unsigned)tmpz[3].im;
336  tmp4 = tmpz[0].im - (unsigned)tmpz[1].im;
337  tmp7 = tmpz[2].re - (unsigned)tmpz[3].re;
338 
339  tmpz[0].re = tmp1 + tmp5;
340  tmpz[2].re = tmp1 - tmp5;
341  tmpz[0].im = tmp2 + tmp6;
342  tmpz[2].im = tmp2 - tmp6;
343  tmpz[1].re = tmp3 + tmp8;
344  tmpz[3].re = tmp3 - tmp8;
345  tmpz[1].im = tmp4 - tmp7;
346  tmpz[3].im = tmp4 + tmp7;
347  }
348 
349  if (fft_size < 8)
350  return;
351 
352  num_transforms = (num_transforms >> 1) | 1;
353 
354  for (n=0; n<num_transforms; n++){
355  offset = ff_fft_offsets_lut[n] << 3;
356  tmpz = z + offset;
357 
358  tmp1 = tmpz[4].re + (unsigned)tmpz[5].re;
359  tmp3 = tmpz[6].re + (unsigned)tmpz[7].re;
360  tmp2 = tmpz[4].im + (unsigned)tmpz[5].im;
361  tmp4 = tmpz[6].im + (unsigned)tmpz[7].im;
362  tmp5 = tmp1 + tmp3;
363  tmp7 = tmp1 - tmp3;
364  tmp6 = tmp2 + tmp4;
365  tmp8 = tmp2 - tmp4;
366 
367  tmp1 = tmpz[4].re - (unsigned)tmpz[5].re;
368  tmp2 = tmpz[4].im - (unsigned)tmpz[5].im;
369  tmp3 = tmpz[6].re - (unsigned)tmpz[7].re;
370  tmp4 = tmpz[6].im - (unsigned)tmpz[7].im;
371 
372  tmpz[4].re = tmpz[0].re - tmp5;
373  tmpz[0].re = tmpz[0].re + tmp5;
374  tmpz[4].im = tmpz[0].im - tmp6;
375  tmpz[0].im = tmpz[0].im + tmp6;
376  tmpz[6].re = tmpz[2].re - tmp8;
377  tmpz[2].re = tmpz[2].re + tmp8;
378  tmpz[6].im = tmpz[2].im + tmp7;
379  tmpz[2].im = tmpz[2].im - tmp7;
380 
381  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp1 + tmp2);
382  tmp5 = (int32_t)((accu + 0x40000000) >> 31);
383  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp3 - tmp4);
384  tmp7 = (int32_t)((accu + 0x40000000) >> 31);
385  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp2 - tmp1);
386  tmp6 = (int32_t)((accu + 0x40000000) >> 31);
387  accu = (int64_t)Q31(M_SQRT1_2)*(int)(tmp3 + tmp4);
388  tmp8 = (int32_t)((accu + 0x40000000) >> 31);
389  tmp1 = tmp5 + tmp7;
390  tmp3 = tmp5 - tmp7;
391  tmp2 = tmp6 + tmp8;
392  tmp4 = tmp6 - tmp8;
393 
394  tmpz[5].re = tmpz[1].re - tmp1;
395  tmpz[1].re = tmpz[1].re + tmp1;
396  tmpz[5].im = tmpz[1].im - tmp2;
397  tmpz[1].im = tmpz[1].im + tmp2;
398  tmpz[7].re = tmpz[3].re - tmp4;
399  tmpz[3].re = tmpz[3].re + tmp4;
400  tmpz[7].im = tmpz[3].im + tmp3;
401  tmpz[3].im = tmpz[3].im - tmp3;
402  }
403 
404  step = 1 << ((MAX_LOG2_NFFT-4) - 4);
405  n4 = 4;
406 
407  for (nbits=4; nbits<=s->nbits; nbits++){
408  n2 = 2*n4;
409  n34 = 3*n4;
410  num_transforms = (num_transforms >> 1) | 1;
411 
412  for (n=0; n<num_transforms; n++){
413  const FFTSample *w_re_ptr = ff_w_tab_sr + step;
414  const FFTSample *w_im_ptr = ff_w_tab_sr + MAX_FFT_SIZE/(4*16) - step;
415  offset = ff_fft_offsets_lut[n] << nbits;
416  tmpz = z + offset;
417 
418  tmp5 = tmpz[ n2].re + (unsigned)tmpz[n34].re;
419  tmp1 = tmpz[ n2].re - (unsigned)tmpz[n34].re;
420  tmp6 = tmpz[ n2].im + (unsigned)tmpz[n34].im;
421  tmp2 = tmpz[ n2].im - (unsigned)tmpz[n34].im;
422 
423  tmpz[ n2].re = tmpz[ 0].re - tmp5;
424  tmpz[ 0].re = tmpz[ 0].re + tmp5;
425  tmpz[ n2].im = tmpz[ 0].im - tmp6;
426  tmpz[ 0].im = tmpz[ 0].im + tmp6;
427  tmpz[n34].re = tmpz[n4].re - tmp2;
428  tmpz[ n4].re = tmpz[n4].re + tmp2;
429  tmpz[n34].im = tmpz[n4].im + tmp1;
430  tmpz[ n4].im = tmpz[n4].im - tmp1;
431 
432  for (i=1; i<n4; i++){
433  FFTSample w_re = w_re_ptr[0];
434  FFTSample w_im = w_im_ptr[0];
435  accu = (int64_t)w_re*tmpz[ n2+i].re;
436  accu += (int64_t)w_im*tmpz[ n2+i].im;
437  tmp1 = (int32_t)((accu + 0x40000000) >> 31);
438  accu = (int64_t)w_re*tmpz[ n2+i].im;
439  accu -= (int64_t)w_im*tmpz[ n2+i].re;
440  tmp2 = (int32_t)((accu + 0x40000000) >> 31);
441  accu = (int64_t)w_re*tmpz[n34+i].re;
442  accu -= (int64_t)w_im*tmpz[n34+i].im;
443  tmp3 = (int32_t)((accu + 0x40000000) >> 31);
444  accu = (int64_t)w_re*tmpz[n34+i].im;
445  accu += (int64_t)w_im*tmpz[n34+i].re;
446  tmp4 = (int32_t)((accu + 0x40000000) >> 31);
447 
448  tmp5 = tmp1 + tmp3;
449  tmp1 = tmp1 - tmp3;
450  tmp6 = tmp2 + tmp4;
451  tmp2 = tmp2 - tmp4;
452 
453  tmpz[ n2+i].re = tmpz[ i].re - tmp5;
454  tmpz[ i].re = tmpz[ i].re + tmp5;
455  tmpz[ n2+i].im = tmpz[ i].im - tmp6;
456  tmpz[ i].im = tmpz[ i].im + tmp6;
457  tmpz[n34+i].re = tmpz[n4+i].re - tmp2;
458  tmpz[ n4+i].re = tmpz[n4+i].re + tmp2;
459  tmpz[n34+i].im = tmpz[n4+i].im + tmp1;
460  tmpz[ n4+i].im = tmpz[n4+i].im - tmp1;
461 
462  w_re_ptr += step;
463  w_im_ptr -= step;
464  }
465  }
466  step >>= 1;
467  n4 <<= 1;
468  }
469 }
470 
471 #else /* !FFT_FLOAT */
472 
473 #define BUTTERFLIES(a0,a1,a2,a3) {\
474  BF(t3, t5, t5, t1);\
475  BF(a2.re, a0.re, a0.re, t5);\
476  BF(a3.im, a1.im, a1.im, t3);\
477  BF(t4, t6, t2, t6);\
478  BF(a3.re, a1.re, a1.re, t4);\
479  BF(a2.im, a0.im, a0.im, t6);\
480 }
481 
482 // force loading all the inputs before storing any.
483 // this is slightly slower for small data, but avoids store->load aliasing
484 // for addresses separated by large powers of 2.
485 #define BUTTERFLIES_BIG(a0,a1,a2,a3) {\
486  FFTSample r0=a0.re, i0=a0.im, r1=a1.re, i1=a1.im;\
487  BF(t3, t5, t5, t1);\
488  BF(a2.re, a0.re, r0, t5);\
489  BF(a3.im, a1.im, i1, t3);\
490  BF(t4, t6, t2, t6);\
491  BF(a3.re, a1.re, r1, t4);\
492  BF(a2.im, a0.im, i0, t6);\
493 }
494 
495 #define TRANSFORM(a0,a1,a2,a3,wre,wim) {\
496  CMUL(t1, t2, a2.re, a2.im, wre, -wim);\
497  CMUL(t5, t6, a3.re, a3.im, wre, wim);\
498  BUTTERFLIES(a0,a1,a2,a3)\
499 }
500 
501 #define TRANSFORM_ZERO(a0,a1,a2,a3) {\
502  t1 = a2.re;\
503  t2 = a2.im;\
504  t5 = a3.re;\
505  t6 = a3.im;\
506  BUTTERFLIES(a0,a1,a2,a3)\
507 }
508 
509 /* z[0...8n-1], w[1...2n-1] */
510 #define PASS(name)\
511 static void name(FFTComplex *z, const FFTSample *wre, unsigned int n)\
512 {\
513  FFTDouble t1, t2, t3, t4, t5, t6;\
514  int o1 = 2*n;\
515  int o2 = 4*n;\
516  int o3 = 6*n;\
517  const FFTSample *wim = wre+o1;\
518  n--;\
519 \
520  TRANSFORM_ZERO(z[0],z[o1],z[o2],z[o3]);\
521  TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\
522  do {\
523  z += 2;\
524  wre += 2;\
525  wim -= 2;\
526  TRANSFORM(z[0],z[o1],z[o2],z[o3],wre[0],wim[0]);\
527  TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\
528  } while(--n);\
529 }
530 
531 PASS(pass)
532 #if !CONFIG_SMALL
533 #undef BUTTERFLIES
534 #define BUTTERFLIES BUTTERFLIES_BIG
535 PASS(pass_big)
536 #endif
537 
538 #define DECL_FFT(n,n2,n4)\
539 static void fft##n(FFTComplex *z)\
540 {\
541  fft##n2(z);\
542  fft##n4(z+n4*2);\
543  fft##n4(z+n4*3);\
544  pass(z,FFT_NAME(ff_cos_##n),n4/2);\
545 }
546 
547 static void fft4(FFTComplex *z)
548 {
549  FFTDouble t1, t2, t3, t4, t5, t6, t7, t8;
550 
551  BF(t3, t1, z[0].re, z[1].re);
552  BF(t8, t6, z[3].re, z[2].re);
553  BF(z[2].re, z[0].re, t1, t6);
554  BF(t4, t2, z[0].im, z[1].im);
555  BF(t7, t5, z[2].im, z[3].im);
556  BF(z[3].im, z[1].im, t4, t8);
557  BF(z[3].re, z[1].re, t3, t7);
558  BF(z[2].im, z[0].im, t2, t5);
559 }
560 
561 static void fft8(FFTComplex *z)
562 {
563  FFTDouble t1, t2, t3, t4, t5, t6;
564 
565  fft4(z);
566 
567  BF(t1, z[5].re, z[4].re, -z[5].re);
568  BF(t2, z[5].im, z[4].im, -z[5].im);
569  BF(t5, z[7].re, z[6].re, -z[7].re);
570  BF(t6, z[7].im, z[6].im, -z[7].im);
571 
572  BUTTERFLIES(z[0],z[2],z[4],z[6]);
573  TRANSFORM(z[1],z[3],z[5],z[7],sqrthalf,sqrthalf);
574 }
575 
576 #if !CONFIG_SMALL
577 static void fft16(FFTComplex *z)
578 {
579  FFTDouble t1, t2, t3, t4, t5, t6;
580  FFTSample cos_16_1 = FFT_NAME(ff_cos_16)[1];
581  FFTSample cos_16_3 = FFT_NAME(ff_cos_16)[3];
582 
583  fft8(z);
584  fft4(z+8);
585  fft4(z+12);
586 
587  TRANSFORM_ZERO(z[0],z[4],z[8],z[12]);
588  TRANSFORM(z[2],z[6],z[10],z[14],sqrthalf,sqrthalf);
589  TRANSFORM(z[1],z[5],z[9],z[13],cos_16_1,cos_16_3);
590  TRANSFORM(z[3],z[7],z[11],z[15],cos_16_3,cos_16_1);
591 }
592 #else
593 DECL_FFT(16,8,4)
594 #endif
595 DECL_FFT(32,16,8)
596 DECL_FFT(64,32,16)
597 DECL_FFT(128,64,32)
598 DECL_FFT(256,128,64)
599 DECL_FFT(512,256,128)
600 #if !CONFIG_SMALL
601 #define pass pass_big
602 #endif
603 DECL_FFT(1024,512,256)
604 DECL_FFT(2048,1024,512)
605 DECL_FFT(4096,2048,1024)
606 DECL_FFT(8192,4096,2048)
607 DECL_FFT(16384,8192,4096)
608 DECL_FFT(32768,16384,8192)
609 DECL_FFT(65536,32768,16384)
610 DECL_FFT(131072,65536,32768)
611 
612 static void (* const fft_dispatch[])(FFTComplex*) = {
613  fft4, fft8, fft16, fft32, fft64, fft128, fft256, fft512, fft1024,
614  fft2048, fft4096, fft8192, fft16384, fft32768, fft65536, fft131072
615 };
616 
618 {
619  fft_dispatch[s->nbits-2](z);
620 }
621 #endif /* !FFT_FLOAT */
fft16
static void fft16(FFTComplex *z)
Definition: fft_template.c:577
func
int(* func)(AVBPrint *dst, const char *in, const char *arg)
Definition: jacosubdec.c:68
ff_fft_init_ppc
void ff_fft_init_ppc(FFTContext *s)
Definition: fft_init.c:152
ff_fft_lut_init
void ff_fft_lut_init(void)
Definition: fft_init_table.c:339
BUTTERFLIES
#define BUTTERFLIES(a0, a1, a2, a3)
Definition: fft_template.c:534
thread.h
split_radix_permutation
static int split_radix_permutation(int i, int n, int inverse)
Definition: fft_template.c:144
im
float im
Definition: fft.c:78
step
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
Definition: rate_distortion.txt:58
index
fg index
Definition: ffmpeg_filter.c:168
t1
#define t1
Definition: regdef.h:29
mathematics.h
CosTabsInitOnce::func
void(* func)(void)
Definition: fft_template.c:70
MAX_FFT_SIZE
#define MAX_FFT_SIZE
Definition: fft_table.h:60
SPLIT_RADIX_PERMUTATION
#define SPLIT_RADIX_PERMUTATION(num)
DECL_FFT
#define DECL_FFT(n, n2, n4)
Definition: fft_template.c:538
ff_fft_init_aarch64
av_cold void ff_fft_init_aarch64(FFTContext *s)
Definition: fft_init_aarch64.c:36
FF_FFT_PERM_DEFAULT
@ FF_FFT_PERM_DEFAULT
Definition: fft.h:65
cos_tabs_init_once
static CosTabsInitOnce cos_tabs_init_once[]
Definition: fft_template.c:95
av_malloc
#define av_malloc(s)
Definition: tableprint_vlc.h:31
COSTABLE
COSTABLE(16)
fail
#define fail()
Definition: checkasm.h:127
tab
static const struct twinvq_data tab
Definition: twinvq_data.h:10345
CosTabsInitOnce::control
AVOnce control
Definition: fft_template.c:71
INIT_FF_COS_TABS_FUNC
#define INIT_FF_COS_TABS_FUNC(index, size)
Definition: fft_template.c:74
fft_dispatch
static void(*const fft_dispatch[])(FFTComplex *)
Definition: fft_template.c:612
ff_thread_once
static int ff_thread_once(char *control, void(*routine)(void))
Definition: thread.h:175
av_cold
#define av_cold
Definition: attributes.h:90
ff_mdct_calc_c
#define ff_mdct_calc_c
Definition: fft-internal.h:56
s
#define s(width, name)
Definition: cbs_vp9.c:257
ff_fft_init_x86
void ff_fft_init_x86(FFTContext *s)
Definition: fft_init.c:27
ff_fft_init
av_cold int ff_fft_init(FFTContext *s, int nbits, int inverse)
Set up a complex FFT.
Definition: fft_template.c:194
t7
#define t7
Definition: regdef.h:35
pass
#define pass
Definition: fft_template.c:601
AV_ONCE_INIT
#define AV_ONCE_INIT
Definition: thread.h:173
ff_fft_init_arm
av_cold void ff_fft_init_arm(FFTContext *s)
Definition: fft_init_arm.c:38
NULL
#define NULL
Definition: coverity.c:32
COSTABLE_CONST
#define COSTABLE_CONST
Definition: fft.h:106
FFT_FLOAT
#define FFT_FLOAT
Definition: aac_defines.h:81
t5
#define t5
Definition: regdef.h:33
fft-internal.h
t6
#define t6
Definition: regdef.h:34
MAX_LOG2_NFFT
#define MAX_LOG2_NFFT
Specifies maximum allowed fft size.
Definition: fft_table.h:59
FFTSample
float FFTSample
Definition: avfft.h:35
fft_perm_avx
static av_cold void fft_perm_avx(FFTContext *s)
Definition: fft_template.c:172
AVOnce
#define AVOnce
Definition: thread.h:172
fft_table.h
is_second_half_of_fft32
static int is_second_half_of_fft32(int i, int n)
Definition: fft_template.c:160
CosTabsInitOnce
Definition: fft_template.c:69
TRANSFORM
#define TRANSFORM(a0, a1, a2, a3, wre, wim)
Definition: fft_template.c:495
FFTComplex::im
FFTSample im
Definition: avfft.h:38
ff_fft_init_mips
void ff_fft_init_mips(FFTContext *s)
FFT transform.
Definition: fft_mips.c:502
FFTDouble
float FFTDouble
Definition: fft.h:40
FFTComplex::re
FFTSample re
Definition: avfft.h:38
t8
#define t8
Definition: regdef.h:53
BF
#define BF(a, b, c, s)
Definition: dct32_template.c:90
offset
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
Definition: writing_filters.txt:86
M_PI
#define M_PI
Definition: mathematics.h:52
FFTContext
Definition: fft.h:75
PASS
#define PASS(name)
Definition: fft_template.c:510
ff_fft_offsets_lut
uint16_t ff_fft_offsets_lut[21845]
Definition: fft_init_table.c:317
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:271
t4
#define t4
Definition: regdef.h:32
t3
#define t3
Definition: regdef.h:31
ff_imdct_half_c
#define ff_imdct_half_c
Definition: fft-internal.h:55
ff_imdct_calc_c
#define ff_imdct_calc_c
Definition: fft-internal.h:54
M_SQRT1_2
#define M_SQRT1_2
Definition: mathematics.h:58
fft.h
t2
#define t2
Definition: regdef.h:30
inverse
static int inverse(AudioFWTDNContext *s, double **in, int *in_length, double *out, int out_length, int ch, uint64_t sn)
Definition: af_afwtdn.c:762
fft4
static void fft4(FFTComplex *z)
Definition: fft_template.c:547
fft_permute_c
static void fft_permute_c(FFTContext *s, FFTComplex *z)
Definition: fft_template.c:291
Q31
#define Q31(x)
Definition: aac_defines.h:96
FFT_NAME
COSTABLE_CONST FFTSample *const FFT_NAME(ff_cos_tabs)[]
ff_fft_end
av_cold void ff_fft_end(FFTContext *s)
Definition: fft_template.c:306
init_ff_cos_tabs
static av_cold void init_ff_cos_tabs(int index)
Definition: fft_template.c:57
ff_init_ff_cos_tabs
av_cold void ff_init_ff_cos_tabs(int index)
Initialize the cosine table in ff_cos_tabs[index].
Definition: fft_template.c:116
fft_calc_c
static void fft_calc_c(FFTContext *s, FFTComplex *z)
Definition: fft_template.c:617
ff_w_tab_sr
const int32_t ff_w_tab_sr[MAX_FFT_SIZE/(4 *16)]
Definition: fft_init_table.c:58
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
TRANSFORM_ZERO
#define TRANSFORM_ZERO(a0, a1, a2, a3)
Definition: fft_template.c:501
int32_t
int32_t
Definition: audioconvert.c:56
fft8
static void fft8(FFTComplex *z)
Definition: fft_template.c:561
int
int
Definition: ffmpeg_filter.c:156
FF_FFT_PERM_AVX
@ FF_FFT_PERM_AVX
Definition: fft.h:67
avx_tab
static const int avx_tab[]
Definition: fft_template.c:156
FFTComplex
Definition: avfft.h:37
re
float re
Definition: fft.c:78