1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libvpx/vp9/common/vp9_treecoder.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,125 @@
1.4 +/*
1.5 + * Copyright (c) 2010 The WebM project authors. All Rights Reserved.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license
1.8 + * that can be found in the LICENSE file in the root of the source
1.9 + * tree. An additional intellectual property rights grant can be found
1.10 + * in the file PATENTS. All contributing project authors may
1.11 + * be found in the AUTHORS file in the root of the source tree.
1.12 + */
1.13 +
1.14 +#ifndef VP9_COMMON_VP9_TREECODER_H_
1.15 +#define VP9_COMMON_VP9_TREECODER_H_
1.16 +
1.17 +#include "./vpx_config.h"
1.18 +#include "vpx/vpx_integer.h"
1.19 +#include "vp9/common/vp9_common.h"
1.20 +
1.21 +typedef uint8_t vp9_prob;
1.22 +
1.23 +#define vp9_prob_half ((vp9_prob) 128)
1.24 +
1.25 +typedef int8_t vp9_tree_index;
1.26 +
1.27 +#define TREE_SIZE(leaf_count) (2 * (leaf_count) - 2)
1.28 +
1.29 +#define vp9_complement(x) (255 - x)
1.30 +
1.31 +/* We build coding trees compactly in arrays.
1.32 + Each node of the tree is a pair of vp9_tree_indices.
1.33 + Array index often references a corresponding probability table.
1.34 + Index <= 0 means done encoding/decoding and value = -Index,
1.35 + Index > 0 means need another bit, specification at index.
1.36 + Nonnegative indices are always even; processing begins at node 0. */
1.37 +
1.38 +typedef const vp9_tree_index vp9_tree[];
1.39 +
1.40 +struct vp9_token {
1.41 + int value;
1.42 + int len;
1.43 +};
1.44 +
1.45 +/* Construct encoding array from tree. */
1.46 +
1.47 +void vp9_tokens_from_tree(struct vp9_token*, vp9_tree);
1.48 +
1.49 +/* Convert array of token occurrence counts into a table of probabilities
1.50 + for the associated binary encoding tree. Also writes count of branches
1.51 + taken for each node on the tree; this facilitiates decisions as to
1.52 + probability updates. */
1.53 +
1.54 +void vp9_tree_probs_from_distribution(vp9_tree tree,
1.55 + unsigned int branch_ct[ /* n - 1 */ ][2],
1.56 + const unsigned int num_events[ /* n */ ]);
1.57 +
1.58 +
1.59 +static INLINE vp9_prob clip_prob(int p) {
1.60 + return (p > 255) ? 255u : (p < 1) ? 1u : p;
1.61 +}
1.62 +
1.63 +// int64 is not needed for normal frame level calculations.
1.64 +// However when outputing entropy stats accumulated over many frames
1.65 +// or even clips we can overflow int math.
1.66 +#ifdef ENTROPY_STATS
1.67 +static INLINE vp9_prob get_prob(int num, int den) {
1.68 + return (den == 0) ? 128u : clip_prob(((int64_t)num * 256 + (den >> 1)) / den);
1.69 +}
1.70 +#else
1.71 +static INLINE vp9_prob get_prob(int num, int den) {
1.72 + return (den == 0) ? 128u : clip_prob((num * 256 + (den >> 1)) / den);
1.73 +}
1.74 +#endif
1.75 +
1.76 +static INLINE vp9_prob get_binary_prob(int n0, int n1) {
1.77 + return get_prob(n0, n0 + n1);
1.78 +}
1.79 +
1.80 +/* this function assumes prob1 and prob2 are already within [1,255] range */
1.81 +static INLINE vp9_prob weighted_prob(int prob1, int prob2, int factor) {
1.82 + return ROUND_POWER_OF_TWO(prob1 * (256 - factor) + prob2 * factor, 8);
1.83 +}
1.84 +
1.85 +static INLINE vp9_prob merge_probs(vp9_prob pre_prob,
1.86 + const unsigned int ct[2],
1.87 + unsigned int count_sat,
1.88 + unsigned int max_update_factor) {
1.89 + const vp9_prob prob = get_binary_prob(ct[0], ct[1]);
1.90 + const unsigned int count = MIN(ct[0] + ct[1], count_sat);
1.91 + const unsigned int factor = max_update_factor * count / count_sat;
1.92 + return weighted_prob(pre_prob, prob, factor);
1.93 +}
1.94 +
1.95 +static unsigned int tree_merge_probs_impl(unsigned int i,
1.96 + const vp9_tree_index *tree,
1.97 + const vp9_prob *pre_probs,
1.98 + const unsigned int *counts,
1.99 + unsigned int count_sat,
1.100 + unsigned int max_update_factor,
1.101 + vp9_prob *probs) {
1.102 + const int l = tree[i];
1.103 + const unsigned int left_count = (l <= 0)
1.104 + ? counts[-l]
1.105 + : tree_merge_probs_impl(l, tree, pre_probs, counts,
1.106 + count_sat, max_update_factor, probs);
1.107 + const int r = tree[i + 1];
1.108 + const unsigned int right_count = (r <= 0)
1.109 + ? counts[-r]
1.110 + : tree_merge_probs_impl(r, tree, pre_probs, counts,
1.111 + count_sat, max_update_factor, probs);
1.112 + const unsigned int ct[2] = { left_count, right_count };
1.113 + probs[i >> 1] = merge_probs(pre_probs[i >> 1], ct,
1.114 + count_sat, max_update_factor);
1.115 + return left_count + right_count;
1.116 +}
1.117 +
1.118 +static void tree_merge_probs(const vp9_tree_index *tree,
1.119 + const vp9_prob *pre_probs,
1.120 + const unsigned int *counts,
1.121 + unsigned int count_sat,
1.122 + unsigned int max_update_factor, vp9_prob *probs) {
1.123 + tree_merge_probs_impl(0, tree, pre_probs, counts,
1.124 + count_sat, max_update_factor, probs);
1.125 +}
1.126 +
1.127 +
1.128 +#endif // VP9_COMMON_VP9_TREECODER_H_
