ebcot_send_bits.c

JPEG2000实现的源码

/*****************************************************************************/
/* Copyright 1998, Hewlett-Packard Company                                   */
/* All rights reserved                                                       */
/* File: "ebcot_send_bits.c"                                                 */
/* Description: Manages rate control and bit-stream construction for the     */
/*              EBCOT encoder; used only once all code blocks in the image   */
/*              have been compressed.                                        */
/* Author: David Taubman                                                     */
/* Affiliation: Hewlett-Packard and                                          */
/*              The University of New South Wales, Australia                 */
/* Version: VM9.0                                                            */
/* Last Revised: 26 April, 2001                                              */
/*****************************************************************************/

/*****************************************************************************/
/* Modified by David Taubman to support new termination methods for parallel */
/* coding options.  Copyright 1999 by Hewlett-Packard Company with all       */
/* rights reserved for the modified parts.                                   */
/*****************************************************************************/

/*****************************************************************************/
/* Modified to combine entropy coders                                        */
/* Copyright 1999 Science Applications International Corporation (SAIC).     */
/* Copyright 1999 University of Arizona, Arizona Board of Regents.           */
/* All Rights Reserved for modified parts.                                   */
/*****************************************************************************/

/* RSV mjg - Portions Modifided Copyright 1999, Ricoh Silicon Valley         */

/*****************************************************************************/
/* Modified by David Taubman to support interface modifications, arbitrary   */
/* changes in coding parameters from component to component and from tile    */
/* to tile, packet partitions, rich packet sequencing conventions and to     */
/* support the full generality of PART-1 of the JPEG2000                     */
/* standard, and to support most anticipated generality of PART-2.  Changes  */
/* are too numerous to flag individually within the code, which in some      */
/* places has been completely rewritten.  All changes copyrighted by HP with */
/* all rights reserved for the modified parts.                               */
/*****************************************************************************/

/*****************************************************************************/
/* Modified by David Taubman to implement changes in Tokyo between CD and    */
/* FCD for Part-1 of the standard.  Copyrighted by HP with all rights        */
/* reserved for the modified parts.                                          */
/*****************************************************************************/

/*****************************************************************************/
/* Modified to incorporate scan based rate control.  Material identified  by */
/* "CRIL Technology/SAIC Scan Buffer" comments has been added by Fabrice     */
/* Pelleau and Olivier Duffez of CRIL Technology and Tom Flohr of SAIC.      */
/* Copyright 2000 CRIL Technology                                            */
/* Copyright 2000 CNES                                                       */
/* Copyright 2000 Science Applications International Corporation (SAIC).     */
/* All Rights Reserved for modified parts.                                   */
/*****************************************************************************/

/*****************************************************************************/
/* Modified for general wavelet decompositions.                              */
/* Copyright 2000 Science Applications International Corporation (SAIC).     */
/* Copyright 1995 University of Arizona, Arizona Board of Regents.           */
/* All Rights Reserved for modified parts.                                   */
/*****************************************************************************/

/*****************************************************************************/
/* Modified by David Taubman to incorporate changes to the POC marker (used  */
/* to be POD).  Changes are quite extensive and not always explicitly        */
/* When flagged, the relevant comment string is "DST POC mod".               */
/* Generally, any reference to tile-parts (e.g. through variable names       */
/* containing the string `tpart' are part of this modification, since the    */
/* compressor did not previously need to be tile-part aware.                 */
/* Copyright 2000 The University of New South Wales.                         */
/* All rights reserved for the modified parts.                               */
/*****************************************************************************/

#include <local_services.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <ifc.h>
#include "ebcot_encoder.h"
#include "ebcot_send_bits.h"
#include "ebcot_vpw.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(EBCOT_MEM_KEY,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(EBCOT_MEM_KEY,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&1);               \
    if ((--_buffer->available_bits) == 0)                                    \
      {                                                                      \
        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;             \
        if (_buffer->byte == 0xFF)                                           \
          _buffer->available_bits = 7;                                       \
        else                                                                 \
          _buffer->available_bits = 8;                                       \
        _buffer->byte = 0;                                                   \
      }                                                                      \
  }

/*****************************************************************************/
/* 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) & 1);
        }
      if (buffer->available_bits == 0)
        {
          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;
          if (buffer->byte == 0xFF)
            buffer->available_bits = 7;
          else
            buffer->available_bits = 8;
          buffer->byte = 0;
        }
    }
}

/*****************************************************************************/
/* 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, stream_out_ref stream)
{
  int num_bytes;

  assert(buffer->available_bits == 0);
  num_bytes = buffer->stored_bytes;
  if (num_bytes)
    stream->push_head_bytes(stream,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                      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. */

{
  if (tree == NULL)
    return;
  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. */

{
  if (src == NULL)
    {
      assert(dest == NULL);
      return;
    }
  src--; dest--;
  do {