ebcot_send_bits.c

JPEG2000 EBCOT算法源码

/*****************************************************************************/
/* File name: "ebcot_send_bits.c"                                            */
/* Author: David Taubman                                                     */
/* Copyright 1998, Hewlett-Packard Company                                   */
/* All rights reserved                                                       */
/*****************************************************************************/
#include <local_heap.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include "ebcot_encoder.h"
#include "ebcot_send_bits.h"

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

/*****************************************************************************/
/* STATIC                        create_tag_buffer                           */
/*****************************************************************************/

static tag_buffer_ptr
  create_tag_buffer(void)
{
  tag_buffer_ptr result;

  result = (tag_buffer_ptr) local_malloc(sizeof(tag_buffer));
  result->byte = 0;
  result->available_bits = 8;
  result->stored_bytes = 0;
  result->max_stored_bytes = 32;
  result->store = (std_byte *)
    local_malloc((size_t)(result->max_stored_bytes));
  return(result);
}

/*****************************************************************************/
/* MACRO                        tag_buffer__push_bit                         */
/*****************************************************************************/

#define tag_buffer__push_bit(_buffer,_val)                                   \
    /* tag_buffer_ptr _buffer, int _val (must be 0 or 1). */                 \
  {                                                                          \
    _buffer->byte = (_buffer->byte << 1) | (std_byte) _val;                  \
    if ((--_buffer->available_bits) == 0)                                    \
      {                                                                      \
        _buffer->available_bits = 8;                                         \
        if (_buffer->stored_bytes == _buffer->max_stored_bytes)              \
          {                                                                  \
            _buffer->max_stored_bytes = 1 + (_buffer->max_stored_bytes<<1);  \
            _buffer->store = (std_byte *)                                    \
              local_realloc(_buffer->store,                                  \
                            (size_t)(_buffer->max_stored_bytes));            \
          }                                                                  \
        _buffer->store[_buffer->stored_bytes++] = _buffer->byte;             \
      }                                                                      \
  }

/*****************************************************************************/
/* STATIC                      tag_buffer__push_bits                         */
/*****************************************************************************/

static void
  tag_buffer__push_bits(tag_buffer_ptr buffer, std_int value, int num_bits)

 /* This function pushes the `num_bits' least significant bits of `value'
    into the tag buffer, starting from the most significant bit.  The
    `num_bits' value must not exceed 31. */

{
  int n;

  assert(num_bits <= 31);
  while (num_bits > 0)
    {
      n = num_bits;
      if (n > buffer->available_bits)
        n = buffer->available_bits;
      buffer->available_bits -= n;
      while (n--)
        {
          num_bits--;
          buffer->byte = (buffer->byte << 1) | (value >> num_bits);
        }
      if (buffer->available_bits == 0)
        {
          buffer->available_bits = 8;
          if (buffer->stored_bytes == buffer->max_stored_bytes)
            {
              buffer->max_stored_bytes = 1 + (buffer->max_stored_bytes<<1);
              buffer->store = (std_byte *)
                local_realloc(buffer->store,
                              (size_t)(buffer->max_stored_bytes));
            }
          buffer->store[buffer->stored_bytes++] = buffer->byte; 
        }
    }
}

/*****************************************************************************/
/* STATIC                        tag_buffer__reset                           */
/*****************************************************************************/

static void
  tag_buffer__reset(tag_buffer_ptr buffer)
{
  buffer->byte = 0;
  buffer->available_bits = 8;
  buffer->stored_bytes = 0;
}

/*****************************************************************************/
/* STATIC                        tag_buffer__flush                           */
/*****************************************************************************/

static int
  tag_buffer__flush(tag_buffer_ptr buffer)

 /* Flushes the contents of the working byte into the byte store and
    returns the total number of stored bytes.  This function must be
    called prior to output. */

{
  if (buffer->available_bits == 8)
    buffer->available_bits = 0; /* Marks buffer as flushed. */
  if (buffer->available_bits > 0)
    {
      while (buffer->available_bits > 0)
        { buffer->byte <<= 1; buffer->available_bits--; }
      if (buffer->stored_bytes == buffer->max_stored_bytes)
        {
          buffer->max_stored_bytes = 1 + (buffer->max_stored_bytes<<1);
          buffer->store = (std_byte *)
            local_realloc(buffer->store,
                          (size_t)(buffer->max_stored_bytes));
        }
      buffer->store[buffer->stored_bytes++] = buffer->byte;
    }
  return(buffer->stored_bytes);
}

/*****************************************************************************/
/* STATIC                        tag_buffer__output                          */
/*****************************************************************************/

static void
  tag_buffer__output(tag_buffer_ptr buffer, bitstream_sink_ref output)
{
  int num_bytes;

  assert(buffer->available_bits == 0);
  num_bytes = buffer->stored_bytes;
  if (num_bytes)
    output->push_bytes(output,buffer->store,num_bytes);
}

/*****************************************************************************/
/* STATIC                       tag_buffer__destroy                          */
/*****************************************************************************/

static void
  tag_buffer__destroy(tag_buffer_ptr buffer)
{
  local_free(buffer->store);
  local_free(buffer);
}


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

/*****************************************************************************/
/* STATIC                        create_tag_tree                             */
/*****************************************************************************/

static tag_tree_node_ptr
  create_tag_tree(int rows, int cols)

 /* Creates a tag-tree with an array of `rows'*`cols' leaf nodes, returning
    a pointer to the top-left hand corner leaf node (the leaf nodes appear
    at the head of the returned array, in scan-line order). */

