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
12#ifndef VP8_ENCODER_TREEWRITER_H_
13#define VP8_ENCODER_TREEWRITER_H_
14
15/* Trees map alphabets into huffman-like codes suitable for an arithmetic
16   bit coder.  Timothy S Murphy  11 October 2004 */
17
18#include "vp8/common/treecoder.h"
19
20#include "boolhuff.h"       /* for now */
21
22#ifdef __cplusplus
23extern "C" {
24#endif
25
26typedef BOOL_CODER vp8_writer;
27
28#define vp8_write vp8_encode_bool
29#define vp8_write_literal vp8_encode_value
30#define vp8_write_bit( W, V) vp8_write( W, V, vp8_prob_half)
31
32#define vp8bc_write vp8bc_write_bool
33#define vp8bc_write_literal vp8bc_write_bits
34#define vp8bc_write_bit( W, V) vp8bc_write_bits( W, V, 1)
35
36
37/* Approximate length of an encoded bool in 256ths of a bit at given prob */
38
39#define vp8_cost_zero( x) ( vp8_prob_cost[x])
40#define vp8_cost_one( x)  vp8_cost_zero( vp8_complement(x))
41
42#define vp8_cost_bit( x, b) vp8_cost_zero( (b)?  vp8_complement(x) : (x) )
43
44/* VP8BC version is scaled by 2^20 rather than 2^8; see bool_coder.h */
45
46
47/* Both of these return bits, not scaled bits. */
48
49static unsigned int vp8_cost_branch(const unsigned int ct[2], vp8_prob p)
50{
51    /* Imitate existing calculation */
52
53    return ((ct[0] * vp8_cost_zero(p))
54            + (ct[1] * vp8_cost_one(p))) >> 8;
55}
56
57/* Small functions to write explicit values and tokens, as well as
58   estimate their lengths. */
59
60static void vp8_treed_write
61(
62    vp8_writer *const w,
63    vp8_tree t,
64    const vp8_prob *const p,
65    int v,
66    int n               /* number of bits in v, assumed nonzero */
67)
68{
69    vp8_tree_index i = 0;
70
71    do
72    {
73        const int b = (v >> --n) & 1;
74        vp8_write(w, b, p[i>>1]);
75        i = t[i+b];
76    }
77    while (n);
78}
79static void vp8_write_token
80(
81    vp8_writer *const w,
82    vp8_tree t,
83    const vp8_prob *const p,
84    vp8_token *const x
85)
86{
87    vp8_treed_write(w, t, p, x->value, x->Len);
88}
89
90static int vp8_treed_cost(
91    vp8_tree t,
92    const vp8_prob *const p,
93    int v,
94    int n               /* number of bits in v, assumed nonzero */
95)
96{
97    int c = 0;
98    vp8_tree_index i = 0;
99
100    do
101    {
102        const int b = (v >> --n) & 1;
103        c += vp8_cost_bit(p[i>>1], b);
104        i = t[i+b];
105    }
106    while (n);
107
108    return c;
109}
110static int vp8_cost_token
111(
112    vp8_tree t,
113    const vp8_prob *const p,
114    vp8_token *const x
115)
116{
117    return vp8_treed_cost(t, p, x->value, x->Len);
118}
119
120/* Fill array of costs for all possible token values. */
121
122void vp8_cost_tokens(
123    int *Costs, const vp8_prob *, vp8_tree
124);
125
126void vp8_cost_tokens2(
127    int *Costs, const vp8_prob *, vp8_tree, int
128);
129
130#ifdef __cplusplus
131}  // extern "C"
132#endif
133
134#endif  // VP8_ENCODER_TREEWRITER_H_
135