Import aom library

This is the reference implementation for the Alliance for Open Media's av1 video code.

The commit used was 4d668d7feb1f8abd809d1bca0418570a7f142a36.

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