The Tor Browser / file comparison
comparison: media/libvpx/vp9/common/vp9_treecoder.h
media/libvpx/vp9/common/vp9_treecoder.h
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:b3c6423a14a6 |
|---|---|
| 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_ |
