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