source: vis_dev/vis-2.3/src/truesim/truesimUtil.c @ 23

/**CFile***********************************************************************

  FileName    [truesimUtil.c]

  PackageName [truesim]

  Synopsis    [Utility functions for the truesim package.]

  Description [Utility functions for the truesim package. Various
  functions include: to compute the topological depth of a node in
  a network, file IO for reading and dumping bit-vector patterns for
  simulation, generating random patterns, and API for accessing
  simulation information for nodes in the network.]

  Author      [Balakrishna Kumthekar]

  Copyright [This file was created at the University of Colorado at Boulder.
  The University of Colorado at Boulder makes no warranty about the suitability
  of this software for any purpose.  It is presented on an AS IS basis.]

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

#include "truesimInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

#define MAX_LENGTH 20000 /* Max. length of a string while reading a file */
#define UNASSIGNED_DEPTH -1 /* Unassigned depth for a node */
#define TOKENS " \t\n" /* For parsing delay-load file */
#define DEFAULT_PROB 0.5

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Structure declarations                                                    */
/*---------------------------------------------------------------------------*/


/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

extern int truesimVerbose;

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static void GetInputs(char *buffer, Ntk_Network_t *network, array_t *inputArray);
static void GetPatternVectors(FILE *fp, int vecLen, array_t *patternArray);
static long NodeComputeDepth(Ntk_Node_t * node);
static long NodeReadDepth(Ntk_Node_t * node);
static void NodeSetDepth(Ntk_Node_t * node, long depth);
static enum st_retval stFloatFree(char *key, char *value, char *arg);
static float computeProbabilityRecur(Ntk_Network_t *network, st_table *nodeToSimTable, st_table *seenTable, bdd_node *bddNode);

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

   Synopsis [Update topological depth of nodes in the network. This
   can be used when the network changes structurally.]
   
   SideEffects [None]
   
   SeeAlso [Truesim_NetworkComputeNodeDepths]

******************************************************************************/
void
Truesim_NetworkUpdateNodeTopologicalDepth(
  Ntk_Network_t *network)
{
  array_t *depthArray,*levelArray;
  Ntk_Node_t *node;
  st_table *nodeToSimTable;
  Truesim_Info_t *simInfo;
  int i,j;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  nodeToSimTable = simInfo->nodeToSimTable;
  depthArray = simInfo->depthArray;

  if (depthArray) {
    arrayForEachItem(array_t *,depthArray,i,levelArray) {
      array_free(levelArray);
    }
    array_free(depthArray);
  }
  
  depthArray = Truesim_NetworkComputeNodeDepths(network);
  simInfo->depthArray = depthArray;
  arrayForEachItem(array_t *,depthArray,i,levelArray) {
    arrayForEachItem(Ntk_Node_t *,levelArray,j,node) {
      TrueSim_t *sim;
      st_lookup(nodeToSimTable,(char *)node,&sim);
      sim->depth = i;
    }
  }

  return;
} /* End of Truesim_NetworkUpdateNodeTopologicalDepth */


/**Function********************************************************************

  Synopsis [Reads the input probabilities of primary inputs from a given file.]

  SideEffects [inputArray and probArray are updated.]
  
  SeeAlso [Truesim_GeneratePrimaryInputProbs]

******************************************************************************/
void
Truesim_ReadInputProbabilities(
  Ntk_Network_t *network,
  char *probFile,
  array_t *inputArray,
  array_t *probArray)
{
  char str[MAX_LENGTH];
  float prob;
  FILE *fp;
  Ntk_Node_t *node;

  if(probFile == 0 || probFile[0] == '\0') {
    (void) fprintf(vis_stderr,
                   "** truesim warning: Probability file was not specified.\n");
    return;    
  }
  /* Read the probabilities. */
  if ((fp = Cmd_FileOpen(probFile,"r",NIL(char *),1)) == NIL(FILE)) {
    lsGen gen;
    (void) fprintf(vis_stderr,
                   "** truesim warning: Could not open %s for reading.\n", probFile);
    (void) fprintf(vis_stderr,
                   "** truesim warning: Using probability as 0.5 for all inputs.\n");
    Ntk_NetworkForEachPrimaryInput(network,gen,node) {
      array_insert_last(float,probArray,DEFAULT_PROB);
      array_insert_last(Ntk_Node_t *,inputArray,node);      
    }
  } else {
    while (fscanf(fp,"%s %f\n",str,&prob) != EOF) {
      node = Ntk_NetworkFindNodeByName(network,str);
      if (!node || !Ntk_NodeTestIsPrimaryInput(node)) {
        (void) fprintf(vis_stderr,
                       "** truesim warning: No PI with name %s. Ignored.\n",str);
      } else {
        if (prob > 1.0 || prob < 0.0) {
          (void) fprintf(vis_stderr,
                         "** truesim warning: %s has invalid prob. %f\n",
                         str,prob);
          (void) fprintf(vis_stderr,
                        "** truesim warning: Assuming 0.5 instead\n");
          prob = DEFAULT_PROB;
        }
        array_insert_last(float,probArray,prob);
        array_insert_last(Ntk_Node_t *,inputArray,node);
      }
    }
    fclose(fp);
  }
} /* End of Truesim_ReadInputProbabilities */


