/*
 *  tree.c:		Input of bintree partitioning
 *
 *  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 "wfalib.h"
#include "tiling.h"

#include "tree.h"

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

				prototypes

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

static unsigned
restore_depth_first_order (unsigned src_state, unsigned level, unsigned x,
			   unsigned y, unsigned *dst_state,
			   word_t (*bfo_tree)[MAXLABELS],
			   wfa_t *wfa, tiling_t *tiling);
static void
decode_tree (bitfile_t *input, byte_t *data, unsigned n_data, unsigned scaling,
	     u_word_t sum0, u_word_t sum1);

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

				public code

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

void
read_tree (wfa_t *wfa, tiling_t *tiling, bitfile_t *input)
/*
 *  Read bintree partitioning of WFA from the 'input' stream.
 *  'tiling' provides the information about image tiling, if applied.
 *
 *  No return value.
 *
 *  Side effects:
 *	'wfa->tree', 'wfa->x', 'wfa->y', 'wfa->level_of_state'
 *      are filled with decoded values.
 */
{
   byte_t *bitstring;			/* the encoded data */
   word_t (*bfo_tree)[MAXLABELS];	/* node numbers in BFO */

   /*
    *  Read WFA tree stored in breadth first order
    */
   {
      unsigned total = (wfa->states - wfa->basis_states) * MAXLABELS;
      unsigned scale = total / 20;

      bitstring = Calloc (total, sizeof (byte_t));
      decode_tree (input, bitstring, total, scale, 1, 11);
   }

   /*
    *  Generate tree using a breadth first traversal
    */
   {
      unsigned 	next;			/* next free node number of the tree */
      unsigned 	state;
      unsigned 	label;
      byte_t   *buffer = bitstring;	/* pointer to decoded data */

      bfo_tree = Calloc (wfa->states * MAXLABELS, sizeof (word_t));
      for (state = 0, next = 1; state < next; state++)
	 for (label = 0; label < MAXLABELS; label++)
	    bfo_tree [state][label] = *buffer++ ? next++ : RANGE;
   }

   /*
    *  Traverse tree and restore depth first order
    */
   {
      unsigned dst_state = wfa->basis_states;

      wfa->root_state
	 = restore_depth_first_order (0, (wfa->wfainfo->level
					  + (wfa->wfainfo->color ? 2 : 0)),
				      0, 0, &dst_state, bfo_tree, wfa, tiling);
   }

   Free (bitstring);
   Free (bfo_tree);
}

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

				private code

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

static unsigned
restore_depth_first_order (unsigned src_state, unsigned level, unsigned x,
			   unsigned y, unsigned *dst_state,
			   word_t (*bfo_tree)[MAXLABELS],
			   wfa_t *wfa, tiling_t *tiling)
/*
 *  Map state 'src_state' (breadth first order)
 *  to state '*dst_state' (depth first order)
 *  Add a tree edge 'state' --> 'child' with label and weight 1.0
 *  if required.
 *  'x', 'y' give the coordinates of the current state in the 'color' image
 *  of size 'image_level'. 'tiling' defines the image partitioning.
 *
 *  Return value:
 *	new node number in depth first order
 *
 *  Side effects:
 *	'wfa->tree', 'wfa->x', 'wfa->y', 'wfa->level_of_state'
 *      are filled with decoded values.
 */
{
   unsigned newx [MAXLABELS];		/* x coordinate of children */
   unsigned newy [MAXLABELS];		/* y coordinate of children */
   unsigned x0, y0;			/* NW corner of image tile */
   unsigned width, height;		/* size of image tile */

   /*
    *  If tiling is performed then replace current coordinates
    */
   if (tiling->exponent && level == wfa->wfainfo->level - tiling->exponent)
   {
      unsigned tile;

      for (tile = 0; tile < 1U << tiling->exponent; tile++)
      {
	 locate_subimage (wfa->wfainfo->level, level, tile,
			  &x0, &y0, &width, &height);
	 if (x0 == x && y0 == y) /* matched ! */
	 {
	    locate_subimage (wfa->wfainfo->level, level, tiling->vorder[tile],
			     &x, &y, &width, &height);
	    break;
	 }
      }
   }
   /*
    *  Coordinates of children 0 and 1
    */
   if (wfa->wfainfo->color && level == wfa->wfainfo->level + 1)
      newx[0] = newy[0] = newx[1] = newy[1] = 0;
   else
   {
      newx[0] = x;
      newy[0] = y;
      newx[1] = level & 1 ? x : x + width_of_level (level - 1);
      newy[1] = level & 1 ? y + height_of_level (level - 1) : y;
   }

   /*
    *  Remap node numbers
    */
   {
      int      child [MAXLABELS];	/* children of current node (state) */
      int      domain;			/* current domain */
      unsigned label;

      for (label = 0; label < MAXLABELS; label++)
	 if (!isrange (domain = bfo_tree [src_state][label]))
	    child [label] = restore_depth_first_order (domain, level - 1,
						       newx [label],
						       newy [label], dst_state,
						       bfo_tree, wfa, tiling);
	 else
	    child [label] = RANGE;

      for (label = 0; label < MAXLABELS; label++)
      {
	 wfa->tree [*dst_state][label] = child [label];
	 wfa->x [*dst_state][label]    = newx [label];
	 wfa->y [*dst_state][label]    = newy [label];
      }
      wfa->level_of_state [*dst_state] = level;
   }

   return (*dst_state)++;
}

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

                 Binary adaptive arithmetic compression

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

static void
decode_tree (bitfile_t *input, byte_t *data, unsigned n_data, unsigned scaling,
	     u_word_t sum0, u_word_t sum1)
/*
 *  Decode bintree partitioning using adaptive binary arithmetic decoding.
 *  'input'	input stream,
 *  'data'	buffer for decoded szmbols,
 *  'n_data'	number of symbols to decode,
 *  'scaling'	rescale probability models if range > 'scaling'
 *  'sum0'	initial totals of symbol '0'
 *  'sum1'	initial totals of symbol '1'
 *
 *  No return value.
 *
 *  Side effects:
 *	'data []' is filled with the decoded bitstring
 */
{
   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 */
   unsigned n;				/* Data counter */

   assert (data);

   code = get_bits (input, 16);
   low  = 0;
   high = 0xffff;

   for (n = n_data; n; n--)
   {
      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;

	 *data++ = 0;
	 /*
	  *  Update the frequency counts
	  */
	 sum0++;
	 sum1++;
	 if (sum1 > scaling) /* scale the symbol frequencies */
	 {
	    sum0 >>= 1;
	    sum1 >>= 1;
	    if (!sum0)
	       sum0 = 1;
	    if (sum0 >= sum1)
	       sum1 = sum0 + 1;
	 }

      }
      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;

	 *data++ = 1;
	 /*
	  *  Update the frequency counts
	  */
	 sum1++;
	 if (sum1 > scaling) /* scale the symbol frequencies */
	 {
	    sum0 >>= 1;
	    sum1 >>= 1;
	    if (!sum0)
	       sum0 = 1;
	    if (sum0 >= sum1)
	       sum1 = sum0 + 1;
	 }
      }
   }
   INPUT_BYTE_ALIGN (input);
}