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
19static 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
45void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t)
46{
47    tree2tok(p, t, 0, 0, 0);
48}
49
50void 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
56static 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
109void 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