1/*
2 *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#ifndef VP9_COMMON_VP9_TREECODER_H_
12#define VP9_COMMON_VP9_TREECODER_H_
13
14#include "./vpx_config.h"
15#include "vpx/vpx_integer.h"
16#include "vp9/common/vp9_common.h"
17
18typedef uint8_t vp9_prob;
19
20#define vp9_prob_half ((vp9_prob) 128)
21
22typedef int8_t vp9_tree_index;
23
24#define vp9_complement(x) (255 - x)
25
26/* We build coding trees compactly in arrays.
27   Each node of the tree is a pair of vp9_tree_indices.
28   Array index often references a corresponding probability table.
29   Index <= 0 means done encoding/decoding and value = -Index,
30   Index > 0 means need another bit, specification at index.
31   Nonnegative indices are always even;  processing begins at node 0. */
32
33typedef const vp9_tree_index vp9_tree[], *vp9_tree_p;
34
35struct vp9_token {
36  int value;
37  int len;
38};
39
40/* Construct encoding array from tree. */
41
42void vp9_tokens_from_tree(struct vp9_token*, vp9_tree);
43void vp9_tokens_from_tree_offset(struct vp9_token*, vp9_tree, int offset);
44
45/* Convert array of token occurrence counts into a table of probabilities
46   for the associated binary encoding tree.  Also writes count of branches
47   taken for each node on the tree; this facilitiates decisions as to
48   probability updates. */
49
50void vp9_tree_probs_from_distribution(vp9_tree tree,
51                                      vp9_prob probs[ /* n - 1 */ ],
52                                      unsigned int branch_ct[ /* n - 1 */ ][2],
53                                      const unsigned int num_events[ /* n */ ],
54                                      unsigned int tok0_offset);
55
56static INLINE vp9_prob clip_prob(int p) {
57  return (p > 255) ? 255u : (p < 1) ? 1u : p;
58}
59
60// int64 is not needed for normal frame level calculations.
61// However when outputing entropy stats accumulated over many frames
62// or even clips we can overflow int math.
63#ifdef ENTROPY_STATS
64static INLINE vp9_prob get_prob(int num, int den) {
65  return (den == 0) ? 128u : clip_prob(((int64_t)num * 256 + (den >> 1)) / den);
66}
67#else
68static INLINE vp9_prob get_prob(int num, int den) {
69  return (den == 0) ? 128u : clip_prob((num * 256 + (den >> 1)) / den);
70}
71#endif
72
73static INLINE vp9_prob get_binary_prob(int n0, int n1) {
74  return get_prob(n0, n0 + n1);
75}
76
77/* this function assumes prob1 and prob2 are already within [1,255] range */
78static INLINE vp9_prob weighted_prob(int prob1, int prob2, int factor) {
79  return ROUND_POWER_OF_TWO(prob1 * (256 - factor) + prob2 * factor, 8);
80}
81
82static INLINE vp9_prob merge_probs(vp9_prob pre_prob, vp9_prob prob,
83                                   const unsigned int ct[2],
84                                   unsigned int count_sat,
85                                   unsigned int max_update_factor) {
86  const unsigned int count = MIN(ct[0] + ct[1], count_sat);
87  const unsigned int factor = max_update_factor * count / count_sat;
88  return weighted_prob(pre_prob, prob, factor);
89}
90
91static INLINE vp9_prob merge_probs2(vp9_prob pre_prob,
92                                   const unsigned int ct[2],
93                                   unsigned int count_sat,
94                                   unsigned int max_update_factor) {
95  return merge_probs(pre_prob, get_binary_prob(ct[0], ct[1]), ct, count_sat,
96                     max_update_factor);
97}
98
99
100#endif  // VP9_COMMON_VP9_TREECODER_H_
101