ebcot_receive_bits.c

JPEG2000 EBCOT算法源码

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


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

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

static tag_buffer_ptr
  create_tag_buffer(bitstream_source_ref source, jmp_buf *except)
{
  tag_buffer_ptr result;

  result = (tag_buffer_ptr) local_malloc(sizeof(tag_buffer));
  result->byte = 0;
  result->available_bits = 0;
  result->retrieved_bytes = 0;
  result->source = source;
  result->except = except;
  return(result);
}

/*****************************************************************************/
/* MACRO                        tag_buffer__pull_bit                         */
/*****************************************************************************/

#define tag_buffer__pull_bit(_buffer,_val)                                   \
    /* tag_buffer_ptr _buffer, int/short/byte _val. */                       \
  {                                                                          \
    if (_buffer->available_bits == 0)                                        \
      {                                                                      \
        if (!(_buffer->source->pull_bytes(_buffer->source,                   \
                                          &(_buffer->byte),1)))              \
          longjmp(*(_buffer->except),1);                                     \
        _buffer->available_bits = 8;                                         \
        _buffer->retrieved_bytes++;                                          \
      }                                                                      \
    _val = (std_byte)((_buffer->byte >> 7) & 1);                             \
    _buffer->byte <<= 1;                                                     \
    _buffer->available_bits--;                                               \
  }

/*****************************************************************************/
/* STATIC                      tag_buffer__pull_bits                         */
/*****************************************************************************/

static std_int
  tag_buffer__pull_bits(tag_buffer_ptr buffer, int num_bits)

 /* This function retrieves `num_bits' bits from the tag buffer and
    returns them as the least significant bits of the returned 32-bit
    word.  The least significant bit of the returned word is the last of
    the `num_bits' retrieved.  The `num_bits' value must not exceed 31. */

{
  std_int result;
  int n;

  assert(num_bits <= 31);
  result = 0;
  while (num_bits > 0)
    {
      if (buffer->available_bits == 0)
        {
          if (!(buffer->source->pull_bytes(buffer->source,&(buffer->byte),1)))
            longjmp(*(buffer->except),1);
          buffer->available_bits = 8;
          buffer->retrieved_bytes++;
        }
      n = num_bits;
      if (n > buffer->available_bits)
        {
          n = buffer->available_bits;
          num_bits -= n;
          buffer->available_bits = 0;
        }
      else
        {
          num_bits = 0;
          buffer->available_bits -= n;
        }
      while (n--)
        {
          result = (result << 1) | ((buffer->byte >> 7) & 1);
          buffer->byte <<= 1;
        }
    }
  return(result);
}

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

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

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

static void
  tag_buffer__destroy(tag_buffer_ptr buffer)
{
  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->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__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->child = NULL;
  } while (tree->parent != NULL);
}

/*****************************************************************************/
/* STATIC                       tag_tree__decode                             */
/*****************************************************************************/

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

 /* Retrieves and decodes sufficient tag bits to determine 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 completely
    decoded and may be retrieved later by directly accessing the `value'
    field of `leaf'.  Values which are greater than or equal to the
    threshold remain unknown.  The function returns 1 if the leaf's value is
    less than the threshold and 0 otherwise. */

{
  tag_tree_node_ptr node;
  int result, bit, lower_bound;

  assert(threshold > 0);
  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__pull_bit(target,bit);
          if (bit)
            node->value = lower_bound;
          else
            lower_bound++;
        }
      node->lower_bound = lower_bound;
    }
  result = (leaf->value < threshold);
  return(result);
}

/* ========================================================================= */
/* ------------------------ Bitstream Layer Management --------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                    recover_bitstream_layer                         */
/*****************************************************************************/

static int
  recover_bitstream_layer(level_info_ptr level, int layer_idx,
                          tag_buffer_ptr tags, bitstream_source_ref input,
                          codeword_heap_ref code_mgr)

 /* This function recovers a new layer from the bit-stream, where the
    new layer is known to represent code blocks from the indicated
    resolution level.  The function updates all relevant fields of the
    affected `block_info' structures in preparation for coding.  It
    returns the number of bytes which were retrieved from the bit-stream.
    If the bit-stream terminates prematurely, while tag information for
    the new layer is being recovered, the function will not explicitly
    return, but control will be returned to the point at which the
    `except' information was installed in the `tags' object.  The fact that
    the function has no opportunity does not create any problems in this
    case, since none of the information recovered while reading tags is
    of any use without the code bytes themselves, which follow, so the