arc.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "arc.h"
#include <sys/time.h>
#include <string.h>
#include <float.h>
#include <setjmp.h>
#include "defines.h"
#include "profiler.h"
#include "util.h"

Functions
static void	arc_display (const fsm_table *table, unsigned int fr_width, unsigned int to_width)
int	arc_find_from_state (const fsm_table *table, const vector *st)
	Finds the specified FROM state in the given FSM table.
int	arc_find_to_state (const fsm_table *table, const vector *st)
	Finds the specified TO state in the given FSM table.
int	arc_find_arc (const fsm_table *table, unsigned int fr_index, unsigned int to_index)
	Finds the specified state transition in the given FSM table.
int	arc_find_arc_by_exclusion_id (const fsm_table *table, int id)
	Finds the specified state transition in the given FSM table by the exclusion ID.
fsm_table *	arc_create ()
	Allocates and initializes new state transition array.
void	arc_add (fsm_table *table, const vector *fr_st, const vector *to_st, int hit, bool exclude)
	Adds new state transition arc entry to specified table.
static int	arc_state_hits (const fsm_table *table)
static int	arc_transition_hits (const fsm_table *table)
static int	arc_transition_excluded (const fsm_table *table)
void	arc_get_stats (const fsm_table *table, int *state_hits, int *state_total, int *arc_hits, int *arc_total, int *arc_excluded)
	Calculates all state and state transition values for reporting purposes.
void	arc_db_write (const fsm_table *table, FILE *file)
	Writes specified arc array to specified CDD file.
void	arc_db_read (fsm_table **table, char **line)
	Reads in arc array from CDD database string.
void	arc_db_merge (fsm_table *base, char **line)
	Merges contents of arc table from line to specified base array.
void	arc_merge (fsm_table *base, const fsm_table *other)
	Merges two FSM arcs, placing the results in the base arc.
void	arc_get_states (char ***fr_states, unsigned int *fr_state_size, char ***to_states, unsigned int *to_state_size, const fsm_table *table, bool hit, bool any, unsigned int fr_width, unsigned int to_width)
	Stores arc array state values to specified string array.
void	arc_get_transitions (char ***from_states, char ***to_states, int **ids, int **excludes, char ***reasons, int *arc_size, const fsm_table *table, func_unit *funit, bool hit, bool any, unsigned int fr_width, unsigned int to_width)
	Outputs arc array state transition values to specified output stream.
bool	arc_are_any_excluded (const fsm_table *table)
	Specifies if any state transitions have been excluded from coverage.
void	arc_dealloc (fsm_table *table)
	Deallocates memory for specified arcs array.
Variables
int	curr_arc_id = 1

---

Detailed Description

Author:

Trevor Williams (phase1geo@gmail.com)

Date:

8/25/2003

What is an arc?

This group of functions handles the allocation, initialization, deallocation, and manipulation of an arc array. An arc array is a specialized, variable sized, compact byte array that contains all of the information necessary for storing state and state transition information for a single FSM within a design. To store this information into as compact a representation as possible, the data is bit-packed into the array.

The first 7 bytes of the array are known as the "arc header". Every arc array is required to have this information. The layout of the header is shown below:

Byte	Description
0	Bits [ 7:0] of output state variable width
1	Bits [15:8] of output state variable width
2	Bits [ 7:0] of number of state transition entries currently allocated
3	Bits [15:8] of number of state transition entries currently allocated
4	Bits [ 7:0] of number of state transition entries currently occupied
5	Bits [15:8] of number of state transition entries currently occupied
6	Bits [ 7:0] of arc array supplemental field

Note: The arc array supplemental field contains miscellaneous information about this arc array. Currently, only bit 0 is used to indicate if the user has specified state transitions manually (using the Verilog-2001 inline attribute mechanism) or whether no state transitions are known prior to simulation.

