ebcot_send_bits.c

JPEG2000 EBCOT算法源码

        If `include_makeup_passes' is non-zero (true), the function includes
    the additional number of coding passes identified by each block's
    `makeup_passes' field.
        The `tags' argument supplies a `tag_buffer' object which may be
    used to manage the buffering of tag bits during the layer formation
    process.
        The function returns the actual number of bytes which are required
    to represent the new bit-stream layer, regardless of whether or not
    `output' is NULL. */

{
  band_info_ptr band;
  block_info_ptr block;
  int b, m, k, tag_val, extra_passes;
  int total_bytes, block_bytes, max_block_pass_bytes;

  total_bytes = 0;
  tag_buffer__reset(tags);
  tag_buffer__push_bit(tags,1); /* Indicates that the layer is in use. */
  for (b=level->min_band; b <= level->max_band; b++)
    {
      band = level->bands + b;
      if (layer_idx == 0)
        {
          band->byte_count_bits = 3; /* Minimum number of bits for
                                        signalling byte counts. */
          tag_tree__reset(band->inclusion_tree);
          tag_tree__reset(band->insignificant_msbs_tree);
        }

      /* Next, determine the number of coding passes to include in
         this bitstream layer and update the tag trees, as necessary. */

      for (block=band->blocks, m=0; m < band->band_blocks; m++, block++)
        {
          if (layer_idx == 0)
            {
              tag_tree__set_value(band->insignificant_msbs_tree+m,
                                  block->insignificant_msbs);
              block->old_passes = block->num_passes = 0;
            }
          else
            block->old_passes = block->num_passes;
          for (k=block->old_passes; k < block->max_passes; k++)
            {
              std_int rd;

              if ((rd = block->passes[k].rd_slope) <= 0)
                continue;
              if (rd >= rd_threshold)
                block->num_passes = k+1;
              else
                break;
            }
          if (block->num_passes && !block->old_passes) /* First inclusion. */
            tag_tree__set_value(band->inclusion_tree+m,layer_idx);
          if (include_makeup_passes)
            {
              assert((block->makeup_passes == 0) ||
                     (block->num_passes != 0));
              block->num_passes += block->makeup_passes;
            }
        }

      /* Now generate all tag information for the subband. */

      max_block_pass_bytes = 0;
      for (block=band->blocks, m=0; m < band->band_blocks; m++, block++)
        {
          /* Generate inclusion information. */

          extra_passes = block->num_passes - block->old_passes;
          if (block->old_passes == 0)
            { /* Not previously included. */
              tag_tree__encode(band->inclusion_tree+m,layer_idx+1,tags);
            }
          else
            { /* Block has already been included in a previous layer. */
              int inclusion_bit;

              inclusion_bit = (extra_passes == 0)?0:1;
              tag_buffer__push_bit(tags,inclusion_bit);
            }
          if (extra_passes == 0)
            continue;

          /* Generate `insignificant_msbs' information, if necessary. */

          if (block->old_passes == 0)
            {
              k = 1;
              while (!tag_tree__encode(band->insignificant_msbs_tree+m,k,tags))
                k++;
            }
          
          /* Now determine the number of new passes. */

          block_bytes = block->passes[block->num_passes-1].cumulative_bytes;
          if (block->old_passes == 0)
            extra_passes -= block->insignificant_msbs * PASSES_PER_BITPLANE;
          else
            block_bytes -= block->passes[block->old_passes-1].cumulative_bytes;
          assert((extra_passes >= 1) && (block_bytes > 0));
          total_bytes += block_bytes;
          for (k=extra_passes; k > 1; k = (k+1)>>1)
            block_bytes = (block_bytes+1)>>1;
          if (block_bytes > max_block_pass_bytes)
            max_block_pass_bytes = block_bytes;

          /* Generate tag information for the number of new passes. */

          extra_passes--;
          tag_val = (extra_passes > 0)?1:0;
          tag_buffer__push_bit(tags,tag_val);
          if (tag_val)
            {
              extra_passes -= tag_val;
              tag_val = (extra_passes > 0)?1:0;
              tag_buffer__push_bit(tags,tag_val);
              if (tag_val)
                {
                  extra_passes -= tag_val;
                  tag_val = (extra_passes > 2)?3:extra_passes;
                  tag_buffer__push_bits(tags,tag_val,2);
                  if (tag_val==3)
                    {
                      extra_passes -= tag_val;
                      tag_val = (extra_passes > 31)?31:extra_passes;
                      tag_buffer__push_bits(tags,tag_val,5);
                      if (tag_val==31)
                        {
                          extra_passes -= tag_val;
                          tag_val = extra_passes;
                          assert(tag_val < 128);
                          tag_buffer__push_bits(tags,tag_val,7);
                        }
                    }
                }
            }
        }

      if (max_block_pass_bytes > 0)
        {
          int num_bits;

          /* Send the number of bits which will be used to signal
             the number of new bytes for a single block coding pass. */

          num_bits = band->byte_count_bits;
          while (max_block_pass_bytes >= (1<<num_bits))
            {
              num_bits++;
              tag_buffer__push_bit(tags,1);
            }
          tag_buffer__push_bit(tags,0);
          band->byte_count_bits = num_bits;
          if (num_bits > 16)
            {
              fprintf(stderr,"Too many code bytes in a single bit-stream "
                      "layer for\n  one or more blocks!  Use smaller code "
                      "blocks or\n  more passes (SNR progressive)!\n");
              exit(-1);
            }

          /* Send the number of new bytes for each included block. */

          for (block=band->blocks, m=0; m < band->band_blocks; m++, block++)
            if ((extra_passes = (block->num_passes - block->old_passes)) > 0)
              {
                k = extra_passes;
                block_bytes =
                  block->passes[block->num_passes-1].cumulative_bytes;
                if (block->old_passes == 0)
                  k -= block->insignificant_msbs * PASSES_PER_BITPLANE;
                else
                  block_bytes -=
                    block->passes[block->old_passes-1].cumulative_bytes;
                for (num_bits=band->byte_count_bits; k > 1; k=(k+1)>>1)
                  num_bits++;
                assert(block_bytes < (1<<num_bits));
                tag_buffer__push_bits(tags,block_bytes,num_bits);
              }
        }
    }
  total_bytes += tag_buffer__flush(tags);
  if (output != NULL)
    {
      tag_buffer__output(tags,output);

      /* Now send the code bytes themselves, for each block for which
         information is being included. */

      for (b=level->min_band; b <= level->max_band; b++)
        {
          band = level->bands + b;
          for (block=band->blocks, m=0; m < band->band_blocks; m++, block++)
            if (block->num_passes > block->old_passes)
              {
                int offset, remaining;
                heap_unit_ptr heap;
                std_byte *buf;
                
                block_bytes =
                  block->passes[block->num_passes-1].cumulative_bytes;
                offset = 0;
                if ((k=block->old_passes) > 0)
                  offset = block->passes[k-1].cumulative_bytes;
                block_bytes -= offset;
                assert(block_bytes > 0);
                heap = block->first_unit;
                remaining = (HEAP_WORDS - block->first_pos) << 2;
                buf = ((std_byte *) heap->words) + HEAP_BYTES - remaining;
                while (offset > 0)
                  {
                    if (remaining >= offset)
                      {
                        buf += offset;
                        remaining -= offset;
                        offset = 0;
                      }
                    else
                      {
                        offset -= remaining;
                        heap = heap->next;
                        remaining = HEAP_BYTES;
                        buf = (std_byte *)(heap->words);
                      }
                  }
                while (block_bytes > 0)
                  {
                    if (remaining >= block_bytes)
                      {
                        output->push_bytes(output,buf,block_bytes);
                        block_bytes = 0;
                      }
                    else
                      {
                        output->push_bytes(output,buf,remaining);
                        block_bytes -= remaining;
                        heap = heap->next;
                        remaining = HEAP_BYTES;
                        buf = (std_byte *)(heap->words);
                      }
                  }
              }
        }
    }
  return(total_bytes);
}

