Don't do theta RDO on intensity-stereo-coded bands
[opus.git] / celt / kiss_fft.c
index 9869e9e..8377516 100644 (file)
 
 static void kf_bfly2(
                      kiss_fft_cpx * Fout,
-                     const size_t fstride,
-                     const kiss_fft_state *st,
                      int m,
-                     int N,
-                     int mm
+                     int N
                     )
 {
    kiss_fft_cpx * Fout2;
-   const kiss_twiddle_cpx * tw1;
-   int i,j;
-   kiss_fft_cpx * Fout_beg = Fout;
-   for (i=0;i<N;i++)
+   int i;
+   (void)m;
+#ifdef CUSTOM_MODES
+   if (m==1)
    {
-      Fout = Fout_beg + i*mm;
-      Fout2 = Fout + m;
-      tw1 = st->twiddles;
-      for(j=0;j<m;j++)
+      celt_assert(m==1);
+      for (i=0;i<N;i++)
       {
          kiss_fft_cpx t;
-         C_MUL (t,  *Fout2 , *tw1);
-         tw1 += fstride;
+         Fout2 = Fout + 1;
+         t = *Fout2;
          C_SUB( *Fout2 ,  *Fout , t );
          C_ADDTO( *Fout ,  t );
-         ++Fout2;
-         ++Fout;
+         Fout += 2;
+      }
+   } else
+#endif
+   {
+      opus_val16 tw;
+      tw = QCONST16(0.7071067812f, 15);
+      /* We know that m==4 here because the radix-2 is just after a radix-4 */
+      celt_assert(m==4);
+      for (i=0;i<N;i++)
+      {
+         kiss_fft_cpx t;
+         Fout2 = Fout + 4;
+         t = Fout2[0];
+         C_SUB( Fout2[0] ,  Fout[0] , t );
+         C_ADDTO( Fout[0] ,  t );
+
+         t.r = S_MUL(ADD32_ovflw(Fout2[1].r, Fout2[1].i), tw);
+         t.i = S_MUL(SUB32_ovflw(Fout2[1].i, Fout2[1].r), tw);
+         C_SUB( Fout2[1] ,  Fout[1] , t );
+         C_ADDTO( Fout[1] ,  t );
+
+         t.r = Fout2[2].i;
+         t.i = -Fout2[2].r;
+         C_SUB( Fout2[2] ,  Fout[2] , t );
+         C_ADDTO( Fout[2] ,  t );
+
+         t.r = S_MUL(SUB32_ovflw(Fout2[3].i, Fout2[3].r), tw);
+         t.i = S_MUL(NEG32_ovflw(ADD32_ovflw(Fout2[3].i, Fout2[3].r)), tw);
+         C_SUB( Fout2[3] ,  Fout[3] , t );
+         C_ADDTO( Fout[3] ,  t );
+         Fout += 8;
       }
    }
 }
