prob.h 6.06 KB
Newer Older
John Koleszar's avatar
John Koleszar committed
1
/*
Yaowu Xu's avatar
Yaowu Xu committed
2
 * Copyright (c) 2016, Alliance for Open Media. All rights reserved
John Koleszar's avatar
John Koleszar committed
3
 *
Yaowu Xu's avatar
Yaowu Xu committed
4
5
6
7
8
9
 * 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.
John Koleszar's avatar
John Koleszar committed
10
11
 */

Yaowu Xu's avatar
Yaowu Xu committed
12
13
#ifndef AOM_DSP_PROB_H_
#define AOM_DSP_PROB_H_
John Koleszar's avatar
John Koleszar committed
14

15
16
#include <assert.h>

Yaowu Xu's avatar
Yaowu Xu committed
17
18
#include "./aom_config.h"
#include "./aom_dsp_common.h"
19

20
#include "aom_ports/bitops.h"
21
#include "aom_ports/mem.h"
22

23
#if !CONFIG_ANS
24
25
26
#include "aom_dsp/entcode.h"
#endif

27
28
29
30
#ifdef __cplusplus
extern "C" {
#endif

Yaowu Xu's avatar
Yaowu Xu committed
31
typedef uint8_t aom_prob;
John Koleszar's avatar
John Koleszar committed
32

33
34
35
// TODO(negge): Rename this aom_prob once we remove vpxbool.
typedef uint16_t aom_cdf_prob;

36
37
#define CDF_SIZE(x) ((x) + 1)

38
39
40
#define CDF_PROB_BITS 15
#define CDF_PROB_TOP (1 << CDF_PROB_BITS)

41
#if !CONFIG_ANS
42
43
44
45
46
#define AOM_ICDF OD_ICDF
#else
#define AOM_ICDF(x) (x)
#endif

47
48
#define MAX_PROB 255

49
50
#define LV_MAP_PROB 1

51
52
#define BR_NODE 1

53
54
55
56
#if CONFIG_ADAPT_SCAN
#define CACHE_SCAN_PROB 1
#endif

Yaowu Xu's avatar
Yaowu Xu committed
57
#define aom_prob_half ((aom_prob)128)
John Koleszar's avatar
John Koleszar committed
58

Yaowu Xu's avatar
Yaowu Xu committed
59
typedef int8_t aom_tree_index;
John Koleszar's avatar
John Koleszar committed
60

61
#define TREE_SIZE(leaf_count) (-2 + 2 * (leaf_count))
62

Yaowu Xu's avatar
Yaowu Xu committed
63
64
#define MODE_MV_COUNT_SAT 20

John Koleszar's avatar
John Koleszar committed
65
/* We build coding trees compactly in arrays.
Yaowu Xu's avatar
Yaowu Xu committed
66
   Each node of the tree is a pair of aom_tree_indices.
John Koleszar's avatar
John Koleszar committed
67
68
69
70
71
   Array index often references a corresponding probability table.
   Index <= 0 means done encoding/decoding and value = -Index,
   Index > 0 means need another bit, specification at index.
   Nonnegative indices are always even;  processing begins at node 0. */

Yaowu Xu's avatar
Yaowu Xu committed
72
typedef const aom_tree_index aom_tree[];
John Koleszar's avatar
John Koleszar committed
73

74
static INLINE aom_prob get_prob(unsigned int num, unsigned int den) {
75
  assert(den != 0);
76
  {
James Zern's avatar
James Zern committed
77
    const int p = (int)(((uint64_t)num * 256 + (den >> 1)) / den);
78
79
80
81
    // (p > 255) ? 255 : (p < 1) ? 1 : p;
    const int clipped_prob = p | ((255 - p) >> 23) | (p == 0);
    return (aom_prob)clipped_prob;
  }
82
}
83

84
static INLINE aom_prob get_binary_prob(unsigned int n0, unsigned int n1) {
85
86
87
  const unsigned int den = n0 + n1;
  if (den == 0) return 128u;
  return get_prob(n0, den);
88
89
}

90
/* This function assumes prob1 and prob2 are already within [1,255] range. */
Yaowu Xu's avatar
Yaowu Xu committed
91
static INLINE aom_prob weighted_prob(int prob1, int prob2, int factor) {
Dmitry Kovalev's avatar
Dmitry Kovalev committed
92
  return ROUND_POWER_OF_TWO(prob1 * (256 - factor) + prob2 * factor, 8);
93
}
John Koleszar's avatar
John Koleszar committed
94

Yaowu Xu's avatar
Yaowu Xu committed
95
static INLINE aom_prob merge_probs(aom_prob pre_prob, const unsigned int ct[2],
96
97
                                   unsigned int count_sat,
                                   unsigned int max_update_factor) {
Yaowu Xu's avatar
Yaowu Xu committed
98
99
  const aom_prob prob = get_binary_prob(ct[0], ct[1]);
  const unsigned int count = AOMMIN(ct[0] + ct[1], count_sat);
100
101
102
103
  const unsigned int factor = max_update_factor * count / count_sat;
  return weighted_prob(pre_prob, prob, factor);
}

Yaowu Xu's avatar
Yaowu Xu committed
104
105
// MODE_MV_MAX_UPDATE_FACTOR (128) * count / MODE_MV_COUNT_SAT;
static const int count_to_update_factor[MODE_MV_COUNT_SAT + 1] = {
clang-format's avatar
clang-format committed
106
  0,  6,  12, 19, 25, 32,  38,  44,  51,  57, 64,
Yaowu Xu's avatar
Yaowu Xu committed
107
108
109
  70, 76, 83, 89, 96, 102, 108, 115, 121, 128
};

Yaowu Xu's avatar
Yaowu Xu committed
110
static INLINE aom_prob mode_mv_merge_probs(aom_prob pre_prob,
Yaowu Xu's avatar
Yaowu Xu committed
111
112
113
114
115
                                           const unsigned int ct[2]) {
  const unsigned int den = ct[0] + ct[1];
  if (den == 0) {
    return pre_prob;
  } else {
Yaowu Xu's avatar
Yaowu Xu committed
116
    const unsigned int count = AOMMIN(den, MODE_MV_COUNT_SAT);
Yaowu Xu's avatar
Yaowu Xu committed
117
    const unsigned int factor = count_to_update_factor[count];
118
    const aom_prob prob = get_prob(ct[0], den);
Yaowu Xu's avatar
Yaowu Xu committed
119
120
121
122
    return weighted_prob(pre_prob, prob, factor);
  }
}

Yaowu Xu's avatar
Yaowu Xu committed
123
124
void aom_tree_merge_probs(const aom_tree_index *tree, const aom_prob *pre_probs,
                          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
130

static INLINE void av1_tree_to_cdf(const aom_tree_index *tree,
131
                                   const aom_prob *probs, aom_cdf_prob *cdf) {
132
133
134
135
136
137
138
139
140
141
142
143
144
145
  aom_tree_index index[16];
  int path[16];
  int dist[16];
  tree_to_cdf(tree, probs, 0, cdf, index, path, dist);
}

#define av1_tree_to_cdf_1D(tree, probs, cdf, u) \
  do {                                          \
    int i;                                      \
    for (i = 0; i < u; i++) {                   \
      av1_tree_to_cdf(tree, probs[i], cdf[i]);  \
    }                                           \
  } while (0)

146
#define av1_tree_to_cdf_2D(tree, probs, cdf, v, u)     \
147
148
149
150
151
152
153
154
155
  do {                                                 \
    int j;                                             \
    int i;                                             \
    for (j = 0; j < v; j++) {                          \
      for (i = 0; i < u; i++) {                        \
        av1_tree_to_cdf(tree, probs[j][i], cdf[j][i]); \
      }                                                \
    }                                                  \
  } while (0)
156

Jingning Han's avatar
Jingning Han committed
157
void av1_indices_from_tree(int *ind, int *inv, const aom_tree_index *tree);
158

159
static INLINE void update_cdf(aom_cdf_prob *cdf, int val, int nsymbs) {
160
161
162
163
164
  int rate = 4 + (cdf[nsymbs] > 31) + get_msb(nsymbs);
#if CONFIG_LV_MAP
  if (nsymbs == 2)
    rate = 4 + (cdf[nsymbs] > 7) + (cdf[nsymbs] > 15) + get_msb(nsymbs);
#endif
165
  const int rate2 = 5;
Thomas Davies's avatar
Thomas Davies committed
166
167
168
169
  int i, tmp;
  int diff;
#if 1
  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
175
176
177
178
  for (i = 0; i < nsymbs - 1; ++i, tmp -= tmp0) {
    tmp -= (i == val ? diff : 0);
    cdf[i] += ((tmp - cdf[i]) >> rate);
  }
#else
Thomas Davies's avatar
Thomas Davies committed
179
180
181
182
  for (i = 0; i < nsymbs - 1; ++i, tmp += tmp0) {
    tmp += (i == val ? diff : 0);
    cdf[i] -= ((cdf[i] - tmp) >> rate);
  }
183
#endif
Thomas Davies's avatar
Thomas Davies committed
184
#else
185
  for (i = 0; i < nsymbs; ++i) {
Thomas Davies's avatar
Thomas Davies committed
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
  }
Thomas Davies's avatar
Thomas Davies committed
194
#endif
195
  cdf[nsymbs] += (cdf[nsymbs] < 32);
196
197
}

198
199
200
201
#ifdef __cplusplus
}  // extern "C"
#endif

Yaowu Xu's avatar
Yaowu Xu committed
202
#endif  // AOM_DSP_PROB_H_