FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavutil/tx.c
Date: 2026-09-24 08:25:19
Exec Total Coverage
Lines: 432 496 87.1%
Functions: 24 25 96.0%
Branches: 466 612 76.1%
Line Branch Exec Source
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 "avassert.h"
20 #include "intmath.h"
21 #include "cpu.h"
22 #include "mem.h"
23 #include "qsort.h"
24 #include "bprint.h"
25
26 #include "tx_priv.h"
27
28 #define TYPE_IS(type, x) \
29 (((x) == AV_TX_FLOAT_ ## type) || \
30 ((x) == AV_TX_DOUBLE_ ## type) || \
31 ((x) == AV_TX_INT32_ ## type))
32
33 /* Calculates the modular multiplicative inverse */
34 5482 static av_always_inline int mulinv(int n, int m)
35 {
36 5482 n = n % m;
37
1/2
✓ Branch 0 taken 55734 times.
✗ Branch 1 not taken.
 55734 for (int x = 1; x < m; x++)
38
2/2
✓ Branch 0 taken 5482 times.
✓ Branch 1 taken 50252 times.
 55734 if (((n * x) % m) == 1)
39 5482 return x;
40 ✗ av_assert0(0); /* Never reached */
41 return 0;
42 }
43
44 81 int ff_tx_gen_pfa_input_map(AVTXContext *s, FFTXCodeletOptions *opts,
45 int d1, int d2)
46 {
47 81 const int sl = d1*d2;
48
49 81 s->map = av_malloc(s->len*sizeof(*s->map));
50
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 81 times.
 81 if (!s->map)
51 ✗ return AVERROR(ENOMEM);
52
53
2/2
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 81 times.
 162 for (int k = 0; k < s->len; k += sl) {
54
3/6
✓ Branch 0 taken 81 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 81 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 81 times.
 81 if (s->inv || (opts && opts->map_dir == FF_TX_MAP_SCATTER)) {
55 ✗ for (int m = 0; m < d2; m++)
56 ✗ for (int n = 0; n < d1; n++)
57 ✗ s->map[k + ((m*d1 + n*d2) % (sl))] = m*d1 + n;
58 } else {
59
2/2
✓ Branch 0 taken 405 times.
✓ Branch 1 taken 81 times.
 486 for (int m = 0; m < d2; m++)
60
2/2
✓ Branch 0 taken 1215 times.
✓ Branch 1 taken 405 times.
 1620 for (int n = 0; n < d1; n++)
61 1215 s->map[k + m*d1 + n] = (m*d1 + n*d2) % (sl);
62 }
63
64
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 81 times.
 81 if (s->inv)
65 ✗ for (int w = 1; w <= ((sl) >> 1); w++)
66 ✗ FFSWAP(int, s->map[k + w], s->map[k + sl - w]);
67 }
68
69
1/2
✓ Branch 0 taken 81 times.
✗ Branch 1 not taken.
 81 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
70
71 81 return 0;
72 }
73
74 /* Guaranteed to work for any n, m where gcd(n, m) == 1 */
75 2741 int ff_tx_gen_compound_mapping(AVTXContext *s, FFTXCodeletOptions *opts,
76 int inv, int n, int m)
77 {
78 int *in_map, *out_map;
79 2741 const int len = n*m; /* Will not be equal to s->len for MDCTs */
80 int m_inv, n_inv;
81
82 /* Make sure the numbers are coprime */
83
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2741 times.
 2741 if (av_gcd(n, m) != 1)
84 ✗ return AVERROR(EINVAL);
85
86 2741 m_inv = mulinv(m, n);
87 2741 n_inv = mulinv(n, m);
88
89
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 2741 times.
 2741 if (!(s->map = av_malloc(2*len*sizeof(*s->map))))
90 ✗ return AVERROR(ENOMEM);
91
92 2741 in_map = s->map;
93 2741 out_map = s->map + len;
94
95 /* Ruritanian map for input, CRT map for output, can be swapped */
96
3/4
✓ Branch 0 taken 519 times.
✓ Branch 1 taken 2222 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 519 times.
 2741 if (opts && opts->map_dir == FF_TX_MAP_SCATTER) {
97 ✗ for (int j = 0; j < m; j++) {
98 ✗ for (int i = 0; i < n; i++) {
99 ✗ in_map[(i*m + j*n) % len] = j*n + i;
100 ✗ out_map[(i*m*m_inv + j*n*n_inv) % len] = i*m + j;
101 }
102 }
103 } else {
104
2/2
✓ Branch 0 taken 95136 times.
✓ Branch 1 taken 2741 times.
 97877 for (int j = 0; j < m; j++) {
105
2/2
✓ Branch 0 taken 725904 times.
✓ Branch 1 taken 95136 times.
 821040 for (int i = 0; i < n; i++) {
106 725904 in_map[j*n + i] = (i*m + j*n) % len;
107 725904 out_map[(i*m*m_inv + j*n*n_inv) % len] = i*m + j;
108 }
109 }
110 }
111
112
2/2
✓ Branch 0 taken 2633 times.
✓ Branch 1 taken 108 times.
 2741 if (inv) {
113
2/2
✓ Branch 0 taken 89304 times.
✓ Branch 1 taken 2633 times.
 91937 for (int i = 0; i < m; i++) {
114 89304 int *in = &in_map[i*n + 1]; /* Skip the DC */
115
2/2
✓ Branch 0 taken 274888 times.
✓ Branch 1 taken 89304 times.
 364192 for (int j = 0; j < ((n - 1) >> 1); j++)
116 274888 FFSWAP(int, in[j], in[n - j - 2]);
117 }
118 }
119
120
2/2
✓ Branch 0 taken 519 times.
✓ Branch 1 taken 2222 times.
 2741 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
121
122 2741 return 0;
123 }
124
125 12679650 static inline int split_radix_permutation(int i, int len, int inv)
126 {
127 12679650 len >>= 1;
128
2/2
✓ Branch 0 taken 1659346 times.
✓ Branch 1 taken 11020304 times.
 12679650 if (len <= 1)
129 1659346 return i & 1;
130
2/2
✓ Branch 0 taken 5510152 times.
✓ Branch 1 taken 5510152 times.
 11020304 if (!(i & len))
131 5510152 return split_radix_permutation(i, len, inv) * 2;
132 5510152 len >>= 1;
133 5510152 return split_radix_permutation(i, len, inv) * 4 + 1 - 2*(!(i & len) ^ inv);
134 }
135
136 5170 int ff_tx_gen_ptwo_revtab(AVTXContext *s, FFTXCodeletOptions *opts)
137 {
138 5170 int len = s->len;
139
140
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 5170 times.
 5170 if (!(s->map = av_malloc(len*sizeof(*s->map))))
141 ✗ return AVERROR(ENOMEM);
142
143
3/4
✓ Branch 0 taken 5170 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2380 times.
✓ Branch 3 taken 2790 times.
 5170 if (opts && opts->map_dir == FF_TX_MAP_SCATTER) {
144
2/2
✓ Branch 0 taken 251044 times.
✓ Branch 1 taken 2380 times.
 253424 for (int i = 0; i < s->len; i++)
145 251044 s->map[-split_radix_permutation(i, len, s->inv) & (len - 1)] = i;
146 } else {
147
2/2
✓ Branch 0 taken 1132170 times.
✓ Branch 1 taken 2790 times.
 1134960 for (int i = 0; i < s->len; i++)
148 1132170 s->map[i] = -split_radix_permutation(i, len, s->inv) & (len - 1);
149 }
150
151
1/2
✓ Branch 0 taken 5170 times.
✗ Branch 1 not taken.
 5170 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
152
153 5170 return 0;
154 }
155
156 ✗ int ff_tx_gen_inplace_map(AVTXContext *s, int len)
157 {
158 ✗ int *src_map, out_map_idx = 0;
159
160 ✗ if (!s->sub || !s->sub->map)
161 ✗ return AVERROR(EINVAL);
162
163 ✗ if (!(s->map = av_mallocz(len*sizeof(*s->map))))
164 ✗ return AVERROR(ENOMEM);
165
166 ✗ src_map = s->sub->map;
167
168 /* The first coefficient is always already in-place */
169 ✗ for (int src = 1; src < s->len; src++) {
170 ✗ int dst = src_map[src];
171 ✗ int found = 0;
172
173 ✗ if (dst <= src)
174 ✗ continue;
175
176 /* This just checks if a closed loop has been encountered before,
177 * and if so, skips it, since to fully permute a loop we must only
178 * enter it once. */
179 do {
180 ✗ for (int j = 0; j < out_map_idx; j++) {
181 ✗ if (dst == s->map[j]) {
182 ✗ found = 1;
183 ✗ break;
184 }
185 }
186 ✗ dst = src_map[dst];
187 ✗ } while (dst != src && !found);
188
189 ✗ if (!found)
190 ✗ s->map[out_map_idx++] = src;
191 }
192
193 ✗ s->map[out_map_idx++] = 0;
194
195 ✗ return 0;
196 }
197
198 68071 static void parity_revtab_generator(int *revtab, int n, int inv, int offset,
199 int is_dual, int dual_high, int len,
200 int basis, int dual_stride, int inv_lookup)
201 {
202 68071 len >>= 1;
203
204
2/2
✓ Branch 0 taken 45951 times.
✓ Branch 1 taken 22120 times.
 68071 if (len <= basis) {
205 int k1, k2, stride, even_idx, odd_idx;
206
207
3/4
✓ Branch 0 taken 34330 times.
✓ Branch 1 taken 11621 times.
✓ Branch 2 taken 34330 times.
✗ Branch 3 not taken.
 45951 is_dual = is_dual && dual_stride;
208 45951 dual_high = is_dual & dual_high;
209
2/2
✓ Branch 0 taken 34330 times.
✓ Branch 1 taken 11621 times.
 45951 stride = is_dual ? FFMIN(dual_stride, len) : 0;
210
211 45951 even_idx = offset + dual_high*(stride - 2*len);
212
4/4
✓ Branch 0 taken 34330 times.
✓ Branch 1 taken 11621 times.
✓ Branch 2 taken 17165 times.
✓ Branch 3 taken 17165 times.
 45951 odd_idx = even_idx + len + (is_dual && !dual_high)*len + dual_high*len;
213
214
2/2
✓ Branch 0 taken 138066 times.
✓ Branch 1 taken 45951 times.
 184017 for (int i = 0; i < len; i++) {
215 138066 k1 = -split_radix_permutation(offset + i*2 + 0, n, inv) & (n - 1);
216 138066 k2 = -split_radix_permutation(offset + i*2 + 1, n, inv) & (n - 1);
217
2/2
✓ Branch 0 taken 102484 times.
✓ Branch 1 taken 35582 times.
 138066 if (inv_lookup) {
218 102484 revtab[even_idx++] = k1;
219 102484 revtab[odd_idx++] = k2;
220 } else {
221 35582 revtab[k1] = even_idx++;
222 35582 revtab[k2] = odd_idx++;
223 }
224
4/4
✓ Branch 0 taken 91924 times.
✓ Branch 1 taken 46142 times.
✓ Branch 2 taken 45962 times.
✓ Branch 3 taken 45962 times.
 138066 if (stride && !((i + 1) % stride)) {
225 45962 even_idx += stride;
226 45962 odd_idx += stride;
227 }
228 }
229
230 45951 return;
231 }
232
233 22120 parity_revtab_generator(revtab, n, inv, offset,
234 0, 0, len >> 0, basis, dual_stride, inv_lookup);
235 22120 parity_revtab_generator(revtab, n, inv, offset + (len >> 0),
236 1, 0, len >> 1, basis, dual_stride, inv_lookup);
237 22120 parity_revtab_generator(revtab, n, inv, offset + (len >> 0) + (len >> 1),
238 1, 1, len >> 1, basis, dual_stride, inv_lookup);
239 }
240
241 1711 int ff_tx_gen_split_radix_parity_revtab(AVTXContext *s, int len, int inv,
242 FFTXCodeletOptions *opts,
243 int basis, int dual_stride)
244 {
245 1711 basis >>= 1;
246
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1711 times.
 1711 if (len < basis)
247 ✗ return AVERROR(EINVAL);
248
249
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1711 times.
 1711 if (!(s->map = av_mallocz(len*sizeof(*s->map))))
250 ✗ return AVERROR(ENOMEM);
251
252
3/4
✓ Branch 0 taken 1439 times.
✓ Branch 1 taken 272 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1439 times.
 1711 av_assert0(!dual_stride || !(dual_stride & (dual_stride - 1)));
253
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1711 times.
 1711 av_assert0(dual_stride <= basis);
254
255
2/2
✓ Branch 0 taken 1687 times.
✓ Branch 1 taken 24 times.
 3398 parity_revtab_generator(s->map, len, inv, 0, 0, 0, len,
256 basis, dual_stride,
257
2/2
✓ Branch 0 taken 853 times.
✓ Branch 1 taken 834 times.
 1687 opts ? opts->map_dir == FF_TX_MAP_GATHER : FF_TX_MAP_GATHER);
258
259
2/2
✓ Branch 0 taken 1687 times.
✓ Branch 1 taken 24 times.
 1711 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
260
261 1711 return 0;
262 }
263
264 42520 static void reset_ctx(AVTXContext *s, int free_sub)
265 {
266
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 42520 times.
 42520 if (!s)
267 ✗ return;
268
269
2/2
✓ Branch 0 taken 7593 times.
✓ Branch 1 taken 34927 times.
 42520 if (s->sub)
270
2/2
✓ Branch 0 taken 30372 times.
✓ Branch 1 taken 7593 times.
 37965 for (int i = 0; i < TX_MAX_SUB; i++)
271 30372 reset_ctx(&s->sub[i], free_sub + 1);
272
273
3/4
✓ Branch 0 taken 19838 times.
✓ Branch 1 taken 22682 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19838 times.
 42520 if (s->cd_self && s->cd_self->uninit)
274 ✗ s->cd_self->uninit(s);
275
276
2/2
✓ Branch 0 taken 37302 times.
✓ Branch 1 taken 5218 times.
 42520 if (free_sub)
277 37302 av_freep(&s->sub);
278
279 42520 av_freep(&s->map);
280 42520 av_freep(&s->exp);
281 42520 av_freep(&s->tmp);
282
283 /* Nothing else needs to be reset, it gets overwritten if another
284 * ff_tx_init_subtx() call is made. */
285 42520 s->nb_sub = 0;
286 42520 s->opaque = NULL;
287 42520 memset(s->fn, 0, sizeof(s->fn));
288 }
289
290 97 void ff_tx_clear_ctx(AVTXContext *s)
291 {
292 97 reset_ctx(s, 0);
293 97 }
294
295 7579 av_cold void av_tx_uninit(AVTXContext **ctx)
296 {
297
2/2
✓ Branch 0 taken 649 times.
✓ Branch 1 taken 6930 times.
 7579 if (!(*ctx))
298 649 return;
299
300 6930 reset_ctx(*ctx, 1);
301 6930 av_freep(ctx);
302 }
303
304 14 static av_cold int ff_tx_null_init(AVTXContext *s, const FFTXCodelet *cd,
305 uint64_t flags, FFTXCodeletOptions *opts,
306 int len, int inv, const void *scale)
307 {
308 /* Can only handle one sample+type to one sample+type transforms */
309
6/12
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 14 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 14 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 14 times.
 14 if (TYPE_IS(MDCT, s->type) || TYPE_IS(RDFT, s->type))
310 ✗ return AVERROR(EINVAL);
311 14 return 0;
312 }
313
314 /* Null transform when the length is 1 */
315 3 static void ff_tx_null(AVTXContext *s, void *_out, void *_in, ptrdiff_t stride)
316 {
317 3 memcpy(_out, _in, stride);
318 3 }
319
320 static const FFTXCodelet ff_tx_null_def = {
321 .name = NULL_IF_CONFIG_SMALL("null"),
322 .function = ff_tx_null,
323 .type = TX_TYPE_ANY,
324 .flags = AV_TX_UNALIGNED | FF_TX_ALIGNED |
325 FF_TX_OUT_OF_PLACE | AV_TX_INPLACE,
326 .factors[0] = TX_FACTOR_ANY,
327 .min_len = 1,
328 .max_len = 1,
329 .init = ff_tx_null_init,
330 .cpu_flags = FF_TX_CPU_FLAGS_ALL,
331 .prio = FF_TX_PRIO_MAX,
332 };
333
334 static const FFTXCodelet * const ff_tx_null_list[] = {
335 &ff_tx_null_def,
336 NULL,
337 };
338
339 /* Array of all compiled codelet lists. Order is irrelevant. */
340 static const FFTXCodelet * const * const codelet_list[] = {
341 ff_tx_codelet_list_float_c,
342 ff_tx_codelet_list_double_c,
343 ff_tx_codelet_list_int32_c,
344 ff_tx_null_list,
345 #if HAVE_X86ASM
346 ff_tx_codelet_list_float_x86,
347 #endif
348 #if ARCH_AARCH64
349 ff_tx_codelet_list_float_aarch64,
350 #endif
351 };
352 static const int codelet_list_num = FF_ARRAY_ELEMS(codelet_list);
353
354 static const int cpu_slow_mask = AV_CPU_FLAG_SSE2SLOW | AV_CPU_FLAG_SSE3SLOW |
355 AV_CPU_FLAG_ATOM | AV_CPU_FLAG_SSSE3SLOW |
356 AV_CPU_FLAG_AVXSLOW | AV_CPU_FLAG_SLOW_GATHER;
357
358 static const int cpu_slow_penalties[][2] = {
359 { AV_CPU_FLAG_SSE2SLOW, 1 + 64 },
360 { AV_CPU_FLAG_SSE3SLOW, 1 + 64 },
361 { AV_CPU_FLAG_SSSE3SLOW, 1 + 64 },
362 { AV_CPU_FLAG_ATOM, 1 + 128 },
363 { AV_CPU_FLAG_AVXSLOW, 1 + 128 },
364 { AV_CPU_FLAG_SLOW_GATHER, 1 + 32 },
365 };
366
367 39016 static int get_codelet_prio(const FFTXCodelet *cd, int cpu_flags, int len)
368 {
369 39016 int prio = cd->prio;
370 39016 int max_factor = 0;
371
372 /* If the CPU has a SLOW flag, and the instruction is also flagged
373 * as being slow for such, reduce its priority */
374
2/2
✓ Branch 0 taken 234096 times.
✓ Branch 1 taken 39016 times.
 273112 for (int i = 0; i < FF_ARRAY_ELEMS(cpu_slow_penalties); i++) {
375
2/2
✓ Branch 0 taken 2652 times.
✓ Branch 1 taken 231444 times.
 234096 if ((cpu_flags & cd->cpu_flags) & cpu_slow_penalties[i][0])
376 2652 prio -= cpu_slow_penalties[i][1];
377 }
378
379 /* Prioritize aligned-only codelets */
380
4/4
✓ Branch 0 taken 5956 times.
✓ Branch 1 taken 33060 times.
✓ Branch 2 taken 5942 times.
✓ Branch 3 taken 14 times.
 39016 if ((cd->flags & FF_TX_ALIGNED) && !(cd->flags & AV_TX_UNALIGNED))
381 5942 prio += 64;
382
383 /* Codelets for specific lengths are generally faster */
384
4/4
✓ Branch 0 taken 8999 times.
✓ Branch 1 taken 30017 times.
✓ Branch 2 taken 8193 times.
✓ Branch 3 taken 806 times.
 39016 if ((len == cd->min_len) && (len == cd->max_len))
385 8193 prio += 64;
386
387 /* Forward-only or inverse-only transforms are generally better */
388
2/2
✓ Branch 0 taken 21172 times.
✓ Branch 1 taken 17844 times.
 39016 if ((cd->flags & (FF_TX_FORWARD_ONLY | FF_TX_INVERSE_ONLY)))
389 21172 prio += 64;
390
391 /* Larger factors are generally better */
392
2/2
✓ Branch 0 taken 156064 times.
✓ Branch 1 taken 39016 times.
 195080 for (int i = 0; i < TX_MAX_SUB; i++)
393 156064 max_factor = FFMAX(cd->factors[i], max_factor);
394
2/2
✓ Branch 0 taken 37106 times.
✓ Branch 1 taken 1910 times.
 39016 if (max_factor)
395 37106 prio += 16*max_factor;
396
397 39016 return prio;
398 }
399
400 typedef struct FFTXLenDecomp {
401 int len;
402 int len2;
403 int prio;
404 const FFTXCodelet *cd;
405 } FFTXLenDecomp;
406
407 475 static int cmp_decomp(FFTXLenDecomp *a, FFTXLenDecomp *b)
408 {
409 475 return FFDIFFSIGN(b->prio, a->prio);
410 }
411
412 5018 int ff_tx_decompose_length(int dst[TX_MAX_DECOMPOSITIONS], enum AVTXType type,
413 int len, int inv)
414 {
415 5018 int nb_decomp = 0;
416 FFTXLenDecomp ld[TX_MAX_DECOMPOSITIONS];
417 5018 int codelet_list_idx = codelet_list_num;
418
419 5018 const int cpu_flags = av_get_cpu_flags();
420
421 /* Loop through all codelets in all codelet lists to find matches
422 * to the requirements */
423
2/2
✓ Branch 0 taken 25090 times.
✓ Branch 1 taken 5018 times.
 30108 while (codelet_list_idx--) {
424 25090 const FFTXCodelet * const * list = codelet_list[codelet_list_idx];
425 25090 const FFTXCodelet *cd = NULL;
426
427
2/2
✓ Branch 0 taken 1083888 times.
✓ Branch 1 taken 25090 times.
 1108978 while ((cd = *list++)) {
428 1083888 int fl = len;
429 1083888 int skip = 0, prio;
430 1083888 int factors_product = 1, factors_mod = 0;
431
432
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1083888 times.
 1083888 if (nb_decomp >= TX_MAX_DECOMPOSITIONS)
433 ✗ goto sort;
434
435 /* Check if the type matches */
436
4/4
✓ Branch 0 taken 1078870 times.
✓ Branch 1 taken 5018 times.
✓ Branch 2 taken 733756 times.
✓ Branch 3 taken 345114 times.
 1083888 if (cd->type != TX_TYPE_ANY && type != cd->type)
437 733756 continue;
438
439 /* Check direction for non-orthogonal codelets */
440
4/4
✓ Branch 0 taken 24560 times.
✓ Branch 1 taken 325572 times.
✓ Branch 2 taken 4163 times.
✓ Branch 3 taken 20397 times.
 350132 if (((cd->flags & FF_TX_FORWARD_ONLY) && inv) ||
441
4/4
✓ Branch 0 taken 8976 times.
✓ Branch 1 taken 320759 times.
✓ Branch 2 taken 7770 times.
✓ Branch 3 taken 1206 times.
 329735 ((cd->flags & (FF_TX_INVERSE_ONLY | AV_TX_FULL_IMDCT)) && !inv) ||
442
3/4
✓ Branch 0 taken 4163 times.
✓ Branch 1 taken 324366 times.
✓ Branch 2 taken 4163 times.
✗ Branch 3 not taken.
 328529 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_REAL)) && inv) ||
443
3/4
✓ Branch 0 taken 4163 times.
✓ Branch 1 taken 324366 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4163 times.
 328529 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_IMAGINARY)) && inv))
444 21603 continue;
445
446 /* Check if the CPU supports the required ISA */
447
2/2
✓ Branch 0 taken 174429 times.
✓ Branch 1 taken 154100 times.
 328529 if (cd->cpu_flags != FF_TX_CPU_FLAGS_ALL &&
448
2/2
✓ Branch 0 taken 173021 times.
✓ Branch 1 taken 1408 times.
 174429 !(cpu_flags & (cd->cpu_flags & ~cpu_slow_mask)))
449 173021 continue;
450
451
1/2
✓ Branch 0 taken 341124 times.
✗ Branch 1 not taken.
 341124 for (int i = 0; i < TX_MAX_FACTORS; i++) {
452
4/4
✓ Branch 0 taken 195636 times.
✓ Branch 1 taken 145488 times.
✓ Branch 2 taken 185616 times.
✓ Branch 3 taken 10020 times.
 341124 if (!cd->factors[i] || (fl == 1))
453 break;
454
455
2/2
✓ Branch 0 taken 30124 times.
✓ Branch 1 taken 155492 times.
 185616 if (cd->factors[i] == TX_FACTOR_ANY) {
456 30124 factors_mod++;
457 30124 factors_product *= fl;
458
2/2
✓ Branch 0 taken 97287 times.
✓ Branch 1 taken 58205 times.
 155492 } else if (!(fl % cd->factors[i])) {
459 97287 factors_mod++;
460
2/2
✓ Branch 0 taken 96446 times.
✓ Branch 1 taken 841 times.
 97287 if (cd->factors[i] == 2) {
461 96446 int b = ff_ctz(fl);
462 96446 fl >>= b;
463 96446 factors_product <<= b;
464 } else {
465 do {
466 873 fl /= cd->factors[i];
467 873 factors_product *= cd->factors[i];
468
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 841 times.
 873 } while (!(fl % cd->factors[i]));
469 }
470 }
471 }
472
473 /* Disqualify if factor requirements are not satisfied or if trivial */
474
4/4
✓ Branch 0 taken 117213 times.
✓ Branch 1 taken 38295 times.
✓ Branch 2 taken 115043 times.
✓ Branch 3 taken 2170 times.
 155508 if ((factors_mod < cd->nb_factors) || (len == factors_product))
475 153338 continue;
476
477
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2170 times.
 2170 if (av_gcd(factors_product, fl) != 1)
478 ✗ continue;
479
480 /* Check if length is supported and factorization was successful */
481
2/2
✓ Branch 0 taken 1198 times.
✓ Branch 1 taken 972 times.
 2170 if ((factors_product < cd->min_len) ||
482
3/4
✓ Branch 0 taken 1198 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 616 times.
✓ Branch 3 taken 582 times.
 1198 (cd->max_len != TX_LEN_UNLIMITED && (factors_product > cd->max_len)))
483 1588 continue;
484
485 582 prio = get_codelet_prio(cd, cpu_flags, factors_product) * factors_product;
486
487 /* Check for duplicates */
488
2/2
✓ Branch 0 taken 979 times.
✓ Branch 1 taken 348 times.
 1327 for (int i = 0; i < nb_decomp; i++) {
489
2/2
✓ Branch 0 taken 234 times.
✓ Branch 1 taken 745 times.
 979 if (factors_product == ld[i].len) {
490 /* Update priority if new one is higher */
491
2/2
✓ Branch 0 taken 204 times.
✓ Branch 1 taken 30 times.
 234 if (prio > ld[i].prio)
492 204 ld[i].prio = prio;
493 234 skip = 1;
494 234 break;
495 }
496 }
497
498 /* Add decomposition if unique */
499
2/2
✓ Branch 0 taken 348 times.
✓ Branch 1 taken 234 times.
 582 if (!skip) {
500 348 ld[nb_decomp].cd = cd;
501 348 ld[nb_decomp].len = factors_product;
502 348 ld[nb_decomp].len2 = fl;
503 348 ld[nb_decomp].prio = prio;
504 348 nb_decomp++;
505 }
506 }
507 }
508
509
2/2
✓ Branch 0 taken 4921 times.
✓ Branch 1 taken 97 times.
 5018 if (!nb_decomp)
