FFmpeg coverage


Directory: ../../../ffmpeg/
File: src/libavutil/tx.c
Date: 2024-02-16 17:37:06
Exec Total Coverage
Lines: 431 495 87.1%
Functions: 24 25 96.0%
Branches: 458 600 76.3%

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 "qsort.h"
23 #include "bprint.h"
24
25 #include "tx_priv.h"
26
27 #define TYPE_IS(type, x) \
28 (((x) == AV_TX_FLOAT_ ## type) || \
29 ((x) == AV_TX_DOUBLE_ ## type) || \
30 ((x) == AV_TX_INT32_ ## type))
31
32 /* Calculates the modular multiplicative inverse */
33 2480 static av_always_inline int mulinv(int n, int m)
34 {
35 2480 n = n % m;
36
1/2
✓ Branch 0 taken 22303 times.
✗ Branch 1 not taken.
22303 for (int x = 1; x < m; x++)
37
2/2
✓ Branch 0 taken 2480 times.
✓ Branch 1 taken 19823 times.
22303 if (((n * x) % m) == 1)
38 2480 return x;
39 av_assert0(0); /* Never reached */
40 return 0;
41 }
42
43 75 int ff_tx_gen_pfa_input_map(AVTXContext *s, FFTXCodeletOptions *opts,
44 int d1, int d2)
45 {
46 75 const int sl = d1*d2;
47
48 75 s->map = av_malloc(s->len*sizeof(*s->map));
49
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 75 times.
75 if (!s->map)
50 return AVERROR(ENOMEM);
51
52
2/2
✓ Branch 0 taken 75 times.
✓ Branch 1 taken 75 times.
150 for (int k = 0; k < s->len; k += sl) {
53
3/6
✓ Branch 0 taken 75 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 75 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 75 times.
75 if (s->inv || (opts && opts->map_dir == FF_TX_MAP_SCATTER)) {
54 for (int m = 0; m < d2; m++)
55 for (int n = 0; n < d1; n++)
56 s->map[k + ((m*d1 + n*d2) % (sl))] = m*d1 + n;
57 } else {
58
2/2
✓ Branch 0 taken 375 times.
✓ Branch 1 taken 75 times.
450 for (int m = 0; m < d2; m++)
59
2/2
✓ Branch 0 taken 1125 times.
✓ Branch 1 taken 375 times.
1500 for (int n = 0; n < d1; n++)
60 1125 s->map[k + m*d1 + n] = (m*d1 + n*d2) % (sl);
61 }
62
63
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 75 times.
75 if (s->inv)
64 for (int w = 1; w <= ((sl) >> 1); w++)
65 FFSWAP(int, s->map[k + w], s->map[k + sl - w]);
66 }
67
68
1/2
✓ Branch 0 taken 75 times.
✗ Branch 1 not taken.
75 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
69
70 75 return 0;
71 }
72
73 /* Guaranteed to work for any n, m where gcd(n, m) == 1 */
74 1240 int ff_tx_gen_compound_mapping(AVTXContext *s, FFTXCodeletOptions *opts,
75 int inv, int n, int m)
76 {
77 int *in_map, *out_map;
78 1240 const int len = n*m; /* Will not be equal to s->len for MDCTs */
79 int m_inv, n_inv;
80
81 /* Make sure the numbers are coprime */
82
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1240 times.
1240 if (av_gcd(n, m) != 1)
83 return AVERROR(EINVAL);
84
85 1240 m_inv = mulinv(m, n);
86 1240 n_inv = mulinv(n, m);
87
88
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1240 times.
1240 if (!(s->map = av_malloc(2*len*sizeof(*s->map))))
89 return AVERROR(ENOMEM);
90
91 1240 in_map = s->map;
92 1240 out_map = s->map + len;
93
94 /* Ruritanian map for input, CRT map for output, can be swapped */
95
3/4
✓ Branch 0 taken 210 times.
✓ Branch 1 taken 1030 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 210 times.
1240 if (opts && opts->map_dir == FF_TX_MAP_SCATTER) {
96 for (int j = 0; j < m; j++) {
97 for (int i = 0; i < n; i++) {
98 in_map[(i*m + j*n) % len] = j*n + i;
99 out_map[(i*m*m_inv + j*n*n_inv) % len] = i*m + j;
100 }
101 }
102 } else {
103
2/2
✓ Branch 0 taken 25288 times.
✓ Branch 1 taken 1240 times.
26528 for (int j = 0; j < m; j++) {
104
2/2
✓ Branch 0 taken 378024 times.
✓ Branch 1 taken 25288 times.
403312 for (int i = 0; i < n; i++) {
105 378024 in_map[j*n + i] = (i*m + j*n) % len;
106 378024 out_map[(i*m*m_inv + j*n*n_inv) % len] = i*m + j;
107 }
108 }
109 }
110
111
2/2
✓ Branch 0 taken 1146 times.
✓ Branch 1 taken 94 times.
1240 if (inv) {
112
2/2
✓ Branch 0 taken 19976 times.
✓ Branch 1 taken 1146 times.
21122 for (int i = 0; i < m; i++) {
113 19976 int *in = &in_map[i*n + 1]; /* Skip the DC */
114
2/2
✓ Branch 0 taken 139512 times.
✓ Branch 1 taken 19976 times.
159488 for (int j = 0; j < ((n - 1) >> 1); j++)
115 139512 FFSWAP(int, in[j], in[n - j - 2]);
116 }
117 }
118
119
2/2
✓ Branch 0 taken 210 times.
✓ Branch 1 taken 1030 times.
1240 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
120
121 1240 return 0;
122 }
123
124 10174994 static inline int split_radix_permutation(int i, int len, int inv)
125 {
126 10174994 len >>= 1;
127
2/2
✓ Branch 0 taken 1285726 times.
✓ Branch 1 taken 8889268 times.
10174994 if (len <= 1)
128 1285726 return i & 1;
129
2/2
✓ Branch 0 taken 4444634 times.
✓ Branch 1 taken 4444634 times.
8889268 if (!(i & len))
130 4444634 return split_radix_permutation(i, len, inv) * 2;
131 4444634 len >>= 1;
132 4444634 return split_radix_permutation(i, len, inv) * 4 + 1 - 2*(!(i & len) ^ inv);
133 }
134
135 3562 int ff_tx_gen_ptwo_revtab(AVTXContext *s, FFTXCodeletOptions *opts)
136 {
137 3562 int len = s->len;
138
139
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3562 times.
3562 if (!(s->map = av_malloc(len*sizeof(*s->map))))
140 return AVERROR(ENOMEM);
141
142
3/4
✓ Branch 0 taken 3562 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1278 times.
✓ Branch 3 taken 2284 times.
3562 if (opts && opts->map_dir == FF_TX_MAP_SCATTER) {
143
2/2
✓ Branch 0 taken 157792 times.
✓ Branch 1 taken 1278 times.
159070 for (int i = 0; i < s->len; i++)
144 157792 s->map[-split_radix_permutation(i, len, s->inv) & (len - 1)] = i;
145 } else {
146
2/2
✓ Branch 0 taken 962442 times.
✓ Branch 1 taken 2284 times.
964726 for (int i = 0; i < s->len; i++)
147 962442 s->map[i] = -split_radix_permutation(i, len, s->inv) & (len - 1);
148 }
149
150
1/2
✓ Branch 0 taken 3562 times.
✗ Branch 1 not taken.
3562 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
151
152 3562 return 0;
153 }
154
155 int ff_tx_gen_inplace_map(AVTXContext *s, int len)
156 {
157 int *src_map, out_map_idx = 0;
158
159 if (!s->sub || !s->sub->map)
160 return AVERROR(EINVAL);
161
162 if (!(s->map = av_mallocz(len*sizeof(*s->map))))
163 return AVERROR(ENOMEM);
164
165 src_map = s->sub->map;
166
167 /* The first coefficient is always already in-place */
168 for (int src = 1; src < s->len; src++) {
169 int dst = src_map[src];
170 int found = 0;
171
172 if (dst <= src)
173 continue;
174
175 /* This just checks if a closed loop has been encountered before,
176 * and if so, skips it, since to fully permute a loop we must only
177 * enter it once. */
178 do {
179 for (int j = 0; j < out_map_idx; j++) {
180 if (dst == s->map[j]) {
181 found = 1;
182 break;
183 }
184 }
185 dst = src_map[dst];
186 } while (dst != src && !found);
187
188 if (!found)
189 s->map[out_map_idx++] = src;
190 }
191
192 s->map[out_map_idx++] = 0;
193
194 return 0;
195 }
196
197 41020 static void parity_revtab_generator(int *revtab, int n, int inv, int offset,
198 int is_dual, int dual_high, int len,
199 int basis, int dual_stride, int inv_lookup)
200 {
201 41020 len >>= 1;
202
203
2/2
✓ Branch 0 taken 27564 times.
✓ Branch 1 taken 13456 times.
41020 if (len <= basis) {
204 int k1, k2, stride, even_idx, odd_idx;
205
206
3/4
✓ Branch 0 taken 20594 times.
✓ Branch 1 taken 6970 times.
✓ Branch 2 taken 20594 times.
✗ Branch 3 not taken.
27564 is_dual = is_dual && dual_stride;
207 27564 dual_high = is_dual & dual_high;
208
2/2
✓ Branch 0 taken 20594 times.
✓ Branch 1 taken 6970 times.
27564 stride = is_dual ? FFMIN(dual_stride, len) : 0;
209
210 27564 even_idx = offset + dual_high*(stride - 2*len);
211
4/4
✓ Branch 0 taken 20594 times.
✓ Branch 1 taken 6970 times.
✓ Branch 2 taken 10297 times.
✓ Branch 3 taken 10297 times.
27564 odd_idx = even_idx + len + (is_dual && !dual_high)*len + dual_high*len;
212
213
2/2
✓ Branch 0 taken 82746 times.
✓ Branch 1 taken 27564 times.
110310 for (int i = 0; i < len; i++) {
214 82746 k1 = -split_radix_permutation(offset + i*2 + 0, n, inv) & (n - 1);
215 82746 k2 = -split_radix_permutation(offset + i*2 + 1, n, inv) & (n - 1);
216
2/2
✓ Branch 0 taken 69002 times.
✓ Branch 1 taken 13744 times.
82746 if (inv_lookup) {
217 69002 revtab[even_idx++] = k1;
218 69002 revtab[odd_idx++] = k2;
219 } else {
220 13744 revtab[k1] = even_idx++;
221 13744 revtab[k2] = odd_idx++;
222 }
223
4/4
✓ Branch 0 taken 55028 times.
✓ Branch 1 taken 27718 times.
✓ Branch 2 taken 27514 times.
✓ Branch 3 taken 27514 times.
82746 if (stride && !((i + 1) % stride)) {
224 27514 even_idx += stride;
225 27514 odd_idx += stride;
226 }
227 }
228
229 27564 return;
230 }
231
232 13456 parity_revtab_generator(revtab, n, inv, offset,
233 0, 0, len >> 0, basis, dual_stride, inv_lookup);
234 13456 parity_revtab_generator(revtab, n, inv, offset + (len >> 0),
235 1, 0, len >> 1, basis, dual_stride, inv_lookup);
236 13456 parity_revtab_generator(revtab, n, inv, offset + (len >> 0) + (len >> 1),
237 1, 1, len >> 1, basis, dual_stride, inv_lookup);
238 }
239
240 652 int ff_tx_gen_split_radix_parity_revtab(AVTXContext *s, int len, int inv,
241 FFTXCodeletOptions *opts,
242 int basis, int dual_stride)
243 {
244 652 basis >>= 1;
245
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 652 times.
652 if (len < basis)
246 return AVERROR(EINVAL);
247
248
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 652 times.
652 if (!(s->map = av_mallocz(len*sizeof(*s->map))))
249 return AVERROR(ENOMEM);
250
251
3/4
✓ Branch 0 taken 519 times.
✓ Branch 1 taken 133 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 519 times.
652 av_assert0(!dual_stride || !(dual_stride & (dual_stride - 1)));
252
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 652 times.
652 av_assert0(dual_stride <= basis);
253
254
2/2
✓ Branch 0 taken 629 times.
✓ Branch 1 taken 23 times.
1281 parity_revtab_generator(s->map, len, inv, 0, 0, 0, len,
255 basis, dual_stride,
256
2/2
✓ Branch 0 taken 340 times.
✓ Branch 1 taken 289 times.
629 opts ? opts->map_dir == FF_TX_MAP_GATHER : FF_TX_MAP_GATHER);
257
258
2/2
✓ Branch 0 taken 629 times.
✓ Branch 1 taken 23 times.
652 s->map_dir = opts ? opts->map_dir : FF_TX_MAP_GATHER;
259
260 652 return 0;
261 }
262
263 26087 static void reset_ctx(AVTXContext *s, int free_sub)
264 {
265
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 26087 times.
26087 if (!s)
266 return;
267
268
2/2
✓ Branch 0 taken 4576 times.
✓ Branch 1 taken 21511 times.
26087 if (s->sub)
269
2/2
✓ Branch 0 taken 18304 times.
✓ Branch 1 taken 4576 times.
22880 for (int i = 0; i < TX_MAX_SUB; i++)
270 18304 reset_ctx(&s->sub[i], free_sub + 1);
271
272
3/4
✓ Branch 0 taken 12450 times.
✓ Branch 1 taken 13637 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12450 times.
26087 if (s->cd_self && s->cd_self->uninit)
273 s->cd_self->uninit(s);
274
275
2/2
✓ Branch 0 taken 22564 times.
✓ Branch 1 taken 3523 times.
26087 if (free_sub)
276 22564 av_freep(&s->sub);
277
278 26087 av_freep(&s->map);
279 26087 av_freep(&s->exp);
280 26087 av_freep(&s->tmp);
281
282 /* Nothing else needs to be reset, it gets overwritten if another
283 * ff_tx_init_subtx() call is made. */
284 26087 s->nb_sub = 0;
285 26087 s->opaque = NULL;
286 26087 memset(s->fn, 0, sizeof(*s->fn));
287 }
288
289 91 void ff_tx_clear_ctx(AVTXContext *s)
290 {
291 91 reset_ctx(s, 0);
292 91 }
293
294 4843 av_cold void av_tx_uninit(AVTXContext **ctx)
295 {
296
2/2
✓ Branch 0 taken 583 times.
✓ Branch 1 taken 4260 times.
4843 if (!(*ctx))
297 583 return;
298
299 4260 reset_ctx(*ctx, 1);
300 4260 av_freep(ctx);
301 }
302
303 13 static av_cold int ff_tx_null_init(AVTXContext *s, const FFTXCodelet *cd,
304 uint64_t flags, FFTXCodeletOptions *opts,
305 int len, int inv, const void *scale)
306 {
307 /* Can only handle one sample+type to one sample+type transforms */
308
6/12
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 13 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 13 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 13 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 13 times.
13 if (TYPE_IS(MDCT, s->type) || TYPE_IS(RDFT, s->type))
309 return AVERROR(EINVAL);
310 13 return 0;
311 }
312
313 /* Null transform when the length is 1 */
314 2 static void ff_tx_null(AVTXContext *s, void *_out, void *_in, ptrdiff_t stride)
315 {
316 2 memcpy(_out, _in, stride);
317 2 }
318
319 static const FFTXCodelet ff_tx_null_def = {
320 .name = NULL_IF_CONFIG_SMALL("null"),
321 .function = ff_tx_null,
322 .type = TX_TYPE_ANY,
323 .flags = AV_TX_UNALIGNED | FF_TX_ALIGNED |
324 FF_TX_OUT_OF_PLACE | AV_TX_INPLACE,
325 .factors[0] = TX_FACTOR_ANY,
326 .min_len = 1,
327 .max_len = 1,
328 .init = ff_tx_null_init,
329 .cpu_flags = FF_TX_CPU_FLAGS_ALL,
330 .prio = FF_TX_PRIO_MAX,
331 };
332
333 static const FFTXCodelet * const ff_tx_null_list[] = {
334 &ff_tx_null_def,
335 NULL,
336 };
337
338 /* Array of all compiled codelet lists. Order is irrelevant. */
339 static const FFTXCodelet * const * const codelet_list[] = {
340 ff_tx_codelet_list_float_c,
341 ff_tx_codelet_list_double_c,
342 ff_tx_codelet_list_int32_c,
343 ff_tx_null_list,
344 #if HAVE_X86ASM
345 ff_tx_codelet_list_float_x86,
346 #endif
347 #if ARCH_AARCH64
348 ff_tx_codelet_list_float_aarch64,
349 #endif
350 };
351 static const int codelet_list_num = FF_ARRAY_ELEMS(codelet_list);
352
353 static const int cpu_slow_mask = AV_CPU_FLAG_SSE2SLOW | AV_CPU_FLAG_SSE3SLOW |
354 AV_CPU_FLAG_ATOM | AV_CPU_FLAG_SSSE3SLOW |
355 AV_CPU_FLAG_AVXSLOW | AV_CPU_FLAG_SLOW_GATHER;
356
357 static const int cpu_slow_penalties[][2] = {
358 { AV_CPU_FLAG_SSE2SLOW, 1 + 64 },
359 { AV_CPU_FLAG_SSE3SLOW, 1 + 64 },
360 { AV_CPU_FLAG_SSSE3SLOW, 1 + 64 },
361 { AV_CPU_FLAG_ATOM, 1 + 128 },
362 { AV_CPU_FLAG_AVXSLOW, 1 + 128 },
363 { AV_CPU_FLAG_SLOW_GATHER, 1 + 32 },
364 };
365
366 23370 static int get_codelet_prio(const FFTXCodelet *cd, int cpu_flags, int len)
367 {
368 23370 int prio = cd->prio;
369 23370 int max_factor = 0;
370
371 /* If the CPU has a SLOW flag, and the instruction is also flagged
372 * as being slow for such, reduce its priority */
373
2/2
✓ Branch 0 taken 140220 times.
✓ Branch 1 taken 23370 times.
163590 for (int i = 0; i < FF_ARRAY_ELEMS(cpu_slow_penalties); i++) {
374
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 140220 times.
140220 if ((cpu_flags & cd->cpu_flags) & cpu_slow_penalties[i][0])
375 prio -= cpu_slow_penalties[i][1];
376 }
377
378 /* Prioritize aligned-only codelets */
379
4/4
✓ Branch 0 taken 2284 times.
✓ Branch 1 taken 21086 times.
✓ Branch 2 taken 2271 times.
✓ Branch 3 taken 13 times.
23370 if ((cd->flags & FF_TX_ALIGNED) && !(cd->flags & AV_TX_UNALIGNED))
380 2271 prio += 64;
381
382 /* Codelets for specific lengths are generally faster */
383
4/4
✓ Branch 0 taken 5439 times.
✓ Branch 1 taken 17931 times.
✓ Branch 2 taken 4946 times.
✓ Branch 3 taken 493 times.
23370 if ((len == cd->min_len) && (len == cd->max_len))
384 4946 prio += 64;
385
386 /* Forward-only or inverse-only transforms are generally better */
387
2/2
✓ Branch 0 taken 12010 times.
✓ Branch 1 taken 11360 times.
23370 if ((cd->flags & (FF_TX_FORWARD_ONLY | FF_TX_INVERSE_ONLY)))
388 12010 prio += 64;
389
390 /* Larger factors are generally better */
391
2/2
✓ Branch 0 taken 93480 times.
✓ Branch 1 taken 23370 times.
116850 for (int i = 0; i < TX_MAX_SUB; i++)
392 93480 max_factor = FFMAX(cd->factors[i], max_factor);
393
2/2
✓ Branch 0 taken 21599 times.
✓ Branch 1 taken 1771 times.
23370 if (max_factor)
394 21599 prio += 16*max_factor;
395
396 23370 return prio;
397 }
398
399 typedef struct FFTXLenDecomp {
400 int len;
401 int len2;
402 int prio;
403 const FFTXCodelet *cd;
404 } FFTXLenDecomp;
405
406 440 static int cmp_decomp(FFTXLenDecomp *a, FFTXLenDecomp *b)
407 {
408 440 return FFDIFFSIGN(b->prio, a->prio);
409 }
410
411 3499 int ff_tx_decompose_length(int dst[TX_MAX_DECOMPOSITIONS], enum AVTXType type,
412 int len, int inv)
413 {
414 3499 int nb_decomp = 0;
415 FFTXLenDecomp ld[TX_MAX_DECOMPOSITIONS];
416 3499 int codelet_list_idx = codelet_list_num;
417
418 3499 const int cpu_flags = av_get_cpu_flags();
419
420 /* Loop through all codelets in all codelet lists to find matches
421 * to the requirements */
422
2/2
✓ Branch 0 taken 17495 times.
✓ Branch 1 taken 3499 times.
20994 while (codelet_list_idx--) {
423 17495 const FFTXCodelet * const * list = codelet_list[codelet_list_idx];
424 17495 const FFTXCodelet *cd = NULL;
425
426
2/2
✓ Branch 0 taken 797772 times.
✓ Branch 1 taken 17495 times.
815267 while ((cd = *list++)) {
427 797772 int fl = len;
428 797772 int skip = 0, prio;
429 797772 int factors_product = 1, factors_mod = 0;
430
431
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 797772 times.
797772 if (nb_decomp >= TX_MAX_DECOMPOSITIONS)
432 goto sort;
433
434 /* Check if the type matches */
435
4/4
✓ Branch 0 taken 794273 times.
✓ Branch 1 taken 3499 times.
✓ Branch 2 taken 543250 times.
✓ Branch 3 taken 251023 times.
797772 if (cd->type != TX_TYPE_ANY && type != cd->type)
436 543250 continue;
437
438 /* Check direction for non-orthogonal codelets */
439
4/4
✓ Branch 0 taken 17035 times.
✓ Branch 1 taken 237487 times.
✓ Branch 2 taken 3498 times.
✓ Branch 3 taken 13537 times.
254522 if (((cd->flags & FF_TX_FORWARD_ONLY) && inv) ||
440
4/4
✓ Branch 0 taken 6078 times.
✓ Branch 1 taken 234907 times.
✓ Branch 2 taken 5106 times.
✓ Branch 3 taken 972 times.
240985 ((cd->flags & (FF_TX_INVERSE_ONLY | AV_TX_FULL_IMDCT)) && !inv) ||
441
3/4
✓ Branch 0 taken 3498 times.
✓ Branch 1 taken 236515 times.
✓ Branch 2 taken 3498 times.
✗ Branch 3 not taken.
240013 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_REAL)) && inv) ||
442
3/4
✓ Branch 0 taken 3498 times.
✓ Branch 1 taken 236515 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3498 times.
240013 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_IMAGINARY)) && inv))
443 14509 continue;
444
445 /* Check if the CPU supports the required ISA */
446
2/2
✓ Branch 0 taken 118035 times.
✓ Branch 1 taken 121978 times.
240013 if (cd->cpu_flags != FF_TX_CPU_FLAGS_ALL &&
447
2/2
✓ Branch 0 taken 116822 times.
✓ Branch 1 taken 1213 times.
118035 !(cpu_flags & (cd->cpu_flags & ~cpu_slow_mask)))
448 116822 continue;
449
450
1/2
✓ Branch 0 taken 267376 times.
✗ Branch 1 not taken.
267376 for (int i = 0; i < TX_MAX_FACTORS; i++) {
451
4/4
✓ Branch 0 taken 151167 times.
✓ Branch 1 taken 116209 times.
✓ Branch 2 taken 144185 times.
✓ Branch 3 taken 6982 times.
267376 if (!cd->factors[i] || (fl == 1))
452 break;
453
454
2/2
✓ Branch 0 taken 21010 times.
✓ Branch 1 taken 123175 times.
144185 if (cd->factors[i] == TX_FACTOR_ANY) {
455 21010 factors_mod++;
456 21010 factors_product *= fl;
457
2/2
✓ Branch 0 taken 82109 times.
✓ Branch 1 taken 41066 times.
123175 } else if (!(fl % cd->factors[i])) {
458 82109 factors_mod++;
459
2/2
✓ Branch 0 taken 81322 times.
✓ Branch 1 taken 787 times.
82109 if (cd->factors[i] == 2) {
460 81322 int b = ff_ctz(fl);
461 81322 fl >>= b;
462 81322 factors_product <<= b;
463 } else {
464 do {
465 819 fl /= cd->factors[i];
466 819 factors_product *= cd->factors[i];
467
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 787 times.
819 } while (!(fl % cd->factors[i]));
468 }
469 }
470 }
471
472 /* Disqualify if factor requirements are not satisfied or if trivial */
473
4/4
✓ Branch 0 taken 95971 times.
✓ Branch 1 taken 27220 times.
✓ Branch 2 taken 93660 times.
✓ Branch 3 taken 2311 times.
123191 if ((factors_mod < cd->nb_factors) || (len == factors_product))
474 120880 continue;
475
476
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2311 times.
2311 if (av_gcd(factors_product, fl) != 1)
477 continue;
478
479 /* Check if length is supported and factorization was successful */
480
2/2
✓ Branch 0 taken 1109 times.
✓ Branch 1 taken 1202 times.
2311 if ((factors_product < cd->min_len) ||
481
3/4
✓ Branch 0 taken 1109 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 566 times.
✓ Branch 3 taken 543 times.
1109 (cd->max_len != TX_LEN_UNLIMITED && (factors_product > cd->max_len)))
482 1768 continue;
483
484 543 prio = get_codelet_prio(cd, cpu_flags, factors_product) * factors_product;
485
486 /* Check for duplicates */
487
2/2
✓ Branch 0 taken 910 times.
✓ Branch 1 taken 324 times.
1234 for (int i = 0; i < nb_decomp; i++) {
488
2/2
✓ Branch 0 taken 219 times.
✓ Branch 1 taken 691 times.
910 if (factors_product == ld[i].len) {
489 /* Update priority if new one is higher */
490
2/2
✓ Branch 0 taken 191 times.
✓ Branch 1 taken 28 times.
219 if (prio > ld[i].prio)
491 191 ld[i].prio = prio;
492 219 skip = 1;
493 219 break;
494 }
495 }
496
497 /* Add decomposition if unique */
498
2/2
✓ Branch 0 taken 324 times.
✓ Branch 1 taken 219 times.
543 if (!skip) {
499 324 ld[nb_decomp].cd = cd;
500 324 ld[nb_decomp].len = factors_product;
501 324 ld[nb_decomp].len2 = fl;
502 324 ld[nb_decomp].prio = prio;
503 324 nb_decomp++;
504 }
505 }
506 }
507
508
2/2
✓ Branch 0 taken 3408 times.
✓ Branch 1 taken 91 times.
3499 if (!nb_decomp)
509 3408 return AVERROR(EINVAL);
510
511 91 sort:
512
27/44
✓ Branch 0 taken 75 times.
✓ Branch 1 taken 83 times.
✓ Branch 3 taken 25 times.
✓ Branch 4 taken 50 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 25 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 50 times.
✓ Branch 12 taken 75 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 75 times.
✓ Branch 16 taken 75 times.
✓ Branch 17 taken 18 times.
✓ Branch 19 taken 18 times.
✓ Branch 20 taken 57 times.
✓ Branch 21 taken 57 times.
✓ Branch 22 taken 75 times.
✓ Branch 24 taken 57 times.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✓ Branch 27 taken 75 times.
✓ Branch 28 taken 75 times.
✓ Branch 29 taken 75 times.
✗ Branch 30 not taken.
✓ Branch 31 taken 75 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 18 times.
✓ Branch 44 taken 57 times.
✓ Branch 46 taken 8 times.
✓ Branch 47 taken 75 times.
✓ Branch 48 taken 158 times.
✓ Branch 49 taken 83 times.
✓ Branch 50 taken 166 times.
✓ Branch 51 taken 91 times.
557 AV_QSORT(ld, nb_decomp, FFTXLenDecomp, cmp_decomp);
513
514
2/2
✓ Branch 0 taken 324 times.
✓ Branch 1 taken 91 times.
415 for (int i = 0; i < nb_decomp; i++) {
515
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 324 times.
324 if (ld[i].cd->nb_factors > 1)
516 dst[i] = ld[i].len2;
517 else
518 324 dst[i] = ld[i].len;
519 }
520
521 91 return nb_decomp;
522 }
523
524 24 int ff_tx_gen_default_map(AVTXContext *s, FFTXCodeletOptions *opts)
525 {
526 24 s->map = av_malloc(s->len*sizeof(*s->map));
527
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
24 if (!s->map)
528 return AVERROR(ENOMEM);
529
530 24 s->map[0] = 0; /* DC is always at the start */
531
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
24 if (s->inv) /* Reversing the ACs flips the transform direction */
532 for (int i = 1; i < s->len; i++)
533 s->map[i] = s->len - i;
534 else
535
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 24 times.
168 for (int i = 1; i < s->len; i++)
536 144 s->map[i] = i;
537
538 24 s->map_dir = FF_TX_MAP_GATHER;
539
540 24 return 0;
541 }
542
543 #if !CONFIG_SMALL
544 40726 static void print_flags(AVBPrint *bp, uint64_t f)
545 {
546 40726 int prev = 0;
547 40726 const char *sep = ", ";
548 40726 av_bprintf(bp, "flags: [");
549
3/4
✓ Branch 0 taken 12640 times.
✓ Branch 1 taken 28086 times.
✓ Branch 2 taken 12640 times.
✗ Branch 3 not taken.
40726 if ((f & FF_TX_ALIGNED) && ++prev)
550 12640 av_bprintf(bp, "aligned");
551
3/4
✓ Branch 0 taken 28112 times.
✓ Branch 1 taken 12614 times.
✓ Branch 2 taken 28112 times.
✗ Branch 3 not taken.
40726 if ((f & AV_TX_UNALIGNED) && ++prev)
552
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 28086 times.
28112 av_bprintf(bp, "%sunaligned", prev > 1 ? sep : "");
553
3/4
✓ Branch 0 taken 19266 times.
✓ Branch 1 taken 21460 times.
✓ Branch 2 taken 19266 times.
✗ Branch 3 not taken.
40726 if ((f & AV_TX_INPLACE) && ++prev)
554
1/2
✓ Branch 0 taken 19266 times.
✗ Branch 1 not taken.
19266 av_bprintf(bp, "%sinplace", prev > 1 ? sep : "");
555
3/4
✓ Branch 0 taken 36259 times.
✓ Branch 1 taken 4467 times.
✓ Branch 2 taken 36259 times.
✗ Branch 3 not taken.
40726 if ((f & FF_TX_OUT_OF_PLACE) && ++prev)
556
1/2
✓ Branch 0 taken 36259 times.
✗ Branch 1 not taken.
36259 av_bprintf(bp, "%sout_of_place", prev > 1 ? sep : "");
557
3/4
✓ Branch 0 taken 1105 times.
✓ Branch 1 taken 39621 times.
✓ Branch 2 taken 1105 times.
✗ Branch 3 not taken.
40726 if ((f & FF_TX_FORWARD_ONLY) && ++prev)
558
1/2
✓ Branch 0 taken 1105 times.
✗ Branch 1 not taken.
1105 av_bprintf(bp, "%sfwd_only", prev > 1 ? sep : "");
559
3/4
✓ Branch 0 taken 14704 times.
✓ Branch 1 taken 26022 times.
✓ Branch 2 taken 14704 times.
✗ Branch 3 not taken.
40726 if ((f & FF_TX_INVERSE_ONLY) && ++prev)
560
1/2
✓ Branch 0 taken 14704 times.
✗ Branch 1 not taken.
14704 av_bprintf(bp, "%sinv_only", prev > 1 ? sep : "");
561
3/4
✓ Branch 0 taken 17825 times.
✓ Branch 1 taken 22901 times.
✓ Branch 2 taken 17825 times.
✗ Branch 3 not taken.
40726 if ((f & FF_TX_PRESHUFFLE) && ++prev)
562
1/2
✓ Branch 0 taken 17825 times.
✗ Branch 1 not taken.
17825 av_bprintf(bp, "%spreshuf", prev > 1 ? sep : "");
563
3/4
✓ Branch 0 taken 207 times.
✓ Branch 1 taken 40519 times.
✓ Branch 2 taken 207 times.
✗ Branch 3 not taken.
40726 if ((f & AV_TX_FULL_IMDCT) && ++prev)
564
1/2
✓ Branch 0 taken 207 times.
✗ Branch 1 not taken.
207 av_bprintf(bp, "%simdct_full", prev > 1 ? sep : "");
565
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 40702 times.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
40726 if ((f & AV_TX_REAL_TO_REAL) && ++prev)
566
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
24 av_bprintf(bp, "%sreal_to_real", prev > 1 ? sep : "");
567
3/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 40702 times.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
40726 if ((f & AV_TX_REAL_TO_IMAGINARY) && ++prev)
568
1/2
✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
24 av_bprintf(bp, "%sreal_to_imaginary", prev > 1 ? sep : "");
569
3/4
✓ Branch 0 taken 2906 times.
✓ Branch 1 taken 37820 times.
✓ Branch 2 taken 2906 times.
✗ Branch 3 not taken.
40726 if ((f & FF_TX_ASM_CALL) && ++prev)
570
1/2
✓ Branch 0 taken 2906 times.
✗ Branch 1 not taken.
2906 av_bprintf(bp, "%sasm_call", prev > 1 ? sep : "");
571 40726 av_bprintf(bp, "]");
572 40726 }
573
574 40726 static void print_type(AVBPrint *bp, enum AVTXType type)
575 {
576
2/2
✓ Branch 0 taken 40700 times.
✓ Branch 1 taken 26 times.
81426 av_bprintf(bp, "%s",
577 type == TX_TYPE_ANY ? "any" :
578
2/2
✓ Branch 0 taken 22777 times.
✓ Branch 1 taken 17923 times.
63477 type == AV_TX_FLOAT_FFT ? "fft_float" :
579
2/2
✓ Branch 0 taken 4201 times.
✓ Branch 1 taken 18576 times.
26978 type == AV_TX_FLOAT_MDCT ? "mdct_float" :
580
2/2
✓ Branch 0 taken 4030 times.
✓ Branch 1 taken 171 times.
8231 type == AV_TX_FLOAT_RDFT ? "rdft_float" :
581
2/2
✓ Branch 0 taken 4006 times.
✓ Branch 1 taken 24 times.
8036 type == AV_TX_FLOAT_DCT_I ? "dctI_float" :
582
2/2
✓ Branch 0 taken 3982 times.
✓ Branch 1 taken 24 times.
7988 type == AV_TX_FLOAT_DST_I ? "dstI_float" :
583
2/2
✓ Branch 0 taken 2188 times.
✓ Branch 1 taken 1794 times.
6170 type == AV_TX_DOUBLE_FFT ? "fft_double" :
584
1/2
✓ Branch 0 taken 2188 times.
✗ Branch 1 not taken.
4376 type == AV_TX_DOUBLE_MDCT ? "mdct_double" :
585
1/2
✓ Branch 0 taken 2188 times.
✗ Branch 1 not taken.
4376 type == AV_TX_DOUBLE_RDFT ? "rdft_double" :
586
1/2
✓ Branch 0 taken 2188 times.
✗ Branch 1 not taken.
4376 type == AV_TX_DOUBLE_DCT_I ? "dctI_double" :
587
1/2
✓ Branch 0 taken 2188 times.
✗ Branch 1 not taken.
4376 type == AV_TX_DOUBLE_DST_I ? "dstI_double" :
588
2/2
✓ Branch 0 taken 1215 times.
✓ Branch 1 taken 973 times.
3403 type == AV_TX_INT32_FFT ? "fft_int32" :
589
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 1203 times.
1227 type == AV_TX_INT32_MDCT ? "mdct_int32" :
590
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
24 type == AV_TX_INT32_RDFT ? "rdft_int32" :
591
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
24 type == AV_TX_INT32_DCT_I ? "dctI_int32" :
592
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
12 type == AV_TX_INT32_DST_I ? "dstI_int32" :
593 "unknown");
594 40726 }
595
596 31754 static void print_cd_info(const FFTXCodelet *cd, int prio, int len, int print_prio)
597 {
598 AVBPrint bp;
599 31754 av_bprint_init(&bp, 0, AV_BPRINT_SIZE_AUTOMATIC);
600
601 31754 av_bprintf(&bp, "%s - type: ", cd->name);
602
603 31754 print_type(&bp, cd->type);
604
605 31754 av_bprintf(&bp, ", len: ");
606
2/2
✓ Branch 0 taken 22827 times.
✓ Branch 1 taken 8927 times.
31754 if (!len) {
607
2/2
✓ Branch 0 taken 18406 times.
✓ Branch 1 taken 4421 times.
22827 if (cd->min_len != cd->max_len)
608 18406 av_bprintf(&bp, "[%i, ", cd->min_len);
609
610
2/2
✓ Branch 0 taken 16903 times.
✓ Branch 1 taken 5924 times.
22827 if (cd->max_len == TX_LEN_UNLIMITED)
611 16903 av_bprintf(&bp, "∞");
612 else
613 5924 av_bprintf(&bp, "%i", cd->max_len);
614 } else {
615 8927 av_bprintf(&bp, "%i", len);
616 }
617
618
2/2
✓ Branch 0 taken 20161 times.
✓ Branch 1 taken 11593 times.
31754 if (cd->factors[1]) {
619
3/4
✓ Branch 0 taken 15808 times.
✓ Branch 1 taken 4353 times.
✓ Branch 2 taken 15808 times.
✗ Branch 3 not taken.
20161 av_bprintf(&bp, "%s, factors", !len && cd->min_len != cd->max_len ? "]" : "");
620
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 20153 times.
20161 if (!cd->nb_factors)
621 8 av_bprintf(&bp, ": [");
622 else
623 20153 av_bprintf(&bp, "[%i]: [", cd->nb_factors);
624
625
1/2
✓ Branch 0 taken 71805 times.
✗ Branch 1 not taken.
71805 for (int i = 0; i < TX_MAX_FACTORS; i++) {
626
4/4
✓ Branch 0 taken 51644 times.
✓ Branch 1 taken 20161 times.
✓ Branch 2 taken 31483 times.
✓ Branch 3 taken 20161 times.
71805 if (i && cd->factors[i])
627 31483 av_bprintf(&bp, ", ");
628
2/2
✓ Branch 0 taken 19735 times.
✓ Branch 1 taken 52070 times.
71805 if (cd->factors[i] == TX_FACTOR_ANY)
629 19735 av_bprintf(&bp, "any");
630
2/2
✓ Branch 0 taken 31909 times.
✓ Branch 1 taken 20161 times.
52070 else if (cd->factors[i])
631 31909 av_bprintf(&bp, "%i", cd->factors[i]);
632 else
633 20161 break;
634 }
635
636 20161 av_bprintf(&bp, "], ");
637 } else {
638 11593 av_bprintf(&bp, "%s, factor: %i, ",
639
4/4
✓ Branch 0 taken 7019 times.
✓ Branch 1 taken 4574 times.
✓ Branch 2 taken 2598 times.
✓ Branch 3 taken 4421 times.
11593 !len && cd->min_len != cd->max_len ? "]" : "", cd->factors[0]);
640 }
641 31754 print_flags(&bp, cd->flags);
642
643
2/2
✓ Branch 0 taken 22827 times.
✓ Branch 1 taken 8927 times.
31754 if (print_prio)
644 22827 av_bprintf(&bp, ", prio: %i", prio);
645
646 31754 av_log(NULL, AV_LOG_DEBUG, "%s\n", bp.str);
647 31754 }
648
649 8927 static void print_tx_structure(AVTXContext *s, int depth)
650 {
651 8927 const FFTXCodelet *cd = s->cd_self;
652
653
2/2
✓ Branch 0 taken 14002 times.
✓ Branch 1 taken 8927 times.
22929 for (int i = 0; i <= depth; i++)
654 14002 av_log(NULL, AV_LOG_DEBUG, " ");
655
656 8927 print_cd_info(cd, cd->prio, s->len, 0);
657
658
2/2
✓ Branch 0 taken 4667 times.
✓ Branch 1 taken 8927 times.
13594 for (int i = 0; i < s->nb_sub; i++)
659 4667 print_tx_structure(&s->sub[i], depth + 1);
660 8927 }
661 #endif /* CONFIG_SMALL */
662
663 typedef struct TXCodeletMatch {
664 const FFTXCodelet *cd;
665 int prio;
666 } TXCodeletMatch;
667
668 22317 static int cmp_matches(TXCodeletMatch *a, TXCodeletMatch *b)
669 {
670 22317 return FFDIFFSIGN(b->prio, a->prio);
671 }
672
673 /* We want all factors to completely cover the length */
674 39458 static inline int check_cd_factors(const FFTXCodelet *cd, int len)
675 {
676 39458 int matches = 0, any_flag = 0;
677
678
1/2
✓ Branch 0 taken 121902 times.
✗ Branch 1 not taken.
121902 for (int i = 0; i < TX_MAX_FACTORS; i++) {
679 121902 int factor = cd->factors[i];
680
681
2/2
✓ Branch 0 taken 33170 times.
✓ Branch 1 taken 88732 times.
121902 if (factor == TX_FACTOR_ANY) {
682 33170 any_flag = 1;
683 33170 matches++;
684 33170 continue;
685
4/4
✓ Branch 0 taken 73365 times.
✓ Branch 1 taken 15367 times.
✓ Branch 2 taken 49274 times.
✓ Branch 3 taken 24091 times.
88732 } else if (len <= 1 || !factor) {
686 break;
687
2/2
✓ Branch 0 taken 18167 times.
✓ Branch 1 taken 31107 times.
49274 } else if (factor == 2) { /* Fast path */
688 18167 int bits_2 = ff_ctz(len);
689
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 18119 times.
18167 if (!bits_2)
690 48 continue; /* Factor not supported */
691
692 18119 len >>= bits_2;
693 18119 matches++;
694 } else {
695 31107 int res = len % factor;
696
2/2
✓ Branch 0 taken 26974 times.
✓ Branch 1 taken 4133 times.
31107 if (res)
697 26974 continue; /* Factor not supported */
698
699
2/2
✓ Branch 0 taken 4297 times.
✓ Branch 1 taken 4133 times.
8430 while (!res) {
700 4297 len /= factor;
701 4297 res = len % factor;
702 }
703 4133 matches++;
704 }
705 }
706
707
6/6
✓ Branch 0 taken 23283 times.
✓ Branch 1 taken 16175 times.
✓ Branch 2 taken 6000 times.
✓ Branch 3 taken 17283 times.
✓ Branch 4 taken 5544 times.
✓ Branch 5 taken 456 times.
39458 return (cd->nb_factors <= matches) && (any_flag || len == 1);
708 }
709
710 8972 av_cold int ff_tx_init_subtx(AVTXContext *s, enum AVTXType type,
711 uint64_t flags, FFTXCodeletOptions *opts,
712 int len, int inv, const void *scale)
713 {
714 8972 int ret = 0;
715 8972 AVTXContext *sub = NULL;
716 8972 TXCodeletMatch *cd_tmp, *cd_matches = NULL;
717 8972 unsigned int cd_matches_size = 0;
718 8972 int codelet_list_idx = codelet_list_num;
719 8972 int nb_cd_matches = 0;
720 #if !CONFIG_SMALL
721 AVBPrint bp;
722 #endif
723
724 /* We still accept functions marked with SLOW, even if the CPU is
725 * marked with the same flag, but we give them lower priority. */
726 8972 const int cpu_flags = av_get_cpu_flags();
727
728 /* Flags the transform wants */
729 8972 uint64_t req_flags = flags;
730
731 /* Flags the codelet may require to be present */
732 8972 uint64_t inv_req_mask = AV_TX_FULL_IMDCT |
733 AV_TX_REAL_TO_REAL |
734 AV_TX_REAL_TO_IMAGINARY |
735 FF_TX_PRESHUFFLE |
736 FF_TX_ASM_CALL;
737
738 /* Unaligned codelets are compatible with the aligned flag */
739
1/2
✓ Branch 0 taken 8972 times.
✗ Branch 1 not taken.
8972 if (req_flags & FF_TX_ALIGNED)
740 8972 req_flags |= AV_TX_UNALIGNED;
741
742 /* If either flag is set, both are okay, so don't check for an exact match */
743
3/4
✓ Branch 0 taken 4467 times.
✓ Branch 1 taken 4505 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4467 times.
8972 if ((req_flags & AV_TX_INPLACE) && (req_flags & FF_TX_OUT_OF_PLACE))
744 req_flags &= ~(AV_TX_INPLACE | FF_TX_OUT_OF_PLACE);
745
2/4
✓ Branch 0 taken 8972 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8972 times.
✗ Branch 3 not taken.
8972 if ((req_flags & FF_TX_ALIGNED) && (req_flags & AV_TX_UNALIGNED))
746 8972 req_flags &= ~(FF_TX_ALIGNED | AV_TX_UNALIGNED);
747
748 /* Loop through all codelets in all codelet lists to find matches
749 * to the requirements */
750
2/2
✓ Branch 0 taken 44860 times.
✓ Branch 1 taken 8972 times.
53832 while (codelet_list_idx--) {
751 44860 const FFTXCodelet * const * list = codelet_list[codelet_list_idx];
752 44860 const FFTXCodelet *cd = NULL;
753
754
2/2
✓ Branch 0 taken 2045616 times.
✓ Branch 1 taken 44860 times.
2090476 while ((cd = *list++)) {
755 /* Check if the type matches */
756
4/4
✓ Branch 0 taken 2036644 times.
✓ Branch 1 taken 8972 times.
✓ Branch 2 taken 1616864 times.
✓ Branch 3 taken 419780 times.
2045616 if (cd->type != TX_TYPE_ANY && type != cd->type)
757 1616864 continue;
758
759 /* Check direction for non-orthogonal codelets */
760
4/4
✓ Branch 0 taken 52134 times.
✓ Branch 1 taken 376618 times.
✓ Branch 2 taken 7548 times.
✓ Branch 3 taken 44586 times.
428752 if (((cd->flags & FF_TX_FORWARD_ONLY) && inv) ||
761
4/4
✓ Branch 0 taken 44258 times.
✓ Branch 1 taken 339908 times.
✓ Branch 2 taken 39747 times.
✓ Branch 3 taken 4511 times.
384166 ((cd->flags & (FF_TX_INVERSE_ONLY | AV_TX_FULL_IMDCT)) && !inv) ||
762
3/4
✓ Branch 0 taken 7548 times.
✓ Branch 1 taken 372107 times.
✓ Branch 2 taken 7548 times.
✗ Branch 3 not taken.
379655 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_REAL)) && inv) ||
763
3/4
✓ Branch 0 taken 7548 times.
✓ Branch 1 taken 372107 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 7548 times.
379655 ((cd->flags & (FF_TX_FORWARD_ONLY | AV_TX_REAL_TO_IMAGINARY)) && inv))
764 49097 continue;
765
766 /* Check if the requested flags match from both sides */
767
2/2
✓ Branch 0 taken 257483 times.
✓ Branch 1 taken 122172 times.
379655 if (((req_flags & cd->flags) != (req_flags)) ||
768
2/2
✓ Branch 0 taken 60240 times.
✓ Branch 1 taken 197243 times.
257483 ((inv_req_mask & cd->flags) != (req_flags & inv_req_mask)))
769 182412 continue;
770
771 /* Check if length is supported */
772
6/6
✓ Branch 0 taken 122141 times.
✓ Branch 1 taken 75102 times.
✓ Branch 2 taken 84687 times.
✓ Branch 3 taken 37454 times.
✓ Branch 4 taken 70302 times.
✓ Branch 5 taken 14385 times.
197243 if ((len < cd->min_len) || (cd->max_len != -1 && (len > cd->max_len)))
773 145404 continue;
774
775 /* Check if the CPU supports the required ISA */
776
2/2
✓ Branch 0 taken 15335 times.
✓ Branch 1 taken 36504 times.
51839 if (cd->cpu_flags != FF_TX_CPU_FLAGS_ALL &&
777
2/2
✓ Branch 0 taken 12381 times.
✓ Branch 1 taken 2954 times.
15335 !(cpu_flags & (cd->cpu_flags & ~cpu_slow_mask)))
778 12381 continue;
779
780 /* Check for factors */
781
2/2
✓ Branch 1 taken 16631 times.
✓ Branch 2 taken 22827 times.
39458 if (!check_cd_factors(cd, len))
782 16631 continue;
783
784 /* Realloc array and append */
785 22827 cd_tmp = av_fast_realloc(cd_matches, &cd_matches_size,
786 22827 sizeof(*cd_tmp) * (nb_cd_matches + 1));
787
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 22827 times.
22827 if (!cd_tmp) {
788 av_free(cd_matches);
789 return AVERROR(ENOMEM);
790 }
791
792 22827 cd_matches = cd_tmp;
793 22827 cd_matches[nb_cd_matches].cd = cd;
794 22827 cd_matches[nb_cd_matches].prio = get_codelet_prio(cd, cpu_flags, len);
795 22827 nb_cd_matches++;
796 }
797 }
798
799 #if !CONFIG_SMALL
800 /* Print debugging info */
801 8972 av_bprint_init(&bp, 0, AV_BPRINT_SIZE_AUTOMATIC);
802
2/2
✓ Branch 0 taken 7512 times.
✓ Branch 1 taken 1460 times.
8972 av_bprintf(&bp, "For transform of length %i, %s, ", len,
803 inv ? "inverse" : "forward");
804 8972 print_type(&bp, type);
805 8972 av_bprintf(&bp, ", ");
806 8972 print_flags(&bp, flags);
807
2/2
✓ Branch 0 taken 8927 times.
✓ Branch 1 taken 45 times.
8972 av_bprintf(&bp, ", found %i matches%s", nb_cd_matches,
808 nb_cd_matches ? ":" : ".");
809 #endif
810
811 /* No matches found */
812
2/2
✓ Branch 0 taken 45 times.
✓ Branch 1 taken 8927 times.
8972 if (!nb_cd_matches)
813 45 return AVERROR(ENOSYS);
814
815 /* Sort the list */
816
44/44
✓ Branch 0 taken 3604 times.
✓ Branch 1 taken 6690 times.
✓ Branch 3 taken 1201 times.
✓ Branch 4 taken 2403 times.
✓ Branch 6 taken 43 times.
✓ Branch 7 taken 1158 times.
✓ Branch 9 taken 1011 times.
✓ Branch 10 taken 1392 times.
✓ Branch 12 taken 1448 times.
✓ Branch 13 taken 2156 times.
✓ Branch 14 taken 2020 times.
✓ Branch 15 taken 1584 times.
✓ Branch 16 taken 3085 times.
✓ Branch 17 taken 1171 times.
✓ Branch 19 taken 2224 times.
✓ Branch 20 taken 861 times.
✓ Branch 21 taken 907 times.
✓ Branch 22 taken 1504 times.
✓ Branch 24 taken 379 times.
✓ Branch 25 taken 528 times.
✓ Branch 26 taken 1504 times.
✓ Branch 27 taken 528 times.
✓ Branch 28 taken 2032 times.
✓ Branch 29 taken 1584 times.
✓ Branch 30 taken 587 times.
✓ Branch 31 taken 997 times.
✓ Branch 32 taken 347 times.
✓ Branch 33 taken 240 times.
✓ Branch 34 taken 290 times.
✓ Branch 35 taken 57 times.
✓ Branch 36 taken 823 times.
✓ Branch 37 taken 2 times.
✓ Branch 39 taken 295 times.
✓ Branch 40 taken 528 times.
✓ Branch 41 taken 2 times.
✓ Branch 42 taken 528 times.
✓ Branch 43 taken 1187 times.
✓ Branch 44 taken 395 times.
✓ Branch 46 taken 3829 times.
✓ Branch 47 taken 2861 times.
✓ Branch 48 taken 10294 times.
✓ Branch 49 taken 1797 times.
✓ Branch 50 taken 10509 times.
✓ Branch 51 taken 8927 times.
27532 AV_QSORT(cd_matches, nb_cd_matches, TXCodeletMatch, cmp_matches);
817
818 #if !CONFIG_SMALL
819 8927 av_log(NULL, AV_LOG_DEBUG, "%s\n", bp.str);
820
821
2/2
✓ Branch 0 taken 22827 times.
✓ Branch 1 taken 8927 times.
31754 for (int i = 0; i < nb_cd_matches; i++) {
822 22827 av_log(NULL, AV_LOG_DEBUG, " %i: ", i + 1);
823 22827 print_cd_info(cd_matches[i].cd, cd_matches[i].prio, 0, 1);
824 }
825 #endif
826
827
2/2
✓ Branch 0 taken 8836 times.
✓ Branch 1 taken 91 times.
8927 if (!s->sub) {
828 8836 s->sub = sub = av_mallocz(TX_MAX_SUB*sizeof(*sub));
829
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8836 times.
8836 if (!sub) {
830 ret = AVERROR(ENOMEM);
831 goto end;
832 }
833 }
834
835 /* Attempt to initialize each */
836
1/2
✓ Branch 0 taken 12359 times.
✗ Branch 1 not taken.
12359 for (int i = 0; i < nb_cd_matches; i++) {
837 12359 const FFTXCodelet *cd = cd_matches[i].cd;
838 12359 AVTXContext *sctx = &s->sub[s->nb_sub];
839
840 12359 sctx->len = len;
841 12359 sctx->inv = inv;
842 12359 sctx->type = type;
843 12359 sctx->flags = cd->flags | flags;
844 12359 sctx->cd_self = cd;
845
846 12359 s->fn[s->nb_sub] = cd->function;
847 12359 s->cd[s->nb_sub] = cd;
848
849 12359 ret = 0;
850
2/2
✓ Branch 0 taken 12342 times.
✓ Branch 1 taken 17 times.
12359 if (cd->init)
851 12342 ret = cd->init(sctx, cd, flags, opts, len, inv, scale);
852
853
2/2
✓ Branch 0 taken 8927 times.
✓ Branch 1 taken 3432 times.
12359 if (ret >= 0) {
854
3/4
✓ Branch 0 taken 4521 times.
✓ Branch 1 taken 4406 times.
✓ Branch 2 taken 4521 times.
✗ Branch 3 not taken.
8927 if (opts && opts->map_dir != FF_TX_MAP_NONE &&
855
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 4500 times.
4521 sctx->map_dir == FF_TX_MAP_NONE) {
856 /* If a specific map direction was requested, and it doesn't
857 * exist, create one.*/
858 21 sctx->map = av_malloc(len*sizeof(*sctx->map));
859
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 21 times.
21 if (!sctx->map) {
860 ret = AVERROR(ENOMEM);
861 goto end;
862 }
863
864
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 21 times.
138 for (int i = 0; i < len; i++)
865 117 sctx->map[i] = i;
866
4/4
✓ Branch 0 taken 4500 times.
✓ Branch 1 taken 4406 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 4484 times.
8906 } else if (opts && (opts->map_dir != sctx->map_dir)) {
867 16 int *tmp = av_malloc(len*sizeof(*sctx->map));
868
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
16 if (!tmp) {
869 ret = AVERROR(ENOMEM);
870 goto end;
871 }
872
873 16 memcpy(tmp, sctx->map, len*sizeof(*sctx->map));
874
875
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 16 times.
128 for (int i = 0; i < len; i++)
876 112 sctx->map[tmp[i]] = i;
877
878 16 av_free(tmp);
879 }
880
881 8927 s->nb_sub++;
882 8927 goto end;
883 }
884
885 3432 s->fn[s->nb_sub] = NULL;
886 3432 s->cd[s->nb_sub] = NULL;
887
888 3432 reset_ctx(sctx, 0);
889
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3432 times.
3432 if (ret == AVERROR(ENOMEM))
890 break;
891 }
892
893 if (!s->nb_sub)
894 av_freep(&s->sub);
895
896 end:
897 8927 av_free(cd_matches);
898 8927 return ret;
899 }
900
901 4260 av_cold int av_tx_init(AVTXContext **ctx, av_tx_fn *tx, enum AVTXType type,
902 int inv, int len, const void *scale, uint64_t flags)
903 {
904 int ret;
905 4260 AVTXContext tmp = { 0 };
906 4260 const double default_scale_d = 1.0;
907 4260 const float default_scale_f = 1.0f;
908
909
4/8
✓ Branch 0 taken 4260 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4260 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4260 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 4260 times.
4260 if (!len || type >= AV_TX_NB || !ctx || !tx)
910 return AVERROR(EINVAL);
911
912
1/2
✓ Branch 0 taken 4260 times.
✗ Branch 1 not taken.
4260 if (!(flags & AV_TX_UNALIGNED))
913 4260 flags |= FF_TX_ALIGNED;
914
1/2
✓ Branch 0 taken 4260 times.
✗ Branch 1 not taken.
4260 if (!(flags & AV_TX_INPLACE))
915 4260 flags |= FF_TX_OUT_OF_PLACE;
916
917
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4248 times.
4260 if (!scale && ((type == AV_TX_FLOAT_MDCT) || (type == AV_TX_INT32_MDCT) || (type == AV_TX_FLOAT_RDFT) || (AV_TX_INT32_RDFT)))
918 12 scale = &default_scale_f;
919
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 4248 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
4248 else if (!scale && ((type == AV_TX_DOUBLE_MDCT) || (type == AV_TX_DOUBLE_RDFT)))
920 scale = &default_scale_d;
921
922 4260 ret = ff_tx_init_subtx(&tmp, type, flags, NULL, len, inv, scale);
923
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4260 times.
4260 if (ret < 0)
924 return ret;
925
926 4260 *ctx = &tmp.sub[0];
927 4260 *tx = tmp.fn[0];
928
929 #if !CONFIG_SMALL
930 4260 av_log(NULL, AV_LOG_DEBUG, "Transform tree:\n");
931 4260 print_tx_structure(*ctx, 0);
932 #endif
933
934 4260 return ret;
935 }
936