/*
 *  nd.c:               Input of prediction tree
 *
 *  Written by:         Ullrich Hafner
 *
 *  This file is part of FIASCO (Fractal Image And Sequence COdec)
 *  Copyright (C) 1994-2000 Ullrich Hafner
 */

/*
 *  $Date: 2000/06/14 20:50:13 $
 *  $Author: hafner $
 *  $Revision: 5.1 $
 *  $State: Exp $
 */

#include "config.h"

#include "types.h"
#include "macros.h"
#include "error.h"

#include "bit-io.h"
#include "arith.h"
#include "misc.h"
#include "list.h"
#include "wfalib.h"

#include "nd.h"

/*****************************************************************************

                                prototypes

*****************************************************************************/

static void
decode_nd_coefficients (unsigned total, wfa_t *wfa, bitfile_t *input);
static unsigned
decode_nd_tree (wfa_t *wfa, bitfile_t *input);

/*****************************************************************************

                                public code

*****************************************************************************/

void
read_nd (wfa_t *wfa, bitfile_t *input)
/*
 *  Read transitions of the nondetermistic 'wfa' part from 'input' stream.
 *  ND is used only at levels {'wfa->p_min_level', ... , 'wfa->p_max_level'}.
 *
 *  Side effects:
 *      'wfa->into' and 'wfa->weights' are filled with the decoded values
 */
{
   unsigned total = decode_nd_tree (wfa, input);

   if (total > 0)
      decode_nd_coefficients (total, wfa, input);
}

/*****************************************************************************

                                private code

*****************************************************************************/

static unsigned
decode_nd_tree (wfa_t *wfa, bitfile_t *input)
/*
 *  Read 'wfa' prediction tree of given 'input' stream.
 *
 *  No return value.
 *
 *  Side effects:
 *      'wfa->into' is filled with the decoded values
 */
{
   lqueue_t *queue;                     /* queue of states */
   int       next, state;               /* state and its current child */
   unsigned  total = 0;                 /* total number of predicted states */
   u_word_t  sum0, sum1;                /* Probability model */
   u_word_t  code;                      /* The present input code value */
   u_word_t  low;                       /* Start of the current code range */
   u_word_t  high;                      /* End of the current code range */

   /*
    *  Initialize arithmetic decoder
    */
   code = get_bits (input, 16);
   low  = 0;
   high = 0xffff;
   sum0 = 1;
   sum1 = 11;

   queue = alloc_queue (sizeof (int));
   state = wfa->root_state;
   queue_append (queue, &state);

   /*
    *  Traverse the WFA tree in breadth first order (using a queue).
    */
   while (queue_remove (queue, &next))
   {
      unsigned label;

      if (wfa->level_of_state [next] > wfa->wfainfo->p_max_level + 1)
      {
         /*
          *  Nondetermismn is not allowed at levels larger than
          *  'wfa->wfainfo->p_max_level'.
          */
         for (label = 0; label < MAXLABELS; label++)
            if (ischild (state = wfa->tree [next][label]))
               queue_append (queue, &state); /* continue with children */
      }
      else if (wfa->level_of_state [next] > wfa->wfainfo->p_min_level)
      {
         for (label = 0; label < MAXLABELS; label++)
            if (ischild (state = wfa->tree [next][label]))
            {
               unsigned count;          /* Current interval count */
               unsigned range;          /* Current interval range */

               count = (((code - low) + 1) * sum1 - 1) / ((high - low) + 1);
               if (count < sum0)
               {
                  /*
                   *  Decode a '0' symbol
                   *  First, the range is expanded to account for the
                   *  symbol removal.
                   */
                  range = (high - low) + 1;
                  high = low + (u_word_t) ((range * sum0) / sum1 - 1 );
                  RESCALE_INPUT_INTERVAL;
                  /*
                   *  Update the frequency counts
                   */
                  sum0++;
                  sum1++;
                  if (sum1 > 50) /* scale the symbol frequencies */
                  {
                     sum0 >>= 1;
                     sum1 >>= 1;
                     if (!sum0)
                        sum0 = 1;
                     if (sum0 >= sum1)
                        sum1 = sum0 + 1;
                  }
                  if (wfa->level_of_state [state] > wfa->wfainfo->p_min_level)
                     queue_append (queue, &state);
               }
               else
               {
                  /*
                   *  Decode a '1' symbol
                   *  First, the range is expanded to account for the
                   *  symbol removal.
                   */
                  range = (high - low) + 1;
                  high = low + (u_word_t) ((range * sum1) / sum1 - 1);
                  low  = low + (u_word_t) ((range * sum0) / sum1);
                  RESCALE_INPUT_INTERVAL;
                  /*
                   *  Update the frequency counts
                   */
                  sum1++;
                  if (sum1 > 50) /* scale the symbol frequencies */
                  {
                     sum0 >>= 1;
                     sum1 >>= 1;
                     if (!sum0)
                        sum0 = 1;
                     if (sum0 >= sum1)
                        sum1 = sum0 + 1;
                  }
                  append_edge (next, 0, -1, label, wfa);
                  total++;
               }
            }
      }
   }
   free_queue (queue);

   INPUT_BYTE_ALIGN (input);

   return total;
}

static void
decode_nd_coefficients (unsigned total, wfa_t *wfa, bitfile_t *input)
/*
 *  Read #'total' weights of nondeterministic part of 'wfa'
 *  of given 'input' stream.
 *  'frame' gives the current frame number.
 *
 *  No return value.
 *
 *  Side effects:
 *      'wfa->weights' is filled with the decoded values.
 */
{
   unsigned *coefficients;              /* array of factors to encode */
   unsigned *ptr;                       /* pointer to current factor */

   /*
    *  Decode array of coefficients stored with arithmetic coding
    */
   {
      const int scaling  = 50;          /* scaling factor of prob. model */
      unsigned  c_symbols = 1 << (wfa->wfainfo->dc_rpf->mantissa_bits + 1);

      ptr = coefficients = decode_array (input, NULL, &c_symbols, 1,
                                         total, scaling);
   }

   /*
    *  Fill 'wfa->weights' with decoded coefficients
    */
   {
      unsigned state, label;

      for (state = wfa->basis_states; state < wfa->states; state++)
         for (label = 0; label < MAXLABELS; label++)
            if (ischild (wfa->tree [state][label])
                && isedge (wfa->into [state][label][0]))
            {
               wfa->weight [state][label][0] = btor (*ptr++,
                                                     wfa->wfainfo->dc_rpf);
               wfa->int_weight [state][label][0]
                  = wfa->weight [state][label][0] * 512 + 0.5;
            }
   }
   Free (coefficients);
}