/**Function********************************************************************

  Synopsis [Generate random probabilities for PI. The probabilites are written
  to probFile.]

  SideEffects [The probabilites are written to probFile.]

  SeeAlso [Truesim_ReadInputProbabilities, Truesim_GenerateRandomVectors]

******************************************************************************/
void
Truesim_GeneratePrimaryInputProbs(
  Ntk_Network_t *network,
  char *probFile)
{
  FILE *fp;
  Ntk_Node_t *node;
  lsGen gen;

  if ((fp = Cmd_FileOpen(probFile,"w",NIL(char *),1)) == NIL(FILE)) {
    fprintf(vis_stderr,"** truesim error: Cannot open %s for writing\n",probFile);
    return;
  }
  Ntk_NetworkForEachPrimaryInput(network,gen,node) {
    fprintf(fp,"%s %f\n",
            Ntk_NodeReadName(node),
            ((double)util_random()/(double)(MODULUS1 - 2)));
  }
  fclose(fp);

} /* End of Truesim_GeneratePrimaryInputProbs */


/**Function********************************************************************

  Synopsis [Read simulation vectors from simFile.]

  Description [Read simulation vectors from simFile. The input file looks 
  like below:

  .i c n d o e p f q g r h s i t j u k a l b m
  .s
  0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 ;
  0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0 1 ;
  0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 ;
  0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 ;

  The .i statement specifies the primary inputs of the network. The patterns
  start after .s key word. Each vector is a space separated list of bits and
  ends in a semi-colon. The length of any vector should be equal to the number
  of signals specified in the .i statement. A line starting with # is a
  comment. The format is simple but strict and so few checks are performed.
  
  inputArray is the array of Ntk_Node_t for primary inputs. patternArray
  is the array of bit-vectors to be simulated.]

  SideEffects [inputArray and patternArray are updated.]

  SeeAlso [Truesim_ReadInputProbabilities]

******************************************************************************/
int
Truesim_ReadSimulationVectors(
  Ntk_Network_t *network,
  char *simFile,
  array_t *inputArray,
  array_t *patternArray)
{

  char buffer[MAX_LENGTH];
  FILE *fp;
  boolean readInputs;
  
  fp = Cmd_FileOpen(simFile,"r",NIL(char *),1);
  if (fp == NIL(FILE)) {
    (void) fprintf(vis_stderr,
                   "** truesim error: Cannot open %s for reading sim. vectors.\n",
                   simFile);
    return 0;
  }

  readInputs = TRUE;
  while (fgets(buffer,MAX_LENGTH - 1,fp) != NULL) {
    if (buffer[0] == '#' || buffer[0] == '\n') 
      continue;
    if (buffer[0] == '.' && buffer[1] == 'i') {
      if (!readInputs) {
        (void) fprintf(vis_stderr,
                       "** spfd error: .i statement encountered earlier.\n");
        fclose(fp);
        return 0;
      }
      GetInputs(buffer,network,inputArray);
      readInputs = FALSE;
    } else if (buffer[0] == '.' && buffer[1] == 's') {
        int vecLen = array_n(inputArray);
        if (!vecLen) {
          /* Error reading pattern file. */
          fclose(fp);
          return 0;
        }
        GetPatternVectors(fp,vecLen,patternArray);
        break;
    } else {
      (void) fprintf(vis_stdout,
                     "** spfd warning: Skipping %s\n",buffer);
    }
  } /* End of while */
  fclose(fp);

  return 1;
} /* End of Truesim_ReadSimulationVectors */


/**Function********************************************************************

  Synopsis [Generate random vectors. ]

  Description [Generate random vectors. probArray specifies the signal
  probabilities for PIs of the network. patternArray stores the individual
  vectors. numInputs is the number of primary inputs in the network. 'N'
  patterns are generated.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
array_t *
Truesim_GenerateRandomVectors(
  Ntk_Network_t *network,
  array_t *probArray,
  array_t *patternArray,
  int numInputs,
  int N)
{
  char *strPtr;
  float prob;
  double randomValue;
  int i,j;

  /* We generate N+1 vectors as the first one is an initialization vector */
  for (i = 0; i <= N; i++) {
    strPtr = ALLOC(char,numInputs+1);
    strPtr[numInputs] = '\0';
    for (j = 0; j < numInputs; j++) {
      prob = array_fetch(float,probArray,j);
      randomValue = ((double)util_random()/(double)(MODULUS1 - 2));
      if ((double) prob < randomValue)
        strPtr[j] = '0';
      else 
        strPtr[j] = '1';
    }
    array_insert_last(char *,patternArray,strPtr);
  }
  return patternArray;
} /* End of Truesim_GenerateRandomVectors */


