Implemented split-cwrs for very large codebooks (>64 bits), but still getting
authorJean-Marc Valin <Jean-Marc.Valin@csiro.au>
Tue, 10 Jun 2008 07:23:03 +0000 (17:23 +1000)
committerJean-Marc Valin <Jean-Marc.Valin@csiro.au>
Tue, 10 Jun 2008 07:23:03 +0000 (17:23 +1000)
a few decoding errors.

libcelt/cwrs.c
libcelt/cwrs.h
libcelt/rate.c
libcelt/rate.h

index 0158b67..6a9fba7 100644 (file)
 #include "cwrs.h"
 #include "mathops.h"
 
+#if 0
+int log2_frac(ec_uint32 val, int frac)
+{
+   int i;
+   /* EC_ILOG() actually returns log2()+1, go figure */
+   int L = EC_ILOG(val)-1;
+   /*printf ("in: %d %d ", val, L);*/
+   if (L>14)
+      val >>= L-14;
+   else if (L<14)
+      val <<= 14-L;
+   L <<= frac;
+   /*printf ("%d\n", val);*/
+   for (i=0;i<frac;i++)
+{
+      val = (val*val) >> 15;
+      /*printf ("%d\n", val);*/
+      if (val > 16384)
+         L |= (1<<(frac-i-1));
+      else   
+         val <<= 1;
+}
+   return L;
+}
+#endif
+
+int log2_frac64(ec_uint64 val, int frac)
+{
+   int i;
+   /* EC_ILOG64() actually returns log2()+1, go figure */
+   int L = EC_ILOG64(val)-1;
+   /*printf ("in: %d %d ", val, L);*/
+   if (L>14)
+      val >>= L-14;
+   else if (L<14)
+      val <<= 14-L;
+   L <<= frac;
+   /*printf ("%d\n", val);*/
+   for (i=0;i<frac;i++)
+   {
+      val = (val*val) >> 15;
+      /*printf ("%d\n", val);*/
+      if (val > 16384)
+         L |= (1<<(frac-i-1));
+      else   
+         val <<= 1;
+   }
+   return L;
+}
+
 int fits_in32(int _n, int _m)
 {
    static const celt_int16_t maxN[15] = {
@@ -367,6 +417,25 @@ static inline void encode_comb64(int _n,int _m,const int *_x,const int *_s,
   RESTORE_STACK;
 }
 
+int get_required_bits(int N, int K, int frac)
+{
+   int nbits = 0;
+   if(fits_in64(N,K))
+   {
+      VARDECL(celt_uint64_t,u);
+      SAVE_STACK;
+      ALLOC(u,N,celt_uint64_t);
+      nbits = log2_frac64(ncwrs_u64(N,K,u), frac);
+      RESTORE_STACK;
+   } else {
+      nbits = log2_frac64(N, frac);
+      nbits += get_required_bits(N/2+1, (K+1)/2, frac);
+      nbits += get_required_bits(N/2+1, K/2, frac);
+   }
+   return nbits;
+}
+
+
 void encode_pulses(int *_y, int N, int K, ec_enc *enc)
 {
    VARDECL(int, comb);
@@ -377,12 +446,36 @@ void encode_pulses(int *_y, int N, int K, ec_enc *enc)
    ALLOC(signs, K, int);
 
    pulse2comb(N, K, comb, signs, _y);
-   /* Simple heuristic to figure out whether it fits in 32 bits */
-   if(fits_in32(N,K))
+   if (N==1)
+   {
+      ec_enc_bits(enc, _y[0]<0, 1);
+   } else if(fits_in32(N,K))
    {
       encode_comb32(N, K, comb, signs, enc);
-   } else {
+   } else if(fits_in64(N,K)) {
       encode_comb64(N, K, comb, signs, enc);
+   } else {
+     int count=0;
+     int split=0;
+     int tmp;
+     while (split<N)
+     {
+       count += abs(_y[split]);
+       if (count >= (K+1)/2)
+         break;
+       split++;
+     }
+     count -= (K+1)/2;
+     ec_enc_uint(enc,split,N);
+     if (_y[split]<0)
+       count = -count;
+     tmp = _y[split];
+     _y[split] -= count;
+     encode_pulses(_y, split+1, (K+1)/2, enc);
+     _y[split] = count;
+     if (K/2 != 0)
+       encode_pulses(_y+split, N-split, K/2, enc);
+     _y[split] = tmp;
    }
    RESTORE_STACK;
 }
@@ -412,12 +505,28 @@ void decode_pulses(int *_y, int N, int K, ec_dec *dec)
    ALLOC(comb, K, int);
    ALLOC(signs, K, int);
    /* Simple heuristic to figure out whether it fits in 32 bits */
-   if(fits_in32(N,K))
+   if (N==1)
+   {
+      int s = ec_dec_bits(dec, 1);
+      if (s==0)
+         _y[0] = K;
+      else
+         _y[0] = -K;
+   } else if(fits_in32(N,K))
    {
       decode_comb32(N, K, comb, signs, dec);
-   } else {
+      comb2pulse(N, K, _y, comb, signs);
+   } else if(fits_in64(N,K)) {
       decode_comb64(N, K, comb, signs, dec);
+      comb2pulse(N, K, _y, comb, signs);
+   } else {
+     int count;
+     int split = ec_dec_uint(dec,N);
+     decode_pulses(_y, split+1, (K+1)/2, dec);
+     count = _y[split];
+     if (K/2 != 0)
+       decode_pulses(_y+split, N-split, K/2, dec);
+     _y[split] += count;
    }
-   comb2pulse(N, K, _y, comb, signs);
    RESTORE_STACK;
 }
index 5585709..6366297 100644 (file)
@@ -36,6 +36,8 @@
 #include "entenc.h"
 #include "entdec.h"
 
+/* Returns log of an integer with fractional accuracy */
+int log2_frac64(ec_uint64 val, int frac);
 /* Whether the CWRS codebook will fit into 32 bits */
 int fits_in32(int _n, int _m);
 /* Whether the CWRS codebook will fit into 64 bits */
@@ -66,6 +68,8 @@ void comb2pulse(int _n,int _m,int * restrict _y,const int *_x,const int *_s);
 
 void pulse2comb(int _n,int _m,int *_x,int *_s,const int *_y);
 
+int get_required_bits(int N, int K, int frac);
+
 void encode_pulses(int *_y, int N, int K, ec_enc *enc);
 
 void decode_pulses(int *_y, int N, int K, ec_dec *dec);
index 97546b1..3aea466 100644 (file)
 #define BITOVERFLOW 30000
 
 #ifndef STATIC_MODES
-#if 0
-static int log2_frac(ec_uint32 val, int frac)
-{
-   int i;
-   /* EC_ILOG() actually returns log2()+1, go figure */
-   int L = EC_ILOG(val)-1;
-   /*printf ("in: %d %d ", val, L);*/
-   if (L>14)
-      val >>= L-14;
-   else if (L<14)
-      val <<= 14-L;
-   L <<= frac;
-   /*printf ("%d\n", val);*/
-   for (i=0;i<frac;i++)
-   {
-      val = (val*val) >> 15;
-      /*printf ("%d\n", val);*/
-      if (val > 16384)
-         L |= (1<<(frac-i-1));
-      else   
-         val <<= 1;
-   }
-   return L;
-}
-#endif
-
-static int log2_frac64(ec_uint64 val, int frac)
-{
-   int i;
-   /* EC_ILOG64() actually returns log2()+1, go figure */
-   int L = EC_ILOG64(val)-1;
-   /*printf ("in: %d %d ", val, L);*/
-   if (L>14)
-      val >>= L-14;
-   else if (L<14)
-      val <<= 14-L;
-   L <<= frac;
-   /*printf ("%d\n", val);*/
-   for (i=0;i<frac;i++)
-   {
-      val = (val*val) >> 15;
-      /*printf ("%d\n", val);*/
-      if (val > 16384)
-         L |= (1<<(frac-i-1));
-      else   
-         val <<= 1;
-   }
-   return L;
-}
 
 celt_int16_t **compute_alloc_cache(CELTMode *m, int C)
 {
@@ -114,14 +65,10 @@ celt_int16_t **compute_alloc_cache(CELTMode *m, int C)
          bits[i] = bits[i-1];
       } else {
          int j;
-         VARDECL(celt_uint64_t, u);
-         SAVE_STACK;
-         ALLOC(u, N, celt_uint64_t);
          /* FIXME: We could save memory here */
          bits[i] = celt_alloc(MAX_PULSES*sizeof(celt_int16_t));
          for (j=0;j<MAX_PULSES;j++)
          {
-            int done = 0;
             int pulses = j;
             /* For bands where there's no pitch, id 1 corresponds to intra prediction 
             with no pulse. id 2 means intra prediction with one pulse, and so on.*/
@@ -130,22 +77,15 @@ celt_int16_t **compute_alloc_cache(CELTMode *m, int C)
             if (pulses < 0)
                bits[i][j] = 0;
             else {
-               celt_uint64_t nc;
-               if (!fits_in64(N, pulses))
-                  break;
-               nc=pulses?ncwrs_unext64(N, u):ncwrs_u64(N, 0, u);
-               bits[i][j] = log2_frac64(nc,BITRES);
+               bits[i][j] = get_required_bits(N, pulses, BITRES);
                /* Add the intra-frame prediction sign bit */
                if (eBands[i] >= m->pitchEnd)
                   bits[i][j] += (1<<BITRES);
             }
-            if (done)
-               break;
          }
          for (;j<MAX_PULSES;j++)
             bits[i][j] = BITOVERFLOW;
          prevN = N;
-         RESTORE_STACK;
       }
    }
    return bits;
index 0edafeb..ff8b05d 100644 (file)
@@ -32,8 +32,8 @@
 #ifndef RATE_H
 #define RATE_H
 
-#define MAX_PULSES 64
-#define LOG_MAX_PULSES 6
+#define MAX_PULSES 128
+#define LOG_MAX_PULSES 7
 
 /** Computes a cache of the pulses->bits mapping in each band */
 celt_int16_t **compute_alloc_cache(CELTMode *m, int C);