ebcot_encoder.h

JPEG2000 EBCOT算法源码

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

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

#define HEAP_WORDS 64
#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, rho, word;
    std_short available_bits;
    context_state_ptr contexts;
    std_int saved_words;
    heap_unit_ptr heap;
    int next_heap_pos;
    codeword_heap_ref code_heap_mgr;
#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 separate copy of this structure is maintained in the
     `block_master' structure for every pass through a given block, whose
     results are saved (there may be up to MAX_SAVED_PASSES of these); this
     enables the number of bytes required to uniquely decode all the symbols
     in any given pass to be computed later once the relevant code bits have
     been output for subsequent passes.  Note that the number of bytes
     required to uniquely decode one pass has a slight dependence on what is
     coded in subsequent passes.
         `A', `C' and `rho' are the usual arithmetic coding state variables,
     corresponding to the normalized interval length, interval lower bound
     and carry influence size, 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 pushed
     into the current `word' buffer before it overflows.
         `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.
         `saved_words' holds the number of full words which have actually been
     saved to the heap store since the arithmetic coder was initialized, during
     normal encoding.
         `heap' points to the currently active `heap_unit' structure which is
     being used to store code words.
         `next_heap_pos' identifies the index of the next word within the
     `heap' structure into which the `word' register should be written once it
     is full.
         `code_heap_mgr' references the object which should be used to obtain
     additional heap units if necessary. */

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

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

typedef
  struct quad_siblings {
    std_short flags; /* Must be the first field. */
    std_short num_siblings;
    ifc_int nodes[4];
    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, but this might not yet have been encoded
     into the bit-stream.  The QUAD_NODE_SIGNIFICANT flag is set if at least
     one of the four siblings has already been found to be significant and
     this fact has been encoded.  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 and there is no need to
     encode 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.
         `num_siblings' identifies the number of sibling nodes which are
     contained within the block.  This number may not exceed 4, but it might
     be less at boundary blocks.
         `nodes' holds the inclusive OR of the 15 or 31 magnitude bits,
     depending upon the value of the IMPLEMENTATION_PRECISION macro, from all
     samples represented by each of the four sibling nodes.  The most
     significant bit of each word is used to mark whether or not the
     relevant node has yet been found to be significant.  Nodes which have
     not yet been found to be significant have a 0 bit in that place, whereas
     all other nodes have 1 in the most significant bit (i.e. the value is
     negative).  If a node does not lie within the region of support of the
     block (usually at boundary blocks), the corresponding entry will be
     marked with as having been found to be significant from the outset so
     that it can be skipped.
         `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 encoding algorithm scans an array of these structures, skipping
     all entries which are insignificant and coding 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;
    code_subblock_ptr first_subblock, last_subblock;
    ifc_int bit_idx;
    ifc_int block_mag;
    std_short *block_update;
    quad_siblings_ptr first_quad, last_quad;
    std_short *context_buffer;
    ifc_int *sample_buffer;
    arith_state coder_state;
    std_byte *zc_lut;
    std_short context_mask;
    context_state contexts[TOTAL_CONTEXTS];
    arith_state saved_states[MAX_PASSES];