/* *  matrices.c:		Input of transition matrices * *  Written by:		Ullrich Hafner *   *  This file is part of FIASCO (獸籸actal 獻(xiàn)籱age 獳籲d 玈籩quence 獵O籨ec) *  Copyright (C) 1994-2000 Ullrich Hafner <hafner@bigfoot.de> *//* *  $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 "matrices.h"#if STDC_HEADERS#	include <stdlib.h>#endif /* not STDC_HEADERS *//*****************************************************************************				prototypes  *****************************************************************************/static unsigneddelta_decoding (wfa_t *wfa, unsigned last_domain, bitfile_t *input);static unsignedcolumn_0_decoding (wfa_t *wfa, unsigned last_row, bitfile_t *input);static unsignedchroma_decoding (wfa_t *wfa, bitfile_t *input);static voidcompute_y_state (int state, int y_state, wfa_t *wfa);/*****************************************************************************				public code  *****************************************************************************/unsignedread_matrices (wfa_t *wfa, bitfile_t *input)/*  *  Read transitions of WFA given from the stream 'input'. * *  Return value: *	number of edges * *  Side effects: *	'wfa->into' is filled with decoded values  */{   unsigned total;			/* total number of edges in the WFA */   unsigned root_state = wfa->wfainfo->color			 ? wfa->tree [wfa->tree [wfa->root_state][0]][0]			 : wfa->root_state;   total  = column_0_decoding (wfa, root_state, input);   total += delta_decoding (wfa, root_state, input);   if (wfa->wfainfo->color)      total += chroma_decoding (wfa, input);          return total;}/*****************************************************************************				private code  *****************************************************************************/static unsigneddelta_decoding (wfa_t *wfa, unsigned last_domain, bitfile_t *input)/* *  Read transition matrices which are encoded with delta coding *  from stream 'input'. *  'last_domain' is the maximum state number used as domain image. * *  Return value: *	number of non-zero matrix elements (WFA edges) * *  Side effects: *	'wfa->into' is filled with decoded values  */{   range_sort_t	 rs;			/* ranges are sorted as in the coder */   unsigned	 max_domain;		/* dummy used for recursion */   unsigned	 range;   unsigned	 count [MAXEDGES + 1];   unsigned 	 state, label;   unsigned	*n_edges;		/* number of elements per row */   unsigned	 total = 0;		/* total number of decoded edges */   /*    *  Generate a list of range blocks.    *  The order is the same as in the coder.    */   rs.range_state      = Calloc ((last_domain + 1) * MAXLABELS,				 sizeof (u_word_t));   rs.range_label      = Calloc ((last_domain + 1) * MAXLABELS,				 sizeof (byte_t));   rs.range_max_domain = Calloc ((last_domain + 1) * MAXLABELS,				 sizeof (u_word_t));   rs.range_subdivided = Calloc ((last_domain + 1) * MAXLABELS,				 sizeof (bool_t));   rs.range_no	       = 0;   max_domain 	       = wfa->basis_states - 1;   sort_ranges (last_domain, &max_domain, &rs, wfa);   /*    *  Get row statistics    */   {      arith_t  *decoder;      model_t  *elements;      unsigned 	max_edges = read_rice_code (3, input);            /*       *  Get the probability array of the number of edges distribution       *  and allocate the corresponding model.       */      {	 unsigned edge;	 	 for (edge = 0; edge <= max_edges; edge++)	    count [edge] = read_rice_code ((int) log2 (last_domain) - 2,					   input);	 elements = alloc_model (max_edges + 1, 0, 0, count);      }            /*       *  Get number of elements per matrix row       */      {	 unsigned row;      	 n_edges = Calloc (wfa->states, sizeof (unsigned));	 decoder = alloc_decoder (input);	 for (row = range = 0; range < rs.range_no; range++)	    if (!rs.range_subdivided [range])	    {	       state = rs.range_state [range];	       label = rs.range_label [range];	       	       n_edges [row++]		  = decode_symbol (decoder, elements)		  - (isedge (wfa->into [state][label][0]) ? 1 : 0);	    }	 	 free_decoder (decoder);	 free_model (elements);      }   }      /*    *  Get matrix elements    */   {      unsigned row;      u_word_t *mapping1           = Calloc (wfa->states, sizeof (word_t));      u_word_t *mapping_coder1     = Calloc (wfa->states, sizeof (word_t));      u_word_t *mapping2           = Calloc (wfa->states, sizeof (word_t));      u_word_t *mapping_coder2     = Calloc (wfa->states, sizeof (word_t));      bool_t	use_normal_domains = get_bit (input);      bool_t	use_delta_domains  = get_bit (input);	        /*       *  Generate array of states which are admitted domains.       *  When coding intra frames 'mapping1' == 'mapping2' otherwise       *  'mapping1' is a list of 'normal' domains which are admitted for        *             coding intra blocks       *  'mapping2' is a list of 'delta' domains which are admitted for       *             coding the motion compensated prediction error        */      {	 unsigned n1, n2, state;	    	 for (n1 = n2 = state = 0; state < wfa->states; state++)	 {	    mapping1 [n1] = state;	    mapping_coder1 [state] = n1;	    if (usedomain (state, wfa)		&& (state < wfa->basis_states		    || use_delta_domains || !wfa->delta_state [state]))	       n1++;	    	    mapping2 [n2] = state;	    mapping_coder2 [state] = n2;	    if (usedomain (state, wfa)		&& (state < wfa->basis_states || use_normal_domains		    || wfa->delta_state [state]))	       n2++;	 }      }	       for (row = 0, range = 0; range < rs.range_no; range++)	 if (!rs.range_subdivided [range])	 {	    u_word_t *mapping;	    u_word_t *mapping_coder;	    unsigned  max_value;	    unsigned  edge;	    unsigned  state = rs.range_state [range];	    unsigned  label = rs.range_label [range];	    unsigned  last  = 1;	    if (wfa->delta_state [state] ||		wfa->mv_tree [state][label].type != NONE)	    {	       mapping 	     = mapping2;	       mapping_coder = mapping_coder2;	    }	    else	    {	       mapping 	     = mapping1;	       mapping_coder = mapping_coder1;	    }	    max_value = mapping_coder [rs.range_max_domain [range]];	    for (edge = n_edges [row]; edge; edge--)	    {	       unsigned domain;	       if (max_value - last)		  domain = read_bin_code (max_value - last, input) + last;	       else		  domain = max_value;	       append_edge (state, mapping [domain], -1, label, wfa);	       last = domain + 1;	       total++;	    }	    row++;	 }      Free (mapping1);      Free (mapping_coder1);      Free (mapping2);      Free (mapping_coder2);   }         Free (n_edges);   Free (rs.range_state);   Free (rs.range_label);   Free (rs.range_max_domain);   Free (rs.range_subdivided);   return total;}static unsignedcolumn_0_decoding (wfa_t *wfa, unsigned last_row, bitfile_t *input)/* *  Read column 0 of the transition matrices of the 'wfa' which are coded *  with quasi arithmetic coding from stream 'input'. *  All rows from 'wfa->basis_states' up to 'last_row' are decoded. *  *  Return value: *	number of non-zero matrix elements (WFA edges) * *  Side effects: *	'wfa->into' is filled with decoded values  */{   unsigned  row;			/* current matrix row */   unsigned  total = 0;			/* total number of edges in col 0 */   unsigned *prob_ptr;			/* pointer to current probability */   unsigned *last;			/* pointer to minimum probability */   unsigned *first;			/* pointer to maximum probability */   unsigned *new_prob_ptr;		/* ptr to probability of last domain */   unsigned *prob;			/* probability array */   u_word_t  high;			/* Start of the current code range */   u_word_t  low;			/* End of the current code range */   u_word_t  code;			/* The present input code value */   word_t   *is_leaf;			/* pointer to the tree structure */   /*    *  Compute the asymmetric probability array    *  prob[] = { 1/2, 1/2, 1/4, 1/4, 1/4, 1/4,    *             1/8, ... , 1/16, ..., 1/(MAXPROB+1)}    */   {      unsigned n;      unsigned index;			/* probability index */      unsigned exp;			/* current exponent */            prob = Calloc (1 << (MAX_PROB + 1), sizeof (unsigned));         for (index = 0, n = MIN_PROB; n <= MAX_PROB; n++)	 for (exp = 0; exp < 1U << n; exp++, index++)	    prob [index] = n;   }   first = prob_ptr = new_prob_ptr = prob;   last  = first + 1020;      is_leaf = wfa->tree [wfa->basis_states]; /* use pointer arithmetics ... */   high = HIGH;				/* 1.0 */   low  = LOW;				/* 0.0 */   code = get_bits (input, 16);		   /*    *  Decode column 0 with a quasi arithmetic coder (QAC).    *  Advantage of this QAC with respect to a binary AC:    *  Instead of using time consuming multiplications and divisions    *  to compute the probability of the most probable symbol (MPS) and    *  the range of the interval, a table look up procedure linked    *  with a shift operation is used for both computations.    *    *  Loops and array accesses have been removed    *  to make real time decoding possible.