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 #include <assert.h>
12 #include <stdio.h>
13
14 #include "vp8/common/treecoder.h"
15
tree2tok(struct vp8_token_struct * const p,vp8_tree t,int i,int v,int L)16 static void tree2tok(struct vp8_token_struct *const p, vp8_tree t, int i, int v,
17 int L) {
18 v += v;
19 ++L;
20
21 do {
22 const vp8_tree_index j = t[i++];
23
24 if (j <= 0) {
25 p[-j].value = v;
26 p[-j].Len = L;
27 } else {
28 tree2tok(p, t, j, v, L);
29 }
30 } while (++v & 1);
31 }
32
vp8_tokens_from_tree(struct vp8_token_struct * p,vp8_tree t)33 void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t) {
34 tree2tok(p, t, 0, 0, 0);
35 }
36
vp8_tokens_from_tree_offset(struct vp8_token_struct * p,vp8_tree t,int offset)37 void vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t,
38 int offset) {
39 tree2tok(p - offset, t, 0, 0, 0);
40 }
41
branch_counts(int n,vp8_token tok[],vp8_tree tree,unsigned int branch_ct[][2],const unsigned int num_events[])42 static void branch_counts(int n, /* n = size of alphabet */
43 vp8_token tok[/* n */], vp8_tree tree,
44 unsigned int branch_ct[/* n-1 */][2],
45 const unsigned int num_events[/* n */]) {
46 const int tree_len = n - 1;
47 int t = 0;
48
49 assert(tree_len);
50
51 do {
52 branch_ct[t][0] = branch_ct[t][1] = 0;
53 } while (++t < tree_len);
54
55 t = 0;
56
57 do {
58 int L = tok[t].Len;
59 const int enc = tok[t].value;
60 const unsigned int ct = num_events[t];
61
62 vp8_tree_index i = 0;
63
64 do {
65 const int b = (enc >> --L) & 1;
66 const int j = i >> 1;
67 assert(j < tree_len && 0 <= L);
68
69 branch_ct[j][b] += ct;
70 i = tree[i + b];
71 } while (i > 0);
72
73 assert(!L);
74 } while (++t < n);
75 }
76
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)77 void vp8_tree_probs_from_distribution(int n, /* n = size of alphabet */
78 vp8_token tok[/* n */], vp8_tree tree,
79 vp8_prob probs[/* n-1 */],
80 unsigned int branch_ct[/* n-1 */][2],
81 const unsigned int num_events[/* n */],
82 unsigned int Pfac, int rd) {
83 const int tree_len = n - 1;
84 int t = 0;
85
86 branch_counts(n, tok, tree, branch_ct, num_events);
87
88 do {
89 const unsigned int *const c = branch_ct[t];
90 const unsigned int tot = c[0] + c[1];
91
92 assert(tot < (1 << 24)); /* no overflow below */
93
94 if (tot) {
95 const unsigned int p = ((c[0] * Pfac) + (rd ? tot >> 1 : 0)) / tot;
96 probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */
97 } else {
98 probs[t] = vp8_prob_half;
99 }
100 } while (++t < tree_len);
101 }
102