1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libvpx/vp8/common/treecoder.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,143 @@
1.4 +/*
1.5 + * Copyright (c) 2010 The WebM project authors. All Rights Reserved.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license
1.8 + * that can be found in the LICENSE file in the root of the source
1.9 + * tree. An additional intellectual property rights grant can be found
1.10 + * in the file PATENTS. All contributing project authors may
1.11 + * be found in the AUTHORS file in the root of the source tree.
1.12 + */
1.13 +
1.14 +
1.15 +#if CONFIG_DEBUG
1.16 +#include <assert.h>
1.17 +#endif
1.18 +#include <stdio.h>
1.19 +
1.20 +#include "treecoder.h"
1.21 +
1.22 +static void tree2tok(
1.23 + struct vp8_token_struct *const p,
1.24 + vp8_tree t,
1.25 + int i,
1.26 + int v,
1.27 + int L
1.28 +)
1.29 +{
1.30 + v += v;
1.31 + ++L;
1.32 +
1.33 + do
1.34 + {
1.35 + const vp8_tree_index j = t[i++];
1.36 +
1.37 + if (j <= 0)
1.38 + {
1.39 + p[-j].value = v;
1.40 + p[-j].Len = L;
1.41 + }
1.42 + else
1.43 + tree2tok(p, t, j, v, L);
1.44 + }
1.45 + while (++v & 1);
1.46 +}
1.47 +
1.48 +void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t)
1.49 +{
1.50 + tree2tok(p, t, 0, 0, 0);
1.51 +}
1.52 +
1.53 +void vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t,
1.54 + int offset)
1.55 +{
1.56 + tree2tok(p - offset, t, 0, 0, 0);
1.57 +}
1.58 +
1.59 +static void branch_counts(
1.60 + int n, /* n = size of alphabet */
1.61 + vp8_token tok [ /* n */ ],
1.62 + vp8_tree tree,
1.63 + unsigned int branch_ct [ /* n-1 */ ] [2],
1.64 + const unsigned int num_events[ /* n */ ]
1.65 +)
1.66 +{
1.67 + const int tree_len = n - 1;
1.68 + int t = 0;
1.69 +
1.70 +#if CONFIG_DEBUG
1.71 + assert(tree_len);
1.72 +#endif
1.73 +
1.74 + do
1.75 + {
1.76 + branch_ct[t][0] = branch_ct[t][1] = 0;
1.77 + }
1.78 + while (++t < tree_len);
1.79 +
1.80 + t = 0;
1.81 +
1.82 + do
1.83 + {
1.84 + int L = tok[t].Len;
1.85 + const int enc = tok[t].value;
1.86 + const unsigned int ct = num_events[t];
1.87 +
1.88 + vp8_tree_index i = 0;
1.89 +
1.90 + do
1.91 + {
1.92 + const int b = (enc >> --L) & 1;
1.93 + const int j = i >> 1;
1.94 +#if CONFIG_DEBUG
1.95 + assert(j < tree_len && 0 <= L);
1.96 +#endif
1.97 +
1.98 + branch_ct [j] [b] += ct;
1.99 + i = tree[ i + b];
1.100 + }
1.101 + while (i > 0);
1.102 +
1.103 +#if CONFIG_DEBUG
1.104 + assert(!L);
1.105 +#endif
1.106 + }
1.107 + while (++t < n);
1.108 +
1.109 +}
1.110 +
1.111 +
1.112 +void vp8_tree_probs_from_distribution(
1.113 + int n, /* n = size of alphabet */
1.114 + vp8_token tok [ /* n */ ],
1.115 + vp8_tree tree,
1.116 + vp8_prob probs [ /* n-1 */ ],
1.117 + unsigned int branch_ct [ /* n-1 */ ] [2],
1.118 + const unsigned int num_events[ /* n */ ],
1.119 + unsigned int Pfac,
1.120 + int rd
1.121 +)
1.122 +{
1.123 + const int tree_len = n - 1;
1.124 + int t = 0;
1.125 +
1.126 + branch_counts(n, tok, tree, branch_ct, num_events);
1.127 +
1.128 + do
1.129 + {
1.130 + const unsigned int *const c = branch_ct[t];
1.131 + const unsigned int tot = c[0] + c[1];
1.132 +
1.133 +#if CONFIG_DEBUG
1.134 + assert(tot < (1 << 24)); /* no overflow below */
1.135 +#endif
1.136 +
1.137 + if (tot)
1.138 + {
1.139 + const unsigned int p = ((c[0] * Pfac) + (rd ? tot >> 1 : 0)) / tot;
1.140 + probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */
1.141 + }
1.142 + else
1.143 + probs[t] = vp8_prob_half;
1.144 + }
1.145 + while (++t < tree_len);
1.146 +}
