shithub: opus

Info  •  Files  •  Log  •  Branches

Changes to ec_dec_cdf() to support 8-bit tables.

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.

--- a/libcelt/celt.c

+++ b/libcelt/celt.c

@@ -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 @@

    } 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 @@

       }

    }

    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 @@

    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 @@

    }

    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)

    {

--- a/libcelt/entdec.h

+++ b/libcelt/entdec.h

@@ -113,15 +113,15 @@

        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);

--- a/libcelt/entenc.h

+++ b/libcelt/entenc.h

@@ -100,6 +100,15 @@

 /* 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.

--- a/libcelt/rangedec.c

+++ b/libcelt/rangedec.c

@@ -187,7 +187,7 @@

   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 @@

   val=0;

   do{

     t=s;

-    s=IMUL32(r,(1<<_ftb)-_cdf[++val]);

+    s=IMUL32(r,_icdf[val++]);

   }

   while(d<s);

   _this->dif=d-s;

--- a/libcelt/rangeenc.c

+++ b/libcelt/rangeenc.c

@@ -169,6 +169,17 @@

   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;

--- a/tests/ectest.c

+++ b/tests/ectest.c

@@ -188,7 +188,7 @@

     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 @@

         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 @@

           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]){