/*****************************************************************************/
/* STATIC                      add_best_makeup_pass                          */
/*****************************************************************************/

static int
  add_best_makeup_pass(the_encoder_ref self, int layer_idx, int max_bytes)

 /* This function tries to utilize any portion of the overall bit-rate which
    is left over once rate-distortion optimization on the final layer is
    complete.  In particular, it passes through the various code blocks
    trying to find a new coding pass(es) which can be added (in addition to the
    number specified by the `num_passes' field), without violating any of
    the following four constraints:
      1) The relevant code block must already be included in the bit-stream;
         this minimizes the impact of including a new coding pass on the
         tag sizes and hence simplifies the algorithm.
      2) The number of additional code bytes must not exceed the `max_bytes'
         threshold.
      3) Either the number of new coding passes must have the same category
         code (i.e. 1,2,3-5,6-36) as that currently assigned for the layer,
         or else a penalty of 1 byte must be taken in satisfying (2).  Again,
         this constraint is enforced merely to simplify the task of identifying
         feasible makeup layers.  It may reduce the optimality of the
         algorithm somewhat, since the cost of coding the number of extra
         layers is generally much smaller than one byte.
      4) The current `byte_count_bits' value for the relevant subband must be
         sufficient to encode the number of code bytes sent for the block in
         the current layer, including bytes which were previously to be sent.
    The function finds the code block of this form which has the largest
    rate-distortion slope, updates the relevant `makeup_layer' and
    `makeup_passes' fields, and returns the number of additional bytes which
    are consumed by this new coding pass.  The function will be called
    iteratively until all remaining bytes have been consumed. */

