source: vis_dev/glu-2.1/src/calBdd/calUtil.c @ 8

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

  FileName    [calUtil.c]

  PackageName [cal]

  Synopsis    [Utility functions for the Cal package.]

  Description [Utility functions used in the Cal package.]

  SeeAlso     [optional]

  Author      [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu)
               Rajeev K. Ranjan   (rajeev@eecs.berkeley.edu)
              ]
  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
  All rights reserved.

  Permission is hereby granted, without written agreement and without license
  or royalty fees, to use, copy, modify, and distribute this software and its
  documentation for any purpose, provided that the above copyright notice and
  the following two paragraphs appear in all copies of this software.

  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

  Revision    [$Id: calUtil.c,v 1.4 2002/09/10 00:10:37 fabio Exp $]

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

#include "calInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/
/* Random generator constants. */
#define CAL_MODULUS1 2147483563
#define CAL_LEQA1 40014
#define CAL_LEQQ1 53668
#define CAL_LEQR1 12211
#define CAL_MODULUS2 2147483399
#define CAL_LEQA2 40692
#define CAL_LEQQ2 52774
#define CAL_LEQR2 3791
#define CAL_STAB_SIZE 64
#define CAL_STAB_DIV (1 + (CAL_MODULUS1 - 1) / CAL_STAB_SIZE)

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


/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/
static long utilRand = 0;
static long utilRand2;
static long shuffleSelect;
static long shuffleTable[CAL_STAB_SIZE];

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/


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

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


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

/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/
void
Cal_ImageDump(Cal_BddManager_t *bddManager, FILE *fp)
{

  CalPageManager_t *pageManager;
  int i, j;
  char *segment, c;
  int count = NUM_PAGES_PER_SEGMENT * PAGE_SIZE;

  pageManager = bddManager->pageManager1;
  for(i = 0; i < pageManager->numSegments; i++){
    segment = (char *) pageManager->pageSegmentArray[i];
    for(j = 1; j <= count; j++){
      c = segment[j];
      fprintf(fp, "%c", j%64?c:'\n');
    }
  }
  pageManager = bddManager->pageManager2;
  for(i = 0; i < pageManager->numSegments; i++){
    segment = (char *) pageManager->pageSegmentArray[i];
    for(j = 1; j <= count; j++){
      c = segment[j];
      fprintf(fp, "%c", j%64?c:'\n');
    }
  }
}


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

  Synopsis    [Prints the function implemented by the argument BDD]

  Description [Prints the function implemented by the argument BDD]

  SideEffects [None]

******************************************************************************/
void
Cal_BddFunctionPrint(Cal_BddManager bddManager, Cal_Bdd  userBdd,
                     char *name)
{
  Cal_Bdd_t calBdd;
  calBdd = CalBddGetInternalBdd(bddManager, userBdd);
  CalBddFunctionPrint(bddManager, calBdd, name);
}

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

  Synopsis    [required]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
void
CalUniqueTablePrint(Cal_BddManager_t *bddManager)
{
  int i;
  for(i = 0; i <= bddManager->numVars; i++){
    CalHashTablePrint(bddManager->uniqueTable[i]);
  }
}

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

  Synopsis    [Prints the function implemented by the argument BDD]

  Description [Prints the function implemented by the argument BDD]

  SideEffects [None]

******************************************************************************/
void
CalBddFunctionPrint(Cal_BddManager_t * bddManager,
                    Cal_Bdd_t  calBdd,
                    char * name)
{
  Cal_Bdd_t T,E;
  Cal_BddId_t id;
  char c;
  static int level;

  if(level == 0)printf("%s = ",name);
  level++;
  printf("( ");
  if(CalBddIsBddZero(bddManager, calBdd)){
    printf("0 ");
  }
  else if(CalBddIsBddOne(bddManager, calBdd)){
    printf("1 ");
  }
  else{
    id = CalBddGetBddId(calBdd);
    c = (char)((int)'a' + id - 1);
    printf("%c ", c);
    CalBddGetCofactors(calBdd, id, T, E);
    CalBddFunctionPrint(bddManager, T, " ");
    printf("+ %c' ", c);
    CalBddFunctionPrint(bddManager, E, " ");
  }
  level--;
  printf(") ");
  if(level == 0)printf("\n");
}

