From bd84685f7841f4f571f063a18b96d53e0fdef8cc Mon Sep 17 00:00:00 2001 From: John Koleszar Date: Sun, 10 Mar 2013 13:39:30 -0700 Subject: [PATCH] Optimize vp9_tree_probs_from_distribution The previous implementation visited each node in the tree multiple times because it used each symbol's encoding to revisit the branches taken and increment its count. Instead, we can traverse the tree depth first and calculate the probabilities and branch counts as we walk back up. The complexity goes from somewhere between O(nlogn) and O(n^2) (depending on how balanced the tree is) to O(n). Only tested one clip (256kbps, CIF), saw 13% decoding perf improvement. Note that this optimization should port trivially to VP8 as well. In VP8, the decoder doesn't use this function, but it does routinely show up on the profile for realtime encoding. Change-Id: I4f2848e4f41dc9a7694f73f3e75034bce08d1b12 --- vp9/common/vp9_entropy.c | 5 +-- vp9/common/vp9_entropymode.c | 79 +++++++++++++++------------------- vp9/common/vp9_entropymv.c | 30 +++++-------- vp9/common/vp9_treecoder.c | 83 ++++++++++++------------------------ vp9/common/vp9_treecoder.h | 7 ++- vp9/encoder/vp9_bitstream.c | 14 +++--- 6 files changed, 83 insertions(+), 135 deletions(-) diff --git a/vp9/common/vp9_entropy.c b/vp9/common/vp9_entropy.c index 1e3a7e17e..bc6935313 100644 --- a/vp9/common/vp9_entropy.c +++ b/vp9/common/vp9_entropy.c @@ -292,10 +292,9 @@ static void update_coef_probs(vp9_coeff_probs *dst_coef_probs, for (l = 0; l < PREV_COEF_CONTEXTS; ++l) { if (l >= 3 && k == 0) continue; - vp9_tree_probs_from_distribution(MAX_ENTROPY_TOKENS, - vp9_coef_encodings, vp9_coef_tree, + vp9_tree_probs_from_distribution(vp9_coef_tree, coef_probs, branch_ct, - coef_counts[i][j][k][l]); + coef_counts[i][j][k][l], 0); for (t = 0; t < ENTROPY_NODES; ++t) { count = branch_ct[t][0] + branch_ct[t][1]; count = count > count_sat ? count_sat : count; diff --git a/vp9/common/vp9_entropymode.c b/vp9/common/vp9_entropymode.c index 23b2abef7..061c279fa 100644 --- a/vp9/common/vp9_entropymode.c +++ b/vp9/common/vp9_entropymode.c @@ -302,40 +302,32 @@ struct vp9_token_struct vp9_sub_mv_ref_encoding_array[VP9_SUBMVREFS]; void vp9_init_mbmode_probs(VP9_COMMON *x) { unsigned int bct [VP9_YMODES] [2]; /* num Ymodes > num UV modes */ - vp9_tree_probs_from_distribution(VP9_YMODES, vp9_ymode_encodings, - vp9_ymode_tree, x->fc.ymode_prob, - bct, y_mode_cts); - vp9_tree_probs_from_distribution(VP9_I32X32_MODES, vp9_sb_ymode_encodings, - vp9_sb_ymode_tree, x->fc.sb_ymode_prob, - bct, y_mode_cts); + vp9_tree_probs_from_distribution(vp9_ymode_tree, x->fc.ymode_prob, + bct, y_mode_cts, 0); + vp9_tree_probs_from_distribution(vp9_sb_ymode_tree, x->fc.sb_ymode_prob, + bct, y_mode_cts, 0); { int i; for (i = 0; i < 8; i++) { - vp9_tree_probs_from_distribution(VP9_YMODES, vp9_kf_ymode_encodings, - vp9_kf_ymode_tree, x->kf_ymode_prob[i], - bct, kf_y_mode_cts[i]); - vp9_tree_probs_from_distribution(VP9_I32X32_MODES, - vp9_sb_kf_ymode_encodings, - vp9_sb_kf_ymode_tree, + vp9_tree_probs_from_distribution(vp9_kf_ymode_tree, x->kf_ymode_prob[i], + bct, kf_y_mode_cts[i], 0); + vp9_tree_probs_from_distribution(vp9_sb_kf_ymode_tree, x->sb_kf_ymode_prob[i], bct, - kf_y_mode_cts[i]); + kf_y_mode_cts[i], 0); } } { int i; for (i = 0; i < VP9_YMODES; i++) { - vp9_tree_probs_from_distribution(VP9_UV_MODES, vp9_uv_mode_encodings, - vp9_uv_mode_tree, x->kf_uv_mode_prob[i], - bct, kf_uv_mode_cts[i]); - vp9_tree_probs_from_distribution(VP9_UV_MODES, vp9_uv_mode_encodings, - vp9_uv_mode_tree, x->fc.uv_mode_prob[i], - bct, uv_mode_cts[i]); + vp9_tree_probs_from_distribution(vp9_uv_mode_tree, x->kf_uv_mode_prob[i], + bct, kf_uv_mode_cts[i], 0); + vp9_tree_probs_from_distribution(vp9_uv_mode_tree, x->fc.uv_mode_prob[i], + bct, uv_mode_cts[i], 0); } } - vp9_tree_probs_from_distribution(VP9_I8X8_MODES, vp9_i8x8_mode_encodings, - vp9_i8x8_mode_tree, x->fc.i8x8_mode_prob, - bct, i8x8_mode_cts); + vp9_tree_probs_from_distribution(vp9_i8x8_mode_tree, x->fc.i8x8_mode_prob, + bct, i8x8_mode_cts, 0); vpx_memcpy(x->fc.sub_mv_ref_prob, vp9_sub_mv_ref_prob2, sizeof(vp9_sub_mv_ref_prob2)); @@ -355,8 +347,7 @@ static void intra_bmode_probs_from_distribution( vp9_prob p[VP9_NKF_BINTRAMODES - 1], unsigned int branch_ct[VP9_NKF_BINTRAMODES - 1][2], const unsigned int events[VP9_NKF_BINTRAMODES]) { - vp9_tree_probs_from_distribution(VP9_NKF_BINTRAMODES, vp9_bmode_encodings, - vp9_bmode_tree, p, branch_ct, events); + vp9_tree_probs_from_distribution(vp9_bmode_tree, p, branch_ct, events, 0); } void vp9_default_bmode_probs(vp9_prob p[VP9_NKF_BINTRAMODES - 1]) { @@ -368,8 +359,7 @@ static void intra_kf_bmode_probs_from_distribution( vp9_prob p[VP9_KF_BINTRAMODES - 1], unsigned int branch_ct[VP9_KF_BINTRAMODES - 1][2], const unsigned int events[VP9_KF_BINTRAMODES]) { - vp9_tree_probs_from_distribution(VP9_KF_BINTRAMODES, vp9_kf_bmode_encodings, - vp9_kf_bmode_tree, p, branch_ct, events); + vp9_tree_probs_from_distribution(vp9_kf_bmode_tree, p, branch_ct, events, 0); } void vp9_kf_default_bmode_probs(vp9_prob p[VP9_KF_BINTRAMODES] @@ -538,17 +528,17 @@ void print_mode_contexts(VP9_COMMON *pc) { #define MODE_COUNT_SAT 20 #define MODE_MAX_UPDATE_FACTOR 144 -static void update_mode_probs(int n_modes, struct vp9_token_struct *encoding, +static void update_mode_probs(int n_modes, const vp9_tree_index *tree, unsigned int *cnt, - vp9_prob *pre_probs, vp9_prob *dst_probs) { + vp9_prob *pre_probs, vp9_prob *dst_probs, + unsigned int tok0_offset) { #define MAX_PROBS 32 vp9_prob probs[MAX_PROBS]; unsigned int branch_ct[MAX_PROBS][2]; int t, count, factor; assert(n_modes - 1 < MAX_PROBS); - vp9_tree_probs_from_distribution(n_modes, encoding, tree, probs, - branch_ct, cnt); + vp9_tree_probs_from_distribution(tree, probs, branch_ct, cnt, tok0_offset); for (t = 0; t < n_modes - 1; ++t) { count = branch_ct[t][0] + branch_ct[t][1]; count = count > MODE_COUNT_SAT ? MODE_COUNT_SAT : count; @@ -604,31 +594,32 @@ void vp9_adapt_mode_probs(VP9_COMMON *cm) { #endif #endif - update_mode_probs(VP9_YMODES, vp9_ymode_encodings, vp9_ymode_tree, + update_mode_probs(VP9_YMODES, vp9_ymode_tree, cm->fc.ymode_counts, cm->fc.pre_ymode_prob, - cm->fc.ymode_prob); - update_mode_probs(VP9_I32X32_MODES, vp9_sb_ymode_encodings, vp9_sb_ymode_tree, + cm->fc.ymode_prob, 0); + update_mode_probs(VP9_I32X32_MODES, vp9_sb_ymode_tree, cm->fc.sb_ymode_counts, cm->fc.pre_sb_ymode_prob, - cm->fc.sb_ymode_prob); + cm->fc.sb_ymode_prob, 0); for (i = 0; i < VP9_YMODES; ++i) { - update_mode_probs(VP9_UV_MODES, vp9_uv_mode_encodings, vp9_uv_mode_tree, + update_mode_probs(VP9_UV_MODES, vp9_uv_mode_tree, cm->fc.uv_mode_counts[i], cm->fc.pre_uv_mode_prob[i], - cm->fc.uv_mode_prob[i]); + cm->fc.uv_mode_prob[i], 0); } - update_mode_probs(VP9_NKF_BINTRAMODES, vp9_bmode_encodings, vp9_bmode_tree, + update_mode_probs(VP9_NKF_BINTRAMODES, vp9_bmode_tree, cm->fc.bmode_counts, cm->fc.pre_bmode_prob, - cm->fc.bmode_prob); - update_mode_probs(VP9_I8X8_MODES, vp9_i8x8_mode_encodings, + cm->fc.bmode_prob, 0); + update_mode_probs(VP9_I8X8_MODES, vp9_i8x8_mode_tree, cm->fc.i8x8_mode_counts, - cm->fc.pre_i8x8_mode_prob, cm->fc.i8x8_mode_prob); + cm->fc.pre_i8x8_mode_prob, cm->fc.i8x8_mode_prob, 0); for (i = 0; i < SUBMVREF_COUNT; ++i) { - update_mode_probs(VP9_SUBMVREFS, vp9_sub_mv_ref_encoding_array, + update_mode_probs(VP9_SUBMVREFS, vp9_sub_mv_ref_tree, cm->fc.sub_mv_ref_counts[i], - cm->fc.pre_sub_mv_ref_prob[i], cm->fc.sub_mv_ref_prob[i]); + cm->fc.pre_sub_mv_ref_prob[i], cm->fc.sub_mv_ref_prob[i], + LEFT4X4); } - update_mode_probs(VP9_NUMMBSPLITS, vp9_mbsplit_encodings, vp9_mbsplit_tree, + update_mode_probs(VP9_NUMMBSPLITS, vp9_mbsplit_tree, cm->fc.mbsplit_counts, cm->fc.pre_mbsplit_prob, - cm->fc.mbsplit_prob); + cm->fc.mbsplit_prob, 0); #if CONFIG_COMP_INTERINTRA_PRED if (cm->use_interintra) { int factor, interintra_prob, count; diff --git a/vp9/common/vp9_entropymv.c b/vp9/common/vp9_entropymv.c index 99e3c2e8c..ab87dfee2 100644 --- a/vp9/common/vp9_entropymv.c +++ b/vp9/common/vp9_entropymv.c @@ -242,29 +242,23 @@ void vp9_counts_to_nmv_context( unsigned int (*branch_ct_hp)[2]) { int i, j, k; vp9_counts_process(NMVcount, usehp); - vp9_tree_probs_from_distribution(MV_JOINTS, - vp9_mv_joint_encodings, - vp9_mv_joint_tree, + vp9_tree_probs_from_distribution(vp9_mv_joint_tree, prob->joints, branch_ct_joint, - NMVcount->joints); + NMVcount->joints, 0); for (i = 0; i < 2; ++i) { prob->comps[i].sign = get_binary_prob(NMVcount->comps[i].sign[0], NMVcount->comps[i].sign[1]); branch_ct_sign[i][0] = NMVcount->comps[i].sign[0]; branch_ct_sign[i][1] = NMVcount->comps[i].sign[1]; - vp9_tree_probs_from_distribution(MV_CLASSES, - vp9_mv_class_encodings, - vp9_mv_class_tree, + vp9_tree_probs_from_distribution(vp9_mv_class_tree, prob->comps[i].classes, branch_ct_classes[i], - NMVcount->comps[i].classes); - vp9_tree_probs_from_distribution(CLASS0_SIZE, - vp9_mv_class0_encodings, - vp9_mv_class0_tree, + NMVcount->comps[i].classes, 0); + vp9_tree_probs_from_distribution(vp9_mv_class0_tree, prob->comps[i].class0, branch_ct_class0[i], - NMVcount->comps[i].class0); + NMVcount->comps[i].class0, 0); for (j = 0; j < MV_OFFSET_BITS; ++j) { prob->comps[i].bits[j] = get_binary_prob(NMVcount->comps[i].bits[j][0], NMVcount->comps[i].bits[j][1]); @@ -274,19 +268,15 @@ void vp9_counts_to_nmv_context( } for (i = 0; i < 2; ++i) { for (k = 0; k < CLASS0_SIZE; ++k) { - vp9_tree_probs_from_distribution(4, - vp9_mv_fp_encodings, - vp9_mv_fp_tree, + vp9_tree_probs_from_distribution(vp9_mv_fp_tree, prob->comps[i].class0_fp[k], branch_ct_class0_fp[i][k], - NMVcount->comps[i].class0_fp[k]); + NMVcount->comps[i].class0_fp[k], 0); } - vp9_tree_probs_from_distribution(4, - vp9_mv_fp_encodings, - vp9_mv_fp_tree, + vp9_tree_probs_from_distribution(vp9_mv_fp_tree, prob->comps[i].fp, branch_ct_fp[i], - NMVcount->comps[i].fp); + NMVcount->comps[i].fp, 0); } if (usehp) { for (i = 0; i < 2; ++i) { diff --git a/vp9/common/vp9_treecoder.c b/vp9/common/vp9_treecoder.c index fbc8a38cd..6e2597954 100644 --- a/vp9/common/vp9_treecoder.c +++ b/vp9/common/vp9_treecoder.c @@ -48,66 +48,37 @@ void vp9_tokens_from_tree_offset(struct vp9_token_struct *p, vp9_tree t, tree2tok(p - offset, t, 0, 0, 0); } -static void branch_counts( - int n, /* n = size of alphabet */ - vp9_token tok [ /* n */ ], - vp9_tree tree, - unsigned int branch_ct [ /* n-1 */ ] [2], - const unsigned int num_events[ /* n */ ] -) { - const int tree_len = n - 1; - int t = 0; - -#if CONFIG_DEBUG - assert(tree_len); -#endif - - do { - branch_ct[t][0] = branch_ct[t][1] = 0; - } while (++t < tree_len); - - t = 0; - - do { - int L = tok[t].Len; - const int enc = tok[t].value; - const unsigned int ct = num_events[t]; - - vp9_tree_index i = 0; - - do { - const int b = (enc >> --L) & 1; - const int j = i >> 1; -#if CONFIG_DEBUG - assert(j < tree_len && 0 <= L); -#endif - - branch_ct [j] [b] += ct; - i = tree[ i + b]; - } while (i > 0); - -#if CONFIG_DEBUG - assert(!L); -#endif - } while (++t < n); - +static unsigned int convert_distribution(unsigned int i, + vp9_tree tree, + vp9_prob probs[], + unsigned int branch_ct[][2], + const unsigned int num_events[], + unsigned int tok0_offset) { + unsigned int left, right; + + if (tree[i] <= 0) { + left = num_events[-tree[i] - tok0_offset]; + } else { + left = convert_distribution(tree[i], tree, probs, branch_ct, + num_events, tok0_offset); + } + if (tree[i + 1] <= 0) { + right = num_events[-tree[i + 1] - tok0_offset]; + } else { + right = convert_distribution(tree[i + 1], tree, probs, branch_ct, + num_events, tok0_offset); + } + probs[i>>1] = get_binary_prob(left, right); + branch_ct[i>>1][0] = left; + branch_ct[i>>1][1] = right; + return left + right; } - void vp9_tree_probs_from_distribution( - int n, /* n = size of alphabet */ - vp9_token tok [ /* n */ ], vp9_tree tree, vp9_prob probs [ /* n-1 */ ], unsigned int branch_ct [ /* n-1 */ ] [2], - const unsigned int num_events[ /* n */ ] -) { - const int tree_len = n - 1; - int t = 0; - - branch_counts(n, tok, tree, branch_ct, num_events); - - do { - probs[t] = get_binary_prob(branch_ct[t][0], branch_ct[t][1]); - } while (++t < tree_len); + const unsigned int num_events[ /* n */ ], + unsigned int tok0_offset) { + convert_distribution(0, tree, probs, branch_ct, num_events, tok0_offset); } diff --git a/vp9/common/vp9_treecoder.h b/vp9/common/vp9_treecoder.h index f9f1d135e..9297d5280 100644 --- a/vp9/common/vp9_treecoder.h +++ b/vp9/common/vp9_treecoder.h @@ -47,12 +47,11 @@ void vp9_tokens_from_tree_offset(struct vp9_token_struct *, vp9_tree, taken for each node on the tree; this facilitiates decisions as to probability updates. */ -void vp9_tree_probs_from_distribution(int n, /* n = size of alphabet */ - vp9_token tok[ /* n */ ], - vp9_tree tree, +void vp9_tree_probs_from_distribution(vp9_tree tree, vp9_prob probs[ /* n - 1 */ ], unsigned int branch_ct[ /* n - 1 */ ][2], - const unsigned int num_events[ /* n */ ]); + const unsigned int num_events[ /* n */ ], + unsigned int tok0_offset); static INLINE vp9_prob clip_prob(int p) { return (p > 255) ? 255u : (p < 1) ? 1u : p; diff --git a/vp9/encoder/vp9_bitstream.c b/vp9/encoder/vp9_bitstream.c index b05da870c..fcbd3a1d6 100644 --- a/vp9/encoder/vp9_bitstream.c +++ b/vp9/encoder/vp9_bitstream.c @@ -110,8 +110,8 @@ static void update_mode( unsigned int new_b = 0, old_b = 0; int i = 0; - vp9_tree_probs_from_distribution(n--, tok, tree, - Pnew, bct, num_events); + vp9_tree_probs_from_distribution(tree, Pnew, bct, num_events, 0); + n--; do { new_b += cost_branch(bct[i], Pnew[i]); @@ -167,10 +167,9 @@ static void update_switchable_interp_probs(VP9_COMP *cpi, int i, j; for (j = 0; j <= VP9_SWITCHABLE_FILTERS; ++j) { vp9_tree_probs_from_distribution( - VP9_SWITCHABLE_FILTERS, - vp9_switchable_interp_encodings, vp9_switchable_interp_tree, + vp9_switchable_interp_tree, pc->fc.switchable_interp_prob[j], branch_ct, - cpi->switchable_interp_count[j]); + cpi->switchable_interp_count[j], 0); for (i = 0; i < VP9_SWITCHABLE_FILTERS - 1; ++i) { if (pc->fc.switchable_interp_prob[j][i] < 1) pc->fc.switchable_interp_prob[j][i] = 1; @@ -1189,11 +1188,10 @@ static void build_tree_distribution(vp9_coeff_probs *coef_probs, for (l = 0; l < PREV_COEF_CONTEXTS; ++l) { if (l >= 3 && k == 0) continue; - vp9_tree_probs_from_distribution(MAX_ENTROPY_TOKENS, - vp9_coef_encodings, vp9_coef_tree, + vp9_tree_probs_from_distribution(vp9_coef_tree, coef_probs[i][j][k][l], coef_branch_ct[i][j][k][l], - coef_counts[i][j][k][l]); + coef_counts[i][j][k][l], 0); #ifdef ENTROPY_STATS if (!cpi->dummy_packing) for (t = 0; t < MAX_ENTROPY_TOKENS; ++t) -- 2.40.0