1ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang/* 2ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang * 4ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang * Use of this source code is governed by a BSD-style license 5ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang * that can be found in the LICENSE file in the root of the source 6ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang * tree. An additional intellectual property rights grant can be found 7ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang * in the file PATENTS. All contributing project authors may 8ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang * be found in the AUTHORS file in the root of the source tree. 9ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang */ 10ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 11ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#ifndef VP9_COMMON_VP9_TREECODER_H_ 12ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#define VP9_COMMON_VP9_TREECODER_H_ 13ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 14ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#include "./vpx_config.h" 15ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#include "vpx/vpx_integer.h" 16ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#include "vp9/common/vp9_common.h" 17ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 18ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangtypedef uint8_t vp9_prob; 19ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 20ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#define vp9_prob_half ((vp9_prob) 128) 21ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 22ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangtypedef int8_t vp9_tree_index; 23ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 24ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#define vp9_complement(x) (255 - x) 25ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 26ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang/* We build coding trees compactly in arrays. 27ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang Each node of the tree is a pair of vp9_tree_indices. 28ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang Array index often references a corresponding probability table. 29ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang Index <= 0 means done encoding/decoding and value = -Index, 30ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang Index > 0 means need another bit, specification at index. 31ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang Nonnegative indices are always even; processing begins at node 0. */ 32ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 33ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangtypedef const vp9_tree_index vp9_tree[], *vp9_tree_p; 34ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 35ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangstruct vp9_token { 36ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int value; 37ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int len; 38ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang}; 39ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 40ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang/* Construct encoding array from tree. */ 41ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 42ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangvoid vp9_tokens_from_tree(struct vp9_token*, vp9_tree); 43ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangvoid vp9_tokens_from_tree_offset(struct vp9_token*, vp9_tree, int offset); 44ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 45ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang/* Convert array of token occurrence counts into a table of probabilities 46ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang for the associated binary encoding tree. Also writes count of branches 47ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang taken for each node on the tree; this facilitiates decisions as to 48ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang probability updates. */ 49ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 50ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangvoid vp9_tree_probs_from_distribution(vp9_tree tree, 51ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang vp9_prob probs[ /* n - 1 */ ], 52ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned int branch_ct[ /* n - 1 */ ][2], 53ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang const unsigned int num_events[ /* n */ ], 54ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang unsigned int tok0_offset); 55ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 56ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangstatic INLINE vp9_prob clip_prob(int p) { 57ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return (p > 255) ? 255u : (p < 1) ? 1u : p; 58ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang} 59ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 60ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang// int64 is not needed for normal frame level calculations. 61ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang// However when outputing entropy stats accumulated over many frames 62ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang// or even clips we can overflow int math. 63ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#ifdef ENTROPY_STATS 64ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangstatic INLINE vp9_prob get_prob(int num, int den) { 65ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return (den == 0) ? 128u : clip_prob(((int64_t)num * 256 + (den >> 1)) / den); 66ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang} 67ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#else 68ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangstatic INLINE vp9_prob get_prob(int num, int den) { 69ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return (den == 0) ? 128u : clip_prob((num * 256 + (den >> 1)) / den); 70ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang} 71ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#endif 72ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 73ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangstatic INLINE vp9_prob get_binary_prob(int n0, int n1) { 74ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return get_prob(n0, n0 + n1); 75ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang} 76ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 77ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang/* this function assumes prob1 and prob2 are already within [1,255] range */ 78ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangstatic INLINE vp9_prob weighted_prob(int prob1, int prob2, int factor) { 79ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang return ROUND_POWER_OF_TWO(prob1 * (256 - factor) + prob2 * factor, 8); 80ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang} 81ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 82f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuangstatic INLINE vp9_prob merge_probs(vp9_prob pre_prob, vp9_prob prob, 83f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang const unsigned int ct[2], 84f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang unsigned int count_sat, 85f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang unsigned int max_update_factor) { 86f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang const unsigned int count = MIN(ct[0] + ct[1], count_sat); 87f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang const unsigned int factor = max_update_factor * count / count_sat; 88f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang return weighted_prob(pre_prob, prob, factor); 89f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang} 90f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang 91f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuangstatic INLINE vp9_prob merge_probs2(vp9_prob pre_prob, 92f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang const unsigned int ct[2], 93f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang unsigned int count_sat, 94f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang unsigned int max_update_factor) { 95f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang return merge_probs(pre_prob, get_binary_prob(ct[0], ct[1]), ct, count_sat, 96f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang max_update_factor); 97f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang} 98f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang 99f3bed9137f66ef693bd406e43b17e9a1114f1e14hkuang 100ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang#endif // VP9_COMMON_VP9_TREECODER_H_ 101