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 #ifndef AOM_DSP_PROB_H_
13 #define AOM_DSP_PROB_H_
14
15 #include <assert.h>
16
17 #include "./aom_config.h"
18 #include "./aom_dsp_common.h"
19
20 #include "aom_ports/bitops.h"
21 #include "aom_ports/mem.h"
22
23 #if !CONFIG_ANS
24 #include "aom_dsp/entcode.h"
25 #endif
26
27 #ifdef __cplusplus
28 extern "C" {
29 #endif
30
31 typedef uint8_t aom_prob;
32
33 // TODO(negge): Rename this aom_prob once we remove vpxbool.
34 typedef uint16_t aom_cdf_prob;
35
36 #define CDF_SIZE(x) ((x) + 1)
37
38 #define CDF_PROB_BITS 15
39 #define CDF_PROB_TOP (1 << CDF_PROB_BITS)
40
41 #if !CONFIG_ANS
42 #define AOM_ICDF OD_ICDF
43 #else
44 #define AOM_ICDF(x) (x)
45 #endif
46
47 #define MAX_PROB 255
48
49 #define LV_MAP_PROB 1
50
51 #define BR_NODE 1
52
53 #if CONFIG_ADAPT_SCAN
54 #define CACHE_SCAN_PROB 1
55 #endif
56
57 #define aom_prob_half ((aom_prob)128)
58
59 typedef int8_t aom_tree_index;
60
61 #define TREE_SIZE(leaf_count) (-2 + 2 * (leaf_count))
62
63 #define MODE_MV_COUNT_SAT 20
64
65 /* We build coding trees compactly in arrays.
66 Each node of the tree is a pair of aom_tree_indices.
67 Array index often references a corresponding probability table.
68 Index <= 0 means done encoding/decoding and value = -Index,
69 Index > 0 means need another bit, specification at index.
70 Nonnegative indices are always even; processing begins at node 0. */
71
72 typedef const aom_tree_index aom_tree[];
73
get_prob(unsigned int num,unsigned int den)74 static INLINE aom_prob get_prob(unsigned int num, unsigned int den) {
75 assert(den != 0);
76 {
77 const int p = (int)(((uint64_t)num * 256 + (den >> 1)) / den);
78 // (p > 255) ? 255 : (p < 1) ? 1 : p;
79 const int clipped_prob = p | ((255 - p) >> 23) | (p == 0);
80 return (aom_prob)clipped_prob;
81 }
82 }
83
get_binary_prob(unsigned int n0,unsigned int n1)84 static INLINE aom_prob get_binary_prob(unsigned int n0, unsigned int n1) {
85 const unsigned int den = n0 + n1;
86 if (den == 0) return 128u;
87 return get_prob(n0, den);
88 }
89
90 /* This function assumes prob1 and prob2 are already within [1,255] range. */
weighted_prob(int prob1,int prob2,int factor)91 static INLINE aom_prob weighted_prob(int prob1, int prob2, int factor) {
92 return ROUND_POWER_OF_TWO(prob1 * (256 - factor) + prob2 * factor, 8);
93 }
94
merge_probs(aom_prob pre_prob,const unsigned int ct[2],unsigned int count_sat,unsigned int max_update_factor)95 static INLINE aom_prob merge_probs(aom_prob pre_prob, const unsigned int ct[2],
96 unsigned int count_sat,
97 unsigned int max_update_factor) {
98 const aom_prob prob = get_binary_prob(ct[0], ct[1]);
99 const unsigned int count = AOMMIN(ct[0] + ct[1], count_sat);
100 const unsigned int factor = max_update_factor * count / count_sat;
101 return weighted_prob(pre_prob, prob, factor);
102 }
103
104 // MODE_MV_MAX_UPDATE_FACTOR (128) * count / MODE_MV_COUNT_SAT;
105 static const int count_to_update_factor[MODE_MV_COUNT_SAT + 1] = {
106 0, 6, 12, 19, 25, 32, 38, 44, 51, 57, 64,
107 70, 76, 83, 89, 96, 102, 108, 115, 121, 128
108 };
109
mode_mv_merge_probs(aom_prob pre_prob,const unsigned int ct[2])110 static INLINE aom_prob mode_mv_merge_probs(aom_prob pre_prob,
111 const unsigned int ct[2]) {
112 const unsigned int den = ct[0] + ct[1];
113 if (den == 0) {
114 return pre_prob;
115 } else {
116 const unsigned int count = AOMMIN(den, MODE_MV_COUNT_SAT);
117 const unsigned int factor = count_to_update_factor[count];
118 const aom_prob prob = get_prob(ct[0], den);
119 return weighted_prob(pre_prob, prob, factor);
120 }
121 }
122
123 void aom_tree_merge_probs(const aom_tree_index *tree, const aom_prob *pre_probs,
124 const unsigned int *counts, aom_prob *probs);
125
126 int tree_to_cdf(const aom_tree_index *tree, const aom_prob *probs,
127 aom_tree_index root, aom_cdf_prob *cdf, aom_tree_index *ind,
128 int *pth, int *len);
129
av1_tree_to_cdf(const aom_tree_index * tree,const aom_prob * probs,aom_cdf_prob * cdf)130 static INLINE void av1_tree_to_cdf(const aom_tree_index *tree,
131 const aom_prob *probs, aom_cdf_prob *cdf) {
132 aom_tree_index index[16];
133 int path[16];
134 int dist[16];
135 tree_to_cdf(tree, probs, 0, cdf, index, path, dist);
136 }
137
138 #define av1_tree_to_cdf_1D(tree, probs, cdf, u) \
139 do { \
140 int i; \
141 for (i = 0; i < u; i++) { \
142 av1_tree_to_cdf(tree, probs[i], cdf[i]); \
143 } \
144 } while (0)
145
146 #define av1_tree_to_cdf_2D(tree, probs, cdf, v, u) \
147 do { \
148 int j; \
149 int i; \
150 for (j = 0; j < v; j++) { \
151 for (i = 0; i < u; i++) { \
152 av1_tree_to_cdf(tree, probs[j][i], cdf[j][i]); \
153 } \
154 } \
155 } while (0)
156
157 void av1_indices_from_tree(int *ind, int *inv, const aom_tree_index *tree);
158
update_cdf(aom_cdf_prob * cdf,int val,int nsymbs)159 static INLINE void update_cdf(aom_cdf_prob *cdf, int val, int nsymbs) {
160 int rate = 4 + (cdf[nsymbs] > 31) + get_msb(nsymbs);
161 #if CONFIG_LV_MAP
162 if (nsymbs == 2)
163 rate = 4 + (cdf[nsymbs] > 7) + (cdf[nsymbs] > 15) + get_msb(nsymbs);
164 #endif
165 const int rate2 = 5;
166 int i, tmp;
167 int diff;
168 #if 1
169 const int tmp0 = 1 << rate2;
170 tmp = AOM_ICDF(tmp0);
171 diff = ((CDF_PROB_TOP - (nsymbs << rate2)) >> rate) << rate;
172 // Single loop (faster)
173 #if !CONFIG_ANS
174 for (i = 0; i < nsymbs - 1; ++i, tmp -= tmp0) {
175 tmp -= (i == val ? diff : 0);
176 cdf[i] += ((tmp - cdf[i]) >> rate);
177 }
178 #else
179 for (i = 0; i < nsymbs - 1; ++i, tmp += tmp0) {
180 tmp += (i == val ? diff : 0);
181 cdf[i] -= ((cdf[i] - tmp) >> rate);
182 }
183 #endif
184 #else
185 for (i = 0; i < nsymbs; ++i) {
186 tmp = (i + 1) << rate2;
187 cdf[i] -= ((cdf[i] - tmp) >> rate);
188 }
189 diff = CDF_PROB_TOP - cdf[nsymbs - 1];
190
191 for (i = val; i < nsymbs; ++i) {
192 cdf[i] += diff;
193 }
194 #endif
195 cdf[nsymbs] += (cdf[nsymbs] < 32);
196 }
197
198 #if CONFIG_LV_MAP
update_bin(aom_cdf_prob * cdf,int val,int nsymbs)199 static INLINE void update_bin(aom_cdf_prob *cdf, int val, int nsymbs) {
200 update_cdf(cdf, val, nsymbs);
201 }
202 #endif
203
204 #ifdef __cplusplus
205 } // extern "C"
206 #endif
207
208 #endif // AOM_DSP_PROB_H_
209