{
  tag_tree_node_ptr result, node, parents;
  int elts, new_elts, next_rows, next_cols, r, c;

  elts = 0;
  next_rows = rows;
  next_cols = cols;
  do {
    new_elts = next_rows*next_cols;
    elts += new_elts;
    next_rows = (1+next_rows)>>1;
    next_cols = (1+next_cols)>>1;
  } while (new_elts > 1);
  result = node = (tag_tree_node_ptr)
    local_malloc(sizeof(tag_tree_node)*(size_t) elts);
  do {
    elts = rows*cols;
    parents = node + elts;
    if (elts == 1)
      parents = NULL;
    next_rows = (1+rows)>>1;
    next_cols = (1+cols)>>1;
    for (r=0; r < rows; r++)
      for (c=0; c < cols; c++, node++)
        {
          node->value = INT_MAX;
          node->lower_bound = 0;
          node->value_known = 0;
          node->child = NULL;
          node->parent = NULL;
          if (parents != NULL)
            node->parent = parents + ((r>>1)*next_cols + (c>>1));
        }
    rows = next_rows;
    cols = next_cols;
  } while (elts > 1);
  return(result);
}

/*****************************************************************************/
/* STATIC                      tag_tree__set_value                           */
/*****************************************************************************/

static void
  tag_tree__set_value(tag_tree_node_ptr leaf, int value)

 /* Sets the value of the supplied leaf node and propagates the information
    up the tree to higher level nodes, which hold the minimum of their
    descendant node values.  Must be called separately for each leaf node.
    It is not strictly necessary to set the value for all leaf nodes, since
    the initial state of the tree (after reset) is such as to ensure that
    all nodes have the maximum possible value.  Generally speaking one
    must be careful about coding leaves before setting values, however, the
    emitted code will be properly decodable provided any encoding steps
    work with thresholds which are no larger than any new value which is
    later set into a leaf node.  This property of the tag tree is exploited
    in the generation of inclusion masks for blocks within each subband. */

{
  assert(value >= 0);
  do {
    if (value < leaf->value)
      leaf->value = value;
    else
      break; /* No need to propagate up the tree. */
    leaf = leaf->parent;
  } while (leaf != NULL);
}

/*****************************************************************************/
/* STATIC                       tag_tree__reset                              */
/*****************************************************************************/

static void
  tag_tree__reset(tag_tree_node_ptr tree)

 /* Resets all values and lower bounds for the supplied tree. */

{
  tree--;
  do {
    tree++;
    tree->value = INT_MAX;
    tree->lower_bound = 0;
    tree->value_known = 0;
    tree->child = NULL;
  } while (tree->parent != NULL);
}

/*****************************************************************************/
/* STATIC                        tag_tree__copy                              */
/*****************************************************************************/

static void
  tag_tree__copy(tag_tree_node_ptr src, tag_tree_node_ptr dest)

 /* Copies values and bounds from the `src' tree to the `dest' tree. */

{
  src--; dest--;
  do {
    src++; dest++;
    dest->value = src->value;
    dest->lower_bound = src->lower_bound;
    dest->value_known = src->value_known;
  } while (src->parent != NULL);
  assert(dest->parent == NULL);
}

/*****************************************************************************/
/* STATIC                       tag_tree__encode                             */
/*****************************************************************************/

static int
  tag_tree__encode(tag_tree_node_ptr leaf, int threshold,
                   tag_buffer_ptr target)

 /* Encodes whether or not the `leaf' node's value is less than the supplied
    threshold.  In the process, values which are less than the threshold are
    explicitly coded.  Returns 1 if the value is less than the threshold and
    0 otherwise.  Encoded bits are pushed into the `target' tag stream
    manager, which collects the tag codes into bytes for outputting as
    a single block of tags later on. */

{
  tag_tree_node_ptr node;
  int lower_bound, result;

  assert(threshold > 0);
  result = 1; /* Prevent compiler warnings. */
  for (node=leaf; node->parent != NULL; node=node->parent)
    node->parent->child = node;
  for (lower_bound=0; node != NULL; node=node->child)
    {
      if (lower_bound > node->lower_bound)
        node->lower_bound = lower_bound;
      else
        lower_bound = node->lower_bound;
      assert(lower_bound <= node->value);
      while ((lower_bound < threshold) && (lower_bound < node->value))
        {
          tag_buffer__push_bit(target,0);
          lower_bound++;
        }
      result = lower_bound < threshold;
      if (result && !node->value_known)
        {
          tag_buffer__push_bit(target,1);
          node->value_known = 1;
        }
      node->lower_bound = lower_bound;
    }
  assert((result && (leaf->value < threshold)) ||
         ((!result) && (leaf->value >= threshold)));
  return(result);
}

/* ========================================================================= */
/* ------------------------ Bitstream Layer Creation ----------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                      form_bitstream_layer                          */
/*****************************************************************************/

static int
  form_bitstream_layer(level_info_ptr level, std_int rd_threshold,
                       bitstream_sink_ref output, int layer_idx,
                       int include_makeup_passes, tag_buffer_ptr tags)

 /* This function forms a new layer in the bit-stream, composed of all
    coding passes for all blocks in the identified level, whose `rd_slope'
    value is greater than or equal to the `rd_threshold' value, and which
    have not already been included in a bit-stream layer.
        If `output' is non-NULL, the bit-stream formed in this way will be
    immediately pushed out to the relevant object.  Otherwise, if `output'
    is NULL, nothing will be output, and the bit-stream layer formation
    process will be simulated.
        `layer_idx' identifies the layer within the bit-stream which is
    being formed here.  The first layer should always have a `layer_idx'
    value of 0, which causes appropriate initialization steps to be applied.
    Thereafter, the indices must increase consecutively.  The `layer_idx'
    value is used with each band's inclusion tag tree in an interesting
    and elegant manner to implement an efficient coding of the point at
    which information from any given block is first included in the
    bit-stream.