ebcot_decoder.h

JPEG2000 EBCOT算法源码

/*****************************************************************************/
/* File name: "ebcot_decoder.h"                                              */
/* Author: David Taubman                                                     */
/* Copyright 1998, Hewlett-Packard Company                                   */
/* All rights reserved                                                       */
/*****************************************************************************/
#ifndef EBCOT_DECODER_H
#define EBCOT_DECODER_H
#include <line_block_ifc.h>
#include <ebcot_common.h>
#include <ebcot_constants.h>


/* ========================================================================= */
/* ----------------------- Compressed Bit-Stream Heap ---------------------- */
/* ========================================================================= */

#define HEAP_WORDS 8
#define HEAP_BYTES (HEAP_WORDS*4)
#define HEAP_GROUP_UNITS 64

/*****************************************************************************/
/*                                  heap_unit                                */
/*****************************************************************************/

typedef
  struct heap_unit {
    std_int words[HEAP_WORDS];
    struct heap_unit *next;
    struct heap_group *group;
  } heap_unit, *heap_unit_ptr;

  /* This structure is used to manage the dynamic memory consumption
     associated with compressed bit-streams.  Heap units are managed
     within larger `heap_group' structures to minimize the impact of
     dynamic memory allocation on implementation efficiency.  The
     `group' field points to the group to which the heap unit belongs.
     If the heap unit is not currently in use, this field is set to
     NULL; it is only set to point to the relevant group once the unit
     is allocated to a client via the `codeword_heap__get_unit' function.
         The `next' field is available to the user and will generally be
     used to create a linked list of heap units which are associated with
     a common store. */

/*****************************************************************************/
/*                                  heap_group                               */
/*****************************************************************************/

typedef
  struct heap_group {
    heap_unit units[HEAP_GROUP_UNITS];
    std_int free_units;
    struct heap_group *next;
  } heap_group, *heap_group_ptr;

  /* This structure is used to allocate and manage multiple heap units
     at once for improved efficiency.  All heap units managed by the
     encoder/decoder are chained via their `next' fields. */

/*****************************************************************************/
/*                                 codeword_heap                             */
/*****************************************************************************/

typedef struct codeword_heap_obj *codeword_heap_ref;

typedef heap_unit_ptr (*codeword_heap__get_unit__func)
  (codeword_heap_ref self);
typedef void (*codeword_heap__return_unit__func)
  (codeword_heap_ref self, heap_unit_ptr unit);
typedef void (*codeword_heap__terminate__func)
  (codeword_heap_ref self);

typedef
  struct codeword_heap_obj {
    codeword_heap__get_unit__func get_unit;
    codeword_heap__return_unit__func return_unit;
    codeword_heap__terminate__func terminate;
    heap_group_ptr heap;
  } codeword_heap_obj;

  /* This structure represents an object in the same style as those defined
     in the public interface header, "line_block_ifc.h", which is responsible
     for managing the codeword heap.  The arithmetic coding engine requires
     a reference to this object. */

/* ========================================================================= */
/* ----------------------------- Arithmetic Coder -------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/*                                context_state                              */
/*****************************************************************************/

typedef std_short context_state, *context_state_ptr;
  /* Each context state is represented by a 16-bit word.  The least significant
     S_BITS bits of this word represent the normalized total symbol count for
     the context state.  The next N_BITS bits of the word represent the
     normalized count of the number of 1's which have been seen in this
     context state.  Generally, N_BITS is much less than S_BITS because we
     do not expect highly skewed probabilities to be skewed towards a the
     symbol 0. */

/*****************************************************************************/
/*                                 arith_state                               */
/*****************************************************************************/