/**Function********************************************************************

  Synopsis [Output vectors to outFile.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
void
Truesim_DumpSimulationVectors(
  Ntk_Network_t *network,                         
  array_t *inputArray,
  array_t *patternArray,
  char *outFile)
{
  FILE *fp;
  int i; unsigned int j;
  char *str;
  Ntk_Node_t *node;
  
  if ((fp = Cmd_FileOpen(outFile,"w",NIL(char *),1)) == NIL(FILE)) {
    fprintf(vis_stderr,
            "** truesim error: Could not open %s for writing\n",outFile);
    return;
  }
  /* Print the intput array */
  fprintf(fp,".i ");
  arrayForEachItem(Ntk_Node_t *,inputArray,i,node) {
    fprintf(fp,"%s ",Ntk_NodeReadName(node));
  }
  fprintf(fp,"\n");

  /* Print the pattern vectors */
  fprintf(fp,".s\n");
  arrayForEachItem(char *,patternArray,i,str) {
    for (j = 0; j < strlen(str); j++)
      fprintf(fp,"%c ",str[j]);
    fprintf(fp,";\n");
  }
  fclose(fp);
} /* End of Truesim_DumpSimulationVectors */


/**Function********************************************************************

  Synopsis    [Computes the depth of each node in the network.]

  Description [Computes the depth of each node in the network. The
  depth of a node is defined inductively: PI and nodes with no
  inputs, have depth 0. Otherwise, the depth of a node is 1 more than
  the maximum depth over the node's fanins.  Intuitively, the depth of
  a node is the length of the longest (backward) path from the node to
  a latch, primary input, pseudo input, or constant.

  The returned array is an array of array_t * of nodes. For ex.

  (n1,n2) (n4,n7,n9) (n3,n8) (n6,n5). 
  
  Nodes, n1 and n2 have depth of 0, n4,n7, and n9 have a depth of 1, and
  so on. ]

  SideEffects [Uses undef field of Ntk_Node_t.]

  SeeAlso     []

******************************************************************************/
array_t *
Truesim_NetworkComputeNodeDepths(
  Ntk_Network_t *network)
{
  lsList rootList;
  lsGen       gen;
  Ntk_Node_t *node;
  long maxDepth;
  int i;
  array_t *tempArray,*depthArray;
  long noDepthCount = 0;

  rootList = Ntk_NetworkReadPrimaryOutputs(network);
  
  /* Initialize the depth of each node to unassigned.  */
  Ntk_NetworkForEachNode(network, gen, node) {
    NodeSetDepth(node, UNASSIGNED_DEPTH);
  }

  /* Start the recursive computation from each root.  */
  lsForEachItem(rootList, gen, node) {
    (void) NodeComputeDepth(node);
  }

  /* Now segregate the nodes according to their depth */
  /* Find the maximum depth */
  maxDepth = UNASSIGNED_DEPTH;
  lsForEachItem(rootList,gen,node) {
    long depth = NodeReadDepth(node);
    if (depth > maxDepth)
      maxDepth = depth;
  }
  /* Put the nodes in an array according to their depths. */
  depthArray = array_alloc(array_t *, maxDepth+1);
  for (i = 0; i < maxDepth+1; i++) {
    tempArray = array_alloc(Ntk_Node_t *, 0);
    array_insert_last(array_t *,depthArray,tempArray);
  }
  Ntk_NetworkForEachNode(network,gen,node) {
    long depth = NodeReadDepth(node);
    array_t *temp = NIL(array_t);

    if (depth != UNASSIGNED_DEPTH) {
      temp = array_fetch(array_t *,depthArray,depth);
      array_insert_last(Ntk_Node_t *,temp,node);
    }else
      noDepthCount++;
  }
  if (noDepthCount > 0)
    fprintf(vis_stderr, "Truesim Warning: %ld nodes have no computed depth.\n",
            noDepthCount);

  return depthArray;
}


/**Function********************************************************************

  Synopsis [Returns topological depth of a node.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
int
Truesim_NetworkReadNodeDepth(
  Ntk_Network_t *network,
  Ntk_Node_t *node)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  nodeToSimTable = simInfo->nodeToSimTable;

  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    return TRUESIM_ERROR_VALUE;
  } else {
    return sim->depth;
  }
  
} /* End of Truesim_NetworkReadNodeDepth */


/**Function********************************************************************

  Synopsis [Returns a node's signal probability.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
float
Truesim_NetworkReadNodeProbability(
  Ntk_Network_t *network,
  Ntk_Node_t *node)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  nodeToSimTable = simInfo->nodeToSimTable;

  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    return (float) TRUESIM_ERROR_VALUE;
  } else {
    return sim->prob;
  }
  
} /* End of Truesim_NetworkReadNodeProbability */


