diff options
Diffstat (limited to 'third_party/aom/aom_dsp/prob.c')
| -rw-r--r-- | third_party/aom/aom_dsp/prob.c | 236 |
1 files changed, 236 insertions, 0 deletions
diff --git a/third_party/aom/aom_dsp/prob.c b/third_party/aom/aom_dsp/prob.c new file mode 100644 index 000000000..c60bfdac5 --- /dev/null +++ b/third_party/aom/aom_dsp/prob.c @@ -0,0 +1,236 @@ +/* + * Copyright (c) 2016, Alliance for Open Media. All rights reserved + * + * This source code is subject to the terms of the BSD 2 Clause License and + * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License + * was not distributed with this source code in the LICENSE file, you can + * obtain it at www.aomedia.org/license/software. If the Alliance for Open + * Media Patent License 1.0 was not distributed with this source code in the + * PATENTS file, you can obtain it at www.aomedia.org/license/patent. + */ + +#include "./aom_config.h" + +#if CONFIG_EC_MULTISYMBOL +#include <string.h> +#endif + +#include "aom_dsp/prob.h" + +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, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 +}; + +static unsigned int tree_merge_probs_impl(unsigned int i, + const aom_tree_index *tree, + const aom_prob *pre_probs, + const unsigned int *counts, + aom_prob *probs) { + const int l = tree[i]; + const unsigned int left_count = + (l <= 0) ? counts[-l] + : tree_merge_probs_impl(l, tree, pre_probs, counts, probs); + const int r = tree[i + 1]; + const unsigned int right_count = + (r <= 0) ? counts[-r] + : tree_merge_probs_impl(r, tree, pre_probs, counts, probs); + const unsigned int ct[2] = { left_count, right_count }; + probs[i >> 1] = mode_mv_merge_probs(pre_probs[i >> 1], ct); + return left_count + right_count; +} + +void aom_tree_merge_probs(const aom_tree_index *tree, const aom_prob *pre_probs, + const unsigned int *counts, aom_prob *probs) { + tree_merge_probs_impl(0, tree, pre_probs, counts, probs); +} + +#if CONFIG_EC_MULTISYMBOL +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; + aom_cdf_prob 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 < AOMMIN(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 aom_cdf_prob tree_node_compute_probs(tree_node *tree, int n, + aom_cdf_prob 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) { + aom_cdf_prob lp; + aom_cdf_prob 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 { + aom_cdf_prob rp; + aom_cdf_prob 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, + aom_cdf_prob *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, aom_cdf_prob *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, CDF_PROB_TOP); + /* Extract the cdf, index, path and length */ + tree_node_extract(symb, 0, 0, cdf, index, path, len); + /* Convert to CDF */ + cdf[0] = AOM_ICDF(cdf[0]); + for (i = 1; i < nsymbs; i++) { + cdf[i] = AOM_ICDF(AOM_ICDF(cdf[i - 1]) + cdf[i]); + } +// Store symbol count at the end of the CDF +#if CONFIG_EC_ADAPT + cdf[nsymbs] = 0; +#endif + return nsymbs; +} + +/* This code assumes that tree contains as unique leaf nodes the integer values + 0 to len - 1 and produces the forward and inverse mapping tables in ind[] + and inv[] respectively. */ +static void tree_to_index(int *stack_index, int *ind, int *inv, + const aom_tree_index *tree, int value, int index) { + value *= 2; + + do { + const aom_tree_index content = tree[index]; + ++index; + if (content <= 0) { + inv[*stack_index] = -content; + ind[-content] = *stack_index; + ++(*stack_index); + } else { + tree_to_index(stack_index, ind, inv, tree, value, content); + } + } while (++value & 1); +} + +void av1_indices_from_tree(int *ind, int *inv, const aom_tree_index *tree) { + int stack_index = 0; + tree_to_index(&stack_index, ind, inv, tree, 0, 0); +} +#endif |