wfalib.c

linux下将各类格式图片转换工具

/*
 *  wfalib.c:		Library functions both for encoding and decoding
 *
 *  Written by:		Ullrich Hafner
 *		
 *  This file is part of FIASCO (獸籸actal 獻籱age 獳籲d 玈籩quence 獵O籨ec)
 *  Copyright (C) 1994-2000 Ullrich Hafner <[e-mail]>
 */

/*
 *  $Date: 2000/07/18 15:57:28 $
 *  $Author: hafner $
 *  $Revision: 5.5 $
 *  $State: Exp $
 */

#define _BSD_SOURCE 1   /* Make sure strdup() is in string.h */
#define _XOPEN_SOURCE 500  /* Make sure strdup() is in string.h */

#include "config.h"

#if STDC_HEADERS
#	include <stdlib.h>
#endif /* not STDC_HEADERS */

#include <string.h>

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

#include "wfa.h"
#include "misc.h"
#include "wfalib.h"

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

				prototypes
  
*****************************************************************************/

static unsigned
xy_to_address (unsigned x, unsigned y, unsigned level, unsigned n);

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

				public code
  
*****************************************************************************/

wfa_t *
alloc_wfa (bool_t coding)
/*
 *  WFA constructor:
 *  Initialize the WFA structure 'wfa' and allocate memory.
 *  Flag 'coding' indicates whether WFA is used for coding or decoding.
 *
 *  Return value:
 *	pointer to the new WFA structure
 */
{
   wfa_t *wfa = Calloc (1, sizeof (wfa_t));
		 
   /*
    *  Allocate memory
    */
   wfa->final_distribution = Calloc (MAXSTATES, sizeof (real_t));
   wfa->level_of_state     = Calloc (MAXSTATES, sizeof (byte_t));
   wfa->domain_type        = Calloc (MAXSTATES, sizeof (byte_t));
   wfa->delta_state        = Calloc (MAXSTATES, sizeof (bool_t));
   wfa->tree               = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
   wfa->x                  = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
   wfa->y                  = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
   wfa->mv_tree            = Calloc (MAXSTATES * MAXLABELS, sizeof (mv_t));
   wfa->y_state            = Calloc (MAXSTATES * MAXLABELS, sizeof (word_t));
   wfa->into               = Calloc (MAXSTATES * MAXLABELS * (MAXEDGES + 1),
				     sizeof (word_t));
   wfa->weight             = Calloc (MAXSTATES * MAXLABELS * (MAXEDGES + 1),
				     sizeof (real_t));
   wfa->int_weight         = Calloc (MAXSTATES * MAXLABELS * (MAXEDGES + 1),
				     sizeof (word_t));
   wfa->wfainfo            = Calloc (1, sizeof (wfa_info_t));;
   wfa->prediction         = Calloc (MAXSTATES * MAXLABELS, sizeof (byte_t));

   wfa->wfainfo->wfa_name   = NULL;
   wfa->wfainfo->basis_name = NULL;
   wfa->wfainfo->title 	    = strdup ("");
   wfa->wfainfo->comment    = strdup ("");

   /*
    *  Initialize structure
    */
   {
      unsigned  state, label;

      wfa->states       = 0;
      wfa->basis_states = 0;
      wfa->root_state   = 0;
      for (state = 0; state < MAXSTATES; state++) 
      {
	 wfa->final_distribution [state] = 0;
	 wfa->domain_type [state]        = 0;
	 for (label = 0; label < MAXLABELS; label++)
	 {
	    wfa->into [state][label][0] = NO_EDGE;
	    wfa->tree [state][label]    = RANGE;
	    wfa->y_state [state][label] = RANGE;
	 }
      }
   }

   if (coding)				/* initialize additional variables */
      wfa->y_column = Calloc (MAXSTATES * MAXLABELS, sizeof (byte_t));
   else
      wfa->y_column = NULL;
   
   return wfa;
}

