ebcot_arith_encoder.c

JPEG2000 EBCOT算法源码

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

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

/*****************************************************************************/
/* EXTERN              ebcot_arith_coder__initialize                         */
/*****************************************************************************/

void
  ebcot_arith_coder__initialize(arith_state_ptr state, heap_unit_ptr heap,
                                int next_heap_pos, codeword_heap_ref code_mgr)
{
  int n;

  state->A = (-1)^((-1)<<W_BITS);;
  state->C = 0;
  state->word = 0;
  state->rho = -1;
  state->available_bits = 32;
  state->saved_words = 0;
  state->heap = heap;
  state->next_heap_pos = next_heap_pos;
  state->code_heap_mgr = code_mgr;
  for (n=0; n < TOTAL_CONTEXTS; n++)
    state->contexts[n] = 2 + (1<<S_BITS); /* S=2 and N=1 */
}

/*****************************************************************************/
/* EXTERN               ebcot_arith_coder__renormalize                       */
/*****************************************************************************/

void
  ebcot_arith_coder__renormalize(arith_state_ptr state)
{
  context_state_ptr csp;
  context_state cs;
  int n;

  csp = state->contexts + ZC_OFFSET + 0;
  for (n=ZC_CONTEXTS; n > 0; n--, csp++)
    {
      cs = *csp;
      while (((cs >> S_BITS) > 2) && ((cs & S_MASK) > 32))
        cs = (cs>>1) & ~S_MSB;
      *csp = cs;
    }
}

/*****************************************************************************/
/* EXTERN              ebcot_arith_coder__output_word                        */
/*****************************************************************************/

void
  ebcot_arith_coder__output_word(arith_state_ptr state, std_int word)

 /* Outputs a word to the code word heap. */

{
  int pos;
  
  pos = state->next_heap_pos;
  state->heap->words[pos++] = word;
  state->saved_words++;
  if (pos == HEAP_WORDS)
    {
      heap_unit_ptr elt;

      pos = 0;
      elt = state->code_heap_mgr->get_unit(state->code_heap_mgr);
      elt->next = NULL;
      state->heap = state->heap->next = elt;
    }
  state->next_heap_pos = pos;
}

/*****************************************************************************/
/* EXTERN                  ebcot_arith_coder__flush                          */
/*****************************************************************************/

void
  ebcot_arith_coder__flush(arith_state_ptr state)

 /* Flushes the state of the arithmetic coder to the code word heap.  Note
    that the `state' structure supplied here must not be passed into the
    `ebcot_arith_coder__get_minimum_bits' function later.  The state structures
    passed into that function should have been saved before the coder was
    flushed. */

{
  std_int C, word, rho;
  std_short avail;

  C=state->C; word=state->word; avail=state->available_bits; rho=state->rho;
  if (rho >= 0)
    {
      word <<= 1; /* Push out a 0. */
      if ((--avail) == 0)
        { avail = 32; ebcot_arith_coder__output_word(state,word); }
    }
  for (; rho > 0; rho--)
    {
      word <<= 1; word++; /* Push out a 1. */
      if ((--avail) == 0)
        { avail = 32; ebcot_arith_coder__output_word(state,word); }
    }
  for (rho=2; rho > 0; ) /* Use `rho' to count # words pushed out. */
    { /* Could generate an extra word of 0's, but who cares? */
      C <<= 1;
      word <<= 1;
      if (C < 0)
        word++;
      if ((--avail) == 0)
        {
          avail = 32;
          ebcot_arith_coder__output_word(state,word);
          rho--;
        }
    }
}

/*****************************************************************************/
/* EXTERN             ebcot_arith_coder__get_minimum_bits                    */
/*****************************************************************************/

int
  ebcot_arith_coder__get_minimum_bits(arith_state_ptr state,
                                      heap_unit_ptr heap, int heap_pos)

 /* Determines the minimum number of bits which are required to correctly
    decode all coded symbols up to and including the last symbol whose
    coding resulted in the state recorded in the supplied `state' structure.
    The `heap' and `heap_pos' arguments identify the heap unit structure and
    the word index within this structure, of the first word saved by the
    arithmetic coding engine.  The `saved_words' and `available_bits' fields
    of the `state' structure may be used to index into the store which
    commences at this location. */