typedef
  struct arith_state {
    std_int A, C, word;
    std_short available_bits;
    context_state_ptr contexts;
    std_int available_bytes;
    heap_unit_ptr heap;
    int next_heap_pos;
#ifdef LOG_SYMBOLS
    FILE *symbol_log;
#endif /* LOG_SYMBOLS */
  } arith_state, *arith_state_ptr;

  /* This structure manages fundamental state information for the arithmetic
     coding engine.
         `A' and `C' are the usual arithmetic decoding state variables,
     corresponding to the normalized interval length and interval lower bound,
     respectively.
         `word' is a 32-bit word which is used to buffer code bits so as
     to avoid excessive access into the main bit-stream store.
         `available_bits' holds the number of bits which can still be
     retrieved from the current `word' buffer before another word must be
     reloaded from the main store.
         `contexts' points to the array of context states which is currently
     in use.  The array itself is managed by the containing `block_master'
     structure, but it is handy to keep a pointer to the array lying around
     here.
         `available_bytes' holds the number of valid bytes which have not yet
     been retrieved from the main store.  Once all valid bytes have been
     retrieved, the `word' buffer must be padded with 1's to ensure correct
     decoding of all relevant symbols.  The number of bytes need not be
     divisible by 4.
         `heap' points to the currently active `heap_unit' structure which
     represents the main store of code bytes.
         `next_heap_pos' identifies the index of the next word within the
     `heap' structure from which the `word' register should be loaded once it
     becomes empty. */

/* ========================================================================= */
/* --------------------------- Quad-Tree Structure ------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/*                                quad_siblings                              */
/*****************************************************************************/

typedef
  struct quad_siblings {
    std_short flags; /* Must be the first field. */
    std_short num_siblings;
    std_short *node_update[4];
  } quad_siblings, *quad_siblings_ptr;

  /* This structure manages the state of four sibling nodes in the
     partial quadtree representation.  It is convenient and efficient to
     treat all four siblings with a common parent at once, rather than to pass
     through each one individually.
         `flags' holds the current state of the set of four siblings.  The
     QUAD_PARENT_SIGNIFICANT flag is set if the parent of the siblings
     has been found to be significant, which means that at least one of the
     siblings must be significant.  The QUAD_NODE_SIGNIFICANT flag is set if
     at least one of the four siblings has already been found to be
     significant.  If we come to the last sibling and QUAD_NODE_SIGNIFICANT is
     still not set, but QUAD_PARENT_SIGNIFICANT is set then that node is known
     to be significant without decoding anything.  The QUAD_LEAVES flag is set
     if the sibling nodes identified here are leaves of the partial quad-tree.
     Leaf nodes are different, because their significance need not be
     propagated further down the tree, but must be reflected in the relevant
     `code_subblock' structure.
       In addition to these three special flags, the most significant four
     bits of the `flags' word identify whether or not the state of each of
     the four siblings has yet to be decoded.  In particular, the most
     significant bit of the `flags' word holds 0 if the first sibling's state
     is still unknown and 1 if it is known.  Similarly, the next most
     significant bit holds the state of the second sibling and so forth.
     Siblings which are not feasible (i.e. their state is irrelevant) should
     have the relevant flag bit set from the outset.
         `num_siblings' identifies the number of feasible sibling nodes which
     are contained within the block.  This number may not exceed 4, but it
     might be less at boundary blocks.
         `node_update' has one entry for each node, which holds the address
     of a short integer whose value should be updated by OR'ing it with the
     QUAD_PARENT_SIGNIFICANT macro, if the relevant node transitions from
     insignificant to significant.  In practice, the relevant update word
     is always the first field of either a `quad_siblings' structure
     (non-leaf nodes) or a `code_subblock' structure (leaf nodes). */

/* ========================================================================= */
/* -------------------------- Block Coding Structure ----------------------- */
/* ========================================================================= */

/*****************************************************************************/
/*                                code_subblock                              */
/*****************************************************************************/

typedef
  struct code_subblock {
    std_short significant; /* Must be the first field. */
    int offset;
    int top_row, left_col, rows, cols;
  } code_subblock, *code_subblock_ptr;

  /* This structure defines a sub-block within the larger code block.  The
     actual decoding algorithm scans an array of these structures, skipping
     all entries which are insignificant and decoding the samples which belong
     to the significant sub-blocks.
         `significant' is non-zero if and only if the sub-block has been found
     to be significant in the current or previous bit-planes.
         `offset' holds the amount by which the context and sample buffers
     passed to the coding engine should be incremented in order to obtain
     the address of the first context word and sample value for the sub-block.
         `top_row' and `left_col' identify the upper left hand corner or the
     sub-block, in relation to the upper left hand corner of the containing
     code block.
         `rows' and `cols' hold the dimensions of the sub-block.  These may
     take on unexpected values near image boundaries. */

/*****************************************************************************/
/*                                 block_master                              */
/*****************************************************************************/

typedef
  struct block_master {
    int max_dim, max_sub_dim, row_gap;