diff options
Diffstat (limited to 'media/libvpx/libvpx/vp8/common/treecoder.c')
-rw-r--r-- | media/libvpx/libvpx/vp8/common/treecoder.c | 102 |
1 files changed, 102 insertions, 0 deletions
diff --git a/media/libvpx/libvpx/vp8/common/treecoder.c b/media/libvpx/libvpx/vp8/common/treecoder.c new file mode 100644 index 0000000000..f1e78f4321 --- /dev/null +++ b/media/libvpx/libvpx/vp8/common/treecoder.c @@ -0,0 +1,102 @@ +/* + * Copyright (c) 2010 The WebM project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include <assert.h> +#include <stdio.h> + +#include "vp8/common/treecoder.h" +#include "vpx/vpx_integer.h" + +static void tree2tok(struct vp8_token_struct *const p, vp8_tree t, int i, int v, + int L) { + v += v; + ++L; + + do { + const vp8_tree_index j = t[i++]; + + if (j <= 0) { + p[-j].value = v; + p[-j].Len = L; + } else { + tree2tok(p, t, j, v, L); + } + } while (++v & 1); +} + +void vp8_tokens_from_tree(struct vp8_token_struct *p, vp8_tree t) { + tree2tok(p, t, 0, 0, 0); +} + +void vp8_tokens_from_tree_offset(struct vp8_token_struct *p, vp8_tree t, + int offset) { + tree2tok(p - offset, t, 0, 0, 0); +} + +static void branch_counts(int n, /* n = size of alphabet */ + vp8_token tok[/* n */], vp8_tree tree, + unsigned int branch_ct[/* n-1 */][2], + const unsigned int num_events[/* n */]) { + const int tree_len = n - 1; + int t = 0; + + assert(tree_len); + + do { + branch_ct[t][0] = branch_ct[t][1] = 0; + } while (++t < tree_len); + + t = 0; + + do { + int L = tok[t].Len; + const int enc = tok[t].value; + const unsigned int ct = num_events[t]; + + vp8_tree_index i = 0; + + do { + const int b = (enc >> --L) & 1; + const int j = i >> 1; + assert(j < tree_len && 0 <= L); + + branch_ct[j][b] += ct; + i = tree[i + b]; + } while (i > 0); + + assert(!L); + } while (++t < n); +} + +void vp8_tree_probs_from_distribution(int n, /* n = size of alphabet */ + vp8_token tok[/* n */], vp8_tree tree, + vp8_prob probs[/* n-1 */], + unsigned int branch_ct[/* n-1 */][2], + const unsigned int num_events[/* n */], + unsigned int Pfactor, int Round) { + const int tree_len = n - 1; + int t = 0; + + branch_counts(n, tok, tree, branch_ct, num_events); + + do { + const unsigned int *const c = branch_ct[t]; + const unsigned int tot = c[0] + c[1]; + + if (tot) { + const unsigned int p = + (unsigned int)(((uint64_t)c[0] * Pfactor) + (Round ? tot >> 1 : 0)) / + tot; + probs[t] = p < 256 ? (p ? p : 1) : 255; /* agree w/old version for now */ + } else { + probs[t] = vp8_prob_half; + } + } while (++t < tree_len); +} |