510 4921 return AVERROR(EINVAL);
511
512 97 sort:
513
27/44
✓ Branch 0 taken 81 times.
✓ Branch 1 taken 89 times.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 54 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 27 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 54 times.
✓ Branch 12 taken 81 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 81 times.
✓ Branch 16 taken 81 times.
✓ Branch 17 taken 19 times.
✓ Branch 19 taken 19 times.
✓ Branch 20 taken 62 times.
✓ Branch 21 taken 62 times.
✓ Branch 22 taken 81 times.
✓ Branch 24 taken 62 times.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✓ Branch 27 taken 81 times.
✓ Branch 28 taken 81 times.
✓ Branch 29 taken 81 times.
✗ Branch 30 not taken.
✓ Branch 31 taken 81 times.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✓ Branch 43 taken 19 times.
✓ Branch 44 taken 62 times.
✓ Branch 46 taken 8 times.
✓ Branch 47 taken 81 times.
✓ Branch 48 taken 170 times.
✓ Branch 49 taken 89 times.
✓ Branch 50 taken 178 times.
✓ Branch 51 taken 97 times.
 599 AV_QSORT(ld, nb_decomp, FFTXLenDecomp, cmp_decomp);
514
515
2/2
✓ Branch 0 taken 348 times.
✓ Branch 1 taken 97 times.
 445 for (int i = 0; i < nb_decomp; i++) {
516
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 348 times.
 348 if (ld[i].cd->nb_factors > 1)
517 ✗ dst[i] = ld[i].len2;
518 else
519 348 dst[i] = ld[i].len;
520 }
521
522 97 return nb_decomp;
523 }
524
525 24 int ff_tx_gen_default_map(AVTXContext *s, FFTXCodeletOptions *opts)
526 {
527 24 s->map = av_malloc(s->len*sizeof(*s->map));
528
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (!s->map)
529 ✗ return AVERROR(ENOMEM);
530
531 24 s->map[0] = 0; /* DC is always at the start */
532
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (s->inv) /* Reversing the ACs flips the transform direction */
533 ✗ for (int i = 1; i < s->len; i++)
534 ✗ s->map[i] = s->len - i;
535 else
536
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 24 times.
 168 for (int i = 1; i < s->len; i++)
537 144 s->map[i] = i;
538
539 24 s->map_dir = FF_TX_MAP_GATHER;
540
541 24 return 0;
542 }
543
544 #if !CONFIG_SMALL
545 67896 static void print_flags(AVBPrint *bp, uint64_t f)
546 {
547 67896 int prev = 0;
548 67896 const char *sep = ", ";
549 67896 av_bprintf(bp, "flags: [");
550
3/4
✓ Branch 0 taken 24371 times.
✓ Branch 1 taken 43525 times.
✓ Branch 2 taken 24371 times.
✗ Branch 3 not taken.
 67896 if ((f & FF_TX_ALIGNED) && ++prev)
551 24371 av_bprintf(bp, "aligned");
552
3/4
✓ Branch 0 taken 43553 times.
✓ Branch 1 taken 24343 times.
✓ Branch 2 taken 43553 times.
✗ Branch 3 not taken.
 67896 if ((f & AV_TX_UNALIGNED) && ++prev)
553
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 43525 times.
 43553 av_bprintf(bp, "%sunaligned", prev > 1 ? sep : "");
554
3/4
✓ Branch 0 taken 31839 times.
✓ Branch 1 taken 36057 times.
✓ Branch 2 taken 31839 times.
✗ Branch 3 not taken.
 67896 if ((f & AV_TX_INPLACE) && ++prev)
555
1/2
✓ Branch 0 taken 31839 times.
✗ Branch 1 not taken.
 31839 av_bprintf(bp, "%sinplace", prev > 1 ? sep : "");
556
3/4
✓ Branch 0 taken 60276 times.
✓ Branch 1 taken 7620 times.
✓ Branch 2 taken 60276 times.
✗ Branch 3 not taken.
 67896 if ((f & FF_TX_OUT_OF_PLACE) && ++prev)
557
1/2
✓ Branch 0 taken 60276 times.
✗ Branch 1 not taken.
 60276 av_bprintf(bp, "%sout_of_place", prev > 1 ? sep : "");
558
3/4
✓ Branch 0 taken 1603 times.
✓ Branch 1 taken 66293 times.
✓ Branch 2 taken 1603 times.
✗ Branch 3 not taken.
 67896 if ((f & FF_TX_FORWARD_ONLY) && ++prev)
559
1/2
✓ Branch 0 taken 1603 times.
✗ Branch 1 not taken.
 1603 av_bprintf(bp, "%sfwd_only", prev > 1 ? sep : "");
560
3/4
✓ Branch 0 taken 26005 times.
✓ Branch 1 taken 41891 times.
✓ Branch 2 taken 26005 times.
✗ Branch 3 not taken.
 67896 if ((f & FF_TX_INVERSE_ONLY) && ++prev)
561
1/2
✓ Branch 0 taken 26005 times.
✗ Branch 1 not taken.
 26005 av_bprintf(bp, "%sinv_only", prev > 1 ? sep : "");
562
3/4
✓ Branch 0 taken 30221 times.
✓ Branch 1 taken 37675 times.
✓ Branch 2 taken 30221 times.
✗ Branch 3 not taken.
 67896 if ((f & FF_TX_PRESHUFFLE) && ++prev)
563
1/2
✓ Branch 0 taken 30221 times.
✗ Branch 1 not taken.
 30221 av_bprintf(bp, "%spreshuf", prev > 1 ? sep : "");
564
3/4
✓ Branch 0 taken 306 times.
✓ Branch 1 taken 67590 times.
✓ Branch 2 taken 306 times.
✗ Branch 3 not taken.
 67896 if ((f & AV_TX_FULL_IMDCT) && ++prev)
565
1/2
✓ Branch 0 taken 306 times.
✗ Branch 1 not taken.
 306 av_bprintf(bp, "%simdct_full", prev > 1 ? sep : "");
566
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 67872 times.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 67896 if ((f & AV_TX_REAL_TO_REAL) && ++prev)
567
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 av_bprintf(bp, "%sreal_to_real", prev > 1 ? sep : "");
568
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 67872 times.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 67896 if ((f & AV_TX_REAL_TO_IMAGINARY) && ++prev)
569
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
 24 av_bprintf(bp, "%sreal_to_imaginary", prev > 1 ? sep : "");
570
3/4
✓ Branch 0 taken 7392 times.
✓ Branch 1 taken 60504 times.
✓ Branch 2 taken 7392 times.
✗ Branch 3 not taken.
 67896 if ((f & FF_TX_ASM_CALL) && ++prev)
571
1/2
✓ Branch 0 taken 7392 times.
✗ Branch 1 not taken.
 7392 av_bprintf(bp, "%sasm_call", prev > 1 ? sep : "");
572 67896 av_bprintf(bp, "]");
573 67896 }
574
575 67896 static void print_type(AVBPrint *bp, enum AVTXType type)
576 {
577
2/2
✓ Branch 0 taken 67868 times.
✓ Branch 1 taken 28 times.
 135764 av_bprintf(bp, "%s",
578 type == TX_TYPE_ANY ? "any" :
579
2/2
✓ Branch 0 taken 37661 times.
✓ Branch 1 taken 30207 times.
 105529 type == AV_TX_FLOAT_FFT ? "fft_float" :
580
2/2
✓ Branch 0 taken 4789 times.
✓ Branch 1 taken 32872 times.
 42450 type == AV_TX_FLOAT_MDCT ? "mdct_float" :
581
2/2
✓ Branch 0 taken 4594 times.
✓ Branch 1 taken 195 times.
 9383 type == AV_TX_FLOAT_RDFT ? "rdft_float" :
582
2/2
✓ Branch 0 taken 4570 times.
✓ Branch 1 taken 24 times.
 9164 type == AV_TX_FLOAT_DCT_I ? "dctI_float" :
583
2/2
✓ Branch 0 taken 4546 times.
✓ Branch 1 taken 24 times.
 9116 type == AV_TX_FLOAT_DST_I ? "dstI_float" :
584
2/2
✓ Branch 0 taken 2614 times.
✓ Branch 1 taken 1932 times.
 7160 type == AV_TX_DOUBLE_FFT ? "fft_double" :
585
1/2
✓ Branch 0 taken 2614 times.
✗ Branch 1 not taken.
 5228 type == AV_TX_DOUBLE_MDCT ? "mdct_double" :
586
1/2
✓ Branch 0 taken 2614 times.
✗ Branch 1 not taken.
 5228 type == AV_TX_DOUBLE_RDFT ? "rdft_double" :
587
1/2
✓ Branch 0 taken 2614 times.
✗ Branch 1 not taken.
 5228 type == AV_TX_DOUBLE_DCT_I ? "dctI_double" :
588
1/2
✓ Branch 0 taken 2614 times.
✗ Branch 1 not taken.
 5228 type == AV_TX_DOUBLE_DST_I ? "dstI_double" :
589
2/2
✓ Branch 0 taken 1439 times.
✓ Branch 1 taken 1175 times.
 4053 type == AV_TX_INT32_FFT ? "fft_int32" :
590
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1427 times.
 1451 type == AV_TX_INT32_MDCT ? "mdct_int32" :
591
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 24 type == AV_TX_INT32_RDFT ? "rdft_int32" :
592
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 24 type == AV_TX_INT32_DCT_I ? "dctI_int32" :
593
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 type == AV_TX_INT32_DST_I ? "dstI_int32" :
594 "unknown");
595 67896 }
596
597 53054 static void print_cd_info(const FFTXCodelet *cd, int prio, int len, int print_prio,
598 int log_level)
599 {
600 AVBPrint bp;
601 53054 av_bprint_init(&bp, 0, AV_BPRINT_SIZE_AUTOMATIC);
602
603 53054 av_bprintf(&bp, "%s - type: ", cd->name);
604
605 53054 print_type(&bp, cd->type);
606
607 53054 av_bprintf(&bp, ", len: ");
608
2/2
✓ Branch 0 taken 38434 times.
✓ Branch 1 taken 14620 times.
 53054 if (!len) {
609
2/2
✓ Branch 0 taken 30805 times.
✓ Branch 1 taken 7629 times.
 38434 if (cd->min_len != cd->max_len)
610 30805 av_bprintf(&bp, "[%i, ", cd->min_len);
611
612
2/2
✓ Branch 0 taken 28246 times.
✓ Branch 1 taken 10188 times.
 38434 if (cd->max_len == TX_LEN_UNLIMITED)
613 28246 av_bprintf(&bp, "∞");
614 else
615 10188 av_bprintf(&bp, "%i", cd->max_len);
616 } else {
617 14620 av_bprintf(&bp, "%i", len);
618 }
619
620
2/2
✓ Branch 0 taken 34410 times.
✓ Branch 1 taken 18644 times.
 53054 if (cd->factors[1]) {
621
3/4
✓ Branch 0 taken 27061 times.
✓ Branch 1 taken 7349 times.
✓ Branch 2 taken 27061 times.
✗ Branch 3 not taken.
 34410 av_bprintf(&bp, "%s, factors", !len && cd->min_len != cd->max_len ? "]" : "");
622
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 34402 times.
 34410 if (!cd->nb_factors)
623 8 av_bprintf(&bp, ": [");
624 else
625 34402 av_bprintf(&bp, "[%i]: [", cd->nb_factors);
626
627
1/2
✓ Branch 0 taken 119856 times.
✗ Branch 1 not taken.
 119856 for (int i = 0; i < TX_MAX_FACTORS; i++) {
628
4/4
✓ Branch 0 taken 85446 times.
✓ Branch 1 taken 34410 times.
✓ Branch 2 taken 51036 times.
✓ Branch 3 taken 34410 times.
 119856 if (i && cd->factors[i])
629 51036 av_bprintf(&bp, ", ");
630
2/2
✓ Branch 0 taken 33366 times.
✓ Branch 1 taken 86490 times.
 119856 if (cd->factors[i] == TX_FACTOR_ANY)
631 33366 av_bprintf(&bp, "any");
632
2/2
✓ Branch 0 taken 52080 times.
✓ Branch 1 taken 34410 times.
 86490 else if (cd->factors[i])
633 52080 av_bprintf(&bp, "%i", cd->factors[i]);
634 else
635 34410 break;
636 }
637
638 34410 av_bprintf(&bp, "], ");
639 } else {
640 18644 av_bprintf(&bp, "%s, factor: %i, ",
641
4/4
✓ Branch 0 taken 11373 times.
✓ Branch 1 taken 7271 times.
✓ Branch 2 taken 3744 times.
✓ Branch 3 taken 7629 times.
 18644 !len && cd->min_len != cd->max_len ? "]" : "", cd->factors[0]);
642 }
643 53054 print_flags(&bp, cd->flags);
644
645
2/2
✓ Branch 0 taken 38434 times.
✓ Branch 1 taken 14620 times.
 53054 if (print_prio)
646 38434 av_bprintf(&bp, ", prio: %i", prio);
647
648 53054 av_log(NULL, log_level, "%s\n", bp.str);
649 53054 }
650
651 14620 static void print_tx_structure(AVTXContext *s, int depth)
652 {
653 14620 const FFTXCodelet *cd = s->cd_self;
654
655
2/2
✓ Branch 0 taken 23068 times.
✓ Branch 1 taken 14620 times.
 37688 for (int i = 0; i <= depth; i++)
656 23068 av_log(NULL, AV_LOG_DEBUG, " ");
657
658 14620 print_cd_info(cd, cd->prio, s->len, 0, AV_LOG_DEBUG);
659
660
2/2
✓ Branch 0 taken 7690 times.
✓ Branch 1 taken 14620 times.
 22310 for (int i = 0; i < s->nb_sub; i++)
661 7690 print_tx_structure(&s->sub[i], depth + 1);
662 14620 }
663 #endif /* CONFIG_SMALL */
664
665 typedef struct TXCodeletMatch {
666 const FFTXCodelet *cd;
667 int prio;
668 } TXCodeletMatch;
669
670 38964 static int cmp_matches(TXCodeletMatch *a, TXCodeletMatch *b)
671 {
672 38964 return FFDIFFSIGN(b->prio, a->prio);
673 }
674
675 /* We want all factors to completely cover the length */
676 66733 static inline int check_cd_factors(const FFTXCodelet *cd, int len)
677 {
678 66733 int matches = 0, any_flag = 0;
679
680
1/2
✓ Branch 0 taken 203720 times.
✗ Branch 1 not taken.
 203720 for (int i = 0; i < TX_MAX_FACTORS; i++) {
681 203720 int factor = cd->factors[i];
682
683
2/2
✓ Branch 0 taken 54564 times.
✓ Branch 1 taken 149156 times.
 203720 if (factor == TX_FACTOR_ANY) {
684 54564 any_flag = 1;
685 54564 matches++;
686 54564 continue;
687
4/4
✓ Branch 0 taken 124324 times.
✓ Branch 1 taken 24832 times.
✓ Branch 2 taken 82423 times.
✓ Branch 3 taken 41901 times.
 149156 } else if (len <= 1 || !factor) {
688 break;
689
2/2
✓ Branch 0 taken 32101 times.
✓ Branch 1 taken 50322 times.
 82423 } else if (factor == 2) { /* Fast path */
690 32101 int bits_2 = ff_ctz(len);
691
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 32053 times.
 32101 if (!bits_2)
692 48 continue; /* Factor not supported */
693
694 32053 len >>= bits_2;
695 32053 matches++;
696 } else {
697 50322 int res = len % factor;
698
2/2
✓ Branch 0 taken 42977 times.
✓ Branch 1 taken 7345 times.
 50322 if (res)
699 42977 continue; /* Factor not supported */
700
701
2/2
✓ Branch 0 taken 7555 times.
✓ Branch 1 taken 7345 times.
 14900 while (!res) {
702 7555 len /= factor;
703 7555 res = len % factor;
704 }
705 7345 matches++;
706 }
707 }
708
709
6/6
✓ Branch 0 taken 39817 times.
✓ Branch 1 taken 26916 times.
✓ Branch 2 taken 11457 times.
✓ Branch 3 taken 28360 times.
✓ Branch 4 taken 10074 times.
✓ Branch 5 taken 1383 times.
 66733 return (cd->nb_factors <= matches) && (any_flag || len == 1);
710 }
711
712 14842 av_cold int ff_tx_init_subtx(AVTXContext *s, enum AVTXType type,
713 uint64_t flags, FFTXCodeletOptions *opts,
714 int len, int inv, const void *scale)
715 {
716 14842 int ret = 0;
717 14842 AVTXContext *sub = NULL;
718 14842 TXCodeletMatch *cd_tmp, *cd_matches = NULL;
719 14842 unsigned int cd_matches_size = 0;
720 14842 int codelet_list_idx = codelet_list_num;
721 14842 int nb_cd_matches = 0;
722 #if !CONFIG_SMALL
723 AVBPrint bp;
724 #endif
725
726 /* We still accept functions marked with SLOW, even if the CPU is
727 * marked with the same flag, but we give them lower priority. */
728 14842 const int cpu_flags = av_get_cpu_flags();
729
730 /* Flags the transform wants */
731 14842 uint64_t req_flags = flags;
732
733 /* Flags the codelet may require to be present */
734 14842 uint64_t inv_req_mask = AV_TX_FULL_IMDCT |
735 AV_TX_REAL_TO_REAL |
736 AV_TX_REAL_TO_IMAGINARY |
737 FF_TX_PRESHUFFLE |
738 FF_TX_ASM_CALL;
739
740 /* Unaligned codelets are compatible with the aligned flag */
741
1/2
✓ Branch 0 taken 14842 times.
✗ Branch 1 not taken.
 14842 if (req_flags & FF_TX_ALIGNED)
742 14842 req_flags |= AV_TX_UNALIGNED;
743
744 /* If either flag is set, both are okay, so don't check for an exact match */
745
3/4
✓ Branch 0 taken 7620 times.
✓ Branch 1 taken 7222 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7620 times.
 14842 if ((req_flags & AV_TX_INPLACE) && (req_flags & FF_TX_OUT_OF_PLACE))
746 ✗ req_flags &= ~(AV_TX_INPLACE | FF_TX_OUT_OF_PLACE);
747
2/4
✓ Branch 0 taken 14842 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 14842 times.
✗ Branch 3 not taken.
 14842 if ((req_flags & FF_TX_ALIGNED) && (req_flags & AV_TX_UNALIGNED))
748 14842 req_flags &= ~(FF_TX_ALIGNED | AV_TX_UNALIGNED);
749
750 /* Loop through all codelets in all codelet lists to find matches
751 * to the requirements */
752
2/2
✓ Branch 0 taken 74210 times.
✓ Branch 1 taken 14842 times.
 89052 while (codelet_list_idx--) {
753 74210 const FFTXCodelet * const * list = codelet_list[codelet_list_idx];
754 74210 const FFTXCodelet *cd = NULL;
755
756
2/2
✓ Branch 0 taken 3205872 times.
✓ Branch 1 taken 74210 times.
 3280082 while ((cd = *list++)) {
757 /* Check if the type matches */
758
4/4
✓ Branch 0 taken 3191030 times.
✓ Branch 1 taken 14842 times.
✓ Branch 2 taken 2518379 times.
✓ Branch 3 taken 672651 times.
 3205872 if (cd->type != TX_TYPE_ANY && type != cd->type)
759 2518379 continue;
760
761 /* Check direction for non-orthogonal codelets */
762
4/4
✓ Branch 0 taken 86755 times.
✓ Branch 1 taken 600738 times.
✓ Branch 2 taken 9679 times.
✓ Branch 3 taken 77076 times.
 687493 if (((cd->flags & FF_TX_FORWARD_ONLY) && inv) ||
763
4/4
✓ Branch 0 taken 74501 times.
✓ Branch 1 taken 535916 times.
✓ Branch 2 taken 68233 times.
✓ Branch 3 taken 6268 times.
 610417 ((cd->flags & (FF_TX_INVERSE_ONLY | AV_TX_FULL_IMDCT)) && !inv) ||
764
3/4
✓ Branch 0 taken 9679 times.
✓ Branch 1 taken 594470 times.
✓ Branch 2 taken 9679 times.
✗ Branch 3 not taken.
 604149 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_REAL)) && inv) ||
765
3/4
✓ Branch 0 taken 9679 times.
✓ Branch 1 taken 594470 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9679 times.
 604149 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_IMAGINARY)) && inv))
