dst_arith_encoder.c

关于视频压缩的jpeg2000压缩算法,C编写

/*****************************************************************************/
/* Copyright 1998, Hewlett-Packard Company                                   */
/* All rights reserved                                                       */
/* File: "dst_arith_encoder.c"                                               */
/* Description: Implementation of non-macro arithmetic encoder functions     */
/* Author: David Taubman                                                     */
/* Affiliation: Hewlett-Packard and                                          */
/*              The University of New South Wales, Australia                 */
/* Version: VM5.3                                                            */
/* Last Revised: 23 November, 1999                                           */
/*****************************************************************************/

/*****************************************************************************/
/* Modified to incorporate MQ-coder by Mitsubishi Electric Corp.             */
/* Copyright 1999, Mitsubishi Electric Corp.                                 */
/* All rights reserved for modified parts                                    */
/*****************************************************************************/

/*****************************************************************************/
/* Modifications tagged with comment lines or delimiters involving the       */
/* string, "David T mod" or "mod by David T", have been made by David        */
/* Taubman; they are copyrighted by Hewlett-Packard Company with all rights  */
/* reserved for the modified parts.                                          */
/*****************************************************************************/

/*****************************************************************************/
/* Substantially modified by David Taubman to support flexible termination   */
/* of code stream segments and error resilience capabilities.  Copyright     */
/* 1999 by Hewlett-Packard Company with all rights reserved for the modified */
/* parts.                                                                    */
/*****************************************************************************/

/*****************************************************************************/
/* Modified by David Taubman to avoid the need for byte stuffing when resync */
/* markers are in use.  This simplifies the code and substantially improves  */
/* the usefulness of the system for applications requiring error resilience. */
/* Changes are as follows: a) changed SOT marker to lie within intra-packet  */
/* marker range 0xFF90 through 0xFFFF; b) introduced an MQ-like bit-stuffing */
/* policy in packet heads; c) introduced an MQ-like bit-stuffing policy in   */
/* the raw bit-stream segments generated by the entropy coder in lazy mode;  */
/* d) modified error resilient termination policy for raw bit-stream         */
/* to fill unused bits with the simpler code 0101... instead of 1010...;     */
/* e) eliminated the use of byte-stuffing with resync markers.  In the new   */
/* code, none of the packet segments (packet head, MQ segments and raw       */
/* segments) may contain any two byte sequence in the range 0xFF90 through   */
/* 0xFFFF; moreover, no segment can terminate with a 0xFF, so that the       */
/* entire packet is guaranteed to be free of two byte sequences in the above */
/* range.  All delimiting markers from the codestream (i.e. SOT, RESYNC and  */
/* EOI) are guaranteed to lie within that range.                             */
/* Copyright 1999 by Hewlett-Packard Company with all                        */
/* rights reserved for the modified parts.                                   */
/*****************************************************************************/

#include <local_services.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ifc.h>
#include <stdio.h>
#include "dst_arith_encoder.h"

/* ========================================================================= */
/* --------------------------- Private Macros ------------------------------ */
/* ========================================================================= */

/*****************************************************************************/
/* MACRO                         put_byte                                    */
/*****************************************************************************/

#define put_byte(_state,_value)                                           \
  {                                                                       \
    if (_state->mqe.io_enable)                                            \
      {                                                                   \
        _state->current_lsb -= 8;                                         \
        _state->word += (_value)<<(_state->current_lsb);                  \
        if (_state->current_lsb == 0)                                     \
          {                                                               \
            dst_arith_coder__output_word(_state,_state->word);            \
            _state->current_lsb = 32;                                     \
            _state->word = 0;                                             \
          }                                                               \
      }                                                                   \
    else                                                                  \
      _state->mqe.io_enable = SW_ON;                                      \
  }


/* ========================================================================= */
/* ------------------------- Internal Functions ---------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* STATIC                         init_enc                                   */
/*****************************************************************************/

static void
  init_enc(mqe_var_ptr mqe)
{
  mqe->areg = ENC_HALF;
  mqe->creg = LONG_ZERO;
  mqe->buffer = LONG_ZERO;
  mqe->io_enable = SW_OFF;
  mqe->ct = NEXTBITS_NML + SPACER + 1;
  mqe->active = 0; /* Wait until first call to `dst_arith_coder__activate'. */
  mqe->num_preceding_bytes = 0;
  mqe->have_unsent_ff = 0;
}

