/* * 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 "vpx_config.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);}
/*
* 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 "vpx_config.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);
}