766 83344 continue;
767
768 /* Check if the requested flags match from both sides */
769
2/2
✓ Branch 0 taken 371660 times.
✓ Branch 1 taken 232489 times.
 604149 if (((req_flags & cd->flags) != (req_flags)) ||
770
2/2
✓ Branch 0 taken 83919 times.
✓ Branch 1 taken 287741 times.
 371660 ((inv_req_mask & cd->flags) != (req_flags & inv_req_mask)))
771 316408 continue;
772
773 /* Check if length is supported */
774
6/6
✓ Branch 0 taken 195868 times.
✓ Branch 1 taken 91873 times.
✓ Branch 2 taken 134215 times.
✓ Branch 3 taken 61653 times.
✓ Branch 4 taken 110945 times.
✓ Branch 5 taken 23270 times.
 287741 if ((len < cd->min_len) || (cd->max_len != -1 && (len > cd->max_len)))
775 202818 continue;
776
777 /* Check if the CPU supports the required ISA */
778
2/2
✓ Branch 0 taken 26163 times.
✓ Branch 1 taken 58760 times.
 84923 if (cd->cpu_flags != FF_TX_CPU_FLAGS_ALL &&
779
2/2
✓ Branch 0 taken 18190 times.
✓ Branch 1 taken 7973 times.
 26163 !(cpu_flags & (cd->cpu_flags & ~cpu_slow_mask)))
