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