@@ -101,10 +126,10 @@ static void kf_bfly4(
          C_ADDTO( *Fout , scratch1 );
          C_SUB( scratch1 , Fout[1] , Fout[3] );
 
-         Fout[1].r = scratch0.r + scratch1.i;
-         Fout[1].i = scratch0.i - scratch1.r;
-         Fout[3].r = scratch0.r - scratch1.i;
-         Fout[3].i = scratch0.i + scratch1.r;
+         Fout[1].r = ADD32_ovflw(scratch0.r, scratch1.i);
+         Fout[1].i = SUB32_ovflw(scratch0.i, scratch1.r);
+         Fout[3].r = SUB32_ovflw(scratch0.r, scratch1.i);
+         Fout[3].i = ADD32_ovflw(scratch0.i, scratch1.r);
          Fout+=4;
       }
    } else {
@@ -118,6 +143,7 @@ static void kf_bfly4(
       {
          Fout = Fout_beg + i*mm;
          tw3 = tw2 = tw1 = st->twiddles;
+         /* m is guaranteed to be a multiple of 4. */
          for (j=0;j<m;j++)
          {
             C_MUL(scratch[0],Fout[m] , *tw1 );
@@ -134,10 +160,10 @@ static void kf_bfly4(
             tw3 += fstride*3;
             C_ADDTO( *Fout , scratch[3] );
 
-            Fout[m].r = scratch[5].r + scratch[4].i;
-            Fout[m].i = scratch[5].i - scratch[4].r;
-            Fout[m3].r = scratch[5].r - scratch[4].i;
-            Fout[m3].i = scratch[5].i + scratch[4].r;
+            Fout[m].r = ADD32_ovflw(scratch[5].r, scratch[4].i);
+            Fout[m].i = SUB32_ovflw(scratch[5].i, scratch[4].r);
+            Fout[m3].r = SUB32_ovflw(scratch[5].r, scratch[4].i);
+            Fout[m3].i = ADD32_ovflw(scratch[5].i, scratch[4].r);
             ++Fout;
          }
       }
@@ -164,11 +190,17 @@ static void kf_bfly3(
    kiss_twiddle_cpx epi3;
 
    kiss_fft_cpx * Fout_beg = Fout;
+#ifdef FIXED_POINT
+   /*epi3.r = -16384;*/ /* Unused */
+   epi3.i = -28378;
+#else
    epi3 = st->twiddles[fstride*m];
+#endif
    for (i=0;i<N;i++)
    {
       Fout = Fout_beg + i*mm;
       tw1=tw2=st->twiddles;
+      /* For non-custom modes, m is guaranteed to be a multiple of 4. */
       k=m;
       do {
 
@@ -180,18 +212,18 @@ static void kf_bfly3(
          tw1 += fstride;
          tw2 += fstride*2;
 
-         Fout[m].r = Fout->r - HALF_OF(scratch[3].r);
-         Fout[m].i = Fout->i - HALF_OF(scratch[3].i);
+         Fout[m].r = SUB32_ovflw(Fout->r, HALF_OF(scratch[3].r));
+         Fout[m].i = SUB32_ovflw(Fout->i, HALF_OF(scratch[3].i));
 
          C_MULBYSCALAR( scratch[0] , epi3.i );
 
          C_ADDTO(*Fout,scratch[3]);
 
-         Fout[m2].r = Fout[m].r + scratch[0].i;
-         Fout[m2].i = Fout[m].i - scratch[0].r;
+         Fout[m2].r = ADD32_ovflw(Fout[m].r, scratch[0].i);
+         Fout[m2].i = SUB32_ovflw(Fout[m].i, scratch[0].r);
 
-         Fout[m].r -= scratch[0].i;
-         Fout[m].i += scratch[0].r;
+         Fout[m].r = SUB32_ovflw(Fout[m].r, scratch[0].i);
+         Fout[m].i = ADD32_ovflw(Fout[m].i, scratch[0].r);
 
          ++Fout;
       } while(--k);
@@ -199,6 +231,7 @@ static void kf_bfly3(
 }
 
 
+#ifndef OVERRIDE_kf_bfly5
 static void kf_bfly5(
                      kiss_fft_cpx * Fout,
                      const size_t fstride,
@@ -211,13 +244,19 @@ static void kf_bfly5(
    kiss_fft_cpx *Fout0,*Fout1,*Fout2,*Fout3,*Fout4;
    int i, u;
    kiss_fft_cpx scratch[13];
-   const kiss_twiddle_cpx * twiddles = st->twiddles;
    const kiss_twiddle_cpx *tw;
    kiss_twiddle_cpx ya,yb;
    kiss_fft_cpx * Fout_beg = Fout;
 
-   ya = twiddles[fstride*m];
-   yb = twiddles[fstride*2*m];
+#ifdef FIXED_POINT
+   ya.r = 10126;
+   ya.i = -31164;
+   yb.r = -26510;
+   yb.i = -19261;
+#else
+   ya = st->twiddles[fstride*m];
+   yb = st->twiddles[fstride*2*m];
+#endif
    tw=st->twiddles;
 
    for (i=0;i<N;i++)
@@ -229,6 +268,7 @@ static void kf_bfly5(
       Fout3=Fout0+3*m;
       Fout4=Fout0+4*m;
 
+      /* For non-custom modes, m is guaranteed to be a multiple of 4. */
       for ( u=0; u<m; ++u ) {
          scratch[0] = *Fout0;
 
@@ -242,22 +282,22 @@ static void kf_bfly5(
          C_ADD( scratch[8],scratch[2],scratch[3]);
          C_SUB( scratch[9],scratch[2],scratch[3]);
 
-         Fout0->r += scratch[7].r + scratch[8].r;
-         Fout0->i += scratch[7].i + scratch[8].i;
+         Fout0->r = ADD32_ovflw(Fout0->r, ADD32_ovflw(scratch[7].r, scratch[8].r));
+         Fout0->i = ADD32_ovflw(Fout0->i, ADD32_ovflw(scratch[7].i, scratch[8].i));
 
-         scratch[5].r = scratch[0].r + S_MUL(scratch[7].r,ya.r) + S_MUL(scratch[8].r,yb.r);
-         scratch[5].i = scratch[0].i + S_MUL(scratch[7].i,ya.r) + S_MUL(scratch[8].i,yb.r);
+         scratch[5].r = ADD32_ovflw(scratch[0].r, ADD32_ovflw(S_MUL(scratch[7].r,ya.r), S_MUL(scratch[8].r,yb.r)));
+         scratch[5].i = ADD32_ovflw(scratch[0].i, ADD32_ovflw(S_MUL(scratch[7].i,ya.r), S_MUL(scratch[8].i,yb.r)));
 
-         scratch[6].r =  S_MUL(scratch[10].i,ya.i) + S_MUL(scratch[9].i,yb.i);
-         scratch[6].i = -S_MUL(scratch[10].r,ya.i) - S_MUL(scratch[9].r,yb.i);
+         scratch[6].r =  ADD32_ovflw(S_MUL(scratch[10].i,ya.i), S_MUL(scratch[9].i,yb.i));
+         scratch[6].i = NEG32_ovflw(ADD32_ovflw(S_MUL(scratch[10].r,ya.i), S_MUL(scratch[9].r,yb.i)));
 
          C_SUB(*Fout1,scratch[5],scratch[6]);
          C_ADD(*Fout4,scratch[5],scratch[6]);
 
-         scratch[11].r = scratch[0].r + S_MUL(scratch[7].r,yb.r) + S_MUL(scratch[8].r,ya.r);
-         scratch[11].i = scratch[0].i + S_MUL(scratch[7].i,yb.r) + S_MUL(scratch[8].i,ya.r);
-         scratch[12].r = - S_MUL(scratch[10].i,yb.i) + S_MUL(scratch[9].i,ya.i);
-         scratch[12].i = S_MUL(scratch[10].r,yb.i) - S_MUL(scratch[9].r,ya.i);
+         scratch[11].r = ADD32_ovflw(scratch[0].r, ADD32_ovflw(S_MUL(scratch[7].r,yb.r), S_MUL(scratch[8].r,ya.r)));
+         scratch[11].i = ADD32_ovflw(scratch[0].i, ADD32_ovflw(S_MUL(scratch[7].i,yb.r), S_MUL(scratch[8].i,ya.r)));
+         scratch[12].r = SUB32_ovflw(S_MUL(scratch[9].i,ya.i), S_MUL(scratch[10].i,yb.i));
+         scratch[12].i = SUB32_ovflw(S_MUL(scratch[10].r,yb.i), S_MUL(scratch[9].r,ya.i));
 
          C_ADD(*Fout2,scratch[11],scratch[12]);
          C_SUB(*Fout3,scratch[11],scratch[12]);
@@ -266,6 +306,7 @@ static void kf_bfly5(
       }
    }
 }
+#endif /* OVERRIDE_kf_bfly5 */
 
 
 #endif
@@ -339,6 +380,11 @@ int kf_factor(int n,opus_int16 * facbuf)
            return 0;
         }
         facbuf[2*stages] = p;
+        if (p==2 && stages > 1)
+        {
+           facbuf[2*stages] = 4;
+           facbuf[2] = 2;
+        }
         stages++;
     } while (n > 1);
     n = nbak;
@@ -377,13 +423,19 @@ static void compute_twiddles(kiss_twiddle_cpx *twiddles, int nfft)
 #endif
 }
 
+int opus_fft_alloc_arch_c(kiss_fft_state *st) {
+   (void)st;
+   return 0;
+}
+
 /*
  *
  * Allocates all necessary storage space for the fft and ifft.
  * The return value is a contiguous block of memory.  As such,
  * It can be freed with free().
  * */
-kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  const kiss_fft_state *base)
+kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,
+                                        const kiss_fft_state *base, int arch)
 {
     kiss_fft_state *st=NULL;
     size_t memneeded = sizeof(struct kiss_fft_state); /* twiddle factors*/
@@ -400,14 +452,20 @@ kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  co
         kiss_twiddle_cpx *twiddles;
 
         st->nfft=nfft;
-#ifndef FIXED_POINT
+#ifdef FIXED_POINT
+        st->scale_shift = celt_ilog2(st->nfft);
+        if (st->nfft == 1<<st->scale_shift)
+           st->scale = Q15ONE;
+        else
+           st->scale = (1073741824+st->nfft/2)/st->nfft>>(15-st->scale_shift);
+#else
         st->scale = 1.f/nfft;
 #endif
         if (base != NULL)
         {
            st->twiddles = base->twiddles;
            st->shift = 0;
-           while (nfft<<st->shift != base->nfft && st->shift < 32)
+           while (st->shift < 32 && nfft<<st->shift != base->nfft)
               st->shift++;
            if (st->shift>=32)
               goto fail;
@@ -426,22 +484,31 @@ kiss_fft_state *opus_fft_alloc_twiddles(int nfft,void * mem,size_t * lenmem,  co
         if (st->bitrev==NULL)
             goto fail;
         compute_bitrev_table(0, bitrev, 1,1, st->factors,st);
+
+        /* Initialize architecture specific fft parameters */
+        if (opus_fft_alloc_arch(st, arch))
+            goto fail;
     }
     return st;
 fail:
-    opus_fft_free(st);
+    opus_fft_free(st, arch);
     return NULL;
 }
 
-kiss_fft_state *opus_fft_alloc(int nfft,void * mem,size_t * lenmem )
+kiss_fft_state *opus_fft_alloc(int nfft,void * mem,size_t * lenmem, int arch)
 {
-   return opus_fft_alloc_twiddles(nfft, mem, lenmem, NULL);
+   return opus_fft_alloc_twiddles(nfft, mem, lenmem, NULL, arch);
 }
 
-void opus_fft_free(const kiss_fft_state *cfg)
+void opus_fft_free_arch_c(kiss_fft_state *st) {
+   (void)st;
+}
+
+void opus_fft_free(const kiss_fft_state *cfg, int arch)
 {
    if (cfg)
    {
+      opus_fft_free_arch((kiss_fft_state *)cfg, arch);
       opus_free((opus_int16*)cfg->bitrev);
       if (cfg->shift < 0)
          opus_free((kiss_twiddle_cpx*)cfg->twiddles);
@@ -481,7 +548,7 @@ void opus_fft_impl(const kiss_fft_state *st,kiss_fft_cpx *fout)
        switch (st->factors[2*i])
        {
        case 2:
-          kf_bfly2(fout,fstride[i]<<shift,st,m, fstride[i], m2);
+          kf_bfly2(fout, m, fstride[i]);
           break;
        case 4:
           kf_bfly4(fout,fstride[i]<<shift,st,m, fstride[i], m2);
@@ -499,39 +566,30 @@ void opus_fft_impl(const kiss_fft_state *st,kiss_fft_cpx *fout)
     }
 }
 
-void opus_fft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
+void opus_fft_c(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
 {
    int i;
-#ifdef FIXED_POINT
-   /* FIXME: This should eventually just go in the state. */
    opus_val16 scale;
-   int scale_shift;
-   scale_shift = celt_ilog2(st->nfft);
-   if (st->nfft == 1<<scale_shift)
-      scale = Q15ONE;
-   else
-      scale = (1073741824+st->nfft/2)/st->nfft>>(15-scale_shift);
+#ifdef FIXED_POINT
+   /* Allows us to scale with MULT16_32_Q16(), which is faster than
+      MULT16_32_Q15() on ARM. */
+   int scale_shift = st->scale_shift-1;
 #endif
+   scale = st->scale;
 
    celt_assert2 (fin != fout, "In-place FFT not supported");
    /* Bit-reverse the input */
    for (i=0;i<st->nfft;i++)
    {
       kiss_fft_cpx x = fin[i];
-#ifdef FIXED_POINT
-      fout[st->bitrev[i]].r = SHR32(MULT16_32_Q15(scale, x.r), scale_shift);
-      fout[st->bitrev[i]].i = SHR32(MULT16_32_Q15(scale, x.i), scale_shift);
-#else
-      fout[st->bitrev[i]].r = st->scale*x.r;
-      fout[st->bitrev[i]].i = st->scale*x.i;
-#endif
+      fout[st->bitrev[i]].r = SHR32(MULT16_32_Q16(scale, x.r), scale_shift);
+      fout[st->bitrev[i]].i = SHR32(MULT16_32_Q16(scale, x.i), scale_shift);
    }
    opus_fft_impl(st, fout);
 }
 
 
-#ifdef TEST_UNIT_DFT_C
-void opus_ifft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
+void opus_ifft_c(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fout)
 {
    int i;
    celt_assert2 (fin != fout, "In-place FFT not supported");
@@ -544,4 +602,3 @@ void opus_ifft(const kiss_fft_state *st,const kiss_fft_cpx *fin,kiss_fft_cpx *fo
    for (i=0;i<st->nfft;i++)
       fout[i].i = -fout[i].i;
 }
-#endif