/**Function********************************************************************

  Synopsis [Returns a node's switching probability.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
float
Truesim_NetworkReadNodeSwitchingProb(
  Ntk_Network_t *network,
  Ntk_Node_t *node)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  nodeToSimTable = simInfo->nodeToSimTable;

  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    return (float) TRUESIM_ERROR_VALUE;
  } else {
    return sim->switching;
  }
  
} /* End of Truesim_NetworkReadNodeSwitchingProb */


/**Function********************************************************************

  Synopsis [Returns a node's load.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
float
Truesim_NetworkReadNodeLoad(
  Ntk_Network_t *network,
  Ntk_Node_t *node)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  nodeToSimTable = simInfo->nodeToSimTable;

  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    return (float) TRUESIM_ERROR_VALUE;
  } else {
    return sim->load;
  }
  
} /* End of Truesim_NetworkReadNodeLoad */


/**Function********************************************************************

  Synopsis [Returns a node's delay.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
float
Truesim_NetworkReadNodeDelay(
  Ntk_Network_t *network,
  Ntk_Node_t *node)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  nodeToSimTable = simInfo->nodeToSimTable;

  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    return (float) TRUESIM_ERROR_VALUE;
  } else {
    return sim->delay;
  }
  
} /* End of Truesim_NetworkReadNodeDelay */


/**Function********************************************************************

  Synopsis [Set a node's load.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
boolean
Truesim_NetworkSetNodeLoad(
  Ntk_Network_t *network,
  Ntk_Node_t *node,
  float load)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  if (!simInfo)
    goto error;
  
  nodeToSimTable = simInfo->nodeToSimTable;
  if (!nodeToSimTable)
    goto error;
  
  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    goto error;
  } else {
    sim->load = load;
  }
  return TRUE;

 error:
  (void) fprintf(vis_stderr,
                 "** truesim error: Network not initialized for simulation.\n");
  (void) fprintf(vis_stderr,
                 "** truesim error: Call Truesim_InitializeSimulation.\n");
  return FALSE;
  
} /* End of Truesim_NetworkSetNodeLoad */


/**Function********************************************************************

  Synopsis [Set a node's delay.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
boolean
Truesim_NetworkSetNodeDelay(
  Ntk_Network_t *network,
  Ntk_Node_t *node,
  float delay)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  if (!simInfo)
    goto error;
  
  nodeToSimTable = simInfo->nodeToSimTable;
  if (!nodeToSimTable)
    goto error;
  
  if (!st_lookup(nodeToSimTable,node,&sim)) {
    goto error;
  } else {
    sim->delay = delay;
  }
  return TRUE;

 error:
  (void) fprintf(vis_stderr,
                 "** truesim error: Network not initialized for simulation.\n");
  (void) fprintf(vis_stderr,
                 "** truesim error: Call Truesim_InitializeSimulation.\n");
  return FALSE;
  
} /* End of Truesim_NetworkSetNodeDelay */


/**Function********************************************************************

  Synopsis [Set a node's static probability.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
boolean
Truesim_NetworkSetNodeStaticProb(
  Ntk_Network_t *network,
  Ntk_Node_t *node,
  float prob)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  if (!simInfo)
    goto error;
  
  nodeToSimTable = simInfo->nodeToSimTable;
  if (!nodeToSimTable)
    goto error;
  
  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    goto error;
  } else {
    sim->prob = prob;
  }
  return TRUE;

 error:
  (void) fprintf(vis_stderr,
                 "** truesim error: Network not initialized for simulation.\n");
  (void) fprintf(vis_stderr,
                 "** truesim error: Call Truesim_InitializeSimulation.\n");
  return FALSE;
  
} /* End of Truesim_NetworkSetNodeStaticProb */


/**Function********************************************************************

  Synopsis [Set a node's switching (transition) probability.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
boolean
Truesim_NetworkSetNodeSwitchingProb(
  Ntk_Network_t *network,
  Ntk_Node_t *node,
  float switching)
{
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  if (!simInfo)
    goto error;
  
  nodeToSimTable = simInfo->nodeToSimTable;
  if (!nodeToSimTable)
    goto error;
  
  if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
    goto error;
  } else {
    sim->switching = switching;
  }
  return TRUE;

 error:
  (void) fprintf(vis_stderr,
                 "** truesim error: Network not initialized for simulation.\n");
  (void) fprintf(vis_stderr,
                 "** truesim error: Call Truesim_InitializeSimulation.\n");
  return FALSE;
  
} /* End of Truesim_NetworkSetNodeSwitchingProb */


