1 /*
2 * This file is part of FFmpeg.
3 *
4 * FFmpeg is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * FFmpeg is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with FFmpeg; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18
19 #include "tx_priv.h"
20
ff_tx_type_is_mdct(enum AVTXType type)21 int ff_tx_type_is_mdct(enum AVTXType type)
22 {
23 switch (type) {
24 case AV_TX_FLOAT_MDCT:
25 case AV_TX_DOUBLE_MDCT:
26 case AV_TX_INT32_MDCT:
27 return 1;
28 default:
29 return 0;
30 }
31 }
32
33 /* Calculates the modular multiplicative inverse, not fast, replace */
mulinv(int n,int m)34 static av_always_inline int mulinv(int n, int m)
35 {
36 n = n % m;
37 for (int x = 1; x < m; x++)
38 if (((n * x) % m) == 1)
39 return x;
40 av_assert0(0); /* Never reached */
41 }
42
43 /* Guaranteed to work for any n, m where gcd(n, m) == 1 */
ff_tx_gen_compound_mapping(AVTXContext * s)44 int ff_tx_gen_compound_mapping(AVTXContext *s)
45 {
46 int *in_map, *out_map;
47 const int n = s->n;
48 const int m = s->m;
49 const int inv = s->inv;
50 const int len = n*m;
51 const int m_inv = mulinv(m, n);
52 const int n_inv = mulinv(n, m);
53 const int mdct = ff_tx_type_is_mdct(s->type);
54
55 if (!(s->pfatab = av_malloc(2*len*sizeof(*s->pfatab))))
56 return AVERROR(ENOMEM);
57
58 in_map = s->pfatab;
59 out_map = s->pfatab + n*m;
60
61 /* Ruritanian map for input, CRT map for output, can be swapped */
62 for (int j = 0; j < m; j++) {
63 for (int i = 0; i < n; i++) {
64 /* Shifted by 1 to simplify MDCTs */
65 in_map[j*n + i] = ((i*m + j*n) % len) << mdct;
66 out_map[(i*m*m_inv + j*n*n_inv) % len] = i*m + j;
67 }
68 }
69
70 /* Change transform direction by reversing all ACs */
71 if (inv) {
72 for (int i = 0; i < m; i++) {
73 int *in = &in_map[i*n + 1]; /* Skip the DC */
74 for (int j = 0; j < ((n - 1) >> 1); j++)
75 FFSWAP(int, in[j], in[n - j - 2]);
76 }
77 }
78
79 /* Our 15-point transform is also a compound one, so embed its input map */
80 if (n == 15) {
81 for (int k = 0; k < m; k++) {
82 int tmp[15];
83 memcpy(tmp, &in_map[k*15], 15*sizeof(*tmp));
84 for (int i = 0; i < 5; i++) {
85 for (int j = 0; j < 3; j++)
86 in_map[k*15 + i*3 + j] = tmp[(i*3 + j*5) % 15];
87 }
88 }
89 }
90
91 return 0;
92 }
93
ff_tx_gen_ptwo_revtab(AVTXContext * s,int invert_lookup)94 int ff_tx_gen_ptwo_revtab(AVTXContext *s, int invert_lookup)
95 {
96 const int m = s->m, inv = s->inv;
97
98 if (!(s->revtab = av_malloc(m*sizeof(*s->revtab))))
99 return AVERROR(ENOMEM);
100
101 /* Default */
102 for (int i = 0; i < m; i++) {
103 int k = -split_radix_permutation(i, m, inv) & (m - 1);
104 if (invert_lookup)
105 s->revtab[i] = k;
106 else
107 s->revtab[k] = i;
108 }
109
110 return 0;
111 }
112
ff_tx_gen_ptwo_inplace_revtab_idx(AVTXContext * s)113 int ff_tx_gen_ptwo_inplace_revtab_idx(AVTXContext *s)
114 {
115 int nb_inplace_idx = 0;
116
117 if (!(s->inplace_idx = av_malloc(s->m*sizeof(*s->inplace_idx))))
118 return AVERROR(ENOMEM);
119
120 for (int src = 1; src < s->m; src++) {
121 int dst = s->revtab[src];
122 int found = 0;
123
124 if (dst <= src)
125 continue;
126
127 do {
128 for (int j = 0; j < nb_inplace_idx; j++) {
129 if (dst == s->inplace_idx[j]) {
130 found = 1;
131 break;
132 }
133 }
134 dst = s->revtab[dst];
135 } while (dst != src && !found);
136
137 if (!found)
138 s->inplace_idx[nb_inplace_idx++] = src;
139 }
140
141 s->inplace_idx[nb_inplace_idx++] = 0;
142
143 return 0;
144 }
145
av_tx_uninit(AVTXContext ** ctx)146 av_cold void av_tx_uninit(AVTXContext **ctx)
147 {
148 if (!(*ctx))
149 return;
150
151 av_free((*ctx)->pfatab);
152 av_free((*ctx)->exptab);
153 av_free((*ctx)->revtab);
154 av_free((*ctx)->inplace_idx);
155 av_free((*ctx)->tmp);
156
157 av_freep(ctx);
158 }
159
av_tx_init(AVTXContext ** ctx,av_tx_fn * tx,enum AVTXType type,int inv,int len,const void * scale,uint64_t flags)160 av_cold int av_tx_init(AVTXContext **ctx, av_tx_fn *tx, enum AVTXType type,
161 int inv, int len, const void *scale, uint64_t flags)
162 {
163 int err;
164 AVTXContext *s = av_mallocz(sizeof(*s));
165 if (!s)
166 return AVERROR(ENOMEM);
167
168 switch (type) {
169 case AV_TX_FLOAT_FFT:
170 case AV_TX_FLOAT_MDCT:
171 if ((err = ff_tx_init_mdct_fft_float(s, tx, type, inv, len, scale, flags)))
172 goto fail;
173 break;
174 case AV_TX_DOUBLE_FFT:
175 case AV_TX_DOUBLE_MDCT:
176 if ((err = ff_tx_init_mdct_fft_double(s, tx, type, inv, len, scale, flags)))
177 goto fail;
178 break;
179 case AV_TX_INT32_FFT:
180 case AV_TX_INT32_MDCT:
181 if ((err = ff_tx_init_mdct_fft_int32(s, tx, type, inv, len, scale, flags)))
182 goto fail;
183 break;
184 default:
185 err = AVERROR(EINVAL);
186 goto fail;
187 }
188
189 *ctx = s;
190
191 return 0;
192
193 fail:
194 av_tx_uninit(&s);
195 *tx = NULL;
196 return err;
197 }
198