780 18190 continue;
781
782 /* Check for factors */
783
2/2
✓ Branch 1 taken 28299 times.
✓ Branch 2 taken 38434 times.
 66733 if (!check_cd_factors(cd, len))
784 28299 continue;
785
786 /* Realloc array and append */
787 38434 cd_tmp = av_fast_realloc(cd_matches, &cd_matches_size,
788 38434 sizeof(*cd_tmp) * (nb_cd_matches + 1));
789
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 38434 times.
 38434 if (!cd_tmp) {
790 ✗ av_free(cd_matches);
791 ✗ return AVERROR(ENOMEM);
792 }
793
794 38434 cd_matches = cd_tmp;
795 38434 cd_matches[nb_cd_matches].cd = cd;
796 38434 cd_matches[nb_cd_matches].prio = get_codelet_prio(cd, cpu_flags, len);
797 38434 nb_cd_matches++;
798 }
799 }
800
801 #if !CONFIG_SMALL
802 /* Print debugging info */
803 14842 av_bprint_init(&bp, 0, AV_BPRINT_SIZE_AUTOMATIC);
804
2/2
✓ Branch 0 taken 13012 times.
✓ Branch 1 taken 1830 times.
 14842 av_bprintf(&bp, "For transform of length %i, %s, ", len,
805 inv ? "inverse" : "forward");
806 14842 print_type(&bp, type);
807 14842 av_bprintf(&bp, ", ");
808 14842 print_flags(&bp, flags);
809
2/2
✓ Branch 0 taken 14620 times.
✓ Branch 1 taken 222 times.
 14842 av_bprintf(&bp, ", found %i matches%s", nb_cd_matches,
810 nb_cd_matches ? ":" : ".");
811 #endif
812
813 /* No matches found */
814
2/2
✓ Branch 0 taken 222 times.
✓ Branch 1 taken 14620 times.
 14842 if (!nb_cd_matches)