/**Function********************************************************************

  Synopsis [Given a BDD of a network node, compute it's probability. This
  function assumes that the variables in the support of the BDD belong to the
  network and those corresponding nodes have their signal probabilites set.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
float
Truesim_BddNodeComputeProbability(
  Ntk_Network_t *network,
  bdd_node *func)
{
  bdd_manager *ddManager = Ntk_NetworkReadMddManager(network);
  Truesim_Info_t *simInfo;
  st_table *nodeToSimTable;
  float prob,*dummy;
  st_table *table;
  bdd_node *one,*zero;
  
  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  nodeToSimTable = simInfo->nodeToSimTable;

  one = bdd_read_one(ddManager);
  zero = bdd_read_logic_zero(ddManager);
  
  if (func == zero)
    return 0.0;
  if (func == one)
    return 1.0;

  table = st_init_table(st_ptrcmp,st_ptrhash);
  dummy = ALLOC(float,1);
  *dummy = 1.0;
  st_insert(table,(char *)one,(char *)dummy);

  prob = computeProbabilityRecur(network,nodeToSimTable,table,func);
  st_foreach(table,stFloatFree,NIL(char));
  st_free_table(table);

  return prob;
  
} /* End of Truesim_BddNodeComputeProbability */

/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/
/**Function********************************************************************

  Synopsis [Evaluate a node given the state of its fanin.]

  Description [Evaluate a node given the state of its fanin. For
  example, if the function at 'node' is y = a + b and node 'a' has
  a value '0' and node 'b' has value '1', (due to propagation of
  bit-vectors during simulation), we evaluate the node 'y' to have a
  value '1'. ]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
char 
TruesimEvaluateNode(
  Ntk_Node_t *node,
  graph_t *partition,
  bdd_manager *ddManager,
  st_table *nodeToSimTable)
{
  bdd_t *faninBdd,*nodeBdd,*tempBdd;
  vertex_t *vertex;
  Mvf_Function_t *nodeMvf;
  char next;
  
  /* Compute the cube for the fanin of node. For ex. if y = a + b, and a =
  '1' and b = '0', the cube faninBdd is ab' */
  faninBdd = TruesimComputeFaninMinterm(ddManager,node,nodeToSimTable);
  vertex = Part_PartitionFindVertexByMddId(partition,
                                           Ntk_NodeReadMddId(node));
  nodeMvf = Part_VertexReadFunction(vertex);
  nodeBdd = array_fetch(bdd_t *,nodeMvf,1);

  /* Evaluate the node */
  tempBdd = bdd_cofactor(nodeBdd,faninBdd);
  next = bdd_is_tautology(tempBdd,TRUE) ? '1' : '0';

  bdd_free(tempBdd);
  bdd_free(faninBdd);
  
  return next;
  
} /* End of TruesimEvaluateNode */


/**Function********************************************************************

  Synopsis [Read the node to simulation structure table.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
st_table *
TruesimNetworkReadSimTable(
  Ntk_Network_t *network)
{
  Truesim_Info_t *simInfo;

  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);

  return simInfo->nodeToSimTable;
  
} /* End of TruesimNetworkReadSimTable */


/**Function********************************************************************

  Synopsis [Read the depthArray of the network.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
array_t *
TruesimNetworkReadDepthArray(Ntk_Network_t *network)
{
  Truesim_Info_t *simInfo;

  simInfo = (Truesim_Info_t *)
    Ntk_NetworkReadApplInfo(network,TRUESIM_NETWORK_APPL_KEY);
  return simInfo->depthArray;
  
}


/**Function********************************************************************

  Synopsis [Initialize the Truesim_t structure for each node in the network.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
void
TruesimInitializeActivityFields(
  Ntk_Network_t *network,                        
  st_table *nodeToSimTable)
{
  Ntk_Node_t *node;
  lsGen gen;

  Ntk_NetworkForEachNode(network,gen,node) {
    TrueSim_t *sim;
    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
      (void) fprintf(vis_stderr,"** truesim fatal: In TruesimInitializeActitivyFields\n");
      assert(0);
    }
    sim->value = '0';
    sim->prob = 0.0;
    sim->switching = 0.0;
    sim->event = NIL(Event);
  }
} /* End of TruesimInitializeActivityFields */


/**Function********************************************************************

  Synopsis [Returns a BDD minterm for a node based on the state of the
  node's fanin.]

  Description [[Returns a BDD minterm for a node based on the state of
  the node's fanin. For ex. if y = a + b, and a = '1' and b = '0',
  the minterm is the BDD of ab'.  ] 
  
  SideEffects [None]

  SeeAlso []

******************************************************************************/
bdd_t *
TruesimComputeFaninMinterm(
  bdd_manager *ddManager,
  Ntk_Node_t *node,
  st_table *nodeToSimTable)
{
  int numFanin = Ntk_NodeReadNumFanins(node);
  int *phase;
  bdd_node **vars,*temp;
  Ntk_Node_t *fanin;
  TrueSim_t *sim;
  int i;

  vars = ALLOC(bdd_node *,numFanin);
  phase = ALLOC(int,numFanin);
  Ntk_NodeForEachFanin(node,i,fanin) {
    int id;

    if (!st_lookup(nodeToSimTable,(char *)fanin,&sim)) {
      (void) fprintf(vis_stderr,"** truesim fatal: In TruesimComputeFaninMinterm\n");      
      assert(0);
    }
    id = Ntk_NodeReadMddId(fanin);
    vars[i] = bdd_bdd_ith_var(ddManager,id);
    phase[i] = (sim->value == '1') ? 1:0;
  }
  temp = bdd_bdd_compute_cube(ddManager,vars,phase,numFanin);
  bdd_ref(temp);

  FREE(phase);
  FREE(vars);

  return (bdd_construct_bdd_t(ddManager,temp));

} /* End of TruesimComputeFaninMinterm */


