-#include <stddef.h>
-#include "tx.h"
-#include "thread.h"
-#include "mem.h"
-#include "avassert.h"
-
-typedef float FFTSample;
-typedef AVComplexFloat FFTComplex;
-
-struct AVTXContext {
- int n; /* Nptwo part */
- int m; /* Ptwo part */
-
- FFTComplex *exptab; /* MDCT exptab */
- FFTComplex *tmp; /* Temporary buffer needed for all compound transforms */
- int *pfatab; /* Input/Output mapping for compound transforms */
- int *revtab; /* Input mapping for power of two transforms */
-};
-
-#define FFT_NAME(x) x
-
-#define COSTABLE(size) \
- static DECLARE_ALIGNED(32, FFTSample, FFT_NAME(ff_cos_##size))[size/2]
-
-static FFTSample * const FFT_NAME(ff_cos_tabs)[18];
-
-COSTABLE(16);
-COSTABLE(32);
-COSTABLE(64);
-COSTABLE(128);
-COSTABLE(256);
-COSTABLE(512);
-COSTABLE(1024);
-COSTABLE(2048);
-COSTABLE(4096);
-COSTABLE(8192);
-COSTABLE(16384);
-COSTABLE(32768);
-COSTABLE(65536);
-COSTABLE(131072);
-
-static av_cold void init_ff_cos_tabs(int index)
-{
- int m = 1 << index;
- double freq = 2*M_PI/m;
- FFTSample *tab = FFT_NAME(ff_cos_tabs)[index];
- for(int i = 0; i <= m/4; i++)
- tab[i] = cos(i*freq);
- for(int i = 1; i < m/4; i++)
- tab[m/2 - i] = tab[i];
-}
-
-typedef struct CosTabsInitOnce {
- void (*func)(void);
- AVOnce control;
-} CosTabsInitOnce;
-
-#define INIT_FF_COS_TABS_FUNC(index, size) \
-static av_cold void init_ff_cos_tabs_ ## size (void) \
-{ \
- init_ff_cos_tabs(index); \
-}
-
-INIT_FF_COS_TABS_FUNC(4, 16)
-INIT_FF_COS_TABS_FUNC(5, 32)
-INIT_FF_COS_TABS_FUNC(6, 64)
-INIT_FF_COS_TABS_FUNC(7, 128)
-INIT_FF_COS_TABS_FUNC(8, 256)
-INIT_FF_COS_TABS_FUNC(9, 512)
-INIT_FF_COS_TABS_FUNC(10, 1024)
-INIT_FF_COS_TABS_FUNC(11, 2048)
-INIT_FF_COS_TABS_FUNC(12, 4096)
-INIT_FF_COS_TABS_FUNC(13, 8192)
-INIT_FF_COS_TABS_FUNC(14, 16384)
-INIT_FF_COS_TABS_FUNC(15, 32768)
-INIT_FF_COS_TABS_FUNC(16, 65536)
-INIT_FF_COS_TABS_FUNC(17, 131072)
-
-static CosTabsInitOnce cos_tabs_init_once[] = {
- { NULL },
- { NULL },
- { NULL },
- { NULL },
- { init_ff_cos_tabs_16, AV_ONCE_INIT },
- { init_ff_cos_tabs_32, AV_ONCE_INIT },
- { init_ff_cos_tabs_64, AV_ONCE_INIT },
- { init_ff_cos_tabs_128, AV_ONCE_INIT },
- { init_ff_cos_tabs_256, AV_ONCE_INIT },
- { init_ff_cos_tabs_512, AV_ONCE_INIT },
- { init_ff_cos_tabs_1024, AV_ONCE_INIT },
- { init_ff_cos_tabs_2048, AV_ONCE_INIT },
- { init_ff_cos_tabs_4096, AV_ONCE_INIT },
- { init_ff_cos_tabs_8192, AV_ONCE_INIT },
- { init_ff_cos_tabs_16384, AV_ONCE_INIT },
- { init_ff_cos_tabs_32768, AV_ONCE_INIT },
- { init_ff_cos_tabs_65536, AV_ONCE_INIT },
- { init_ff_cos_tabs_131072, AV_ONCE_INIT },
-};
-
-static FFTSample * const FFT_NAME(ff_cos_tabs)[] = {
- NULL, NULL, NULL, NULL,
- FFT_NAME(ff_cos_16),
- FFT_NAME(ff_cos_32),
- FFT_NAME(ff_cos_64),
- FFT_NAME(ff_cos_128),
- FFT_NAME(ff_cos_256),
- FFT_NAME(ff_cos_512),
- FFT_NAME(ff_cos_1024),
- FFT_NAME(ff_cos_2048),
- FFT_NAME(ff_cos_4096),
- FFT_NAME(ff_cos_8192),
- FFT_NAME(ff_cos_16384),
- FFT_NAME(ff_cos_32768),
- FFT_NAME(ff_cos_65536),
- FFT_NAME(ff_cos_131072),
-};
-
-static av_cold void ff_init_ff_cos_tabs(int index)
-{
- ff_thread_once(&cos_tabs_init_once[index].control,
- cos_tabs_init_once[index].func);
-}
-
-static AVOnce tabs_53_once = AV_ONCE_INIT;
-static DECLARE_ALIGNED(32, FFTComplex, FFT_NAME(ff_53_tabs))[4];
-
-static av_cold void ff_init_53_tabs(void)
-{
- ff_53_tabs[0] = (FFTComplex){ cos(2 * M_PI / 12), cos(2 * M_PI / 12) };
- ff_53_tabs[1] = (FFTComplex){ 0.5, 0.5 };
- ff_53_tabs[2] = (FFTComplex){ cos(2 * M_PI / 5), sin(2 * M_PI / 5) };
- ff_53_tabs[3] = (FFTComplex){ cos(2 * M_PI / 10), sin(2 * M_PI / 10) };
-}
-
-#define BF(x, y, a, b) do { \
- x = (a) - (b); \
- y = (a) + (b); \
- } while (0)
-
-#define CMUL(dre, dim, are, aim, bre, bim) do { \
- (dre) = (are) * (bre) - (aim) * (bim); \
- (dim) = (are) * (bim) + (aim) * (bre); \
- } while (0)
-
-#define CMUL3(c, a, b) CMUL((c).re, (c).im, (a).re, (a).im, (b).re, (b).im)
-
-static av_always_inline void fft3(FFTComplex *out, FFTComplex *in,
- ptrdiff_t stride)
-{
- FFTComplex tmp[2];
-
- tmp[0].re = in[1].im - in[2].im;
- tmp[0].im = in[1].re - in[2].re;
- tmp[1].re = in[1].re + in[2].re;
- tmp[1].im = in[1].im + in[2].im;
-
- out[0*stride].re = in[0].re + tmp[1].re;
- out[0*stride].im = in[0].im + tmp[1].im;
-
- tmp[0].re *= ff_53_tabs[0].re;
- tmp[0].im *= ff_53_tabs[0].im;
- tmp[1].re *= ff_53_tabs[1].re;
- tmp[1].im *= ff_53_tabs[1].re;
-
- out[1*stride].re = in[0].re - tmp[1].re + tmp[0].re;
- out[1*stride].im = in[0].im - tmp[1].im - tmp[0].im;
- out[2*stride].re = in[0].re - tmp[1].re - tmp[0].re;
- out[2*stride].im = in[0].im - tmp[1].im + tmp[0].im;
-}
-
-#define DECL_FFT5(NAME, D0, D1, D2, D3, D4) \
-static av_always_inline void NAME(FFTComplex *out, FFTComplex *in, \
- ptrdiff_t stride) \
-{ \
- FFTComplex z0[4], t[6]; \
- \
- t[0].re = in[1].re + in[4].re; \
- t[0].im = in[1].im + in[4].im; \
- t[1].im = in[1].re - in[4].re; \
- t[1].re = in[1].im - in[4].im; \
- t[2].re = in[2].re + in[3].re; \
- t[2].im = in[2].im + in[3].im; \
- t[3].im = in[2].re - in[3].re; \
- t[3].re = in[2].im - in[3].im; \
- \
- out[D0*stride].re = in[0].re + in[1].re + in[2].re + \
- in[3].re + in[4].re; \
- out[D0*stride].im = in[0].im + in[1].im + in[2].im + \
- in[3].im + in[4].im; \
- \
- t[4].re = ff_53_tabs[2].re * t[2].re - ff_53_tabs[3].re * t[0].re; \
- t[4].im = ff_53_tabs[2].re * t[2].im - ff_53_tabs[3].re * t[0].im; \
- t[0].re = ff_53_tabs[2].re * t[0].re - ff_53_tabs[3].re * t[2].re; \
- t[0].im = ff_53_tabs[2].re * t[0].im - ff_53_tabs[3].re * t[2].im; \
- t[5].re = ff_53_tabs[2].im * t[3].re - ff_53_tabs[3].im * t[1].re; \
- t[5].im = ff_53_tabs[2].im * t[3].im - ff_53_tabs[3].im * t[1].im; \
- t[1].re = ff_53_tabs[2].im * t[1].re + ff_53_tabs[3].im * t[3].re; \
- t[1].im = ff_53_tabs[2].im * t[1].im + ff_53_tabs[3].im * t[3].im; \
- \
- z0[0].re = t[0].re - t[1].re; \
- z0[0].im = t[0].im - t[1].im; \
- z0[1].re = t[4].re + t[5].re; \
- z0[1].im = t[4].im + t[5].im; \
- \
- z0[2].re = t[4].re - t[5].re; \
- z0[2].im = t[4].im - t[5].im; \
- z0[3].re = t[0].re + t[1].re; \
- z0[3].im = t[0].im + t[1].im; \
- \
- out[D1*stride].re = in[0].re + z0[3].re; \
- out[D1*stride].im = in[0].im + z0[0].im; \
- out[D2*stride].re = in[0].re + z0[2].re; \
- out[D2*stride].im = in[0].im + z0[1].im; \
- out[D3*stride].re = in[0].re + z0[1].re; \
- out[D3*stride].im = in[0].im + z0[2].im; \
- out[D4*stride].re = in[0].re + z0[0].re; \
- out[D4*stride].im = in[0].im + z0[3].im; \
-}
-
-DECL_FFT5(fft5, 0, 1, 2, 3, 4)
-DECL_FFT5(fft5_m1, 0, 6, 12, 3, 9)
-DECL_FFT5(fft5_m2, 10, 1, 7, 13, 4)
-DECL_FFT5(fft5_m3, 5, 11, 2, 8, 14)
-
-static av_always_inline void fft15(FFTComplex *out, FFTComplex *in,
- ptrdiff_t stride)
-{
- FFTComplex tmp[15];
-
- for (int i = 0; i < 5; i++)
- fft3(tmp + i, in + i*3, 5);
-
- fft5_m1(out, tmp + 0, stride);
- fft5_m2(out, tmp + 5, stride);
- fft5_m3(out, tmp + 10, stride);
-}
-
-#define BUTTERFLIES(a0,a1,a2,a3) {\
- BF(t3, t5, t5, t1);\
- BF(a2.re, a0.re, a0.re, t5);\
- BF(a3.im, a1.im, a1.im, t3);\
- BF(t4, t6, t2, t6);\
- BF(a3.re, a1.re, a1.re, t4);\
- BF(a2.im, a0.im, a0.im, t6);\
-}
-
-// force loading all the inputs before storing any.
-// this is slightly slower for small data, but avoids store->load aliasing
-// for addresses separated by large powers of 2.
-#define BUTTERFLIES_BIG(a0,a1,a2,a3) {\
- FFTSample r0=a0.re, i0=a0.im, r1=a1.re, i1=a1.im;\
- BF(t3, t5, t5, t1);\
- BF(a2.re, a0.re, r0, t5);\
- BF(a3.im, a1.im, i1, t3);\
- BF(t4, t6, t2, t6);\
- BF(a3.re, a1.re, r1, t4);\
- BF(a2.im, a0.im, i0, t6);\
-}
-
-#define TRANSFORM(a0,a1,a2,a3,wre,wim) {\
- CMUL(t1, t2, a2.re, a2.im, wre, -wim);\
- CMUL(t5, t6, a3.re, a3.im, wre, wim);\
- BUTTERFLIES(a0,a1,a2,a3)\
-}
-
-#define TRANSFORM_ZERO(a0,a1,a2,a3) {\
- t1 = a2.re;\
- t2 = a2.im;\
- t5 = a3.re;\
- t6 = a3.im;\
- BUTTERFLIES(a0,a1,a2,a3)\
-}
-
-/* z[0...8n-1], w[1...2n-1] */
-#define PASS(name)\
-static void name(FFTComplex *z, const FFTSample *wre, unsigned int n)\
-{\
- FFTSample t1, t2, t3, t4, t5, t6;\
- int o1 = 2*n;\
- int o2 = 4*n;\
- int o3 = 6*n;\
- const FFTSample *wim = wre+o1;\
- n--;\
-\
- TRANSFORM_ZERO(z[0],z[o1],z[o2],z[o3]);\
- TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\
- do {\
- z += 2;\
- wre += 2;\
- wim -= 2;\
- TRANSFORM(z[0],z[o1],z[o2],z[o3],wre[0],wim[0]);\
- TRANSFORM(z[1],z[o1+1],z[o2+1],z[o3+1],wre[1],wim[-1]);\
- } while(--n);\
-}
-
-PASS(pass)
-#undef BUTTERFLIES
-#define BUTTERFLIES BUTTERFLIES_BIG
-PASS(pass_big)
-
-#define DECL_FFT(n,n2,n4)\
-static void fft##n(FFTComplex *z)\
-{\
- fft##n2(z);\
- fft##n4(z+n4*2);\
- fft##n4(z+n4*3);\
- pass(z,FFT_NAME(ff_cos_##n),n4/2);\
-}
-
-static void fft4(FFTComplex *z)
-{
- FFTSample t1, t2, t3, t4, t5, t6, t7, t8;
-
- BF(t3, t1, z[0].re, z[1].re);
- BF(t8, t6, z[3].re, z[2].re);
- BF(z[2].re, z[0].re, t1, t6);
- BF(t4, t2, z[0].im, z[1].im);
- BF(t7, t5, z[2].im, z[3].im);
- BF(z[3].im, z[1].im, t4, t8);
- BF(z[3].re, z[1].re, t3, t7);
- BF(z[2].im, z[0].im, t2, t5);
-}
-
-static void fft8(FFTComplex *z)
-{
- FFTSample t1, t2, t3, t4, t5, t6;
-
- fft4(z);
-
- BF(t1, z[5].re, z[4].re, -z[5].re);
- BF(t2, z[5].im, z[4].im, -z[5].im);
- BF(t5, z[7].re, z[6].re, -z[7].re);
- BF(t6, z[7].im, z[6].im, -z[7].im);
-
- BUTTERFLIES(z[0],z[2],z[4],z[6]);
- TRANSFORM(z[1],z[3],z[5],z[7],M_SQRT1_2,M_SQRT1_2);
-}
-
-static void fft16(FFTComplex *z)
-{
- FFTSample t1, t2, t3, t4, t5, t6;
- FFTSample cos_16_1 = FFT_NAME(ff_cos_16)[1];
- FFTSample cos_16_3 = FFT_NAME(ff_cos_16)[3];
-
- fft8(z);
- fft4(z+8);
- fft4(z+12);
-
- TRANSFORM_ZERO(z[0],z[4],z[8],z[12]);
- TRANSFORM(z[2],z[6],z[10],z[14],M_SQRT1_2,M_SQRT1_2);
- TRANSFORM(z[1],z[5],z[9],z[13],cos_16_1,cos_16_3);
- TRANSFORM(z[3],z[7],z[11],z[15],cos_16_3,cos_16_1);
-}
-
-DECL_FFT(32,16,8)
-DECL_FFT(64,32,16)
-DECL_FFT(128,64,32)
-DECL_FFT(256,128,64)
-DECL_FFT(512,256,128)
-#define pass pass_big
-DECL_FFT(1024,512,256)
-DECL_FFT(2048,1024,512)
-DECL_FFT(4096,2048,1024)
-DECL_FFT(8192,4096,2048)
-DECL_FFT(16384,8192,4096)
-DECL_FFT(32768,16384,8192)
-DECL_FFT(65536,32768,16384)
-DECL_FFT(131072,65536,32768)
-
-static void (* const fft_dispatch[])(FFTComplex*) = {
- fft4, fft8, fft16, fft32, fft64, fft128, fft256, fft512, fft1024,
- fft2048, fft4096, fft8192, fft16384, fft32768, fft65536, fft131072
-};
-
-#define DECL_COMP_FFT(N) \
-static void compound_fft_##N##xM(AVTXContext *s, void *_out, \
- void *_in, ptrdiff_t stride) \
-{ \
- const int m = s->m, *in_map = s->pfatab, *out_map = in_map + N*m; \
- FFTComplex *in = _in; \
- FFTComplex *out = _out; \
- FFTComplex fft##N##in[N]; \
- void (*fftp)(FFTComplex *z) = fft_dispatch[av_log2(m) - 2]; \
- \
- for (int i = 0; i < m; i++) { \
- for (int j = 0; j < N; j++) \
- fft##N##in[j] = in[in_map[i*N + j]]; \
- fft##N(s->tmp + s->revtab[i], fft##N##in, m); \
- } \
- \
- for (int i = 0; i < N; i++) \
- fftp(s->tmp + m*i); \
- \
- for (int i = 0; i < N*m; i++) \
- out[i] = s->tmp[out_map[i]]; \
-}