Changes to ec_dec_cdf() to support 8-bit tables.
authorTimothy B. Terriberry <tterribe@xiph.org>
Mon, 3 Jan 2011 00:53:28 +0000 (16:53 -0800)
committerJean-Marc Valin <jean-marc.valin@usherbrooke.ca>
Sat, 8 Jan 2011 19:57:01 +0000 (14:57 -0500)
This renames ec_dec_cdf() to ec_dec_icdf(), and changes the
 functionality to use an "inverse" CDF table, where
 icdf[i]=ft-cdf[i+1].
The first entry is omitted entirely.
It also adds a corresonding ec_enc_icdf() to the encoder, which uses
 the same table.
One could use ec_encode_bin() by converting the values in the tables
 back to normal CDF values, but the icdf[] table already has them in
 the form ec_encode_bin() wants to use them, so there's no reason to
 translate them and then translate them back.

This is done primarily to allow SILK to use the range coder with
 8-bit probability tables containing cumulative frequencies that
 span the full range 0...256.
With an 8-bit table, the final 256 of a normal CDF becomes 0 in the
 "inverse" CDF.
It's the 0 at the start of a normal CDF which would become 256, but
 this is the value we omit, as it already has to be special-cased in
 the encoder, and is not used at all in the decoder.

libcelt/celt.c
libcelt/entdec.h
libcelt/entenc.h
libcelt/rangedec.c
libcelt/rangeenc.c
tests/ectest.c

index 6b83908..b2f875f 100644 (file)
@@ -53,8 +53,9 @@
 #include <stdarg.h>
 #include "plc.h"
 
-static const unsigned trim_cdf[12] = {0, 2, 4, 9, 19, 41, 87, 109, 119, 124, 126, 128};
-static const unsigned spread_cdf[5] = {0, 7, 9, 30, 32};
+static const unsigned char trim_icdf[11] = {126, 124, 119, 109, 87, 41, 19, 9, 4, 2, 0};
+/* Probs: NONE: 21.875%, LIGHT: 6.25%, NORMAL: 65.625%, AGGRESSIVE: 6.25% */
+static const unsigned char spread_icdf[4] = {25, 23, 2, 0};
 
 #define COMBFILTER_MAXPERIOD 1024
 #define COMBFILTER_MINPERIOD 16
@@ -975,9 +976,7 @@ int celt_encode_with_ec_float(CELTEncoder * restrict st, const celt_sig * pcm, i
    } else {
       st->spread_decision = spreading_decision(st->mode, X, &st->tonal_average, st->spread_decision, effEnd, C, M);
    }
-   /* Probs: NONE: 21.875%, LIGHT: 6.25%, NORMAL: 65.625%, AGGRESSIVE: 6.25% */
-   ec_encode_bin(enc, spread_cdf[st->spread_decision],
-         spread_cdf[st->spread_decision+1], 5);
+   ec_enc_icdf(enc, st->spread_decision, spread_icdf, 5);
 
    ALLOC(offsets, st->mode->nbEBands, int);
 
@@ -1030,7 +1029,7 @@ int celt_encode_with_ec_float(CELTEncoder * restrict st, const celt_sig * pcm, i
       }
    }
    alloc_trim = alloc_trim_analysis(st->mode, X, bandLogE, st->mode->nbEBands, LM, C, N);
-   ec_encode_bin(enc, trim_cdf[alloc_trim], trim_cdf[alloc_trim+1], 7);
+   ec_enc_icdf(enc, alloc_trim, trim_icdf, 7);
 
    /* Variable bitrate */
    if (st->vbr_rate_norm>0)
@@ -1850,7 +1849,7 @@ int celt_decode_with_ec_float(CELTDecoder * restrict st, const unsigned char *da
    ALLOC(tf_res, st->mode->nbEBands, int);
    tf_decode(st->start, st->end, C, isTransient, tf_res, LM, dec);
 
-   spread_decision = ec_dec_cdf(dec, spread_cdf, 5);
+   spread_decision = ec_dec_icdf(dec, spread_icdf, 5);
 
    ALLOC(pulses, st->mode->nbEBands, int);
    ALLOC(offsets, st->mode->nbEBands, int);
@@ -1878,7 +1877,7 @@ int celt_decode_with_ec_float(CELTDecoder * restrict st, const unsigned char *da
    }
 
    ALLOC(fine_quant, st->mode->nbEBands, int);
-   alloc_trim = ec_dec_cdf(dec, trim_cdf, 7);
+   alloc_trim = ec_dec_icdf(dec, trim_icdf, 7);
 
    if (C==2)
    {
index d4c0686..ac8d43e 100644 (file)
@@ -113,15 +113,15 @@ ec_uint32 ec_dec_bits(ec_dec *_this,unsigned _ftb);
        This must be at least one, and no more than 2**32-1.
   Return: The decoded bits.*/
 ec_uint32 ec_dec_uint(ec_dec *_this,ec_uint32 _ft);
-/*Decodes a symbol given its CDF.
+/*Decodes a symbol given an "inverse" CDF table.
   No call to ec_dec_update() is necessary after this call.
-  _cdf: The CDF, such that symbol s falls in the range [_cdf[s],_cdf[s+1]).
-        The first value must be 0, the last value must be (1<<_ftb), and the
-         values must be monotonicly non-decreasing.
+  _icdf: The "inverse" CDF, such that symbol s falls in the range
+          [s>0?ft-_icdf[s-1]:0,ft-_icdf[s]), where ft=1<<_ftb.
+         The values must be monotonically non-increasing, and the last value
+          must be 0.
   _ftb: The number of bits of precision in the cumulative distribution.
-  Return: The decoded symbol s, which must have been encoded with
-   ec_encode_bin(enc,_cdf[s],_cdf[s+1],_ftb).*/
-int ec_dec_cdf(ec_dec *_this,const unsigned *_cdf,unsigned _ftb);
+  Return: The decoded symbol s.*/
+int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb);
 
 /* Decode a bit that has a _prob/65536 probability of being a one */
 int ec_dec_bit_prob(ec_dec *_this,unsigned _prob);
index b64ed81..4840440 100644 (file)
@@ -100,6 +100,15 @@ void ec_enc_bit_prob(ec_enc *_this,int val,unsigned _prob);
 /* Encode a bit that has a 1/(1<<_logp) probability of being a one */
 void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp);
 