void
free_wfa (wfa_t *wfa)
/*
 *  WFA destructor:
 *  Free memory of given 'wfa'.
 *
 *  No return value.
 *
 *  Side effects:
 *	'wfa' struct is discarded.
 */
{
   if (wfa->wfainfo->wfa_name)
      Free (wfa->wfainfo->wfa_name);
   if (wfa->wfainfo->basis_name)
      Free (wfa->wfainfo->basis_name);
   if (wfa->wfainfo->title)
      Free (wfa->wfainfo->title);
   if (wfa->wfainfo->comment)
      Free (wfa->wfainfo->comment);

   Free (wfa->final_distribution);
   Free (wfa->level_of_state);
   Free (wfa->domain_type);
   Free (wfa->tree);
   Free (wfa->x);
   Free (wfa->y);
   Free (wfa->mv_tree);
   Free (wfa->y_state);
   Free (wfa->into);
   Free (wfa->weight);
   Free (wfa->int_weight);
   Free (wfa->wfainfo);
   Free (wfa->prediction);
   Free (wfa->delta_state);
   if (wfa->y_column)
      Free (wfa->y_column);
   Free (wfa);
}

real_t 
compute_final_distribution (unsigned state, const wfa_t *wfa)
/*
 *  Compute the final distribution of the given 'state'.
 *  Uses the fact that the generated 'wfa' is average preserving.
 *
 *  Return value:
 *	final distribution
 */
{
   unsigned label;
   real_t   final = 0;

   for (label = 0; label < MAXLABELS; label++)
   {
      unsigned edge;
      int      domain;
      
      if (ischild (domain = wfa->tree [state][label]))
	 final += wfa->final_distribution [domain];
      for (edge = 0; isedge (domain = wfa->into [state][label][edge]); edge++)
	 final += wfa->weight [state][label][edge]
		  * wfa->final_distribution [domain];
   }
   
   return final / MAXLABELS;
}

word_t *
compute_hits (unsigned from, unsigned to, unsigned n, const wfa_t *wfa)
/*
 *  Selects the 'n' most popular domain images of the given 'wfa'.
 *  Consider only linear combinations of state images
 *  {i | 'from' <= i <= 'to'}. I.e. domains are in {i | from <= i < 'to'}
 *  Always ensure that state 0 is among selected states even though from
 *  may be > 0.
 *  
 *  Return value:
 *	pointer to array of the most popular state images
 *	sorted by increasing state numbers and terminated by -1
 */
{
   word_t   *domains;
   unsigned  state, label, edge;
   int       domain;
   pair_t   *hits = Calloc (to, sizeof (pair_t));

   for (domain = 0; domain < (int) to; domain++)
   {
      hits [domain].value = domain;
      hits [domain].key   = 0;
   }
   
   for (state = from; state <= to; state++)
      for (label = 0; label < MAXLABELS; label++)
	 for (edge = 0; isedge (domain = wfa->into [state][label][edge]);
	      edge++)
	    hits [domain].key++;

   qsort (hits + 1, to - 1, sizeof (pair_t), sort_desc_pair);

   n       = min (to, n);
   domains = Calloc (n + 1, sizeof (word_t));

   for (domain = 0; domain < (int) n && (!domain || hits [domain].key);
	domain++)
      domains [domain] = hits [domain].value;
   if (n != domain)
      debug_message ("Only %d domains have been used in the luminance.",
		     domain);
   n = domain;
   qsort (domains, n, sizeof (word_t), sort_asc_word);
   domains [n] = -1;
   
   Free (hits);
   
   return domains;
}

void
append_edge (unsigned from, unsigned into, real_t weight,
	     unsigned label, wfa_t *wfa)
/*
 *  Append an edge from state 'from' to state 'into' with
 *  the given 'label' and 'weight' to the 'wfa'.
 *
 *  No return value.
 *
 *  Side effects:
 *	'wfa' structure is changed.
 */
{
   unsigned new;			/* position of the new edge */
   unsigned edge;

   /*
    *  First look where to insert the new edge:
    *  edges are sorted by increasing 'into' values
    */
   for (new = 0; (isedge (wfa->into [from][label][new])
		  && wfa->into [from][label][new] < (int) into); new++)
      ;
   /*
    *  Move the edges 'n' to position 'n+1', for n = max, ..., 'new'
    */
   for (edge = new; isedge (wfa->into [from][label][edge]); edge++)
      ;
   for (edge++; edge != new; edge--)
   {
      wfa->into [from][label][edge]    = wfa->into [from][label][edge - 1];
      wfa->weight [from][label][edge]  = wfa->weight [from][label][edge - 1];
      wfa->int_weight [from][label][edge]
	 = wfa->int_weight [from][label][edge - 1];
   }
   /*
    *  Insert the new edge
    */
   wfa->into [from][label][edge]       = into;
   wfa->weight [from][label][edge]     = weight;
   wfa->int_weight [from][label][edge] = weight * 512 + 0.5;
}

