Use Daala entropy coder to code trees.
When building with --enable-daala_ec, calls to aom_write_tree() and
aom_read_tree() will convert a aom_tree_index structure with associated
aom_prob probabilities into a CDF on the fly for use with the
od_ec_encode_cdf_q15().
The number of symbols in the CDF is capped at 16, and trees that contain
more than 16 leaf nodes are handled by splitting the most likely, e.g.,
highest probability symbols, first and coding multiple symbols if
necessary.
ntt-short-1:
MEDIUM (%) HIGH (%)
PSNR 0.000227 0.000213
PSNRHVS 0.000215 0.000205
SSIM 0.000229 0.000209
FASTSSIM 0.000229 0.000214
subset1:
RATE (%) DSNR (dB)
PSNR -0.00026 0.00002
PSNRHVS -0.00026 0.00002
SSIM -0.00026 0.00001
FASTSSIM -0.00026 0.00001
Change-Id: Icb1a8cb854fd81fdd88fbe4bc6761c7eb4757dfe
diff --git a/aom_dsp/bitreader.h b/aom_dsp/bitreader.h
index 9f06d69..74d529c 100644
--- a/aom_dsp/bitreader.h
+++ b/aom_dsp/bitreader.h
@@ -94,7 +94,11 @@
static INLINE int aom_read_tree(aom_reader *r, const aom_tree_index *tree,
const aom_prob *probs) {
+#if CONFIG_DAALA_EC
+ return daala_read_tree_bits(r, tree, probs);
+#else
return aom_read_tree_bits(r, tree, probs);
+#endif
}
#ifdef __cplusplus
diff --git a/aom_dsp/bitwriter.h b/aom_dsp/bitwriter.h
index d992e6c..e650c97 100644
--- a/aom_dsp/bitwriter.h
+++ b/aom_dsp/bitwriter.h
@@ -77,7 +77,11 @@
static INLINE void aom_write_tree(aom_writer *w, const aom_tree_index *tree,
const aom_prob *probs, int bits, int len,
aom_tree_index i) {
+#if CONFIG_DAALA_EC
+ daala_write_tree_bits(w, tree, probs, bits, len, i);
+#else
aom_write_tree_bits(w, tree, probs, bits, len, i);
+#endif
}
#ifdef __cplusplus
diff --git a/aom_dsp/daalaboolreader.h b/aom_dsp/daalaboolreader.h
index c15f749..3ccea1d 100644
--- a/aom_dsp/daalaboolreader.h
+++ b/aom_dsp/daalaboolreader.h
@@ -47,6 +47,25 @@
return r->ec.error;
}
+static INLINE int daala_read_tree_bits(daala_reader *r,
+ const aom_tree_index *tree,
+ const aom_prob *probs) {
+ aom_tree_index i = 0;
+ do {
+ uint16_t cdf[16];
+ aom_tree_index index[16];
+ int path[16];
+ int dist[16];
+ int nsymbs;
+ int symb;
+ nsymbs = tree_to_cdf(tree, probs, i, cdf, index, path, dist);
+ symb = od_ec_decode_cdf_q15(&r->ec, cdf, nsymbs, "aom");
+ OD_ASSERT(symb >= 0 && symb < nsymbs);
+ i = index[symb];
+ } while (i > 0);
+ return -i;
+}
+
#ifdef __cplusplus
} // extern "C"
#endif
diff --git a/aom_dsp/daalaboolwriter.h b/aom_dsp/daalaboolwriter.h
index 250ec62..f9102f0 100644
--- a/aom_dsp/daalaboolwriter.h
+++ b/aom_dsp/daalaboolwriter.h
@@ -13,6 +13,7 @@
#define AOM_DSP_DAALABOOLWRITER_H_
#include "aom_dsp/entenc.h"
+#include "aom_dsp/prob.h"
#ifdef __cplusplus
extern "C" {
@@ -38,6 +39,45 @@
}
}
+static INLINE void daala_write_tree_bits(daala_writer *w,
+ const aom_tree_index *tree,
+ const aom_prob *probs, int bits,
+ int len, aom_tree_index i) {
+ aom_tree_index root;
+ root = i;
+ do {
+ uint16_t cdf[16];
+ aom_tree_index index[16];
+ int path[16];
+ int dist[16];
+ int nsymbs;
+ int symb;
+ int j;
+ /* Compute the CDF of the binary tree using the given probabilities. */
+ nsymbs = tree_to_cdf(tree, probs, root, cdf, index, path, dist);
+ /* Find the symbol to code. */
+ symb = -1;
+ for (j = 0; j < nsymbs; j++) {
+ /* If this symbol codes a leaf node, */
+ if (index[j] <= 0) {
+ if (len == dist[j] && path[j] == bits) {
+ symb = j;
+ break;
+ }
+ } else {
+ if (len > dist[j] && path[j] == bits >> (len - dist[j])) {
+ symb = j;
+ break;
+ }
+ }
+ }
+ OD_ASSERT(symb != -1);
+ od_ec_encode_cdf_q15(&w->ec, symb, cdf, nsymbs);
+ bits &= (1 << (len - dist[symb])) - 1;
+ len -= dist[symb];
+ } while (len);
+}
+
#ifdef __cplusplus
} // extern "C"
#endif
diff --git a/aom_dsp/prob.c b/aom_dsp/prob.c
index 20c82c6..3485929 100644
--- a/aom_dsp/prob.c
+++ b/aom_dsp/prob.c
@@ -9,8 +9,16 @@
* PATENTS file, you can obtain it at www.aomedia.org/license/patent.
*/
+#if CONFIG_DAALA_EC
+#include <string.h>
+#endif
+
#include "aom_dsp/prob.h"
+#if CONFIG_DAALA_EC
+#include "aom_dsp/entcode.h"
+#endif
+
const uint8_t aom_norm[256] = {
0, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
@@ -46,3 +54,153 @@
const unsigned int *counts, aom_prob *probs) {
tree_merge_probs_impl(0, tree, pre_probs, counts, probs);
}
+
+#if CONFIG_DAALA_EC
+typedef struct tree_node tree_node;
+
+struct tree_node {
+ aom_tree_index index;
+ uint8_t probs[16];
+ uint8_t prob;
+ int path;
+ int len;
+ int l;
+ int r;
+ uint16_t pdf;
+};
+
+/* Compute the probability of this node in Q23 */
+static uint32_t tree_node_prob(tree_node n, int i) {
+ uint32_t prob;
+ /* 1.0 in Q23 */
+ prob = 16777216;
+ for (; i < n.len; i++) {
+ prob = prob * n.probs[i] >> 8;
+ }
+ return prob;
+}
+
+static int tree_node_cmp(tree_node a, tree_node b) {
+ int i;
+ uint32_t pa;
+ uint32_t pb;
+ for (i = 0; i < OD_MINI(a.len, b.len) && a.probs[i] == b.probs[i]; i++) {
+ }
+ pa = tree_node_prob(a, i);
+ pb = tree_node_prob(b, i);
+ return pa > pb ? 1 : pa < pb ? -1 : 0;
+}
+
+/* Given a Q15 probability for symbol subtree rooted at tree[n], this function
+ computes the probability of each symbol (defined as a node that has no
+ children). */
+static uint16_t tree_node_compute_probs(tree_node *tree, int n, uint16_t pdf) {
+ if (tree[n].l == 0) {
+ /* This prevents probability computations in Q15 that underflow from
+ producing a symbol that has zero probability. */
+ if (pdf == 0) pdf = 1;
+ tree[n].pdf = pdf;
+ return pdf;
+ } else {
+ /* We process the smaller probability first, */
+ if (tree[n].prob < 128) {
+ uint16_t lp;
+ uint16_t rp;
+ lp = (((uint32_t)pdf) * tree[n].prob + 128) >> 8;
+ lp = tree_node_compute_probs(tree, tree[n].l, lp);
+ rp = tree_node_compute_probs(tree, tree[n].r, lp > pdf ? 0 : pdf - lp);
+ return lp + rp;
+ } else {
+ uint16_t rp;
+ uint16_t lp;
+ rp = (((uint32_t)pdf) * (256 - tree[n].prob) + 128) >> 8;
+ rp = tree_node_compute_probs(tree, tree[n].r, rp);
+ lp = tree_node_compute_probs(tree, tree[n].l, rp > pdf ? 0 : pdf - rp);
+ return lp + rp;
+ }
+ }
+}
+
+static int tree_node_extract(tree_node *tree, int n, int symb, uint16_t *pdf,
+ aom_tree_index *index, int *path, int *len) {
+ if (tree[n].l == 0) {
+ pdf[symb] = tree[n].pdf;
+ if (index != NULL) index[symb] = tree[n].index;
+ if (path != NULL) path[symb] = tree[n].path;
+ if (len != NULL) len[symb] = tree[n].len;
+ return symb + 1;
+ } else {
+ symb = tree_node_extract(tree, tree[n].l, symb, pdf, index, path, len);
+ return tree_node_extract(tree, tree[n].r, symb, pdf, index, path, len);
+ }
+}
+
+int tree_to_cdf(const aom_tree_index *tree, const aom_prob *probs,
+ aom_tree_index root, uint16_t *cdf, aom_tree_index *index,
+ int *path, int *len) {
+ tree_node symb[2 * 16 - 1];
+ int nodes;
+ int next[16];
+ int size;
+ int nsymbs;
+ int i;
+ /* Create the root node with probability 1 in Q15. */
+ symb[0].index = root;
+ symb[0].path = 0;
+ symb[0].len = 0;
+ symb[0].l = symb[0].r = 0;
+ nodes = 1;
+ next[0] = 0;
+ size = 1;
+ nsymbs = 1;
+ while (size > 0 && nsymbs < 16) {
+ int m;
+ tree_node n;
+ aom_tree_index j;
+ uint8_t prob;
+ m = 0;
+ /* Find the internal node with the largest probability. */
+ for (i = 1; i < size; i++) {
+ if (tree_node_cmp(symb[next[i]], symb[next[m]]) > 0) m = i;
+ }
+ i = next[m];
+ memmove(&next[m], &next[m + 1], sizeof(*next) * (size - (m + 1)));
+ size--;
+ /* Split this symbol into two symbols */
+ n = symb[i];
+ j = n.index;
+ prob = probs[j >> 1];
+ /* Left */
+ n.index = tree[j];
+ n.path <<= 1;
+ n.len++;
+ n.probs[n.len - 1] = prob;
+ symb[nodes] = n;
+ if (n.index > 0) {
+ next[size++] = nodes;
+ }
+ /* Right */
+ n.index = tree[j + 1];
+ n.path += 1;
+ n.probs[n.len - 1] = 256 - prob;
+ symb[nodes + 1] = n;
+ if (n.index > 0) {
+ next[size++] = nodes + 1;
+ }
+ symb[i].prob = prob;
+ symb[i].l = nodes;
+ symb[i].r = nodes + 1;
+ nodes += 2;
+ nsymbs++;
+ }
+ /* Compute the probabilities of each symbol in Q15 */
+ tree_node_compute_probs(symb, 0, 32768);
+ /* Extract the cdf, index, path and length */
+ tree_node_extract(symb, 0, 0, cdf, index, path, len);
+ /* Convert to CDF */
+ for (i = 1; i < nsymbs; i++) {
+ cdf[i] = cdf[i - 1] + cdf[i];
+ }
+ return nsymbs;
+}
+#endif
diff --git a/aom_dsp/prob.h b/aom_dsp/prob.h
index 24aa6e9..66af5d5 100644
--- a/aom_dsp/prob.h
+++ b/aom_dsp/prob.h
@@ -93,6 +93,12 @@
void aom_tree_merge_probs(const aom_tree_index *tree, const aom_prob *pre_probs,
const unsigned int *counts, aom_prob *probs);
+#if CONFIG_DAALA_EC
+int tree_to_cdf(const aom_tree_index *tree, const aom_prob *probs,
+ aom_tree_index root, uint16_t *cdf, aom_tree_index *ind,
+ int *pth, int *len);
+#endif
+
DECLARE_ALIGNED(16, extern const uint8_t, aom_norm[256]);
#ifdef __cplusplus
diff --git a/av1/encoder/bitstream.c b/av1/encoder/bitstream.c
index d7c8ac1..848c3f0 100644
--- a/av1/encoder/bitstream.c
+++ b/av1/encoder/bitstream.c
@@ -336,12 +336,13 @@
if (t >= TWO_TOKEN && t < EOB_TOKEN) {
int len = UNCONSTRAINED_NODES - p->skip_eob_node;
int bits = v >> (n - len);
- aom_write_tree(w, av1_coef_tree, p->context_tree, bits, len, i);
+ aom_write_tree_bits(w, av1_coef_tree, p->context_tree, bits, len, i);
+ v &= (1 << (n - len)) - 1;
aom_write_tree(w, av1_coef_con_tree,
av1_pareto8_full[p->context_tree[PIVOT_NODE] - 1], v,
n - len, 0);
} else {
- aom_write_tree(w, av1_coef_tree, p->context_tree, v, n, i);
+ aom_write_tree_bits(w, av1_coef_tree, p->context_tree, v, n, i);
}
if (b->base_val) {
