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