michael@0: /*
michael@0:  *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
michael@0:  *
michael@0:  *  Use of this source code is governed by a BSD-style license
michael@0:  *  that can be found in the LICENSE file in the root of the source
michael@0:  *  tree. An additional intellectual property rights grant can be found
michael@0:  *  in the file PATENTS.  All contributing project authors may
michael@0:  *  be found in the AUTHORS file in the root of the source tree.
michael@0:  */
michael@0: 
michael@0: #ifndef VP9_COMMON_VP9_TREECODER_H_
michael@0: #define VP9_COMMON_VP9_TREECODER_H_
michael@0: 
michael@0: #include "./vpx_config.h"
michael@0: #include "vpx/vpx_integer.h"
michael@0: #include "vp9/common/vp9_common.h"
michael@0: 
michael@0: typedef uint8_t vp9_prob;
michael@0: 
michael@0: #define vp9_prob_half ((vp9_prob) 128)
michael@0: 
michael@0: typedef int8_t vp9_tree_index;
michael@0: 
michael@0: #define TREE_SIZE(leaf_count) (2 * (leaf_count) - 2)
michael@0: 
michael@0: #define vp9_complement(x) (255 - x)
michael@0: 
michael@0: /* We build coding trees compactly in arrays.
michael@0:    Each node of the tree is a pair of vp9_tree_indices.
michael@0:    Array index often references a corresponding probability table.
michael@0:    Index <= 0 means done encoding/decoding and value = -Index,
michael@0:    Index > 0 means need another bit, specification at index.
michael@0:    Nonnegative indices are always even;  processing begins at node 0. */
michael@0: 
michael@0: typedef const vp9_tree_index vp9_tree[];
michael@0: 
michael@0: struct vp9_token {
michael@0:   int value;
michael@0:   int len;
michael@0: };
michael@0: 
michael@0: /* Construct encoding array from tree. */
michael@0: 
michael@0: void vp9_tokens_from_tree(struct vp9_token*, vp9_tree);
michael@0: 
michael@0: /* Convert array of token occurrence counts into a table of probabilities
michael@0:    for the associated binary encoding tree.  Also writes count of branches
michael@0:    taken for each node on the tree; this facilitiates decisions as to
michael@0:    probability updates. */
michael@0: 
michael@0: void vp9_tree_probs_from_distribution(vp9_tree tree,
michael@0:                                       unsigned int branch_ct[ /* n - 1 */ ][2],
michael@0:                                       const unsigned int num_events[ /* n */ ]);
michael@0: 
michael@0: 
michael@0: static INLINE vp9_prob clip_prob(int p) {
michael@0:   return (p > 255) ? 255u : (p < 1) ? 1u : p;
michael@0: }
michael@0: 
michael@0: // int64 is not needed for normal frame level calculations.
michael@0: // However when outputing entropy stats accumulated over many frames
michael@0: // or even clips we can overflow int math.
michael@0: #ifdef ENTROPY_STATS
michael@0: static INLINE vp9_prob get_prob(int num, int den) {
michael@0:   return (den == 0) ? 128u : clip_prob(((int64_t)num * 256 + (den >> 1)) / den);
michael@0: }
michael@0: #else
michael@0: static INLINE vp9_prob get_prob(int num, int den) {
michael@0:   return (den == 0) ? 128u : clip_prob((num * 256 + (den >> 1)) / den);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: static INLINE vp9_prob get_binary_prob(int n0, int n1) {
michael@0:   return get_prob(n0, n0 + n1);
michael@0: }
michael@0: 
michael@0: /* this function assumes prob1 and prob2 are already within [1,255] range */
michael@0: static INLINE vp9_prob weighted_prob(int prob1, int prob2, int factor) {
michael@0:   return ROUND_POWER_OF_TWO(prob1 * (256 - factor) + prob2 * factor, 8);
michael@0: }
michael@0: 
michael@0: static INLINE vp9_prob merge_probs(vp9_prob pre_prob,
michael@0:                                    const unsigned int ct[2],
michael@0:                                    unsigned int count_sat,
michael@0:                                    unsigned int max_update_factor) {
michael@0:   const vp9_prob prob = get_binary_prob(ct[0], ct[1]);
michael@0:   const unsigned int count = MIN(ct[0] + ct[1], count_sat);
michael@0:   const unsigned int factor = max_update_factor * count / count_sat;
michael@0:   return weighted_prob(pre_prob, prob, factor);
michael@0: }
michael@0: 
michael@0: static unsigned int tree_merge_probs_impl(unsigned int i,
michael@0:                                           const vp9_tree_index *tree,
michael@0:                                           const vp9_prob *pre_probs,
michael@0:                                           const unsigned int *counts,
michael@0:                                           unsigned int count_sat,
michael@0:                                           unsigned int max_update_factor,
michael@0:                                           vp9_prob *probs) {
michael@0:   const int l = tree[i];
michael@0:   const unsigned int left_count = (l <= 0)
michael@0:                  ? counts[-l]
michael@0:                  : tree_merge_probs_impl(l, tree, pre_probs, counts,
michael@0:                                          count_sat, max_update_factor, probs);
michael@0:   const int r = tree[i + 1];
michael@0:   const unsigned int right_count = (r <= 0)
michael@0:                  ? counts[-r]
michael@0:                  : tree_merge_probs_impl(r, tree, pre_probs, counts,
michael@0:                                          count_sat, max_update_factor, probs);
michael@0:   const unsigned int ct[2] = { left_count, right_count };
michael@0:   probs[i >> 1] = merge_probs(pre_probs[i >> 1], ct,
michael@0:                               count_sat, max_update_factor);
michael@0:   return left_count + right_count;
michael@0: }
michael@0: 
michael@0: static void tree_merge_probs(const vp9_tree_index *tree,
michael@0:                              const vp9_prob *pre_probs,
michael@0:                              const unsigned int *counts,
michael@0:                              unsigned int count_sat,
michael@0:                              unsigned int max_update_factor, vp9_prob *probs) {
michael@0:   tree_merge_probs_impl(0, tree, pre_probs, counts,
michael@0:                         count_sat, max_update_factor, probs);
michael@0: }
michael@0: 
michael@0: 
michael@0: #endif  // VP9_COMMON_VP9_TREECODER_H_