ebcot_send_bits.h

JPEG2000 EBCOT算法源码

/*****************************************************************************/
/* File name: "ebcot_send_bits.h"                                            */
/* Author: David Taubman                                                     */
/* Copyright 1998, Hewlett-Packard Company                                   */
/* All rights reserved                                                       */
/*****************************************************************************/
#ifndef EBCOT_SEND_BITS_H
#define EBCOT_SEND_BITS_H
#include "ebcot_encoder.h"

/* ========================================================================= */
/* -------------------------------- Tag Trees ------------------------------ */
/* ========================================================================= */

/*****************************************************************************/
/*                                tag_tree_node                              */
/*****************************************************************************/

typedef
  struct tag_tree_node {
    int value;
    int lower_bound;
    int value_known;
    struct tag_tree_node *child;
    struct tag_tree_node *parent;
  } tag_tree_node, *tag_tree_node_ptr;

  /* This structure represents a single node in a tag tree.  Tag trees are
     always navigated from the leaves to the root so the entire tree may be
     accessed by knowing where all the leaves are (see definition of the
     `tag_tree' structure) and knowing each leaf's parent.  The `parent'
     field enables this navigation.
         The process of sending tag bits is driven from the leaves.
     Specifically, a request arrives to send tag bits for a given leaf to
     represent whether or not the leaf's `value' field is less than some
     threshold, T.  The request is propagated up the tree to the root, leaving
     behind `child' pointers in order to allow the path from the leaf
     to be retraced.  In each non-leaf node, the `value' field holds the
     minimum of the `value' fields in all descendant nodes.  During coding,
     the following steps are taken:
       For each node in the path to the leaf, starting from the root of the
       tree, do the following:
         a) while (`lower_bound' < T) and (`lower_bound < `value')
            -> send a 0 bit
            -> increment `lower_bound' by 1.
         b) if (`lower_bound' < T) and (`value_known' is false)
            -> send a 1 bit
            -> set `value_known' to true.
         c) Set the child node's `lower_bound' field equal to the current
            `lower_bound' value.
     This algorithm has the effect of encoding whether or not any given leaf
     is less than an arbitrary threshold, T, and, if it is less than T,
     encoding the actual value.  Moreover, the algorithm avoids redundancy as
     the threshold and leaf which we are interested in are arbitrary selected
     in subsequent coding steps.  It is a highly generalized quad-tree
     coding algorithm, which is particularly useful in coding the tag
     information we want to insert into our bit-stream.
         During initialization, the `lower_bound' field of each node is set
     to 0; the `value_known' flag is set to 0 (false); and the `value'
     field is set to INT_MAX. */


/* ========================================================================= */
/* ------------------------------ Tag Buffering ---------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/*                                 tag_buffer                                */
/*****************************************************************************/

typedef
  struct tag_buffer {
    std_byte byte;
    int available_bits;
    int stored_bytes;
    int max_stored_bytes;
    std_byte *store;
  } tag_buffer, *tag_buffer_ptr;

  /* This structure is provided to manage the buffering of tag information
     for writing into the bit-stream.  Tags are buffered in a dynamically
     growing array, which is byte oriented and padded, until the point
     comes to actually write the block of tag information into the bit-stream.
     We generally keep tag information for an entire resolution level in
     the wavelet transform together.
         `byte' is used to accumulate the next byte of tag information.  The
     number of bit positions which have not yet been written is identified by
     the `available_bits' field.
         `store' points to an array with `max_stored_bytes' elements, of which
     `stored_bytes' currently hold valid entries.  The array may occasionally
     need to be reallocated if initial sizing is found to be insufficient. */

/* ========================================================================= */
/* ---------------------------- External Functions ------------------------- */
/* ========================================================================= */

extern void
  ebcot_send_bit_stream(the_encoder_ref self);

#endif /* EBCOT_SEND_BITS_H */