media/libvpx/vp8/common/treecoder.c@6474c204b198
media/libvpx/vp8/common/treecoder.c
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
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 */
12 #if CONFIG_DEBUG
13 #include <assert.h>
14 #endif
15 #include <stdio.h>
17 #include "treecoder.h"
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;
30 do
31 {
32 const vp8_tree_index j = t[i++];
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 }
45 void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t)
46 {
47 tree2tok(p, t, 0, 0, 0);
48 }
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 }
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;
67 #if CONFIG_DEBUG
68 assert(tree_len);
69 #endif
71 do
72 {
73 branch_ct[t][0] = branch_ct[t][1] = 0;
74 }
75 while (++t < tree_len);
77 t = 0;
79 do
80 {
81 int L = tok[t].Len;
82 const int enc = tok[t].value;
83 const unsigned int ct = num_events[t];
85 vp8_tree_index i = 0;
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
95 branch_ct [j] [b] += ct;
96 i = tree[ i + b];
97 }
98 while (i > 0);
100 #if CONFIG_DEBUG
101 assert(!L);
102 #endif
103 }
104 while (++t < n);
106 }
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;
123 branch_counts(n, tok, tree, branch_ct, num_events);
125 do
126 {
127 const unsigned int *const c = branch_ct[t];
128 const unsigned int tot = c[0] + c[1];
130 #if CONFIG_DEBUG
131 assert(tot < (1 << 24)); /* no overflow below */
132 #endif
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 }