/*****************************************************************************/
/* STATIC                 perform_best_terminating_flush                     */
/*****************************************************************************/

static int
  perform_best_terminating_flush(dst_arith_state_ptr state)

 /* Flushes the arithmetic coder using a relatively complex, near optimal
    algorithm to determine the termination length.  Better performance
    cannot be achieved without compromising the operation of the code
    stream queueing system.  The termination length is returned to the
    caller. */

{
  int num_bytes, min_bytes;
  std_int upper_C, upper_buf, lower_C, lower_buf;
  std_short ct;

  min_bytes = state->mqe.num_preceding_bytes;
  num_bytes = (state->saved_words << 2) + ((32-state->current_lsb)>>3);
  if (state->mqe.io_enable)
    num_bytes++;
  num_bytes--;
  assert(num_bytes >= (min_bytes-1));
    /* `num_bytes' represents the number of bytes which have been pushed
       out to the heap by this stage, not including any value sent to
       the byte buffer in the `state->mqe' structure.  This value might
       be less than `min_bytes'.  For example, if no symbols have been coded
       at all, this value will be equal to `min_bytes'-1.  The interpretation
       of a value of `min_bytes'-1 is that the byte buffer in the `state->mqe'
       structure is itself empty. */

  ct = state->mqe.ct;
  lower_C = state->mqe.creg;
  upper_C = lower_C + state->mqe.areg;
  lower_C <<= ct;
  upper_C <<= ct;
  upper_buf = lower_buf = state->mqe.buffer;
  if (upper_C & M_CR_C)
    {
      upper_C -= M_CR_C;
      upper_buf++;
    }
  if (lower_C & M_CR_C)
    {
      lower_C -= M_CR_C;
      lower_buf++;
    }

  /* At this point, `upper_buf' holds the buffer value and
     `upper_C' the C-register value corresponding to an upper bound;
     Similarly, `lower_C' and `lower_buf' represent the lower bound on
     the arithmetic code-word.  After appending 1's to the truncated code-word,
     it must be strictly less than the upper bound and no less than the
     lower bound in order to ensure correct decoding.  We would normally
     only need to consider the upper bound, but the bit-stuffing policy
     used by the MQ coder renders this insufficient. */

  /* Now for the loop to find the minimum number of bytes required and also
     to output these as necessary to the code stream. */

  while (1)
    {
      if (state->mqe.have_unsent_ff)
        {  /* We may be able to terminate here and discard the FF.  Otherwise,
              we will need to send this FF which is still pending.  If we stop
              immediately before this pending FF, the decoder will replicate it
              with the extension convention and then will append 0x7F, 0xFF,
              0x7F, etc., which is equivalent to a number strictly less than
              128, but larger than any number less than 128. */
          state->mqe.have_unsent_ff = 0;
          if ((upper_buf >= 128) && (lower_buf < 128))
            { /* Can stop before the unsent FF.  Actually, we must not send
                 the trailing FF or we might accidentally introduce a false
                 marker at the boundary between segments of the bit-stream. */
              break;
            }
          put_byte(state,LONG_FF);
          num_bytes++;
        }
      else
        { /* If we stop here, the decoder will pad with 0xFF, 0x7F, ...,
             which is equivalent to a number strictly less than 256, but
             larger than any number less than 256. */
          if ((upper_buf >= 256) && (lower_buf < 256))
            break; /* We are done. */
        }

      /* Push a byte out and advance the bound registers and byte
         count accordingly. */

      assert(!(lower_C & M_CR_C)); /* Should not be able to get a carry. */
      if (lower_buf < 255)
        {
          put_byte(state,lower_buf);
          num_bytes++;
          upper_buf -= lower_buf;
          upper_buf <<= 8;
          upper_buf |= (upper_C >> (16+SPACER)) & 0x00FF;
          lower_buf = (lower_C >> (16+SPACER)) & 0x00FF;
          upper_C <<= 8; lower_C <<= 8;
        }
      else
        { /* buffer == BYTE_FF */
          state->mqe.have_unsent_ff = 1;
          upper_buf -= 255;
          lower_buf -= 255;
          upper_buf <<= 7;
          lower_buf <<= 7;
          upper_buf |= (upper_C >> (16+SPACER+1)) & 0x007F;
          lower_buf |= (lower_C >> (16+SPACER+1)) & 0x007F;
          upper_C <<= 7; lower_C <<= 7;
        }
      upper_C &= M_CR_BSX;
      lower_C &= M_CR_BSX;
    }
  assert(num_bytes >= min_bytes);
  return(num_bytes);  
}

