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 #if CONFIG_DEBUG
     13 #include <assert.h>
     14 #endif
     15 #include <stdio.h>
     16 
     17 #include "treecoder.h"
     18 
     19 static void tree2tok(
     20     struct vp8_token_struct *const p,
     21     vp8_tree t,
     22     int i,
     23     int v,
     24     int L
     25 )
     26 {
     27     v += v;
     28     ++L;
     29 
     30     do
     31     {
     32         const vp8_tree_index j = t[i++];
     33 
     34         if (j <= 0)
     35         {
     36             p[-j].value = v;
     37             p[-j].Len = L;
     38         }
     39         else
     40             tree2tok(p, t, j, v, L);
     41     }
     42     while (++v & 1);
     43 }
     44 
     45 void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t)
     46 {
     47     tree2tok(p, t, 0, 0, 0);
     48 }
     49 
     50 void vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t,
     51                                  int offset)
     52 {
     53     tree2tok(p - offset, t, 0, 0, 0);
     54 }
     55 
     56 static void branch_counts(
     57     int n,                      /* n = size of alphabet */
     58     vp8_token tok               [ /* n */ ],
     59     vp8_tree tree,
     60     unsigned int branch_ct       [ /* n-1 */ ] [2],
     61     const unsigned int num_events[ /* n */ ]
     62 )
     63 {
     64     const int tree_len = n - 1;
     65     int t = 0;
     66 
     67 #if CONFIG_DEBUG
     68     assert(tree_len);
     69 #endif
     70 
     71     do
     72     {
     73         branch_ct[t][0] = branch_ct[t][1] = 0;
     74     }
     75     while (++t < tree_len);
     76 
     77     t = 0;
     78 
     79     do
     80     {
     81         int L = tok[t].Len;
     82         const int enc = tok[t].value;
     83         const unsigned int ct = num_events[t];
     84 
     85         vp8_tree_index i = 0;
     86 
     87         do
     88         {
     89             const int b = (enc >> --L) & 1;
     90             const int j = i >> 1;
     91 #if CONFIG_DEBUG
     92             assert(j < tree_len  &&  0 <= L);
     93 #endif
     94 
     95             branch_ct [j] [b] += ct;
     96             i = tree[ i + b];
     97         }
     98         while (i > 0);
     99 
    100 #if CONFIG_DEBUG
    101         assert(!L);
    102 #endif
    103     }
    104     while (++t < n);
    105 
    106 }
    107 
    108 
    109 void vp8_tree_probs_from_distribution(
    110     int n,                      /* n = size of alphabet */
    111     vp8_token tok               [ /* n */ ],
    112     vp8_tree tree,
    113     vp8_prob probs          [ /* n-1 */ ],
    114     unsigned int branch_ct       [ /* n-1 */ ] [2],
    115     const unsigned int num_events[ /* n */ ],
    116     unsigned int Pfac,
    117     int rd
    118 )
    119 {
    120     const int tree_len = n - 1;
    121     int t = 0;
    122 
    123     branch_counts(n, tok, tree, branch_ct, num_events);
    124 
    125     do
    126     {
    127         const unsigned int *const c = branch_ct[t];
    128         const unsigned int tot = c[0] + c[1];
    129 
    130 #if CONFIG_DEBUG
    131         assert(tot < (1 << 24));        /* no overflow below */
    132 #endif
    133 
    134         if (tot)
    135         {
    136             const unsigned int p = ((c[0] * Pfac) + (rd ? tot >> 1 : 0)) / tot;
    137             probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */
    138         }
    139         else
    140             probs[t] = vp8_prob_half;
    141     }
    142     while (++t < tree_len);
    143 }
    144