815 222 return AVERROR(ENOSYS);
816
817 /* Sort the list */
818
44/44
✓ Branch 0 taken 6771 times.
✓ Branch 1 taken 10094 times.
✓ Branch 3 taken 1770 times.
✓ Branch 4 taken 5001 times.
✓ Branch 6 taken 460 times.
✓ Branch 7 taken 1310 times.
✓ Branch 9 taken 2254 times.
✓ Branch 10 taken 2747 times.
✓ Branch 12 taken 2568 times.
✓ Branch 13 taken 4203 times.
✓ Branch 14 taken 4063 times.
✓ Branch 15 taken 2708 times.
✓ Branch 16 taken 5056 times.
✓ Branch 17 taken 2032 times.
✓ Branch 19 taken 3609 times.
✓ Branch 20 taken 1447 times.
✓ Branch 21 taken 1495 times.
✓ Branch 22 taken 2614 times.
✓ Branch 24 taken 630 times.
✓ Branch 25 taken 865 times.
✓ Branch 26 taken 2614 times.
✓ Branch 27 taken 865 times.
✓ Branch 28 taken 3479 times.
✓ Branch 29 taken 2708 times.
✓ Branch 30 taken 1102 times.
✓ Branch 31 taken 1606 times.
✓ Branch 32 taken 375 times.
✓ Branch 33 taken 727 times.
✓ Branch 34 taken 316 times.
✓ Branch 35 taken 59 times.
✓ Branch 36 taken 2006 times.
✓ Branch 37 taken 178 times.
✓ Branch 39 taken 1141 times.
✓ Branch 40 taken 865 times.
✓ Branch 41 taken 178 times.
✓ Branch 42 taken 865 times.
✓ Branch 43 taken 1874 times.
✓ Branch 44 taken 656 times.
✓ Branch 46 taken 6315 times.
✓ Branch 47 taken 3779 times.
✓ Branch 48 taken 16865 times.
✓ Branch 49 taken 2815 times.
✓ Branch 50 taken 17150 times.
✓ Branch 51 taken 14620 times.
 45867 AV_QSORT(cd_matches, nb_cd_matches, TXCodeletMatch, cmp_matches);
