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