ref: 3ad8db49c55111896610c0d1f4ac9c425741b41e
parent: ba3a28921a2a4cb898efe7867e6c1ff370ebe8e4
author: Jean-Marc Valin <[email protected]>
date: Wed Aug 25 09:11:09 EDT 2010
New pulse cache
--- a/libcelt/bands.c
+++ b/libcelt/bands.c
@@ -718,8 +718,8 @@
} 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 @@
{*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;
}
--- a/libcelt/cwrs.c
+++ b/libcelt/cwrs.c
@@ -269,27 +269,6 @@
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 @@
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 @@
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 @@
_y[i] = 0;
return;
}
- celt_assert (fits_in32(_n,_k));
switch(_n){ case 1:{celt_assert(ncwrs1(_k)==2);
--- a/libcelt/dump_modes.c
+++ b/libcelt/dump_modes.c
@@ -99,43 +99,6 @@
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);--- a/libcelt/modes.c
+++ b/libcelt/modes.c
@@ -413,17 +413,6 @@
#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 @@
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 @@
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,34 +470,6 @@
}
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);
@@ -515,6 +476,8 @@
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);
--- a/libcelt/modes.h
+++ b/libcelt/modes.h
@@ -67,6 +67,12 @@
#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 @@
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 @@
int *prob;
const celt_int16 *logN;
+
+ PulseCache cache;
celt_uint32 marker_end;
};
--- a/libcelt/rate.c
+++ b/libcelt/rate.c
@@ -46,65 +46,87 @@
#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++;
+ }
+ }
}
- return bits;
+ 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];
+ }
}
#endif /* !STATIC_MODES */
--- a/libcelt/rate.h
+++ b/libcelt/rate.h
@@ -46,38 +46,49 @@
#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 */