vp8/common/treecoder.c

/*
 *  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.
 */


#if CONFIG_DEBUG
#include <assert.h>
#endif
#include <stdio.h>

#include "treecoder.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;

#if CONFIG_DEBUG
    assert(tree_len);
#endif

    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;
#if CONFIG_DEBUG
            assert(j < tree_len  &&  0 <= L);
#endif

            branch_ct [j] [b] += ct;
            i = tree[ i + b];
        }
        while (i > 0);

#if CONFIG_DEBUG
        assert(!L);
#endif
    }
    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 Pfac,
    int rd
)
{
    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 CONFIG_DEBUG
        assert(tot < (1 << 24));        /* no overflow below */
#endif

        if (tot)
        {
            const unsigned int p = ((c[0] * Pfac) + (rd ? 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);
}