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_COMMON_TREECODER_H_
13 #define VP8_COMMON_TREECODER_H_
14 
15 #ifdef __cplusplus
16 extern "C" {
17 #endif
18 
19 typedef unsigned char vp8bc_index_t; /* probability index */
20 
21 
22 typedef unsigned char vp8_prob;
23 
24 #define vp8_prob_half ( (vp8_prob) 128)
25 
26 typedef signed char vp8_tree_index;
27 struct bool_coder_spec;
28 
29 typedef struct bool_coder_spec bool_coder_spec;
30 typedef struct bool_writer bool_writer;
31 typedef struct bool_reader bool_reader;
32 
33 typedef const bool_coder_spec c_bool_coder_spec;
34 typedef const bool_writer c_bool_writer;
35 typedef const bool_reader c_bool_reader;
36 
37 
38 
39 # define vp8_complement( x) (255 - x)
40 
41 
42 /* We build coding trees compactly in arrays.
43    Each node of the tree is a pair of vp8_tree_indices.
44    Array index often references a corresponding probability table.
45    Index <= 0 means done encoding/decoding and value = -Index,
46    Index > 0 means need another bit, specification at index.
47    Nonnegative indices are always even;  processing begins at node 0. */
48 
49 typedef const vp8_tree_index vp8_tree[], *vp8_tree_p;
50 
51 
52 typedef const struct vp8_token_struct
53 {
54     int value;
55     int Len;
56 } vp8_token;
57 
58 /* Construct encoding array from tree. */
59 
60 void vp8_tokens_from_tree(struct vp8_token_struct *, vp8_tree);
61 void vp8_tokens_from_tree_offset(struct vp8_token_struct *, vp8_tree,
62                                  int offset);
63 
64 
65 /* Convert array of token occurrence counts into a table of probabilities
66    for the associated binary encoding tree.  Also writes count of branches
67    taken for each node on the tree; this facilitiates decisions as to
68    probability updates. */
69 
70 void vp8_tree_probs_from_distribution(
71     int n,                      /* n = size of alphabet */
72     vp8_token tok               [ /* n */ ],
73     vp8_tree tree,
74     vp8_prob probs          [ /* n-1 */ ],
75     unsigned int branch_ct       [ /* n-1 */ ] [2],
76     const unsigned int num_events[ /* n */ ],
77     unsigned int Pfactor,
78     int Round
79 );
80 
81 /* Variant of above using coder spec rather than hardwired 8-bit probs. */
82 
83 void vp8bc_tree_probs_from_distribution(
84     int n,                      /* n = size of alphabet */
85     vp8_token tok               [ /* n */ ],
86     vp8_tree tree,
87     vp8_prob probs          [ /* n-1 */ ],
88     unsigned int branch_ct       [ /* n-1 */ ] [2],
89     const unsigned int num_events[ /* n */ ],
90     c_bool_coder_spec *s
91 );
92 
93 
94 #ifdef __cplusplus
95 }  // extern "C"
96 #endif
97 
98 #endif  // VP8_COMMON_TREECODER_H_
99