819
820 #if !CONFIG_SMALL
821 14620 av_log(NULL, AV_LOG_TRACE, "%s\n", bp.str);
822
823
2/2
✓ Branch 0 taken 38434 times.
✓ Branch 1 taken 14620 times.
 53054 for (int i = 0; i < nb_cd_matches; i++) {
824 38434 av_log(NULL, AV_LOG_TRACE, " %i: ", i + 1);
825 38434 print_cd_info(cd_matches[i].cd, cd_matches[i].prio, 0, 1, AV_LOG_TRACE);
826 }
827 #endif
828
829
2/2
✓ Branch 0 taken 14523 times.
✓ Branch 1 taken 97 times.
 14620 if (!s->sub) {
830 14523 s->sub = sub = av_mallocz(TX_MAX_SUB*sizeof(*sub));
831
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 14523 times.
 14523 if (!sub) {
832 ✗ ret = AVERROR(ENOMEM);
833 ✗ goto end;
834 }
835 }
836
837 /* Attempt to initialize each */
838
1/2
✓ Branch 0 taken 19741 times.
✗ Branch 1 not taken.
 19741 for (int i = 0; i < nb_cd_matches; i++) {
839 19741 const FFTXCodelet *cd = cd_matches[i].cd;
840 19741 AVTXContext *sctx = &s->sub[s->nb_sub];
841
842 19741 sctx->len = len;
843 19741 sctx->inv = inv;
844 19741 sctx->type = type;
845 19741 sctx->flags = cd->flags | flags;
846 19741 sctx->cd_self = cd;
847
848 19741 s->fn[s->nb_sub] = cd->function;
849 19741 s->cd[s->nb_sub] = cd;
850
851 19741 ret = 0;
852
2/2
✓ Branch 0 taken 19722 times.
✓ Branch 1 taken 19 times.
 19741 if (cd->init)
853 19722 ret = cd->init(sctx, cd, flags, opts, len, inv, scale);
854
855
2/2
✓ Branch 0 taken 14620 times.
✓ Branch 1 taken 5121 times.
 19741 if (ret >= 0) {
856
3/4
✓ Branch 0 taken 7503 times.
✓ Branch 1 taken 7117 times.
✓ Branch 2 taken 7503 times.
✗ Branch 3 not taken.
 14620 if (opts && opts->map_dir != FF_TX_MAP_NONE &&
857
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 7481 times.
 7503 sctx->map_dir == FF_TX_MAP_NONE) {
858 /* If a specific map direction was requested, and it doesn't
859 * exist, create one.*/
860 22 sctx->map = av_malloc(len*sizeof(*sctx->map));
861
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22 times.
 22 if (!sctx->map) {
862 ✗ ret = AVERROR(ENOMEM);
863 ✗ goto end;
864 }
865
866
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 22 times.
 140 for (int i = 0; i < len; i++)
867 118 sctx->map[i] = i;
868
4/4
✓ Branch 0 taken 7481 times.
✓ Branch 1 taken 7117 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 7465 times.
 14598 } else if (opts && (opts->map_dir != sctx->map_dir)) {
869 16 int *tmp = av_malloc(len*sizeof(*sctx->map));
870
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (!tmp) {
871 ✗ ret = AVERROR(ENOMEM);
872 ✗ goto end;
873 }
874
875 16 memcpy(tmp, sctx->map, len*sizeof(*sctx->map));
876
877
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 16 times.
 128 for (int i = 0; i < len; i++)
878 112 sctx->map[tmp[i]] = i;
879
880 16 av_free(tmp);
881 }
882
883 14620 s->nb_sub++;
884 14620 goto end;
885 }
886
887 5121 s->fn[s->nb_sub] = NULL;
888 5121 s->cd[s->nb_sub] = NULL;
889
890 5121 reset_ctx(sctx, 0);
891
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5121 times.
 5121 if (ret == AVERROR(ENOMEM))
892 ✗ break;
893 }
894
895 ✗ if (!s->nb_sub)
896 ✗ av_freep(&s->sub);
897
898 ✗ end:
899 14620 av_free(cd_matches);
900 14620 return ret;
901 }
902
903 6930 av_cold int av_tx_init(AVTXContext **ctx, av_tx_fn *tx, enum AVTXType type,
904 int inv, int len, const void *scale, uint64_t flags)
905 {
906 int ret;
907 6930 AVTXContext tmp = { 0 };
908 6930 const double default_scale_d = 1.0;
909 6930 const float default_scale_f = 1.0f;
910
911
4/8
✓ Branch 0 taken 6930 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6930 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 6930 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 6930 times.
 6930 if (!len || type >= AV_TX_NB || !ctx || !tx)
912 ✗ return AVERROR(EINVAL);
913
914
1/2
✓ Branch 0 taken 6930 times.
✗ Branch 1 not taken.
 6930 if (!(flags & AV_TX_UNALIGNED))
915 6930 flags |= FF_TX_ALIGNED;
916
1/2
✓ Branch 0 taken 6930 times.
✗ Branch 1 not taken.
 6930 if (!(flags & AV_TX_INPLACE))
917 6930 flags |= FF_TX_OUT_OF_PLACE;
918
919
5/8
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6918 times.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 12 times.
✗ Branch 7 not taken.
 6930 if (!scale && ((type == AV_TX_DOUBLE_MDCT) || (type == AV_TX_DOUBLE_DCT) ||
920
2/4
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
 12 (type == AV_TX_DOUBLE_DCT_I) || (type == AV_TX_DOUBLE_DST_I) ||
921 (type == AV_TX_DOUBLE_RDFT)))
922 ✗ scale = &default_scale_d;
923
3/8
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6918 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 6930 else if (!scale && !TYPE_IS(FFT, type))
924 ✗ scale = &default_scale_f;
925
926 6930 ret = ff_tx_init_subtx(&tmp, type, flags, NULL, len, inv, scale);
927
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6930 times.
 6930 if (ret < 0)
928 ✗ return ret;
929
930 6930 *ctx = &tmp.sub[0];
931 6930 *tx = tmp.fn[0];
932
933 #if !CONFIG_SMALL
934 6930 av_log(NULL, AV_LOG_DEBUG, "Transform tree:\n");
935 6930 print_tx_structure(*ctx, 0);
936 #endif
937
938 6930 return ret;
939 }
940