/*****************************************************************************/
/* STATIC                 perform_easy_terminating_flush                     */
/*****************************************************************************/

static int
  perform_easy_terminating_flush(dst_arith_state_ptr state)

 /* Flushes the arithmetic coder using a simple, minimally invasive
    algorithm to determine the termination length, which is returned to
    the caller. */

{
  std_short ct;
  unsigned long creg;
  int bits_left;
  int num_bytes;

  ct = state->mqe.ct;
  creg = state->mqe.creg;
  bits_left = 8 + SPACER - ct + 1; /* Need only MSB of C register. */
  creg <<= ct; /* Shift bits in `creg' to upper portion. */
  for (; bits_left > 0; bits_left-=ct, creg<<=ct)
    creg = dst_arith_coder__byteout(creg,&ct,state);
  dst_arith_coder__byteout(creg,&ct,state); /* Flush `buffer'. */
  num_bytes = (state->saved_words << 2) + ((32-state->current_lsb)>>3);
  return(num_bytes);
}

/*****************************************************************************/
/* STATIC                 perform_error_resilient_flush                      */
/*****************************************************************************/

static int
  perform_error_resilient_flush(dst_arith_state_ptr state)

 /* The termination length is identical to that produce by
    `perform_easy_terminating_flush', but the spare code space is used
    to embed error resilience information.  Consult the comments appearing
    with the definition of the `dst_error_resilience' structure embedded
    in `state' for more information on this policy. */

{
  return(perform_easy_terminating_flush(state));
}

/*****************************************************************************/
/* STATIC                 perform_raw_terminating_flush                      */
/*****************************************************************************/

static int
  perform_raw_terminating_flush(dst_arith_state_ptr state)
{
  int num_bytes;
  std_int code;

  code = 0; /* By appending the sequence 01010... we avoid the possibility of
               terminating FF's. */
  while (state->current_lsb & 7)
    {
      state->current_lsb--;
      state->word |= code << state->current_lsb;
      code = 1-code;
    }
  if (state->current_lsb == 0)
    {
      dst_arith_coder__output_word(state,state->word);
      state->current_lsb = 32;
      state->word = 0;
    }
  num_bytes = (state->saved_words << 2) + ((32-state->current_lsb)>>3);
  return(num_bytes);
}


/* ========================================================================= */
/* ------------------------- External Functions ---------------------------- */
/* ========================================================================= */

/*****************************************************************************/
/* EXTERN               dst_arith_coder__initialize                          */
/*****************************************************************************/

void
  dst_arith_coder__initialize(dst_arith_state_ptr state, int num_contexts,
                              dst_context_state_ptr contexts,
                              dst_heap_unit_ptr heap, int next_heap_pos,
                              dst_codeword_heap_ref code_mgr,
                              int error_resilient_termination)
{
  init_enc(&(state->mqe));

  state->current_lsb = 32;
  state->word = 0;
  state->saved_words = 0;
  state->heap = heap;
  state->next_heap_pos = next_heap_pos;
  state->code_heap_mgr = code_mgr;
  state->num_contexts = num_contexts;
  state->contexts = contexts;
  state->error_resilient_termination = error_resilient_termination;
}

/*****************************************************************************/
/* EXTERN                dst_arith_coder__model_init                         */
/*****************************************************************************/

void
  dst_arith_coder__model_init(dst_arith_state_ptr state,
                              dst_context_state_ptr init)
{
  dst_context_state_ptr csp1, csp2;
  int n;

  csp1 = state->contexts;
  csp2 = csp1 + DST_ARITH_MAX_CTXTS;
  for (n=state->num_contexts; n > 0; n--, csp1++, csp2++, init++)
    {
      *csp1 = *init;
      *csp2 = dst_arith_state_to_delta[*csp1];
    }
}

/*****************************************************************************/
/* EXTERN                 dst_arith_coder__activate                          */
/*****************************************************************************/

void
  dst_arith_coder__activate(dst_arith_state_ptr state)
{
  /* Align on byte boundary. */

  state->current_lsb &= ~7;
  if (state->current_lsb == 0)
    {
      state->current_lsb = 32;