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
tree2tok(struct vp8_token_struct * const p,vp8_tree t,int i,int v,int L)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
vp8_tokens_from_tree(struct vp8_token_struct * p,vp8_tree t)45 void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t)
46 {
47 tree2tok(p, t, 0, 0, 0);
48 }
49
vp8_tokens_from_tree_offset(struct vp8_token_struct * p,vp8_tree t,int offset)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
branch_counts(int n,vp8_token tok[],vp8_tree tree,unsigned int branch_ct[][2],const unsigned int num_events[])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
vp8_tree_probs_from_distribution(int n,vp8_token tok[],vp8_tree tree,vp8_prob probs[],unsigned int branch_ct[][2],const unsigned int num_events[],unsigned int Pfac,int rd)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