git.sesse.net Git - ffmpeg/blob - libavutil/tx.c

   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
  21 /* Calculates the modular multiplicative inverse, not fast, replace */
  22 static av_always_inline int mulinv(int n, int m)
  23 {
  24     n = n % m;
  25     for (int x = 1; x < m; x++)
  26         if (((n * x) % m) == 1)
  27             return x;
  28     av_assert0(0); /* Never reached */
  29 }
  30
  31 /* Guaranteed to work for any n, m where gcd(n, m) == 1 */
  32 int ff_tx_gen_compound_mapping(AVTXContext *s)
  33 {
  34     int *in_map, *out_map;
  35     const int n     = s->n;
  36     const int m     = s->m;
  37     const int inv   = s->inv;
  38     const int type  = s->type;
  39     const int len   = n*m;
  40     const int m_inv = mulinv(m, n);
  41     const int n_inv = mulinv(n, m);
  42     const int mdct  = type == AV_TX_FLOAT_MDCT || type == AV_TX_DOUBLE_MDCT;
  43
  44     if (!(s->pfatab = av_malloc(2*len*sizeof(*s->pfatab))))
  45         return AVERROR(ENOMEM);
  46
  47     in_map  = s->pfatab;
  48     out_map = s->pfatab + n*m;
  49
  50     /* Ruritanian map for input, CRT map for output, can be swapped */
  51     for (int j = 0; j < m; j++) {
  52         for (int i = 0; i < n; i++) {
  53             /* Shifted by 1 to simplify MDCTs */
  54             in_map[j*n + i] = ((i*m + j*n) % len) << mdct;
  55             out_map[(i*m*m_inv + j*n*n_inv) % len] = i*m + j;
  56         }
  57     }
  58
  59     /* Change transform direction by reversing all ACs */
  60     if (inv) {
  61         for (int i = 0; i < m; i++) {
  62             int *in = &in_map[i*n + 1]; /* Skip the DC */
  63             for (int j = 0; j < ((n - 1) >> 1); j++)
  64                 FFSWAP(int, in[j], in[n - j - 2]);
  65         }
  66     }
  67
  68     /* Our 15-point transform is also a compound one, so embed its input map */
  69     if (n == 15) {
  70         for (int k = 0; k < m; k++) {
  71             int tmp[15];
  72             memcpy(tmp, &in_map[k*15], 15*sizeof(*tmp));
  73             for (int i = 0; i < 5; i++) {
  74                 for (int j = 0; j < 3; j++)
  75                     in_map[k*15 + i*3 + j] = tmp[(i*3 + j*5) % 15];
  76             }
  77         }
  78     }
  79
  80     return 0;
  81 }
  82
  83 int ff_tx_gen_ptwo_revtab(AVTXContext *s)
  84 {
  85     const int m = s->m, inv = s->inv;
  86
  87     if (!(s->revtab = av_malloc(m*sizeof(*s->revtab))))
  88         return AVERROR(ENOMEM);
  89
  90     /* Default */
  91     for (int i = 0; i < m; i++) {
  92         int k = -split_radix_permutation(i, m, inv) & (m - 1);
  93         s->revtab[k] = i;
  94     }
  95
  96     return 0;
  97 }
  98
  99 av_cold void av_tx_uninit(AVTXContext **ctx)
 100 {
 101     if (!(*ctx))
 102         return;
 103
 104     av_free((*ctx)->pfatab);
 105     av_free((*ctx)->exptab);
 106     av_free((*ctx)->revtab);
 107     av_free((*ctx)->tmp);
 108
 109     av_freep(ctx);
 110 }
 111
 112 av_cold int av_tx_init(AVTXContext **ctx, av_tx_fn *tx, enum AVTXType type,
 113                        int inv, int len, const void *scale, uint64_t flags)
 114 {
 115     int err;
 116     AVTXContext *s = av_mallocz(sizeof(*s));
 117     if (!s)
 118         return AVERROR(ENOMEM);
 119
 120     switch (type) {
 121     case AV_TX_FLOAT_FFT:
 122     case AV_TX_FLOAT_MDCT:
 123         if ((err = ff_tx_init_mdct_fft_float(s, tx, type, inv, len, scale, flags)))
 124             goto fail;
 125         break;
 126     case AV_TX_DOUBLE_FFT:
 127     case AV_TX_DOUBLE_MDCT:
 128         if ((err = ff_tx_init_mdct_fft_double(s, tx, type, inv, len, scale, flags)))
 129             goto fail;
 130         break;
 131     default:
 132         err = AVERROR(EINVAL);
 133         goto fail;
 134     }
 135
 136     *ctx = s;
 137
 138     return 0;
 139
 140 fail:
 141     av_tx_uninit(&s);
 142     *tx = NULL;
 143     return err;
 144 }