Home | History | Annotate | Download | only in celt
      1 /* Copyright (c) 2007-2008 CSIRO
      2    Copyright (c) 2007-2008 Xiph.Org Foundation
      3    Written by Jean-Marc Valin */
      4 /*
      5    Redistribution and use in source and binary forms, with or without
      6    modification, are permitted provided that the following conditions
      7    are met:
      8 
      9    - Redistributions of source code must retain the above copyright
     10    notice, this list of conditions and the following disclaimer.
     11 
     12    - Redistributions in binary form must reproduce the above copyright
     13    notice, this list of conditions and the following disclaimer in the
     14    documentation and/or other materials provided with the distribution.
     15 
     16    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
     20    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
     21    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     22    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     23    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
     24    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     25    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     26    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
     28 
     29 /* This is a simple MDCT implementation that uses a N/4 complex FFT
     30    to do most of the work. It should be relatively straightforward to
     31    plug in pretty much and FFT here.
     32 
     33    This replaces the Vorbis FFT (and uses the exact same API), which
     34    was a bit too messy and that was ending up duplicating code
     35    (might as well use the same FFT everywhere).
     36 
     37    The algorithm is similar to (and inspired from) Fabrice Bellard's
     38    MDCT implementation in FFMPEG, but has differences in signs, ordering
     39    and scaling in many places.
     40 */
     41 
     42 #ifndef SKIP_CONFIG_H
     43 #ifdef HAVE_CONFIG_H
     44 #include "config.h"
     45 #endif
     46 #endif
     47 
     48 #include "mdct.h"
     49 #include "kiss_fft.h"
     50 #include "_kiss_fft_guts.h"
     51 #include <math.h>
     52 #include "os_support.h"
     53 #include "mathops.h"
     54 #include "stack_alloc.h"
     55 
     56 #if defined(MIPSr1_ASM)
     57 #include "mips/mdct_mipsr1.h"
     58 #endif
     59 
     60 
     61 #ifdef CUSTOM_MODES
     62 
     63 int clt_mdct_init(mdct_lookup *l,int N, int maxshift, int arch)
     64 {
     65    int i;
     66    kiss_twiddle_scalar *trig;
     67    int shift;
     68    int N2=N>>1;
     69    l->n = N;
     70    l->maxshift = maxshift;
     71    for (i=0;i<=maxshift;i++)
     72    {
     73       if (i==0)
     74          l->kfft[i] = opus_fft_alloc(N>>2>>i, 0, 0, arch);
     75       else
     76          l->kfft[i] = opus_fft_alloc_twiddles(N>>2>>i, 0, 0, l->kfft[0], arch);
     77 #ifndef ENABLE_TI_DSPLIB55
     78       if (l->kfft[i]==NULL)
     79          return 0;
     80 #endif
     81    }
     82    l->trig = trig = (kiss_twiddle_scalar*)opus_alloc((N-(N2>>maxshift))*sizeof(kiss_twiddle_scalar));
     83    if (l->trig==NULL)
     84      return 0;
     85    for (shift=0;shift<=maxshift;shift++)
     86    {
     87       /* We have enough points that sine isn't necessary */
     88 #if defined(FIXED_POINT)
     89 #if 1
     90       for (i=0;i<N2;i++)
     91          trig[i] = TRIG_UPSCALE*celt_cos_norm(DIV32(ADD32(SHL32(EXTEND32(i),17),N2+16384),N));
     92 #else
     93       for (i=0;i<N2;i++)
     94          trig[i] = (kiss_twiddle_scalar)MAX32(-32767,MIN32(32767,floor(.5+32768*cos(2*M_PI*(i+.125)/N))));
     95 #endif
     96 #else
     97       for (i=0;i<N2;i++)
     98          trig[i] = (kiss_twiddle_scalar)cos(2*PI*(i+.125)/N);
     99 #endif
    100       trig += N2;
    101       N2 >>= 1;
    102       N >>= 1;
    103    }
    104    return 1;
    105 }
    106 
    107 void clt_mdct_clear(mdct_lookup *l, int arch)
    108 {
    109    int i;
    110    for (i=0;i<=l->maxshift;i++)
    111       opus_fft_free(l->kfft[i], arch);
    112    opus_free((kiss_twiddle_scalar*)l->trig);
    113 }
    114 
    115 #endif /* CUSTOM_MODES */
    116 
    117 /* Forward MDCT trashes the input array */
    118 #ifndef OVERRIDE_clt_mdct_forward
    119 void clt_mdct_forward_c(const mdct_lookup *l, kiss_fft_scalar *in, kiss_fft_scalar * OPUS_RESTRICT out,
    120       const opus_val16 *window, int overlap, int shift, int stride, int arch)
    121 {
    122    int i;
    123    int N, N2, N4;
    124    VARDECL(kiss_fft_scalar, f);
    125    VARDECL(kiss_fft_cpx, f2);
    126    const kiss_fft_state *st = l->kfft[shift];
    127    const kiss_twiddle_scalar *trig;
    128    opus_val16 scale;
    129 #ifdef FIXED_POINT
    130    /* Allows us to scale with MULT16_32_Q16(), which is faster than
    131       MULT16_32_Q15() on ARM. */
    132    int scale_shift = st->scale_shift-1;
    133 #endif
    134    SAVE_STACK;
    135    (void)arch;
    136    scale = st->scale;
    137 
    138    N = l->n;
    139    trig = l->trig;
    140    for (i=0;i<shift;i++)
    141    {
    142       N >>= 1;
    143       trig += N;
    144    }
    145    N2 = N>>1;
    146    N4 = N>>2;
    147 
    148    ALLOC(f, N2, kiss_fft_scalar);
    149    ALLOC(f2, N4, kiss_fft_cpx);
    150 
    151    /* Consider the input to be composed of four blocks: [a, b, c, d] */
    152    /* Window, shuffle, fold */
    153    {
    154       /* Temp pointers to make it really clear to the compiler what we're doing */
    155       const kiss_fft_scalar * OPUS_RESTRICT xp1 = in+(overlap>>1);
    156       const kiss_fft_scalar * OPUS_RESTRICT xp2 = in+N2-1+(overlap>>1);
    157       kiss_fft_scalar * OPUS_RESTRICT yp = f;
    158       const opus_val16 * OPUS_RESTRICT wp1 = window+(overlap>>1);
    159       const opus_val16 * OPUS_RESTRICT wp2 = window+(overlap>>1)-1;
    160       for(i=0;i<((overlap+3)>>2);i++)
    161       {
    162          /* Real part arranged as -d-cR, Imag part arranged as -b+aR*/
    163          *yp++ = MULT16_32_Q15(*wp2, xp1[N2]) + MULT16_32_Q15(*wp1,*xp2);
    164          *yp++ = MULT16_32_Q15(*wp1, *xp1)    - MULT16_32_Q15(*wp2, xp2[-N2]);
    165          xp1+=2;
    166          xp2-=2;
    167          wp1+=2;
    168          wp2-=2;
    169       }
    170       wp1 = window;
    171       wp2 = window+overlap-1;
    172       for(;i<N4-((overlap+3)>>2);i++)
    173       {
    174          /* Real part arranged as a-bR, Imag part arranged as -c-dR */
    175          *yp++ = *xp2;
    176          *yp++ = *xp1;
    177          xp1+=2;
    178          xp2-=2;
    179       }
    180       for(;i<N4;i++)
    181       {
    182          /* Real part arranged as a-bR, Imag part arranged as -c-dR */
    183          *yp++ =  -MULT16_32_Q15(*wp1, xp1[-N2]) + MULT16_32_Q15(*wp2, *xp2);
    184          *yp++ = MULT16_32_Q15(*wp2, *xp1)     + MULT16_32_Q15(*wp1, xp2[N2]);
    185          xp1+=2;
    186          xp2-=2;
    187          wp1+=2;
    188          wp2-=2;
    189       }
    190    }
    191    /* Pre-rotation */
    192    {
    193       kiss_fft_scalar * OPUS_RESTRICT yp = f;
    194       const kiss_twiddle_scalar *t = &trig[0];
    195       for(i=0;i<N4;i++)
    196       {
    197          kiss_fft_cpx yc;
    198          kiss_twiddle_scalar t0, t1;
    199          kiss_fft_scalar re, im, yr, yi;
    200          t0 = t[i];
    201          t1 = t[N4+i];
    202          re = *yp++;
    203          im = *yp++;
    204          yr = S_MUL(re,t0)  -  S_MUL(im,t1);
    205          yi = S_MUL(im,t0)  +  S_MUL(re,t1);
    206          yc.r = yr;
    207          yc.i = yi;
    208          yc.r = PSHR32(MULT16_32_Q16(scale, yc.r), scale_shift);
    209          yc.i = PSHR32(MULT16_32_Q16(scale, yc.i), scale_shift);
    210          f2[st->bitrev[i]] = yc;
    211       }
    212    }
    213 
    214    /* N/4 complex FFT, does not downscale anymore */
    215    opus_fft_impl(st, f2);
    216 
    217    /* Post-rotate */
    218    {
    219       /* Temp pointers to make it really clear to the compiler what we're doing */
    220       const kiss_fft_cpx * OPUS_RESTRICT fp = f2;
    221       kiss_fft_scalar * OPUS_RESTRICT yp1 = out;
    222       kiss_fft_scalar * OPUS_RESTRICT yp2 = out+stride*(N2-1);
    223       const kiss_twiddle_scalar *t = &trig[0];
    224       /* Temp pointers to make it really clear to the compiler what we're doing */
    225       for(i=0;i<N4;i++)
    226       {
    227          kiss_fft_scalar yr, yi;
    228          yr = S_MUL(fp->i,t[N4+i]) - S_MUL(fp->r,t[i]);
    229          yi = S_MUL(fp->r,t[N4+i]) + S_MUL(fp->i,t[i]);
    230          *yp1 = yr;
    231          *yp2 = yi;
    232          fp++;
    233          yp1 += 2*stride;
    234          yp2 -= 2*stride;
    235       }
    236    }
    237    RESTORE_STACK;
    238 }
    239 #endif /* OVERRIDE_clt_mdct_forward */
    240 
    241 #ifndef OVERRIDE_clt_mdct_backward
    242 void clt_mdct_backward_c(const mdct_lookup *l, kiss_fft_scalar *in, kiss_fft_scalar * OPUS_RESTRICT out,
    243       const opus_val16 * OPUS_RESTRICT window, int overlap, int shift, int stride, int arch)
    244 {
    245    int i;
    246    int N, N2, N4;
    247    const kiss_twiddle_scalar *trig;
    248    (void) arch;
    249 
    250    N = l->n;
    251    trig = l->trig;
    252    for (i=0;i<shift;i++)
    253    {
    254       N >>= 1;
    255       trig += N;
    256    }
    257    N2 = N>>1;
    258    N4 = N>>2;
    259 
    260    /* Pre-rotate */
    261    {
    262       /* Temp pointers to make it really clear to the compiler what we're doing */
    263       const kiss_fft_scalar * OPUS_RESTRICT xp1 = in;
    264       const kiss_fft_scalar * OPUS_RESTRICT xp2 = in+stride*(N2-1);
    265       kiss_fft_scalar * OPUS_RESTRICT yp = out+(overlap>>1);
    266       const kiss_twiddle_scalar * OPUS_RESTRICT t = &trig[0];
    267       const opus_int16 * OPUS_RESTRICT bitrev = l->kfft[shift]->bitrev;
    268       for(i=0;i<N4;i++)
    269       {
    270          int rev;
    271          kiss_fft_scalar yr, yi;
    272          rev = *bitrev++;
    273          yr = S_MUL(*xp2, t[i]) + S_MUL(*xp1, t[N4+i]);
    274          yi = S_MUL(*xp1, t[i]) - S_MUL(*xp2, t[N4+i]);
    275          /* We swap real and imag because we use an FFT instead of an IFFT. */
    276          yp[2*rev+1] = yr;
    277          yp[2*rev] = yi;
    278          /* Storing the pre-rotation directly in the bitrev order. */
    279          xp1+=2*stride;
    280          xp2-=2*stride;
    281       }
    282    }
    283 
    284    opus_fft_impl(l->kfft[shift], (kiss_fft_cpx*)(out+(overlap>>1)));
    285 
    286    /* Post-rotate and de-shuffle from both ends of the buffer at once to make
    287       it in-place. */
    288    {
    289       kiss_fft_scalar * yp0 = out+(overlap>>1);
    290       kiss_fft_scalar * yp1 = out+(overlap>>1)+N2-2;
    291       const kiss_twiddle_scalar *t = &trig[0];
    292       /* Loop to (N4+1)>>1 to handle odd N4. When N4 is odd, the
    293          middle pair will be computed twice. */
    294       for(i=0;i<(N4+1)>>1;i++)
    295       {
    296          kiss_fft_scalar re, im, yr, yi;
    297          kiss_twiddle_scalar t0, t1;
    298          /* We swap real and imag because we're using an FFT instead of an IFFT. */
    299          re = yp0[1];
    300          im = yp0[0];
    301          t0 = t[i];
    302          t1 = t[N4+i];
    303          /* We'd scale up by 2 here, but instead it's done when mixing the windows */
    304          yr = S_MUL(re,t0) + S_MUL(im,t1);
    305          yi = S_MUL(re,t1) - S_MUL(im,t0);
    306          /* We swap real and imag because we're using an FFT instead of an IFFT. */
    307          re = yp1[1];
    308          im = yp1[0];
    309          yp0[0] = yr;
    310          yp1[1] = yi;
    311 
    312          t0 = t[(N4-i-1)];
    313          t1 = t[(N2-i-1)];
    314          /* We'd scale up by 2 here, but instead it's done when mixing the windows */
    315          yr = S_MUL(re,t0) + S_MUL(im,t1);
    316          yi = S_MUL(re,t1) - S_MUL(im,t0);
    317          yp1[0] = yr;
    318          yp0[1] = yi;
    319          yp0 += 2;
    320          yp1 -= 2;
    321       }
    322    }
    323 
    324    /* Mirror on both sides for TDAC */
    325    {
    326       kiss_fft_scalar * OPUS_RESTRICT xp1 = out+overlap-1;
    327       kiss_fft_scalar * OPUS_RESTRICT yp1 = out;
    328       const opus_val16 * OPUS_RESTRICT wp1 = window;
    329       const opus_val16 * OPUS_RESTRICT wp2 = window+overlap-1;
    330 
    331       for(i = 0; i < overlap/2; i++)
    332       {
    333          kiss_fft_scalar x1, x2;
    334          x1 = *xp1;
    335          x2 = *yp1;
    336          *yp1++ = MULT16_32_Q15(*wp2, x2) - MULT16_32_Q15(*wp1, x1);
    337          *xp1-- = MULT16_32_Q15(*wp1, x2) + MULT16_32_Q15(*wp2, x1);
    338          wp1++;
    339          wp2--;
    340       }
    341    }
    342 }
    343 #endif /* OVERRIDE_clt_mdct_backward */
    344