+/*Encodes a symbol given an "inverse" CDF table.
+  _s:    The index of the symbol to encode.
+  _icdf: The "inverse" CDF, such that symbol _s falls in the range
+          [_s>0?ft-_icdf[_s-1]:0,ft-_icdf[_s]), where ft=1<<_ftb.
+         The values must be monotonically non-increasing, and the last value
+          must be 0.
+  _ftb: The number of bits of precision in the cumulative distribution.*/
+void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb);
+
 /*Returns the number of bits "used" by the encoded symbols so far.
   This same number can be computed by the decoder, and is suitable for making
    coding decisions.
index 7dce4a1..51cb8e2 100644 (file)
@@ -187,7 +187,7 @@ int ec_dec_bit_logp(ec_dec *_this,unsigned _logp){
   return val;
 }
 
-int ec_dec_cdf(ec_dec *_this,const unsigned *_cdf,unsigned _ftb){
+int ec_dec_icdf(ec_dec *_this,const unsigned char *_icdf,unsigned _ftb){
   ec_uint32 r;
   ec_uint32 d;
   ec_uint32 s;
@@ -199,7 +199,7 @@ int ec_dec_cdf(ec_dec *_this,const unsigned *_cdf,unsigned _ftb){
   val=0;
   do{
     t=s;
-    s=IMUL32(r,(1<<_ftb)-_cdf[++val]);
+    s=IMUL32(r,_icdf[val++]);
   }
   while(d<s);
   _this->dif=d-s;
index 5f27644..fad9aa6 100644 (file)
@@ -169,6 +169,17 @@ void ec_enc_bit_logp(ec_enc *_this,int _val,unsigned _logp){
   ec_enc_normalize(_this);
 }
 
+void ec_enc_icdf(ec_enc *_this,int _s,const unsigned char *_icdf,unsigned _ftb){
+  ec_uint32 r;
+  r=_this->rng>>_ftb;
+  if(_s>0){
+    _this->low+=_this->rng-IMUL32(r,_icdf[_s-1]);
+    _this->rng=IMUL32(r,_icdf[_s-1]-_icdf[_s]);
+  }
+  else _this->rng-=IMUL32(r,_icdf[_s]);
+  ec_enc_normalize(_this);
+}
+
 void ec_enc_bits(ec_enc *_this,ec_uint32 _fl,unsigned _bits){
   ec_window window;
   int       used;
index 190beef..7b65c04 100644 (file)
@@ -188,7 +188,7 @@ int main(int _argc,char **_argv){
     for(j=0;j<sz;j++){
       data[j]=rand()/((RAND_MAX>>1)+1);
       logp1[j]=(rand()%15)+1;
-      enc_method[j]=rand()%3;
+      enc_method[j]=rand()/((RAND_MAX>>2)+1);
       switch(enc_method[j]){
         case 0:{
           ec_encode(&enc,data[j]?(1<<logp1[j])-1:0,
@@ -201,6 +201,12 @@ int main(int _argc,char **_argv){
         case 2:{
           ec_enc_bit_logp(&enc,data[j],logp1[j]);
         }break;
+        case 3:{
+          unsigned icdf[2];
+          icdf[0]=1;
+          icdf[1]=0;
+          ec_enc_icdf(&enc,data[j],icdf,logp1[j]);
+        }break;
       }
       tell[j+1]=ec_enc_tell(&enc,3);
     }
@@ -238,11 +244,10 @@ int main(int _argc,char **_argv){
           sym=ec_dec_bit_logp(&dec,logp1[j]);
         }break;
         case 3:{
-          unsigned cdf[3];
-          cdf[0]=0;
-          cdf[1]=(1<<logp1[j])-1;
-          cdf[2]=1<<logp1[j];
-          sym=ec_dec_cdf(&dec,cdf,logp1[j]);
+          unsigned icdf[2];
+          icdf[0]=1;
+          icdf[1]=0;
+          sym=ec_dec_icdf(&dec,icdf,logp1[j]);
         }break;
       }
       if(sym!=data[j]){