summaryrefslogtreecommitdiffstats
path: root/third_party/aom/aom_dsp/prob.c
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/aom/aom_dsp/prob.c')
-rw-r--r--third_party/aom/aom_dsp/prob.c217
1 files changed, 0 insertions, 217 deletions
diff --git a/third_party/aom/aom_dsp/prob.c b/third_party/aom/aom_dsp/prob.c
deleted file mode 100644
index a42fb806b..000000000
--- a/third_party/aom/aom_dsp/prob.c
+++ /dev/null
@@ -1,217 +0,0 @@
-/*
- * 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"
-
-#include <string.h>
-
-#include "aom_dsp/prob.h"
-
-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);
-}
-
-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
- cdf[nsymbs] = 0;
- 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);
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-20 02:41:28 +0000