New pulse cache
authorJean-Marc Valin <jean-marc.valin@octasic.com>
Wed, 25 Aug 2010 17:11:09 +0000 (13:11 -0400)
committerJean-Marc Valin <jean-marc.valin@octasic.com>
Wed, 25 Aug 2010 17:11:09 +0000 (13:11 -0400)
libcelt/bands.c
libcelt/cwrs.c
libcelt/dump_modes.c
libcelt/modes.c
libcelt/modes.h
libcelt/rate.c
libcelt/rate.h

index f0c008c..3e2390d 100644 (file)
@@ -718,8 +718,8 @@ static void quant_band(int encode, const CELTMode *m, int i, celt_norm *X, celt_
 
    } else {
       /* This is the basic no-split case */
-      q = bits2pulses(m, m->bits[LM][i], N, b);
-      curr_bits = pulses2bits(m->bits[LM][i], N, q);
+      q = bits2pulses(m, i, LM, b);
+      curr_bits = pulses2bits(m, i, LM, q);
       *remaining_bits -= curr_bits;
 
       /* Ensures we can never bust the budget */
@@ -727,7 +727,7 @@ static void quant_band(int encode, const CELTMode *m, int i, celt_norm *X, celt_
       {
          *remaining_bits += curr_bits;
          q--;
-         curr_bits = pulses2bits(m->bits[LM][i], N, q);
+         curr_bits = pulses2bits(m, i, LM, q);
          *remaining_bits -= curr_bits;
       }
 
index 2d9975c..8f35c85 100644 (file)
@@ -269,27 +269,6 @@ static inline celt_uint32 imusdiv32even(celt_uint32 _a,celt_uint32 _b,
     year=1986
   }*/
 
-/*Determines if V(N,K) fits in a 32-bit unsigned integer.
-  N and K are themselves limited to 15 bits.*/
-static int fits_in32(int _n, int _k)
-{
-   static const celt_int16 maxN[15] = {
-      32767, 32767, 32767, 1476, 283, 109,  60,  40,
-       29,  24,  20,  18,  16,  14,  13};
-   static const celt_int16 maxK[15] = {
-      32767, 32767, 32767, 32767, 1172, 238,  95,  53,
-       36,  27,  22,  18,  16,  15,  13};
-   if (_n>=14)
-   {
-      if (_k>=14)
-         return 0;
-      else
-         return _n <= maxN[_k];
-   } else {
-      return _k <= maxK[_n];
-   }
-}
-
 #ifndef SMALL_FOOTPRINT
 
 /*Compute U(1,_k).*/
@@ -670,25 +649,20 @@ void get_required_bits(celt_int16 *_bits,int _n,int _maxk,int _frac){
   int k;
   /*_maxk==0 => there's nothing to do.*/
   celt_assert(_maxk>0);
+  _bits[0]=0;
   if (_n==1)
   {
-    _bits[0] = 0;
     for (k=1;k<_maxk;k++)
       _bits[k] = 1<<_frac;
   }
   else {
-    _bits[0]=0;
-    if(_maxk>1){
-      VARDECL(celt_uint32,u);
-      SAVE_STACK;
-      ALLOC(u,_maxk+1U,celt_uint32);
-      ncwrs_urow(_n,_maxk-1,u);
-      for(k=1;k<_maxk&&fits_in32(_n, k);k++)
-        _bits[k]=log2_frac(u[k]+u[k+1],_frac);
-      for(;k<_maxk;k++)
-        _bits[k] = 10000;
-      RESTORE_STACK;
-    }
+    VARDECL(celt_uint32,u);
+    SAVE_STACK;
+    ALLOC(u,_maxk+2U,celt_uint32);
+    ncwrs_urow(_n,_maxk,u);
+    for(k=1;k<=_maxk;k++)
+      _bits[k]=log2_frac(u[k]+u[k+1],_frac);
+    RESTORE_STACK;
   }
 }
 
@@ -697,7 +671,6 @@ void encode_pulses(const int *_y,int _n,int _k,ec_enc *_enc){
   celt_uint32 i;
   if (_k==0)
      return;
-  celt_assert(fits_in32(_n,_k));
   switch(_n){
     case 1:{
       i=icwrs1(_y,&_k);
@@ -743,7 +716,6 @@ void decode_pulses(int *_y,int _n,int _k,ec_dec *_dec)
          _y[i] = 0;
       return;
    }
-   celt_assert (fits_in32(_n,_k));
    switch(_n){
     case 1:{
       celt_assert(ncwrs1(_k)==2);
index 1552478..1a8ad53 100644 (file)
@@ -99,43 +99,6 @@ void dump_modes(FILE *file, CELTMode **modes, int nb_modes)
       fprintf(file, "#endif\n");
       fprintf(file, "\n");
 
-      for (k=0;(1<<k>>1)<=mode->nbShortMdcts;k++)
-      {
-         int mdctSize2 = mode->shortMdctSize;
-         if (k>=1)
-            mdctSize2 <<= k-1;
-         else
-            mdctSize2 >>= 1;
-         fprintf(file, "#ifndef DEF_ALLOC_CACHE%d_%d\n", mode->Fs, mdctSize2);
-         fprintf(file, "#define DEF_ALLOC_CACHE%d_%d\n", mode->Fs, mdctSize2);
-         for (j=0;j<mode->nbEBands;j++)
-         {
-            int m;
-            if (mode->_bits[k][j]==NULL)
-            {
-               fprintf (file, "#define allocCache_band%d_%d_%d NULL\n", j, mode->Fs, mdctSize2);
-               continue;
-            }
-            if (j==0 || (mode->_bits[k][j] != mode->_bits[k][j-1]))
-            {
-               fprintf (file, "static const celt_int16 allocCache_band%d_%d_%d[MAX_PSEUDO] = {\n", j, mode->Fs, mdctSize2);
-               for (m=0;m<MAX_PSEUDO;m++)
-                  fprintf (file, "%2d, ", mode->_bits[k][j][m]);
-               fprintf (file, "};\n");
-            } else {
-               fprintf (file, "#define allocCache_band%d_%d_%d allocCache_band%d_%d_%d\n", j, mode->Fs, mdctSize2, j-1, mode->Fs, mdctSize2);
-            }
-         }
-         fprintf (file, "static const celt_int16 *allocCache%d_%d[%d] = {\n", mode->Fs, mdctSize2, mode->nbEBands);
-         for (j=0;j<mode->nbEBands;j++)
-         {
-            fprintf (file, "allocCache_band%d_%d_%d, ", j, mode->Fs, mdctSize2);
-         }
-         fprintf (file, "};\n");
-         fprintf(file, "#endif\n");
-         fprintf(file, "\n");
-      }
-
       fprintf(file, "#ifndef DEF_LOGN%d_%d\n", mode->Fs, mdctSize);
       fprintf(file, "#define DEF_LOGN%d_%d\n", mode->Fs, mdctSize);
       fprintf (file, "static const celt_int16 logN%d_%d[%d] = {\n", mode->Fs, mdctSize, mode->nbEBands);
index b8e7258..dc78cc3 100644 (file)
@@ -413,17 +413,6 @@ CELTMode *celt_mode_create(celt_int32 Fs, int frame_size, int *error)
 #endif
    mode->window = window;
 
-   mode->bits = mode->_bits+1;
-   for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
-   {
-      mode->bits[i] = (const celt_int16 **)compute_alloc_cache(mode, 1<<i);
-      if (mode->bits[i]==NULL)
-         goto failure;
-   }
-   mode->bits[-1] = (const celt_int16 **)compute_alloc_cache(mode, 0);
-   if (mode->bits[-1]==NULL)
-      goto failure;
-
    logN = (celt_int16*)celt_alloc(mode->nbEBands*sizeof(celt_int16));
    if (logN==NULL)
       goto failure;
@@ -431,6 +420,8 @@ CELTMode *celt_mode_create(celt_int32 Fs, int frame_size, int *error)
    for (i=0;i<mode->nbEBands;i++)
       logN[i] = log2_frac(mode->eBands[i+1]-mode->eBands[i], BITRES);
    mode->logN = logN;
+
+   compute_pulse_cache(mode, mode->maxLM);
 #endif /* !STATIC_MODES */
 
    clt_mdct_init(&mode->mdct, 2*mode->shortMdctSize*mode->nbShortMdcts, LM);
@@ -460,8 +451,6 @@ failure:
 
 void celt_mode_destroy(CELTMode *mode)
 {
-   int i, m;
-   const celt_int16 *prevPtr = NULL;
    if (mode == NULL)
    {
       celt_warning("NULL passed to celt_mode_destroy");
@@ -481,40 +470,14 @@ void celt_mode_destroy(CELTMode *mode)
    }
    mode->marker_start = MODEFREED;
 #ifndef STATIC_MODES
-   for (m=0;(1<<m)<=mode->nbShortMdcts;m++)
-   {
-      if (mode->bits[m]!=NULL)
-      {
-         for (i=0;i<mode->nbEBands;i++)
-         {
-            if (mode->bits[m][i] != prevPtr)
-            {
-               prevPtr = mode->bits[m][i];
-               celt_free((int*)mode->bits[m][i]);
-            }
-         }
-      }
-      celt_free((celt_int16**)mode->bits[m]);
-   }
-   if (mode->bits[-1]!=NULL)
-   {
-      for (i=0;i<mode->nbEBands;i++)
-      {
-         if (mode->bits[-1][i] != prevPtr)
-         {
-            prevPtr = mode->bits[-1][i];
-            celt_free((int*)mode->bits[-1][i]);
-         }
-      }
-   }
-   celt_free((celt_int16**)mode->bits[-1]);
-
    celt_free((celt_int16*)mode->eBands);
    celt_free((celt_int16*)mode->allocVectors);
    
    celt_free((celt_word16*)mode->window);
    celt_free((celt_int16*)mode->logN);
 
+   celt_free(mode->cache.index);
+   celt_free(mode->cache.bits);
 #endif
    clt_mdct_clear(&mode->mdct);
 
index 7bf642f..e45c542 100644 (file)
 #define FRAMESIZE(mode) ((mode)->mdctSize)
 #endif
 
+typedef struct {
+   int nbBands;
+   celt_int16 *index;
+   unsigned char *bits;
+} PulseCache;
+
 /** Mode definition (opaque)
  @brief Mode definition 
  */
@@ -83,9 +89,6 @@ struct CELTMode {
    int          nbAllocVectors; /**< Number of lines in the matrix below */
    const unsigned char   *allocVectors;   /**< Number of bits in each band for several rates */
    
-   const celt_int16 * const **bits;
-   const celt_int16 * const *(_bits[MAX_CONFIG_SIZES]); /**< Cache for pulses->bits mapping in each band */
-
    /* Stuff that could go in the {en,de}coder, but we save space this way */
    mdct_lookup mdct;
 
@@ -97,6 +100,8 @@ struct CELTMode {
 
    int *prob;
    const celt_int16 *logN;
+
+   PulseCache cache;
    celt_uint32 marker_end;
 };
 
index 6330b17..eef27ea 100644 (file)
 
 #ifndef STATIC_MODES
 
-celt_int16 **compute_alloc_cache(CELTMode *m, int M)
+/*Determines if V(N,K) fits in a 32-bit unsigned integer.
+  N and K are themselves limited to 15 bits.*/
+static int fits_in32(int _n, int _k)
 {
-   int i, prevN;
-   int error = 0;
-   celt_int16 **bits;
-   const celt_int16 *eBands = m->eBands;
-
-   bits = celt_alloc(m->nbEBands*sizeof(celt_int16*));
-   if (bits==NULL)
-     return NULL;
-        
-   prevN = -1;
-   for (i=0;i<m->nbEBands;i++)
+   static const celt_int16 maxN[15] = {
+      32767, 32767, 32767, 1476, 283, 109,  60,  40,
+       29,  24,  20,  18,  16,  14,  13};
+   static const celt_int16 maxK[15] = {
+      32767, 32767, 32767, 32767, 1172, 238,  95,  53,
+       36,  27,  22,  18,  16,  15,  13};
+   if (_n>=14)
    {
-      int N;
-      if (M>0)
-         N = M*(eBands[i+1]-eBands[i]);
+      if (_k>=14)
+         return 0;
       else
-         N = (eBands[i+1]-eBands[i])>>1;
-      if (N==0)
-      {
-         bits[i] = NULL;
-         continue;
-      }
-      if (N == prevN)
-      {
-         bits[i] = bits[i-1];
-      } else {
-         bits[i] = celt_alloc(MAX_PSEUDO*sizeof(celt_int16));
-         if (bits[i]!=NULL) {
-            int j;
-            celt_int16 tmp[MAX_PULSES];
-            get_required_bits(tmp, N, MAX_PULSES, BITRES);
-            for (j=0;j<MAX_PSEUDO;j++)
-               bits[i][j] = tmp[get_pulses(j)];
-         } else {
-            error=1;
-         }
-         prevN = N;
-      }
+         return _n <= maxN[_k];
+   } else {
+      return _k <= maxK[_n];
    }
-   if (error)
+}
+
+void compute_pulse_cache(CELTMode *m, int LM)
+{
+   int i;
+   int curr=0;
+   int nbEntries=0;
+   int entryN[100], entryK[100], entryI[100];
+   const celt_int16 *eBands = m->eBands;
+   PulseCache *cache = &m->cache;
+
+   cache->nbBands = m->nbEBands;
+   cache->index = celt_alloc(sizeof(cache->index[0])*cache->nbBands*(LM+2));
+
+   for (i=0;i<=LM+1;i++)
    {
-      const celt_int16 *prevPtr = NULL;
-      if (bits!=NULL)
+      int j;
+      for (j=0;j<cache->nbBands;j++)
       {
-         for (i=0;i<m->nbEBands;i++)
+         int k;
+         int N = (eBands[j+1]-eBands[j])<<i>>1;
+         cache->index[i*cache->nbBands+j] = -1;
+         for (k=0;k<=i;k++)
          {
-            if (bits[i] != prevPtr && bits[i] != NULL)
+            int n;
+            for (n=0;n<cache->nbBands && (k!=i || n<j);n++)
             {
-               prevPtr = bits[i];
-               celt_free((int*)bits[i]);
+               if (N == (eBands[n+1]-eBands[n])<<k>>1)
+               {
+                  cache->index[i*cache->nbBands+j] =
+                        cache->index[k*cache->nbBands+n];
+                  break;
+               }
             }
          }
-         free(bits);
-         bits=NULL;
-      }   
+         if (cache->index[i*cache->nbBands+j] == -1)
+         {
+            int K;
+            entryN[nbEntries] = N;
+            K = 0;
+            while (fits_in32(N,get_pulses(K+1)) && K<MAX_PSEUDO-1)
+               K++;
+            entryK[nbEntries] = K;
+            cache->index[i*cache->nbBands+j] = curr;
+            entryI[nbEntries] = curr;
+
+            curr += K+1;
+            nbEntries++;
+         }
+      }
+   }
+   cache->bits = celt_alloc(sizeof(unsigned char)*curr);
+   for (i=0;i<nbEntries;i++)
+   {
+      int j;
+      unsigned char *ptr = cache->bits+entryI[i];
+      celt_int16 tmp[MAX_PULSES];
+      get_required_bits(tmp, entryN[i], get_pulses(entryK[i]), BITRES);
+      for (j=1;j<=entryK[i];j++)
+         ptr[j] = tmp[get_pulses(j)]-1;
+      ptr[0] = entryK[i];
    }
-   return bits;
 }
 
 #endif /* !STATIC_MODES */
index 6466f75..ebda8f3 100644 (file)
 #define BITOVERFLOW 30000
 
 #include "cwrs.h"
+#include "modes.h"
+
+void compute_pulse_cache(CELTMode *m, int LM);
 
 static inline int get_pulses(int i)
 {
    return i<8 ? i : (8 + (i&7)) << ((i>>3)-1);
 }
 
-static inline int bits2pulses(const CELTMode *m, const celt_int16 *cache, int N, int bits)
+static inline int bits2pulses(const CELTMode *m, int band, int LM, int bits)
 {
    int i;
    int lo, hi;
+   unsigned char *cache;
+
+   LM++;
+   cache = m->cache.bits + m->cache.index[LM*m->cache.nbBands+band];
 
    lo = 0;
-   hi = MAX_PSEUDO-1;
+   hi = cache[0];
+   //for (i=0;i<=hi;i++) printf ("%d ", cache[i]); printf ("\n");
    for (i=0;i<LOG_MAX_PSEUDO;i++)
    {
       int mid = (lo+hi)>>1;
       /* OPT: Make sure this is implemented with a conditional move */
-      if (cache[mid] >= bits)
+      if (cache[mid]+1 >= bits)
          hi = mid;
       else
          lo = mid;
    }
-   if (bits-cache[lo] <= cache[hi]-bits)
+   if (bits- (lo == 0 ? 0 : cache[lo]+1) <= cache[hi]+1-bits)
       return lo;
    else
       return hi;
 }
 
-
-static inline int pulses2bits(const celt_int16 *cache, int N, int pulses)
+static inline int pulses2bits(const CELTMode *m, int band, int LM, int pulses)
 {
-   return cache[pulses];
+   unsigned char *cache;
+
+   LM++;
+   cache = m->cache.bits + m->cache.index[LM*m->cache.nbBands+band];
+   return pulses == 0 ? 0 : cache[pulses]+1;
 }
 
 /** Computes a cache of the pulses->bits mapping in each band */