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