ebcot_decoder.c

JPEG2000 EBCOT算法源码

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


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

/*****************************************************************************/
/* STATIC                  codeword_heap__get_unit                           */
/*****************************************************************************/

static heap_unit_ptr
  codeword_heap__get_unit(codeword_heap_ref self)
{
  heap_group_ptr scan;
  heap_unit_ptr unit;
  int i;

  for (scan=self->heap; scan != NULL; scan=scan->next)
    if (scan->free_units)
      break;
  if (scan == NULL)
    {
      scan = (heap_group_ptr)
        local_malloc(sizeof(heap_group));
      scan->next = self->heap;
      self->heap = scan;
      scan->free_units = HEAP_GROUP_UNITS;
      for (unit=scan->units, i=HEAP_GROUP_UNITS; i > 0; i--, unit++)
        {
          unit->next = NULL;
          unit->group = NULL;
        }
    }
  for (unit=scan->units, i=HEAP_GROUP_UNITS; i > 0; i--, unit++)
    if (unit->group == NULL)
      break;
  assert(i > 0);
  scan->free_units--;
  unit->group = scan;
  unit->next = NULL;
  return(unit);
}

/*****************************************************************************/
/* STATIC                 codeword_heap__return_unit                         */
/*****************************************************************************/

static void
  codeword_heap__return_unit(codeword_heap_ref self, heap_unit_ptr unit)
{
  heap_group_ptr group;

  group = unit->group;
  assert((group != NULL) && (group->free_units < HEAP_GROUP_UNITS));
  group->free_units++;
  unit->group = NULL;
}

/*****************************************************************************/
/* STATIC                  codeword_heap__terminate                          */
/*****************************************************************************/

static void
  codeword_heap__terminate(codeword_heap_ref self)
{
  heap_group_ptr tmp;

  while ((tmp=self->heap) != NULL)
    {
      self->heap = tmp->next;
      local_free(tmp);
    }
  local_free(self);
}

/*****************************************************************************/
/* STATIC                     create_codeword_heap                           */
/*****************************************************************************/

static codeword_heap_ref
  create_codeword_heap(void)
{
  codeword_heap_ref result;

  result = (codeword_heap_ref) local_malloc(sizeof(codeword_heap_obj));
  memset(result,0,sizeof(codeword_heap_obj));
  result->get_unit = codeword_heap__get_unit;
  result->return_unit = codeword_heap__return_unit;
  result->terminate = codeword_heap__terminate;
  return(result);
}

/* ========================================================================= */
/* -------------------- Configuration Utility Functions -------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                      start_symbol_log                              */
/*****************************************************************************/
#ifdef LOG_SYMBOLS
static FILE *
  start_symbol_log(band_info_ptr band, block_info_ptr block)
{
  FILE *fp;
  char fname[81];

  sprintf(fname,"symbol_log_%d_%d_%d",band->level_idx,band->band_idx,
          (int)(block-band->blocks));
  fp = fopen(fname,"rb");
  assert(fp != NULL);
  return(fp);
}
#endif /* LOG_SYMBOLS */

/*****************************************************************************/
/* STATIC                    get_block_dimensions                            */
/*****************************************************************************/

static void
  get_block_dimensions(the_decoder_ref self)
{
  int dim, sub_dim;
  std_byte byte;

  self->input->pull_bytes(self->input,&byte,1);
  dim = (byte==0)?256:((int) byte);
  self->input->pull_bytes(self->input,&byte,1);
  sub_dim = (byte==0)?256:((int) byte);
  assert((dim >= sub_dim) && ((dim & 3) == 0) && ((sub_dim & 3) == 0));
  self->master.max_dim = dim;
  self->master.max_sub_dim = sub_dim;
  self->input->pull_bytes(self->input,&byte,1);
  dim = (byte==0)?256:((int) byte);
  assert(dim <= self->master.max_dim);
  self->max_block_height = dim;
  self->extra_header_bytes += 3;
}

/*****************************************************************************/
/* STATIC                       get_layer_info                               */
/*****************************************************************************/

static void
  get_layer_info(the_decoder_ref self)
{
  std_byte byte;

  if (!self->input->pull_bytes(self->input,&byte,1))
    {
      fprintf(stderr,"Bit-stream terminated prematurely while reading "
              "critical header info!\n");
      exit(-1);
    }
  self->bitstream_layers = (byte==0)?256:((int) byte);
  self->extra_header_bytes += 1;
}

/*****************************************************************************/
/* STATIC                      create_quadtree                               */
/*****************************************************************************/

static void
  create_quadtree(int height, int width, code_subblock_ptr subblocks,
                  quad_siblings_ptr *first_entry,
                  quad_siblings_ptr *last_entry)

 /* Builds the quad-tree structure for a tree whose base measures
    `height' by `width'.  The base does not need to be square, nor do
    its dimensions need to be powers of 2.  Returns the head and tail of the
    array which represents the quad-tree via the `first_entry' and
    `last_entry' arguments. */

