vp8/common/treecoder.h

   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 __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 void vp8_tokens_from_tree_offset(struct vp8_token_struct *, vp8_tree,
  58                                  int offset);
  59
  60
  61 /* Convert array of token occurrence counts into a table of probabilities
  62    for the associated binary encoding tree.  Also writes count of branches
  63    taken for each node on the tree; this facilitiates decisions as to
  64    probability updates. */
  65
  66 void vp8_tree_probs_from_distribution(
  67     int n,                      /* n = size of alphabet */
  68     vp8_token tok               [ /* n */ ],
  69     vp8_tree tree,
  70     vp8_prob probs          [ /* n-1 */ ],
  71     unsigned int branch_ct       [ /* n-1 */ ] [2],
  72     const unsigned int num_events[ /* n */ ],
  73     unsigned int Pfactor,
  74     int Round
  75 );
  76
  77 /* Variant of above using coder spec rather than hardwired 8-bit probs. */
  78
  79 void vp8bc_tree_probs_from_distribution(
  80     int n,                      /* n = size of alphabet */
  81     vp8_token tok               [ /* n */ ],
  82     vp8_tree tree,
  83     vp8_prob probs          [ /* n-1 */ ],
  84     unsigned int branch_ct       [ /* n-1 */ ] [2],
  85     const unsigned int num_events[ /* n */ ],
  86     c_bool_coder_spec *s
  87 );
  88
  89
  90 #endif