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