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 18 typedef uint8_t vp9_prob; 19 20 #define vp9_prob_half ((vp9_prob) 128) 21 22 typedef int8_t vp9_tree_index; 23 24 #define TREE_SIZE(leaf_count) (2 * (leaf_count) - 2) 25 26 #define vp9_complement(x) (255 - x) 27 28 /* We build coding trees compactly in arrays. 29 Each node of the tree is a pair of vp9_tree_indices. 30 Array index often references a corresponding probability table. 31 Index <= 0 means done encoding/decoding and value = -Index, 32 Index > 0 means need another bit, specification at index. 33 Nonnegative indices are always even; processing begins at node 0. */ 34 35 typedef const vp9_tree_index vp9_tree[]; 36 37 struct vp9_token { 38 int value; 39 int len; 40 }; 41 42 /* Construct encoding array from tree. */ 43 44 void vp9_tokens_from_tree(struct vp9_token*, vp9_tree); 45 46 /* Convert array of token occurrence counts into a table of probabilities 47 for the associated binary encoding tree. Also writes count of branches 48 taken for each node on the tree; this facilitiates decisions as to 49 probability updates. */ 50 51 void vp9_tree_probs_from_distribution(vp9_tree tree, 52 unsigned int branch_ct[ /* n - 1 */ ][2], 53 const unsigned int num_events[ /* n */ ]); 54 55 56 static 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 64 static 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 68 static 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 73 static 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 */ 78 static 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 82 static INLINE vp9_prob merge_probs(vp9_prob pre_prob, 83 const unsigned int ct[2], 84 unsigned int count_sat, 85 unsigned int max_update_factor) { 86 const vp9_prob prob = get_binary_prob(ct[0], ct[1]); 87 const unsigned int count = MIN(ct[0] + ct[1], count_sat); 88 const unsigned int factor = max_update_factor * count / count_sat; 89 return weighted_prob(pre_prob, prob, factor); 90 } 91 92 static unsigned int tree_merge_probs_impl(unsigned int i, 93 const vp9_tree_index *tree, 94 const vp9_prob *pre_probs, 95 const unsigned int *counts, 96 unsigned int count_sat, 97 unsigned int max_update_factor, 98 vp9_prob *probs) { 99 const int l = tree[i]; 100 const unsigned int left_count = (l <= 0) 101 ? counts[-l] 102 : tree_merge_probs_impl(l, tree, pre_probs, counts, 103 count_sat, max_update_factor, probs); 104 const int r = tree[i + 1]; 105 const unsigned int right_count = (r <= 0) 106 ? counts[-r] 107 : tree_merge_probs_impl(r, tree, pre_probs, counts, 108 count_sat, max_update_factor, probs); 109 const unsigned int ct[2] = { left_count, right_count }; 110 probs[i >> 1] = merge_probs(pre_probs[i >> 1], ct, 111 count_sat, max_update_factor); 112 return left_count + right_count; 113 } 114 115 static void tree_merge_probs(const vp9_tree_index *tree, 116 const vp9_prob *pre_probs, 117 const unsigned int *counts, 118 unsigned int count_sat, 119 unsigned int max_update_factor, vp9_prob *probs) { 120 tree_merge_probs_impl(0, tree, pre_probs, counts, 121 count_sat, max_update_factor, probs); 122 } 123 124 125 #endif // VP9_COMMON_VP9_TREECODER_H_ 126