The rest of the bytes in the arc array represent a list of state transition entries. An entry contains enough information to describe a bidirectional state transition with coverage information. The bit-width of an entry is determined by taking bytes 0 & 1 of the header (the output state variable width, multiplying this value by 2, and adding the number of entry supplemental bits for an entry (currently this value is 6). Each entry is byte-aligned in the arc array. The fields that comprise an entry are described below.

Bits	Description
0	Set to 1 if the forward bidirectional state transition was hit; otherwise, set to 0.
1	Set to 1 if the reverse bidirectional state transition was hit; otherwise, set to 0.
2	Set to 1 if this entry is bidirectional (reverse is a transition); otherwise, only forward is valid.
3	Set to 1 if the output state of the forward transition is a new state in the arc array.
4	Set to 1 if the input state of the forward transition is a new state in the arc array.
5	Set to 1 if the forward state transition is excluded from coverage.
6	Set to 1 if the reverse state transition is excluded from coverage.
(width + 6):7	Bit value of output state of the forward transition.
((width * 2) + 6):(width + 7)	Bit value of input state of the forward transition.

Adding State Transitions

When an state transition occurs during simulation, the arc array is searched to see if an entry already exists that contains the same state transition. If no matching entry is found, a new entry is added to the existing arc array. If the arc array allocated is currently full (current allocated size in header equals the current number of used entries), the array is grown. The number of entries that the array grows is equal to the bit width of the output state variable. When the new state is added, the entry is stored as a "forward" entry. A forward entry is an entry that contains the input state value in the upper bits of the entry and the output state value in the lower bits of the entry. If the state is added prior to simulation, bit 0 (hit forward) of the entry is set to 0; otherwise, it is set to a value of 1, indicating that the forward version of the state transition was hit. If a state transition is found in the array but the order of the input and output values are reversed from the stored entry, the entry is stored into the same entry, setting bit 2 (bidirectional entry bit) to a value of 1. This indicates that the current entry contains a forward entry and a reverse entry (input state value is stored in lower order bits and output state value is stored in upper order bits of the entry). If this type of entry is stored prior to simulation, bit 1 (reverse hit bit) is set to 0; otherwise, the bit is set to a value of 1. The following example shows an arc array as state transitions are added to it during simulation.

HF: Forward direction hit, HR: Reverse direction hit, BD: Entry is bidirectional

Event	Entry			Action
	0	1	2
Add 0->1	0->1,HF=1,HR=0,BD=0			0->1 not found in table, add as forward in entry 0
Add 1->2	0->1,HF=1,HR=0,BD=0	1->2,HF=1,HR=0,BD=0		1->2 not found in table, add as forward in entry 1
Add 1->0	0->1,HF=1,HR=1,BD=1	1->2,HF=1,HR=0,BD=0		1->0 found in entry 0, add as reverse and set bidirectional entry bit

Calculating FSM State Coverage Metrics

To calculate the number of FSM states that are in an arc array, we first need to figure out what state values are unique in the arc array. Since state transitions contain two state values (input and output), we need to compare each state whether it is an input or an output state to every other state value in the arc array. To do this, we start with the input state (in the forward direction -- value in upper bits of entry) in entry 0 and compare it to each and every state in the arc array. If the current state value matches the first entry and the current state value is in the upper bits of the entry, bit 4 is set in the entry's supplemental field to indicate that its state is not unique. If the current state value matches the first entry and the current state value is in the lower bits of the entry, bit 5 is set in the entry's supplemental field to indicate that its state is not unique. If the current value does not match the first state value, nothing happens. After all states have been compared, the right value (if bit 5 in its entry supplemental field is not set) is compared to all of the rest of the state values (if their bit 4 or bit 5 in their supplemental field is not already set) are compared. This continues for all state values. After the state comparing phase has occurred, we can simply walk through the arc array counting all of the states that do not have their corresponding bit 4 or bit 5 set.

Calculating FSM State Transition Coverage Metrics

To calculate state transition coverage for the arc array is simple. Just count the number of entries that have bit 0 set to 1 and bits 1 and 2 set to 1. This will give you the number of state transitions that were hit during simulation.

Outputting an Arc to a File

Writing and reading an arc to and from a file is accomplished by writing each byte in the arc array to the file in hexidecimal format (zero-filling the output) with no spaces between the bytes. Additionally, if a byte contains the hexidecimal value of 0x0, simply output a comma character (this saves one character in the file for each byte that contains a value of 0x0). Keeping the output of an arc array to as small as possible in the file is necessary due to the large memory footprint that just one FSM can take.

---

Function Documentation

void arc_add	(	fsm_table *	table,
		const vector *	fr_st,
		const vector *	to_st,
		int	hit,
		bool	exclude
	)

Adds new state transition arc entry to specified table.

If specified arcs array has not been created yet (value is set to NULL), allocate enough memory in the arc array to hold width number of state transitions. If the specified arcs array has been created but is currently full (arc array max_size and curr_size are equal to each other), add width number of more arc array entries to the current array. After memory has been allocated, create a state transition entry from the fr_st and to_st expressions, setting the hit bits in the entry to 0.

Parameters:

	table	Pointer to FSM table to add state transition arc array to
	fr_st	Pointer to vector containing the from state
	to_st	Pointer to vector containing the to state
	hit	Specifies if arc entry should be marked as hit
	exclude	If new arc is created, sets the exclude bit to this value

References asuppl_u::all, arc_find_arc(), arc_find_from_state(), arc_find_to_state(), fsm_table_s::arcs, vsuppl_u::data_type, asuppl_u::excluded, fsm_table_s::fr_states, fsm_table_arc_s::from, asuppl_u::hit, fsuppl_u::known, malloc_safe, fsm_table_s::num_arcs, fsm_table_s::num_fr_states, fsm_table_s::num_to_states, fsuppl_u::part, asuppl_u::part, vsuppl_u::part, PROFILE, PROFILE_END, realloc_safe, fsm_table_s::suppl, fsm_table_arc_s::suppl, vector_s::suppl, fsm_table_arc_s::to, fsm_table_s::to_states, TRUE, vector_copy(), vector_create(), vector_is_unknown(), VTYPE_VAL, and vector_s::width.

Referenced by arc_db_merge(), arc_merge(), fsm_create_tables(), and fsm_table_set().

  { PROFILE(ARC_ADD);

  int from_index;  /* Index of found from_state in states array */
  int to_index;    /* Index of found to_state in states array */
  int arcs_index;  /* Index of found state transition in arcs array */

  assert( table != NULL );

  if( (hit == 0) || (!vector_is_unknown( fr_st ) && !vector_is_unknown( to_st )) ) {

    /* Search for the from_state vector in the states array */
    if( (from_index = arc_find_from_state( table, fr_st )) == -1 ) {
      table->fr_states = (vector**)realloc_safe( table->fr_states, (sizeof( vector* ) * table->num_fr_states), (sizeof( vector* ) * (table->num_fr_states + 1)) );
      from_index    = table->num_fr_states;
      table->fr_states[from_index] = vector_create( fr_st->width, VTYPE_VAL, fr_st->suppl.part.data_type, TRUE );
      vector_copy( fr_st, table->fr_states[from_index] );
      table->num_fr_states++;
    }

    /* Search for the to_state vector in the states array */
    if( (to_index = arc_find_to_state( table, to_st )) == -1 ) {
      table->to_states = (vector**)realloc_safe( table->to_states, (sizeof( vector* ) * table->num_to_states), (sizeof( vector* ) * (table->num_to_states + 1)) );
      to_index      = table->num_to_states;
      table->to_states[to_index] = vector_create( to_st->width, VTYPE_VAL, to_st->suppl.part.data_type, TRUE );
      vector_copy( to_st, table->to_states[to_index] );
      table->num_to_states++;
    }

    /* If we need to add a new arc, do so now */
    if( (arcs_index = arc_find_arc( table, from_index, to_index )) == -1 ) {

      table->arcs = (fsm_table_arc**)realloc_safe( table->arcs, (sizeof( fsm_table_arc* ) * table->num_arcs), (sizeof( fsm_table_arc* ) * (table->num_arcs + 1)) );
      table->arcs[table->num_arcs] = (fsm_table_arc*)malloc_safe( sizeof( fsm_table_arc ) );
      table->arcs[table->num_arcs]->suppl.all           = 0;
      table->arcs[table->num_arcs]->suppl.part.hit      = hit;
      table->arcs[table->num_arcs]->suppl.part.excluded = exclude;
      table->arcs[table->num_arcs]->from                = from_index;
      table->arcs[table->num_arcs]->to                  = to_index;
      table->num_arcs++;

    /* Otherwise, adjust hit and exclude information */
    } else {

      table->arcs[arcs_index]->suppl.part.hit      |= hit;
      table->arcs[arcs_index]->suppl.part.excluded |= exclude;

    }

    /* If we have set a side with hit equal to 0, we are specifying a known transition. */
    if( hit == 0 ) {
      table->suppl.part.known = 1;
    }

  }

  PROFILE_END;

}

bool arc_are_any_excluded

(

const fsm_table *

table

)

Specifies if any state transitions have been excluded from coverage.

Returns:

Returns TRUE if any state transitions were excluded from coverage; otherwise, returns FALSE.

Parameters:

table

Pointer to state transition arc array

References fsm_table_s::arcs, asuppl_u::excluded, asuppl_u::part, PROFILE, PROFILE_END, and fsm_table_arc_s::suppl.

Referenced by fsm_collect().

  { PROFILE(ARC_ARE_ANY_EXCLUDED);

  unsigned int i = 0;  /* Loop iterator */

  assert( table != NULL );

  while( (i < table->num_arcs) && (table->arcs[i]->suppl.part.excluded == 0) ) i++;

  PROFILE_END;

  return( i < table->num_arcs );

}

fsm_table* arc_create

(

)

Allocates and initializes new state transition array.

Returns:

Returns a pointer to the newly created arc transition structure.

Allocates memory for a new state transition arc array and initializes its contents.

References fsuppl_u::all, fsm_table_s::arcs, fsm_table_s::fr_states, fsm_table_s::id, malloc_safe, fsm_table_s::num_arcs, fsm_table_s::num_fr_states, fsm_table_s::num_to_states, PROFILE, PROFILE_END, fsm_table_s::suppl, and fsm_table_s::to_states.

Referenced by arc_db_read(), and fsm_create_tables().

                        { PROFILE(ARC_CREATE);

  fsm_table* table;  /* Pointer to newly created FSM table */

  /* Allocate memory for the new table here */
  table = (fsm_table*)malloc_safe( sizeof( fsm_table ) );

  /* Initialize */
  table->suppl.all     = 0;
  table->id            = 0;
  table->fr_states     = NULL;
  table->num_fr_states = 0;
  table->to_states     = NULL;
  table->num_to_states = 0;
  table->arcs          = NULL;
  table->num_arcs      = 0;

  PROFILE_END;

  return( table );

}

void arc_db_merge	(	fsm_table *	base,
		char **	line
	)

Merges contents of arc table from line to specified base array.

Exceptions:

anonymous

Throw arc_db_read

Merges the specified FSM arc information from the current line into the base FSM arc information.

Parameters:

	base	Pointer to arc table to merge data into
	line	Pointer to read in line from CDD file to merge

References arc_add(), arc_db_read(), arc_dealloc(), fsm_table_s::arcs, asuppl_u::excluded, fsm_table_s::fr_states, fsm_table_arc_s::from, asuppl_u::hit, fsm_table_s::num_arcs, asuppl_u::part, PROFILE, PROFILE_END, fsm_table_arc_s::suppl, fsm_table_arc_s::to, and fsm_table_s::to_states.

Referenced by fsm_db_merge().

  { PROFILE(ARC_DB_MERGE);

  /*@-mustfreeonly -mustfreefresh@*/

  fsm_table*   table;  /* Currently read FSM table */
  unsigned int i;      /* Loop iterator */

  /* Read in the table */
  arc_db_read( &table, line );

  /* Merge state transitions */
  for( i=0; i<table->num_arcs; i++ ) {
    arc_add( base, table->fr_states[table->arcs[i]->from], table->to_states[table->arcs[i]->to], table->arcs[i]->suppl.part.hit, table->arcs[i]->suppl.part.excluded );
  }

  /* Deallocate the merged table */
  arc_dealloc( table );

  PROFILE_END;

  /*@=mustfreeonly =mustfreefresh@*/

}

void arc_db_read	(	fsm_table **	table,
		char **	line
	)

Reads in arc array from CDD database string.

Exceptions:

anonymous

Throw

Reads in specified state transition arc table, allocating the appropriate space to hold the table. Returns TRUE if the specified line contained an appropriately written arc transition table; otherwise, returns FALSE.

Parameters:

	table	Pointer to state transition arc array
	line	String containing current CDD line of arc information

References arc_create(), arc_dealloc(), Catch_anonymous, curr_arc_id, FATAL, malloc_safe, print_output(), PROFILE, PROFILE_END, Throw, Try, and vector_db_read().

Referenced by arc_db_merge(), and fsm_db_read().

  { PROFILE(ARC_DB_READ);

  /* Allocate table */
  *table = arc_create();

  Try {

    unsigned int num_fr_states;
    unsigned int num_to_states;
    int          chars_read;

    /*@-formatcode@*/
    if( sscanf( *line, "%hhx %u %u%n", &((*table)->suppl.all), &num_fr_states, &num_to_states, &chars_read ) == 3 ) {
    /*@=formatcode@*/

      unsigned int i;
      unsigned int num_arcs;

      *line += chars_read;

      /* Set exclusion ID */
      (*table)->id = curr_arc_id;

      /* Allocate and initialize fr_states array */
      (*table)->fr_states     = (vector**)malloc_safe( sizeof( vector* ) * num_fr_states );
      (*table)->num_fr_states = num_fr_states;
      for( i=0; i<num_fr_states; i++ ) {
        (*table)->fr_states[i] = NULL;
      }

      /* Read in from vectors */
      for( i=0; i<num_fr_states; i++ ) {
        vector_db_read( &((*table)->fr_states[i]), line );
      }

      /* Allocate and initialize to_states array */
      (*table)->to_states     = (vector**)malloc_safe( sizeof( vector* ) * num_to_states );
      (*table)->num_to_states = num_to_states;
      for( i=0; i<num_to_states; i++ ) {
        (*table)->to_states[i] = NULL;
      }

      /* Read in vectors */
      for( i=0; i<num_to_states; i++ ) {
        vector_db_read( &((*table)->to_states[i]), line );
      }

      if( sscanf( *line, "%u%n", &num_arcs, &chars_read ) == 1 ) {

        *line += chars_read;

        /* Allocate arcs array */
        (*table)->arcs     = (fsm_table_arc**)malloc_safe( sizeof( fsm_table_arc* ) * num_arcs );
        (*table)->num_arcs = num_arcs;
        for( i=0; i<num_arcs; i++ ) {
          (*table)->arcs[i] = NULL;
        }

        for( i=0; i<num_arcs; i++ ) {

          /* Allocate fsm_table_arc */
          (*table)->arcs[i] = (fsm_table_arc*)malloc_safe( sizeof( fsm_table_arc ) );

          /*@-formatcode@*/
          if( sscanf( *line, "%u %u %hhx%n", &((*table)->arcs[i]->from), &((*table)->arcs[i]->to), &((*table)->arcs[i]->suppl.all), &chars_read ) != 3 ) {
          /*@=formatcode@*/
            print_output( "Unable to parse FSM table information from database.  Unable to read.", FATAL, __FILE__, __LINE__ );
            Throw 0;
          } else {
            *line += chars_read;
            curr_arc_id++;
          }

        }

      } else {
        print_output( "Unable to parse FSM table information from database.  Unable to read.", FATAL, __FILE__, __LINE__ );
        Throw 0;
      }

    } else {
      print_output( "Unable to parse FSM table information from database.  Unable to read.", FATAL, __FILE__, __LINE__ );
      Throw 0;
    }

  } Catch_anonymous {
    arc_dealloc( *table );
    *table = NULL;
    Throw 0;
  }

  PROFILE_END;

}

void arc_db_write	(	const fsm_table *	table,
		FILE *	file
	)

Writes specified arc array to specified CDD file.

Writes the specified arcs array to the specified CDD output file. An arc array is output in a special format that is described in the above documentation for this file.

Parameters:

	table	Pointer to state transition arc array to write
	file	Pointer to CDD file to write

References asuppl_u::all, fsuppl_u::all, fsm_table_s::arcs, FALSE, fsm_table_s::fr_states, fsm_table_arc_s::from, fsm_table_s::num_arcs, fsm_table_s::num_fr_states, fsm_table_s::num_to_states, PROFILE, PROFILE_END, fsm_table_arc_s::suppl, fsm_table_s::suppl, fsm_table_arc_s::to, fsm_table_s::to_states, TRUE, and vector_db_write().

Referenced by fsm_db_write().

  { PROFILE(ARC_DB_WRITE);

  unsigned int  i;   /* Loop iterator */

  assert( table != NULL );

  /*@-formatcode@*/
  fprintf( file, " %hhx %u %u ", table->suppl.all, table->num_fr_states, table->num_to_states );
  /*@=formatcode@*/

  /* Output state information */
  for( i=0; i<table->num_fr_states; i++ ) {
    vector_db_write( table->fr_states[i], file, TRUE, FALSE );
    fprintf( file, "  " );
  }
  for( i=0; i<table->num_to_states; i++ ) {
    vector_db_write( table->to_states[i], file, TRUE, FALSE );
    fprintf( file, "  " );
  }

  /* Output arc information */
  fprintf( file, " %u", table->num_arcs );
  for( i=0; i<table->num_arcs; i++ ) {
    /*@-formatcode@*/
    fprintf( file, "  %u %u %hhx", table->arcs[i]->from, table->arcs[i]->to, table->arcs[i]->suppl.all );
    /*@=formatcode@*/
  }

  PROFILE_END;

}

void arc_dealloc

(

fsm_table *

table

)

Deallocates memory for specified arcs array.

Deallocates all allocated memory for the specified state transition arc array.

Parameters:

table

Pointer to state transition arc array

References fsm_table_s::arcs, fsm_table_s::fr_states, free_safe, fsm_table_s::num_arcs, fsm_table_s::num_fr_states, fsm_table_s::num_to_states, PROFILE, PROFILE_END, fsm_table_s::to_states, and vector_dealloc().

Referenced by arc_db_merge(), arc_db_read(), fsm_db_write(), and fsm_dealloc().

  { PROFILE(ARC_DEALLOC);

  if( table != NULL ) {

    unsigned int i;

    /* Deallocate fr_states */
    for( i=0; i<table->num_fr_states; i++ ) {
      vector_dealloc( table->fr_states[i] );
    }
    free_safe( table->fr_states, (sizeof( vector* ) * table->num_fr_states) );

    /* Deallocate to_states */
    for( i=0; i<table->num_to_states; i++ ) {
      vector_dealloc( table->to_states[i] );
    }
    free_safe( table->to_states, (sizeof( vector* ) * table->num_to_states) );

    /* Deallocate arcs */
    for( i=0; i<table->num_arcs; i++ ) {
      free_safe( table->arcs[i], sizeof( fsm_table_arc ) );
    }
    free_safe( table->arcs, (sizeof( fsm_table_arc* ) * table->num_arcs) );

    /* Now deallocate ourself */
    free_safe( table, sizeof( fsm_table ) );

  }

  PROFILE_END;

}

static void arc_display	(	const fsm_table *	table,
		unsigned int	fr_width,
		unsigned int	to_width
	)			[static]

Displays the given state transition arcs in a human-readable format.

Parameters:

	table	Pointer to state transition arc array to display
	fr_width	Width of "from" state
	to_width	Width of "to" state

References fsm_table_s::arcs, asuppl_u::excluded, fsm_table_s::fr_states, free_safe, fsm_table_arc_s::from, HEXIDECIMAL, asuppl_u::hit, fsm_table_s::num_arcs, asuppl_u::part, fsm_table_arc_s::suppl, fsm_table_arc_s::to, fsm_table_s::to_states, TRUE, and vector_to_string().

  {

  unsigned int i;  /* Loop iterator */

  assert( table != NULL );

  for( i=0; i<table->num_arcs; i++ ) {

    char* lvec = vector_to_string( table->fr_states[table->arcs[i]->from], HEXIDECIMAL, TRUE, fr_width );
    char* rvec = vector_to_string( table->to_states[table->arcs[i]->to],   HEXIDECIMAL, TRUE, to_width );

    printf( "       entry %u: ", i );

    /* Output the state transition */
    printf( "%s", lvec );
    printf( " --> " );
    printf( "%s", rvec );

    /* Now output the relevant supplemental information */
    printf( "  (%s %s)\n",
            ((table->arcs[i]->suppl.part.excluded == 1) ? "E" : "  "),
            ((table->arcs[i]->suppl.part.hit      == 1) ? "H" : "  ") );

    
    /* Deallocate strings */
    free_safe( lvec, (strlen( lvec ) + 1) );
    free_safe( rvec, (strlen( rvec ) + 1) );

  }

}

int arc_find_arc	(	const fsm_table *	table,
		unsigned int	fr_index,
		unsigned int	to_index
	)

Finds the specified state transition in the given FSM table.

Returns:

Returns the index of the found arc in the arcs array if it is found; otherwise, returns -1.

Searches for the arc in the arcs array of the given FSM table specified by the given state indices.

Parameters:

	table	Pointer to FSM table to search in
	fr_index	Index of from state to find
	to_index	Index of to state to find

References fsm_table_s::arcs, fsm_table_arc_s::from, PROFILE, PROFILE_END, and fsm_table_arc_s::to.

Referenced by arc_add(), exclude_is_fsm_excluded(), and exclude_set_fsm_exclude().

  { PROFILE(ARC_FIND_ARC);

  int          index = -1;
  unsigned int i     = 0;

  while( (i < table->num_arcs) && (index == -1) ) {
    if( (table->arcs[i]->from == fr_index) && (table->arcs[i]->to == to_index) ) {
      index = i;
    }
    i++;
  }

  PROFILE_END;

  return( index );

}

int arc_find_arc_by_exclusion_id	(	const fsm_table *	table,
		int	id
	)

Finds the specified state transition in the given FSM table by the exclusion ID.

Returns:

Returns the index of the found arc in the arcs array if it is found; otherwise, returns -1.

Parameters:

	table	Pointer to FSM table structure to search
	id	Exclusion ID to search for

References fsm_table_s::id, fsm_table_s::num_arcs, PROFILE, and PROFILE_END.

Referenced by instance_find_fsm_arc_index_by_exclusion_id().

  { PROFILE(ARC_FIND_ARC_BY_EXCLUSION_ID);

  int index = -1;

  if( (table->id <= id) && ((table->id + table->num_arcs) > id) ) {
    index = id - table->id;
  }

  PROFILE_END;

  return( index );

}

int arc_find_from_state	(	const fsm_table *	table,
		const vector *	st
	)

Finds the specified FROM state in the given FSM table.

Returns:

Returns the index of the found from_state in the fr_states array if one is found; otherwise, returns -1 to indicate that a match could not be found.

Searches the list of FROM states for a match to the given vector value.

Parameters:

	table	Pointer to FSM table to search in
	st	State to search for

References fsm_table_s::fr_states, PROFILE, PROFILE_END, and vector_ceq_ulong().

Referenced by arc_add(), exclude_is_fsm_excluded(), and exclude_set_fsm_exclude().

  { PROFILE(ARC_FIND_FROM_STATE);

  int          index = -1;  /* Return value for this function */
  unsigned int i     = 0;   /* Loop iterator */

  assert( table != NULL );

  while( (i < table->num_fr_states) && !vector_ceq_ulong( st, table->fr_states[i] ) ) i++;
  if( i < table->num_fr_states ) {
    index = i;
  }

  PROFILE_END;

  return( index );

}

int arc_find_to_state	(	const fsm_table *	table,
		const vector *	st
	)

Finds the specified TO state in the given FSM table.

Returns:

Returns the index of the found to_state in the to_states array if one is found; otherwise, returns -1 to indicate that a match could not be found. that no match occurred.

Searches the list of TO states for a match to the given vector value.

Parameters:

	table	Pointer to FSM table to search in
	st	State to search for

References PROFILE, PROFILE_END, fsm_table_s::to_states, and vector_ceq_ulong().

Referenced by arc_add(), exclude_is_fsm_excluded(), and exclude_set_fsm_exclude().

  { PROFILE(ARC_FIND_TO_STATE);

  int          index = -1;  /* Return value for this function */
  unsigned int i     = 0;   /* Loop iterator */

  assert( table != NULL );

  while( (i < table->num_to_states) && !vector_ceq_ulong( st, table->to_states[i] ) ) i++;
  if( i < table->num_to_states ) {
    index = i;
  }

  PROFILE_END;

  return( index );

}

void arc_get_states	(	char ***	fr_states,
		unsigned int *	fr_state_size,
		char ***	to_states,
		unsigned int *	to_state_size,
		const fsm_table *	table,
		bool	hit,
		bool	any,
		unsigned int	fr_width,
		unsigned int	to_width
	)

Stores arc array state values to specified string array.

Traverses entire arc array, storing all states that were hit during simulation (if hit parameter is true or the any parameter is true) or missed during simulation (if hit parameter is false or the any parameter is true).

Parameters:

	fr_states	Pointer to string array containing stringified state information
	fr_state_size	Pointer to number of elements stored in states array
	to_states	Pointer to string array containing stringified state information
	to_state_size	Pointer to number of elements stored in states array
	table	Pointer to FSM table
	hit	Specifies if hit or missed transitions should be gathered
	any	Specifies if we should gather any transition or only the type specified by hit
	fr_width	Width of "from" FSM state to output
	to_width	Width of "to" FSM state to output

References fsm_table_s::arcs, fsm_table_s::fr_states, fsm_table_arc_s::from, HEXIDECIMAL, asuppl_u::hit, fsm_table_s::num_arcs, fsm_table_s::num_fr_states, fsm_table_s::num_to_states, asuppl_u::part, PROFILE, PROFILE_END, realloc_safe, fsm_table_arc_s::suppl, fsm_table_arc_s::to, fsm_table_s::to_states, TRUE, and vector_to_string().

Referenced by fsm_display_state_verbose(), and fsm_get_coverage().

  { PROFILE(ARC_GET_STATES);

  unsigned int i, j;  /* Loop iterator */

  /*@-nullstate@*/

  assert( fr_states != NULL );
  assert( fr_state_size != NULL );
  assert( to_states != NULL );
  assert( to_state_size != NULL );

  /* Initialize states array pointers and sizes */
  *fr_states     = NULL;
  *fr_state_size = 0;
  *to_states     = NULL;
  *to_state_size = 0;

  /* Iterate through the fr_states array, gathering all matching states */
  for( i=0; i<table->num_fr_states; i++ ) {
    bool state_hit = any;
    for( j=0; j<table->num_arcs; j++ ) {
      if( table->arcs[j]->from == i ) {
        state_hit = state_hit || (table->arcs[j]->suppl.part.hit == 1);
      }
    }
    if( state_hit == hit ) {
      *fr_states                     = (char**)realloc_safe( *fr_states, (sizeof( char* ) * (*fr_state_size)), (sizeof( char* ) * ((*fr_state_size) + 1)) );
      (*fr_states)[(*fr_state_size)] = vector_to_string( table->fr_states[i], HEXIDECIMAL, TRUE, fr_width );
      (*fr_state_size)++;
    }
  }

  /* Iterate through the to_states array, gathering all matching states */
  for( i=0; i<table->num_to_states; i++ ) {
    bool state_hit = any;
    for( j=0; j<table->num_arcs; j++ ) { 
      if( table->arcs[j]->to == i ) {
        state_hit = state_hit || (table->arcs[j]->suppl.part.hit == 1);
      }
    }
    if( state_hit == hit ) {
      *to_states                     = (char**)realloc_safe( *to_states, (sizeof( char* ) * (*to_state_size)), (sizeof( char* ) * ((*to_state_size) + 1)) );
      (*to_states)[(*to_state_size)] = vector_to_string( table->to_states[i], HEXIDECIMAL, TRUE, to_width );
      (*to_state_size)++;
    }
  }

  PROFILE_END;

}

void arc_get_stats	(	const fsm_table *	table,
		int *	state_hits,
		int *	state_total,
		int *	arc_hits,
		int *	arc_total,
		int *	arc_excluded
	)

Calculates all state and state transition values for reporting purposes.

Calculates values for all specified totals from given state transition arc array. If the state and state transition totals are not known (i.e., user specified state variables without specifying legal states and state transitions and/or the user specified state variables and state table was not able to be automatically extracted), return a value of -1 for total values to indicate to the calling function that a different report output is required.

Parameters:

	table	Pointer to FSM table
	state_hits	Pointer to total number of states hit during simulation
	state_total	Pointer to total number of states in table
	arc_hits	Pointer to total number of state transitions hit during simulation
	arc_total	Pointer to total number of state transitions in table
	arc_excluded	Pointer to total number of excluded arcs

References arc_state_hits(), arc_transition_excluded(), arc_transition_hits(), fsuppl_u::known, fsm_table_s::num_arcs, fsm_table_s::num_fr_states, fsuppl_u::part, PROFILE, PROFILE_END, and fsm_table_s::suppl.

Referenced by fsm_collect(), and fsm_get_stats().

  { PROFILE(ARC_GET_STATS);

  /* First get hits */
  *state_hits   += arc_state_hits( table );
  *arc_hits     += arc_transition_hits( table );
  *arc_excluded += arc_transition_excluded( table );
  
  /* If the state transitions are known, calculate them; otherwise, return -1 for totals */
  if( table->suppl.part.known == 0 ) {
    *state_total = -1;
    *arc_total   = -1;
  } else {
    *state_total += table->num_fr_states;
    *arc_total   += table->num_arcs;
  }

  PROFILE_END;

}

void arc_get_transitions	(	char ***	from_states,
		char ***	to_states,
		int **	ids,
		int **	excludes,
		char ***	reasons,
		int *	arc_size,
		const fsm_table *	table,
		func_unit *	funit,
		bool	hit,
		bool	any,
		unsigned int	fr_width,
		unsigned int	to_width
	)

Outputs arc array state transition values to specified output stream.

Traverses entire arc array, storing all state transitions that were hit during simulation (if hit parameter is true or the any parameter is true) or missed during simulation (if hit parameter is false or the any parameter is true).

Parameters:

	from_states	Pointer to string array containing from_state values
	to_states	Pointer to string array containing to_state values
	ids	List of arc IDs
	excludes	Pointer to integer array containing exclude values
	reasons	Pointer to string array containing exclude reasons
	arc_size	Number of elements in both the from_states and to_states arrays
	table	Pointer to FSM table
	funit	Pointer to functional unit containing this FSM
	hit	Specifies if hit or missed transitions should be gathered
	any	Specifies if all arc transitions or just the ones that meet the hit criteria should be gathered
	fr_width	Width of "from" vector to output
	to_width	Width of "to" vector to output

References fsm_table_s::arcs, exclude_find_exclude_reason(), asuppl_u::excluded, fsm_table_s::fr_states, fsm_table_arc_s::from, HEXIDECIMAL, asuppl_u::hit, fsm_table_s::id, fsm_table_s::num_arcs, asuppl_u::part, PROFILE, PROFILE_END, realloc_safe, exclude_reason_s::reason, strdup_safe, fsm_table_arc_s::suppl, fsm_table_arc_s::to, fsm_table_s::to_states, TRUE, and vector_to_string().

Referenced by fsm_display_arc_verbose(), and fsm_get_coverage().

  { PROFILE(ARC_GET_TRANSITIONS);

  unsigned int i;  /* Loop iterator */

  assert( table != NULL );

  /* Initialize state arrays and arc_size */
  *from_states = NULL;
  *to_states   = NULL;
  *ids         = NULL;
  *excludes    = NULL;
  *reasons     = NULL;
  *arc_size    = 0;

  /* Iterate through arc transitions */
  for( i=0; i<table->num_arcs; i++ ) {

    if( (table->arcs[i]->suppl.part.hit == hit) || any ) {
      exclude_reason* er;

      *from_states                = (char**)realloc_safe( *from_states, (sizeof( char* ) * (*arc_size)), (sizeof( char* ) * (*arc_size + 1)) );
      *to_states                  = (char**)realloc_safe( *to_states,   (sizeof( char* ) * (*arc_size)), (sizeof( char* ) * (*arc_size + 1)) );
      *ids                        = (int*)realloc_safe( *ids, (sizeof( int ) * (*arc_size)), (sizeof( int ) * (*arc_size + 1)) );
      *excludes                   = (int*)realloc_safe( *excludes, (sizeof( int ) * (*arc_size)), (sizeof( int ) * (*arc_size + 1)) );
      *reasons                    = (char**)realloc_safe( *reasons, (sizeof( char* ) * (*arc_size)), (sizeof( char* ) * (*arc_size + 1)) );
      (*from_states)[(*arc_size)] = vector_to_string( table->fr_states[table->arcs[i]->from], HEXIDECIMAL, TRUE, fr_width );
      (*to_states)[(*arc_size)]   = vector_to_string( table->to_states[table->arcs[i]->to],   HEXIDECIMAL, TRUE, to_width );
      (*ids)[(*arc_size)]         = table->id + i;
      (*excludes)[(*arc_size)]    = table->arcs[i]->suppl.part.excluded;

      /* If the assertion is currently excluded, check to see if there's a reason associated with it */
      if( (table->arcs[i]->suppl.part.excluded == 1) && ((er = exclude_find_exclude_reason( 'F', (table->id + i), funit )) != NULL) ) {
        (*reasons)[(*arc_size)] = strdup_safe( er->reason );
      } else {
        (*reasons)[(*arc_size)] = NULL;
      }

      (*arc_size)++;
    }

  }

  PROFILE_END;

}

void arc_merge	(	fsm_table *	base,
		const fsm_table *	other
	)

Merges two FSM arcs, placing the results in the base arc.

Merges two FSM arcs into one, placing the result back into the base FSM arc. This function is used to calculate module coverage for the GUI.

References arc_add(), fsm_table_s::arcs, asuppl_u::excluded, fsm_table_s::fr_states, fsm_table_arc_s::from, asuppl_u::hit, fsm_table_s::num_arcs, asuppl_u::part, PROFILE, PROFILE_END, fsm_table_arc_s::suppl, fsm_table_arc_s::to, and fsm_table_s::to_states.

Referenced by fsm_merge().

  { PROFILE(ARC_MERGE);

  unsigned int i;  /* Loop iterator */

  /* Merge state transitions */
  for( i=0; i<other->num_arcs; i++ ) {
    arc_add( base, other->fr_states[other->arcs[i]->from], other->to_states[other->arcs[i]->to], other->arcs[i]->suppl.part.hit, other->arcs[i]->suppl.part.excluded );
  }

  PROFILE_END;

}

static int arc_state_hits

(

const fsm_table *

table

)

[static]

Returns:

Returns number of unique states hit during simulation.

Traverses through specified state transition table, figuring out what states in the table are unique. This is done by traversing through the entire arc array, comparing states that have their ARC_NOT_UNIQUE_x bits set to a value 0. If both states contain the same value, the second state has its ARC_NOT_UNIQUE_x set to indicate that this state is not unique to the table.

Parameters:

table

Pointer to state transition arc array

References fsm_table_s::arcs, asuppl_u::excluded, free_safe, fsm_table_arc_s::from, asuppl_u::hit, malloc_safe, fsm_table_s::num_arcs, fsm_table_s::num_fr_states, asuppl_u::part, PROFILE, PROFILE_END, and fsm_table_arc_s::suppl.

Referenced by arc_get_stats().

  { PROFILE(ARC_STATE_HITS);

  int          hit = 0;     /* Number of states hit */
  unsigned int i;           /* Loop iterators */
  int*         state_hits;  /* Contains state hit information */

  assert( table != NULL );

  /* First, create and intialize a state table to hold hit counts */
  state_hits = (int*)malloc_safe( sizeof( int ) * table->num_fr_states );
  for( i=0; i<table->num_fr_states; i++ ) {
    state_hits[i] = 0;
  }
  
  /* Iterate through arc transition array and count unique hits */
  for( i=0; i<table->num_arcs; i++ ) {
    if( (table->arcs[i]->suppl.part.hit || table->arcs[i]->suppl.part.excluded) ) {
      hit += (state_hits[table->arcs[i]->from]++ == 0) ? 1 : 0; 
    }
  }

  /* Deallocate state_hits */
  free_safe( state_hits, (sizeof( int ) * table->num_fr_states) );

  PROFILE_END;

  return( hit );

}

static int arc_transition_excluded

(

const fsm_table *

table

)

[static]

Returns:

Returns the number of state transitions that are excluded from coverage.

Parameters:

table

Pointer to state transition arc array

References fsm_table_s::arcs, asuppl_u::excluded, fsm_table_s::num_arcs, asuppl_u::part, PROFILE, PROFILE_END, and fsm_table_arc_s::suppl.

Referenced by arc_get_stats().

  { PROFILE(ARC_TRANSITION_EXCLUDED);

  int          excluded = 0;  /* Number of arcs excluded */
  unsigned int i;             /* Loop iterator */

  assert( table != NULL );

  for( i=0; i<table->num_arcs; i++ ) {
    excluded += table->arcs[i]->suppl.part.excluded;
  }

  PROFILE_END;

  return( excluded );

}

static int arc_transition_hits

(

const fsm_table *

table

)

[static]

Returns:

Returns the number of hit state transitions in the specified arc array.

Iterates through arc array, accumulating the number of state transitions that were hit in simulation.

Parameters:

table

Pointer to state transition arc array

References fsm_table_s::arcs, asuppl_u::excluded, asuppl_u::hit, fsm_table_s::num_arcs, asuppl_u::part, PROFILE, PROFILE_END, and fsm_table_arc_s::suppl.

Referenced by arc_get_stats().

  { PROFILE(ARC_TRANSITION_HITS);

  int          hit = 0;  /* Number of arcs hit */
  unsigned int i;        /* Loop iterator */

  assert( table != NULL );

  for( i=0; i<table->num_arcs; i++ ) {
    hit += table->arcs[i]->suppl.part.hit | table->arcs[i]->suppl.part.excluded;
  }

  PROFILE_END;

  return( hit );

}

---

Variable Documentation

int curr_arc_id = 1

Unique identifier for each arc in the design (used for exclusion purposes). This value is assigned to an arc when it is read from the CDD file.

Referenced by arc_db_read(), and db_get_exclusion_id_size().