Adds a generic adaptation scheme based on the Q15 entropy coder
authorJean-Marc Valin <jmvalin@jmvalin.ca>
Fri, 15 Apr 2016 06:59:37 +0000 (02:59 -0400)
committerJean-Marc Valin <jmvalin@jmvalin.ca>
Fri, 15 Apr 2016 18:13:46 +0000 (14:13 -0400)
This first version is designed to behave as close as possible to the non-Q15
od_{en,de}code_cdf_adapt() functions.

src/generic_code.c
src/generic_code.h
src/generic_decoder.c
src/generic_encoder.c

index ed8280c..de63f70 100644 (file)
@@ -38,6 +38,40 @@ void od_cdf_init(uint16_t *cdf, int ncdfs, int nsyms, int val, int first) {
   }
 }
 
+/** Adapts a Q15 cdf after encoding/decoding a symbol. The total frequency
+    count on input and output (cdf[n - 1]) must be equal to (32768 - n)
+    so that we can add a floor probability of 1. */
+void od_cdf_adapt_q15(int val, uint16_t *cdf, int n, int *count, int rate) {
+  int i;
+  *count = OD_MINI(*count + 1, 1 << rate);
+  OD_ASSERT(cdf[n - 1] == 32768);
+  /* Remove probability floor for adaptation. */
+  for (i = 0; i < n; i++) cdf[i] -= (i + 1);
+  if (*count >= 1 << rate) {
+    /* Steady-state adaptation based on a simple IIR with dyadic rate. */
+    for (i = 0; i < n; i++) {
+      int tmp;
+      tmp = (32768 - n)*(i >= val);
+      cdf[i] -= ((cdf[i] - tmp) + (1 << rate >> 1)) >> rate;
+    }
+  }
+  else {
+    int alpha;
+    /* Initial adaptation for the first symbols. The adaptation rate is
+       computed to be equivalent to what od_{en,de}code_cdf_adapt() does
+       when the initial cdf is set to increment/4. */
+    alpha = 4*32768/(n + 4**count);
+    for (i = 0; i < n; i++) {
+      int tmp;
+      tmp = (32768 - n)*(i >= val);
+      cdf[i] -= ((cdf[i] - tmp)*alpha + 16384) >> 15;
+    }
+  }
+  /* Add back the probability floor. */
+  for (i = 0; i < n; i++) cdf[i] += (i + 1);
+  OD_ASSERT(cdf[n - 1] == 32768);
+}
+
 /** Initializes the cdfs and freq counts for a model.
  *
  * @param [out] model model being initialized
index 0228926..666a628 100644 (file)
@@ -32,9 +32,11 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*/
 
 #if OD_ACCOUNTING
 # define generic_decode(dec, model, max, ex_q16, integration, str) generic_decode_(dec, model, max, ex_q16, integration, str)
+# define od_decode_cdf_adapt_q15(ec, cdf, n, count, rate, str) od_decode_cdf_adapt_q15_(ec, cdf, n, count, rate, str)
 # define od_decode_cdf_adapt(ec, cdf, n, increment, str) od_decode_cdf_adapt_(ec, cdf, n, increment, str)
 #else
 # define generic_decode(dec, model, max, ex_q16, integration, str) generic_decode_(dec, model, max, ex_q16, integration)
+# define od_decode_cdf_adapt_q15(ec, cdf, n, count, rate, str) od_decode_cdf_adapt_q15_(ec, cdf, n, count, rate)
 # define od_decode_cdf_adapt(ec, cdf, n, increment, str) od_decode_cdf_adapt_(ec, cdf, n, increment)
 #endif
 
@@ -63,6 +65,11 @@ void generic_model_init(generic_encoder *model);
 
 void od_cdf_init(uint16_t *cdf, int ncdfs, int nsyms, int val, int first);
 
+void od_cdf_adapt_q15(int val, uint16_t *cdf, int n, int *count, int rate);
+
+void od_encode_cdf_adapt_q15(od_ec_enc *ec, int val, uint16_t *cdf, int n,
+ int *count, int rate);
+
 void od_encode_cdf_adapt(od_ec_enc *ec, int val, uint16_t *cdf, int n,
  int increment);
 
@@ -76,6 +83,9 @@ double generic_encode_cost(generic_encoder *model, int x, int max,
 
 double od_encode_cdf_cost(int val, uint16_t *cdf, int n);
 
+int od_decode_cdf_adapt_q15_(od_ec_dec *ec, uint16_t *cdf, int n,
+ int *count, int rate OD_ACC_STR);
+
 int generic_decode_(od_ec_dec *dec, generic_encoder *model, int max,
  int *ex_q16, int integration OD_ACC_STR);
 
index 17667cd..dcee5b8 100644 (file)
@@ -38,6 +38,32 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*/
  * the cdf accordingly.
  *
  * @param [in,out] enc   range encoder
+ * @param [in,out] cdf   CDF of the variable (Q15)
+ * @param [in]     n     number of values possible
+ * @param [in,out] count number of symbols encoded with that cdf so far
+ * @param [in]     rate  adaptation rate shift (smaller is faster)
+ * @return decoded variable
+ */
+int od_decode_cdf_adapt_q15_(od_ec_dec *ec, uint16_t *cdf, int n,
+ int *count, int rate OD_ACC_STR) {
+  int val;
+  int i;
+  if (*count == 0) {
+    int ft;
+    ft = cdf[n - 1];
+    for (i = 0; i < n; i++) {
+      cdf[i] = cdf[i]*32768/ft;
+    }
+  }
+  val = od_ec_decode_cdf_q15(ec, cdf, n, acc_str);
+  od_cdf_adapt_q15(val, cdf, n, count, rate);
+  return val;
+}
+
+/** Decodes a value from 0 to N-1 (with N up to 16) based on a cdf and adapts
+ * the cdf accordingly.
+ *
+ * @param [in,out] enc   range encoder
  * @param [in]     cdf   CDF of the variable (Q15)
  * @param [in]     n     number of values possible
  * @param [in]     increment adaptation speed (Q15)
index 166aa4b..63a073b 100644 (file)
@@ -40,6 +40,33 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*/
  *
  * @param [in,out] enc   range encoder
  * @param [in]     val   variable being encoded
+ * @param [in,out] cdf   CDF of the variable (Q15)
+ * @param [in]     n     number of values possible
+ * @param [in,out] count number of symbols encoded with that cdf so far
+ * @param [in]     rate  adaptation rate shift (smaller is faster)
+ */
+void od_encode_cdf_adapt_q15(od_ec_enc *ec, int val, uint16_t *cdf, int n,
+ int *count, int rate) {
+  int i;
+  if (*count == 0) {
+    /* On the first call, we normalize the cdf to (32768 - n). This should
+       eventually be moved to the state init, but for now it makes it much
+       easier to experiment and convert symbols to the Q15 adaptation.*/
+    int ft;
+    ft = cdf[n - 1];
+    for (i = 0; i < n; i++) {
+      cdf[i] = cdf[i]*32768/ft;
+    }
+  }
+  od_ec_encode_cdf_q15(ec, val, cdf, n);
+  od_cdf_adapt_q15(val, cdf, n, count, rate);
+}
+
+/** Encodes a value from 0 to N-1 (with N up to 16) based on a cdf and adapts
+ * the cdf accordingly.
+ *
+ * @param [in,out] enc   range encoder
+ * @param [in]     val   variable being encoded
  * @param [in]     cdf   CDF of the variable (Q15)
  * @param [in]     n     number of values possible
  * @param [in]     increment adaptation speed (Q15)