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