media/libvpx/vp8/common/treecoder.c

   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 }