{
  int rows, cols, last_rows, last_cols, elts, leaves;
  int r, c, r_node, c_node, r_child, c_child, n, idx;
  quad_siblings_ptr head, tail, last_start, start, qp;

  rows = height; cols = width; elts = 0;
  while ((rows > 1) || (cols > 1))
    {
      rows = 1 + ((rows-1)>>1);
      cols = 1 + ((cols-1)>>1);
      elts += rows*cols;
    }
  if (elts == 0)
    {
      *first_entry = *last_entry = NULL;
      return;
    }
  head = (quad_siblings_ptr)
    local_malloc(sizeof(quad_siblings)*(size_t) elts);
  tail = head + (elts-1);
  last_start = tail + 1;
  last_rows = height; last_cols = width; leaves = 1;
  while ((last_rows > 1) || (last_cols > 1))
    {
      rows = 1 + ((last_rows-1)>>1);
      cols = 1 + ((last_cols-1)>>1);
      elts = rows*cols;
      start = last_start - elts;
      for (qp=start, r=0; r < rows; r++)
        for (c=0; c < cols; c++, qp++)
          {
            qp->flags = (leaves)?QUAD_LEAVES:0;
            qp->num_siblings = 0; /* Actual value will be set before coding. */
            for (n=0, r_node=0; r_node < 2; r_node++)
              for (c_node=0; c_node < 2; c_node++, n++)
                {
                  r_child = 2*r + r_node;
                  c_child = 2*c + c_node;
                  idx = r_child * last_cols + c_child;
                  if ((r_child >= last_rows) || (c_child >= last_cols))
                    qp->node_update[n] = NULL; /* Illegal node. */
                  else if (leaves)
                    qp->node_update[n] = (std_short *)(subblocks + idx);
                  else
                    qp->node_update[n] = (std_short *)(last_start + idx);
                }
          }
      leaves = 0;
      last_start = start;
      last_rows = rows;
      last_cols = cols;
    }
  assert(last_start == head);
  *first_entry = head;
  *last_entry = tail;
}

/* ========================================================================= */
/* --------------------------- Decoding Functions -------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                    transpose_sample_buffer                         */
/*****************************************************************************/

static void
  transpose_sample_buffer(ifc_int *src, ifc_int *dest,
                          int src_rows, int src_cols, int row_gap)

 /* Transposes the array in `src', copying the result to `dest'.  The source
    buffer has the indicated dimensions and for both buffers, the separation
    between rows is `row_gap', which must of course be no less than the
    maximum of `src_rows' and `src_cols'. */

{
  int r, c;
  ifc_int *sp, *dp, *spp, *dpp;

  assert((row_gap >= src_rows) && (row_gap >= src_cols));
  for (spp=src, dpp=dest, r=src_rows; r > 0; r--, spp+=row_gap, dpp++)
    for (sp=spp, dp=dpp, c=src_cols; c > 0; c--, sp++, dp+=row_gap)
      *dp = *sp;
}

/*****************************************************************************/
/* STATIC                      initialize_quadtree                           */
/*****************************************************************************/

static void
  initialize_quadtree(block_master_ptr master)

 /* Initializes the array of `quad_siblings' structures which runs from
    `first_quad' to `last_quad' in the `master' structure, to work with
    a `block_rows'x`block_cols' array of sample values. */

{
  quad_siblings_ptr scan;
  int num_siblings, b;
  std_short feasible_pos;

  if (master->first_quad == NULL)
    { /* Empty quad-tree case. */
      assert(master->first_subblock == master->last_subblock);
      return;
    }

  for (scan=master->last_quad; scan >= master->first_quad; scan--)
    if (scan->flags & QUAD_LEAVES)
      {
        scan->flags = QUAD_LEAVES; /* Reset all other flags. */
        for (feasible_pos=15, num_siblings=b=0; b < 4; b++, feasible_pos--)
          {
            code_subblock_ptr subblock;

            subblock = (code_subblock_ptr)(scan->node_update[b]);
            if ((subblock == NULL) ||
                (subblock->rows <= 0) || (subblock->cols <= 0))
              { scan->flags |= (1<<feasible_pos); continue; }
            num_siblings++;
          }
        scan->num_siblings = num_siblings;
      }
    else
      {
        scan->flags = 0; /* Reset flags. */
        for (feasible_pos=15, num_siblings=b=0; b < 4; b++, feasible_pos--)
          {
            quad_siblings_ptr child;

            child = (quad_siblings_ptr)(scan->node_update[b]);
            if ((child == NULL) || (child->num_siblings == 0))
              { scan->flags |= (1<<feasible_pos); continue; }
            num_siblings++;
          }
        scan->num_siblings = num_siblings;
      }
}

/*****************************************************************************/
/* STATIC                        decode_quadtree                             */
/*****************************************************************************/

static void
  decode_quadtree(block_master_ptr master)

 /* Decodes the new quad-tree information for the current bit-plane (as
    identified by `master'->bit_plane). */

{
  quad_siblings_ptr scan, end;
  arith_state_ptr state;
  std_int A, C, word;
  std_short avail, symbol, flags, feasible_pos;
  int n;

  scan = master->first_quad;
  end = master->last_quad;
  if (scan == NULL)
    return; /* Nothing to do.  No quad-tree in use. */
  state = &(master->coder_state);
  A=state->A; C=state->C; word=state->word; avail=state->available_bits;
  for (; scan <= end; scan++)
    {
      flags = scan->flags;
      if (!(flags & QUAD_PARENT_SIGNIFICANT))
        continue;
      if (!(flags & QUAD_NODE_SIGNIFICANT))
        { /* First time through. */
          int num_siblings;

          num_siblings = scan->num_siblings;
          for (feasible_pos=15, n=0; n < 4; n++, feasible_pos--)
            if (((flags >> feasible_pos) & 1) == 0)
              { /* Otherwise, the node is not a valid sibling. */
                num_siblings--;
                if ((num_siblings > 0) || (flags & QUAD_NODE_SIGNIFICANT))
                  { /* Significance of node must be coded. */
                    get_uniform_symbol(state,A,C,word,avail,symbol);
                  }
                else
                  { /* Node must be significant. */
                    symbol = 1;
                  }
                if (symbol)
                  {
                    flags |= (1<<feasible_pos) | QUAD_NODE_SIGNIFICANT;
                    *(scan->node_update[n]) |= QUAD_PARENT_SIGNIFICANT;
                  }
              }
          assert(flags & QUAD_NODE_SIGNIFICANT);
        }