/**Function********************************************************************
  
  Synopsis    [required]
  
  Description [optional]
  
  SideEffects [required]
  
  SeeAlso     [optional]
  
******************************************************************************/
#if HAVE_STDARG_H
int
CalBddPreProcessing(Cal_BddManager_t *bddManager, int count, ...)
{
  int allValid;
  va_list ap;
  Cal_Bdd fUserBdd;
  Cal_Bdd_t f;
  
  va_start(ap, count);
#else
#  if HAVE_VARARGS_H
int
CalBddPreProcessing(va_alist)
va_dcl
{
  int allValid;
  va_list ap;
  Cal_Bdd *fUserBdd;
  int count;
  Cal_BddManager_t *bddManager;
  Cal_Bdd_t f;
  
  va_start(ap);
  bddManager = va_arg(ap, Cal_BddManager_t *);
  count = va_arg(ap, int);
#  endif
#endif  

  allValid=1;
  while (count){
    fUserBdd = va_arg(ap, Cal_Bdd);
        if (fUserBdd == 0){
          allValid=0;
    }
        else {
      f = CalBddGetInternalBdd(bddManager, fUserBdd);
      if (CalBddIsRefCountZero(f)){
        CalBddFatalMessage("Bdd With Zero Reference Count Used.");
      }
    }
    --count;
  }
  if (allValid) {
    CalBddPostProcessing(bddManager);
  }
  va_end(ap);
  return (allValid);
}


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

  Synopsis    [required]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
int
CalBddPostProcessing(Cal_BddManager_t *bddManager)
{
  if (bddManager->gcCheck > 0) return CAL_BDD_OK;
  bddManager->gcCheck = CAL_GC_CHECK;
  if(bddManager->numNodes > bddManager->uniqueTableGCLimit){
    long origNodes = bddManager->numNodes;
    Cal_BddManagerGC(bddManager);
    if ((bddManager->numNodes > bddManager->reorderingThreshold) &&
        (3*bddManager->numNodes > 2* bddManager->uniqueTableGCLimit) &&
        (bddManager->dynamicReorderingEnableFlag) &&
        (bddManager->reorderTechnique != CAL_REORDER_NONE)){
      CalCacheTableTwoFlush(bddManager->cacheTable);
      if (bddManager->reorderMethod == CAL_REORDER_METHOD_BF){
        CalBddReorderAuxBF(bddManager);
      }
      else{
        CalBddReorderAuxDF(bddManager);
      }
    }
    else {
      /* Check if we should repack */
      Cal_Assert(CalCheckAllValidity(bddManager));
      if (bddManager->numNodes <
          bddManager->repackAfterGCThreshold*origNodes){
        CalRepackNodesAfterGC(bddManager);
      }
      Cal_Assert(CalCheckAllValidity(bddManager));
    }
    Cal_BddManagerSetGCLimit(bddManager);
    if (bddManager->nodeLimit && (bddManager->numNodes >
                                  bddManager->nodeLimit)){ 
      CalBddWarningMessage("Overflow: Node Limit Exceeded");
      bddManager->overflow = 1;
      return CAL_BDD_OVERFLOWED;
    }
    /*
     * Check to see if the cache table needs to be rehashed.
     */
    CalCacheTableRehash(bddManager);
  }
  return CAL_BDD_OK;
}

/**Function********************************************************************
  
  Synopsis    [required]
  
  Description [optional]
  
  SideEffects [required]
  
  SeeAlso     [optional]
  
******************************************************************************/
int
CalBddArrayPreProcessing(Cal_BddManager_t *bddManager, Cal_Bdd *userBddArray) 
{
  int i = 0;
  Cal_Bdd userBdd;
  while ((userBdd = userBddArray[i++])){
    if (CalBddPreProcessing(bddManager, 1, userBdd) == 0){
      return 0;
    }
  }
  return 1;
}
    
                       
/**Function********************************************************************

  Name        [CalBddFatalMessage]

  Synopsis    [Prints fatal message and exits.]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
Cal_Bdd_t
CalBddGetInternalBdd(Cal_BddManager bddManager, Cal_Bdd userBdd)
{
  Cal_Bdd_t resultBdd;
  if (CalBddNodeIsOutPos(userBdd)){
    CalBddNodeGetThenBdd(userBdd, resultBdd);
  }
  else {
    Cal_Bdd userBddNot = CalBddNodeNot(userBdd);
    Cal_Bdd_t internalBdd;
        CalBddNodeGetThenBdd(userBddNot,internalBdd);
    CalBddNot(internalBdd, resultBdd);
  }
  return resultBdd;
}

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

  Name        [CalBddFatalMessage]

  Synopsis    [Prints fatal message and exits.]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
Cal_Bdd
CalBddGetExternalBdd(Cal_BddManager_t *bddManager, Cal_Bdd_t internalBdd)
{
  CalHashTable_t *hashTableForUserBdd = bddManager->uniqueTable[0];
  Cal_Bdd_t resultBdd;
  int found;
  
  if(CalBddIsOutPos(internalBdd)){
    found = CalHashTableFindOrAdd(hashTableForUserBdd, internalBdd,
                          bddManager->bddOne, &resultBdd);
  }
  else {
    Cal_Bdd_t internalBddNot;
    CalBddNot(internalBdd, internalBddNot);
    found = CalHashTableFindOrAdd(hashTableForUserBdd, internalBddNot,
                          bddManager->bddOne, &resultBdd);
    CalBddNot(resultBdd, resultBdd);
  }
  if (found == 0){
    CalBddIcrRefCount(internalBdd);
  }
  CalBddIcrRefCount(resultBdd);
  return CalBddGetBddNode(resultBdd);
}


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

  Name        [CalBddFatalMessage]

  Synopsis    [Prints fatal message and exits.]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
void
CalBddFatalMessage(char *string)
{
  (void) fprintf(stderr,"Fatal: %s\n", string);
  exit(-1);
}
/**Function********************************************************************

  Name        [CalBddWarningMessage]

  Synopsis    [Prints warning message.]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
void
CalBddWarningMessage(char *string)
{
  (void) fprintf(stderr,"Warning: %s\n", string);
}

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

  Synopsis    [required]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
void
CalBddNodePrint(CalBddNode_t *bddNode)
{
  int refCount;
  CalBddNodeGetRefCount(bddNode, refCount);
  printf("Node (%lx) thenBdd(%2d %lx)  elseBdd(%2d %lx) ref_count (%d) next (%lx)\n",
         (CalAddress_t)bddNode,
         CalBddNodeGetThenBddId(bddNode),
         (CalAddress_t) CalBddNodeGetThenBddNode(bddNode), 
         CalBddNodeGetElseBddId(bddNode),
         (CalAddress_t) CalBddNodeGetElseBddNode(bddNode),
         refCount, (CalAddress_t)bddNode->nextBddNode);
}

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

  Synopsis    [required]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

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

void
CalBddPrint(Cal_Bdd_t calBdd)
{
  printf("Id(%2d) node(%lx) ",
      CalBddGetBddId(calBdd), (CalAddress_t) CalBddGetBddNode(calBdd));
  printf("thenBdd(%2d %lx)  elseBdd(%2d %lx)\n",
         CalBddGetThenBddId(calBdd),
         (CalAddress_t) CalBddGetThenBddNode(calBdd), 
         CalBddGetElseBddId(calBdd),
         (CalAddress_t) CalBddGetElseBddNode(calBdd));
}

#ifdef TEST_CALBDDNODE
main(int argc, char **argv)
{
  CalBddNode_t *bddNode, *thenBddNode, *elseBddNode;

  bddNode = Cal_MemAlloc(CalBddNode_t, 1);
  thenBddNode = Cal_MemAlloc(CalBddNode_t, 1);
  elseBddNode = Cal_MemAlloc(CalBddNode_t, 1);

  CalBddNodePutThenBddId(bddNode, 1);
  CalBddNodePutThenBddNode(bddNode, thenBddNode);
  CalBddNodePutElseBddId(bddNode, 2);
  CalBddNodePutElseBddNode(bddNode, elseBddNode);

  printf("then( 1 %x) else( 2 %x)\n", thenBddNode, elseBddNode);
  CalBddNodePrint(bddNode);
}
#endif


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

  Synopsis    [Prints a hash table.]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
void
CalHashTablePrint(CalHashTable_t *hashTable)
{
  int i;
  CalBddNode_t *ptr;
  Cal_Bdd_t calBdd, T, E;
  int refCount, firstFlag;

  printf("HashTable bddId(%d) entries(%ld) bins(%ld) capacity(%ld)\n",
         hashTable->bddId, hashTable->numEntries, hashTable->numBins,
         hashTable->maxCapacity);
  for(i = 0; i < hashTable->numBins; i++){
    ptr = hashTable->bins[i];
    firstFlag = 1;
    while(ptr != Cal_Nil(CalBddNode_t)){
      CalBddPutBddNode(calBdd, ptr);
      CalBddNodeGetThenBdd(ptr, T);
      CalBddNodeGetElseBdd(ptr, E);
      if (firstFlag){
        printf("\tbin = (%d) ", i);
        firstFlag = 0;
      }
      printf("\t\tbddNode(%lx) ", (CalAddress_t)ptr);
      printf("thenId(%d) ", CalBddGetBddId(T)); 
      printf("thenBddNode(%lx) ", (CalAddress_t) CalBddGetBddNode(T));
      printf("elseId(%d) ", CalBddGetBddId(E)); 
      printf("elseBddNode(%lx) ", (unsigned long)CalBddGetBddNode(E));
      CalBddGetRefCount(calBdd, refCount);
      printf("refCount(%d)\n", refCount);
      ptr = CalBddNodeGetNextBddNode(ptr);
    }
  }
}

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

  Synopsis    [required]

  Description [optional]

  SideEffects [required]

  SeeAlso     [optional]

******************************************************************************/
void
CalHashTableOnePrint(CalHashTable_t *hashTable, int flag)
{
  int i;
  CalBddNode_t *ptr, *node;
  Cal_Bdd_t keyBdd;

  printf("*************************************************\n");
  for(i = 0; i < hashTable->numBins; i++){
    ptr = hashTable->bins[i];
    while(ptr != Cal_Nil(CalBddNode_t)){
      CalBddNodeGetThenBdd(ptr, keyBdd);
      node = CalBddNodeGetElseBddNode(ptr);
      if(flag == 1){
        printf("Key(%d %lx) Value(%f)\n", 
            CalBddGetBddId(keyBdd), (CalAddress_t)CalBddGetBddNode(keyBdd), *(double *)node); 
      }
      else{
        printf("Key(%d %lx) Value(%d)\n",
            CalBddGetBddId(keyBdd), (CalAddress_t)CalBddGetBddNode(keyBdd),  *(int *)node); 
      }
      ptr = CalBddNodeGetNextBddNode(ptr);
    }
  }
}

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

  Synopsis    [Initializer for the portable random number generator.]

  Description [Initializer for the portable number generator based on
  ran2 in "Numerical Recipes in C." The input is the seed for the
  generator. If it is negative, its absolute value is taken as seed.
  If it is 0, then 1 is taken as seed. The initialized sets up the two
  recurrences used to generate a long-period stream, and sets up the
  shuffle table.]

  SideEffects [None]

  SeeAlso     [CalUtilRandom]

******************************************************************************/
void
CalUtilSRandom(long seed)
{
    int i;

    if (seed < 0)       utilRand = -seed;
    else if (seed == 0) utilRand = 1;
    else                utilRand = seed;
    utilRand2 = utilRand;
    /* Load the shuffle table (after 11 warm-ups). */
    for (i = 0; i < CAL_STAB_SIZE + 11; i++) {
        long int w;
        w = utilRand / CAL_LEQQ1;
        utilRand = CAL_LEQA1 * (utilRand - w * CAL_LEQQ1) - w * CAL_LEQR1;
        utilRand += (utilRand < 0) * CAL_MODULUS1;
        shuffleTable[i % CAL_STAB_SIZE] = utilRand;
    }
    shuffleSelect = shuffleTable[1 % CAL_STAB_SIZE];
} /* end of CalUtilSRandom */

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

  Synopsis    [Portable random number generator.]

  Description [Portable number generator based on ran2 from "Numerical
  Recipes in C." It is a long period (> 2 * 10^18) random number generator
  of L'Ecuyer with Bays-Durham shuffle. Returns a long integer uniformly
  distributed between 0 and 2147483561 (inclusive of the endpoint values).
  The random generator can be explicitly initialized by calling
  CalUtilSRandom. If no explicit initialization is performed, then the
  seed 1 is assumed.]

  SideEffects []

  SeeAlso     [CalUtilSRandom]

******************************************************************************/
long
CalUtilRandom(void)
{
    int i;      /* index in the shuffle table */
    long int w; /* work variable */

    /* utilRand == 0 if the geneartor has not been initialized yet. */
    if (utilRand == 0) CalUtilSRandom((long)1);

    /* Compute utilRand = (utilRand * CAL_LEQA1) % CAL_MODULUS1 avoiding
    ** overflows by Schrage's method.
    */
    w          = utilRand / CAL_LEQQ1;
    utilRand   = CAL_LEQA1 * (utilRand - w * CAL_LEQQ1) - w * CAL_LEQR1;
    utilRand  += (utilRand < 0) * CAL_MODULUS1;

    /* Compute utilRand2 = (utilRand2 * CAL_LEQA2) % CAL_MODULUS2 avoiding
    ** overflows by Schrage's method.
    */
    w          = utilRand2 / CAL_LEQQ2;
    utilRand2  = CAL_LEQA2 * (utilRand2 - w * CAL_LEQQ2) - w * CAL_LEQR2;
    utilRand2 += (utilRand2 < 0) * CAL_MODULUS2;

    /* utilRand is shuffled with the Bays-Durham algorithm.
    ** shuffleSelect and utilRand2 are combined to generate the output.
    */

    /* Pick one element from the shuffle table; "i" will be in the range
    ** from 0 to CAL_STAB_SIZE-1.
    */
    i = shuffleSelect / CAL_STAB_DIV;
    /* Mix the element of the shuffle table with the current iterate of
    ** the second sub-generator, and replace the chosen element of the
    ** shuffle table with the current iterate of the first sub-generator.
    */
    shuffleSelect   = shuffleTable[i] - utilRand2;
    shuffleTable[i] = utilRand;
    shuffleSelect  += (shuffleSelect < 1) * (CAL_MODULUS1 - 1);
    /* Since shuffleSelect != 0, and we want to be able to return 0,
    ** here we subtract 1 before returning.
    */
    return(shuffleSelect - 1);

} /* end of CalUtilRandom */