ref: 78cbe51bc304d177ce5790ba4eab46a00f1d4084
dir: /vp8/common/treecoder.c/
/* * Copyright (c) 2010 The WebM project authors. All Rights Reserved. * * Use of this source code is governed by a BSD-style license * that can be found in the LICENSE file in the root of the source * tree. An additional intellectual property rights grant can be found * in the file PATENTS. All contributing project authors may * be found in the AUTHORS file in the root of the source tree. */ #if CONFIG_DEBUG #include <assert.h> #endif #include <stdio.h> #include "treecoder.h" static void tree2tok( struct vp8_token_struct *const p, vp8_tree t, int i, int v, int L ) { v += v; ++L; do { const vp8_tree_index j = t[i++]; if (j <= 0) { p[-j].value = v; p[-j].Len = L; } else tree2tok(p, t, j, v, L); } while (++v & 1); } void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t) { tree2tok(p, t, 0, 0, 0); } void vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t, int offset) { tree2tok(p - offset, t, 0, 0, 0); } static void branch_counts( int n, /* n = size of alphabet */ vp8_token tok [ /* n */ ], vp8_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]; vp8_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); } void vp8_tree_probs_from_distribution( int n, /* n = size of alphabet */ vp8_token tok [ /* n */ ], vp8_tree tree, vp8_prob probs [ /* n-1 */ ], unsigned int branch_ct [ /* n-1 */ ] [2], const unsigned int num_events[ /* n */ ], unsigned int Pfac, int rd ) { const int tree_len = n - 1; int t = 0; branch_counts(n, tok, tree, branch_ct, num_events); do { const unsigned int *const c = branch_ct[t]; const unsigned int tot = c[0] + c[1]; #if CONFIG_DEBUG assert(tot < (1 << 24)); /* no overflow below */ #endif if (tot) { const unsigned int p = ((c[0] * Pfac) + (rd ? tot >> 1 : 0)) / tot; probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */ } else probs[t] = vp8_prob_half; } while (++t < tree_len); }