/**Function********************************************************************

  Synopsis [Print PI/PO names for better readability of simulation output.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
void
TruesimPrintNameHeader(Ntk_Network_t *network)
{
  lsGen gen;
  Ntk_Node_t *node;

  /* Print PIs first */
  Ntk_NetworkForEachPrimaryInput(network,gen,node) {
    (void) fprintf(vis_stdout,"%s ",Ntk_NodeReadName(node));
  }

  if (truesimVerbose > 3) {
    (void) fprintf(vis_stdout," -- ");
    /* Print internal nodes next */
    Ntk_NetworkForEachNode(network,gen,node) {
      if (!Ntk_NodeTestIsPrimaryInput(node) &&
          !Ntk_NodeTestIsPrimaryOutput(node)) {
        (void) fprintf(vis_stdout,"%s ",Ntk_NodeReadName(node));
      }
    }
  }
  
  /* Print POs last */
  (void) fprintf(vis_stdout," -- ");
  Ntk_NetworkForEachPrimaryOutput(network,gen,node) {
    (void) fprintf(vis_stdout,"%s ",Ntk_NodeReadName(node));
  }
  (void) fprintf(vis_stdout,"\n");

  return ;
  
} /* End of TruesimPrintNameHeader  */


/**Function********************************************************************

  Synopsis [Print the logic state of network nodes.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
void
TruesimPrintNetworkNodeLogicState(Ntk_Network_t *network)
{
  st_table *nodeToSimTable;
  TrueSim_t *sim;
  lsGen gen;
  Ntk_Node_t *node;

  nodeToSimTable = TruesimNetworkReadSimTable(network);

  /* Print PIs first */
  Ntk_NetworkForEachPrimaryInput(network,gen,node) {
    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
      (void) fprintf(vis_stderr,
                     "** truesim fatal: In TruesimPrintNetworkNodeLogicState\n");
      assert(0);
    }
    (void) fprintf(vis_stdout,"%c ",sim->value);
  }

  if (truesimVerbose > 3) {
    (void) fprintf(vis_stdout," -- ");
    /* Print internal nodes next */
    Ntk_NetworkForEachNode(network,gen,node) {
      if (!Ntk_NodeTestIsPrimaryInput(node) &&
          !Ntk_NodeTestIsPrimaryOutput(node)) {
        if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
          (void) fprintf(vis_stderr,
                         "** truesim fatal: In TruesimPrintNetworkNodeLogicState\n");
          assert(0);
        }
        (void) fprintf(vis_stdout,"%c ",sim->value);
      }
    }
  }

  /* Print POs last */
  (void) fprintf(vis_stdout," -- ");
  Ntk_NetworkForEachPrimaryOutput(network,gen,node) {
    if (!st_lookup(nodeToSimTable,(char *)node,&sim)) {
      (void) fprintf(vis_stderr,
                     "** truesim fatal: In TruesimPrintNetworkNodeLogicState\n");
      assert(0);
    }
    (void) fprintf(vis_stdout,"%c ",sim->value);
  }
  (void) fprintf(vis_stdout,"\n");

  return ;
  
} /* End of TruesimPrintNodeLogicState  */