{
  int n, b, k, m, comp_idx;
  level_info_ptr lev;
  band_info_ptr band;
  block_info_ptr block, best_block;
  std_int rd, best_rd;
  int current_passes, current_extra_passes, current_bytes, current_extra_bytes;
  int extra_passes, extra_bytes, max_extra_bytes;
  int best_extra_passes, best_extra_bytes;

  best_extra_passes = 0;
  best_extra_bytes = 0;
  best_block = NULL; best_rd = 0;
  for (n=0; n < self->num_levels; n++)
    for (comp_idx=0; comp_idx < self->num_components; comp_idx++)
      {
        lev = self->components[comp_idx].levels + n;
        for (b=lev->min_band; b <= lev->max_band; b++)
          {
            band = lev->bands + b;
            max_extra_bytes = 1<<(band->byte_count_bits);
            for (block=band->blocks, m=band->band_blocks; m > 0; m--, block++)
              {
                if (block->num_passes == 0)
                  continue; /* Doesn't satisfy first constraint. */
                current_passes = block->num_passes + block->makeup_passes;
                current_bytes =
                  block->passes[current_passes-1].cumulative_bytes;
                current_extra_passes = current_passes;
                current_extra_bytes = current_bytes;
                if (block->old_passes == 0)
                  current_extra_passes -=
                    block->insignificant_msbs * PASSES_PER_BITPLANE;
                else
                  {
                    current_extra_passes -= block->old_passes;
                    current_extra_bytes -=
                      block->passes[block->old_passes-1].cumulative_bytes;
                  }
                for (extra_passes=1, k=current_passes;
                     k < block->max_passes; k++, extra_passes++)
                  {
                    if (((rd = block->passes[k].rd_slope) < 0) ||
                        ((rd <= best_rd) && (best_block != NULL)))
                      continue;
                    extra_bytes =
                      block->passes[k].cumulative_bytes-current_bytes;
                    if ((extra_bytes > max_bytes) ||
                        ((extra_bytes+current_extra_bytes) > max_extra_bytes))
                      break;
                    if ((current_extra_passes <= 2) ||
                        ((current_extra_passes < 6) &&
                        ((current_extra_passes+extra_passes) >= 6)))
                      { /* Take one byte hit for encoding different # passes */
                        extra_bytes++;
                        if (extra_bytes > max_bytes)
                          break;
                      }
                    if ((current_extra_passes < 37) &&
                        ((current_extra_passes+extra_passes) >= 37))
                      { /* Take extra one byte hit to encode
                           different # passes. */
                        extra_bytes++;
                        if (extra_bytes > max_bytes)
                          break;
                      }
                    best_rd = rd;
                    best_block = block;
                    best_extra_bytes = extra_bytes;
                    best_extra_passes = extra_passes;
                  }
              }
          }
      }
  if (best_block == NULL)
    return(0);
  best_block->makeup_passes = best_extra_passes;
  return(best_extra_bytes);
}

/*****************************************************************************/
/* STATIC                    optimize_bitstream_layer                        */
/*****************************************************************************/

static std_int