vp8/common/treecoder.h

   1 /*
   2  *  Copyright (c) 2010 The VP8 project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license and patent
   5  *  grant that can be found in the LICENSE file in the root of the source
   6  *  tree. All contributing project authors may be found in the AUTHORS
   7  *  file in the root of the source tree.
   8  */
   9
  10
  11 #ifndef __INC_TREECODER_H
  12 #define __INC_TREECODER_H
  13
  14 typedef unsigned char vp8bc_index_t; // probability index
  15
  16
  17 typedef unsigned char vp8_prob;
  18
  19 #define vp8_prob_half ( (vp8_prob) 128)
  20
  21 typedef signed char vp8_tree_index;
  22 struct bool_coder_spec;
  23
  24 typedef struct bool_coder_spec bool_coder_spec;
  25 typedef struct bool_writer bool_writer;
  26 typedef struct bool_reader bool_reader;
  27
  28 typedef const bool_coder_spec c_bool_coder_spec;
  29 typedef const bool_writer c_bool_writer;
  30 typedef const bool_reader c_bool_reader;
  31
  32
  33
  34 # define vp8_complement( x) (255 - x)
  35
  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
  47 typedef const struct vp8_token_struct
  48 {
  49     int value;
  50     int Len;
  51 } vp8_token;
  52
  53 /* Construct encoding array from tree. */
  54
  55 void vp8_tokens_from_tree(struct vp8_token_struct *, vp8_tree);
  56
  57
  58 /* Convert array of token occurrence counts into a table of probabilities
  59    for the associated binary encoding tree.  Also writes count of branches
  60    taken for each node on the tree; this facilitiates decisions as to
  61    probability updates. */
  62
  63 void vp8_tree_probs_from_distribution(
  64     int n,                      /* n = size of alphabet */
  65     vp8_token tok               [ /* n */ ],
  66     vp8_tree tree,
  67     vp8_prob probs          [ /* n-1 */ ],
  68     unsigned int branch_ct       [ /* n-1 */ ] [2],
  69     const unsigned int num_events[ /* n */ ],
  70     unsigned int Pfactor,
  71     int Round
  72 );
  73
  74 /* Variant of above using coder spec rather than hardwired 8-bit probs. */
  75
  76 void vp8bc_tree_probs_from_distribution(
  77     int n,                      /* n = size of alphabet */
  78     vp8_token tok               [ /* n */ ],
  79     vp8_tree tree,
  80     vp8_prob probs          [ /* n-1 */ ],
  81     unsigned int branch_ct       [ /* n-1 */ ] [2],
  82     const unsigned int num_events[ /* n */ ],
  83     c_bool_coder_spec *s
  84 );
  85
  86
  87 #endif