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 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 33 typedef const vp9_tree_index vp9_tree[], *vp9_tree_p; 34 35 struct vp9_token { 36 int value; 37 int len; 38 }; 39 40 /* Construct encoding array from tree. */ 41 42 void vp9_tokens_from_tree(struct vp9_token*, vp9_tree); 43 void 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 50 void 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 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, 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 91 static 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
