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_AOM_DSP_PROB_H_
13 #define AOM_AOM_DSP_PROB_H_
14
15 #include <assert.h>
16 #include <stdio.h>
17
18 #include "config/aom_config.h"
19
20 #include "aom_dsp/aom_dsp_common.h"
21 #include "aom_dsp/entcode.h"
22 #include "aom_ports/bitops.h"
23 #include "aom_ports/mem.h"
24
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28
29 typedef uint16_t aom_cdf_prob;
30
31 #define CDF_SIZE(x) ((x) + 1)
32 #define CDF_PROB_BITS 15
33 #define CDF_PROB_TOP (1 << CDF_PROB_BITS)
34 /*The value stored in an iCDF is CDF_PROB_TOP minus the actual cumulative
35 probability (an "inverse" CDF).
36 This function converts from one representation to the other (and is its own
37 inverse).*/
38 #define AOM_ICDF(x) (CDF_PROB_TOP - (x))
39
40 #define AOM_CDF2(a0) AOM_ICDF(a0), AOM_ICDF(CDF_PROB_TOP), 0
41 #define AOM_CDF3(a0, a1) AOM_ICDF(a0), AOM_ICDF(a1), AOM_ICDF(CDF_PROB_TOP), 0
42 #define AOM_CDF4(a0, a1, a2) \
43 AOM_ICDF(a0), AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(CDF_PROB_TOP), 0
44 #define AOM_CDF5(a0, a1, a2, a3) \
45 AOM_ICDF(a0) \
46 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(CDF_PROB_TOP), 0
47 #define AOM_CDF6(a0, a1, a2, a3, a4) \
48 AOM_ICDF(a0) \
49 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), \
50 AOM_ICDF(CDF_PROB_TOP), 0
51 #define AOM_CDF7(a0, a1, a2, a3, a4, a5) \
52 AOM_ICDF(a0) \
53 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
54 AOM_ICDF(CDF_PROB_TOP), 0
55 #define AOM_CDF8(a0, a1, a2, a3, a4, a5, a6) \
56 AOM_ICDF(a0) \
57 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
58 AOM_ICDF(a6), AOM_ICDF(CDF_PROB_TOP), 0
59 #define AOM_CDF9(a0, a1, a2, a3, a4, a5, a6, a7) \
60 AOM_ICDF(a0) \
61 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
62 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(CDF_PROB_TOP), 0
63 #define AOM_CDF10(a0, a1, a2, a3, a4, a5, a6, a7, a8) \
64 AOM_ICDF(a0) \
65 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
66 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(a8), AOM_ICDF(CDF_PROB_TOP), 0
67 #define AOM_CDF11(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9) \
68 AOM_ICDF(a0) \
69 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
70 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(a8), AOM_ICDF(a9), \
71 AOM_ICDF(CDF_PROB_TOP), 0
72 #define AOM_CDF12(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10) \
73 AOM_ICDF(a0) \
74 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
75 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(a8), AOM_ICDF(a9), AOM_ICDF(a10), \
76 AOM_ICDF(CDF_PROB_TOP), 0
77 #define AOM_CDF13(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11) \
78 AOM_ICDF(a0) \
79 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
80 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(a8), AOM_ICDF(a9), AOM_ICDF(a10), \
81 AOM_ICDF(a11), AOM_ICDF(CDF_PROB_TOP), 0
82 #define AOM_CDF14(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12) \
83 AOM_ICDF(a0) \
84 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
85 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(a8), AOM_ICDF(a9), AOM_ICDF(a10), \
86 AOM_ICDF(a11), AOM_ICDF(a12), AOM_ICDF(CDF_PROB_TOP), 0
87 #define AOM_CDF15(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13) \
88 AOM_ICDF(a0) \
89 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
90 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(a8), AOM_ICDF(a9), AOM_ICDF(a10), \
91 AOM_ICDF(a11), AOM_ICDF(a12), AOM_ICDF(a13), AOM_ICDF(CDF_PROB_TOP), 0
92 #define AOM_CDF16(a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, \
93 a14) \
94 AOM_ICDF(a0) \
95 , AOM_ICDF(a1), AOM_ICDF(a2), AOM_ICDF(a3), AOM_ICDF(a4), AOM_ICDF(a5), \
96 AOM_ICDF(a6), AOM_ICDF(a7), AOM_ICDF(a8), AOM_ICDF(a9), AOM_ICDF(a10), \
97 AOM_ICDF(a11), AOM_ICDF(a12), AOM_ICDF(a13), AOM_ICDF(a14), \
98 AOM_ICDF(CDF_PROB_TOP), 0
99
get_prob(unsigned int num,unsigned int den)100 static inline uint8_t get_prob(unsigned int num, unsigned int den) {
101 assert(den != 0);
102 {
103 const int p = (int)(((uint64_t)num * 256 + (den >> 1)) / den);
104 // (p > 255) ? 255 : (p < 1) ? 1 : p;
105 const int clipped_prob = p | ((255 - p) >> 23) | (p == 0);
106 return (uint8_t)clipped_prob;
107 }
108 }
109
update_cdf(aom_cdf_prob * cdf,int8_t val,int nsymbs)110 static inline void update_cdf(aom_cdf_prob *cdf, int8_t val, int nsymbs) {
111 assert(nsymbs < 17);
112 const int count = cdf[nsymbs];
113
114 // rate is computed in the spec as:
115 // 3 + ( cdf[N] > 15 ) + ( cdf[N] > 31 ) + Min(FloorLog2(N), 2)
116 // In this case cdf[N] is |count|.
117 // Min(FloorLog2(N), 2) is 1 for nsymbs == {2, 3} and 2 for all
118 // nsymbs > 3. So the equation becomes:
119 // 4 + (count > 15) + (count > 31) + (nsymbs > 3).
120 // Note that the largest value for count is 32 (it is not incremented beyond
121 // 32). So using that information:
122 // count >> 4 is 0 for count from 0 to 15.
123 // count >> 4 is 1 for count from 16 to 31.
124 // count >> 4 is 2 for count == 31.
125 // Now, the equation becomes:
126 // 4 + (count >> 4) + (nsymbs > 3).
127 const int rate = 4 + (count >> 4) + (nsymbs > 3);
128
129 int i = 0;
130 do {
131 if (i < val) {
132 cdf[i] += (CDF_PROB_TOP - cdf[i]) >> rate;
133 } else {
134 cdf[i] -= cdf[i] >> rate;
135 }
136 } while (++i < nsymbs - 1);
137 cdf[nsymbs] += (count < 32);
138 }
139
140 #ifdef __cplusplus
141 } // extern "C"
142 #endif
143
144 #endif // AOM_AOM_DSP_PROB_H_
145