FFmpeg
tx.c
Go to the documentation of this file.
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 
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 */
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  return 0;
42 }
43 
44 /* Guaranteed to work for any n, m where gcd(n, m) == 1 */
46 {
47  int *in_map, *out_map;
48  const int n = s->n;
49  const int m = s->m;
50  const int inv = s->inv;
51  const int len = n*m;
52  const int m_inv = mulinv(m, n);
53  const int n_inv = mulinv(n, m);
54  const int mdct = ff_tx_type_is_mdct(s->type);
55 
56  if (!(s->pfatab = av_malloc(2*len*sizeof(*s->pfatab))))
57  return AVERROR(ENOMEM);
58 
59  in_map = s->pfatab;
60  out_map = s->pfatab + n*m;
61 
62  /* Ruritanian map for input, CRT map for output, can be swapped */
63  for (int j = 0; j < m; j++) {
64  for (int i = 0; i < n; i++) {
65  /* Shifted by 1 to simplify MDCTs */
66  in_map[j*n + i] = ((i*m + j*n) % len) << mdct;
67  out_map[(i*m*m_inv + j*n*n_inv) % len] = i*m + j;
68  }
69  }
70 
71  /* Change transform direction by reversing all ACs */
72  if (inv) {
73  for (int i = 0; i < m; i++) {
74  int *in = &in_map[i*n + 1]; /* Skip the DC */
75  for (int j = 0; j < ((n - 1) >> 1); j++)
76  FFSWAP(int, in[j], in[n - j - 2]);
77  }
78  }
79 
80  /* Our 15-point transform is also a compound one, so embed its input map */
81  if (n == 15) {
82  for (int k = 0; k < m; k++) {
83  int tmp[15];
84  memcpy(tmp, &in_map[k*15], 15*sizeof(*tmp));
85  for (int i = 0; i < 5; i++) {
86  for (int j = 0; j < 3; j++)
87  in_map[k*15 + i*3 + j] = tmp[(i*3 + j*5) % 15];
88  }
89  }
90  }
91 
92  return 0;
93 }
94 
95 static inline int split_radix_permutation(int i, int m, int inverse)
96 {
97  m >>= 1;
98  if (m <= 1)
99  return i & 1;
100  if (!(i & m))
101  return split_radix_permutation(i, m, inverse) * 2;
102  m >>= 1;
103  return split_radix_permutation(i, m, inverse) * 4 + 1 - 2*(!(i & m) ^ inverse);
104 }
105 
106 int ff_tx_gen_ptwo_revtab(AVTXContext *s, int invert_lookup)
107 {
108  const int m = s->m, inv = s->inv;
109 
110  if (!(s->revtab = av_malloc(s->m*sizeof(*s->revtab))))
111  return AVERROR(ENOMEM);
112  if (!(s->revtab_c = av_malloc(m*sizeof(*s->revtab_c))))
113  return AVERROR(ENOMEM);
114 
115  /* Default */
116  for (int i = 0; i < m; i++) {
117  int k = -split_radix_permutation(i, m, inv) & (m - 1);
118  if (invert_lookup)
119  s->revtab[i] = s->revtab_c[i] = k;
120  else
121  s->revtab[i] = s->revtab_c[k] = i;
122  }
123 
124  return 0;
125 }
126 
128 {
129  int nb_inplace_idx = 0;
130 
131  if (!(s->inplace_idx = av_malloc(s->m*sizeof(*s->inplace_idx))))
132  return AVERROR(ENOMEM);
133 
134  /* The first coefficient is always already in-place */
135  for (int src = 1; src < s->m; src++) {
136  int dst = revtab[src];
137  int found = 0;
138 
139  if (dst <= src)
140  continue;
141 
142  /* This just checks if a closed loop has been encountered before,
143  * and if so, skips it, since to fully permute a loop we must only
144  * enter it once. */
145  do {
146  for (int j = 0; j < nb_inplace_idx; j++) {
147  if (dst == s->inplace_idx[j]) {
148  found = 1;
149  break;
150  }
151  }
152  dst = revtab[dst];
153  } while (dst != src && !found);
154 
155  if (!found)
156  s->inplace_idx[nb_inplace_idx++] = src;
157  }
158 
159  s->inplace_idx[nb_inplace_idx++] = 0;
160 
161  return 0;
162 }
163 
164 static void parity_revtab_generator(int *revtab, int n, int inv, int offset,
165  int is_dual, int dual_high, int len,
166  int basis, int dual_stride)
167 {
168  len >>= 1;
169 
170  if (len <= basis) {
171  int k1, k2, *even, *odd, stride;
172 
173  is_dual = is_dual && dual_stride;
174  dual_high = is_dual & dual_high;
175  stride = is_dual ? FFMIN(dual_stride, len) : 0;
176 
177  even = &revtab[offset + dual_high*(stride - 2*len)];
178  odd = &even[len + (is_dual && !dual_high)*len + dual_high*len];
179 
180  for (int i = 0; i < len; i++) {
181  k1 = -split_radix_permutation(offset + i*2 + 0, n, inv) & (n - 1);
182  k2 = -split_radix_permutation(offset + i*2 + 1, n, inv) & (n - 1);
183  *even++ = k1;
184  *odd++ = k2;
185  if (stride && !((i + 1) % stride)) {
186  even += stride;
187  odd += stride;
188  }
189  }
190 
191  return;
192  }
193 
194  parity_revtab_generator(revtab, n, inv, offset,
195  0, 0, len >> 0, basis, dual_stride);
196  parity_revtab_generator(revtab, n, inv, offset + (len >> 0),
197  1, 0, len >> 1, basis, dual_stride);
198  parity_revtab_generator(revtab, n, inv, offset + (len >> 0) + (len >> 1),
199  1, 1, len >> 1, basis, dual_stride);
200 }
201 
202 void ff_tx_gen_split_radix_parity_revtab(int *revtab, int len, int inv,
203  int basis, int dual_stride)
204 {
205  basis >>= 1;
206  if (len < basis)
207  return;
208  av_assert0(!dual_stride || !(dual_stride & (dual_stride - 1)));
209  av_assert0(dual_stride <= basis);
210  parity_revtab_generator(revtab, len, inv, 0, 0, 0, len, basis, dual_stride);
211 }
212 
214 {
215  if (!(*ctx))
216  return;
217 
218  av_free((*ctx)->pfatab);
219  av_free((*ctx)->exptab);
220  av_free((*ctx)->revtab);
221  av_free((*ctx)->revtab_c);
222  av_free((*ctx)->inplace_idx);
223  av_free((*ctx)->tmp);
224 
225  av_freep(ctx);
226 }
227 
229  int inv, int len, const void *scale, uint64_t flags)
230 {
231  int err;
232  AVTXContext *s = av_mallocz(sizeof(*s));
233  if (!s)
234  return AVERROR(ENOMEM);
235 
236  switch (type) {
237  case AV_TX_FLOAT_FFT:
238  case AV_TX_FLOAT_MDCT:
239  if ((err = ff_tx_init_mdct_fft_float(s, tx, type, inv, len, scale, flags)))
240  goto fail;
241  if (ARCH_X86)
242  ff_tx_init_float_x86(s, tx);
243  break;
244  case AV_TX_DOUBLE_FFT:
245  case AV_TX_DOUBLE_MDCT:
246  if ((err = ff_tx_init_mdct_fft_double(s, tx, type, inv, len, scale, flags)))
247  goto fail;
248  break;
249  case AV_TX_INT32_FFT:
250  case AV_TX_INT32_MDCT:
251  if ((err = ff_tx_init_mdct_fft_int32(s, tx, type, inv, len, scale, flags)))
252  goto fail;
253  break;
254  default:
255  err = AVERROR(EINVAL);
256  goto fail;
257  }
258 
259  *ctx = s;
260 
261  return 0;
262 
263 fail:
264  av_tx_uninit(&s);
265  *tx = NULL;
266  return err;
267 }
stride
int stride
Definition: mace.c:144
AV_TX_DOUBLE_MDCT
@ AV_TX_DOUBLE_MDCT
Same as AV_TX_FLOAT_MDCT with data and scale type of double.
Definition: tx.h:72
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later. That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another. Frame references ownership and permissions
AVTXContext
Definition: tx_priv.h:110
basis
static int16_t basis[64][64]
Definition: mpegvideo_enc.c:4134
tmp
static uint8_t tmp[11]
Definition: aes_ctr.c:26
even
Tag MUST be even
Definition: snow.txt:206
AV_TX_DOUBLE_FFT
@ AV_TX_DOUBLE_FFT
Same as AV_TX_FLOAT_FFT with a data type of AVComplexDouble.
Definition: tx.h:66
av_tx_init
av_cold int av_tx_init(AVTXContext **ctx, av_tx_fn *tx, enum AVTXType type, int inv, int len, const void *scale, uint64_t flags)
Initialize a transform context with the given configuration (i)MDCTs with an odd length are currently...
Definition: tx.c:228
av_malloc
#define av_malloc(s)
Definition: tableprint_vlc.h:31
ff_tx_gen_split_radix_parity_revtab
void ff_tx_gen_split_radix_parity_revtab(int *revtab, int len, int inv, int basis, int dual_stride)
Definition: tx.c:202
fail
#define fail()
Definition: checkasm.h:127
type
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf type
Definition: writing_filters.txt:86
scale
static av_always_inline float scale(float x, float s)
Definition: vf_v360.c:1377
ff_tx_init_float_x86
void ff_tx_init_float_x86(AVTXContext *s, av_tx_fn *tx)
Definition: tx_float_init.c:37
av_cold
#define av_cold
Definition: attributes.h:90
av_tx_fn
void(* av_tx_fn)(AVTXContext *s, void *out, void *in, ptrdiff_t stride)
Function pointer to a function to perform the transform.
Definition: tx.h:102
AV_TX_FLOAT_MDCT
@ AV_TX_FLOAT_MDCT
Standard MDCT with sample data type of float and a scale type of float.
Definition: tx.h:61
ff_tx_init_mdct_fft_double
int ff_tx_init_mdct_fft_double(AVTXContext *s, av_tx_fn *tx, enum AVTXType type, int inv, int len, const void *scale, uint64_t flags)
s
#define s(width, name)
Definition: cbs_vp9.c:257
ff_tx_gen_compound_mapping
int ff_tx_gen_compound_mapping(AVTXContext *s)
Definition: tx.c:45
AV_TX_INT32_MDCT
@ AV_TX_INT32_MDCT
Same as AV_TX_FLOAT_MDCT with data type of int32_t and scale type of float.
Definition: tx.h:84
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
AV_TX_FLOAT_FFT
@ AV_TX_FLOAT_FFT
Standard complex to complex FFT with sample data type AVComplexFloat.
Definition: tx.h:45
ctx
AVFormatContext * ctx
Definition: movenc.c:48
ff_tx_init_mdct_fft_float
int ff_tx_init_mdct_fft_float(AVTXContext *s, av_tx_fn *tx, enum AVTXType type, int inv, int len, const void *scale, uint64_t flags)
NULL
#define NULL
Definition: coverity.c:32
ff_tx_gen_ptwo_inplace_revtab_idx
int ff_tx_gen_ptwo_inplace_revtab_idx(AVTXContext *s, int *revtab)
Definition: tx.c:127
src
#define src
Definition: vp8dsp.c:255
AVTXType
AVTXType
Definition: tx.h:39
AV_TX_INT32_FFT
@ AV_TX_INT32_FFT
Same as AV_TX_FLOAT_FFT with a data type of AVComplexInt32.
Definition: tx.h:77
ff_tx_init_mdct_fft_int32
int ff_tx_init_mdct_fft_int32(AVTXContext *s, av_tx_fn *tx, enum AVTXType type, int inv, int len, const void *scale, uint64_t flags)
offset
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf offset
Definition: writing_filters.txt:86
ff_tx_type_is_mdct
int ff_tx_type_is_mdct(enum AVTXType type)
Definition: tx.c:21
av_tx_uninit
av_cold void av_tx_uninit(AVTXContext **ctx)
Frees a context and sets ctx to NULL, does nothing when ctx == NULL.
Definition: tx.c:213
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:271
ff_tx_gen_ptwo_revtab
int ff_tx_gen_ptwo_revtab(AVTXContext *s, int invert_lookup)
Definition: tx.c:106
av_always_inline
#define av_always_inline
Definition: attributes.h:49
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49
av_mallocz
void * av_mallocz(size_t size)
Allocate a memory block with alignment suitable for all memory accesses (including vectors if availab...
Definition: mem.c:263
len
int len
Definition: vorbis_enc_data.h:426
tx_priv.h
FFSWAP
#define FFSWAP(type, a, b)
Definition: macros.h:52
split_radix_permutation
static int split_radix_permutation(int i, int m, int inverse)
Definition: tx.c:95
inverse
static int inverse(AudioFWTDNContext *s, double **in, int *in_length, double *out, int out_length, int ch, uint64_t sn)
Definition: af_afwtdn.c:762
av_free
#define av_free(p)
Definition: tableprint_vlc.h:34
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
flags
#define flags(name, subs,...)
Definition: cbs_av1.c:561
mulinv
static av_always_inline int mulinv(int n, int m)
Definition: tx.c:34
parity_revtab_generator
static void parity_revtab_generator(int *revtab, int n, int inv, int offset, int is_dual, int dual_high, int len, int basis, int dual_stride)
Definition: tx.c:164