Home | History | Annotate | Download | only in common 
      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 
     12 #include <assert.h>
     13 
     14 #include "./vpx_config.h"
     15 #include "vp9/common/vp9_treecoder.h"
     16 
     17 static void tree2tok(struct vp9_token *const p, vp9_tree t,
     18                     int i, int v, int l) {
     19   v += v;
     20   ++l;
     21 
     22   do {
     23     const vp9_tree_index j = t[i++];
     24 
     25     if (j <= 0) {
     26       p[-j].value = v;
     27       p[-j].len = l;
     28     } else
     29       tree2tok(p, t, j, v, l);
     30   } while (++v & 1);
     31 }
     32 
     33 void vp9_tokens_from_tree(struct vp9_token *p, vp9_tree t) {
     34   tree2tok(p, t, 0, 0, 0);
     35 }
     36 
     37 void vp9_tokens_from_tree_offset(struct vp9_token *p, vp9_tree t,
     38                                  int offset) {
     39   tree2tok(p - offset, t, 0, 0, 0);
     40 }
     41 
     42 static unsigned int convert_distribution(unsigned int i,
     43                                          vp9_tree tree,
     44                                          vp9_prob probs[],
     45                                          unsigned int branch_ct[][2],
     46                                          const unsigned int num_events[],
     47                                          unsigned int tok0_offset) {
     48   unsigned int left, right;
     49 
     50   if (tree[i] <= 0) {
     51     left = num_events[-tree[i] - tok0_offset];
     52   } else {
     53     left = convert_distribution(tree[i], tree, probs, branch_ct,
     54                                 num_events, tok0_offset);
     55   }
     56   if (tree[i + 1] <= 0)
     57     right = num_events[-tree[i + 1] - tok0_offset];
     58   else
     59     right = convert_distribution(tree[i + 1], tree, probs, branch_ct,
     60                                  num_events, tok0_offset);
     61 
     62   probs[i>>1] = get_binary_prob(left, right);
     63   branch_ct[i>>1][0] = left;
     64   branch_ct[i>>1][1] = right;
     65   return left + right;
     66 }
     67 
     68 void vp9_tree_probs_from_distribution(
     69   vp9_tree tree,
     70   vp9_prob probs          [ /* n-1 */ ],
     71   unsigned int branch_ct       [ /* n-1 */ ] [2],
     72   const unsigned int num_events[ /* n */ ],
     73   unsigned int tok0_offset) {
     74   convert_distribution(0, tree, probs, branch_ct, num_events, tok0_offset);
     75 }
     76