/**Function********************************************************************

  Synopsis [Read delay and load values from a given file. The format is
  
  nodeName delay load
  
  The format is strict and few checks are performed. A line starting
  with # is considered a comment. Delay and load values are specified
  one per line.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
void
TruesimReadDelayFile(
  Ntk_Network_t *network,
  char *delayFile,
  st_table *nodeToSimTable)
{
  char buffer[MAX_LENGTH], *ptr;
  FILE *fp;
  lsGen gen;
  TrueSim_t *sim;
  Ntk_Node_t *node;

  fp = Cmd_FileOpen(delayFile,"r",NIL(char *),1);
  while (fgets(buffer,MAX_LENGTH - 1,fp) != NULL) {
    if (buffer[0] == '#' || buffer[0] == '\n') 
      continue;
    if (truesimVerbose > 10) {
      (void) fprintf(vis_stdout,"%s",buffer);
    }
    ptr = strtok(buffer,TOKENS);
    node = Ntk_NetworkFindNodeByName(network,ptr);
    if (!node) {
      (void) fprintf(vis_stderr, "** truesim warning: %s not in the network\n",
                     ptr);
      (void) fprintf(vis_stderr, "** truesim warning: Values ignored ...\n");
      continue;
    }
    sim = ALLOC(TrueSim_t,1);
    ptr = strtok(NIL(char),TOKENS);
    if (ptr) {
      sim->delay = atof(ptr);
    }
    ptr = strtok(NIL(char),TOKENS);
    if (ptr) {
      sim->load = atof(ptr);
    }
    st_insert(nodeToSimTable, (char *)node, (char *)sim);
    if (truesimVerbose > 10) {
      (void) fprintf(vis_stdout,"%s %f %f\n",Ntk_NodeReadName(node),
                     sim->delay,sim->load);
    }
  }

  /* Now check that all the nodes have load and delay values. If a
     node delay/load value is not initialized, set it to default. */

  Ntk_NetworkForEachNode(network,gen,node) {
    if (!st_lookup(nodeToSimTable,(char *)node, &sim)) {
      sim = ALLOC(TrueSim_t,1);
      sim->delay = 1.0;
      sim->load = 0.0;
      st_insert(nodeToSimTable, (char *)node, (char *)sim);
    }
    if (sim->delay == 0.0)
      sim->delay = 1.0;
    /* if (Ntk_NodeTestIsPrimaryInput(node))
       sim->delay = 0.0; */
  }
  fclose(fp);
  return;
} /* End of TruesimReadDelayFile */


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************

  Synopsis [Read PI names from the string.]

  Description [Read PI names from the string. This function is called
  in Truesim_ReadSimulationVectors. ] 

  SideEffects [Primary input nodes are returned in inputArray.]

  SeeAlso [GetPatternVectors]

******************************************************************************/
static void
GetInputs(
  char *buffer,
  Ntk_Network_t *network,
  array_t *inputArray)
{
  char internalBuf[MAX_LENGTH];
  long i,index;
  Ntk_Node_t *node;

  index = 2;
  while (buffer[index] != '\0') {
    if (buffer[index] == ' ' ||
        buffer[index] == '\t' ||
        buffer[index] == '\n') {
      index++;
      continue;
    }
    i = 0;
    while (buffer[index] != ' ' && buffer[index] != '\t'
           && buffer[index] != '\n') {
      internalBuf[i] = buffer[index];
      i++;
      index++;
    } /* End of while */
    if (i > 0); {
      internalBuf[i] = '\0';
      node = Ntk_NetworkFindNodeByName(network,internalBuf);
      if (node)
        array_insert_last(Ntk_Node_t *,inputArray,node);
      else {
        (void) fprintf(vis_stderr,
                       "** truesim error: %s not found in the circuit.\n", 
                       internalBuf);
      }
      index++;
    }
  } /* End of while */
} /* End of GetInputs */


/**Function********************************************************************

  Synopsis [Read the pattern vectors from the simulation file.]

  Description [Read the pattern vectors from the simulation file. This
  function is called in Truesim_ReadSimulationVectors. The length of the
  vectors specified in the file should be of vecLen.]

  SideEffects [The bit-vectors are returned in patternArray.]

  SeeAlso [GetInputs]

******************************************************************************/
static void
GetPatternVectors(
  FILE *fp,
  int vecLen,
  array_t *patternArray)
{
  char buffer[MAX_LENGTH];
  char internalBuf[MAX_LENGTH];
  char *str;
  int index,i,j;
  boolean skip;

  while (fgets(buffer,MAX_LENGTH - 1,fp) != NULL) {
    index = i = 0;
    if (buffer[0] == '\n' ||
        buffer[0] == '#')
      continue;
    while (buffer[index] != '\0') {
      if (buffer[index] == ' ' ||
          buffer[index] == ';' ||
          buffer[index] == '\n') {
        index++;
        continue;
      }
      internalBuf[i] = buffer[index];
      i++;
      index++;
    }
    if (i > 0) {
      internalBuf[i] = '\0';
      /* Ascertain that internalBuf has only '0's and '1's. */
      skip = FALSE;      j = 0;
      while (internalBuf[j] != '\0') {
        if ((internalBuf[j] != '0') && (internalBuf[j] != '1')) {
          skip = TRUE;
          break;
        }
        j++;
      }
      if (skip) {
        (void) fprintf(vis_stdout,
                       "** spfd warning: Invalid vector < %s > is ignored.\n",
                       internalBuf);
      } else if ((unsigned) vecLen != strlen(internalBuf)) {
        (void) fprintf(vis_stdout,
                       "** spfd warning: Length < %ld > of < %s > incorrect.\n",
                       (long) strlen(internalBuf), internalBuf);
        (void) fprintf(vis_stdout,
                       "** spfd warning: Ignoring < %s > .\n",internalBuf);
      } else {
        str = util_strsav(internalBuf);
        array_insert_last(char *,patternArray,str);
      }
    }
  }
} /* End of GetPatternVectors */