void 
remove_states (unsigned from, wfa_t *wfa)
/* 
 *  Remove 'wfa' states 'wfa->basis_states',...,'wfa->states' - 1.
 *
 *  No return value.
 *
 *  Side effects:
 *	'wfa' structure is cleared for the given states.
 */
{
   unsigned state;

   for (state = from; state < wfa->states; state++)
   {
      unsigned label;
      
      for (label = 0; label < MAXLABELS; label++) 
      {
	 wfa->into [state][label][0]      = NO_EDGE;
	 wfa->tree [state][label]         = RANGE;
	 wfa->prediction [state][label]   = FALSE;
	 wfa->y_state [state][label]      = RANGE;
	 wfa->mv_tree [state][label].type = NONE;
	 wfa->mv_tree [state][label].fx   = 0;
	 wfa->mv_tree [state][label].fy   = 0;
	 wfa->mv_tree [state][label].bx   = 0;
	 wfa->mv_tree [state][label].by   = 0;
      }
      wfa->domain_type [state] = 0;
      wfa->delta_state [state] = FALSE;
   }

   wfa->states = from;
}

void
copy_wfa (wfa_t *dst, const wfa_t *src)
/*
 *  Copy WFA struct 'src' to WFA struct 'dst'.
 *
 *  No return value.
 *
 *  Side effects:
 *	'dst' is filled with same data as 'src'
 *
 *  NOTE: size of WFA 'dst' must be at least size of WFA 'src'
 */
{
   unsigned state;

   memset (dst->final_distribution, 0, MAXSTATES * sizeof (real_t));
   memset (dst->level_of_state, 0, MAXSTATES * sizeof (byte_t));
   memset (dst->domain_type, 0, MAXSTATES * sizeof (byte_t));
   memset (dst->mv_tree, 0, MAXSTATES * MAXLABELS * sizeof (mv_t));
   memset (dst->tree, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
   memset (dst->x, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
   memset (dst->y, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
   memset (dst->y_state, 0, MAXSTATES * MAXLABELS * sizeof (word_t));
   memset (dst->into, NO_EDGE,
	   MAXSTATES * MAXLABELS * (MAXEDGES + 1) * sizeof (word_t));
   memset (dst->weight, 0,
	   MAXSTATES * MAXLABELS * (MAXEDGES + 1) * sizeof (real_t));
   memset (dst->int_weight, 0,
	   MAXSTATES * MAXLABELS * (MAXEDGES + 1) * sizeof (word_t));
   memset (dst->prediction, 0, MAXSTATES * MAXLABELS * sizeof (byte_t));
   memset (dst->delta_state, 0, MAXSTATES * sizeof (bool_t));
   if (dst->y_column)
      memset (dst->y_column, 0, MAXSTATES * MAXLABELS * sizeof (byte_t));

   for (state = 0; state < MAXSTATES; state++) /* clear WFA struct */
   {
      unsigned label;
      
      for (label = 0; label < MAXLABELS; label++)
      {
	 dst->into [state][label][0]      = NO_EDGE;
	 dst->tree [state][label]         = RANGE;
	 dst->mv_tree [state][label].type = NONE;
	 dst->y_state[state][label]       = RANGE;
      }
      dst->delta_state [state] = NO;
      dst->domain_type [state] = 0;
   }
   
   dst->frame_type   = src->frame_type;
   dst->states 	     = src->states;
   dst->basis_states = src->basis_states;
   dst->root_state   = src->root_state;

   memcpy (dst->wfainfo, src->wfainfo, sizeof (wfa_info_t));

   if (dst->states == 0)		/* nothing to do */
      return;

   memcpy (dst->final_distribution, src->final_distribution,
	   src->states * sizeof (real_t));
   memcpy (dst->level_of_state, src->level_of_state,
	   src->states * sizeof (byte_t));
   memcpy (dst->domain_type, src->domain_type,
	   src->states * sizeof (byte_t));
   memcpy (dst->delta_state, src->delta_state,
	   src->states * sizeof (bool_t));
   memcpy (dst->mv_tree, src->mv_tree,
	   src->states * MAXLABELS * sizeof (mv_t));
   memcpy (dst->tree, src->tree,
	   src->states * MAXLABELS * sizeof (word_t));