Line data Source code
1 : /*
2 : * Copyright (c) 2016, Alliance for Open Media. All rights reserved
3 : *
4 : * This source code is subject to the terms of the BSD 2 Clause License and
5 : * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
6 : * was not distributed with this source code in the LICENSE file, you can
7 : * obtain it at www.aomedia.org/license/software. If the Alliance for Open
8 : * Media Patent License 1.0 was not distributed with this source code in the
9 : * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
10 : */
11 :
12 : #include "./aom_config.h"
13 :
14 : #include <string.h>
15 :
16 : #include "aom_dsp/prob.h"
17 :
18 0 : static unsigned int tree_merge_probs_impl(unsigned int i,
19 : const aom_tree_index *tree,
20 : const aom_prob *pre_probs,
21 : const unsigned int *counts,
22 : aom_prob *probs) {
23 0 : const int l = tree[i];
24 0 : const unsigned int left_count =
25 0 : (l <= 0) ? counts[-l]
26 0 : : tree_merge_probs_impl(l, tree, pre_probs, counts, probs);
27 0 : const int r = tree[i + 1];
28 0 : const unsigned int right_count =
29 0 : (r <= 0) ? counts[-r]
30 0 : : tree_merge_probs_impl(r, tree, pre_probs, counts, probs);
31 0 : const unsigned int ct[2] = { left_count, right_count };
32 0 : probs[i >> 1] = mode_mv_merge_probs(pre_probs[i >> 1], ct);
33 0 : return left_count + right_count;
34 : }
35 :
36 0 : void aom_tree_merge_probs(const aom_tree_index *tree, const aom_prob *pre_probs,
37 : const unsigned int *counts, aom_prob *probs) {
38 0 : tree_merge_probs_impl(0, tree, pre_probs, counts, probs);
39 0 : }
40 :
41 : typedef struct tree_node tree_node;
42 :
43 : struct tree_node {
44 : aom_tree_index index;
45 : uint8_t probs[16];
46 : uint8_t prob;
47 : int path;
48 : int len;
49 : int l;
50 : int r;
51 : aom_cdf_prob pdf;
52 : };
53 :
54 : /* Compute the probability of this node in Q23 */
55 0 : static uint32_t tree_node_prob(tree_node n, int i) {
56 : uint32_t prob;
57 : /* 1.0 in Q23 */
58 0 : prob = 16777216;
59 0 : for (; i < n.len; i++) {
60 0 : prob = prob * n.probs[i] >> 8;
61 : }
62 0 : return prob;
63 : }
64 :
65 0 : static int tree_node_cmp(tree_node a, tree_node b) {
66 : int i;
67 : uint32_t pa;
68 : uint32_t pb;
69 0 : for (i = 0; i < AOMMIN(a.len, b.len) && a.probs[i] == b.probs[i]; i++) {
70 : }
71 0 : pa = tree_node_prob(a, i);
72 0 : pb = tree_node_prob(b, i);
73 0 : return pa > pb ? 1 : pa < pb ? -1 : 0;
74 : }
75 :
76 : /* Given a Q15 probability for symbol subtree rooted at tree[n], this function
77 : computes the probability of each symbol (defined as a node that has no
78 : children). */
79 0 : static aom_cdf_prob tree_node_compute_probs(tree_node *tree, int n,
80 : aom_cdf_prob pdf) {
81 0 : if (tree[n].l == 0) {
82 : /* This prevents probability computations in Q15 that underflow from
83 : producing a symbol that has zero probability. */
84 0 : if (pdf == 0) pdf = 1;
85 0 : tree[n].pdf = pdf;
86 0 : return pdf;
87 : } else {
88 : /* We process the smaller probability first, */
89 0 : if (tree[n].prob < 128) {
90 : aom_cdf_prob lp;
91 : aom_cdf_prob rp;
92 0 : lp = (((uint32_t)pdf) * tree[n].prob + 128) >> 8;
93 0 : lp = tree_node_compute_probs(tree, tree[n].l, lp);
94 0 : rp = tree_node_compute_probs(tree, tree[n].r, lp > pdf ? 0 : pdf - lp);
95 0 : return lp + rp;
96 : } else {
97 : aom_cdf_prob rp;
98 : aom_cdf_prob lp;
99 0 : rp = (((uint32_t)pdf) * (256 - tree[n].prob) + 128) >> 8;
100 0 : rp = tree_node_compute_probs(tree, tree[n].r, rp);
101 0 : lp = tree_node_compute_probs(tree, tree[n].l, rp > pdf ? 0 : pdf - rp);
102 0 : return lp + rp;
103 : }
104 : }
105 : }
106 :
107 0 : static int tree_node_extract(tree_node *tree, int n, int symb,
108 : aom_cdf_prob *pdf, aom_tree_index *index,
109 : int *path, int *len) {
110 0 : if (tree[n].l == 0) {
111 0 : pdf[symb] = tree[n].pdf;
112 0 : if (index != NULL) index[symb] = tree[n].index;
113 0 : if (path != NULL) path[symb] = tree[n].path;
114 0 : if (len != NULL) len[symb] = tree[n].len;
115 0 : return symb + 1;
116 : } else {
117 0 : symb = tree_node_extract(tree, tree[n].l, symb, pdf, index, path, len);
118 0 : return tree_node_extract(tree, tree[n].r, symb, pdf, index, path, len);
119 : }
120 : }
121 :
122 0 : int tree_to_cdf(const aom_tree_index *tree, const aom_prob *probs,
123 : aom_tree_index root, aom_cdf_prob *cdf, aom_tree_index *index,
124 : int *path, int *len) {
125 : tree_node symb[2 * 16 - 1];
126 : int nodes;
127 : int next[16];
128 : int size;
129 : int nsymbs;
130 : int i;
131 : /* Create the root node with probability 1 in Q15. */
132 0 : symb[0].index = root;
133 0 : symb[0].path = 0;
134 0 : symb[0].len = 0;
135 0 : symb[0].l = symb[0].r = 0;
136 0 : nodes = 1;
137 0 : next[0] = 0;
138 0 : size = 1;
139 0 : nsymbs = 1;
140 0 : while (size > 0 && nsymbs < 16) {
141 : int m;
142 : tree_node n;
143 : aom_tree_index j;
144 : uint8_t prob;
145 0 : m = 0;
146 : /* Find the internal node with the largest probability. */
147 0 : for (i = 1; i < size; i++) {
148 0 : if (tree_node_cmp(symb[next[i]], symb[next[m]]) > 0) m = i;
149 : }
150 0 : i = next[m];
151 0 : memmove(&next[m], &next[m + 1], sizeof(*next) * (size - (m + 1)));
152 0 : size--;
153 : /* Split this symbol into two symbols */
154 0 : n = symb[i];
155 0 : j = n.index;
156 0 : prob = probs[j >> 1];
157 : /* Left */
158 0 : n.index = tree[j];
159 0 : n.path <<= 1;
160 0 : n.len++;
161 0 : n.probs[n.len - 1] = prob;
162 0 : symb[nodes] = n;
163 0 : if (n.index > 0) {
164 0 : next[size++] = nodes;
165 : }
166 : /* Right */
167 0 : n.index = tree[j + 1];
168 0 : n.path += 1;
169 0 : n.probs[n.len - 1] = 256 - prob;
170 0 : symb[nodes + 1] = n;
171 0 : if (n.index > 0) {
172 0 : next[size++] = nodes + 1;
173 : }
174 0 : symb[i].prob = prob;
175 0 : symb[i].l = nodes;
176 0 : symb[i].r = nodes + 1;
177 0 : nodes += 2;
178 0 : nsymbs++;
179 : }
180 : /* Compute the probabilities of each symbol in Q15 */
181 0 : tree_node_compute_probs(symb, 0, CDF_PROB_TOP);
182 : /* Extract the cdf, index, path and length */
183 0 : tree_node_extract(symb, 0, 0, cdf, index, path, len);
184 : /* Convert to CDF */
185 0 : cdf[0] = AOM_ICDF(cdf[0]);
186 0 : for (i = 1; i < nsymbs; i++) {
187 0 : cdf[i] = AOM_ICDF(AOM_ICDF(cdf[i - 1]) + cdf[i]);
188 : }
189 : // Store symbol count at the end of the CDF
190 : #if CONFIG_EC_ADAPT
191 0 : cdf[nsymbs] = 0;
192 : #endif
193 0 : return nsymbs;
194 : }
195 :
196 : /* This code assumes that tree contains as unique leaf nodes the integer values
197 : 0 to len - 1 and produces the forward and inverse mapping tables in ind[]
198 : and inv[] respectively. */
199 0 : static void tree_to_index(int *stack_index, int *ind, int *inv,
200 : const aom_tree_index *tree, int value, int index) {
201 0 : value *= 2;
202 :
203 : do {
204 0 : const aom_tree_index content = tree[index];
205 0 : ++index;
206 0 : if (content <= 0) {
207 0 : inv[*stack_index] = -content;
208 0 : ind[-content] = *stack_index;
209 0 : ++(*stack_index);
210 : } else {
211 0 : tree_to_index(stack_index, ind, inv, tree, value, content);
212 : }
213 0 : } while (++value & 1);
214 0 : }
215 :
216 0 : void av1_indices_from_tree(int *ind, int *inv, const aom_tree_index *tree) {
217 0 : int stack_index = 0;
218 0 : tree_to_index(&stack_index, ind, inv, tree, 0, 0);
219 0 : }
|