/**Function********************************************************************

  Synopsis    [Computes the depth of a node.]

  SideEffects [Changes the undef field of the node.]

  SeeAlso     [NetworkComputeNodeDepths]

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

/**Function********************************************************************

  Synopsis    [Computes the depth of a node.]

  SideEffects [Changes the undef field of the node.]

  SeeAlso     [NetworkComputeNodeDepths]

******************************************************************************/
static long
NodeComputeDepth(
  Ntk_Node_t * node)
{
  long depth = NodeReadDepth(node);

  /* If the node's depth has already been computed (i.e. it's not
   unassigned), then just return it below.  If it's unassigned, then
   recursively compute it.  */
  if (depth == UNASSIGNED_DEPTH) {
    if (Ntk_NodeTestIsCombInput(node) || Ntk_NodeTestIsConstant(node)) {
      /* PI and nodes with no fanins, get depth 0. This is the
        terminal case of recursion.  */
      depth = 0;
    } else {
      int i;
      Ntk_Node_t *fanin;
      /* Compute the depth of each fanin node in the support of node,
        and maintain the maximum.  We start depth at 0 for max
        calculation.  */
      depth = 0;
      Ntk_NodeForEachFanin(node, i, fanin) {  
        long faninDepth = NodeComputeDepth(fanin);

        depth = (depth > faninDepth) ? depth:faninDepth;
      }
      
      /* The depth of node is one more than the max depths of its
       fanins.  */
      depth++;
    }

    /* Store the depth.  */
    NodeSetDepth(node, depth);
  }
  
  return depth;
}


/**Function********************************************************************

  Synopsis    [Reads the depth of a node.]

  SideEffects [None]

  SeeAlso     [NodeSetDepth] 

******************************************************************************/
static long
NodeReadDepth(
  Ntk_Node_t * node)
{
  return ((long) Ntk_NodeReadUndef(node));
}


/**Function********************************************************************

  Synopsis    [Sets the depth of a node.]

  SideEffects [Changes the undef field of the node.]

  SeeAlso     [NodeReadDepth]

******************************************************************************/
static void
NodeSetDepth(
  Ntk_Node_t * node,
  long depth)
{
  Ntk_NodeSetUndef(node, (void *) depth);
}

/**Function********************************************************************

  Synopsis [Free float pointed in an st_table.]

  SideEffects [None]

  SeeAlso []

******************************************************************************/
static enum st_retval
stFloatFree(
  char *key,
  char *value,
  char *arg)
{
  float *dummy;
  dummy = (float *)value;

  if (dummy)
    FREE(dummy);

  return (ST_CONTINUE);

} /* End of stFloatFree */


/**Function********************************************************************

  Synopsis [Recursive function of Truesim_BddNodeComputeProbability]

  Description [Compute the probability of a function represented by
  ADD. For example, Probability of a Boolean function f being 1 is given
  as follows:
  
  Prob(f(x) == 1) = Prob(x) * Prob(f_x) + (1.0 - Prob(x)) * Prob(f_x') 
  
  The probability values for the support of f is stored in
  nodeToSimTable. ]

  SideEffects [None]

  SeeAlso [Truesim_BddNodeComputeProbability]

******************************************************************************/
static float
computeProbabilityRecur(
  Ntk_Network_t *network,
  st_table *nodeToSimTable,
  st_table *seenTable,
  bdd_node *bddNode)
{
  float value,*probability,*dummy;
  float valueL,valueR;
  Ntk_Node_t *networkNode;
  TrueSim_t *sim;
  bdd_node *N,*Nv,*Nnv;

  N = bdd_regular(bddNode);

  if (st_lookup(seenTable,(char *)N,&dummy)) {
    return ((N != bddNode) ? 1.0 - *dummy : *dummy);
  }
  
  Nv = bdd_bdd_T(N);
  Nnv = bdd_bdd_E(N);

  /* Recur on the children */
  valueR = computeProbabilityRecur(network,nodeToSimTable,seenTable,Nv);
  valueL = computeProbabilityRecur(network,nodeToSimTable,seenTable,Nnv);

  networkNode = Ntk_NetworkFindNodeByMddId(network,bdd_node_read_index(N));
  if (st_lookup(nodeToSimTable,(char *)networkNode,&sim)) {
    value = sim->prob;
    probability = ALLOC(float,1);
    *probability = value * valueR + (1.0 - value) * valueL;
  } else {
    fprintf(vis_stderr,
            "** truesim error: Could not find prob. for node %s\n",
            Ntk_NodeReadName(networkNode));
    return (float) TRUESIM_ERROR_VALUE;
  }

  st_insert(seenTable,(char *)N,(char *)probability);

  return ((N != bddNode) ? 1.0 - *probability : *probability);

} /* End of computeProbabilityRecur */