{
  std_int A, C, word, rho, min_bits, saved_words, tmp, done;

  A = state->A; C = state->C; rho = state->rho;
  saved_words = state->saved_words;
  min_bits = (saved_words<<5) + (32-state->available_bits);
  if ((min_bits == 0) && (rho < 0) && (A == ((-1)^((-1)<<W_BITS))))
    return(0);
  while (saved_words)
    {
      tmp = HEAP_WORDS - heap_pos;
      if (tmp > saved_words)
        {
          heap_pos += saved_words;
          saved_words = 0;
        }
      else
        {
          saved_words -= tmp;
          heap_pos = 0;
          heap = heap->next;
        }
    }
  word = heap->words[heap_pos++];
  word <<= (min_bits & 31);
  C += (A << P_BITS); /* Upper bound of interval.  Want this to be strictly
                         greater than the approximate code word formed by
                         appending 1's to the truncated code word. */
  done = 0;
  if (C < 0)
    { /* Carry bit generated in forming the upper bound value. */
      done = (word >= 0); /* If MSB of `word' is 0 then C is > code word. */
      word <<= 1; min_bits++;
      if ((min_bits & 31) == 0)
        { /* Load in new word. */
          if (heap_pos >= HEAP_WORDS)
            { heap = heap->next; heap_pos = 0; }
          word = heap->words[heap_pos++];
        }
      if (!done)
        { /* Both the upper bound and the actual code word must have
             `rho' 0's in the next set of bit positions, as a consequence
             of the carry bit. */
          assert(rho >= 0);
          for (; rho > 0; rho--)
            {
              assert(word >= 0);
              word <<= 1; min_bits++;
              if ((min_bits & 31) == 0)
                { /* Load in new word. */
                  if (heap_pos >= HEAP_WORDS)
                    { heap = heap->next; heap_pos = 0; }
                  word = heap->words[heap_pos++];
                }
            }
        }
    }
  else if (rho >= 0)
    { /* No carry generated in forming the upper bound, so the bit-sequence
         0111... with `rho' 1's must appear next. */
      assert(word >= 0); /* Can't have upper bound < actual code word. */
      word <<= 1; min_bits++;
      if ((min_bits & 31) == 0)
        { /* Load in new word. */
          if (heap_pos >= HEAP_WORDS)
            { heap = heap->next; heap_pos = 0; }
          word = heap->words[heap_pos++];
        }
      for (; rho > 0; rho--)
        {
          assert(word < 0); /* Same set of 1's must be in actual code word. */
          word <<= 1; min_bits++;
          if ((min_bits & 31) == 0)
            { /* Load in new word. */
              if (heap_pos >= HEAP_WORDS)
                { heap = heap->next; heap_pos = 0; }
              word = heap->words[heap_pos++];
            }
        }
    }

  /* All information in `rho' has been cleaned out.  We now have only to
     compare the bits of C with the remaining bit positions in `word'. */

  while (!done)
    {
      C <<= 1;
      if ((C ^ word) < 0)
        { /* At last a difference in the bit positions. */
          assert(C < 0); /* Upper bound must be larger than actual code word */
          done = 1;
        }
      word <<= 1; min_bits++;
      if ((min_bits & 31) == 0)
        { /* Load in new word. */
          if (heap_pos >= HEAP_WORDS)
            { heap = heap->next; heap_pos = 0; }
          word = heap->words[heap_pos++];
        }
    }
  return(min_bits);
}

/*****************************************************************************/
/* EXTERN                ebcot_arith_coder__log_symbol                       */
/*****************************************************************************/

#ifdef LOG_SYMBOLS
void
  ebcot_arith_coder__log_symbol(arith_state_ptr state, context_state_ptr ctxt,
                                std_short symbol)
{
  int val;

  if (ctxt == NULL)
    val = 255;
  else
    val = ctxt - state->contexts;
  putc(val,state->symbol_log);
  val = (symbol)?1:0;
  putc(val,state->symbol_log);
}
#endif /* LOG_SYMBOLS */